【文章內(nèi)容簡介】 日 益膨脹和 IP地址的短缺，都預(yù)示著新一代網(wǎng)絡(luò)協(xié)議 IPv6必然在不久的將來被實施，因為 IPv6協(xié)議不僅可提供充足的地址空間，還能對路由前綴實施更好的聚合，以減小路由表規(guī)模。但是， IPv6協(xié)議的應(yīng)用也將給路由查找?guī)砗艽蟮奶魬?zhàn)，因為 IPv6的實施意味著 IP地址將從 32位迅速增加到 128位，而目前大多數(shù)成熟的算法都和 IP地址長度密切相關(guān)，有些算法根本無法適用于 IPv6。 路由查找現(xiàn)狀 路由查找是尋找最長前綴匹配的問題，其難點在于不僅需要考慮與地址前綴相匹配，而且還需要考慮地址前綴的長度。可以用基于硬件和軟件 兩種方法來實現(xiàn)路由查找。 基于硬件的查找算法分析 基于 RAM的路由查找方案是最簡單的基于硬件的查找算法，該方案是在 RAM中為所有的 IP地址都建立一個對應(yīng)的轉(zhuǎn)發(fā)表項。進行路由查找時，僅需要根據(jù)目的 IP地址進行檢索，一次訪存就可以找到對應(yīng)的路由信息。但這將造成轉(zhuǎn)發(fā)表空間的極大浪費，因此，這種方案在實際中并不可行。 目前使用最多的硬件實現(xiàn)方式是在基于 RAM技術(shù)的改進：內(nèi)容尋址存儲器 (ContentAddressableMemory，簡記 CAM)來進行快速的路由查找。 CAM能夠在一個硬件時鐘周期內(nèi)完 成關(guān)鍵字的精確匹配查找。常用的隨機存儲器通過輸入地址來返回該地址所對應(yīng)的數(shù)據(jù)信息，而 CAM的訪問方式不同，只需輸入關(guān)鍵字的內(nèi)容， CAM就會將此關(guān)鍵字與 C胡中所有的表項同時進行匹配比較，最后返回匹配表項在 CAM中所對應(yīng)的地址。這種方法有一個明顯的缺點，即在對地址前綴長度具體分布沒有準(zhǔn)確了解之前，為了保證能夠存儲 N個前綴表項，每個 CAM都需要有 N個表項的空間，因此，預(yù)留方案使得 CAM存儲空間的利用率大大降低了，而且成本昂貴。 為了能夠克服 CAM 方 法 的 缺 點 ， 又 有 一 種 CAM 實現(xiàn)機制 三態(tài)CAM(TernaryContent一 AddressableMemory，簡記 TCAM)提出來。 TCAM一個特殊的CAM硬件設(shè)備，是 CAM實現(xiàn)機制的改進。結(jié)構(gòu)同 CAM一樣，由一個二維陣列組成，陣列中的每一行對應(yīng)存儲器的一個槽，槽的大小依照不同的應(yīng)用設(shè)置成 64bits、 72bits或 128bits及更高的比特位大小。它能起到和完全相關(guān)聯(lián)存儲器一樣的功用。 TCAM的優(yōu)點是它保存的表項在長度要求上非常靈活，可以在同一個 TCAM芯片中保存任意長度的關(guān)鍵字表項。 TCAM具有實現(xiàn)簡單、查找速度快的優(yōu)點，它使用并行技術(shù)，查找復(fù)雜度僅為 O(1)， 但 TCAM最大的不足之處在于其造價昂貴、集成度低和高功耗。 基于軟件的查找算法分析 基于 Binary Trie 的 IP 地址查找算法研究與實現(xiàn) 4 基于軟件的路由查找算法有很多種，現(xiàn)按照算法實現(xiàn)的數(shù)學(xué)模型，對一些經(jīng)典的路由查找算法做簡要介紹。 基于線性查找：路由表內(nèi)的表項按照簡單的線性排列方式組織，查找將待查找的IP地址和數(shù)據(jù)庫內(nèi)的前綴逐一進行比較，直到匹配為止。這種算法實現(xiàn)非常簡單，而且存儲代價也并不高，適用于低速要求下非常小規(guī)模的路由表實例。然而，此算法不可能被廣泛采用，特別是對于速度要求嚴(yán)苛的環(huán)境，因為其時間復(fù)雜度和路由表的規(guī)模成正比，其期望值是 N/2；其空間復(fù)雜度為 O(NW)(其中 W為最長前綴長度 )。 基于 Trie結(jié)構(gòu)的查找：根據(jù)前綴的二進制比特值，構(gòu)建二叉樹或二的次叉樹，根據(jù)前綴的二進制比特值將其關(guān)聯(lián)的存儲在分叉樹上。檢索將待查找的 IP地址的二進制比特值作為索引，在 Trie樹數(shù)據(jù)結(jié)構(gòu)上索得到相應(yīng)的前綴以及對應(yīng)的下一跳路由信息。 二分 /多分查找：根據(jù)前綴的一些特性，例如前綴長度、前綴區(qū)間等，先將前綴進行預(yù)分割處理，并構(gòu)造相應(yīng)的決策樹，將前綴存儲在決策的不同分支。查找時，利用待匹配目的 IP地址對應(yīng)的屬性值，在決策上進行搜索，得到與之匹配的最佳表 項。 基于哈希表結(jié)構(gòu)的查找：根據(jù)前綴某個指定屬性的哈希函數(shù)值，構(gòu)造希表對前綴進行存儲組織。查找時根據(jù)待匹配目的 IP地址的哈希值進哈希索引，進而得到匹配結(jié)果。由于哈希沖突的存在，基于哈希表的法通常需結(jié)合其它的算法思想，或常被融入到眾多算法的思想精髓里。 規(guī)避查找技術(shù)：通過利用查找任務(wù)的某些局部性特征，或者對查找任進行特定的轉(zhuǎn)化和重新分配，使得某些查找任務(wù)可以被簡化或規(guī)避，而減小路由查找的壓力，以滿足高性能的需求。 基于 Trie 結(jié)構(gòu)的路由算法的介紹 下面對基于 Trie結(jié)構(gòu)的基于 Binary Trie的路由算法（在第二章重點介紹）、路徑壓縮（ PathCompressed） Trie算法、多比特 Trie算法、級壓縮 Trie（ LCTrie）算法、位圖壓縮（ BitmapCompressed） Trie算法進行簡要介紹。 Binary Trie 的路由算法 基于 Binary Trie 的 IP 地址查找算法研究與實現(xiàn) 5 圖 13路由前綴集用例以及對應(yīng)的二進制 Trie算法數(shù)據(jù)結(jié)構(gòu) 基本的二進制 Trie 數(shù)據(jù)結(jié)構(gòu)早在 20 世紀(jì) 70 年代就被提出，這種 Trie 的每個結(jié)點最多包含 2 個指針，分別指向他的左右孩子結(jié)點，代表前綴的某個比特位為‘ 0’和‘ 1’時兩種情況 的搜索分支。在 Trie 樹中，處于第 L 層的結(jié)點實際上代表了一類地址前 L1 比特均相同的地址空間，如圖 13 所示。查找搜索時，根據(jù)待查找 IP 地址的比特位，從 Trie 樹的根結(jié)點開始依次向其子孫結(jié)點進行，直到再無分支可搜索為止，其間記錄的最后一個前綴結(jié)點對應(yīng)的路由信息就是查找結(jié)果?；镜亩M制Trie 數(shù)據(jù)結(jié)構(gòu)構(gòu)造的 Trie 最多有 W+1 層，因此每次搜索的次數(shù)最多為 W 次，所以查找時間復(fù)雜度是 O(W)；存儲一個前綴，最多可能產(chǎn)生 W 個 Trie 結(jié)點，因而該算法的存儲復(fù)雜度為 O(WN)。 路徑壓縮 Trie 算法 要提 高查找速度、減少存儲器訪問操作的次數(shù)，必須降低 Trie樹的高度。降低 Trie樹高度的一種方法是使用路徑壓縮技術(shù)。路徑壓縮是 1968年 提出的一種叫做 PATRICIA的算術(shù)編碼算法基礎(chǔ)上，提出的一種稱為路徑壓縮 Trie的最長前綴路由查找算法。 很明顯，在二進制 trie樹中存在著許多不含轉(zhuǎn)發(fā)信息的中間結(jié)點。從地址前綴分布的特點可知，到目前為止還沒有長度小于 8比特的地址前綴，即便是長度介于 915比特之間的前綴也并不多，這就使得二進制 Trie樹的前若干層主要是由那些不含轉(zhuǎn) 發(fā)信息的中間結(jié)點組成。路徑壓縮的 Trie樹是對樹的層次進行壓縮，來減小樹的深度。由于某些結(jié)點被刪除，查找過程中不是逐位對比，而是維護一個位變量指示下一個需要檢查的比特位。為了恢復(fù)原有信息，路徑壓縮 Trie樹需要保存地址前綴的比特串。 基于 Binary Trie 的 IP 地址查找算法研究與實現(xiàn) 6 圖 14路徑壓縮 Trie算法數(shù)據(jù)結(jié)構(gòu) 當(dāng)二進制 Trie樹稀疏時，有許多內(nèi)部結(jié)點具有單個的分支，當(dāng)訪問這樣的結(jié)點時，沒有分支決策，僅有的操作是當(dāng)這個結(jié)點對應(yīng)路由表中的一個前綴時記錄下一跳信息，使得 Trie有一個高的空間復(fù)雜度和大的查找時間。為了降低存儲需求，縮短 Trie樹的深度（查找時間），路徑壓縮 Trie中去掉了所有具有單個分支的內(nèi)部結(jié)點（不包括含有前綴的結(jié)點）。圖 14給出了路徑壓縮 Trie算法的一個示例（采用與圖 13中相同的前綴集）。前綴結(jié)點 b和 e都處于一個“單分支并且內(nèi)部不包含前綴結(jié)點的子 Trie結(jié)構(gòu)”的末端，因而對應(yīng)的單分支 Trie結(jié)構(gòu)被壓縮掉。為了保證查找正確，在結(jié)點中增加兩個域： Bitposition，表示下一個要比較的字符位； Bitstring，表示從根到該結(jié)點位置的路徑對應(yīng)的位串。路徑壓縮 Trie的每一個葉子結(jié)點 含有一個路由前綴和一個下一跳信息指針。當(dāng)遍歷一個路徑壓縮時間 Trie查找一個地址時，將結(jié)點中的位串與待查找的地址比較。如果該位串是地址的一個前綴，則存儲下一跳信息指針 (如果存在 )并且轉(zhuǎn)向下一個結(jié)點。當(dāng)比較失敗或者到達(dá)葉子結(jié)點時，查找終止。此時，最近記錄的下一跳信息指針作為結(jié)果被返回。事實上，對于非前綴內(nèi)部結(jié)點，路徑壓縮 Trie中的位串并不是必需的，增加這樣的信息有助于盡早終止查找，從而提高平均查找性能。 路徑壓縮 Trie減少了對 Trie結(jié)構(gòu)查找的平均次數(shù)，但最壞情況下，路徑中可能不存在單分支結(jié)構(gòu)，因此查找時 間復(fù)雜度仍為 O(W)；最壞情況下，沒有分支被壓縮，因而存儲復(fù)雜度還是 O(NW)。事實上，路徑壓縮 Trie僅當(dāng)二進制 Trie樹稀疏時其性能較優(yōu)。隨著前綴個數(shù)的增加以及二進制 Trie樹變得稠密，使用路徑壓縮 Trie的改進性能降低。 多比特 Trie 算法 基本二進制 Trie算法在查找時每次僅檢查 IP地址的一個比特，查找速度較慢。多比特 Trie算法在查找過程的每一步檢查多個比特，加速查找的進程，其中每步檢查的比特數(shù)定義為搜索步長。如圖 15所示，該多比特 Trie的第一層上有 8個分支，對應(yīng)的搜索步長 為 3；而在第二層，每個結(jié)點有 4個分支，對應(yīng)的搜索步長為 2。我們看到，整個 Trie樹僅有 2層，即最多僅需 2次多分支 Trie搜索就可以得到最終匹配結(jié)果，相比基于 Binary Trie 的 IP 地址查找算法研究與實現(xiàn) 7 基本二進制 Trie在性能上有了較大的改進。一般的， k比特（即每層都有 2k個分支的）Trie的查找時間復(fù)雜度是 O(W/k)。另一方面，我們注意到，多比特 Trie不能支持任意長度的地址前綴，如圖 15的例子，該多比特 Trie僅支持長度為 3和 5的前綴，為了能夠用多比特 Trie來進行前綴查找，路由表中的地址前綴需要被擴展成這兩種長度。這種擴展帶來了存儲的冗余度，增加 了存儲復(fù)雜度。最壞情況下，存儲復(fù)雜度為 O(N 2k W/k)。 圖 15多分支 Trie的數(shù)據(jù)結(jié)構(gòu)示意 針對常規(guī)的多比特 Trie浪費存儲空間的問題， 壓縮 Trie（ LevelCompressed Trie）的算法。該算法的主要思想是：靈活的為 Trie的各個層、各個分支按照前綴集分布特點自適應(yīng)選定不同的搜索步長：當(dāng)子 Trie結(jié)構(gòu)分支是滿 2L叉樹時，才使用步長 L。這樣既能發(fā)揮多比特 Trie的優(yōu)勢，同時由于子 Trie結(jié)構(gòu)本來就是滿 2L叉樹，不會產(chǎn)生結(jié)點復(fù)制。但我們也注意到 ，層壓縮 Trie僅在 Trie結(jié)點分布較為密集時才較為有效。 級壓縮 Trie（ LCTrie）算法 如上所述，路徑壓縮 Trie適合于結(jié)點稀疏的情況。 Nilsson ET AL提出了一種級壓縮技術(shù)用于結(jié)點稠密的情況。這種技術(shù)被稱為級壓縮 Trie，簡稱 LC一 Trie。 LC一 Trie結(jié)合路徑壓縮和多位 Trie的特點進一步優(yōu)化基本 Trie結(jié)構(gòu)。 LC壓縮樹中每個內(nèi)部結(jié)點的孩子結(jié)點都是連續(xù)存放的，父結(jié)點只存放左孩子指針，每個父結(jié)點還存放分支(branch)信息，如果父結(jié)點有 8個孩子結(jié)點，分支記錄將是