本文關(guān)鍵詞：命名數(shù)據(jù)網(wǎng)絡(luò)的路由查找算法研究

  更多相關(guān)文章： 命名數(shù)據(jù)網(wǎng)絡(luò) 路由查找 查找樹(shù) 布隆過(guò)濾器

【摘要】：以IP包交換為核心的互聯(lián)網(wǎng)結(jié)構(gòu)設(shè)計(jì)已經(jīng)流行了數(shù)十年,網(wǎng)絡(luò)之間互聯(lián)最初的目標(biāo)是實(shí)現(xiàn)硬件資源的共享。然而,隨著技術(shù)飛速發(fā)展和信息的爆炸式增加,信息共享成為了如今的主要需求,硬件共享變得不再那么重要。命名數(shù)據(jù)網(wǎng)絡(luò)作為一種全新的網(wǎng)絡(luò)模式,其目的是為了更好的滿足用戶快速便捷的訪問(wèn)互聯(lián)網(wǎng)內(nèi)容的需求。命名數(shù)據(jù)網(wǎng)絡(luò)通過(guò)內(nèi)容名字進(jìn)行路由查找與轉(zhuǎn)發(fā)。與IP網(wǎng)絡(luò)路由方法相比,名字查找有一些不同的特征。例如可變長(zhǎng)度、層次化的名字結(jié)構(gòu);比IP網(wǎng)絡(luò)大2~3個(gè)數(shù)量級(jí)的路由表規(guī)模;內(nèi)容頻繁的發(fā)布刪除導(dǎo)致的路由更新。這些特征使得實(shí)現(xiàn)快速名字路由查找算法成為一個(gè)重大而艱巨的任務(wù)。針對(duì)這一問(wèn)題,本課題結(jié)合命名數(shù)據(jù)網(wǎng)絡(luò)名字的特性,對(duì)名字結(jié)構(gòu)及算法進(jìn)行了改進(jìn)。本課題先研究了常用的查找樹(shù)、哈希表、布隆過(guò)濾器三種經(jīng)典結(jié)構(gòu)的名字路由查找算法。針對(duì)查找樹(shù)存儲(chǔ)開(kāi)銷(xiāo)太大,哈希表存在碰撞且不滿足最長(zhǎng)前綴匹配等問(wèn)題,并結(jié)合名字層次結(jié)構(gòu)的特征,本課題設(shè)計(jì)了一種基于哈希查找樹(shù)的路由算法。這種方法通過(guò)哈希函數(shù)將詞元組件而不是整個(gè)名字散列成哈希值,從而適用于最長(zhǎng)前綴匹配。同時(shí)每層詞元單獨(dú)設(shè)計(jì)哈希函數(shù)能保證哈希碰撞控制在一個(gè)很低的范圍內(nèi)。然后查找樹(shù)的狀態(tài)轉(zhuǎn)移不通過(guò)詞元而是通過(guò)哈希值匹配來(lái)確定,使得查找效率得到提升。此外哈希值比名字詞元將占用更少的存儲(chǔ)空間,從而降低了結(jié)構(gòu)的空間開(kāi)銷(xiāo)。同時(shí)哈希計(jì)算可以預(yù)處理,和名字查找處于并行結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明該結(jié)構(gòu)有效的提升了查找樹(shù)的空間效率并小幅度提升了查找效率。為了進(jìn)一步解決名字可變長(zhǎng)度導(dǎo)致的查找樹(shù)結(jié)構(gòu)層次過(guò)深,查找效率低下的問(wèn)題。本課題設(shè)計(jì)了一種詞元查找樹(shù)結(jié)合布隆過(guò)濾器的組合數(shù)據(jù)結(jié)構(gòu)。該算法結(jié)構(gòu)充分考慮到命名數(shù)據(jù)網(wǎng)絡(luò)名字分層可變長(zhǎng)的結(jié)構(gòu),將一個(gè)完整的名字劃分為兩個(gè)較短的部分處理:前一部分是固定長(zhǎng)度的查找樹(shù)段,后一部分是可變長(zhǎng)度的布隆過(guò)濾器段。并著重討論了不同的分層對(duì)于算法效率的影響,最終得出一個(gè)最優(yōu)的分層劃分。對(duì)比實(shí)驗(yàn)結(jié)果表明,該結(jié)構(gòu)在存儲(chǔ)開(kāi)銷(xiāo)和查找速度方面均有良好的表現(xiàn)。
【關(guān)鍵詞】：命名數(shù)據(jù)網(wǎng)絡(luò) 路由查找 查找樹(shù) 布隆過(guò)濾器
【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：TP393.02
【目錄】：

• 摘要4-5
• ABSTRACT5-9
• 第1章 緒論9-15
• 1.1 課題背景及研究的目的和意義9-10
• 1.2 國(guó)內(nèi)外研究現(xiàn)狀10-13
• 1.3 本文主要研究?jī)?nèi)容13-14
• 1.4 本文的組織結(jié)構(gòu)14-15
• 第2章 命名數(shù)據(jù)網(wǎng)絡(luò)及其路由算法概述15-24
• 2.1 命名數(shù)據(jù)網(wǎng)絡(luò)體系結(jié)構(gòu)15-20
• 2.1.1 數(shù)據(jù)包類(lèi)型16-18
• 2.1.2 命名與轉(zhuǎn)發(fā)機(jī)制18-19
• 2.1.3 數(shù)據(jù)包路由查找過(guò)程19-20
• 2.2 路由查找算法20-23
• 2.3 本章小結(jié)23-24
• 第3章 基于哈希多叉樹(shù)的路由查找算法24-32
• 3.1 名字路由表的建立24-25
• 3.2 詞元查找樹(shù)25-26
• 3.3 哈希多叉查找樹(shù)算法26-31
• 3.3.1 算法結(jié)構(gòu)26-28
• 3.3.2 算法描述28-30
• 3.3.3 算法分析30-31
• 3.4 本章小結(jié)31-32
• 第4章 基于組合結(jié)構(gòu)的路由查找算法32-41
• 4.1 問(wèn)題分析32-33
• 4.2 建立查找樹(shù)與布隆過(guò)濾器組合模型33-37
• 4.2.1 整體框架描述33
• 4.2.2 模型邊界的劃分33-35
• 4.2.3 并行查找過(guò)程35
• 4.2.4 更新方案35-37
• 4.3 模型分析37-40
• 4.4 本章小結(jié)40-41
• 第5章 仿真實(shí)驗(yàn)與分析41-50
• 5.1 實(shí)驗(yàn)平臺(tái)及流程41-42
• 5.2 哈希多叉樹(shù)實(shí)驗(yàn)分析42-44
• 5.3 組合結(jié)構(gòu)實(shí)驗(yàn)分析44-49
• 5.3.1 內(nèi)存開(kāi)銷(xiāo)44-45
• 5.3.2 分層影響分析45-48
• 5.3.3 總體時(shí)延48-49
• 5.4 本章小結(jié)49-50
• 結(jié)論50-51
• 參考文獻(xiàn)51-57
• 致謝57

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

10 周昔平;高德遠(yuǎn);樊曉椏;張盛兵;;基于索引和壓縮的超高速路由查找及更新算法[J];小型微型計(jì)算機(jī)系統(tǒng);2006年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 張理陽(yáng);一種基于哈希策略的路由查找算法[D];長(zhǎng)沙理工大學(xué);2011年

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

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

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

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

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

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

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

，

本文編號(hào)：827102