本文關(guān)鍵詞：基于哈希表與多比特樹的路由查找算法

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

【摘要】：網(wǎng)絡(luò)帶寬的急劇增加對處于網(wǎng)絡(luò)節(jié)點的路由器設(shè)備數(shù)據(jù)轉(zhuǎn)發(fā)速度提出了更高的要求。為此,將哈希表和多比特樹相結(jié)合,提出一種新的路由查找算法。根據(jù)路由前綴的長度將路由表項分層存儲在固定的三層Tree中,采用哈希表存儲路由下一跳的信息,根據(jù)目的 IP地址在三層Tree結(jié)構(gòu)中按最長前綴匹配的原則進行快速路由表項定位,并通過表項的信息在對應的哈希表中讀取下一跳信息,進行數(shù)據(jù)轉(zhuǎn)發(fā)。在多核平臺上的測試結(jié)果表明,該算法在百萬條路由環(huán)境下可達到雙向10 GB/s的速度,平均查找次數(shù)介于1~2次之間,平均延時小于30μs。
【作者單位】： 光纖通信技術(shù)和網(wǎng)絡(luò)國家重點實驗室;武漢烽火網(wǎng)絡(luò)有限責任公司;
【關(guān)鍵詞】： 路由器 路由查找 哈希表 多比特樹 最長前綴匹配
【基金】：國家“863”計劃基金資助項目“軟件定義網(wǎng)絡(luò)體系結(jié)構(gòu)與關(guān)鍵技術(shù)研發(fā)與示范”(2015AA016100)
【分類號】：TP301.6;TP393.05
【正文快照】： 中文引用格式:范富明,李念軍,雷升平,等.基于哈希表和多比特樹的路由查找算法[J].計算機工程,2015,41(9):63-67.英文引用格式:Fan Fuming,Li Nianjun,Lei Shengping,et al.Route Lookup Algorithm Based on Hash Table and Multi-bitTree[J].Computer Engineering,2015,41(9):

【參考文獻】

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

1 殷科,鄧亞平;基于RAM和TCAM存儲結(jié)構(gòu)的高速路由查找算法[J];計算機工程與應用;2005年20期

2 王亞剛;杜慧敏;楊康平;;使用Hash表和樹位圖的兩級IPv6地址查找算法[J];計算機科學;2010年09期

3 華澤;班建民;陸悠;;基于分段地址結(jié)構(gòu)的快速路由查找算法[J];計算機與數(shù)字工程;2009年10期

4 汪志莉;沈富可;;一種基于哈希表和Trie樹的快速內(nèi)容路由查找算法[J];計算機應用與軟件;2009年10期

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

6 張琦;金胤丞;李苗;章建雄;;Trie樹路由查找算法在網(wǎng)絡(luò)處理器中的實現(xiàn)[J];計算機工程;2014年01期

7 陸笑天;李曦;周學海;紀金松;;基于前驅(qū)查找的快速IP路由查找和更新方案[J];計算機工程;2007年13期

【共引文獻】

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

1 鄧亞平;周美紅;;基于多層混合結(jié)構(gòu)的IPv6路由表查找算法[J];計算機應用;2013年02期

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

3 付仲滿;張輝;李苗;劉濤;;Hash算法在網(wǎng)絡(luò)處理器中的實現(xiàn)[J];計算機工程;2014年09期

4 劉陽;;基于三級索引和Trie的IPv6路由查找算法研究[J];山東農(nóng)業(yè)大學學報(自然科學版);2015年04期

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

1 王亞剛;IP路由器系統(tǒng)芯片關(guān)鍵技術(shù)研究[D];西安電子科技大學;2012年

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

1 余曉磊;WSN路由算法的研究[D];華東師范大學;2011年

2 泰冬雪;基于Hadoop的海量小文件處理方法的研究[D];遼寧大學;2011年

3 廖文斌;網(wǎng)間加速技術(shù)研究與實現(xiàn)[D];華中科技大學;2011年

4 徐軍霞;WSN節(jié)點感知區(qū)域模型實驗研究[D];華中科技大學;2011年

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

6 周小堯;基于網(wǎng)絡(luò)處理器的分布式入侵檢測系統(tǒng)研究與設(shè)計[D];中南大學;2007年

7 謝文亮;基于FPGA的入侵檢測系統(tǒng)的網(wǎng)絡(luò)包分類技術(shù)研究[D];廣州大學;2007年

8 嚴錦蕓;高速網(wǎng)絡(luò)信息過濾系統(tǒng)設(shè)計與實現(xiàn)[D];華中科技大學;2007年

9 程冕;面向網(wǎng)絡(luò)取證的CDMA2000報文處理與分流技術(shù)[D];國防科學技術(shù)大學;2012年

10 張云;基于軟件路由器的網(wǎng)絡(luò)環(huán)境自動構(gòu)建技術(shù)研究[D];哈爾濱工業(yè)大學;2014年

【二級參考文獻】

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

1 李振強;鄭東去;馬嚴;;TSB:一種多階段IPv6路由表查找算法[J];電子學報;2007年10期

2 孔婷;;IPv4網(wǎng)絡(luò)向IPv6網(wǎng)絡(luò)的演進[J];福建電腦;2008年01期

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

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

5 崔尚森,張白一;一種基于哈希表和Trie樹的快速IP路由查找算法[J];計算機工程與應用;2005年09期

6 喻梅;吳普青;趙政;于健;;基于B~+樹的分布式哈希表路由結(jié)構(gòu)[J];計算機工程與應用;2008年01期

7 王亞剛;杜慧敏;楊康平;;使用Hash表和樹位圖的兩級IPv6地址查找算法[J];計算機科學;2010年09期

8 吳強,蘇金樹,王勇軍;基于Patricia樹的快速多維分組分類算法[J];計算機工程;2004年21期

9 孫慶南;魯士文;;一種改進的二分法IPv6路由查找算法[J];計算機工程;2006年18期

10 徐海;徐濤;;一種改進的網(wǎng)絡(luò)選播路由算法[J];計算機工程;2008年01期

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

1 郭文文;基于TRIE的軟轉(zhuǎn)發(fā)路由查找模塊的設(shè)計實現(xiàn)[D];南京郵電大學;2011年

【相似文獻】

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

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

2 王智強,王振興,張定心;快速路由查找算法研究[J];計算機應用研究;2004年02期

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

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

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

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

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

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

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

10 周昔平;高德遠;樊曉椏;張盛兵;;基于索引和壓縮的超高速路由查找及更新算法[J];小型微型計算機系統(tǒng);2006年06期

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

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

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

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

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

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

2 王翌;路由器的三種身份[N];計算機世界;2004年

3 許文;路由器的類型及特點[N];中國計算機報;2006年

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

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

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

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

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

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

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

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

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

2 王智強;高速路由查找算法研究[D];中國人民解放軍信息工程大學;2003年

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

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

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

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

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

8 楊斌濤;IP路由查找算法的研究[D];電子科技大學;2010年

9 郭玲麗;基于多分支trie的快速路由查找算法[D];西安電子科技大學;2009年

10 郭文文;基于TRIE的軟轉(zhuǎn)發(fā)路由查找模塊的設(shè)計實現(xiàn)[D];南京郵電大學;2011年

，

本文編號：621299