一种自适应扩展的虚拟网络映射算法

彭利民

(1.广州体育学院计算机教研室，广州510500;2.华南理工大学自动化科学与工程学院，广州510006)

随着互联网新型应用的层出不穷，不同的应用对底层物理网络在安全性、服务质量和可扩展性等方面提出了不同的需求. 现有的互联网架构很难满足新型应用的发展需求，在某种程度上呈现出僵化现象，导致一些新型应用很难应用到现有的网络架构上［1］. 虚拟网络映射允许多个虚拟网络(Virtual Network，VN)运行在同一个物理网络(Substrate Network，SN)之上，被公认为是解决当前互联网架构问题的有效手段.在网络虚拟化环境下，传统的互联网服务运营商被分为了2个角色:一个是底层基础设施运营商，负责部署和维护底层网络资源，另一个是服务提供商，负责租用一个或多个底层基础设施提供商提供的底层网络资源，为用户提供定制的、可扩展的网络服务［2］.

虚拟网络映射是网络虚拟化中的关键问题，文献［3］将虚拟网络映射分为节点映射和链路映射，首先采用贪婪算法将资源需求较大的虚拟节点映射到可用资源量较多的物理节点上，然后利用K-最短路径算法完成虚拟链路的映射操作. 在文献［3］的基础上，文献［4］在节点映射过程中综合考虑了虚拟节点和物理网络中节点之间的位置关系，将虚拟网络映射到物理网络的局部区域内. 虽然这些算法的执行效率较高，但两阶段的映射方法破坏了节点和链路之间的耦合关系，使虚拟网络映射的质量受到影响.文献［5］通过扩展物理网络中的节点和链路，将虚拟网络映射转化为混合整数规划问题，然后利用整数规划松弛算法协调完成节点和链路的映射操作，但整数规划算法的时间复杂度较高，算法的执行效率受到影响;在文献［5］的基础上，文献［6］将所有符合条件的物理节点都作为虚拟节点的候选宿主，扩大了宿主的选择空间，同时选择那些分布紧凑的节点作宿主，将相邻的虚拟节点映射到邻近的物理节点之上，减少虚拟链路对网络资源的占用，但该算法仍然没有考虑虚拟节点间的邻接关系，相邻的虚拟节点被映射到物理网络中无法保持相邻关系，增加了虚拟网络映射的资源开销. 文献［7］将物理网络和虚拟网络描述为带权有向图，然后采用同构子图搜索方法，在同一阶段内协调完成节点映射和链路的映射操作. 针对文献［7］在映射过程中仅考虑节点自身资源能力的局限性，文献［8］在虚拟网络映射过程中综合考虑节点的资源属性和网络拓扑属性，尽管这2个算法在同构子图搜索时限制了回溯次数(4n 次)，但时间复杂度仍然较高，在虚拟网络映射过程中没有考虑虚拟网络中节点之间的邻接关系，增加了虚拟网络映射的资源开销.

综上所述，现有的虚拟网络映射算法主要存在以下问题:(1)两阶段的虚拟网络映射算法破坏了节点和链路之间固有的拓扑关系，并且在节点映射阶段无法预见链路映射阶段的网络状态，使虚拟网络映射的性能受到影响;(2)采用整数规划松弛算法和同构子图搜索回溯算法的时间复杂度太高，不适合处理动态的虚拟网络映射问题;(3)虚拟网络映射过程中没有考虑虚拟网络中节点间的邻接关系，导致虚拟网络中的节点和链路被映射到物理网络，无法保持原有的拓扑关系，降低了虚拟网络映射的质量;(4)在虚拟网络映射过程中，没有考虑节点和链路的资源状态，物理网络中的资源分布易呈现不均衡分布问题，使虚拟网络映射的质量受到影响.针对这些问题，本文根据节点和链路状态，自适应扩展物理网络结构，将相邻的虚拟节点和链路映射到邻接的物理节点和链路上，使虚拟网络成为物理网络或λ 扩展物理网络的同构子图，协调映射虚拟节点及其邻接虚拟链路，使虚拟网络被映射后应尽可能地保持原有的拓扑结构，降低虚拟网络映射的资源开销.

1 虚拟网络映射模型

1.1 问题描述

虚拟网络映射问题可以抽象为图论问题.文中使用带权无向图Gs= (Ns，Es，，AE s)表示物理网络，其中Ns和Es分别代表物理网络节点集和物理链路集表示物理节点nsNs的资源属性集合，它们通常指节点的计算、存储和转发等属性;表示节点ni和nj之间物理链路es(ni，nj)Es的资源属性集合，它们通常指物理链路的可用带宽、时延等属性.类似地，使用带权无向图Gv=(Nv，Ev，)表示虚拟网络请求，其中Nv和Ev分别表示虚拟网络节点集和虚拟链路集，表示虚拟节点nvNv的资源属性集，表示虚拟节点ni和nj之间虚拟链路ev(ni，nj)Ev的资源属性集.

虚拟网络映射是指从Gv到G's的一个映射M:Gv→G's(Ns，Ps)，其中G's是Gs的一个子图，Ps表示Gs中无环物理路径集.虚拟网络映射M 需同时满足以下3个基本条件:(1)每一个虚拟节点i，∀iNv映射到不同的物理节点M(i)之上;(2)每一条虚拟链路ev(i，j)Ev，∀evEv映射到一条无环的物理路径p(is，js)Ps之上，并满足M(i)=is，M(j)=js;(3)虚拟网络映射需满足所有虚拟节点和虚拟链路的资源约束条件，则称M 是一个可行的虚拟网络映射方案.

1.2 自适应扩展网络模型

给定2个图G1(V1，E1)和G2(V2，E2)，同构子图映射是指存在一个映射M:N1→N2，并满足(u，v)E1⇒(M(u)，M(v))E2，∀u，vV1.同构子图映射是一对一的映射方式，一个虚拟节点映射到一个物理节点上，一条虚拟链路映射到一条物理链路上.由于虚拟网络请求拓扑结构的多样性，物理网络不可能存在所有虚拟网络的同构子图.针对这个问题，文中根据节点和链路的资源状态，利用自适应扩展因子λ 对物理网络进行动态扩展，构造一个自适应扩展的物理网络模型，使虚拟网络成为扩展物理网络的同构子图，从而有效地解决虚拟网络映射问题.)表示λ 扩展物理网络结构，其中，=Es∪{e(u，v)|1 ＜hop(u，v)≤λ，∀u，vNs}，hop(u，v)表示节点u 和节点v 之间的路由跳数，λ 为自适应扩张因子. 图1B 是图1A 的部分节点扩展后的物理网络结构.

图1 扩展物理网络实例Figure 1 An example of augmenting substrate network

对物理网络进行λ 扩展后，物理节点u 将新增Ω(u)个邻居节点和η(u)条连接节点u 和Ω(u)中节点的邻接链路，Ω(u)={vNs|1 ＜hop(u，v)≤λ}，η(u)={e(u，v)|u，vNs∧vΩ(u)}，其中，η(u)表示节点u 到Ω(u)中节点之间物理路径上的可用带宽.如图1 所示，当λ 为2 时，物理网络进行扩展后，节点A 新增了2个物理邻居节点F 和G，以及2 条物理邻接链路(A，F)和(A，G)，它们的可用带宽分别为30 和10.

1.3 优化模型

虚拟网络映射的主要研究目标是指在满足虚拟节点和虚拟链路的资源约束条件下，通过优化分配物理网络中的节点和链路资源，提高虚拟网络请求接受率和网络收益.

(1)虚拟链路扩张系数. 虚拟链路的映射路径长度表示虚拟链路在物理网络中的映射物理路径长度，它可以用于表示虚拟链路映射消耗的物理链路带宽资源量.虚拟链路扩张系数表示虚拟网络中所有虚拟链路的映射路径长度的平均值，它可定义为

(2)网络收益与开销比. 当虚拟网络被成功映射后，网络收益是指虚拟网络中节点的CPU 资源量和链路的带宽资源量总和.类似地，网络开销是指虚拟网络中虚拟节点实际消耗的CPU 资源量和虚拟链路实际消耗的带宽资源量总和，因此网络收益与开销比可表示为

(3)节点、链路的负载强度.在虚拟网络映射过程中，一方面要尽量保证物理网络中的节点资源均衡分布，另一方面也要尽量保证物理网络中的链路资源均衡分布，从而提高虚拟网络请求接受率和物理网络资源的利用率. 为了量化物理网络的负载均衡程度，文中使用负载强度刻画节点和链路的资源状态.节点的负载强度是指已利用的CPU 资源量和它的CPU 资源总量之比，它可表示为

其中nv→ns表示虚拟节点nv映射到物理节点ns上;cpu(ns)表示物理节点ns的CPU 资源总量;als(Ns)表示物理网络中节点的平均负载均衡度，反映了物理网络中节点资源的分布状态，该值越小，物理网络中节点资源分布越均衡，虚拟网络映射的质量越高.类似地，链路的负载强度指已利用的链路带宽和它的总带宽量之比，它可表示为

其中ev→es表示虚拟链路ev映射到物理链路es上;bw(es)表示物理链路es的带宽资源总量;ls(es)表示物理路径es的负载强度;als(Es)表示物理网络中链路的平均负载强度，可以反映物理网络中链路资源的分布状态，该值越小，物理链路的负载越均衡，虚拟网络映射的质量越高.

2 虚拟网络映射算法

为了减少虚拟网络映射的资源开销，虚拟网络被映射后应尽可能地保持原有的网络拓扑结构. 针对这个目标，AAG-VNM 算法根据节点和链路的资源状态，自适应地扩展物理网络，将相邻的虚拟节点和其邻接链路映射到邻接的物理节点和邻接的物理链路或物理路径上，使虚拟网络成为物理网络或λ扩展物理网络的同构子图，从而降低虚拟网络映射的资源开销.

算法1 AAG-VNM 算法

(1)对虚拟网络进行深度优先遍历，构造虚拟节点映射序列;

(2)将第1个虚拟节点u 随机地映射到物理网络中满足节点u 的CPU 资源需求的物理节点上;

(3)如果节点u 映射成功，则将虚拟节点u 和对应的物理节点M(u)分别加入已映射虚拟节点集Q 和已映射物理节点集P 中;

(4)从虚拟节点映射序列中的第2个节点i 开始，依次按照以下步骤进行虚拟网络映射操作:

①如果M(u)存在一个尚未参加映射的邻居节点j，j 的CPU 资源量满足节点i 的CPU 资源需求，且物理链路(M(u)，j)的带宽资源量和时延满足虚拟链路(u，i)的带宽需求，那么将虚拟节点i 映射到物理节点j 上，同时将虚拟链路(u，i)映射到物理链路(M(u)，j)上，并分别将节点i 和节点j 加入集合Q 和P 中;如果M(u)存在多个满足映射条件的邻居节点，则优先选择节点的负载强度和链路的负载强度相对较小的邻居节点进行映射操作;

②否则，λ 值从2 开始逐渐递增到δ，然后对物理网络进行λ 扩展，并按照步骤①的映射方法将虚拟节点i 和其邻接链路映射到λ 扩展物理网络中，直到映射成功;当λ 值达到阈值δ 时还没找到满足节点和链路需求的邻居节点和邻接链路，则终止算法，映射失败;

③如果虚拟节点i 和集合Q 中的节点之间还有未映射的虚拟链路，则使用K-最短路径算法［9］搜索满足条件的物理路径，并优先将虚拟链路映射到负载强度相对较小的物理路径上;

(5)当所有虚拟节点和链路成功映射后，返回虚拟网络映射结果.

AAG-VNM 算法的执行时间主要表现在步骤②中，其时间复杂度为O(|Ns|·|Es| +δ|Ns|3)，其中|Ns|和|Es|分别为物理网络的节点个数和链路个数，δ 为自适应扩展因子.因此，AAG-VNM 算法的时间复杂度为O(|Nv|·|Ns|·|Es| +δ|Nv| |Ns|3)，其中|Nv|为虚拟网络节点个数.

3 性能评估与分析

为了验证AAG-VNM 算法的有效性，文中通过仿真实验对AAG-VNM 算法的性能进行测试. 为了便于比较，本文同时实现了文献［4］和文献［8］中的算法，它们分别标记为TA-VNM 和VF-VNM.

3.1 实验设置

与文献［4］、［8］类似，仿真实验使用GT-ITM 工具［10］生成网络拓扑结构，每个物理网络设置为100个节点和大约560 条物理链路，每个物理节点的CPU 资源量和物理链路的带宽资源量在区间［50，100］内均匀分布，每条物理链路的时延均设为5.每个虚拟网络请求的节点个数在区间［5，15］内均匀分布，虚拟网络请求的到达服从泊松分布，每秒平均到达5个虚拟网络请求，任意一对虚拟节点之间的连接概率为0.5，虚拟网络的生存时间服从指数分布，平均生存时间设置为10 s，虚拟链路的最大时延在［20，30］内均匀分布，虚拟节点的CPU 资源需求量和虚拟链路的带宽资源需求量在区间［0，β］内均匀分布，当β 值为50 时，节点CPU 资源需求量和链路的带宽需求量最大为50，β 值越大，虚拟网络映射的难度越大.除第一组实验β 值分别取30 和60 外，其他仿真实验β 值均为50. AAG-VNM 算法的自适应扩展阈值δ 设置为6.每次仿真实验的时间为10 min，取10 次实验的平均值为仿真实验的最终结果.

3.2 实验结果与分析

从图2 可以看出，3个算法在β 值为30 时的平均执行时间基本相等，β 值为60 时的平均执行时间均呈增加趋势，VF-VNM 算法的平均执行时间最多.

如图3 和图4 所示，在物理网络资源和虚拟网络请求一定的情况下，AAG-VNM 算法的虚拟链路扩张系数相对较小，网络收益与开销比相对较大，其主要原因是AAG-VNM 算法根据节点和链路的资源状态，自适应地扩展物理网络，将相邻的虚拟节点和链路映射到邻接的物理节点和链路上，降低了虚拟链路的映射路径长度和虚拟网络映射的资源开销，因此提高了虚拟网络映射的质量.

图2 算法的平均执行时间图Figure 2 Algorithms'running time under different β value

图3 虚拟链路扩张系数图Figure 3 Stretch factor of virtual links

图4 网络收益与开销比(β=30)Figure 4 Network revenue-to-cost ratio

如图5 和图6 所示，AAG-VNM 算法的平均负载强度相对较小，其主要原因是在虚拟网络映射过程中，AAG-VNM 算法根据物理网络资源的分布状态，优先选择负载强度相对较小的物理节点和物理链路进行映射操作，降低了物理节点和物理链路的平均负载强度.如图7 所示，AAG-VNM 算法的虚拟网络请求接受率相对较高，进一步验证了AAGVNM 算法能根据节点、链路的资源状态，通过采用自适应扩展物理网络和负载均衡操作方法，不仅降低了虚拟网络映射的资源开销，而且均衡了物理网络中节点和链路的资源分布水平，有效地提高了虚拟网络映射的质量和物理网络资源的利用率，获得了较优的资源分配性能.

图5 物理节点的平均负载强度(β=30)Figure 5 Load stress of substrate nodes

图6 物理链路的平均负载强度(β=30)Figure 6 Load stress of substrate links

图7 虚拟网络请求接受率(β=30)Figure 7 Acceptance ratio of virtual network requests

4 结语

针对现有虚拟网络映射的主要问题，本文根据物理网络的资源分布状态，采用自适应扩展物理网络的映射方法，将节点映射和链路映射阶段有机地综合为一个映射过程，均衡地消耗物理网络资源，协调地解决虚拟节点和虚拟链路的映射操作，使虚拟网络成为物理网络或λ 扩展物理网络的同构子图.仿真结果表明，AAG-VNM 算法提高了物理网络的负载均衡性能，有效地降低了虚拟链路的映射路径长度，获得了较优的资源分配性能.由于底层物理网络中的节点和链路可能出现失效等问题，从而导致多个虚拟网络服务无法使用，在现有工作的基础上，将进一步研究容错性虚拟网络映射问题.

［1］李小玲，王怀民，丁博，等. 虚拟网络映射问题研究及其进展［J］.软件学报，2012，23(11):3009－3028.Li X L，Wang H M，Ding B，et al. Research and development of virtual network mapping problem［J］. Journal of Software，2012，23(11):3009－3028.

［2］刘光远，苏森. 面向底层单节点失效的轻量级可靠虚拟网络映射算法［J］.电子与信息学报，2013，35(11):2644－2649.Liu G Y，Su S. Less stringent reliable virtual network mapping algorithm for substrate single node failure［J］.Journal of Electronic ＆ Information Technology，2013，35(11):2644－2649.

［3］Yu M L，Yi Y，Jennifer R，et al. Rethinking virtual network embedding:Substrate support for path splitting and migration［J］. ACM Sigcomm Computer Communication Review，2008，38(2):17－29.

［4］Li X L，Wang H M，Guo C G，et al. Topology awareness algorithm for virtual network mapping［J］.Journal of Zhejiang University:Science C，2012，13(3):178－186.

［5］Chowdhury M，Rahman M R，Boutaba R. ViNEYard:Virtual network embedding algorithms with coordinated node and link mapping［J］. IEEE/ACM Transactions on Networking，2012，34(3):206－219.

［6］刘新刚，怀进鹏，高庆一，等. 一种保持结点紧凑的虚拟网络映射方法［J］.计算机学报，2012，35(12):2492－2503.Liu X G，Huai J P，Gao Q Y，et al. A virtual network embedding approach to preserving node closeness［J］.Chinese Journal of Computers，2012，35(12):2492－2503.

［7］Lischka J，Karl H. A virtual network mapping algorithm based on subgraph isomorphism detection［C］∥Proceeding of the 1st ACM workshop on virtualized infrastructure systems and architectures. Barcelona，Spain，2009:81－88.

［8］魏晓辉，邹磊，李洪亮.基于优化的同构子图搜索的虚拟网络映射算法［J］.吉林大学学报:工学版，2013，43(1):165－171.Wei X H，Zou L，Li H L. Virtual network embedding algorithm based on improved sub-graph isomorphism search［J］. Journal of Jilin University:Engineering and Technology Edition，2013，43(1):165－171.

［9］Eppstein D. Finding the k shortest paths［J］. SIAM Journal of Computer，1994，28(2):652－763.

［10］Zegura E，Calvert K，Bhattacharjee S. How to model an internetwork［C］∥Proceeding of the 15th annual joint conference of the IEEE computer and communications society. San Francisco CA，USA，1996:594－602.