本文選題：并行路由查找算法 + Trie樹��； 參考：《光通信研究》2014年05期

【摘要】：為解決在多核處理器平臺(tái)下路由器報(bào)文轉(zhuǎn)發(fā)時(shí)路由查找速度慢的"瓶頸"問題,提出了一種基于分割的多分枝Trie樹的并行路由查找算法。該算法將一棵多分枝Trie樹根據(jù)處理器的核數(shù)分割成若干子樹,每棵子樹又構(gòu)成一棵單獨(dú)的多分枝Trie樹,子樹中取消了前綴查找,采取組成一個(gè)大中間節(jié)點(diǎn)的方式,在中間節(jié)點(diǎn)之間采用固定步長(zhǎng)查詢,中間節(jié)點(diǎn)內(nèi)部采用二進(jìn)制Trie樹來表示。實(shí)驗(yàn)結(jié)果表明,該算法具有訪存次數(shù)少、查詢速度快、占用存儲(chǔ)空間少和更新開銷小等特點(diǎn),同時(shí)適用于IPv4和IPv6地址。
[Abstract]:In order to solve the "bottleneck" problem of routing lookup slow when router packets are forwarded on multi-core processor platform, a parallel routing lookup algorithm based on partitioned multi-branch Trie tree is proposed. The algorithm divides a multi-branched Trie tree into several sub-trees according to the kernel number of the processor. Each sub-tree constitutes a single multi-branched Trie tree, and the prefix search is cancelled in the sub-tree, and a large and medium node is formed. The intermediate nodes are queried with fixed step size and the intermediate nodes are represented by binary Trie tree. Experimental results show that the proposed algorithm has the advantages of less memory access, faster query speed, less storage space and less update overhead. It is also suitable for IPv4 and IPv6 addresses.
【作者單位】： 光纖通信技術(shù)和網(wǎng)絡(luò)國家重點(diǎn)實(shí)驗(yàn)室;武漢烽火網(wǎng)絡(luò)有限責(zé)任公司;
【分類號(hào)】：TP393.02

【參考文獻(xiàn)】

相關(guān)期刊論文 前3條

1 陳蹊;趙躍龍;;多分枝trie樹路由查找算法研究[J];電子設(shè)計(jì)工程;2010年03期

2 楊玉梅;黎仁國;;基于二分查找和Trie的IPv6路由查找算法[J];蘭州理工大學(xué)學(xué)報(bào);2012年04期

3 曹折波;李青;;多核處理器并行編程模型的研究與設(shè)計(jì)[J];計(jì)算機(jī)工程與設(shè)計(jì);2010年13期

【共引文獻(xiàn)】

相關(guān)期刊論文 前10條

1 周瑞;常旭;林丹峰;楊林峰;;基于多分支Trie的路由查找算法設(shè)計(jì)與實(shí)現(xiàn)[J];大眾科技;2013年08期

2 崔陽;呂志平;陳正生;王宇譜;呂浩;;多核環(huán)境下的GNSS網(wǎng)平差數(shù)據(jù)并行處理研究[J];測(cè)繪學(xué)報(bào);2013年05期

3 李正浩;曾智洪;曾曉贏;史振寧;付仕清;;農(nóng)村信息化建設(shè)中多媒體數(shù)據(jù)的并行管理框架設(shè)計(jì)[J];重慶大學(xué)學(xué)報(bào);2013年12期

4 余濤;吳衛(wèi)東;;基于多核處理器的L7-Filter規(guī)則匹配改進(jìn)算法[J];計(jì)算機(jī)應(yīng)用;2012年03期

5 汪前進(jìn);高勇;李存華;;基于多核處理器的多任務(wù)并行處理技術(shù)研究[J];計(jì)算機(jī)應(yīng)用與軟件;2012年07期

6 杜飛;董治國;苗琳;庹宇鵬;;基于無沖突哈希表和多比特樹的兩級(jí)IPv6路由查找算法[J];計(jì)算機(jī)應(yīng)用;2013年05期

7 黃偉建;牛沛;蔡忠亞;;水質(zhì)預(yù)報(bào)系統(tǒng)中垂向湍擴(kuò)散并行算法實(shí)現(xiàn)研究[J];計(jì)算機(jī)工程與設(shè)計(jì);2011年12期

8 程小華;鄭昌文;吳佳澤;;基于多核處理器的星空背景彌散效果實(shí)現(xiàn)算法[J];計(jì)算機(jī)工程與設(shè)計(jì);2013年01期

9 羅新建;;計(jì)算機(jī)應(yīng)用程序編輯模型的發(fā)展[J];數(shù)字技術(shù)與應(yīng)用;2013年08期

10 李彬彬;李青;;LBM在多核并行編程模型中的應(yīng)用[J];計(jì)算機(jī)技術(shù)與發(fā)展;2011年07期

相關(guān)碩士學(xué)位論文 前10條

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

2 王世遠(yuǎn);基于Linux的XviD編碼多核并行化的研究與實(shí)現(xiàn)[D];東北大學(xué);2011年

3 石文娟;異構(gòu)環(huán)境下分層并行通用計(jì)算模型的設(shè)計(jì)與實(shí)現(xiàn)[D];中國海洋大學(xué);2012年

4 牛沛;并行計(jì)算在膠州灣水質(zhì)預(yù)報(bào)系統(tǒng)中的應(yīng)用研究[D];河北工程大學(xué);2012年

5 葉光輝;基于多分支Trie的虛擬路由查找算法研究[D];湖南大學(xué);2012年

6 王東菊;基于Bloom濾波器的快速路由查找算法研究[D];大連理工大學(xué);2013年

7 崔陽;大規(guī)模測(cè)量平差分布式計(jì)算技術(shù)及應(yīng)用研究[D];解放軍信息工程大學(xué);2013年

8 劉建志;基于虛擬路由器的IPv6路由策略研究[D];哈爾濱工業(yè)大學(xué);2012年

9 余濤;基于多核處理器的L7-Filter規(guī)則匹配改進(jìn)算法[D];武漢科技大學(xué);2013年

10 馮富輝;并行處理技術(shù)在通信系統(tǒng)中的應(yīng)用研究[D];北京交通大學(xué);2014年

【二級(jí)參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 張彥軍;賈世國;薛曉敏;;IPv6下DoS/DDoS SYN Flood入侵和攻擊的檢測(cè)[J];蘭州理工大學(xué)學(xué)報(bào);2008年02期

2 穆曉霞;陳留院;牛振齊;;IPv4到IPv6的遷移技術(shù)研究[J];河南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2010年06期

3 劉永鋒,楊宗凱;高速路由器中基于樹型結(jié)構(gòu)路由查找算法的研究與實(shí)現(xiàn)[J];計(jì)算機(jī)工程與科學(xué);2004年01期

4 譚明鋒;高蕾;龔正虎;;IP路由查找算法研究概述[J];計(jì)算機(jī)工程與科學(xué);2006年06期

5 陳俊;陳孝威;;移動(dòng)IPv4/IPv6的虛擬機(jī)遷移過渡框架[J];計(jì)算機(jī)應(yīng)用;2011年05期

6 張宏麗;昝利國;;IPv6路由查找算法探究[J];內(nèi)蒙古電大學(xué)刊;2010年02期

7 馬杰;張永平;楊磊;;基于LFT和DAG方式的IPv6路由查找算法[J];計(jì)算機(jī)工程與設(shè)計(jì);2008年05期

8 吳彤,楊嗣超,諸鴻文;路由表快速查找算法[J];通信技術(shù);2000年04期

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

10 劉宏義;;IPv6快速路由查找算法分析與研究[J];微電子學(xué)與計(jì)算機(jī);2008年04期

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 王智強(qiáng),王振興,張定心;基于Trie的快速路由查找算法[J];信息工程大學(xué)學(xué)報(bào);2003年03期

2 莊雄雄;呂蘭蘭;高宋O，

本文編號(hào)：1901747