畢業(yè)論文----基于binary trie的ip地址查找算法研究與實(shí)現(xiàn)

1、<p>　　畢 業(yè) 設(shè) 計(jì)（論 文）</p><p>　　題 目： 基于Binary Trie的IP地址 </p><p>　　查找算法研究與實(shí)現(xiàn) </p><p>　　院 系： 計(jì)算機(jī)學(xué)院 </p><p>　　專(zhuān)

2、 業(yè)： 網(wǎng)絡(luò)工程 </p><p>　　班 級(jí)： </p><p>　　學(xué)生姓名： </p><p>　　導(dǎo)師姓名：

3、 職稱(chēng)： 副教授 </p><p>　　起止時(shí)間： 2010年 3 月 8 日至 2010 年 6月 11 日 </p><p>　　畢業(yè)設(shè)計(jì)(論文)任務(wù)書(shū)</p><p><b>　　任務(wù)與要求</b></p><p>　　畢業(yè)設(shè)計(jì)(論文)開(kāi)題報(bào)告</p><p>　　計(jì)

4、算機(jī) 學(xué)院 網(wǎng)絡(luò)工程 專(zhuān)業(yè) 06 級(jí) 06 班</p><p>　　課題名稱(chēng)： 基于Binary Trie的IP地址查找算法</p><p><b>　　研究與實(shí)現(xiàn)</b></p><p>　　學(xué)生姓名： 學(xué)號(hào)：04063188</p><p>　　指導(dǎo)教師：

5、 </p><p>　　報(bào)告日期： 2010年3月14日 </p><p><b>　　說(shuō)明：</b></p><p>　　本報(bào)告必須由承擔(dān)畢業(yè)論文(設(shè)計(jì))課題任務(wù)的學(xué)生在畢業(yè)論文(設(shè)計(jì)) 正式開(kāi)始的第1周周五之前獨(dú)立撰寫(xiě)完成，并交指導(dǎo)教師審閱。</p><p>　　畢業(yè)

6、設(shè)計(jì) (論文)成績(jī)?cè)u(píng)定表</p><p>　　西安郵電學(xué)院畢業(yè)論文(設(shè)計(jì))成績(jī)?cè)u(píng)定表(續(xù)表)</p><p><b>　　目 錄</b></p><p><b>　　摘要I</b></p><p>　　AbstractII</p><p><b>　　1引言

7、1</b></p><p>　　1.1 背景介紹1</p><p>　　1.2 路由查找現(xiàn)狀3</p><p>　　1.3 基于Trie結(jié)構(gòu)的路由算法的介紹4</p><p>　　1.4 論文結(jié)構(gòu)9</p><p>　　2 基于Binary Trie的算法分析10</p><p

8、>　　2.1 Binary Trie算法概述10</p><p>　　2.2 算法涉及的主要操作11</p><p>　　2.3 Binary Trie算法性能12</p><p>　　3 算法的詳細(xì)設(shè)計(jì)與實(shí)現(xiàn)13</p><p>　　3.1 算法邏輯結(jié)構(gòu)的實(shí)現(xiàn)13</p><p>　　3.2 主要函數(shù)

9、的實(shí)現(xiàn)和作用13</p><p>　　3.3 部分函數(shù)流程圖14</p><p>　　4 算法測(cè)試及性能評(píng)價(jià)17</p><p>　　4.1 測(cè)試環(huán)境17</p><p>　　4.2 測(cè)試結(jié)果17</p><p>　　4.3 算法的可擴(kuò)展性評(píng)價(jià)19</p><p><b>

10、　　5 結(jié)論20</b></p><p>　　5.1 全文總結(jié)20</p><p>　　5.2 改進(jìn)方案20</p><p><b>　　致謝21</b></p><p><b>　　參考文獻(xiàn)22</b></p><p><b>　　摘 要&

11、lt;/b></p><p>　　隨著信息技術(shù)的高速發(fā)展，因特網(wǎng)承載的業(yè)務(wù)越來(lái)越豐富，加之人們對(duì)網(wǎng)絡(luò)的依賴(lài)程度不斷增加，使得骨干網(wǎng)對(duì)帶寬的需求越來(lái)越大，而在對(duì)骨干網(wǎng)的擴(kuò)展中，最為關(guān)鍵的是核心路由器性能的提升。這就要求核心路由器每秒能轉(zhuǎn)發(fā)幾百萬(wàn)甚至更多的分組，快速路由查找技術(shù)成為路由器報(bào)文轉(zhuǎn)發(fā)的瓶頸。因此如何實(shí)現(xiàn)路由表的高速查找和更新就成為研究的難點(diǎn)。同時(shí)隨著IPv6技術(shù)的逐步成熟和推廣，也進(jìn)一步要求提升路由

12、查找的性能。</p><p>　　本文簡(jiǎn)要介紹了目前因特網(wǎng)的使用情況及發(fā)展趨勢(shì)以及當(dāng)下路由查找算法的現(xiàn)狀，并簡(jiǎn)要介紹了幾種常用的基于Trie結(jié)構(gòu)的IP路由算法。重點(diǎn)研究了基于Trie結(jié)構(gòu)的基礎(chǔ)算法基于Binary Trie的IP地址查找算法，本文完成了該算法的實(shí)現(xiàn)并根據(jù)實(shí)驗(yàn)數(shù)據(jù)對(duì)其進(jìn)行了定性及定量的性能分析。</p><p>　　關(guān)鍵詞：IP路由查找 最長(zhǎng)前綴匹配 Trie樹(shù)<

13、;/p><p><b>　　Abstract</b></p><p>　　With the rapid development of information technology, the Internet is carrying more and more applications, and the number of web users is fast increas

14、ing, which lead to the demand for bandwidth increase on its backbone network, so to improve and upgrade the core router becomes the key to expand the backbone network . It orders the core router to be able to forward ten

15、 million of packets per second. Fast routing lookup has become the bottleneck of high speed packet forwarding. Thus how to improve</p><p>　　This paper describes the Internet usage situation and trends and su

16、mmarizes the route lookup algorithm existed, then briefly introduces some IP routing lookup algorithms based on trie structure. This paper emphatic describes the binary trie IP routing lookup algorithm, and implements th

17、e algorithm, in the same time , we carry out qualitative and quantitative analysis according to the experimental data.</p><p>　　Key Words: IP Route Lookup Longest Prefix Match Trie tree</p><p&

18、gt;<b>　　1引言</b></p><p>　　互聯(lián)網(wǎng)已經(jīng)走進(jìn)千家萬(wàn)戶(hù)，成為人們生活中不可缺少的組成部分，它不僅為人們提供了各種各樣的簡(jiǎn)單且快捷的通信與信息檢索手段，更重要的是為人們提供了巨大的信息資源和服務(wù)資源。隨著越來(lái)越多的人認(rèn)識(shí)并使用互聯(lián)網(wǎng)，使得在互聯(lián)網(wǎng)中起互聯(lián)作用的路由器或路由交換機(jī)不堪重負(fù)。路由器或路由交換機(jī)完成的核心功能就是在路由表中為來(lái)自不同鏈路、去往不同目的地的IP分組

19、找到最佳的傳送路由，并以接力的方式把分組送到下一跳的路由器，如此反復(fù)，直到分組到達(dá)最終目的地。而為每個(gè)IP分組根據(jù)各自的目的地，在路由表里找到最佳匹配路由的算法，就是路由查找算法。</p><p><b>　　1.1 背景介紹</b></p><p>　　1.1.1 因特網(wǎng)應(yīng)用需求及發(fā)展趨勢(shì)</p><p>　　截至2009年底，中國(guó)網(wǎng)民規(guī)模達(dá)

20、到3.84億人，較2008年增長(zhǎng)28.9%，在總?cè)丝谥械谋戎貜?2.6%提升到28.9%，互聯(lián)網(wǎng)普及率在穩(wěn)步上升。隨著中國(guó)網(wǎng)民規(guī)模的不斷增加，意味著IP地址資源的不足將會(huì)表現(xiàn)的更加突出，更加迫切的要求互聯(lián)網(wǎng)技術(shù)快速的更新和發(fā)展。</p><p>　　圖1-1 中國(guó)網(wǎng)民規(guī)模與增長(zhǎng)率</p><p>　　表1-1：世界范圍使用Internet的人口分布情況（2009\12）</p>

21、<p>　　從表1-1中可以看出，世界范圍內(nèi)使用互聯(lián)網(wǎng)的速度呈現(xiàn)快速增長(zhǎng)的的趨勢(shì)，我們可以相信，互聯(lián)網(wǎng)的使用在世界范圍內(nèi)的迅速擴(kuò)展，將對(duì)網(wǎng)絡(luò)容量和互連設(shè)備性能提出更高的要求。</p><p>　　1.1.2 核心路由表（BGP）的增長(zhǎng)趨勢(shì)</p><p>　　圖1-2 Internet核心網(wǎng)BGP路由表規(guī)模增長(zhǎng)趨勢(shì)</p><p>　　如圖1-2所示

22、，路由表的規(guī)模的迅猛增加是不可避免的，路由表的規(guī)模和前綴的潛在數(shù)量直接影響路由查找和分組分類(lèi)算法的時(shí)間和空間復(fù)雜度，這將使路由查找技術(shù)面臨嚴(yán)峻的考驗(yàn)。</p><p>　　路由表的日益膨脹和IP地址的短缺，都預(yù)示著新一代網(wǎng)絡(luò)協(xié)議IPv6必然在不久的將來(lái)被實(shí)施，因?yàn)镮Pv6協(xié)議不僅可提供充足的地址空間，還能對(duì)路由前綴實(shí)施更好的聚合，以減小路由表規(guī)模。但是，IPv6協(xié)議的應(yīng)用也將給路由查找?guī)?lái)很大的挑戰(zhàn)，因?yàn)镮Pv6

23、的實(shí)施意味著IP地址將從32位迅速增加到128位，而目前大多數(shù)成熟的算法都和IP地址長(zhǎng)度密切相關(guān)，有些算法根本無(wú)法適用于IPv6。</p><p>　　1.2 路由查找現(xiàn)狀</p><p>　　路由查找是尋找最長(zhǎng)前綴匹配的問(wèn)題，其難點(diǎn)在于不僅需要考慮與地址前綴相匹配，而且還需要考慮地址前綴的長(zhǎng)度?？梢杂没谟布蛙浖煞N方法來(lái)實(shí)現(xiàn)路由查找。</p><p>　　1.

24、2.1 基于硬件的查找算法分析</p><p>　　基于RAM的路由查找方案是最簡(jiǎn)單的基于硬件的查找算法，該方案是在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í)際中并不可行。</p><p>　　目前使用最多的硬件實(shí)現(xiàn)方式是在基于RAM技術(shù)的改進(jìn)：內(nèi)容尋

25、址存儲(chǔ)器 (ContentAddressableMemory，簡(jiǎn)記CAM)來(lái)進(jìn)行快速的路由查找。CAM能夠在一個(gè)硬件時(shí)鐘周期內(nèi)完成關(guān)鍵字的精確匹配查找。常用的隨機(jī)存儲(chǔ)器通過(guò)輸入地址來(lái)返回該地址所對(duì)應(yīng)的數(shù)據(jù)信息，而CAM的訪問(wèn)方式不同，只需輸入關(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ǎng)度具體分布沒(méi)有準(zhǔn)確了解之前，為了保證能夠存儲(chǔ)

26、N個(gè)前綴表項(xiàng)，每個(gè)CAM都需要有N個(gè)表項(xiàng)的空間，因此，預(yù)留方案使得CAM存儲(chǔ)空間的利用率大大降低了，而且成本昂貴。</p><p>　　為了能夠克服CAM方法的缺點(diǎn)，又有一種CAM實(shí)現(xiàn)機(jī)制--三態(tài)CAM(TernaryContent一 AddressableMemory，簡(jiǎn)記TCAM)提出來(lái)。TCAM一個(gè)特殊的CAM硬件設(shè)備，是CAM實(shí)現(xiàn)機(jī)制的改進(jìn)。結(jié)構(gòu)同CAM一樣，由一個(gè)二維陣列組成，陣列中的每一行對(duì)應(yīng)存儲(chǔ)器的

27、一個(gè)槽，槽的大小依照不同的應(yīng)用設(shè)置成64bits、72bits或128bits及更高的比特位大小。它能起到和完全相關(guān)聯(lián)存儲(chǔ)器一樣的功用。TCAM的優(yōu)點(diǎn)是它保存的表項(xiàng)在長(zhǎng)度要求上非常靈活，可以在同一個(gè)TCAM芯片中保存任意長(zhǎng)度的關(guān)鍵字表項(xiàng)。TCAM具有實(shí)現(xiàn)簡(jiǎn)單、查找速度快的優(yōu)點(diǎn)，它使用并行技術(shù)，查找復(fù)雜度僅為O(1)，但TCAM最大的不足之處在于其造價(jià)昂貴、集成度低和高功耗。</p><p>　　1.2.2 基于軟

28、件的查找算法分析</p><p>　　基于軟件的路由查找算法有很多種，現(xiàn)按照算法實(shí)現(xiàn)的數(shù)學(xué)模型，對(duì)一些經(jīng)典的路由查找算法做簡(jiǎn)要介紹。</p><p>　　基于線(xiàn)性查找：路由表內(nèi)的表項(xiàng)按照簡(jiǎn)單的線(xiàn)性排列方式組織，查找將待查找的IP地址和數(shù)據(jù)庫(kù)內(nèi)的前綴逐一進(jìn)行比較，直到匹配為止。這種算法實(shí)現(xiàn)非常簡(jiǎn)單，而且存儲(chǔ)代價(jià)也并不高，適用于低速要求下非常小規(guī)模的路由表實(shí)例。然而，此算法不可能被廣泛采用，特

29、別是對(duì)于速度要求嚴(yán)苛的環(huán)境，因?yàn)槠鋾r(shí)間復(fù)雜度和路由表的規(guī)模成正比，其期望值是N/2；其空間復(fù)雜度為O(NW)(其中W為最長(zhǎng)前綴長(zhǎng)度)。</p><p>　　基于Trie結(jié)構(gòu)的查找：根據(jù)前綴的二進(jìn)制比特值，構(gòu)建二叉樹(shù)或二的次叉樹(shù)，根據(jù)前綴的二進(jìn)制比特值將其關(guān)聯(lián)的存儲(chǔ)在分叉樹(shù)上。檢索將待查找的IP地址的二進(jìn)制比特值作為索引，在Trie樹(shù)數(shù)據(jù)結(jié)構(gòu)上索得到相應(yīng)的前綴以及對(duì)應(yīng)的下一跳路由信息。</p><

30、;p>　　二分/多分查找：根據(jù)前綴的一些特性，例如前綴長(zhǎng)度、前綴區(qū)間等，先將前綴進(jìn)行預(yù)分割處理，并構(gòu)造相應(yīng)的決策樹(shù)，將前綴存儲(chǔ)在決策的不同分支。查找時(shí)，利用待匹配目的IP地址對(duì)應(yīng)的屬性值，在決策上進(jìn)行搜索，得到與之匹配的最佳表項(xiàng)。</p><p>　　基于哈希表結(jié)構(gòu)的查找：根據(jù)前綴某個(gè)指定屬性的哈希函數(shù)值，構(gòu)造希表對(duì)前綴進(jìn)行存儲(chǔ)組織。查找時(shí)根據(jù)待匹配目的IP地址的哈希值進(jìn)哈希索引，進(jìn)而得到匹配結(jié)果。由于哈希

31、沖突的存在，基于哈希表的法通常需結(jié)合其它的算法思想，或常被融入到眾多算法的思想精髓里。</p><p>　　規(guī)避查找技術(shù)：通過(guò)利用查找任務(wù)的某些局部性特征，或者對(duì)查找任進(jìn)行特定的轉(zhuǎn)化和重新分配，使得某些查找任務(wù)可以被簡(jiǎn)化或規(guī)避，而減小路由查找的壓力，以滿(mǎn)足高性能的需求。</p><p>　　1.3 基于Trie結(jié)構(gòu)的路由算法的介紹</p><p>　　下面對(duì)基于Tr

32、ie結(jié)構(gòu)的基于Binary Trie的路由算法（在第二章重點(diǎn)介紹）、路徑壓縮（Path-Compressed）Trie算法、多比特Trie算法、級(jí)壓縮Trie（LC-Trie）算法、位圖壓縮（Bitmap-Compressed）Trie算法進(jìn)行簡(jiǎn)要介紹。</p><p>　　1.3.1 Binary Trie的路由算法</p><p>　　圖1-3路由前綴集用例以及對(duì)應(yīng)的二進(jìn)制Trie算法

33、數(shù)據(jù)結(jié)構(gòu)</p><p>　　基本的二進(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樹(shù)中，處于第L層的結(jié)點(diǎn)實(shí)際上代表了一類(lèi)地址前L-1比特均相同的地址空間，如圖1-3所示。查找搜索時(shí)，根據(jù)待查找IP地址的比特位，從Trie樹(shù)的根結(jié)點(diǎn)開(kāi)始依次向其子孫結(jié)點(diǎn)進(jìn)行，直到再無(wú)分支可搜索為

34、止，其間記錄的最后一個(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)。</p><p>　　1.3.2 路徑壓縮Trie算法</p><p>　　要提高查找速度、減少存儲(chǔ)器訪問(wèn)操作的次數(shù)，必須降低Trie樹(shù)

35、的高度。降低Trie樹(shù)高度的一種方法是使用路徑壓縮技術(shù)。路徑壓縮是K.Sklower在1968年D.R.Morrison提出的一種叫做PATRICIA的算術(shù)編碼算法基礎(chǔ)上，提出的一種稱(chēng)為路徑壓縮Trie的最長(zhǎng)前綴路由查找算法。</p><p>　　很明顯，在二進(jìn)制trie樹(shù)中存在著許多不含轉(zhuǎn)發(fā)信息的中間結(jié)點(diǎn)。從地址前綴分布的特點(diǎn)可知，到目前為止還沒(méi)有長(zhǎng)度小于8比特的地址前綴，即便是長(zhǎng)度介于9-15比特之間的前綴也

36、并不多，這就使得二進(jìn)制Trie樹(shù)的前若干層主要是由那些不含轉(zhuǎn)發(fā)信息的中間結(jié)點(diǎn)組成。路徑壓縮的Trie樹(shù)是對(duì)樹(shù)的層次進(jìn)行壓縮，來(lái)減小樹(shù)的深度。由于某些結(jié)點(diǎn)被刪除，查找過(guò)程中不是逐位對(duì)比，而是維護(hù)一個(gè)位變量指示下一個(gè)需要檢查的比特位。為了恢復(fù)原有信息，路徑壓縮Trie樹(shù)需要保存地址前綴的比特串。</p><p>　　圖1-4路徑壓縮Trie算法數(shù)據(jù)結(jié)構(gòu)</p><p>　　當(dāng)二進(jìn)制Trie樹(shù)稀

37、疏時(shí)，有許多內(nèi)部結(jié)點(diǎn)具有單個(gè)的分支，當(dāng)訪問(wèn)這樣的結(jié)點(diǎn)時(shí)，沒(méi)有分支決策，僅有的操作是當(dāng)這個(gè)結(jié)點(diǎn)對(duì)應(yīng)路由表中的一個(gè)前綴時(shí)記錄下一跳信息，使得Trie有一個(gè)高的空間復(fù)雜度和大的查找時(shí)間。為了降低存儲(chǔ)需求，縮短Trie樹(shù)的深度（查找時(shí)間），路徑壓縮Trie中去掉了所有具有單個(gè)分支的內(nèi)部結(jié)點(diǎn)（不包括含有前綴的結(jié)點(diǎn)）。圖1-4給出了路徑壓縮Trie算法的一個(gè)示例（采用與圖1-3中相同的前綴集）。前綴結(jié)點(diǎn)b和e都處于一個(gè)“單分支并且內(nèi)部不包含前綴結(jié)點(diǎn)

38、的子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)。

39、當(dāng)比較失敗或者到達(dá)葉子結(jié)點(diǎn)時(shí)，查找終止。此時(shí)，最近記錄的下一跳信息指針作為結(jié)果被返回。事實(shí)上，對(duì)于非</p><p>　　路徑壓縮Trie減少了對(duì)Trie結(jié)構(gòu)查找的平均次數(shù)，但最壞情況下，路徑中可能不存在單分支結(jié)構(gòu)，因此查找時(shí)間復(fù)雜度仍為O(W)；最壞情況下，沒(méi)有分支被壓縮，因而存儲(chǔ)復(fù)雜度還是O(NW)。事實(shí)上，路徑壓縮Trie僅當(dāng)二進(jìn)制Trie樹(shù)稀疏時(shí)其性能較優(yōu)。隨著前綴個(gè)數(shù)的增加以及二進(jìn)制Trie樹(shù)變得稠密，

40、使用路徑壓縮Trie的改進(jìn)性能降低。</p><p>　　1.3.3 多比特Trie算法</p><p>　　基本二進(jìn)制Trie算法在查找時(shí)每次僅檢查IP地址的一個(gè)比特，查找速度較慢。多比特Trie算法在查找過(guò)程的每一步檢查多個(gè)比特，加速查找的進(jìn)程，其中每步檢查的比特?cái)?shù)定義為搜索步長(zhǎng)。如圖1-5所示，該多比特Trie的第一層上有8個(gè)分支，對(duì)應(yīng)的搜索步長(zhǎng)為3；而在第二層，每個(gè)結(jié)點(diǎn)有4個(gè)分支，

41、對(duì)應(yīng)的搜索步長(zhǎng)為2。我們看到，整個(gè)Trie樹(shù)僅有2層，即最多僅需2次多分支Trie搜索就可以得到最終匹配結(jié)果，相比基本二進(jìn)制Trie在性能上有了較大的改進(jìn)。一般的，k比特（即每層都有2k個(gè)分支的）Trie的查找時(shí)間復(fù)雜度是O(W/k)。另一方面，我們注意到，多比特Trie不能支持任意長(zhǎng)度的地址前綴，如圖1-5的例子，該多比特Trie僅支持長(zhǎng)度為3和5的前綴，為了能夠用多比特Trie來(lái)進(jìn)行前綴查找，路由表中的地址前綴需要被擴(kuò)展成這兩種長(zhǎng)度

42、。這種擴(kuò)展帶來(lái)了存儲(chǔ)的冗余度，增加了存儲(chǔ)復(fù)雜度。最壞情況下，存儲(chǔ)復(fù)雜度為O(N ×2k×W/k)。</p><p>　　圖1-5多分支Trie的數(shù)據(jù)結(jié)構(gòu)示意</p><p>　　針對(duì)常規(guī)的多比特Trie浪費(fèi)存儲(chǔ)空間的問(wèn)題，S.Nilsson等人提出了一種叫做層壓縮Trie（Level-Compressed Trie）的算法。該算法的主要思想是：靈活的為T(mén)rie的各個(gè)層、

43、各個(gè)分支按照前綴集分布特點(diǎn)自適應(yīng)選定不同的搜索步長(zhǎng)：當(dāng)子Trie結(jié)構(gòu)分支是滿(mǎn)2L叉樹(shù)時(shí)，才使用步長(zhǎng)L。這樣既能發(fā)揮多比特Trie的優(yōu)勢(shì)，同時(shí)由于子Trie結(jié)構(gòu)本來(lái)就是滿(mǎn)2L叉樹(shù)，不會(huì)產(chǎn)生結(jié)點(diǎn)復(fù)制。但我們也注意到，層壓縮Trie僅在Trie結(jié)點(diǎn)分布較為密集時(shí)才較為有效。</p><p>　　1.3.4 級(jí)壓縮Trie（LC-Trie）算法</p><p>　　如上所述，路徑壓縮Trie適合于

44、結(jié)點(diǎn)稀疏的情況。Nilsson ET AL提出了一種級(jí)壓縮技術(shù)用于結(jié)點(diǎn)稠密的情況。這種技術(shù)被稱(chēng)為級(jí)壓縮Trie，簡(jiǎn)稱(chēng)LC一Trie。LC一Trie結(jié)合路徑壓縮和多位Trie的特點(diǎn)進(jìn)一步優(yōu)化基本Trie結(jié)構(gòu)。LC壓縮樹(shù)中每個(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)，分支記錄將是3，孩子結(jié)點(diǎn)的個(gè)數(shù)剛好是分支記錄的2的冪次方。另外每個(gè)父結(jié)點(diǎn)還記錄跳步(skip

45、)信息，跳步是指查找到當(dāng)前結(jié)點(diǎn)所跨越的比特?cái)?shù)。查找時(shí)，從樹(shù)的根部開(kāi)始查找，根據(jù)分支信息、跳步信息和左孩子指針就可以搜索到對(duì)應(yīng)的下一個(gè)孩子結(jié)點(diǎn)，最終能找到葉結(jié)點(diǎn)，從葉結(jié)點(diǎn)就可以知道路由信息。LC層壓縮算法的關(guān)鍵是構(gòu)建層壓縮樹(shù)。構(gòu)建LC樹(shù)時(shí)，首先對(duì)前綴(稱(chēng)為基矢量，base vector)進(jìn)行排序，對(duì)已經(jīng)排好序的基矢量，采用由上至下的方法來(lái)構(gòu)建LC樹(shù)。它將基矢量劃分成許多子間隔(subinterval)，子間隔的劃分是按照基矢量的第一個(gè)成員

46、，基矢量的個(gè)數(shù)和它們相同的前綴部分進(jìn)行的。如果子間隔只有一個(gè)基矢量，就生成一個(gè)葉結(jié)點(diǎn)，否</p><p>　　可以看到，采用這種方法有些不確定因索，壓縮樹(shù)的深度受填充因子的影響比較明顯，如果前綴比較分散，可能會(huì)使樹(shù)的搜索深度加大。構(gòu)建LC壓縮樹(shù)的操作比較復(fù)雜，因?yàn)樗獙?duì)基矢量進(jìn)行排序，并需要對(duì)基矢量進(jìn)行子間隔內(nèi)的處理，這種采用遞歸方法來(lái)構(gòu)建壓縮樹(shù)的過(guò)程顯得比較復(fù)雜。而且，插入和刪除路由將可能會(huì)導(dǎo)致樹(shù)的變動(dòng)比較大，

47、這種變動(dòng)可能會(huì)要求子結(jié)點(diǎn)合并，這帶來(lái)了插入和刪除的復(fù)雜性。</p><p>　　1.3.5 位圖壓縮（Bitmap-Compressed）Trie算法</p><p>　　路徑壓縮Trie、層壓縮Trie等所謂的壓縮都是從提高查找性能的角度考慮的，主要是將搜索的步驟進(jìn)行壓縮。而位圖壓縮Trie技術(shù)則是針對(duì)多比特Trie造成的大量前綴擴(kuò)展問(wèn)題而提出的。它實(shí)際上是一種數(shù)據(jù)壓縮技術(shù)，試圖對(duì)多比特

48、Trie的數(shù)據(jù)結(jié)構(gòu)進(jìn)行無(wú)損數(shù)據(jù)壓縮減少系統(tǒng)的內(nèi)存使用量。位圖壓縮的思想首先由M.Degermark等人提出，N.Huang和D.E.Taylor等人也分別將它采用到他們的路由查找算法里面，其原理如圖1-6所示。</p><p>　　對(duì)于多比特Trie的某一個(gè)分支子Trie，假設(shè)其搜索步長(zhǎng)為k，則子Trie包含2k個(gè)分支，對(duì)應(yīng)一個(gè)含有2k個(gè)元素的結(jié)點(diǎn)信息陣列；而實(shí)際上，這個(gè)陣列中的元素很多可能是由于多比特Trie的

49、結(jié)點(diǎn)復(fù)制產(chǎn)生的，對(duì)應(yīng)同一個(gè)路由前綴，含有完全一致的路由信息。如圖1-6所示，“結(jié)點(diǎn)信息陣列”包含多個(gè)長(zhǎng)串的相同元素的“數(shù)據(jù)串”。位圖壓縮算法引入一個(gè)叫做“壓縮位圖”的數(shù)據(jù)結(jié)構(gòu)來(lái)表示這些數(shù)據(jù)串在陣列中的起點(diǎn)位置，位圖的對(duì)應(yīng)比特被標(biāo)志為“1”，否則為0；而每個(gè)數(shù)據(jù)串相同的數(shù)據(jù)僅需要保存一份，即其它相同的元素可以被“壓縮”掉。壓縮后的陣列叫做“壓縮的結(jié)點(diǎn)信息陣列”。不難驗(yàn)證壓縮前后的數(shù)據(jù)等價(jià)。查找時(shí)，首先定位對(duì)應(yīng)元素在“結(jié)點(diǎn)信息陣列”中的位置

50、，計(jì)算對(duì)應(yīng)的“壓縮位圖”中該位置之前有多少個(gè)“1”，然后再根據(jù)這個(gè)計(jì)算的數(shù)值，索引“壓縮的結(jié)點(diǎn)信息陣列”相應(yīng)的元素，得到結(jié)果。</p><p>　　圖1-6位圖壓縮技術(shù)的原理示意</p><p>　　多比特Trie結(jié)點(diǎn)陣列中相同元素組成“數(shù)據(jù)串”的個(gè)數(shù)是和路由前綴的規(guī)模N成正比的，因此“壓縮的結(jié)點(diǎn)信息陣列”是O(NW)的規(guī)模。原來(lái)O(N ×2k×W/k)量級(jí)的“結(jié)點(diǎn)信息

51、陣列”被同樣數(shù)量的位圖陣列取代。假設(shè)原來(lái)一個(gè)結(jié)點(diǎn)需要4Bytes來(lái)存儲(chǔ)，現(xiàn)在僅需1bit，這部分縮小了32倍。</p><p><b>　　1.4 論文結(jié)構(gòu)</b></p><p>　　本文的組織結(jié)構(gòu)如下：</p><p>　　介紹了基于Binary Trie的IP地址查找算法的概述。文中對(duì)該算法涉及的主要操作做了重點(diǎn)介紹，并對(duì)其算法性能進(jìn)行了

52、定性的評(píng)價(jià)。</p><p>　　對(duì)該算法的實(shí)現(xiàn)和邏輯結(jié)構(gòu)做了介紹。文中對(duì)算法所用的存儲(chǔ)結(jié)構(gòu)作了介紹，以及對(duì)主要函數(shù)的功能進(jìn)行了說(shuō)明并畫(huà)出主要函數(shù)的流程圖。</p><p>　　根據(jù)實(shí)驗(yàn)數(shù)據(jù)對(duì)該算法進(jìn)行定性定量的性能分析。經(jīng)過(guò)多組數(shù)據(jù)實(shí)驗(yàn)，對(duì)該算法的性能做統(tǒng)計(jì)分析并用圖表的形式表示。</p><p>　　是論文的總結(jié)及對(duì)該算法提出進(jìn)一步的改進(jìn)方案。</p>

53、;<p>　　2 基于Binary Trie的算法分析</p><p>　　2.1 Binary Trie算法概述</p><p>　　這是IP查找中使用的基本Trie結(jié)構(gòu)，也就是我們常提到的二叉樹(shù)。在這種結(jié)構(gòu)中，每次進(jìn)行結(jié)點(diǎn)相關(guān)操作時(shí)，都是以一個(gè)比特作為比較對(duì)象的，其下屬分支最多包含左右兩個(gè)結(jié)點(diǎn):0(左結(jié)點(diǎn))和1(右結(jié)點(diǎn))。如圖2-1所示。這樣的一棵樹(shù)包含了所有的可能的網(wǎng)絡(luò)

54、前綴，但并非每一個(gè)結(jié)點(diǎn)都被使用。使用的結(jié)點(diǎn)將會(huì)存有轉(zhuǎn)發(fā)信息。如圖2-2示，一個(gè)位于樹(shù)的第n層上的結(jié)點(diǎn)k表示所有具有同樣的頭n位的路由前綴的集合。結(jié)點(diǎn)k的每一個(gè)分支按照下一位是0或1分別指向?qū)?yīng)子樹(shù)的根結(jié)點(diǎn)，該子樹(shù)根結(jié)點(diǎn)代表了所有具有同樣的頭h+l位的路由前綴。由于采用最長(zhǎng)前綴匹配原則，每一次結(jié)點(diǎn)訪問(wèn)過(guò)程中，要從Trie的根結(jié)點(diǎn)開(kāi)始，按包中目標(biāo)地址的每一位是O或l決定下一個(gè)要訪問(wèn)的結(jié)點(diǎn)，搜索到葉子結(jié)點(diǎn)后搜索過(guò)程才結(jié)束。在Trie的遍歷過(guò)程

55、中，記錄目前匹配的最長(zhǎng)地址前綴從而獲取下一跳信息。結(jié)點(diǎn)的增加或刪除通過(guò)路由協(xié)議來(lái)實(shí)現(xiàn)。使用的結(jié)點(diǎn)并不需要保存前綴信息，因此它的路徑就決定了它所要存儲(chǔ)的數(shù)據(jù)。這種Trie的每個(gè)結(jié)點(diǎn)最多包含2個(gè)指針，分別指向他的左右孩子結(jié)點(diǎn)，代表前綴的某個(gè)比特位為‘0’和‘1’時(shí)兩種情況的搜索分支。在Trie樹(shù)中，處于第L層的結(jié)點(diǎn)實(shí)際上</p><p>　　采用二叉Trie樹(shù)進(jìn)行IP地址最長(zhǎng)匹配的最有名的例子是BSD內(nèi)核.它的算法稱(chēng)

56、為 Radixtrie。首先把整個(gè)轉(zhuǎn)發(fā)表構(gòu)造成二叉樹(shù)的結(jié)構(gòu)。結(jié)點(diǎn)代表轉(zhuǎn)發(fā)表中的一條記錄。在搜索時(shí)，沿著匹配的路徑逐漸從樹(shù)根出發(fā)走向樹(shù)葉。同時(shí)，記住最新經(jīng)過(guò)的結(jié)點(diǎn)，直到路徑走不下去為止。從根到最新的結(jié)點(diǎn)就是最長(zhǎng)的地址前綴。</p><p>　　圖2-1Binary Trie結(jié)構(gòu)</p><p>　　圖2-2 Binary Trie樹(shù)代表的地址空間結(jié)構(gòu)</p><p>

57、　　2.2 算法涉及的主要操作</p><p>　　2.2.1 路由表的構(gòu)建</p><p>　　路由表的構(gòu)建就是根據(jù)每個(gè)IP前綴構(gòu)造二叉樹(shù)結(jié)點(diǎn)。結(jié)點(diǎn)的插入是在已有的Trie樹(shù)中按IP比特位比較，尋找合適的插入位置的過(guò)程。過(guò)程中除了為新的路由項(xiàng)生成新結(jié)點(diǎn)外，可能會(huì)插入輔助結(jié)點(diǎn)來(lái)平衡樹(shù)結(jié)構(gòu)，這將導(dǎo)致附加結(jié)點(diǎn)的內(nèi)存申請(qǐng)。對(duì)于路由表，其初始狀態(tài)為空，需要逐條加入。</p><

58、p>　　2.2.2 刪除路由表項(xiàng)</p><p>　　刪除路由表項(xiàng)是刪除二叉樹(shù)中不用的IP前綴信息，實(shí)際上就是刪除無(wú)用的結(jié)點(diǎn)。無(wú)用結(jié)點(diǎn)的刪除可以理解為結(jié)點(diǎn)查詢(xún)動(dòng)作的擴(kuò)展—對(duì)查找到的結(jié)點(diǎn)進(jìn)行刪除操作，該操作可能引起連鎖反應(yīng)，即遞歸刪除上層的中間結(jié)點(diǎn)。當(dāng)實(shí)際路由刪除時(shí)可能會(huì)涉及更復(fù)雜的更新動(dòng)作，比如對(duì)其他關(guān)心路由變化的協(xié)議的通知等，由于其根實(shí)際環(huán)境的相關(guān)性較大，所以在本文不做討論。</p><

59、;p>　　2.2.3 路由表的更新</p><p>　　路由表的更新操作實(shí)際上是新路由的插入和無(wú)用路由的刪除過(guò)程。因?yàn)榻Y(jié)點(diǎn)本身只包含了基本的比特信息，不存在更新問(wèn)題，只存在插入、刪除兩個(gè)操作。對(duì)于包含的結(jié)點(diǎn)中具體路由信息的修改，可以通過(guò)查詢(xún)到相應(yīng)的結(jié)點(diǎn)，然后修改或者分解為先刪除后增加兩個(gè)操作來(lái)完成。</p><p>　　2.2.4 路由查詢(xún)</p><p>　

60、　路由查詢(xún)是指根據(jù)待查的IP地址在所建的二叉樹(shù)中尋找最差匹配前綴的操作。路由查詢(xún)的效率是決定數(shù)據(jù)轉(zhuǎn)發(fā)速度的重要因素之一。另外路由的刪除、更新操作實(shí)質(zhì)上也是查詢(xún)的一個(gè)操作，所以他們的效率也將受到查詢(xún)算法效率的影響，當(dāng)然其他的根世紀(jì)路由條目相關(guān)的操作不再考慮之列。</p><p>　　2.3 Binary Trie算法性能</p><p>　　Binary Trie樹(shù)的優(yōu)點(diǎn)在于其實(shí)現(xiàn)的簡(jiǎn)單性，

61、它只用根據(jù)IP地址比特逐個(gè)比較，直到找到一最長(zhǎng)的前綴匹配。其不足之處在于樹(shù)的深度較大，比較搜索的次數(shù)較多，查找速度不是很快。</p><p>　　基于樹(shù)型結(jié)構(gòu)的路由查找容易受到前綴長(zhǎng)度的影響。如果Trie中存儲(chǔ)的最長(zhǎng)前綴的位數(shù)是W，則查找的時(shí)間復(fù)雜度是O(W)，如果有N個(gè)前綴，其存儲(chǔ)需要是O(Nw)(N表示路由表中的項(xiàng)數(shù))，更新的過(guò)程基于結(jié)點(diǎn)的查找，更新時(shí)間是O(W)。雖然這種結(jié)構(gòu)簡(jiǎn)單，但是他的最壞時(shí)間復(fù)雜度是O

62、(W)，而W可能很大，如果32比特的IP地址用一棵二叉trie樹(shù)存儲(chǔ)，那么樹(shù)的深度為32，在最壞情況下樹(shù)的深度為32，即需要32次的存儲(chǔ)器訪問(wèn)。這對(duì)128位地址的IPv6來(lái)說(shuō)，無(wú)疑是一個(gè)極大的挑戰(zhàn)。為了減少查詢(xún)的時(shí)間，必須減小樹(shù)的深度。由于低檔路由器要求的查找速率不是很高，該查找算法在低檔路由器中可以得到應(yīng)用。</p><p>　　3 算法的詳細(xì)設(shè)計(jì)與實(shí)現(xiàn)</p><p>　　3.1 算法

63、邏輯結(jié)構(gòu)的實(shí)現(xiàn)</p><p>　　該算法采取鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，如圖3-1所示含有兩個(gè)指針域，左孩子指針和右孩子指針，當(dāng)比特位為‘0’時(shí)指向左孩子，當(dāng)比特位為‘1’時(shí)指向右孩子。還有一個(gè)int型數(shù)據(jù)域，用來(lái)記錄下一跳端口信息，當(dāng)該節(jié)點(diǎn)為有效節(jié)點(diǎn)時(shí)數(shù)據(jù)域記錄下一跳端口信息，否則數(shù)據(jù)域記為‘-1’。</p><p>　　圖3-1 Binary Trie的存儲(chǔ)結(jié)構(gòu)</p><p&

64、gt;　　3.2 主要函數(shù)的實(shí)現(xiàn)和作用</p><p>　　3.2.1 ReadIProute（）函數(shù)</p><p>　　該函數(shù)是從路由表中讀取路由信息，路由表以文本文件的方式存儲(chǔ)，在該函數(shù)中以只讀的方式讀取路由信息，當(dāng)該文本文件非空時(shí)，以“前綴長(zhǎng)度 IP地址 下一跳端口”的形式讀取路由信息，再根據(jù)所讀取的信息構(gòu)造二叉樹(shù)。</p><p>　　3.2.2 Crea

65、tBitree（）函數(shù)</p><p>　　該函數(shù)是根據(jù)從路由表中讀取的路由信息創(chuàng)建二叉樹(shù)，根據(jù)IP地址前綴值確定分支方向，‘0’指向左分支；‘1’指向右分支。如果當(dāng)前分之存在時(shí)就利用當(dāng)前結(jié)點(diǎn)，如果不存在就申請(qǐng)空間，并對(duì)該結(jié)點(diǎn)進(jìn)行初始化。當(dāng)樹(shù)深度小于該IP地址前綴長(zhǎng)度時(shí)，結(jié)點(diǎn)的數(shù)據(jù)域記為‘-1’，否則該結(jié)點(diǎn)數(shù)據(jù)域記錄下一跳端口信息。</p><p>　　3.2.3 SearchIP（）函數(shù)

66、</p><p>　　該函數(shù)是以所要查找的IP地址為關(guān)鍵字，在所創(chuàng)建的二叉樹(shù)中進(jìn)行搜索，從Trie的根結(jié)點(diǎn)開(kāi)始，按目標(biāo)IP地址的每一位是0或l決定下一個(gè)要訪問(wèn)的結(jié)點(diǎn)，搜索到葉子結(jié)點(diǎn)后搜索過(guò)程才結(jié)束。在Trie的遍歷過(guò)程中，記錄目前匹配的最長(zhǎng)地址前綴從而獲取下一跳信息。</p><p>　　3.2.4 SaveMessage（）函數(shù)</p><p>　　該函數(shù)是將查找

67、結(jié)果以只寫(xiě)的方式存入名為“BinaryTrie”的文本文件之中，存儲(chǔ)格式是“待查IP地址 匹配的前綴值 下一跳端口號(hào) 查找次數(shù)”。</p><p>　　3.3 部分函數(shù)流程圖</p><p>　　3.3.1 該算法流程圖</p><p>　　圖3-2 該算法流程圖</p><p>　　3.3.2 CreatBitree（）函數(shù)流程圖</

68、p><p>　　圖3-3CreatBitree（）函數(shù)流程圖</p><p>　　3.3.3 SearchIP（）函數(shù)流程圖</p><p>　　圖3-4 SearchIP（）函數(shù)流程圖</p><p>　　4 算法測(cè)試及性能評(píng)價(jià)</p><p><b>　　4.1 測(cè)試環(huán)境</b></p>

69、;<p>　　主頻1.67Ghz，512MB內(nèi)存，英特爾奔騰處理器，Ubuntu 7.10操作系統(tǒng)，標(biāo)準(zhǔn)gcc編譯器。</p><p><b>　　4.2 測(cè)試結(jié)果</b></p><p>　　測(cè)試結(jié)果如表4-1所示。</p><p>　　表4-1 實(shí)驗(yàn)測(cè)試結(jié)果</p><p>　　如圖4-2所示，橫軸表示

70、的是不同的路由表文本文件，豎軸表示的是每個(gè)文件中所含路由信息條目的個(gè)數(shù)。</p><p><b>　　圖4-2路由表項(xiàng)</b></p><p>　　圖4-3待查路由表項(xiàng)</p><p>　　如圖4-3所示，橫軸表示的是待查的IP文本文件，豎軸表示的是每個(gè)待查文本文件中所含待查IP的個(gè)數(shù)。</p><p>　　圖4-4路由

71、表構(gòu)造Binary Trie結(jié)構(gòu)所需存儲(chǔ)容量</p><p>　　本文用構(gòu)建相應(yīng)的二叉樹(shù)所需結(jié)點(diǎn)的個(gè)數(shù)來(lái)表示一個(gè)路由表所需的存儲(chǔ)容量。如圖4-4所示，橫軸表示不同的路由表文本文件，豎軸表示每個(gè)路由表所需的存儲(chǔ)空間。</p><p>　　圖4-5待查路由表項(xiàng)所需的平均查找次數(shù)</p><p>　　如圖4-5所示，橫軸表示不同的待查IP文本文件在所對(duì)應(yīng)的路由表中的查找結(jié)

72、果，豎軸表示找到與待查IP相匹配的最長(zhǎng)前綴所需的平均查找次數(shù)。</p><p>　　4.3 算法的可擴(kuò)展性評(píng)價(jià)</p><p>　　由于新一代IP協(xié)議IPv6使用長(zhǎng)度為128的地址，所以它給本來(lái)己經(jīng)很復(fù)雜的最長(zhǎng)匹配前綴查找?guī)?lái)了更大的困難，對(duì)于目前的32位計(jì)算機(jī)系統(tǒng)來(lái)說(shuō)，訪問(wèn)一個(gè)128地址就需要進(jìn)行4次讀寫(xiě)操作，查找速度會(huì)大大降低。Trie樹(shù)的查找復(fù)雜度為O(W/K)，其中l(wèi)<K&l

73、t;W。如果W從32增加到128，在K不發(fā)生變化的前提下，算法的查找性能將下降到原來(lái)的1/4。為了能夠提高查找性能，唯一的做法就是提高K的大小。但是，從算法存儲(chǔ)容量的復(fù)雜度來(lái)看，增加K的大小勢(shì)必會(huì)增加算法的存儲(chǔ)空間，從而影響算法在實(shí)際系統(tǒng)中的使用。</p><p>　　基于Trie結(jié)構(gòu)的查找方案結(jié)構(gòu)簡(jiǎn)單，易于實(shí)現(xiàn)，因此，在IPv6占主導(dǎo)地位的將來(lái)，研究基于Trie的IP路由查找方案有不錯(cuò)的發(fā)展前景。</p&

74、gt;<p><b>　　5 結(jié)論</b></p><p><b>　　5.1 全文總結(jié)</b></p><p>　　隨著信息技術(shù)的高速發(fā)展，因特網(wǎng)承載的業(yè)務(wù)越來(lái)越豐富，加之人們對(duì)網(wǎng)絡(luò)的依賴(lài)程度不斷增加，使得骨干網(wǎng)對(duì)帶寬的需求越來(lái)越大，而在對(duì)骨干網(wǎng)的擴(kuò)展中，最為關(guān)鍵的是核心路由器性能的提升，這就要求核心路由器每秒能轉(zhuǎn)發(fā)幾百萬(wàn)甚至更多

75、的分組，快速路由查找技術(shù)成為路由器報(bào)文轉(zhuǎn)發(fā)的瓶頸。因此如何實(shí)現(xiàn)路由表的高速查找和更新就成為研究的難點(diǎn)。同時(shí)隨著IPv6技術(shù)的逐步成熟和推廣，也進(jìn)一步要求提升路由查找的性能。</p><p>　　目前常用的路由查找算法分為軟件實(shí)現(xiàn)和硬件實(shí)現(xiàn)兩類(lèi)，硬件方面主要圍繞CAM和TCAM展開(kāi);基于軟件算法主要包括樹(shù)形結(jié)構(gòu)為主體的Trie算法及其變種算法：Binary Trie的路由算法、路徑壓縮Trie算法、多分支Trie算

76、法、級(jí)壓縮Trie（LC-Trie）、位圖壓縮（Bitmap-Compressed）Trie算法其他壓縮算法和以表結(jié)構(gòu)為主體的基于前綴長(zhǎng)度二分查找和地址區(qū)間二分查找算法相關(guān)研究。這些算法一定程度上解決了路由查找速度的技術(shù)問(wèn)題，但是還存在結(jié)構(gòu)復(fù)雜，插入和刪除表項(xiàng)的難度較大，難于解決空間復(fù)雜度和時(shí)間復(fù)雜度之間的關(guān)系。</p><p>　　本論文重點(diǎn)研究了基于Binary Trie的IP路由查找算法，第二章對(duì)該算法進(jìn)行

77、綜述，定性的了解了該算法的優(yōu)缺點(diǎn)；第三章對(duì)該算法進(jìn)行邏輯實(shí)現(xiàn)，并對(duì)該算法的主要函數(shù)做了介紹并附有相應(yīng)流程圖；第四章通過(guò)實(shí)驗(yàn)數(shù)據(jù)對(duì)該算法做了相應(yīng)的定性分析。</p><p><b>　　5.2 改進(jìn)方案</b></p><p>　　該算法不能根據(jù)路由表的實(shí)時(shí)更新插入新的路由信息或刪除無(wú)用的路由信息，下一步可以在此基礎(chǔ)上實(shí)現(xiàn)該插入新的路由信息和刪除無(wú)用路由的工作。因?yàn)樵撍?/p>

78、法的存儲(chǔ)器訪問(wèn)次數(shù)較高，并不非常高效，隨著IPv6應(yīng)用的不斷擴(kuò)大，應(yīng)該考慮如何實(shí)現(xiàn)與硬件結(jié)合，實(shí)現(xiàn)路由的快速查找。</p><p><b>　　致 謝</b></p><p>　　首先要感謝我的指導(dǎo)老師，在他的正確指導(dǎo)下我順利的完成了畢業(yè)設(shè)計(jì)的任務(wù)。在畢業(yè)設(shè)計(jì)過(guò)程中，指導(dǎo)老師幫助我搜集了許多相關(guān)資料，幫助我解答了設(shè)計(jì)中遇到的許多專(zhuān)業(yè)問(wèn)題。他堅(jiān)持每周五給我們進(jìn)行相關(guān)答

79、疑，啟發(fā)開(kāi)拓我們的設(shè)計(jì)思路，并敦促我們完成相應(yīng)的工作任務(wù)。幾個(gè)月來(lái)，指導(dǎo)老師嚴(yán)謹(jǐn)?shù)墓ぷ髯黠L(fēng)深深地感染著我，在此謹(jǐn)向老師致以崇高的敬意和誠(chéng)摯的謝意。</p><p>　　再次是要感謝和我一起完成畢業(yè)設(shè)計(jì)的同學(xué)們，特別是和我是同一個(gè)指導(dǎo)老師的同學(xué)們還有我親愛(ài)的舍友們，正是有了他們，我才可以解決畢業(yè)設(shè)計(jì)中遇到的種種困難，我們之間的互相幫助，互相探討最終圓滿(mǎn)地完成了畢業(yè)設(shè)計(jì)。</p><p>　　

80、最后，衷心地感謝學(xué)校給我提供了良好的學(xué)習(xí)條件，讓我在這度過(guò)了四年難忘的大學(xué)生活，感謝我校圖書(shū)館及電子數(shù)據(jù)庫(kù)給我們提供了國(guó)內(nèi)外眾多的參考文獻(xiàn)和良好的學(xué)習(xí)環(huán)境，以及學(xué)校提供的固定的畢設(shè)實(shí)驗(yàn)室網(wǎng)絡(luò)教研室，使我有良好的條件完成畢業(yè)設(shè)計(jì)。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告 2010年1月 http://res

81、earch.cnnic.cn</p><p>　　[2] nternet World Stats.Internet Usage and Population Statistics Report(Dec 2009).</p><p>　　http://www.internetworldstats.com</p><p>　　[3] Huston G.BGP Route

82、 Table Analysis Reports(March 2010). http://bgp.potaroo.net</p><p>　　[4] Knuth D.Fundamental Algorithms Vol.3:Sorting and Searching. Addison-wesley 1973</p><p>　　[5] Morrison D R.PATRICIA-Prati

83、cal Algorithm to Retrieve Information Coded in Alphanumeric.</p><p>　　Journal of ACM,1968,15(4):514~534</p><p>　　[6] Sklower K.A Tree-based Routing Table for Berkeley Unix.Technical report,Unive

84、rsity of California,Berkeley,USA,1993</p><p>　　[7] Nilsson S and Karlsson G.IP-Address lookup using LC-tries.IEEE Journal on Select Areas of Communication,1999,17:1083~1092</p><p>　　[8] 鄭凱.高性能IP