畢業(yè)論文----基于binary trie的ip地址查找算法研究與實現(xiàn)_第1頁
已閱讀1頁,還剩33頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

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

2、 業(yè): 網(wǎng)絡工程 </p><p>  班 級: </p><p>  學生姓名: </p><p>  導師姓名:

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

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

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

6、設計 (論文)成績評定表</p><p>  西安郵電學院畢業(yè)論文(設計)成績評定表(續(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結構的路由算法的介紹4</p><p>  1.4 論文結構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 算法的詳細設計與實現(xiàn)13</p><p>  3.1 算法邏輯結構的實現(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 測試結果17</p><p>  4.3 算法的可擴展性評價19</p><p><b>

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

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

12、查找的性能。</p><p>  本文簡要介紹了目前因特網(wǎng)的使用情況及發(fā)展趨勢以及當下路由查找算法的現(xiàn)狀,并簡要介紹了幾種常用的基于Trie結構的IP路由算法。重點研究了基于Trie結構的基礎算法基于Binary Trie的IP地址查找算法,本文完成了該算法的實現(xiàn)并根據(jù)實驗數(shù)據(jù)對其進行了定性及定量的性能分析。</p><p>  關鍵詞: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)走進千家萬戶,成為人們生活中不可缺少的組成部分,它不僅為人們提供了各種各樣的簡單且快捷的通信與信息檢索手段,更重要的是為人們提供了巨大的信息資源和服務資源。隨著越來越多的人認識并使用互聯(lián)網(wǎng),使得在互聯(lián)網(wǎng)中起互聯(lián)作用的路由器或路由交換機不堪重負。路由器或路由交換機完成的核心功能就是在路由表中為來自不同鏈路、去往不同目的地的IP分組

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

34、止,其間記錄的最后一個前綴結點對應的路由信息就是查找結果?;镜亩M制Trie數(shù)據(jù)結構構造的Trie最多有W+1層,因此每次搜索的次數(shù)最多為W次,所以查找時間復雜度是O(W);存儲一個前綴,最多可能產生W個Trie結點,因而該算法的存儲復雜度為O(WN)。</p><p>  1.3.2 路徑壓縮Trie算法</p><p>  要提高查找速度、減少存儲器訪問操作的次數(shù),必須降低Trie樹

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

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

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

38、的子Trie結構”的末端,因而對應的單分支Trie結構被壓縮掉。為了保證查找正確,在結點中增加兩個域:Bitposition,表示下一個要比較的字符位;Bitstring,表示從根到該結點位置的路徑對應的位串。路徑壓縮Trie的每一個葉子結點含有一個路由前綴和一個下一跳信息指針。當遍歷一個路徑壓縮時間Trie查找一個地址時,將結點中的位串與待查找的地址比較。如果該位串是地址的一個前綴,則存儲下一跳信息指針(如果存在)并且轉向下一個結點。

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

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

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

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

43、各個分支按照前綴集分布特點自適應選定不同的搜索步長:當子Trie結構分支是滿2L叉樹時,才使用步長L。這樣既能發(fā)揮多比特Trie的優(yōu)勢,同時由于子Trie結構本來就是滿2L叉樹,不會產生結點復制。但我們也注意到,層壓縮Trie僅在Trie結點分布較為密集時才較為有效。</p><p>  1.3.4 級壓縮Trie(LC-Trie)算法</p><p>  如上所述,路徑壓縮Trie適合于

44、結點稀疏的情況。Nilsson ET AL提出了一種級壓縮技術用于結點稠密的情況。這種技術被稱為級壓縮Trie,簡稱LC一Trie。LC一Trie結合路徑壓縮和多位Trie的特點進一步優(yōu)化基本Trie結構。LC壓縮樹中每個內部結點的孩子結點都是連續(xù)存放的,父結點只存放左孩子指針,每個父結點還存放分支(branch)信息,如果父結點有8個孩子結點,分支記錄將是3,孩子結點的個數(shù)剛好是分支記錄的2的冪次方。另外每個父結點還記錄跳步(skip

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

67、結果以只寫的方式存入名為“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內存,英特爾奔騰處理器,Ubuntu 7.10操作系統(tǒng),標準gcc編譯器。</p><p><b>  4.2 測試結果</b></p><p>  測試結果如表4-1所示。</p><p>  表4-1 實驗測試結果</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、表構造Binary Trie結構所需存儲容量</p><p>  本文用構建相應的二叉樹所需結點的個數(shù)來表示一個路由表所需的存儲容量。如圖4-4所示,橫軸表示不同的路由表文本文件,豎軸表示每個路由表所需的存儲空間。</p><p>  圖4-5待查路由表項所需的平均查找次數(shù)</p><p>  如圖4-5所示,橫軸表示不同的待查IP文本文件在所對應的路由表中的查找結

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

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

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

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

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

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

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

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

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論