基于資源區域聚集度的虛擬網映射算法

毛宇星 郭云飛 王志明 扈紅超

?

基于資源區域聚集度的虛擬網映射算法

毛宇星*①郭云飛②王志明②扈紅超②

①(解放軍理工大學指揮信息系統學院 南京 210007)②(國家數字交換系統工程技術研究中心 鄭州 450002)

虛擬網映射是網絡虛擬化研究中亟待解決的問題，針對已有映射算法中存在的對于網絡拓撲信息利用不足的現狀，該文提出了基于資源區域聚集度的虛擬網映射算法(RCI-VNE)。在映射預處理階段，根據局部拓撲信息和區域資源聚集度提出節點區域資源聚集評價算法。在節點映射階段，提出一種基于節點區域資源聚集排名的2-近鄰聚集映射算法，該算法將虛擬網節點集中映射到底層網絡中可用資源豐富的區域，減小承載鏈路的長度。實驗結果表明，該算法降低了虛擬網映射開銷，且具有較高的虛擬網請求接受率和較低的平均執行時間。

網絡虛擬化；網絡虛擬化映射；拓撲信息；區域資源聚集指數

1 引言

網絡僵化問題[1]是當前互聯網發展所面臨的一個巨大挑戰，網絡虛擬化技術[2]由于能夠有效地解決互聯網在技術創新上面臨的瓶頸而受到了學術界和產業界的廣泛關注。網絡虛擬化是指通過虛擬化技術在共同的底層物理設施上同時運行多個虛擬網，不同的虛擬網使用不同的路由策略和網絡協議。單個虛擬網絡是根據需求由一組虛擬節點和虛擬鏈路連接而成的一個服務切面，虛擬網映射主要完成如何將這些虛擬節點和虛擬鏈路對應匹配到底層物理網絡中的節點和鏈路上的任務，是網絡虛擬化研究的關鍵內容。

由于存在多個目標和約束，虛擬網映射問題已經被證明為NP-hard[3]問題，通常使用基于啟發式算法的方法求解，如文獻[4]提出的節點/鏈路負載均衡的啟發式算法，文獻[5]提出的基于鏈路可分割的多商品流映射算法，文獻[6]提出了一種分布式的虛擬網映射算法，底層網絡節點之間傳遞資源信息并將虛擬網分為若干星型拓撲結構。上述算法將虛擬網映射問題分成節點映射和鏈路映射兩個階段，各個階段分別依據自身的目標函數和約束條件進行求解。文獻[7,8]使用整數規劃方法將節點映射和鏈路映射統一進行求解，在節點映射階段就考慮了負載均衡和最大化映射利潤，但是該方法在本質上仍然是兩階段的映射方法。兩階段映射算法的優點在于縮小了解空間，能夠獲得較快的執行速度，但算法的成功率和對底層網絡的資源利用情況還有待提高。文獻[9]提出了一種基于子圖同型檢測的一階段虛擬網映射算法，該算法使用回溯機制統一進行節點和鏈路映射。一階段方法在整個解空間進行搜索，能夠取得較好的映射方案，但是也造成了算法復雜度高、執行速度慢的問題。文獻[10]提出了一種支持接入控制的虛擬網映射近似算法，能夠提高物理網資源的負載均衡度和利用率。文獻[11]提出了一種基于人工魚群的網絡虛擬化映射算法，該算法根據虛擬網絡請求與底層網絡節點和鏈路之間的約束關系建立二進制組合優化模型，能夠有效降低底層網絡的開銷和求解時間。文獻[12]研究了分布式環境下的虛擬網映射方法，提出了基于多節點協商的映射機制，實驗表明該算法能夠降低資源和通信開銷。

為了在映射方案的效果和算法復雜度之間取得平衡，近年來的研究傾向于在節點映射階段就考慮鏈路映射的限制條件，利用節點的拓撲信息將虛擬網請求映射到底層網絡中可用資源豐富的位置，提高映射的成功率和底層網絡資源的利用率。文獻[13~17]利用節點在網絡中位置的全局拓撲信息設計虛擬網映射算法，在一定程度上避免了上述問題，但仍然存在以下不足：(1)評價節點重要性時依賴全局信息，增加了算法的復雜度，并且忽視了被評價節點附近其他節點之間的連接關系對該節點重要性造成的影響；(2)沒有設計將虛擬節點集中映射到底層網絡某個區域的機制，承載物理節點的間距無法控制，增加映射開銷。

為了解決上述問題，本文首先提出一種基于局部拓撲信息和區域資源聚集度的節點區域資源聚集評價算法，該算法根據目標節點與其兩層鄰居的可用資源數量以及該區域節點之間連接的緊密程度對目標節點的重要性進行評價。其次，本文提出基于節點區域資源聚集排名的2-近鄰聚集虛擬網映射算法RCI-VNE，該算法將虛擬網節點集中映射到底層網絡中可用資源數量較多的區域，降低了虛擬網映射開銷，且具有較高的虛擬網請求接受率和較低的平均執行時間。

2 問題分析

2.1網絡模型

虛擬網映射問題的網絡模型如圖1所示。

圖1 虛擬網映射模型解析

3 基于節點區域資源聚集度的虛擬網映射

3.1 節點區域資源聚集程度評價方法

在復雜網絡中為了衡量節點的重要性，需要對節點的拓撲信息加以考慮。文獻[18]提出了一種利用半局部信息的節點重要性排序方法，該方法利用節點二階鄰居信息對節點的重要性進行評價，并指出該方法的時間復雜度隨網絡規模線性增長，實驗顯示，該方法能夠取得優于PageRank和LeaderRank算法的結果。但是該算法只考慮了節點之間鏈路的權值，沒有對節點本身的可用資源數量進行評價，無法直接應用在虛擬網映射問題上。本文對該方法進行改進，考慮了節點本身的可用資源數量，提出了節點區域資源因子。

定義1 節點區域資源因子：

節點的聚集因子[19]反映了節點與其鄰居以及鄰居節點之間連接的緊密程度，該因子越大則節點與周圍的鄰居以及鄰居之間的連接越緊密，越小則連接越疏松。

定義2 節點區域聚集因子：

本文將節點區域資源因子與節點區域聚集因子相結合，提出了評價節點所在區域資源聚集程度的節點區域資源聚集指數。

定義3 節點區域資源聚集指數：

計算節點區域資源聚集指數的具體算法如表1所示，算法的復雜度為，其中為網絡拓撲中節點的個數，為網絡拓撲中節點的平均度數。

3.2 2-近鄰聚集節點映射算法

為了充分利用底層物理網絡中的CPU資源和帶寬資源，本文提出了基于節點區域資源聚集指數的2-近鄰聚集節點映射算法，該算法的特點是：(1)將對資源要求高的虛擬節點映射到區域資源聚集指數高的物理節點上，盡量提高節點映射和鏈路映射階段的成功率。(2)將虛擬網請求映射在底層網絡中資源聚集度高的區域，減少承載虛擬鏈路的物理鏈路的長度，降低映射開銷。算法的基本思路為：將虛擬網請求中的節點和底層網絡中的節點分別按照其節點區域資源聚集指數降序排列；將排名靠前的虛擬網請求節點映射到能夠承載該節點且排名靠前的底層網絡節點上；將映射成功的虛擬網請求節點的兩層鄰居節點映射到承載的物理節點的兩層鄰居節點中滿足其資源約束的節點上。算法的具體流程如表2所示。

表1節點區域資源聚集指數算法

算法1 NRCI(Node Regional Resource Clustering Index)算法 輸入：網絡拓撲。 輸出：節點區域資源聚集指數向量R。 (1);(2) for each do(3) ;(4) for each do(5) ;(6) for each do(7) if k==i(8) continue;(9) end if(10) ;(11) end for(12) ;(13) ;(14) end for

表2基于區域資源聚集度的虛擬網映射算法

算法2 RCI-VNE(Virtual Network Embedding algorithm based on Resource Clustering Index)算法 輸入：。輸出：節點映射方案。(1) 將虛擬網請求和底層網絡中的節點列表和分別按照 其區域資源聚集指數分別降序排列； (2) 將中所有節點置為沒有映射，中所有節點置為沒有 承載；(3) while 存在沒有映射成功的節點do(4) vNode中區域資源聚集指數最高的節點 (5) for each (6) if sNode已經承載了虛擬節點；(7) continue;(8) end if(9) else if (10) continue;(11) else(12) 將vNode映射到sNode上；(13) 設置vNode為已映射；設置sNode為已承 載；(14) Map_neighbour(vNode, sNode);(15) 將vNode節點從未映射成功的節點隊列中 刪除；(16) end if(17) end for(18) if vNode沒有映射成功(19) return false;(20) end if(21) end while(22) return true

子程序Map_neighbour( )負責將映射成功的虛擬網請求節點的兩層鄰居節點映射在承載該虛擬網節點的底層網絡節點的兩層鄰居節點上，映射方案見表3。該節點映射算法的時間復雜度為。

在鏈路映射階段，如果底層網絡的支持鏈路分割，就使用多商品流算法將虛擬網請求鏈路映射到底層網絡的鏈路上。如果底層網絡不支持鏈路分割則使用K-最短路徑算法進行映射。K-最短路徑算法和多商品流問題的時間復雜度在多項式時間之內。所以整個虛擬網映射算法的時間復雜度在多項式時間之內。

表3子程序Map_neighbour映射方案

PROCEDURE Map_neighbour(vNode, sNode):(1)unMapListvNode未映射的鄰居節點列表；unUseList sNode未承載鄰居節點列表；(2) for each (3) for each (4) if (5) 將vNei映射到sNei上；(6) 將vNei設置為已映射；將sNei.used設置為已承載；(7) 在unMapList上刪除vNei；(8) 在unUseLists上刪除Nei；(9) end if(10) end for(11) end for

4 實驗評估

4.1 實驗環境

本文實驗使用配置為3.10 GHz Intel Core i7- 4600的計算平臺，利用C++編程仿真虛擬網映射請求的到達和離開以及虛擬網映射過程。本文使用GT-ITM拓撲生成器[20]構建底層網絡和虛擬請求拓撲。為了方便實驗對比，與現有的文獻[15,16]類似，本文實驗生成具有100個節點的底層網絡拓撲結構和2000個虛擬網請求。底層網絡的節點CPU資源和鏈路帶寬資源的取值服從[50,100]內的均勻分布，底層網絡節點的連接概率為0.2。虛擬網請求的節點個數服從[2,20]內的均勻分布，虛擬網請求的節點連接概率為0.5。虛擬網請求的節點和鏈路資源取值在[0,50]內服從均勻分布。虛擬網請求的到達過程服從到達率為平均100個時間單位到達4個請求的泊松過程，生命周期服從期望為1000個時間單位的指數分布。此外，設置RCI-VNE算法中的參數為0.8,-最短路徑算法中的為10。

4.2 評價指標

與現有文獻[14~16]類似，本文使用如下4個評價指標對本文提出的映射算法以及現有的映射算法進行評價。

(1)虛擬網請求接受率：該指標用來衡量在給定的時間間隔之內底層物理網絡接受的虛擬網請求占全部到達虛擬網請求的比例。

(2)底層網絡的長期平均收益：該指標衡量了虛擬網映射算法給底層網絡帶來的長期平均收益情況。

(3)長期利潤成本比：該指標用于衡量映射算法產生單位利潤所花費的資源開銷。

(4)映射算法平均執行時間：該指標衡量了映射算法執行的平均時間。

本文使用上述指標比較了本文提出的RCI- VNE算法和現有的其他5種虛擬網映射算法(GRC- VNE[13], R-ViNE-SP[7], VNE-B[9], Hybrid-VNE[15], G-SP[4])的性能。

圖2所示為不同虛擬網映射算法的接受率，從圖2中可以看出，在映射開始階段由于底層物理網絡可用資源較為充足，各個映射算法都有著較高的請求接受率。隨著時間的推移，各個映射算法的接受率不斷下降，平最終達到穩定。其中RCI-VNE算法的接受率最高，穩定接受率保持在54.19%, GRC-VNE, VNE-B, R-ViNE-SP, Hybrid-VNE算法的穩定接受率分別保持在47.23%, 39.74%, 33.13%和23.09%, G-SP算法的接受率最低，穩定接受率保持在18.35%。該指標主要與底層網絡的資源使用情況有關。實驗結果顯示，本文提出的RCI- VNE算法和文獻[13]提出的GRC-VNE算法能夠較好的在物理網絡和虛擬網請求中對節點的資源情況進行評價，GRC-VNE算法在評價某個節點的資源能力時考慮了整個物理網絡中的節點信息，忽略了底層網絡拓撲遠大于虛擬網請求拓撲的事實，使得算法的針對性下降，而且該算法在節點映射時沒有考慮到承載節點之間的距離，這也造成對底層網絡資源的過度使用。Hybrid-VNE算法將虛擬網請求中的節點進行了K-core分解，考慮了節點的拓撲屬性，但是沒有考慮到底層網絡中節點的可用資源情況，其他算法都沒有考慮節點的拓撲屬性。

圖3，圖4所示分別是不同虛擬網映射算法的長期平均收益和利潤成本比，由于本文提出的映射算法在節點映射階段將節點集中映射在物理網絡中可用集中的區域，使得承載虛擬鏈路的物理鏈路的距離更短，降低了承載虛擬網請求的開銷，獲得比其他算法更高的利潤成本比。其他算法在節點映射時基本都只考慮了底層網絡節點的資源豐富程度，這就造成了承載節點之間的距離可能很大，導致較高的鏈路映射開銷。從圖3和圖4可以看出，本文算法在這兩項指標上都有優于其他算法的表現。

圖2 虛擬網請求接受率

圖5所示為本文進行比較的虛擬網映射算法在同一仿真環境下映射2000個虛擬網請求的算法平均執行時間和標準差。從圖中可以看出本文提出的RCI-VNE算法在評價節點的承載能力時，只依賴于被評價節點兩層鄰居的信息，能夠獲得比依賴于全局拓撲信息的GRC-VNE映射算法更短的執行時間。VNE-B映射算法由于將節點映射和鏈路映射結合起來，需要的回溯操作較多，算法的執行時間相對較長。

由實驗結果可知，本文提出的基于節點區域資源聚集指數的RCI-VNE虛擬網映射算法在上述3個評價指標上具有明顯優勢，能夠有效地提高虛擬網請求接受率和利潤成本比，并最終提高底層網絡的長期平均收益。

5 結束語

本文基于復雜網絡中節點重要性排名的半局部中心拓撲屬性和區域聚集因子提出了節點區域資源聚集指數，該指數能夠評價以節點為中心的兩層鄰居范圍內的可用節點資源以及該范圍內節點之間可用鏈路資源的水平，并基于該指數提出了RCI-VNE虛擬網映射算法，該算法將虛擬網請求集中映射到底層網絡中區域可用資源豐富的位置，有效地提高了虛擬網請求的接受率和利潤成本比，最終提高底層網絡的長期平均收益。此外與基于節點全局拓撲屬性的算法相比，該算法具有更低的時間復雜度和平均映射時間。

圖3 長期平均利潤 圖4 利潤成本比

圖5 虛擬網映射算法平均執行時間和標準差

[1] Turner J S and Taylor D. Diversifying the Internet[C]. Proceedings of IEEE Conference on Global Telecommunications, St. Louis, 2005: 755-760.

[2] Anderson T, Peterson L, Shenker S,.. Overcoming the Internet impasse through virtualization[J]., 2005, 38(4): 34-41.

[3] Andersen D G. Theoretical Approaches to Node Assignment [M]. New York: Computer Science Department, 2002: 86-123.

[4] Zhang Y, Ammar M,.. Algorithm for assigning substrate network resources to virtual network components[C]. Proceedings of IEEE INFOCOM, Barcelona, 2006: 1-12.

[5] Yu M, Yi Y, Rexford J,.. Rethinking virtual network embedding: substrate support for path splitting and migration[J]., 2008, 38(2): 17-29.

[6] Houidi I, Louati W,.. A distributed virtual network mapping algorithm[C]. IEEE International Conference on Communication, Beijing, 2008: 5634-5640.

[7] Chowdhury M, Rahman M,.. ViNEYard: virtual network embedding algorithms with coordinated node and link mapping[J]./, 2012, 20(1): 206-219.

[8] Melo M, Sargento S, Killat U,.. Optimal virtual network embedding: node-link formulation[J]., 2013, 10(4): 356-368.

[9] Lischka J, Karl H,.. A virtual network mapping algorithm based on subgraph isomorphism detection[C]. Proceedings of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures, Barcelona, 2009: 81-88.

[10] 余建軍, 吳春明. 支持接入控制的虛擬網映射近似算法[J]. 電子與信息學報, 2014, 36(5): 1235-1241.

Yu Jian-jun and Wu Chun-ming. Virtual network mapping approximation algorithm with admission control[J].&, 2014, 36(5):1235-1241.

[11] 朱強, 王慧強, 等. VNE-AFS: 基于人工魚群的網絡虛擬化映射算法[J]. 通信學報, 2012, 33(Z1): 170-177.

Zhu Q, Wang Hui-qiang,.. VNE-AFS: virtual network embedding based on artificial fish swarm[J]., 2012, 33(Z1): 170-177.

[12] 江逸茗, 蘭巨龍, 程東年, 等. 分布式環境中基于協商的虛擬網映射算法[J]. 通信學報, 2014, 35(12): 62-69.

Jiang Yi-ming, Lan Ju-long, Cheng Dong-nian,.. Virtual network embedding algorithm based on negotiation in distributed environment[J]., 2014, 35(12): 62-69.

[13] Gong L, Wen Y, Zhu Z,.. Toward profit-seeking virtual network embedding algorithm via global resource capacity[C]. Proceedings of IEEE INFOCOM, Toronto, 2014: 1-9.

[14] Cui H, Gao W, Liu J,.. A virtual network embedding algorithm based on virtual topology connection feature[C]. IEEE 16th International Symposium on Wireless Personal Multimedia Communications, Atlantic City, 2013: 1-5.

[15] Qing S, Liao J, Zhu X,.. Hybrid virtual network embedding with K-core decomposition and time-oriented priority[C]. IEEE International Conference on Communications, Ottawa, Canada, 2012: 2695-2699.

[16] Huang T, Liu J, Chen J,.. A topology-cognitive algorithm framework for virtual network embedding problem [J].,, 2014, 11(4): 73-84.

[17] Cui H, Tang S, Huang X,.. A novel method of virtual network embedding based on topology convergence-degree[C]. IEEE International Conference on Communications Workshops, Budapest, 2013: 246-250.

[18] Chen D, Lü L, Shang M S,.. Identifying influential nodes in complex networks[J]., 2012, 391(4): 1777-1787.

[19] Fagiolo G. Clustering in complex directed networks[J]., 2007, 76(2): 470-475.

[20] Zegura E, Calvert K, and Bhattacharjee S. How to model an Internetwork[C]. Proceedings of IEEE INFOCOM, Philadelphia, 1996: 594-602.

Virtual Network Embedding Algorithm Based on Regional Resource Clustering Index

Mao Yu-xing①Guo Yun-fei②Wang Zhi-ming②Hu Hong-chao②

①(,,210007,)②(&,450002,)

Virtual network embedding is a critical issue in network virtualization. To overcome the ignorance of network local topology information in existing literatures, a Virtual Network Embedding (VNE) algorithm based on regional Resource Clustering Index (RCI-VNE), is proposed. In embedding preprocessing stage, a node regional resource clustering index evaluation algorithm is proposed, which considers local topology information and resource aggregation extent. In node embedding stage, a 2-adjacent aggregation node embedding algorithm based on the regional resource clustering index is also proposed. The algorithm embeds virtual nodes intensively to the location of abundant resources in substrate network and decreases embedding cost. Simulation results show that the algorithm improves virtual network request acceptance ratio, long-time average revenue and benefit-cost ratio compared with the existing embedding algorithms.

Network Virtualization; Virtualization Network Embedding (VNE); Topology Information; Regional Resource Clustering Index (RCI)

TP393.4

A

1009-5896(2015)10-2405-06

10.11999/JEIT150278

2015-03-09；改回日期：2015-06-16；

2015-07-27

毛宇星 myx_lgdx@163.com

國家自然科學基金(61309020)，國家973計劃項目(2012CB315901, 2012CB315905)和國家863計劃項目(2011AA 01A103)

The National Natural Science Foundation of China (61309020); The National 973 Program of China (2012CB 315901, 2012CB315905); The National 863 Program of China (2011AA01A103)

毛宇星： 男，1989年生，博士生，研究方向為寬帶信息網絡.

郭云飛： 男，1963年生，博士，教授，博士生導師，研究方向為下一代網絡.

王志明： 男，1986年生，博士生，研究方向為下一代網絡.

扈紅超： 男，1982年生，博士，研究方向為高性能路由交換技術.