基于IP網絡的路由查找算法的研究與設計.pdf

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

2、流量還是由IPv4網絡承載，研究基于IPv4的路由查找算法有其現實意義。如何解決最長前綴匹配問題，是設計路由查找算法的核心問題，目前眾多學者主要圍繞路由查找算法的最長前綴匹配問題展開研究。
　　IPv6作為IPv4的下一代技術，具有128位的地址長度。它對IPv6網絡中的核心路由器處理負擔更重、要求更高。已有的基于IPv4的路由查找算法，擴展到IPv6后無法適應新的需求或效率低下，需要建立新的基于IPv6的路由查找算法。
　

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

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

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