關(guān)于ipv6路由查找算法的發(fā)展?fàn)顩r研究

《關(guān)于ipv6路由查找算法的發(fā)展?fàn)顩r研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、關(guān)于IPv6路由查找算法的發(fā)展?fàn)顩r研究隨著IPv4地址即將面臨枯竭以及IPv6技術(shù)的發(fā)展，傳統(tǒng)的路由查找算法已不能滿足基于IPv6的128位地址的快速查找，一方面在算法的移植過程中，算法的適用性受到了很大的約束，另一方面，基于IPv4的32為前綴算法的查找性能已經(jīng)遠(yuǎn)遠(yuǎn)達(dá)不到要求。本文就目前存在的經(jīng)典的軟件路由算法進(jìn)行算法實(shí)現(xiàn)分析。最后，在對(duì)比中提出了基于IPv6新的路由查找算法研究設(shè)計(jì)的基本要求。關(guān)鍵詞：IPv6；路由查找；算法；trie樹　　引言：IP(InterProtocol)協(xié)議是TCP/IP協(xié)議族中兩個(gè)最重要的協(xié)議之一[1]。雖然各個(gè)方面在研究一些補(bǔ)救辦法，但是傳統(tǒng)的IPv4已經(jīng)不

2、能完全的滿足需求[1][2]，IPv6正是在人們對(duì)IPv4協(xié)議的地址空間、性能以及安全性等方面提出更高要求的情況下應(yīng)運(yùn)而生的[3]。IPv6是由IETF設(shè)計(jì)的，用來替代IPv4的下一代互聯(lián)X協(xié)議。它和IPv4相比，最大的特點(diǎn)是它使用了128位超長IP地址。2003年IPv6X絡(luò)已開始進(jìn)入規(guī)?；瘜?shí)施階段，IPv6將逐步取代IPv4，最終完全過度到IPv6。目前，許多國家和地區(qū)都在大力發(fā)展IPv6X絡(luò)，如我國的CER2是世界上規(guī)模最大的純IPv6X絡(luò)。然而現(xiàn)有的大多數(shù)路由查找算法只能適應(yīng)IPv4環(huán)境下的32位前綴，而應(yīng)用至IPv6中，由于內(nèi)存訪問次數(shù)或消耗的增加，導(dǎo)致算法性能非常低。因此，128

3、位的IPv6地址給路由查找?guī)砹诵碌奶魬?zhàn)，而隨著IPv6X絡(luò)規(guī)模的日趨擴(kuò)大，尋找高性能的IPv6路由查找算法也勢(shì)在必行[3]。1.基于IPv4的軟件路由查找算法　　IPv4查找算法主要有基于二分支的算法、基于多分支的算法，X絡(luò)前綴上的二分搜索算法、多路前綴值范圍搜索樹算法等[1]?；诙种У乃惴ㄓ卸M(jìn)制trie樹、Redix、Patricia[2]等。其思想是根據(jù)前綴值構(gòu)建二叉樹，檢索時(shí)以目標(biāo)地址作為索引，遍歷二叉樹。1.1二進(jìn)制trie樹　　IP路由要求查找最長匹配的前綴地址，即X絡(luò)地址?；跇湫谓Y(jié)構(gòu)的路由查找算法將最長前綴匹配查找模型化為l棵二進(jìn)制樹的過程,即二進(jìn)制trie樹——用結(jié)點(diǎn)

4、間的路徑表示前綴，一般規(guī)定從某節(jié)點(diǎn)出發(fā)到左孩子結(jié)點(diǎn)的路徑表示前綴中的對(duì)應(yīng)比特為0。到右孩子結(jié)點(diǎn)的路徑代表前綴中的對(duì)應(yīng)比特為1。IPv4中地址長度為32，由于CIDR技術(shù)的引入，所以二進(jìn)制trie樹的最大深度為32。其一次更新操作只需要首先查詢定位并修改一個(gè)結(jié)點(diǎn)，開銷較小。最大不足在于：對(duì)于IPv4地址查找最多需要32次訪存，而IPv6地址為128次。1.2路徑壓縮Patricia　　在二進(jìn)制trie樹中可能出現(xiàn)大量的單分支節(jié)點(diǎn)。這種單分支結(jié)點(diǎn)造成查找過程中浪費(fèi)大量的空間(空指針)和不必要的訪存，從而影響了算法的效率。由于單分支結(jié)構(gòu)代表查找只能按照一條路進(jìn)行，因此可以對(duì)其進(jìn)行壓縮Patrici

5、a[2]，壓縮單子節(jié)點(diǎn)。其查找過程與二進(jìn)制trie樹類似，但是在節(jié)點(diǎn)選取比特時(shí)使用的是比特位變量所指示的比特位。Patricia的最大深度有所降低，因此在最壞情況下的查找性能要優(yōu)于二進(jìn)制trie樹。2.基于IPv6的軟件路由查找算法　　在傳統(tǒng)的路由查找算法中，有的不能夠應(yīng)用到IPv6中，有的應(yīng)用到IPv6之后，由于內(nèi)存訪問次數(shù)或內(nèi)存消耗的增加，導(dǎo)致算法性能非常低。而由于Inter的發(fā)展和IP移動(dòng)的要求，傳統(tǒng)的IPv4X絡(luò)已面臨地址耗盡的危險(xiǎn)，新一代的X絡(luò)協(xié)議IPv6的采用將成為必然的趨勢(shì)，因此，現(xiàn)在又更多的路由查找算法專門針對(duì)IPv6提出。這些算法有：基于B-樹的IPv6路由查找算法、TSB

6、算法[3]、基于trie的IPv6路由查找算法、基于哈希表和trie樹的快速內(nèi)容路由查找算法[4]。2.1基于B-樹的IPv6路由查找算法　　B-樹路由查找算法，用IP地址作為插入和查找的關(guān)鍵字，將表項(xiàng)有序的存儲(chǔ)在B-樹結(jié)構(gòu)中，同時(shí)利用B-樹基于外存查找效率高這一優(yōu)點(diǎn)，在路由表規(guī)模龐大的情況下，可以有效地降低訪存次數(shù)，提高查找效率。由于IPv6地址由128位構(gòu)成。無法用一個(gè)整型數(shù)表示．因此要將地址進(jìn)行分段表示，對(duì)于字長為32位的機(jī)器?？梢苑譃樗亩?，表示形式為：，分別存儲(chǔ)在四個(gè)整型數(shù)據(jù)中，同時(shí)附加掩碼長度，就可以構(gòu)成在B-樹中插入和查找該表項(xiàng)所需的關(guān)鍵字。關(guān)鍵字Key共由五個(gè)字段構(gòu)成，Key[

7、0]對(duì)應(yīng)掩碼長度，分別對(duì)應(yīng)?！　‘?dāng)路由器收到來自一個(gè)X絡(luò)接口的數(shù)據(jù)包，提取目的IP，在B-樹中查找相應(yīng)的路由表項(xiàng)，按如下方法進(jìn)行關(guān)鍵字比對(duì)：對(duì)于B-樹結(jié)點(diǎn)中比較的關(guān)鍵字X絡(luò)位部分。若相同，則該結(jié)點(diǎn)中記錄的路由項(xiàng)是此IP的一個(gè)路由選擇，按照該路由項(xiàng)中指示的下一跳進(jìn)行路由。2.2TSB(Tree，SegmentTable，andRouteBucket)算法　　TSB[3]是一種多階段IPv6路由表查找算法。它對(duì)真