本文關(guān)鍵詞：基于IP網(wǎng)絡(luò)的路由查找算法的研究與設(shè)計

  更多相關(guān)文章： 路由查找 最長前綴匹配 哈希函數(shù) 多比特樹

【摘要】：路由器是組成互聯(lián)網(wǎng)的重要節(jié)點設(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ù)的流量還是由IPv4網(wǎng)絡(luò)承載,研究基于IPv4的路由查找算法有其現(xiàn)實意義。如何解決最長前綴匹配問題,是設(shè)計路由查找算法的核心問題,目前眾多學(xué)者主要圍繞路由查找算法的最長前綴匹配問題展開研究。IPv6作為IPv4的下一代技術(shù),具有128位的地址長度。它對IPv6網(wǎng)絡(luò)中的核心路由器處理負(fù)擔(dān)更重、要求更高。已有的基于IPv4的路由查找算法,擴(kuò)展到IPv6后無法適應(yīng)新的需求或效率低下,需要建立新的基于IPv6的路由查找算法。論文主要圍繞基于IPv4、IPv6路由查找算法展開,分別給出了適用于IPv4和IPv6的路由查找算法。主要工作包括:1、分析了 IPv4的地址結(jié)構(gòu)及其發(fā)展史,通過對核心路由器中路由表數(shù)據(jù)的分析,發(fā)現(xiàn)了 IPv4地址前綴分布呈現(xiàn)一定特點:地址前綴長度為24的表項最多。論文針對這個特性,提出了一種哈希表和多比特樹相結(jié)合的分階段路由查找算法,算法將路由查找階段分為兩個階段,分別是哈希表查找階段和多比特樹結(jié)構(gòu)查找階段。為了減少對存儲器的訪問,還提出了一種固定高度的多比特樹結(jié)構(gòu):4-3Trie,該結(jié)構(gòu)將路由查找時訪問存儲器的次數(shù)限定在了可接受的范圍之內(nèi)。算法分析和實驗仿真表明,該算法通過利用IPv4地址前綴分布的特點,提高了查找效率,具有良好的路由查找性能。2、分析了 IPv6地址結(jié)構(gòu),通過對從Internet核心路由器的路由表中獲取了路由前綴分布數(shù)據(jù)分析,發(fā)現(xiàn)地址前綴長度為16倍數(shù)的表項最多,其中尤以地址前綴長度為48的表項最多,其次是地址前綴長度為32的表項。同時分析還發(fā)現(xiàn),在路由表中前綴中以20、24、26、28和2a開頭的表項占了絕大多數(shù)。在此分析基礎(chǔ)上,綜合運(yùn)用了哈希表和多比特樹兩種結(jié)構(gòu),提出了一種適用于IPv6的分階段的路由查找算法,給出了 H16、H32、H32c、H48、H48c和H64六個哈希函數(shù)和一套哈希沖突解決策略。同時算法還提出了 6-5-4Trie結(jié)構(gòu),將樹的高度控制在了可接受的范圍,并且,算法在壓縮樹高度的同時,盡可能的降低樹的稀疏程度來減少存儲空間的浪費(fèi)。算法分析和實驗仿真證明,該算法在查找速度和存儲空間上都有優(yōu)勢,能夠滿足核心路由器的性能要求。路由查找算法是復(fù)雜的,眾多學(xué)者對其進(jìn)行了深入的研究,我們是在前人研究的基礎(chǔ)上進(jìn)行了改進(jìn)和探索。相關(guān)研究成果已被錄用,即將在國內(nèi)外的核心期刊上發(fā)表。
【學(xué)位授予單位】：揚(yáng)州大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP393.0

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 廖恬瑜,涂曉東,黃協(xié);高速路由查找算法的研究[J];電子科技大學(xué)學(xué)報;2004年06期

2 徐恪,徐明偉,吳建平,吳劍;路由查找算法研究綜述[J];軟件學(xué)報;2002年01期

3 王智強(qiáng),王振興,張定心;快速路由查找算法研究[J];計算機(jī)應(yīng)用研究;2004年02期

4 劉英臣;傅光軒;;路由查找技術(shù)的分析及研究[J];貴州大學(xué)學(xué)報(自然科學(xué)版);2006年03期

5 郭潤偉;;路由查找算法研究與分析[J];科技經(jīng)濟(jì)市場;2009年06期

6 朱國勝;余少華;;一種新的二分路由查找方法[J];小型微型計算機(jī)系統(tǒng);2010年09期

7 袁博;汪斌強(qiáng);王志明;;并行多流水綠色路由查找架構(gòu)和算法[J];西安電子科技大學(xué)學(xué)報;2012年02期

8 田園;王萌;繆建軍;劉葳;;星上路由查找的設(shè)計與分析[J];電子質(zhì)量;2012年04期

9 徐宇鋒,李樂民;快速路由查找算法及其實現(xiàn)[J];通信技術(shù);2001年07期

10 姚興苗,李樂民,胡光岷;快速路由器的路由查找和流分類算法研究[J];電子科技大學(xué)學(xué)報;2004年06期

中國重要會議論文全文數(shù)據(jù)庫 前3條

1 張榮高;龔雪春;;基于位圖映射路由查找算法的研究[A];2006通信理論與技術(shù)新進(jìn)展——第十一屆全國青年通信學(xué)術(shù)會議論文集[C];2006年

2 王燕;;IPv6的快速路由查找算法研究[A];2005年全國開放式分布與并行計算學(xué)術(shù)會議論文集[C];2005年

3 苗建松;丁煒;;改進(jìn)的TCAM路由更新方法與實現(xiàn)[A];2006年全國開放式分布與并行計算學(xué)術(shù)會議論文集（二）[C];2006年

中國重要報紙全文數(shù)據(jù)庫 前1條

1 吳;神碼網(wǎng)絡(luò)加速多業(yè)務(wù)融合[N];計算機(jī)世界;2006年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前6條

1 王振興;NGI高性能路由器轉(zhuǎn)發(fā)處理算法與實現(xiàn)[D];南京理工大學(xué);2004年

2 譚明鋒;域間路由協(xié)議BGP-4健壯性測試技術(shù)的研究[D];國防科學(xué)技術(shù)大學(xué);2005年

3 鄭凱;高性能IP路由查找和分組分類技術(shù)的研究[D];清華大學(xué);2006年

4 汪漪;內(nèi)容中心網(wǎng)絡(luò)路由查找關(guān)鍵技術(shù)研究[D];清華大學(xué);2013年

5 胥小波;新型蜜網(wǎng)體系結(jié)構(gòu)及告警聚類的關(guān)鍵技術(shù)研究[D];北京郵電大學(xué);2012年

6 朱國勝;高速分組查找規(guī)則匹配算法研究[D];華中科技大學(xué);2010年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 張寧;基于Lua的手游服務(wù)器的研究與設(shè)計[D];南華大學(xué);2015年

2 賀雨虹;命名數(shù)據(jù)網(wǎng)絡(luò)的路由查找算法研究[D];哈爾濱工業(yè)大學(xué);2015年

3 秦怡;基于IP網(wǎng)絡(luò)的路由查找算法的研究與設(shè)計[D];揚(yáng)州大學(xué);2017年

4 張理陽;一種基于哈希策略的路由查找算法[D];長沙理工大學(xué);2011年

5 王智強(qiáng);高速路由查找算法研究[D];中國人民解放軍信息工程大學(xué);2003年

6 張榮高;網(wǎng)絡(luò)處理器原型系統(tǒng)路由查找算法的研究[D];國防科學(xué)技術(shù)大學(xué);2006年

7 陳靜;路由器中路由查找子系統(tǒng)的實現(xiàn)和優(yōu)化[D];華中科技大學(xué);2006年

8 王波;基于FPGA的快速路由查找算法研究及實現(xiàn)[D];西安電子科技大學(xué);2009年

9 奚曉華;基于FPGA的可編程高速路由查找算法的研究與實現(xiàn)[D];南京郵電大學(xué);2013年

10 張曉波;路由查找算法的研究及其FPGA實現(xiàn)[D];華東師范大學(xué);2006年

，

本文編號：1279674