支持接入控制的虛擬網映射近似算法

余建軍 吳春明

?

支持接入控制的虛擬網映射近似算法

余建軍*①吳春明②

①(衢州職業技術學院 衢州 324000)②(浙江大學人工智能研究所 杭州 310027)

該文對網絡虛擬化技術中的虛擬網映射問題及其研究現狀進行介紹，指出當前虛擬網映射算法在接入控制和算法性能評估方面存在的問題，提出一種支持接入控制的虛擬網映射近似算法，并給出了算法的競爭比分析。實驗表明，該算法能提高物理網資源的負載均衡度和利用率，從而提高了虛擬網構建請求的接受率和物理網提供商的收益。

虛擬網映射；接入控制；近似算法；競爭分析

1 引言

網絡虛擬化技術被視為構建新一代互聯網架構的重要技術，該技術通過在底層物理網上構建多個獨立的虛擬網，從而實現同時支持多種服務和網絡體系結構的目的[1]。虛擬網映射是實現網絡虛擬化的關鍵環節，其任務是在虛擬網構建請求到達后，在滿足虛擬網構建約束的前提下，把虛擬網的虛擬節點和虛擬鏈路分別映射到底層物理網的節點和路徑上。虛擬網映射問題是在線問題，但即使是離線的虛擬網映射問題仍是NP難問題[2]。求解虛擬網映射問題的挑戰[3]包括資源約束，訪問控制(接入控制)，在線請求等。其中接入控制是指物理網提供商根據物理網中資源使用情況、物理網提供商收益等因素權衡是否接受虛擬網構建請求。在物理網基礎設施資源有限，且虛擬網構建請求數量很大時，接入控制顯得尤其重要。

目前提出的虛擬網映射算法在接入控制策略設計方面和對虛擬網映射問題解的質量保證方面存在較大缺陷。其中對算法性能的評估主要通過實驗手段，而沒有進行競爭比分析[14]。

目前僅有文獻[15,16]涉及到支持接入控制，僅有文獻[15]給出虛擬網映射算法的競爭比分析(針對Pipe流量模型和多路徑路由模型的GIPO算法)。但文獻[15]給出的算法存在以下問題：(1)不支持虛擬節點映射；(2)僅支持路徑可分割的虛擬鏈路映射[7]；文獻[16]給出的接入控制策略存在以下問題：(1)僅考慮物理節點的使用情況，而不考慮物理鏈路的使用情況；(2)不考慮虛擬網構建所能獲得的收益情況。

本文針對物理網資源有限且虛擬網構建請求數量很大的場景，提出支持接入控制的近似算法(Approximation Algorithm with Admission Control, ACAA)，其接入控制策略綜合考慮了物理節點和物理鏈路資源的使用情況以及虛擬網構建所能獲得的收益，并證明了該算法的競爭比。

2 網絡模型和問題描述

另外，虛擬網映射問題的目標是物理網提供商長期收益的最大化。

3 支持接入控制的虛擬網映射近似算法ACAA

3.1 假設與定義

同文獻[16]類似，通過假設2和假設3對虛擬節點的CPU容量和虛擬鏈路帶寬容量的上限進行限定。如不限定，則任意在線算法的競爭比會趨向無窮大，其證明如下：具體通過構造一個實例來證明，設物理網和虛擬網都只有兩個節點和一條鏈路，物理鏈路帶寬和物理節點CPU容量都為1；虛擬網B1的節點CPU容量和鏈路帶寬都為(→0)；虛擬網A1的節點CPU容量為，鏈路的帶寬為1; A1和B1的生存期都為。當B1請求到達后，如在線算法拒絕B1，則把B1作為唯一的虛擬網構建請求，此時離線最優算法必然接受B1，則此實例下在線算法的競爭比為(3×)/0→+；如在線算法接受B1，則A1作為第2個虛擬網構建請求，因在線算法必然拒絕A1，而離線最優算法是拒絕B1接受A1，則此實例下的在線算法的競爭比為：(2+ 1)/(3×)→+。虛擬節點的CPU容量無限定時的證明類似。

3.2 ACAA算法設計

基于貪婪方法的思想對到達的第個虛擬網VN構建請求，分兩階段來完成：(1)把虛擬節點映射到滿足虛擬節點接入控制條件的映射代價最小的物理節點上；(2)把虛擬鏈路映射到滿足虛擬鏈路接入控制條件的映射代價最小的物理網路徑上。具體步驟如表1所示。

4 ACAA算法分析

對算法性能的評價從兩個方面進行：(1)采用競爭分析法，分析ACAA算法在最壞情況下的性能；(2)用實驗法，分析ACAA算法的平均性能。

4.1 時間復雜性分析

表1 ACAA算法步驟

4.2 算法正確性和競爭比分析

對ACAA算法的分析分成兩部分。首先證明該算法不會違反物理節點的CPU容量約束和物理鏈路的帶寬約束；然后證明ACAA算法的競爭比，具體是在任意時間，針對時間之前所接受的所有虛擬網構建請求，分析采用ACAA算法所獲收益與采用最優離線算法所獲得收益之比。

記為ACAA算法成功完成構建的虛擬網序號(虛擬網VN的序號為)的集合。

記

證明 用反證法，設VN()是第1個導致物理鏈路相對負載大于1的虛擬網，設該物理鏈路為e(設虛擬網VN的第，共條虛擬鏈路映射到包含物理鏈路e的物理路徑上)。即在某時間[]，物理鏈路e的相對負載，即，根據假設3可得：。又根據假設1，當[]時，；根據假設2,。故：。這與算法中虛擬鏈路接入控制條件相矛盾，即第1條虛擬鏈路不可能映射到含物理鏈路e的物理路徑上，與假設相矛盾。 證畢

定理2 對所有物理節點nN, ACAA算法不會違反物理節點的CPU容量約束，即。

證明 證明過程與定理1類似。主要區別是一個物理節點只能被一個虛擬網的一個虛擬節點所映射。

定理3是最后一個虛擬網請求的虛擬網序號，則

即可。

定理 4

證明 證明過程與定理3類似，主要區別是一個物理節點只能被一個虛擬網的一個虛擬節點所映射。

定理5 設2是離線最優算法完成構建，但ACAA算法沒有完成構建(原因是存在虛擬鏈路不能夠完成映射)的虛擬網序號的集合，2是2中最大值，則

證畢

4.3 算法平均性能實驗分析

把ACAA算法與G-SP(鏈路映射用最短路徑算法，節點映射用貪婪算法[6])，R-ViNE-SP算法[8]和支持接入控制的基于約束優化的映射算法COMM[16]進行對比分析。

4.3.1仿真環境及性能評估指標 ACAA算法平均性能的評估通過Matlab模擬仿真來進行。對算法性能的評估指標除虛擬網構建請求接受率(虛擬網構建成功的個數占構建請求數的百分比)和物理網提供商的平均收益(單位時間物理網提供商收益)外，另外再使用物理節點和物理鏈路的利用率與最高負載等指標來衡量物理網資源的利用情況。

4.3.3實驗結果及分析

(1)物理網資源利用情況分析 表2結果表明：(a)采用ACAA算法，節點和鏈路的平均利用率更高。結合圖1可知，利用率高的原因是ACAA算法有更高的虛擬網構建請求接受率，同時ACAA算法在映射虛擬鏈路時會過濾掉負載相對較高(相對物理網提供商收益)的物理鏈路，導致映射虛擬鏈路的物理路徑相對更長；(b)因ACAA算法會過濾掉負載相對較高的物理節點和物理鏈路，從而使物理節點和鏈路的使用更加均衡；(c)ACAA算法過濾掉的是其生命周期內負載相對較高的物理節點和物理鏈路，而不是即時負載較高的節點和鏈路，故ACAA算法會使用即時負載很高但在虛擬網生命周期內負載會下降較多的物理節點和物理鏈路。

(2)虛擬網構建請求接受率和映射收益分析 從圖1可觀察到，當虛擬網構建請求數不斷增多時，隨著物理網負載逐漸加重，虛擬網構建請求接受率和平均收益接近線性下降。但隨著請求數的增加，虛擬網構建的接收率和平均收益會逐漸達到穩態。從實驗結果可以看出，采用ACAA算法有利于提高虛擬網接受率和物理網提供商的平均收益。從圖1數據可以觀察到，當物理網絡上運行的虛擬網個數達到一定規模后，采用ACAA算法的虛擬網構建成功率和平均收益逐漸穩定在0.68和19.5左右，比COMM, R- ViNE-SP和G-SP算法分別提高10%, 17%和34%左右。

表2資源利用情況

算法節點平均利用率鏈路平均利用率節點利用率方差鏈路利用率方差節點最高負載鏈路最高負載 G-SP0.5100.4580.2780.3240.9300.975 R-ViNE-SP0.5870.5230.2990.3200.8680.811 COMM0.6150.4910.2680.3340.8560.905 ACAA0.6830.5820.2670.3030.9100.925

(3)接入控制分析 統計分析表明，虛擬網映射單位時間收益在平均值之下(取21)，ACAA算法在映射該虛擬網時，會過濾掉在該虛擬網生存周期內平均相對負載超過76%的物理節點和物理鏈路，而當虛擬網映射單位時間收益接近單位時間最大收益時，則不會過濾掉任何物理鏈路和物理節點。最終大約有5%的虛擬網請求因接入控制的原因被拒絕，而COMM算法大約是1%。

5 結束語

本文針對當前所提出虛擬網映射算法存在的主要問題，提出了支持接入控制的虛擬網映射算法ACAA，最后對ACAA算法進行了競爭比分析和實驗驗證，以說明所設計算法的有效性和實用性。

[1] Chowdhury N M M K and Boutaba R. A survey of network virtualization[J]., 2010, 54(5):862-876.

[2] Andersen D.Theoretical approaches to node assignment [OL]. http://www.cs.cmu.edu/~dga/papers/andersen-assign.ps, 2013. 2.

[3] 李小玲, 王懷民, 丁博, 等. 虛擬網絡映射問題研究及其進展[J]. 軟件學報, 2012,23(11): 3009-3028.

Li Xiao-ling, Wang Huai-min, Ding Bo,.. Research and development of virtual network mapping problem[J]., 2012,23(11): 3009-3028.

[4] Ricci R, Alfeld C, and Lepreau J. A solver for the network testbed mapping problem[J]., 2003,33(2): 65-81.

[5] Szeto W,Iraqi Y, and Boutaba R. A multi-commodity flow based approach to virtual network resource allocation[C]. Proceedings of the IEEE Global Telecommunications Conference, San Francisco, 2003: 3004-3008.

[6] Zhu Y and Ammar M. Algorithms for assigning substrate network resources to virtual network components[C]. IEEE International Conference on Computer Communications (INFOCOM), Spain, 2006: 1-12.

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

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

[9] 劉新剛, 懷進鵬, 高慶一, 等. 一種保持結點緊湊的虛擬網絡映射方法[J]. 計算機學報, 2012, 35(12): 2492-2504.

Liu Xin-gang, Huai Jin-peng, Gao Qing-yi,.. A virtual network embedding approach to preserving node closeness[J]., 2012, 35(12): 2492-2504.

[10] Cheng X, Su S, and Zhang Z B. Virtual network embedding through topology-aware node ranking[J]., 2011, 41(2): 39-47.

[11] Qing S D, Liao J X, Wang J Y,.. Hybrid virtual network embedding with k-core decomposition and time-oriented priority[C]. IEEE International Conference on Communications (ICC), Canada, 2012: 2695-2699.

[12] Jens L and Holger K. A virtual network mapping algorithm based on subgraph isomorphism detection[C]. Proceedings of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures, Spain, 2009: 81-88.

[13] Alkmin G P, Batista D M, and Fonseca N L S. Optimal mapping of virtual networks[C]. Proceedings of the IEEE Global Telecommunications Conference, Houston, 2011: 1-6.

[14] Borodin A and EI-Yaniv R. Online Computation and Competitive Analysis[M]. New York: Cambridge University Press, 1998: 1-19.

[15] Even G, Medina M, Schaffrath G,.. Competitive and deterministic embeddings of virtual networks[J]., 2013, 496(1): 184-194.

[16] 李小玲, 郭長國, 李小勇, 等. 一種基于約束優化的虛擬網絡映射方法[J]. 計算機研究與發展, 2012, 48(9): 1601-1610.

Li Xiao-ling, Guo Chang-guo, Li Xiao-yong,.. A constraint optimization based mapping method for virtual network[J]., 2012,48(9):1601-1610.

余建軍： 男，1969年生，副教授，研究方向為算法設計與分析、光網絡、無線傳感器網絡、網絡虛擬化技術等.

吳春明： 男，1967年生，教授，博士生導師，研究方向為面向服務提供的大規模可重構柔性網絡構建技術、計算機網絡QoS、三網融合體系結構、網絡虛擬化等.

Virtual Network Mapping Approximation Algorithm with Admission Control

Yu Jian-jun①Wu Chun-ming②

①(,324000,)②(,,310027,)

In this study, the virtual network mapping issue in network visualization area and its current research progress are reviewed, and the main issues in admission control and algorithm performance evaluation for existing virtual network mapping algorithm are pointed out. Then the virtual network mapping approximation algorithm with admission control is proposed, and the competitive analysis of this algorithm is provided. Experiment result shows that the proposed algorithm increases the physical network resource load balancing metric and the coefficient of utilization, hence it can improve the virtual network construction request acceptance ratio and the income profit of physical network service provider.

Virtual network mapping; Admission control; Approximation algorithm; Competitive analysis

TP393

A

1009-5896(2014)05-1235-07

10.3724/SP.J.1146.2013.00965

余建軍 yjj691121@126.com

2013-07-04收到，2014-01-15改回

國家自然科學基金(61070157, 61070213)和國家863計劃項目(2008AA01A323, 2008AA01A325, 2009AA01A334)資助課題