基于多層混合結(jié)構(gòu)的IPv6路由查找算法.pdf

1、隨著互聯(lián)網(wǎng)以及建立在互聯(lián)網(wǎng)上的各種新業(yè)務(wù)的飛速發(fā)展，互聯(lián)網(wǎng)的用戶規(guī)模不斷擴大。由此，IPv4已經(jīng)不能完全滿足互聯(lián)網(wǎng)的發(fā)展要求，并且暴露出了明顯的局限性，其中最大的缺陷就是IPv4地址空間的嚴重不足。IPv6以其強大的地址空間，更好的支持QoS服務(wù)等性能優(yōu)勢成為下一代互聯(lián)網(wǎng)的中心，得到快速的發(fā)展。在高速鏈路發(fā)展和IPv6網(wǎng)絡(luò)規(guī)模不斷擴大的大背景下，由于現(xiàn)有的路由查找算法并不能直接移植到IPv6上，因此研究適合于IPv6的高速路由查找算法勢

2、在必行。
　　 首先，文中通過對經(jīng)典的IPv4路由查找算法和現(xiàn)有一些IPv6路由查找算法的性能優(yōu)缺點進行研究分析，得出新算法可以嘗試結(jié)合多種查找技術(shù)來進行IPv6路由查找，以便發(fā)揮各種技術(shù)的優(yōu)點。然后，統(tǒng)計分析了當前IPv6骨干網(wǎng)路由表，總結(jié)出IPv6路由前綴的層次性特點，且不同的層次在所包含的前綴數(shù)目，前綴取值方面有不同的特點。根據(jù)IPv6路由前綴的層次性特點，借鑒了最優(yōu)查找樹針對查找概率不等時，查找性能良好的特點，結(jié)合使用了

3、平衡二叉樹及線性表的基本查找思想，研究了一種基于多層混合結(jié)構(gòu)的IPv6路由查找算法。該算法在第一層借鑒最優(yōu)查找樹的優(yōu)點，把所有前綴1～16比特這個位段的不同取值按其在路由表中出現(xiàn)的概率降序存儲在線性表中，在第二、三層把前綴17～32比特的位段值和33～48比特的位段值分別都用平衡二叉樹組織，在第四層把前綴49～64比特的位段值使用線性表組織。最后，用C語言開發(fā)了該算法的源代碼，并在安裝Windows XP操作系統(tǒng)，硬件配置為512M D