本文選題：網絡虛擬化 + 虛擬路由器　； 參考：《清華大學》2016年博士論文

【摘要】：網絡虛擬化技術通過對網絡硬件基礎設施的資源進行復用,可以以較低的經濟成本建立多個虛擬網絡。這些虛擬網絡可以為有不同需求的用戶提供服務,也可以為各種網絡創(chuàng)新研究提供真實的部署驗證環(huán)境,加快互聯(lián)網的創(chuàng)新進程。虛擬路由器是構建虛擬網絡的核心設備,其轉發(fā)技術的研究對于提高虛擬網絡的性能具有重要意義。本文針對虛擬路由器的獨立轉發(fā)與合并轉發(fā)兩種機制展開研究,分別提出相應的路由表(Forwarding Information Base,FIB)壓縮與查找算法,取得的主要研究成果如下:(1)針對虛擬路由器獨立轉發(fā)機制中路由表的存儲開銷隨虛擬路由器實例數(shù)量的增加而線性增長的挑戰(zhàn),提出路由表快速壓縮算法US,通過改變路由表的trie樹結構,可將前綴數(shù)量壓縮到原來的65%。該算法不僅可以保證壓縮后路由表在最壞情況下的更新性能,而且可以與大部分現(xiàn)有的路由表壓縮與查找算法聯(lián)合使用。(2)針對虛擬路由器獨立轉發(fā)機制中路由器片內內存容量有限的問題,提出基于最小完美哈希表的MPHL路由表查找算法,將路由表的片內內存占用降到理論最低。克服了最小完美哈希表不支持增量更新的缺點,提出MPHL算法的快速更新機制,平均更新復雜度為O(1)。算法對IPv4、IPv6兩種路由表的平均查找復雜度均為O(1)。(3)針對虛擬路由器合并轉發(fā)機制中現(xiàn)有查找算法速度較慢、支持虛擬路由表個數(shù)較少的問題,提出一種基于布隆過濾器的路由表查找算法,實現(xiàn)了查找速度與虛擬路由表個數(shù)無關,查找速度接近片外訪存速度。在此基礎上提出AE壓縮算法,將查找方案的片內內存占用減少1/3。(4)設計實現(xiàn)了支持快速轉發(fā)的虛擬網絡平臺MAVIN,提出可對各虛擬網絡進行二層隔離的MAC編址機制,與隧道虛擬化機制相比,避免了分組轉發(fā)時封裝解封裝導致的額外轉發(fā)開銷。本文對MAVIN平臺的轉發(fā)性能與可擴展性進行了全面評價。
[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.
【學位授予單位】：清華大學
【學位級別】：博士
【學位授予年份】：2016
【分類號】：TP393.0

【相似文獻】

相關期刊論文 前10條

1 張慶紅;程國建;;淺析路由表原理在網絡中的應用[J];網絡安全技術與應用;2010年04期

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

3 司麗娟;;基于路由表權重調整提高任意播負載均衡性能的算法[J];計算機應用;2011年S2期

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

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

6 崔欣波;;策略性路由應用[J];內蒙古電大學刊;2006年12期

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

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

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

10 王利媛,馬躍,徐塞虹;對路由表結構和查找算法的研究[J];計算機應用;2004年11期

相關會議論文 前3條

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

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

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

相關重要報紙文章 前10條

1 江蘇 白洋;看路由表就是這么簡單[N];電腦報;2005年

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

3 ;測試方法解析[N];網絡世界;2002年

4 浙江 林美榮;修改ADSL Modem路由表，限制用戶訪問[N];電腦報;2003年

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

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

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

8 張志剛 屈永華;路由器撐不住了咋辦[N];中國計算機報;2001年

9 廣州 梁俊清;ADSL Modem的遠程控制[N];電腦報;2001年

10 華為公司供稿;華為MPLS VPN技術特色[N];計算機世界;2002年

相關博士學位論文 前9條

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

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

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

4 楊仝;骨干網路由表壓縮、查找及增量更新技術研究[D];清華大學;2013年

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

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

7 孫慶南;面向IPv6分組轉發(fā)的路由技術研究[D];中國科學院研究生院（計算技術研究所）;2005年

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

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

相關碩士學位論文 前10條

1 趙曼;基于路由表的無線傳感器網絡路由算法的研究[D];華北電力大學;2016年

2 王志坤;一種基于實際交通數(shù)據(jù)的RSU網絡構建策略[D];重慶大學;2016年

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

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

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

6 鄒香玲;基于路由表的無線傳感器網絡路由算法研究[D];華中師范大學;2013年

7 任勇軍;一個P2P資源查找的改進方法[D];河海大學;2004年

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

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

10 吳婷婷;基于四叉樹的路由技術研究[D];中國科學技術大學;2015年

，

本文編號：1908667