基于IP網(wǎng)絡(luò)的路由查找算法的研究與設(shè)計(jì).pdf

1、路由器是組成互聯(lián)網(wǎng)的重要節(jié)點(diǎn)設(shè)備，位于ISO/OSI七層模型中的網(wǎng)絡(luò)層，負(fù)責(zé)網(wǎng)絡(luò)中數(shù)據(jù)的轉(zhuǎn)發(fā)工作。它將不同的網(wǎng)絡(luò)連接起來，并為經(jīng)過它的數(shù)據(jù)包選擇最佳的出口進(jìn)行轉(zhuǎn)發(fā)。路由器轉(zhuǎn)發(fā)數(shù)據(jù)包的快慢，決定了經(jīng)過路由器的所有數(shù)據(jù)包的傳輸速度。目前，鏈路上傳輸?shù)臄?shù)據(jù)已經(jīng)可以通過光纖來承載，其傳輸速度可以達(dá)到400Gbps，因此當(dāng)前路由器的性能瓶頸在于路由查找算法。路由器的查找效率決定了路由器的性能，決定了互聯(lián)網(wǎng)的數(shù)據(jù)吞吐量。
　　互聯(lián)網(wǎng)上大多數(shù)的

2、流量還是由IPv4網(wǎng)絡(luò)承載，研究基于IPv4的路由查找算法有其現(xiàn)實(shí)意義。如何解決最長(zhǎng)前綴匹配問題，是設(shè)計(jì)路由查找算法的核心問題，目前眾多學(xué)者主要圍繞路由查找算法的最長(zhǎng)前綴匹配問題展開研究。
　　IPv6作為IPv4的下一代技術(shù)，具有128位的地址長(zhǎng)度。它對(duì)IPv6網(wǎng)絡(luò)中的核心路由器處理負(fù)擔(dān)更重、要求更高。已有的基于IPv4的路由查找算法，擴(kuò)展到IPv6后無法適應(yīng)新的需求或效率低下，需要建立新的基于IPv6的路由查找算法。
　

3、　論文主要圍繞基于IPv4、IPv6路由查找算法展開，分別給出了適用于IPv4和IPv6的路由查找算法。主要工作包括:
　　1、分析了IPv4的地址結(jié)構(gòu)及其發(fā)展史，通過對(duì)核心路由器中路由表數(shù)據(jù)的分析，發(fā)現(xiàn)了IPv4地址前綴分布呈現(xiàn)一定特點(diǎn):地址前綴長(zhǎng)度為24的表項(xiàng)最多。論文針對(duì)這個(gè)特性，提出了一種哈希表和多比特樹相結(jié)合的分階段路由查找算法，算法將路由查找階段分為兩個(gè)階段，分別是哈希表查找階段和多比特樹結(jié)構(gòu)查找階段。為了減少對(duì)存儲(chǔ)器

4、的訪問，還提出了一種固定高度的多比特樹結(jié)構(gòu):4-3Trie，該結(jié)構(gòu)將路由查找時(shí)訪問存儲(chǔ)器的次數(shù)限定在了可接受的范圍之內(nèi)。算法分析和實(shí)驗(yàn)仿真表明，該算法通過利用IPv4地址前綴分布的特點(diǎn)，提高了查找效率，具有良好的路由查找性能。
　　2、分析了IPv6地址結(jié)構(gòu)，通過對(duì)從Internet核心路由器的路由表中獲取了路由前綴分布數(shù)據(jù)分析，發(fā)現(xiàn)地址前綴長(zhǎng)度為16倍數(shù)的表項(xiàng)最多，其中尤以地址前綴長(zhǎng)度為48的表項(xiàng)最多，其次是地址前綴長(zhǎng)度為32的

5、表項(xiàng)。同時(shí)分析還發(fā)現(xiàn)，在路由表中前綴中以20、24、26、28和2a開頭的表項(xiàng)占了絕大多數(shù)。在此分析基礎(chǔ)上，綜合運(yùn)用了哈希表和多比特樹兩種結(jié)構(gòu)，提出了一種適用于IPv6的分階段的路由查找算法，給出了H16、H32、H32c、H48、H48c和H64六個(gè)哈希函數(shù)和一套哈希沖突解決策略。同時(shí)算法還提出了6-5-4Trie結(jié)構(gòu)，將樹的高度控制在了可接受的范圍，并且，算法在壓縮樹高度的同時(shí)，盡可能的降低樹的稀疏程度來減少存儲(chǔ)空間的浪費(fèi)。算法分析