發(fā)布時(shí)間：2017-12-11 19:27

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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

中國(guó)重要報(bào)紙全文數(shù)據(jù)庫(kù) 前1條

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：1279674