支持接入控制的虚拟网映射近似算法

余建军 吴春明



支持接入控制的虚拟网映射近似算法

余建军*①吴春明②

①(衢州职业技术学院 衢州 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)资助课题