大類的技術手記

IP Lookup 演算法 - Multibits Trie

  • 分類:
  • 字數:雞 x 0雞數:計算文長的常見計量單位,一般而言數字大小與文章長度呈正相關

「Binary Trie」這個演算法非常簡單易懂,而且也相當好實作。但在搜尋的速度上, 仍有許多待改進的空間,最大的問題在於「Binary Trie」這個演算法建立的二元搜尋樹太深了! 1 個位元一層, 32 個位元就可能要往下 32 層,也就是說可能就要比較 32 次才會得到結果, 自然效果不太好。

於是有人問了:「為什麼要這麼麻煩呢?既然一個位元一個位元比較速度不夠快, 那一次比較好幾個位元不就得了?」

於是「Multibits Trie」這個演算法因應而生,它的概念和「Binary Trie」沒什麼不同, 差別在「Multibits Trie」會一次比較多個位元來減少層數,用這種方法增加搜尋的速度。

https://marco79423.net/backend/static/cfe6d8b2-2b3f-11ed-a9be-0242ac110003/

「stride」代表一次看幾個位元,所以上圖左代表「stride」為 2 的樹。 理論上「stride」值越多,樹的層數也會相應得變少。

不過這樣一來,就會產生新的問題,其實從圖中就可以看得出來,雖然層數變少了, 但是節點數卻增加了!換言之,就是所需要的記憶體增加了!為什麼會發生這種情況呢? 原因很簡單,因為本來「Binary Trie」是一個位元一個位元比較, 一直比到 Prefix 的長度為止(因為超過 Prefix 的長度的話,之後不管值是什麼都沒關係)。

但「Multibits Trie」是一次看數個位元,很可能會碰到要比較位元已經超過 Prefix 長度的情況, 好比說我一次看 2 個位元,但後面的位元本來是不用看的。

如下表

Prefix Nexthop
1*** 粉紅色的出口

(這個例子中,只要看 1 個位元即可,後面都不需要看,但若我是要 2 個位元 2 個位元看, 第 2 個位元就超過 Prefix 長度了)

那怎麼辦呢?解決問題的方法也很簡單,比如說剛剛的例子, 只要列出所有的長度既是「stride」的倍數,而且又能包含原來 Prefix 的所有可能的新 Prefix 即行了。

像剛才的例子,就可以用新的兩條規則取代舊的規則,如下表

Prefix Nexthop
10** 粉紅色的出口
11** 粉紅色的出口

這樣一來,意義不變,但是卻可以方便我們建立節點。

不過用這種方法又會產生新的問題,因為規則的 Prefix 是我們自己變長的(上例是從 1 變 2), 所以若碰到原來 Prefix 就是 2,而且又是共用同一個節點存放「Nexthop資訊」時, 就會有優先權的問題。幸好這個問題也很好解決,只要紀錄原來的 Prefix 長度, 等到碰到共用同一個節點的情況時,比較原來的 Prefix 長度,把舊的蓋掉即可。

關於搜尋的範例程式碼

def search(root, ip, stride):
    current = root
    nexthop = root.nexthop #預設值,此例直接把預設值放在 root 中。

    length = 0
    while length < 32 and current:
        length += stride #Binary Trie 時是一次 shift 1,現在是一次 stride 個
        index = (ip >> (32 - length)) & (pow(2, stride) - 1)
        current = current.children[index]

        if current and current.nexthop != None:
            nexthop = current.nexthop

    return nexthop

若比較「Binary Trie」的搜尋的程式碼,就會發現兩者非常相似, 差別在於一次看的的位元數目不同而已,還有「Binary Trie」每個節點都只會有兩個子節點, 「Multibits Trie」則會因「stride」不同而有不同的子節點數目僅此而已。

因此在「Binary Trie」中,我取「left」、「right」代表左子節點和右子節點, 而在「Multibits Trie」時,因為不會只有兩個子節點,所以用串列「children」代表子節點。

接下來是建立樹的部分,概念上和「Binary Trie」大同小異,只是多了兩個關鍵點,分別是:

  • 把長度不是「stride」的倍數的 Prefix 展開成多個 Prefix
  • 碰到 Prefix 長度相同的規則比較其優先權(自己變的當然優先權會比較小)
def create_tree(entrys, stride):
    root = Node(stride)

    #prefix, nexthop 表各別的規則
    for prefix, nexthop in entrys:

        # /0 表預設值
        if entry.prefix.length == 0:
            root.nexthop = nexthop
            root.length = prefix.length #紀錄 prefix 的長度,之後可以用來比較優先權
        else:

            #bit_count 表不足一個 stride 的位元個數
            bit_count = (32 - prefix.length) % stride

            #把長度不是「stride」的倍數的 Prefix 展開成多個 Prefix
            new_prefixs = []
            if bit_count != 0:
                for i in range(pow(2, bit_count)):
                    new_prefix = Prefix()
                    new_prefix.length = prefix.length + bit_count

                    new_prefix.ip = prefix.ip >> (32 - prefix.length) << (32 - prefix.length)
                    new_prefix.ip += i << ( 32 - new_prefix.length)

                    new_prefixs.append(new_prefix)
            else:
                new_prefixs.append(prefix)

            for new_prefix in new_prefixs:
                current = root
                length = 0
                while length < new_prefix.length:
                    length += stride
                    index =  (new_ip >> (32 - length)) & (pow(2, stride)-1)
                    if current.children[index] == None:
                        current.children[index] = Node(stride)
                    current = current.children[index]

                #用 prefix 的長度比較優先權
                if prefix.length > current.length:
                    current.nexthop = nexthop
                    current.length = prefix.length

「Multibits Trie」演算法可以有效的增加搜尋的速度,不過代價是必須要付出更多的記憶體。 這個演算法非常實用,建立、更新、搜尋都有不錯的效果,根據我導師的說法,雖然這個演算法非常基本, 但現在業界其實都是只在用這種演算法而已。

所以說,有研究相關領域的人,這個演算法鐵定要非常熟悉才是。