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

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

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

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

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

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

6、設(shè)計 (論文)成績評定表</p><p>　　西安郵電學(xué)院畢業(yè)論文(設(shè)計)成績評定表(續(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 算法的詳細設(shè)計與實現(xiàn)13</p><p>　　3.1 算法邏輯結(jié)構(gòu)的實現(xiàn)13</p><p>　　3.2 主要函數(shù)

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

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

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

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

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)走進千家萬戶，成為人們生活中不可缺少的組成部分，它不僅為人們提供了各種各樣的簡單且快捷的通信與信息檢索手段，更重要的是為人們提供了巨大的信息資源和服務(wù)資源。隨著越來越多的人認識并使用互聯(lián)網(wǎng)，使得在互聯(lián)網(wǎng)中起互聯(lián)作用的路由器或路由交換機不堪重負。路由器或路由交換機完成的核心功能就是在路由表中為來自不同鏈路、去往不同目的地的IP分組

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

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

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

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

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

24、2.1 基于硬件的查找算法分析</p><p>　　基于RAM的路由查找方案是最簡單的基于硬件的查找算法，該方案是在RAM中為所有的IP地址都建立一個對應(yīng)的轉(zhuǎn)發(fā)表項。進行路由查找時，僅需要根據(jù)目的IP地址進行檢索，一次訪存就可以找到對應(yīng)的路由信息。但這將造成轉(zhuǎn)發(fā)表空間的極大浪費，因此，這種方案在實際中并不可行。</p><p>　　目前使用最多的硬件實現(xiàn)方式是在基于RAM技術(shù)的改進：內(nèi)容尋

25、址存儲器 (ContentAddressableMemory，簡記CAM)來進行快速的路由查找。CAM能夠在一個硬件時鐘周期內(nèi)完成關(guān)鍵字的精確匹配查找。常用的隨機存儲器通過輸入地址來返回該地址所對應(yīng)的數(shù)據(jù)信息，而CAM的訪問方式不同，只需輸入關(guān)鍵字的內(nèi)容，CAM就會將此關(guān)鍵字與C胡中所有的表項同時進行匹配比較，最后返回匹配表項在CAM中所對應(yīng)的地址。這種方法有一個明顯的缺點，即在對地址前綴長度具體分布沒有準確了解之前，為了保證能夠存儲

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

27、一個槽，槽的大小依照不同的應(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最大的不足之處在于其造價昂貴、集成度低和高功耗。</p><p>　　1.2.2 基于軟

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

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

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

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

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

33、數(shù)據(jù)結(jié)構(gòu)</p><p>　　基本的二進制Trie數(shù)據(jù)結(jié)構(gòu)早在20世紀70年代就被提出，這種Trie的每個結(jié)點最多包含2個指針，分別指向他的左右孩子結(jié)點，代表前綴的某個比特位為‘0’和‘1’時兩種情況的搜索分支。在Trie樹中，處于第L層的結(jié)點實際上代表了一類地址前L-1比特均相同的地址空間，如圖1-3所示。查找搜索時，根據(jù)待查找IP地址的比特位，從Trie樹的根結(jié)點開始依次向其子孫結(jié)點進行，直到再無分支可搜索為

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

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

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

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

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

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

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

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

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

43、各個分支按照前綴集分布特點自適應(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é)點分布較為密集時才較為有效。</p><p>　　1.3.4 級壓縮Trie（LC-Trie）算法</p><p>　　如上所述，路徑壓縮Trie適合于

44、結(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é)點，分支記錄將是3，孩子結(jié)點的個數(shù)剛好是分支記錄的2的冪次方。另外每個父結(jié)點還記錄跳步(skip

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

67、結(jié)果以只寫的方式存入名為“BinaryTrie”的文本文件之中，存儲格式是“待查IP地址 匹配的前綴值 下一跳端口號 查找次數(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 算法測試及性能評價</p><p><b>　　4.1 測試環(huán)境</b></p>

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

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

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

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

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

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

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

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

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

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

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

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