發(fā)布時(shí)間：2018-05-19 04:15

  本文選題：網(wǎng)絡(luò)虛擬化 + 虛擬路由器�。� 參考：《清華大學(xué)》2016年博士論文

【摘要】：網(wǎng)絡(luò)虛擬化技術(shù)通過(guò)對(duì)網(wǎng)絡(luò)硬件基礎(chǔ)設(shè)施的資源進(jìn)行復(fù)用,可以以較低的經(jīng)濟(jì)成本建立多個(gè)虛擬網(wǎng)絡(luò)。這些虛擬網(wǎng)絡(luò)可以為有不同需求的用戶提供服務(wù),也可以為各種網(wǎng)絡(luò)創(chuàng)新研究提供真實(shí)的部署驗(yàn)證環(huán)境,加快互聯(lián)網(wǎng)的創(chuàng)新進(jìn)程。虛擬路由器是構(gòu)建虛擬網(wǎng)絡(luò)的核心設(shè)備,其轉(zhuǎn)發(fā)技術(shù)的研究對(duì)于提高虛擬網(wǎng)絡(luò)的性能具有重要意義。本文針對(duì)虛擬路由器的獨(dú)立轉(zhuǎn)發(fā)與合并轉(zhuǎn)發(fā)兩種機(jī)制展開(kāi)研究,分別提出相應(yīng)的路由表(Forwarding Information Base,FIB)壓縮與查找算法,取得的主要研究成果如下:(1)針對(duì)虛擬路由器獨(dú)立轉(zhuǎn)發(fā)機(jī)制中路由表的存儲(chǔ)開(kāi)銷隨虛擬路由器實(shí)例數(shù)量的增加而線性增長(zhǎng)的挑戰(zhàn),提出路由表快速壓縮算法US,通過(guò)改變路由表的trie樹(shù)結(jié)構(gòu),可將前綴數(shù)量壓縮到原來(lái)的65%。該算法不僅可以保證壓縮后路由表在最壞情況下的更新性能,而且可以與大部分現(xiàn)有的路由表壓縮與查找算法聯(lián)合使用。(2)針對(duì)虛擬路由器獨(dú)立轉(zhuǎn)發(fā)機(jī)制中路由器片內(nèi)內(nèi)存容量有限的問(wèn)題,提出基于最小完美哈希表的MPHL路由表查找算法,將路由表的片內(nèi)內(nèi)存占用降到理論最低。克服了最小完美哈希表不支持增量更新的缺點(diǎn),提出MPHL算法的快速更新機(jī)制,平均更新復(fù)雜度為O(1)。算法對(duì)IPv4、IPv6兩種路由表的平均查找復(fù)雜度均為O(1)。(3)針對(duì)虛擬路由器合并轉(zhuǎn)發(fā)機(jī)制中現(xiàn)有查找算法速度較慢、支持虛擬路由表個(gè)數(shù)較少的問(wèn)題,提出一種基于布隆過(guò)濾器的路由表查找算法,實(shí)現(xiàn)了查找速度與虛擬路由表個(gè)數(shù)無(wú)關(guān),查找速度接近片外訪存速度。在此基礎(chǔ)上提出AE壓縮算法,將查找方案的片內(nèi)內(nèi)存占用減少1/3。(4)設(shè)計(jì)實(shí)現(xiàn)了支持快速轉(zhuǎn)發(fā)的虛擬網(wǎng)絡(luò)平臺(tái)MAVIN,提出可對(duì)各虛擬網(wǎng)絡(luò)進(jìn)行二層隔離的MAC編址機(jī)制,與隧道虛擬化機(jī)制相比,避免了分組轉(zhuǎn)發(fā)時(shí)封裝解封裝導(dǎo)致的額外轉(zhuǎn)發(fā)開(kāi)銷。本文對(duì)MAVIN平臺(tái)的轉(zhuǎn)發(fā)性能與可擴(kuò)展性進(jìn)行了全面評(píng)價(jià)。
[Abstract]:By reusing the resources of network hardware infrastructure, network virtualization technology can set up multiple virtual networks at low cost. These virtual networks can provide services for users with different needs, and can also provide real deployment and verification environment for various network innovation studies, thus speeding up the innovation process of the Internet. Virtual router is the core device to construct virtual network. The research of forwarding technology is of great significance to improve the performance of virtual network. In this paper, two mechanisms of independent forwarding and merge forwarding of virtual routers are studied, and the corresponding routing table forwarding Information base FIB-compression and lookup algorithms are proposed, respectively. The main research results are as follows: 1) aiming at the challenge that the storage overhead of routing table in the independent forwarding mechanism of virtual router increases linearly with the increase of the number of virtual router instances. By changing the trie tree structure of the routing table, the prefix number can be compressed to the original 65. The algorithm can not only guarantee the update performance of the compressed routing table in the worst case, Moreover, it can be used in conjunction with most existing routing table compression and lookup algorithms. Aiming at the problem of limited in-chip memory capacity in the independent forwarding mechanism of virtual routers, a MPHL routing table lookup algorithm based on minimum perfect hash table is proposed. Reduce the in-chip memory footprint of the routing table to the theoretical minimum. In order to overcome the shortcoming that the minimum perfect hash table does not support incremental update, a fast updating mechanism of MPHL algorithm is proposed, with an average updating complexity of OF-1. The average lookup complexity of the algorithm for IPv4 / IPv6 routing tables is O ~ (1) / n ~ (3). In order to solve the problem of the slow speed of the existing search algorithms and the small number of virtual routing tables in the merging and forwarding mechanism of virtual routers, the proposed algorithm has the following advantages: 1. A routing table lookup algorithm based on Bloom filter is proposed. The lookup speed is independent of the number of virtual routing tables, and the lookup speed is close to the output-memory speed. On this basis, the AE compression algorithm is proposed, and the in-chip memory footprint of the lookup scheme is reduced by 1 / 3. 4) the virtual network platform MAVIN, which supports fast forwarding, is designed and implemented, and the MAC addressing mechanism, which can separate each virtual network layer 2, is proposed. Compared with the tunneling virtualization mechanism, the additional forwarding overhead caused by encapsulation and unencapsulation of packet forwarding is avoided. This paper evaluates the forwarding performance and extensibility of MAVIN platform.
【學(xué)位授予單位】：清華大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP393.0

【相似文獻(xiàn)】

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

1 張慶紅;程國(guó)建;;淺析路由表原理在網(wǎng)絡(luò)中的應(yīng)用[J];網(wǎng)絡(luò)安全技術(shù)與應(yīng)用;2010年04期

2 王姝;陳常嘉;;基于地址分配算法壓縮路由表[J];北京交通大學(xué)學(xué)報(bào);2010年02期

3 司麗娟;;基于路由表權(quán)重調(diào)整提高任意播負(fù)載均衡性能的算法[J];計(jì)算機(jī)應(yīng)用;2011年S2期

4 劉倉(cāng)明;基于流量分布的高速路由表查找算法[J];山西電子技術(shù);2004年01期

5 趙光富,姜建國(guó),楊曉強(qiáng),王曉峰;一種路由表三層下發(fā)算法[J];電子科技;2005年03期

6 崔欣波;;策略性路由應(yīng)用[J];內(nèi)蒙古電大學(xué)刊;2006年12期

7 張龍;;MPLS VPN互訪的幾種方式[J];電力信息化;2008年09期

8 張昊;;基于信任概率的雙向路由表研究[J];硅谷;2012年03期

9 李臘元;一種路由表維護(hù)協(xié)議的分析[J];微電子學(xué)與計(jì)算機(jī);1992年09期

10 王利媛,馬躍,徐塞虹;對(duì)路由表結(jié)構(gòu)和查找算法的研究[J];計(jì)算機(jī)應(yīng)用;2004年11期

相關(guān)會(huì)議論文 前3條

1 趙永勝;谷利澤;;基于路由表的主機(jī)非法外聯(lián)監(jiān)控技術(shù)研究與分析[A];2009通信理論與技術(shù)新發(fā)展——第十四屆全國(guó)青年通信學(xué)術(shù)會(huì)議論文集[C];2009年

2 程青松;王文鼐;唐寶民;;考慮業(yè)務(wù)流量分布的路由表查找算法[A];開(kāi)創(chuàng)新世紀(jì)的通信技術(shù)——第七屆全國(guó)青年通信學(xué)術(shù)會(huì)議論文集[C];2001年

3 譚振華;程維;常桂然;高曉興;王賀;;一種基于分布式選舉算法的結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)路由協(xié)議[A];2008'中國(guó)信息技術(shù)與應(yīng)用學(xué)術(shù)論壇論文集（二）[C];2008年

相關(guān)重要報(bào)紙文章 前10條

1 江蘇 白洋;看路由表就是這么簡(jiǎn)單[N];電腦報(bào);2005年

2 Mark Gibbs;IT從業(yè)十誡[N];網(wǎng)絡(luò)世界;2006年

3 ;測(cè)試方法解析[N];網(wǎng)絡(luò)世界;2002年

4 浙江 林美榮;修改ADSL Modem路由表，限制用戶訪問(wèn)[N];電腦報(bào);2003年

5 ;MPLS不利于Internet發(fā)展[N];計(jì)算機(jī)世界;2001年

6 工信部電信研究院規(guī)劃所 蘇嘉;IPv6地址資源規(guī)劃需趁早[N];人民郵電;2011年

7 何茂平;中興SmartNetwork智能IP城域網(wǎng)[N];人民郵電;2001年

8 張志剛 屈永華;路由器撐不住了咋辦[N];中國(guó)計(jì)算機(jī)報(bào);2001年

9 廣州 梁俊清;ADSL Modem的遠(yuǎn)程控制[N];電腦報(bào);2001年

10 華為公司供稿;華為MPLS VPN技術(shù)特色[N];計(jì)算機(jī)世界;2002年

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

1 陸璇;互聯(lián)網(wǎng)域間路由可擴(kuò)展性的相關(guān)研究[D];北京郵電大學(xué);2015年

2 潘恬;支持快速啟動(dòng)和協(xié)議識(shí)別的路由器線卡的研究[D];清華大學(xué);2015年

3 張媛媛;虛擬路由表壓縮與查找算法研究[D];清華大學(xué);2016年

4 楊仝;骨干網(wǎng)路由表壓縮、查找及增量更新技術(shù)研究[D];清華大學(xué);2013年

5 葉麟;基于行為測(cè)量的P2P系統(tǒng)優(yōu)化研究[D];哈爾濱工業(yè)大學(xué);2011年

6 王洪君;Internet域間路由穩(wěn)定性研究[D];東北大學(xué);2006年

7 孫慶南;面向IPv6分組轉(zhuǎn)發(fā)的路由技術(shù)研究[D];中國(guó)科學(xué)院研究生院（計(jì)算技術(shù)研究所）;2005年

8 高蕾;面向多核多線程的BGP協(xié)議并行技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2009年

9 張曉哲;路由協(xié)議并行處理技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2005年

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

1 趙曼;基于路由表的無(wú)線傳感器網(wǎng)絡(luò)路由算法的研究[D];華北電力大學(xué);2016年

2 王志坤;一種基于實(shí)際交通數(shù)據(jù)的RSU網(wǎng)絡(luò)構(gòu)建策略[D];重慶大學(xué);2016年

3 吳晶晶;基于四叉樹(shù)編碼實(shí)現(xiàn)路由表壓縮的復(fù)合路由方案研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2017年

4 朱凱;FCoE路由管理模塊的設(shè)計(jì)與實(shí)現(xiàn)[D];北京郵電大學(xué);2010年

5 陶中平;基于鄰近度的P2P路由算法的設(shè)計(jì)與實(shí)現(xiàn)[D];電子科技大學(xué);2007年

6 鄒香玲;基于路由表的無(wú)線傳感器網(wǎng)絡(luò)路由算法研究[D];華中師范大學(xué);2013年

7 任勇軍;一個(gè)P2P資源查找的改進(jìn)方法[D];河海大學(xué);2004年

8 馬常霞;基于移動(dòng)Agent的分布式路由算法研究[D];南京理工大學(xué);2003年

9 劉昊東;基于DHT的P2P路由算法研究[D];武漢理工大學(xué);2010年

10 吳婷婷;基于四叉樹(shù)的路由技術(shù)研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2015年

，

本文編號(hào)：1908667