Trie樹(shù)路由查找算法在網(wǎng)絡(luò)處理器中的實(shí)現(xiàn)

張 琦，金胤丞，李 苗，章建雄

(中國(guó)電子科技集團(tuán)公司第三十二研究所，上海 200233)

1 概述

國(guó)際互聯(lián)網(wǎng)絡(luò)規(guī)模的高速增長(zhǎng)對(duì) IP(Internet Protocol)路由查找算法處理大容量路由表的適應(yīng)性提出了更高要求，骨干路由器每秒所需轉(zhuǎn)發(fā)的報(bào)文數(shù)隨之劇增，IP路由查找算法的優(yōu)劣直接影響了當(dāng)前和未來(lái)互聯(lián)網(wǎng)的整體性能[1]。此外，隨著網(wǎng)絡(luò)系統(tǒng)的發(fā)展，現(xiàn)有網(wǎng)絡(luò)系統(tǒng)的瓶頸越來(lái)越明顯，為了解決這些問(wèn)題，研究者提出了網(wǎng)絡(luò)處理器(Network Processor, NP)解決方案。網(wǎng)絡(luò)處理器是面向網(wǎng)絡(luò)應(yīng)用領(lǐng)域的專(zhuān)用指令處理器，是面向數(shù)據(jù)分組處理的、具有特定電路的軟件可編程器件。它將RISC(Reduced Instruction Set Computer)處理器的低成本、靈活性與ASIC (Application Specific Integrated Circuit)專(zhuān)用網(wǎng)絡(luò)處理芯片的高性能、可擴(kuò)展性很好地結(jié)合在一起[2]。網(wǎng)絡(luò)處理器中查找微引擎的設(shè)計(jì)是處理速度提升的關(guān)鍵，所以，查找微引擎中路由查找算法的研究對(duì)實(shí)現(xiàn)高速網(wǎng)絡(luò)處理器具有直接和重要的意義。

另外，在此網(wǎng)絡(luò)環(huán)境下查找算法應(yīng)滿(mǎn)足下列條件：(1)存儲(chǔ)器訪(fǎng)問(wèn)最壞情況下應(yīng)不大于一個(gè)合理的、確定的次數(shù)，平均訪(fǎng)問(wèn)次數(shù)應(yīng)滿(mǎn)足轉(zhuǎn)發(fā)速率的要求。(2)確定合理的最壞情況路由表更新操作，不影響正常轉(zhuǎn)發(fā)速率所要求的路由表查找操作。(3)具有較高的存儲(chǔ)空間利用率。對(duì)于一定的路由表表項(xiàng)深度，所占的存儲(chǔ)空間應(yīng)盡可能小，且路由表的大小對(duì)算法的查找性能影響不大。(4)實(shí)現(xiàn)所需的物理器件應(yīng)有較低的成本，適合應(yīng)用于實(shí)際的產(chǎn)品。(5)數(shù)據(jù)結(jié)構(gòu)與查找操作相對(duì)簡(jiǎn)單，適合于硬件實(shí)現(xiàn)[4]。

本文提出一種 IP路由查找算法應(yīng)用于交換速率為10 Gb/s的網(wǎng)絡(luò)處理器中，按照每個(gè)數(shù)據(jù)包長(zhǎng)度為80 Byte計(jì)算，如果要實(shí)現(xiàn)線(xiàn)速轉(zhuǎn)發(fā)，則至少需要達(dá)到10 Gb/s/((80+12)×8)=13.58 Mb/s的路由查找速率[3]。

2 路由查找算法分析

實(shí)現(xiàn)地址最長(zhǎng)前綴匹配是路由查找算法的難點(diǎn)，在前綴匹配的過(guò)程中要考慮地址前綴的長(zhǎng)度以及地址前綴的值，現(xiàn)有的路由查找算法都可以歸結(jié)為這 2個(gè)方面的匹配查找過(guò)程。具體的，基于地址前綴長(zhǎng)度的路由查找算法考慮的是在長(zhǎng)度空間內(nèi)進(jìn)行查找，可以在查找過(guò)程中使用線(xiàn)性遍歷法或者二分遍歷法；基于地址前綴值的路由查找算法為消除地址前綴長(zhǎng)度對(duì)查找的影響，采取窮舉整個(gè)地址前綴空間地址關(guān)鍵字的方法。

常用的路由查找算法主要有基于線(xiàn)性表查找結(jié)構(gòu)的線(xiàn)性查找算法、基于Hash表結(jié)構(gòu)的路由查找算法、基于Trie結(jié)構(gòu)的路由查找算法[5]。

基于 Trie樹(shù)的算法[6]因?yàn)榫哂休^好的查找速度、時(shí)間復(fù)雜度和空間復(fù)雜度，并且還能適應(yīng)不斷提高的路由器性能要求，所以現(xiàn)代快速的路由查找算法都是基于Trie樹(shù)算法優(yōu)化實(shí)現(xiàn)的，如路徑壓縮Trie樹(shù)算法、多分支Trie樹(shù)算法以及基于Trie樹(shù)的前綴擴(kuò)展等策略的算法。假設(shè)地址關(guān)鍵字長(zhǎng)度為 W，地址前綴表中前綴數(shù)目為 N，則有如表 1所示的典型算法復(fù)雜度分析列表。

表1 典型算法的復(fù)雜度分析

對(duì)于基于Trie樹(shù)的算法，樹(shù)高決定了訪(fǎng)存次數(shù)，從而決定了算法的時(shí)間性能。對(duì)于路徑壓縮Trie樹(shù)算法，與二進(jìn)制樹(shù)算法一樣，查找過(guò)程中需要大量的存儲(chǔ)器訪(fǎng)問(wèn)操作。對(duì)IPv4來(lái)說(shuō)，一顆完整Trie樹(shù)的深度是32，最壞情況下需要32次存儲(chǔ)器訪(fǎng)問(wèn)。而多分支Trie樹(shù)算法采用大于1的查找步寬，從根本上降低了樹(shù)的高度，查找性能得到很大程度的提高。

事實(shí)上，IP路由查找算法很難同時(shí)滿(mǎn)足查找速度、更新速度、空間利用率等 3個(gè)方面的要求。傳統(tǒng)上僅采用一種算法或者方法會(huì)導(dǎo)致查找性能受到一定的限制，即便可以實(shí)現(xiàn)很快的查找速度，往往也有轉(zhuǎn)發(fā)表更新困難或者擴(kuò)展性差等問(wèn)題[7]。

本文提出基于查找速度快且易于硬件實(shí)現(xiàn)的Trie樹(shù)的路由查找算法，吸取壓縮Trie樹(shù)和多分支Trie樹(shù)的優(yōu)點(diǎn)，通過(guò)一些軟件建樹(shù)和硬件查找策略，以在上述 3個(gè)方面取得平衡優(yōu)勢(shì)。

3 路由算法實(shí)現(xiàn)

3.1 IP地址前綴的樹(shù)型結(jié)構(gòu)表示

本文提出一種基于最優(yōu)平衡、多層存儲(chǔ)的Trie樹(shù)算法，即建立一種平衡的壓縮樹(shù)結(jié)構(gòu)；然后將該樹(shù)中相鄰的多層節(jié)點(diǎn)壓縮到一個(gè)存儲(chǔ)節(jié)點(diǎn)中。其中借鑒了Patricia Trie樹(shù)數(shù)據(jù)結(jié)構(gòu)思想[8]，即通過(guò)路徑壓縮算法刪除路徑上的一些單去向節(jié)點(diǎn)，經(jīng)過(guò)選列(即被選測(cè)試位)壓縮了冗余節(jié)點(diǎn)，而樹(shù)搜索時(shí)僅對(duì)被選位進(jìn)行測(cè)試比較，大大減少了測(cè)試比較次數(shù)，以及內(nèi)存占用空間和訪(fǎng)存次數(shù)。一個(gè)Patricia Trie樹(shù)結(jié)構(gòu)如圖1所示。

圖1 Trie樹(shù)結(jié)構(gòu)舉例

建樹(shù)過(guò)程的具體實(shí)現(xiàn)步驟如下：

(1)每次建立一顆子樹(shù)后，開(kāi)始消除不考慮的條目。即從所有條目中剔除不能夠和其他條目區(qū)分的條目，壓縮冗余信息。

(2)選列。即查找條目中的一個(gè)或多個(gè)有不同的指定值的列。首先，被選列必須是既有“0”又有“1”的列(才有分支的可能)。其次，列中“0”和“1”的數(shù)目應(yīng)較多且相近，以把較多的規(guī)則分開(kāi)到 2個(gè)不同的組中，“0”表示走向左子樹(shù)或葉子；“1”表示走向右子樹(shù)或葉子；“*”表示范圍域的范圍之內(nèi)，或是掩碼值域的掩碼未作屏蔽，故走向左、右子樹(shù)或葉子均可。

(3)若步驟(2)查找條件匹配，應(yīng)先選擇含有通配符“*”數(shù)目最少的列。若這樣的列僅有一個(gè)，直接進(jìn)入步驟(5)。若滿(mǎn)足條件的列有多個(gè)，則采用子樹(shù)內(nèi)部關(guān)鍵字的最優(yōu)平衡準(zhǔn)則建樹(shù)。

圖2是采用平衡準(zhǔn)則建立的一顆子樹(shù)，與圖1中普通的Patricia Trie子樹(shù)相比較，平衡準(zhǔn)則優(yōu)先把含通配符數(shù)目較多的關(guān)鍵字置于深度較小的子樹(shù)中，以達(dá)到降低關(guān)鍵字平均搜索深度的目的。

圖2 最優(yōu)平衡子樹(shù)建立

(4)若步驟(2)查找條件不匹配，算法檢查當(dāng)前條目集合是否能插入一個(gè)葉子。若可以，則建立葉子并定義為葉子節(jié)點(diǎn)，子樹(shù)建立完成。否則，如當(dāng)條目集合超過(guò)1000個(gè)時(shí)，超過(guò)了硬件限制的葉子數(shù)量則無(wú)法插入新的葉子。

(5)選擇條目的值為 0建立左子樹(shù)，選擇條目的值為 1建立右子樹(shù)，然后采用遞歸的方式回到步驟(1)。每當(dāng)建立新子樹(shù)，將新子樹(shù)鏈接為當(dāng)前節(jié)點(diǎn)的孩子，并且定義為內(nèi)部節(jié)點(diǎn)，內(nèi)部節(jié)點(diǎn)不含關(guān)鍵字路由信息。所提出的樹(shù)的結(jié)構(gòu)和算法中建樹(shù)部分解決了 2個(gè)問(wèn)題：含有通配符條目的編入與不同長(zhǎng)度條目的編入。

當(dāng)樹(shù)建立之后，將其按照如圖3所示的結(jié)構(gòu)進(jìn)行存儲(chǔ)，在圖3(a)中，樹(shù)結(jié)構(gòu)被分成若干子樹(shù)進(jìn)行存儲(chǔ)，每一棵子樹(shù)放在一個(gè)存儲(chǔ)單元中，只需要進(jìn)行一次訪(fǎng)存操作，一棵子樹(shù)包含多個(gè)存儲(chǔ)節(jié)點(diǎn)，能實(shí)現(xiàn)多位關(guān)鍵字查找；故而在進(jìn)行數(shù)據(jù)查找的過(guò)程中，一次訪(fǎng)存可以進(jìn)行多次數(shù)據(jù)查找，如圖 3(b)所示，在該子樹(shù)結(jié)構(gòu)所代表的結(jié)構(gòu)中，一個(gè)存儲(chǔ)單元為256位，代表了樹(shù)結(jié)構(gòu)中3層，即可以對(duì)關(guān)鍵字進(jìn)行3次查找，縮短訪(fǎng)存時(shí)間。

圖3 樹(shù)形結(jié)構(gòu)

3.2 硬件路由查找過(guò)程

子樹(shù)信息位于存儲(chǔ)器中，首先提取一個(gè)子樹(shù)的地址，然后根據(jù)地址從內(nèi)部存儲(chǔ)器中取出相應(yīng)的數(shù)據(jù)。根據(jù)解析表相應(yīng)位，確定該樹(shù)型結(jié)構(gòu)的拓?fù)鋱D。解析拓?fù)浣Y(jié)構(gòu)圖，判斷是否為該子樹(shù)的葉節(jié)點(diǎn)。若是繼續(xù)下一步，否則繼續(xù)解析。接著判斷是否為整棵樹(shù)的葉節(jié)點(diǎn)。若是，從外部存儲(chǔ)器中讀出相應(yīng)的數(shù)據(jù)。若否，遞歸方式重新提取子樹(shù)地址。最后將讀出值的葉子節(jié)點(diǎn)值比較。若一致，返回查找結(jié)果，若不一致，返回默認(rèn)值。

基于Trie的硬件路由查找過(guò)程狀態(tài)機(jī)如圖4所示。

圖4 樹(shù)查找狀態(tài)機(jī)

硬件路由的查找過(guò)程如下：

(1)MEM_ACCESS

首先確定根節(jié)點(diǎn)的值，根節(jié)點(diǎn)地址都存儲(chǔ)在片內(nèi)寄存器中。提取一個(gè)子樹(shù)的地址，然后根據(jù)地址從內(nèi)部存儲(chǔ)器中取出相應(yīng)的 256位數(shù)據(jù)。每一棵子樹(shù)的存儲(chǔ)信息為256位，其代表的含義如圖5所示。

圖5 節(jié)點(diǎn)數(shù)據(jù)字段解析

(2)SUB_LEAF

讀出該節(jié)點(diǎn)的值后，根據(jù)圖中拓?fù)浣Y(jié)構(gòu)描述符Descriptor[4:1]，判斷每一棵子樹(shù)所對(duì)應(yīng)的拓?fù)鋱D，解析出該4位所對(duì)應(yīng)的值value[7:0]，根據(jù)value的值從低位到高位，確定拓?fù)浣Y(jié)構(gòu)，value[i]的值表明該節(jié)點(diǎn)是否為該子樹(shù)的葉子節(jié)點(diǎn)，1表示是；0表示否；非葉子節(jié)點(diǎn)可以?huà)旖恿硗?個(gè)偽節(jié)點(diǎn)；在葉子節(jié)點(diǎn)上，掛接2個(gè)另外的二級(jí)子樹(shù)的根地址或者整棵樹(shù)的葉子。例如：Descriptor[4:1]為0001時(shí)，value[7:0]為 01101010，那么該的樹(shù)的拓?fù)浣Y(jié)構(gòu)如圖 6所示，同理，還存在其他8種樹(shù)的拓?fù)浣Y(jié)構(gòu)。

圖6 子樹(shù)拓?fù)浣Y(jié)構(gòu)

根據(jù)解析的拓?fù)浣Y(jié)構(gòu)圖，判斷是否為該子樹(shù)的葉節(jié)點(diǎn)。若是，繼續(xù)下一步，否則繼續(xù)解析直到葉節(jié)點(diǎn)為止。

(3)TREE_LEAF

判斷是否為整棵樹(shù)的葉節(jié)點(diǎn)。對(duì)讀出值進(jìn)行判斷是否為整棵樹(shù)的葉子節(jié)點(diǎn)時(shí)，即根據(jù)圖 2中[75:68]位，判斷二級(jí)子樹(shù)中對(duì)應(yīng)的結(jié)構(gòu)為整棵樹(shù)葉子節(jié)點(diǎn)或者二級(jí)子樹(shù)，1表明為葉子，0表明為二級(jí)子樹(shù)。若是，當(dāng)為整棵樹(shù)的葉子節(jié)點(diǎn)時(shí)，利用圖 2中[83:76]位確定從內(nèi)部或者外部存儲(chǔ)器中讀出數(shù)據(jù)，讀出該地址所對(duì)應(yīng)的值。若否，遞歸回到步驟(1)。

(4)COMPARE

將讀出值與上一級(jí)輸入的 key(包含 IP地址的關(guān)鍵字)的相應(yīng)值比較。

(5)OUT

如果相等，則證明查找到結(jié)果，返回查找結(jié)果result(包含路由等信息的結(jié)果)；如果不相等，則證明查找出錯(cuò)，返回默認(rèn)的值。當(dāng)為二級(jí)子樹(shù)時(shí)，返回到步驟(1)繼續(xù)開(kāi)始做，直至找到葉子節(jié)點(diǎn)的值為止。

3.3 算法硬件的實(shí)現(xiàn)

該網(wǎng)絡(luò)處理器有解析、查找、解決、修改 4種類(lèi)型的微引擎，每個(gè)都被優(yōu)化執(zhí)行一個(gè)特殊的任務(wù)，實(shí)現(xiàn)對(duì)數(shù)據(jù)包的分類(lèi)、轉(zhuǎn)發(fā)和修改，本文算法在查找微引擎中實(shí)現(xiàn)。微引擎采用一種獨(dú)特的體系結(jié)構(gòu)，帶一個(gè)定制的、特殊功能的數(shù)據(jù)通路和指令集。這減少了復(fù)雜數(shù)據(jù)包操作需要的時(shí)鐘周期數(shù)目，提供相當(dāng)快速的數(shù)據(jù)包處理。微引擎性能受益于超標(biāo)量結(jié)構(gòu)，多個(gè)實(shí)例在每個(gè)流水段并行運(yùn)行。查找微引擎接收解析微引擎輸入的查找關(guān)鍵字key，以及各種查找結(jié)構(gòu)的匹配，執(zhí)行對(duì)表的查找。查找結(jié)構(gòu)存儲(chǔ)在若干內(nèi)部和外部存儲(chǔ)器中。查找微引擎將最終的查找結(jié)果result傳遞到下一級(jí)微引擎處理。

如圖 7所示，算法硬件采用 65 nm工藝實(shí)現(xiàn)，包含三大模塊：處理器模塊，I/O模塊，存儲(chǔ)器模塊。處理器模塊包含 4個(gè)并行處理查找微引擎；存儲(chǔ)器模塊包含指令存儲(chǔ)器和數(shù)據(jù)存儲(chǔ)器，數(shù)據(jù)存儲(chǔ)器分為內(nèi)部存儲(chǔ)器和外部存儲(chǔ)器，分別采用SRAM和DRAM實(shí)現(xiàn)，微引擎從數(shù)據(jù)存儲(chǔ)器中的樹(shù)型結(jié)構(gòu)中獲取所需要的信息。

圖7 算法實(shí)現(xiàn)的硬件結(jié)構(gòu)

4 仿真與性能分析

4.1 算法仿真驗(yàn)證

查找算法采用 Verilog HDL語(yǔ)言編寫(xiě)，開(kāi)發(fā)環(huán)境為Xilinx公司ISE14.1軟件，仿真工具為QuestaSim 6.6a。通過(guò)隨機(jī)輸入key=0h09004200進(jìn)行測(cè)試，即作為輸入的目的IP地址(在存儲(chǔ)器中key的存儲(chǔ)是按低字節(jié)在左)。如圖8方框所示，該key(0h00420009)在路由表中對(duì)應(yīng)的路由查找信息 result為 0h0300000009000009000000410009FC00。圖 9為路由查找的時(shí)序仿真圖，key_reg和result_reg分別為查找key和查找最終返回值。圖8和圖9的結(jié)果驗(yàn)證了查找電路時(shí)序正確，實(shí)現(xiàn)了所設(shè)計(jì)的路由查找功能[9]。

圖8 存儲(chǔ)器中的路由表信息

圖9 仿真驗(yàn)證結(jié)果

4.2 算法性能分析

影響路由查找算法性能的主要因素是查找時(shí)間復(fù)雜度、存儲(chǔ)器復(fù)雜度和更新時(shí)間復(fù)雜度[10]。對(duì)于查找時(shí)間復(fù)雜度，首先實(shí)現(xiàn)了創(chuàng)新壓縮算法，減少查找的地址前綴長(zhǎng)度。其次提議算法比其他壓縮二進(jìn)制樹(shù)更進(jìn)一步，本文一次訪(fǎng)存可以進(jìn)行 3次數(shù)據(jù)查找，減少典型查找的次數(shù)到正常需要查找操作的 1/3，即存儲(chǔ)器訪(fǎng)問(wèn)次數(shù)為原來(lái) 1/3。對(duì)于子樹(shù)的查找，查找步長(zhǎng)可變，其查找時(shí)間復(fù)雜度為O(子樹(shù)的深度)≈O(logN)，存儲(chǔ)空間復(fù)雜度為 O(1)。對(duì)于整棵樹(shù)，若查找步長(zhǎng)為 k，時(shí)間復(fù)雜度為 O(W/k)，節(jié)點(diǎn)數(shù)為O(N)，故存儲(chǔ)器復(fù)雜度為O(N)。地址前綴更新操作首先要進(jìn)行一次查找過(guò)程確定更新節(jié)點(diǎn)的位置，因此更新時(shí)間復(fù)雜度和查找過(guò)程相同，為O(W/k)。

為對(duì)算法性能有一個(gè)更加直觀的認(rèn)識(shí)，對(duì)幾種常用快速軟件路由算法進(jìn)行了仿真比較[11]，測(cè)試數(shù)據(jù)使用 http://www.meri.edu/ipma/routing_table提供的 MAE-EAST路由表，其中包含路由表項(xiàng) 38項(xiàng)和 816項(xiàng)，該測(cè)試系統(tǒng)使用2.8 GHz(Pentium4)處理器，求出查找不同前綴長(zhǎng)度路由信息所消耗時(shí)間的統(tǒng)計(jì)平均值，經(jīng)過(guò)換算后的比較結(jié)果如表2所示。本文設(shè)計(jì)算法在最壞情況下查找一次需要訪(fǎng)問(wèn)10次SRAM和1次DRAM，如果使用500 MHz的SRAM和800 MHz的 DRAM，訪(fǎng)問(wèn)一次存儲(chǔ)器分別需 5個(gè)周期和100個(gè)周期，那么需要的時(shí)間是225 ns，存儲(chǔ)容量為220 KB。

表2 算法實(shí)際運(yùn)行性能比較

從表2的對(duì)比中可以看出，提議Trie樹(shù)算法比傳統(tǒng)快速Trie算法在路由查找速度方面有較大的提升，在IPv4的環(huán)境下，提議算法比二分查找算法速度也有明顯提升；算法存儲(chǔ)空間比這些傳統(tǒng)的快速路由算法較為節(jié)省。使用提議算法一次查找過(guò)程只需 225 ns，因此，查找速度可達(dá)到4.4 Mb/s，應(yīng)用于4個(gè)并行處理的微引擎中，可使網(wǎng)絡(luò)處理器達(dá)到萬(wàn)兆的交換速率。

5 結(jié)束語(yǔ)

高效的IP路由查找算法應(yīng)該綜合考慮查找速度、路由表更新的開(kāi)銷(xiāo)，以及所需存儲(chǔ)空間的大小等方面，以取得較佳的綜合性能為主要目標(biāo)[12]。本文提出一種基于Trie樹(shù)的路由查找算法，通過(guò)硬件查找機(jī)制具有查找速度快、所需存儲(chǔ)空間小、更新速度快、硬件實(shí)現(xiàn)簡(jiǎn)單等特點(diǎn)，已成功應(yīng)用于 10 Gb/s帶寬的網(wǎng)絡(luò)處理器設(shè)計(jì)中。由于下一代Internet協(xié)議采用IPv6協(xié)議，路由地址擴(kuò)展為128位，因此在網(wǎng)絡(luò)處理器的實(shí)際應(yīng)用中，該算法對(duì)IPv6的支持是下一步要展開(kāi)的工作。

[1]Chang Y K , Lin Y C.A Fast and Memory Efficient Dynamic IP Lookups Algorithm Based on B-tree[C]//Proc.of International Conference on Advanced Information Networking and Applications.Bradford, UK: IEEE Press, 2009:278-284.

[2]李 韜, 孫志剛.基于SoPC的粗粒度數(shù)據(jù)流網(wǎng)絡(luò)處理器原型設(shè)計(jì)[C]//第五屆中國(guó)通信集成電路技術(shù)與應(yīng)用研討會(huì)論文集.西安: 中國(guó)通信學(xué)會(huì), 2007.

[3]劉英臣, 傅光軒.路由查找技術(shù)的分析及研究[J].貴州大學(xué)學(xué)報(bào): 自然科學(xué)版, 2006, 23(3): 294-299.

[4]劉永鋒, 楊宗凱.高速路由器中基于樹(shù)型結(jié)構(gòu)路由查找算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與科學(xué), 2004, 26(1): 22-25.

[5]華 澤, 馬 濤.基于Trie的路由查找設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)與現(xiàn)代化, 2006, 22(2): 42-45.

[6]科 默.網(wǎng)絡(luò)處理器與網(wǎng)絡(luò)系統(tǒng)設(shè)計(jì)(英文版)[M].北京:電子工業(yè)出版社, 2004.

[7]郜國(guó)良, 李廣軍.一種基于Trie的快速I(mǎi)P路由查找算法[J].微電子學(xué)與計(jì)算機(jī), 2011, 28(6): 163-167.

[8]吳 強(qiáng), 蘇金樹(shù), 王勇軍.基于 Patricia樹(shù)的快速多維分組分類(lèi)算法[J].計(jì)算機(jī)工程, 2004, 30(21): 50-52.

[9]田 園, 張曙光, 喬廬峰, 等.路徑壓縮查找算法的 FPGA實(shí)現(xiàn)[J].軍事通信技術(shù), 2012, 33(3): 48-52.

[10]郭文文.基于 Trie的軟轉(zhuǎn)發(fā)路由查找模塊的設(shè)計(jì)實(shí)現(xiàn)[D].南京: 南京郵電大學(xué), 2011.

[11]張 毅, 郭玲麗.基于FPGA的高速路由查找算法[J].電子元器件應(yīng)用, 2009, 11(9): 22-27.

[12]譚明鋒, 高 蕾, 龔正虎.IP路由查找算法研究概述[J].計(jì)算機(jī)工程與科學(xué), 2006, 28(6): 77-80.