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