本文選題：內(nèi)容中心網(wǎng)絡(luò)CCN + 轉(zhuǎn)發(fā)信息表FIB��； 參考：《解放軍信息工程大學(xué)》2014年博士論文

【摘要】：內(nèi)容中心網(wǎng)絡(luò)CCN(Content Centric Networking)的提出是網(wǎng)絡(luò)技術(shù)的一次革新,傳統(tǒng)IP網(wǎng)絡(luò)關(guān)心信息“在哪兒”,而CCN直接關(guān)心請求的數(shù)據(jù)“是什么”,數(shù)據(jù)本身成為因特網(wǎng)架構(gòu)中的核心要素,從根本上解決IP地址耗盡、安全性和移動性等傳統(tǒng)問題,其系統(tǒng)架構(gòu)及相關(guān)支撐技術(shù)研究已成為熱點(diǎn)。查表是內(nèi)容中心網(wǎng)絡(luò)的研究重點(diǎn)之一。CCN中信息或者數(shù)據(jù)的傳遞基于數(shù)據(jù)名字而不是IP地址,表項規(guī)模比IP路由表高出兩個數(shù)量級,達(dá)到108條;基于TCAM或分布式存儲單元等傳統(tǒng)的實現(xiàn)手段不能滿足CCN表項的容量需求。目前對CCN查找技術(shù)的研究尚處于起步階段,既缺乏整體的解決思路,也沒有針對性的高效算法,需要在理論模型、算法研究、工程實現(xiàn)等層面展開全方位的研究。本文圍繞其轉(zhuǎn)發(fā)信息表FIB與未決興趣表PIT這兩大不同需求特點(diǎn)的查找問題開展了以下研究工作:1、描述IP前綴集的二進(jìn)制樹模型無法用于表示FIB前綴集,必須尋找新的合理模型。根據(jù)CCN前綴集層次化命名的基本屬性特征,提出一種基于有根樹的FIB名字前綴樹模型,并分析總結(jié)實際域名特點(diǎn),指出了該模型參數(shù)的統(tǒng)計特性。該模型具有較強(qiáng)的理論和工程應(yīng)用價值。2、已有空間利用率高的算法,如布魯姆過濾器,通常要求很高的存儲器訪問帶寬,被迫依賴于分布式存儲單元實現(xiàn),容量受限,不能滿足FIB的規(guī)模需求。利用大容量存儲單元一次訪問可獲得很寬數(shù)據(jù)的特點(diǎn),并考慮實際FIB的負(fù)載特性,提出一種負(fù)載均衡的FIB最長匹配快速搜索方法,稱為EMA-NPMA算法,并分析給出了調(diào)整成功率定理以及任意次塊空間比例的理論計算式,在此基礎(chǔ)上給出誤判率、吞吐率的估算方法。理論分析和仿真實驗表明,在付出一定誤判率代價的條件下,該算法很好地滿足了名字前綴匹配在空間和時間上的雙重要求,每一條目表示僅需10多個比特,且90%以上的前綴最長匹配均可以一次存儲器訪問完成。以一片容量為1.25G比特的RLDRAM為例,算法可在誤判率低于5%的條件下,以每秒約60M次的包轉(zhuǎn)發(fā)速率,實現(xiàn)規(guī)模高達(dá)100M條的名字前綴的最長匹配。3、基于d-left的完美哈�？色@得很好的空間利用率,但每一個條目查詢可能需要d次查找,吞吐率低。本文首先提出一種基于最小完美哈希函數(shù)(MPHF)的哈希桶索引機(jī)制。分析發(fā)現(xiàn),d-left可模型化為一個可容納更多沖突項的哈希桶,為此,提出建立虛擬哈希桶并利用所提的索引機(jī)制來確定條目所在的子表,實現(xiàn)d-left哈希表查找的無誤判準(zhǔn)確定位,將對哈希表的訪問限制到確定的一次。分析和仿真表明,算法為每一條目付出約10比特的空間代價,但只需一次存儲器訪問,從而可利用片外大容量存儲單元來解決CCN前綴集這樣超大規(guī)模哈希表的查找加速難題。4、MPHF函數(shù)適用于面向靜態(tài)條目集合的應(yīng)用場景,用于動態(tài)數(shù)據(jù)集的索引時,由于條目更新造成MPHF函數(shù)變化帶來更新效率問題。為此,對MPHF函數(shù)更新效率問題進(jìn)行數(shù)學(xué)建模和理論分析,提出條目添加的平均搬移數(shù)定理,理論上給出了搬移次數(shù)與可選MPHF函數(shù)個數(shù)間的關(guān)系,并因此提出用地址映射表來實現(xiàn)無搬移的快速更新。5、PIT作為CCN區(qū)別于IP的重要特征,其選擇性超時老化和逐包處理機(jī)制,大大增加了查表處理的難度�？偨Y(jié)歸納不同PIT流量對搜索引擎的不同處理要求,提出一種PIT搜索引擎的操作模型,定量描述不同PIT流量分布對搜索引擎的吞吐率需求。6、基于定時掃描的老化方法對存儲器帶寬要求高,基于軟件維護(hù)的老化方法則實時性差。PIT表項規(guī)模大、查找關(guān)鍵字長且可變,適合采用布魯姆過濾器作為搜索引擎。本文在布魯姆過濾器雙緩存老化機(jī)制的基礎(chǔ)上,提出了適合PIT的改進(jìn)算法A2-PIT,以很少的精度損失,即可實現(xiàn)無需額外掃描帶寬和通信代價的高效選擇性超時老化。7、PIT查找的最壞性能發(fā)生在鏈路中所有包均為新興趣包的情形,而新興趣包均為布魯姆過濾器的無匹配條目。本文在研究了布魯姆過濾器條目無匹配時的特點(diǎn)的基礎(chǔ)上,提出一種布魯姆過濾器無匹配查找加速控制方法,只需付出很少的主處理器邏輯資源代價,即可大大改善吞吐率最壞性能,將包轉(zhuǎn)發(fā)率提高到約為原來的1.5倍。
[Abstract]:Content Center Networking is an innovation in the network technology , where traditional IP networks care about where the information is , and what is " what is the data " directly concerned about the request In this paper , the research work is carried out in this paper , which is based on the data name instead of the IP routing table . This paper puts forward an improved algorithm A2 - PIT , which is suitable for the dynamic data set , and proposes an improved algorithm A2 - PIT which is suitable for the dynamic data set .

【學(xué)位授予單位】：解放軍信息工程大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2014
【分類號】：TP393.02

【參考文獻(xiàn)】

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

1 楊柳;馬少武;王曉湘;;以內(nèi)容為中心的互聯(lián)網(wǎng)體系架構(gòu)研究[J];信息通信技術(shù);2011年06期

2 唐暉;周旭;韓言妮;覃毅芳;;以內(nèi)容為中心的下一代寬帶網(wǎng)絡(luò)演進(jìn)[J];信息通信技術(shù);2011年04期

3 唐紅;吳勇軍;趙國鋒;;用于特定流匹配的隨機(jī)矩陣映射Hash算法研究[J];通信學(xué)報;2007年02期

4 尚鳳軍,唐紅,潘英俊;完全無沖突散列IP分類算法研究[J];通信學(xué)報;2005年02期

5 周立力;基于TCAM技術(shù)的高速路由查找方案[J];計算機(jī)應(yīng)用;2003年09期

，

本文編號：1747487