优化的虚拟网络两阶段协同映射算法

郑永伟，艾中良

(华北计算技术研究所总体部，北京 100083)

0 引言

随着互联网技术的发展，网络协议和服务不断丰富，传统的互联网架构已经不能满足当前的需要，而重新规划网络架构困难重重，网络虚拟化作为构建新一代互联网架构的重要技术被提出［1］。利用网络虚拟化技术，多个异构的网络架构能够同时存在于同一个共享的底层基础网络环境之上。在网络虚拟化环境中，多个服务提供商SP无需自己投资搭建物理基础设施，只需要从一个或多个基础设施提供商ISP租赁共享的资源，并在其基础上构建异构虚拟网络，为端用户提供定制的端到端服务［2-4］。网络虚拟化也是网络测试试验床(GENI，Emulab，DETER等)的重要组成［5-7］，基于虚拟化，每个项目组根据试验需求构建满足要求的虚拟网络拓扑，之后在共享的试验床上部署试验环境并测试，而不用担心与其他项目组的试验冲突。

虚拟网络由虚拟节点和连接虚拟节点的虚拟链路组成，节点有计算能力和位置等要求，链路有带宽等要求，其中虚拟节点部署在底层网络的一个物理节点上，虚拟链路对应到底层网络上通常是源节点到目的节点的一条路径。网络虚拟化首要解决的是虚拟网映射问题，即如何把带有虚拟节点和虚拟链路约束的虚拟网络请求，映射到具有有限计算能力的物理节点和有限带宽资源的物理路径的底层网络上。虚拟网络映射问题已经成为了研究热点，它本身是NP难［8］，并且高效的映射算法能提高底层环境接收虚拟网络的数量和底层环境的利用率。从根本讲，虚拟网映射问题也属于资源分配问题，随着时间的增长，底层网络资源将产生不能使用的资源碎片，即空闲的资源被分割成许多小片，这些资源不能分配给新的请求。

虚拟网的映射由节点映射和链路映射两部分组成，一个设计合理的映射算法需要具备映射成功率高以及映射完成后底层环境能够接受更多的映射请求的能力，底层资源利用率高。虚拟网络映射如图1所示。

本文采用中心资源分配方式设计节点和链路协同映射的算法，该算法结合链路分割和链路迁移技术来提高资源映射的成功率和收益比，并采取邻近节点邻近映射来降低映射花费。

图1 虚拟网络映射

1 相关工作

虚拟网络映射问题与虚拟私有网VPN［9］嵌套以及网络测试床映射问题类似，然而经典的VPN请求仅包含带宽需求，不含节点约束;Emulab测试床使用Assign算法［10］，考虑带宽约束以及节点的独占使用，也就是说不同的虚拟网络不能共享底层物理节点。但是网络虚拟化具有虚拟节点和虚拟链路的容量要求，并且底层节点和链路可以被不同的虚拟网络共享，但同一个虚拟网络内的不同虚拟节点不能映射到同一个物理节点上。

为了减少虚拟网络映射的难度，当前的研究从不同的角度来限制问题空间，包括:(1)设定所有请求的到达时间是静态的、可知的，并且占用物理网络的时间也是可知的［11-12］;(2)忽略请求的资源约束［13］;(3)设定物理网络资源理想化，即资源是无限的［12-13］;(4)忽略请求拓扑的多样性［11］。文献［14］提到的分布式算法在没有中央控制器的情况下，同时映射虚拟节点和虚拟链路，但是算法的规模和性能与中心控制算法相比相差许多。文献［15］提出一种基于窗口的算法，根据收益大小来选择虚拟网络，此算法简化了问题，类似线下解决方案;为了能够接收更多的虚拟网络请求，文献［16］周期性地对底层物理环境中映射的虚拟链路进行重新映射来减少底层环境资源的碎片。

本文研究的问题是在线网络映射也称作动态网络映射，并且充分考虑请求的资源约束。

2 虚拟网映射模型

虚拟网络映射由3部分组成:虚拟网络、底层物理网络、虚拟网络和底层物理网络的映射约束。

2.1 底层网络模型

底层网络模型用加权无向图表示为GS=(NS，LS)，其中NS是底层节点的集合，LS是节点集合中节点之间的底层链路集合。与属于NS的底层节点ns相关的加权能力值分别为:C(ns)表示节点ns的CPU计算能力，Loc(ns)表示节点ns的地址位置，B(ns)表示与节点ns相连链路的带宽资源，以及Deg(ns)表示与节点ns连接的链路个数，其值越大表示节点ns资源越稀缺。与属于集合LS的节点i和j之间的链路ls(i，j)相关联的两个非负数为:(1)W(ls(i，j))表示链路的花费和延迟等一系列参数的集合;(2)C(ls(i，j))表示链路全部带宽。

设φ为底层网络GS中的底层路径的集合，两个底层节点间的底层路径P∈φ的最大带宽定义为底层路径中的最小带宽，即C(P)=C(ls(i，j));底层路径的权重(花费、延迟、抖动等)W(P)定义为路径P中的所有链路权重的和:W(P)=W(ls(i，j))。

2个物理节点的距离定义为底层网络中2个节点的最小跳数。

2.2 虚拟网络请求模型

用户提交的对共享底层网络的请求可以用加权无向图表示为GV(NV，LV)，其中NV是虚拟节点的集合，LV是NV集合中节点之间的虚拟链路集合。每个属于NV的虚拟节点nv与物理节点类似，具有相关加权能力值:C(nv)表示节点nv的CPU计算需求，Loc(nv)表示节点nv的地址位置需求，B(nv)表示与节点nv相连链路的带宽资源需求，以及非负最大距离D(nv)表示从虚拟节点nv到映射节点ns的往返时延RTT 约束，即 dis(Loc(nv)，Loc(ns))≤D(nv)。两个相连节点之间的虚拟链路lv∈LV的最低带宽需求用能力加权值C(lv)表示，链路的花费和延迟用W(lv)表示。

虚拟网络请求可以用四维的公式Req=(Reqid，GV，VV，MV)表示，其中 Reqid为请求的唯一标识。=(，)，其中和表示请求中的虚拟节点和虚拟链路。VV和MV分别表示图GV中节点和链路的需求矩阵:是虚拟节点的需求向量，其中1 ≤i≤||。

M=[(C(l(i，j))，W(l(i，j)))]表示节点Vvv和之间的虚拟链路lv∈的需求矩阵。

2.3 底层网络的资源负载

底层网络的资源使用情况采用S标识，其中底层节点负载SN(ns)表示为:分配在该底层节上所有虚拟节点的CPU需求总和，即SN(ns)，其中ns∈NS，x→y表示虚拟节点x映射在底层物理节点y上;同样地，底层链路负载SL(ls)表示为:所有分配的底层物理路径经过此链路的虚拟链路的带宽总和，即SL(ls)，其中 ls∈LS，x→y 表示虚拟链路x映射到的底层路径经过底层链路y。

底层节点的剩余可用计算资源RN(ns)表示为底层节点ns∈NS的可用CPU资源，即RN(ns)=C(ns)-SN(ns)。同样，底层链路的剩余可用带宽资源RL(ls)表示为底层链路ls∈LS的所有可用带宽的总量，即RL(ls)=C(ls)-SL(ls)。底层节点的剩余可用带宽资源RL(ns)表示为所有与底层节点ns∈NS相连的链路的可用带宽资源之和，即RL(ns)=(ls)，其中，ns≠nj。底层节点的所有资源RAN(ns)表示为:节点的CPU资源、节点的剩余可用带宽资源以及与节点相连链路个数的乘积，即RAN(ns)=RN(ns)*RL(ns)*Deg(ns)。底层路径P∈φ的可用带宽能力表示为该路径上所有底层链路的最小带宽资源，即RL(P)=

2.4 虚拟网络映射问题

基于底层和虚拟网络模型，查找虚拟网络GV到底层网络GS的最佳映射方案是一个NP难问题。映射MAP需要底层网络资源达到最好的负载均衡，并且在满足能力约束情况的同时，减少花费。虚拟网络映射可以分解为两个组成部分。

(1)节点映射。设MAPN:→表示虚拟节点到底层节点的映射函数，其中表示至少能够满足请求中一个虚拟节点的底层节点的集合，即:

(2)链路映射。设MAPL→ϑ∈φ表示虚拟链路和底层路径之间的映射函数，其中ϑ={P∈φ|RL(P)≥C(lv)，∀lv∈}。

2.5 映射目标

虚拟网络映射算法的目标为:虚拟网络请求映射的成功率最大、产生的收益最大、消耗的资源最少。虚拟网络请求映射的成功率定义为:θ=m/n，其中m为n个虚拟网络请求映射成功的个数;映射成功的收益定义为:

其中α表示链路带宽资源和节点计算资源的相对权重;定义虚拟请求消耗的底层资源的总和为:

其中nv→ns和表示底层链路ls分配给虚拟链路lv的带宽总和，αls与βns表示底层资源消耗的参数。由上可知，单位时间内收益的提高可通过提高映射的成功率和首先映射收益较大的请求，由于要解决的属于线上问题，请求不可预知，因此只能通过提高映射成功率来提高收益;映射资源的消耗可通过降低映射过程中链路映射到路径的长度来解决。

3 优化的两阶段协同映射算法

对映射目标分析可知，消耗资源的降低主要通过降低虚拟链路映射到物理路径上的距离(距离指跳数)，跳数越低则消耗的链路带宽资源越少，因此提出一种综合考虑节点映射和链路映射的两阶段协同映射算法。算法在节点映射阶段采用贪婪算法来尽可能映射虚拟网络上相邻节点到底层网络上的邻近节点上，结合路径迁移来解决瓶颈链路。算法在链路映射阶段采用链路分流来解决瓶颈映射带宽。其中路径迁移和链路分流结束能够使用底层物理网络的链路碎片，从而提高映射的成功率;贪婪算法是为了解决在节点映射阶段选取节点时，如何降低资源消耗的问题。本文采用的贪婪算法是集中映射的贪婪算法，即所有的虚拟节点尽可能映射到较小的底层物理网络区域范围，由此降低链路带宽消耗。

3.1 节点映射

令F表示本次请求已经完成映射的虚拟节点，S表示本次请求未映射到的物理节点。初始化时，F=Φ，S=Ns。

(1)统计每个虚拟节点nv的满足其距离约束的物理节点集合，记作θ(nv)。按照nv计算需求从θ(nv)排除掉节点计算能力不够的节点得δ(nv)={ns|RN(ns)≥C(nv)，ns∈NS}∩θ(nv)。若 δ(nv)= Φ，映射失败，终止算法;统计S中每个节点的计算能力与相连链路带宽和乘积，记作q(ns)。

(2)分别对底层节点的剩余可用带宽资源RL(ns)和虚拟节点的带宽需求B(nv)按照从大到小进行排序，排序的结果分别记作SSubBand和SReqBand。

(3)从SReqBand中选取尚未分配的第一个节点记作nv，并从SSubBand中查找大于B(nv)的物理节点，并与δ(nv)相交取得交集∂(nv)。

(4)∂(nv)={ns|B(nv)≤RL(ns)，ns∈S}∩δ(nv)。若∂(nv)为空，进行第(4)步;否则进行第(5)步。

(5)从δ(nv)中查找本次请求中尚未分配的物理节点δ(nv)∩S，并且与该节点相连的链路在现已完成的映射中已被分配，统计与该节点相连的链路在现已完成映射的链路映射阶段的带宽消耗和(注:只统计节点既不作为路径的源节点，也不作为路径的目的节点的带宽消耗)，将得到的带宽和与该节点相连链路剩余带宽和加起来，从结果集中查找大于带宽请求的节点子集，继续从中筛选出路径迁移代价较小的(迁移链路个数最小)的几个节点按照代价从小到大进行路径迁移，并且要求后面的迁移不能影响前面节点的路径迁移，如果全部迁移失败，则映射失败，终止算法;否则路径迁移成功的节点记作集合∂(nv)，更新带宽资源和q(ns)，并继续进行下一步。

(6)从F中查询所有与节点nv相连的节点集合，记作 τ(nv)={nvi|l(nv，nvi)∈LV，nvi∈F}，若 τ(nv)≠Φ，分别统计∂(nv)中每个节点与τ(nv)集合中所有节点映射到的物理节点ns的最短距离与对应虚拟链路带宽的乘积和，并除以q(ns)，选择结果最小的即为nv映射到的物理节点。若τ(nv)=Φ，则选择∂(nv)中节点的q(ns)最大的节点，作为nv映射到的物理节点。

(7)更新GN节点和带宽的剩余资源，重新排序，并把nv添加到F中，映射到的物理节点从S中删除，重复步骤(3)。

算法分析:该节点映射算法，结合了距离约束和节点相连的链路约束，减少了映射解的空间;算法采用路径迁移来解决由于与节点相连的链路资源不足问题;算法第(6)步采用到已完成映射节点对应物理节点链路带宽消耗最小和节点资源最大作为贪婪准则的贪婪算法来选取映射节点，能有效降低映射资源消耗中的带宽消耗;如果有大量以往或未来虚拟网络请求数据，可以统计所有虚拟节点的计算能力，形成概率分布，查找物理节点分配成功后剩余计算能力的对应概率，该概率表示将来能够映射的可能性，概率越大映射的可能性越大，该概率加一并除以到已完成映射节点对应物理节点链路带宽消耗的结果可以作为贪婪准则。

3.2 链路映射

该阶段主要采用多商品流算法，算法默认采用了链路分割技术来解决节点链路资源能满足需求，但单独的链路不满足映射的问题，如果不存在可行解，则拒绝本次映射请求，算法终止;否则，接受该请求，并更新节点和链路资源。

4 仿真实验结果及分析

本文的仿真实验环境采用GT-ITM工具生成网络拓扑结构，执行时间为40000个时间单元，并参考文献［15，17］分别设计生成底层网络拓扑和虚拟网络拓扑请求。其中底层网络拓扑是模拟具有100个节点的中等规模的ISP，每对底层节点有0.5的概率随机相连，底层节点CPU和底层链路带宽资源都是服务参数为50和100的均匀分布。虚拟网络的请求，以每100时间单元6虚拟网络请求的速率泊松到达。每个虚拟网络请求的生命周期服从均值为1000时间单元的指数分布，虚拟节点的个数服从参数为2和10的均匀分布，虚拟网络节点对的连接率固定在0.5，虚拟节点的CPU需求服从参数为0和20的均匀分布，虚拟链路的带宽需求服从参数为0和0的均匀分布，并且虚拟节点的位置随机选取一个物理节点作为中心，满足距离约束的节点是到中心节点的跳数为1或2的节点。

仿真实验结果见图2、图3，并与文献［17］中提到的两阶段映射算法D-ViNE进行对比，其中两种算法依赖的软硬件环境和算法的输入是一致的，结果表明本文的算法在映射成功率、资源收益消耗比方面有一定程度的提高。

图2 映射成功率对比图

图3 算法收益花费比对比图

5 结束语

本文主要研究了网络虚拟化中的关键问题——虚拟网络映射问题，针对该问题进行了讨论和分析，并基于现有的两阶段映射算法，加以优化。该算法与现有算法相比，主要改进如下:(1)在节点映射的链路带宽资源不能满足需求的情况下，采用路径迁移，提高了映射的成功率;(2)算法充分考虑了节点的位置、计算、带宽等需求，使得映射更加符合真实情况;(3)节点映射阶段综合考虑了物理节点的资源和链路映射的带宽消耗，并有效地把两个阶段协同起来，降低映射的资源消耗;(4)算法着重降低链路映射资源消耗;(5)本文分析了采用贪婪算法的原因以及贪婪准则。

［1］Thomas Anderson，Larry Peterson，Scott Shenker，et a1.Overcoming the Internet impasse through virtualization［J］.Computer，2005，38(4):34-41.

［2］Turner J，Taylor D.Diversifying the Internet［C］//Proceedings of the 2005 IEEE GLOBECOM.2005，2:755-760.

［3］Bavier A，Feamster N，Huang M，et al.In VINI veritas:Realistic and controlled network experimentation［C］//Proceedings of the 2006 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications.2006:3-14.

［4］Feamster N，Gao L，Rexford J.How to lease the Internet in your spare time［J］.ACM SIGCOMM Computer Communication Review，2007，37(1):61-64.

［5］GENI.net.Global Environment for Network Innovations［EB/OL］.http://www.geni.net，2010-12-22.

［6］Jay Lepreau.Emulab:Network Emulation Testbed［EB/OL］.http://www.emulab.net，2006-12-22.

［7］The DETER Project.The DETER Testbed:Overview［DB/OL］.http://www.isi.edu/deter/docs/testbed.overview.pdf，2004-08-25.

［8］Andersen D G.Theoretical Approaches to Node Assignment［DB/OL］.http://www.cs.cmu.edu/～ dga/papers/andersen-assign-abstract.html，2002-12-01.

［9］Duffield N G，Goyal P，Greenberg A，et al.Resource management with hoses:Point-to-cloud services for virtual private networks［J］.IEEE/ACM Transactions on Networking，2002，10(5):679-692.

［10］Ricci R，Alfeld C，Lepreau J.A solver for the network testbed mapping problem［J］.ACM SIGCOMM Computer Communication Review，2003，33(2):65-81.

［11］Lu J，Turner J.Efficient Mapping of Virtual Networks onto a Shared Substrate［R］.Washington University，2006.

［12］Zhu Y，Ammar M.Algorithms for assigning substrate network resources to virtual network components［C］//Proceedings of the 25th IEEE International Conference on Computer Communications.2006，6:2812-2823.

［13］Fan J，Ammar M.Dynamic topology configuration in service overlay networks:A study of reconfiguration policies［C］//Proceedings of the 25th IEEE International Conference on Computer Communications.2006，2:641-652.

［14］Chowdhury M，Samuel F，Boutaba R.PolyViNe:Policybased virtual network embedding across multiple domains［C］//Proceedings of the 2nd ACM SIGCOMM Workshop on Virtualized Infrastructure Systems and Architectures.2010:49-56.

［15］Yu M，Yi Y，Rexford J，et al.Rethinking virtual network embedding:Substrate support for path splitting and migration［J］.ACM SIGCOMM Computer Communication Review，2008，38(2):17-29.

［16］Butt N F，Chowdhury M，Boutaba R.Topology-awareness and reoptimization mechanism for virtual network embedding［C］//Proceedings of the 9th IFIP TC 6 International Conference on Networking.2010:27-39.

［17］Chowdhury M，Rahman M R，Boutaba R.Virtual network embedding with coordinated node and link mapping［C］//Proceedings of the 28th IEEE International Conference on Computer Communications.2009:783-791.