支持接入控制的虛擬網(wǎng)映射近似算法

余建軍 吳春明

?

支持接入控制的虛擬網(wǎng)映射近似算法

余建軍*①吳春明②

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

該文對(duì)網(wǎng)絡(luò)虛擬化技術(shù)中的虛擬網(wǎng)映射問(wèn)題及其研究現(xiàn)狀進(jìn)行介紹，指出當(dāng)前虛擬網(wǎng)映射算法在接入控制和算法性能評(píng)估方面存在的問(wèn)題，提出一種支持接入控制的虛擬網(wǎng)映射近似算法，并給出了算法的競(jìng)爭(zhēng)比分析。實(shí)驗(yàn)表明，該算法能提高物理網(wǎng)資源的負(fù)載均衡度和利用率，從而提高了虛擬網(wǎng)構(gòu)建請(qǐng)求的接受率和物理網(wǎng)提供商的收益。

虛擬網(wǎng)映射；接入控制；近似算法；競(jìng)爭(zhēng)分析

1 引言

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

目前提出的虛擬網(wǎng)映射算法在接入控制策略設(shè)計(jì)方面和對(duì)虛擬網(wǎng)映射問(wèn)題解的質(zhì)量保證方面存在較大缺陷。其中對(duì)算法性能的評(píng)估主要通過(guò)實(shí)驗(yàn)手段，而沒(méi)有進(jìn)行競(jìng)爭(zhēng)比分析[14]。

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

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

2 網(wǎng)絡(luò)模型和問(wèn)題描述

另外，虛擬網(wǎng)映射問(wèn)題的目標(biāo)是物理網(wǎng)提供商長(zhǎng)期收益的最大化。

3 支持接入控制的虛擬網(wǎng)映射近似算法ACAA

3.1 假設(shè)與定義

同文獻(xiàn)[16]類(lèi)似，通過(guò)假設(shè)2和假設(shè)3對(duì)虛擬節(jié)點(diǎn)的CPU容量和虛擬鏈路帶寬容量的上限進(jìn)行限定。如不限定，則任意在線(xiàn)算法的競(jìng)爭(zhēng)比會(huì)趨向無(wú)窮大，其證明如下：具體通過(guò)構(gòu)造一個(gè)實(shí)例來(lái)證明，設(shè)物理網(wǎng)和虛擬網(wǎng)都只有兩個(gè)節(jié)點(diǎn)和一條鏈路，物理鏈路帶寬和物理節(jié)點(diǎn)CPU容量都為1；虛擬網(wǎng)B1的節(jié)點(diǎn)CPU容量和鏈路帶寬都為(→0)；虛擬網(wǎng)A1的節(jié)點(diǎn)CPU容量為，鏈路的帶寬為1; A1和B1的生存期都為。當(dāng)B1請(qǐng)求到達(dá)后，如在線(xiàn)算法拒絕B1，則把B1作為唯一的虛擬網(wǎng)構(gòu)建請(qǐng)求，此時(shí)離線(xiàn)最優(yōu)算法必然接受B1，則此實(shí)例下在線(xiàn)算法的競(jìng)爭(zhēng)比為(3×)/0→+；如在線(xiàn)算法接受B1，則A1作為第2個(gè)虛擬網(wǎng)構(gòu)建請(qǐng)求，因在線(xiàn)算法必然拒絕A1，而離線(xiàn)最優(yōu)算法是拒絕B1接受A1，則此實(shí)例下的在線(xiàn)算法的競(jìng)爭(zhēng)比為：(2+ 1)/(3×)→+。虛擬節(jié)點(diǎn)的CPU容量無(wú)限定時(shí)的證明類(lèi)似。

3.2 ACAA算法設(shè)計(jì)

基于貪婪方法的思想對(duì)到達(dá)的第個(gè)虛擬網(wǎng)VN構(gòu)建請(qǐng)求，分兩階段來(lái)完成：(1)把虛擬節(jié)點(diǎn)映射到滿(mǎn)足虛擬節(jié)點(diǎn)接入控制條件的映射代價(jià)最小的物理節(jié)點(diǎn)上；(2)把虛擬鏈路映射到滿(mǎn)足虛擬鏈路接入控制條件的映射代價(jià)最小的物理網(wǎng)路徑上。具體步驟如表1所示。

4 ACAA算法分析

對(duì)算法性能的評(píng)價(jià)從兩個(gè)方面進(jìn)行：(1)采用競(jìng)爭(zhēng)分析法，分析ACAA算法在最壞情況下的性能；(2)用實(shí)驗(yàn)法，分析ACAA算法的平均性能。

4.1 時(shí)間復(fù)雜性分析

表1 ACAA算法步驟

4.2 算法正確性和競(jìng)爭(zhēng)比分析

對(duì)ACAA算法的分析分成兩部分。首先證明該算法不會(huì)違反物理節(jié)點(diǎn)的CPU容量約束和物理鏈路的帶寬約束；然后證明ACAA算法的競(jìng)爭(zhēng)比，具體是在任意時(shí)間，針對(duì)時(shí)間之前所接受的所有虛擬網(wǎng)構(gòu)建請(qǐng)求，分析采用ACAA算法所獲收益與采用最優(yōu)離線(xiàn)算法所獲得收益之比。

記為ACAA算法成功完成構(gòu)建的虛擬網(wǎng)序號(hào)(虛擬網(wǎng)VN的序號(hào)為)的集合。

記

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

定理2 對(duì)所有物理節(jié)點(diǎn)nN, ACAA算法不會(huì)違反物理節(jié)點(diǎn)的CPU容量約束，即。

證明 證明過(guò)程與定理1類(lèi)似。主要區(qū)別是一個(gè)物理節(jié)點(diǎn)只能被一個(gè)虛擬網(wǎng)的一個(gè)虛擬節(jié)點(diǎn)所映射。

定理3是最后一個(gè)虛擬網(wǎng)請(qǐng)求的虛擬網(wǎng)序號(hào)，則

即可。

定理 4

證明 證明過(guò)程與定理3類(lèi)似，主要區(qū)別是一個(gè)物理節(jié)點(diǎn)只能被一個(gè)虛擬網(wǎng)的一個(gè)虛擬節(jié)點(diǎn)所映射。

定理5 設(shè)2是離線(xiàn)最優(yōu)算法完成構(gòu)建，但ACAA算法沒(méi)有完成構(gòu)建(原因是存在虛擬鏈路不能夠完成映射)的虛擬網(wǎng)序號(hào)的集合，2是2中最大值，則

證畢

4.3 算法平均性能實(shí)驗(yàn)分析

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

4.3.1仿真環(huán)境及性能評(píng)估指標(biāo) ACAA算法平均性能的評(píng)估通過(guò)Matlab模擬仿真來(lái)進(jìn)行。對(duì)算法性能的評(píng)估指標(biāo)除虛擬網(wǎng)構(gòu)建請(qǐng)求接受率(虛擬網(wǎng)構(gòu)建成功的個(gè)數(shù)占構(gòu)建請(qǐng)求數(shù)的百分比)和物理網(wǎng)提供商的平均收益(單位時(shí)間物理網(wǎng)提供商收益)外，另外再使用物理節(jié)點(diǎn)和物理鏈路的利用率與最高負(fù)載等指標(biāo)來(lái)衡量物理網(wǎng)資源的利用情況。

4.3.3實(shí)驗(yàn)結(jié)果及分析

(1)物理網(wǎng)資源利用情況分析 表2結(jié)果表明：(a)采用ACAA算法，節(jié)點(diǎn)和鏈路的平均利用率更高。結(jié)合圖1可知，利用率高的原因是ACAA算法有更高的虛擬網(wǎng)構(gòu)建請(qǐng)求接受率，同時(shí)ACAA算法在映射虛擬鏈路時(shí)會(huì)過(guò)濾掉負(fù)載相對(duì)較高(相對(duì)物理網(wǎng)提供商收益)的物理鏈路，導(dǎo)致映射虛擬鏈路的物理路徑相對(duì)更長(zhǎng)；(b)因ACAA算法會(huì)過(guò)濾掉負(fù)載相對(duì)較高的物理節(jié)點(diǎn)和物理鏈路，從而使物理節(jié)點(diǎn)和鏈路的使用更加均衡；(c)ACAA算法過(guò)濾掉的是其生命周期內(nèi)負(fù)載相對(duì)較高的物理節(jié)點(diǎn)和物理鏈路，而不是即時(shí)負(fù)載較高的節(jié)點(diǎn)和鏈路，故ACAA算法會(huì)使用即時(shí)負(fù)載很高但在虛擬網(wǎng)生命周期內(nèi)負(fù)載會(huì)下降較多的物理節(jié)點(diǎn)和物理鏈路。

(2)虛擬網(wǎng)構(gòu)建請(qǐng)求接受率和映射收益分析 從圖1可觀察到，當(dāng)虛擬網(wǎng)構(gòu)建請(qǐng)求數(shù)不斷增多時(shí)，隨著物理網(wǎng)負(fù)載逐漸加重，虛擬網(wǎng)構(gòu)建請(qǐng)求接受率和平均收益接近線(xiàn)性下降。但隨著請(qǐng)求數(shù)的增加，虛擬網(wǎng)構(gòu)建的接收率和平均收益會(huì)逐漸達(dá)到穩(wěn)態(tài)。從實(shí)驗(yàn)結(jié)果可以看出，采用ACAA算法有利于提高虛擬網(wǎng)接受率和物理網(wǎng)提供商的平均收益。從圖1數(shù)據(jù)可以觀察到，當(dāng)物理網(wǎng)絡(luò)上運(yùn)行的虛擬網(wǎng)個(gè)數(shù)達(dá)到一定規(guī)模后，采用ACAA算法的虛擬網(wǎng)構(gòu)建成功率和平均收益逐漸穩(wěn)定在0.68和19.5左右，比COMM, R- ViNE-SP和G-SP算法分別提高10%, 17%和34%左右。

表2資源利用情況

算法節(jié)點(diǎn)平均利用率鏈路平均利用率節(jié)點(diǎn)利用率方差鏈路利用率方差節(jié)點(diǎn)最高負(fù)載鏈路最高負(fù)載 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)接入控制分析 統(tǒng)計(jì)分析表明，虛擬網(wǎng)映射單位時(shí)間收益在平均值之下(取21)，ACAA算法在映射該虛擬網(wǎng)時(shí)，會(huì)過(guò)濾掉在該虛擬網(wǎng)生存周期內(nèi)平均相對(duì)負(fù)載超過(guò)76%的物理節(jié)點(diǎn)和物理鏈路，而當(dāng)虛擬網(wǎng)映射單位時(shí)間收益接近單位時(shí)間最大收益時(shí)，則不會(huì)過(guò)濾掉任何物理鏈路和物理節(jié)點(diǎn)。最終大約有5%的虛擬網(wǎng)請(qǐng)求因接入控制的原因被拒絕，而COMM算法大約是1%。

5 結(jié)束語(yǔ)

本文針對(duì)當(dāng)前所提出虛擬網(wǎng)映射算法存在的主要問(wèn)題，提出了支持接入控制的虛擬網(wǎng)映射算法ACAA，最后對(duì)ACAA算法進(jìn)行了競(jìng)爭(zhēng)比分析和實(shí)驗(yàn)驗(yàn)證，以說(shuō)明所設(shè)計(jì)算法的有效性和實(shí)用性。

[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] 李小玲, 王懷民, 丁博, 等. 虛擬網(wǎng)絡(luò)映射問(wèn)題研究及其進(jìn)展[J]. 軟件學(xué)報(bào), 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ìn)鵬, 高慶一, 等. 一種保持結(jié)點(diǎn)緊湊的虛擬網(wǎng)絡(luò)映射方法[J]. 計(jì)算機(jī)學(xué)報(bào), 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] 李小玲, 郭長(zhǎng)國(guó), 李小勇, 等. 一種基于約束優(yōu)化的虛擬網(wǎng)絡(luò)映射方法[J]. 計(jì)算機(jī)研究與發(fā)展, 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年生，副教授，研究方向?yàn)樗惴ㄔO(shè)計(jì)與分析、光網(wǎng)絡(luò)、無(wú)線(xiàn)傳感器網(wǎng)絡(luò)、網(wǎng)絡(luò)虛擬化技術(shù)等.

吳春明： 男，1967年生，教授，博士生導(dǎo)師，研究方向?yàn)槊嫦蚍?wù)提供的大規(guī)?？芍貥?gòu)柔性網(wǎng)絡(luò)構(gòu)建技術(shù)、計(jì)算機(jī)網(wǎng)絡(luò)QoS、三網(wǎng)融合體系結(jié)構(gòu)、網(wǎng)絡(luò)虛擬化等.

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改回

國(guó)家自然科學(xué)基金(61070157, 61070213)和國(guó)家863計(jì)劃項(xiàng)目(2008AA01A323, 2008AA01A325, 2009AA01A334)資助課題