论文部分内容阅读
摘要
网络虚拟化技术通过对物理资源的抽象，可以有效解决现有互联网架构中存在的网络结构僵化、可扩展性差等问题。虚拟网络映射问题是指将用户发送的所有虚网请求映射到底层物理网络中，同时还要满足虚网请求中对各个资源的限制要求（如节点计算能力、链路带宽等）。从节点负载平衡的角度出发，在基于就近原则的虚网映射算法基础上，引入节点负载平衡的反馈机制，引导各个虚网请求更均匀地映射到底层物理网络中。另外，在k短路径算法机制中引入了当前链路资源占有率作为评价参考标准，这样可以尽可能均匀地分散链路压力。同时，在检验链路资源是否满足虚网请求的过程中，由于优先选中的链路资源占有率低，所以算法映射成功率高，映射耗时更短，虚拟网络映射效率得到了有效提高。关键词网络虚拟化；虚网映射；占有率反馈；负载平衡；链路映射
中图分类号TP242
文献标志码A
收稿日期20160725
资助项目国家自然科学基金（61372103）；中兴通讯产学研项目（2015ZTE0413）
作者简介
王慕阳，男，硕士生，主要研究方向为虚拟网络映射机制与算法。wangmuyang@seu.edu.cn
陈立全（通信作者），男，博士，副教授，博士生导师，主要研究方向为网络与信息安全.Lqchen@seu.edu.cn
1东南大学信息科学与工程学院，南京，210096
2中兴通讯股份有限公司，深圳，518057
0 引言
网络虚拟化是为解决网络结构僵化问题而提出的新兴网络技术。
网络虚拟化技术的核心是虚拟网络中节点和链路到物理网络的映射。在实际应用中，底层物理网络承载多个虚拟网络，需要消耗相应的物理资源，包括节点CPU资源、链路带宽等。当有一个新的虚拟网络请求需要映射到底层物理网络上时，有些物理节点和链路已经无法满足新到来的虚网请求的资源需求，无法在其上映射此虚拟网络。而且，如果虚拟网络映射不合理，可能会出现各个节点之间的数据流量需要经过多个节点的转发，增加额外的带宽资源消耗，甚至会因为所选节点之间的链路已经没有足够的带宽，而导致映射失败。可见，当前虚拟网络发展急需要设计高效的虚拟网络映射算法来将虚拟网络的各个节点和链路映射到物理网络上，并希望在满足虚网请求的资源需求的同时，尽可能地提高物理网络的资源利用率，降低虚网映射的成本。
传统的虚网映射算法较多是基于启发式的两步映射算法[13]。它们一般先进行节点映射，再进行链路映射。但目前的虚网映射算法大多基于对节点CPU和链路资源的贪心算法，这就导致物理网中具有较高CPU资源的节点及其周边节点会被优先映射，从而导致该部分节点已经饱和而其他节点还尚未映射的情况发生，甚至会发生所有虚网竞争同一片物理网资源的情况，这对某一区域会形成较大的负载压力。
除此之外，在两步映射算法中，优化方案的重点往往放在了节点映射算法中，对于链路映射算法，如果不支持路径切割，则通常采用k短路径算法作为最常见的链路算法模型[4]。k短路径算法一般选取路径最短的前k个映射方案，再依次验证这些路径是否满足虚网请求中的链路资源要求来实现算法。当底层网络支持路径切割时，链路映射算法大多是基于多商品流的线性规划进行求解[5]。
针对各种拓扑结构，文献[6]提出了一种针对星状拓扑的离线的两阶段映射方案，文献[7]提出了针对流量矩阵的在线的两阶段映射算法，文献[8]提出了针对星状和辐射状拓扑结构的离线的一阶段映射算法。这三种算法都是以减少映射开销为优化目标，且在各自的拓扑结构中都能取得不错的效果，但是在其他拓扑结构，或无明顯拓扑特征的网络中，上述方法的算法性能并不理想。
文献[9]提出了重映射的概念，这是一种在线的一阶段映射算法。它的优化目标是当底层物
理网不再满足虚网需求，或虚网需求发生改变时，尽可能地降低虚网重新映射的代价。
为了解决上述问题，本文从节点负载平衡的角度出发，在基于就近原则的虚网映射算法[10]的基础上，引入节点负载平衡的反馈机制，引导各个虚网请求更加均匀地映射到底层物理网络中，从而有效避免节点映射阶段资源瓶颈的发生。另外该算法在k短路径算法机制[11]中引入了当前链路资源占有率作为路径长度的评价参考标准。这样，在计算路径长度的时候，就会将剩余链路资源较多的物理路径优先映射，就可以尽可能均匀地分散链路压力。同时，在检验链路资源是否满足虚网请求的过程中，由于优先选中的链路资源占有率低，剩余资源较多，所以算法映射成功率高，耗时较短，虚拟网络映射的效率得到了有效的提高。
1 基于占有率反馈的虚拟网络映射
1.1 节点映射方法
完整的节点映射算法流程如图1所示。在本文提出的基于占有率反馈的虚拟网络映射算法中，首先根据当前的虚网请求，计算虚网请求中各个虚网节点的请求值（rv），将虚网节点按照其请求值（rv）从大到小顺序进行节点映射。请求值（rv）是指虚网节点映射所需的物理资源，其定义为
其中Bw是指虚拟链路lv的带宽需求，Ccpu指的是虚网节点nv的CPU容量需求，L（nv）是指与虚网节点nv相连的虚拟链路lv的集合，α和β是用于平衡CPU和带宽的权重调节参数，一般情况下，α和β的取值范围在1～3之间，默认α和β取1。式（1）定义了虚网请求中一个虚拟节点的请求值rv，它象征了这个虚拟节点在虚网请求中的重要程度，也一定程度上代表了该节点映射的困难程度。因此在节点映射过程中，将会优先映射rv值较高的虚拟节点。
在虚网请求中，不断选取尚未映射的虚网节点进行节点映射，选取的顺序就按照rv值从高到低选取。每次节点映射时，先从底层物理网中选择出剩余CPU资源大于此虚网节点所需CPU资源的所有物理节点，作为可供映射的物理节点，然后计算所有选出的物理网节点的加权资源值（rwv），将选出的物理网节点按照加权资源值（rwv）从大到小排序，并将加权资源值（rwv）最大的物理节点作为当前虚网节点的映射对象。这样该节点的映射过程就算成功了，接着进入下一节点的映射工作。加权资源值（rwv）是指物理节点提供资源的能力： 其中，Nneigh是针对底层物理网节点ns的相关系数，Nneigh为大于1的实数，该参数用来定义两个物理节点的相近程度，指数m 表示当前虚网请求中已经映射成功并且映射的物理节点与ns有直接连接的虚网节点个数.一个物理节点的Nmneigh值越高，说明该节点与当前虚网请求中已经映射的物理节点集合距离较近，联系更密切，有较好的带宽资源。所以在映射过程中，设计的算法会更倾向于映射该节点，以提高之后的链路映射的成功率。Ooccupy表示物理节点ns已经被其他虚网请求占用的相关参数，Ooccupy为0到1之间的实数，且随着Ooccupy的减小，反馈作用得到加强。n表示物理节点被其他虚网请求占用的次数，一个物理节点Onoccupy的值越小，说明该节点已经被其他虚网请求映射的次数越多。出于负载平衡的考虑，设计的算法将更倾向于不再映射该节点，而是选择其他尚未被映射的物理节点。
当无法找到满足虚网节点CPU需求的物理节点时，该节点映射失败，整个虚网节点映射失败。当所有节点都完成节点映射时，该虚网节点映射成功，准备进入链路映射阶段。
1.2 链路映射方法
在链路映射阶段，如图2所示，首先选择当前未链路映射的虚网请求，计算其虚网链路的链路带宽Rbw，并从大到小进行排序，其中链路带宽Rbw为虚网请求中，虚网链路所需的通信带宽大小。
根据链路带宽Rbw的排序，依次对每条虚网链路进行映射。每次链路映射时，先计算底层物理网中任意两个直接相连的物理节点的链路占用系数，将该系数作为这两个物理节点的路径距离，构成一个新的无向图Gs′（Ns，Ls，Rls ′）。然后找出待映射链路的两个端点节点，虚拟节点1和虚拟节点2，再分别找到其映射的物理节点1 和物理节点2，将这两个节点作为源节点和目标节点在无向
图G′s中进行k短路径的求解，寻找出路径最短的前k条路径。
最后，依次判断这前k条最短路径是否满足虚网链路的带宽需求。如果满足，则将满足带宽条件的最短路径作为虚拟链路的映射对象，该虚拟链路映射成功，继续对下一条虚拟链路进行映射。如果在链路映射过程中，无法找到满足虚网链路带宽需求的路径，则此次虚网链路映射失败。如果虚网中所有的虚拟链路都映射成功，则该虚网链路映射成功。
在上述链路映射算法中，链路占用系数定义为：链路占用系数=1-链路可用带宽链路总带宽+ε，其中ε根据需要取大于零的值，建议取0.5。无向图Gs′（Ns，Ls，Rls′）中，Ns为底层物理节点的集合，Ls为底层物理链路的集合，Rls′为底层物理链路l的路径距离，其大小为链路占用系数的值。
2 仿真实验与结果分析
在Matlab上建立仿真环境。模拟的底层物理网络共有100个物理节点，任意两个物理节点之间存在链路的概率为0.5。这些节点的CPU资源和链路的带宽值在50和100之间随机分布。虚拟网络请求的参数设置参照文献[1213]。虚网请求的到达频率是每个时间窗5个请求。对于每个虚网请求，虚拟节点的数目在2至10之间随机生成。虚拟网络中每两个节点之间的联通概率为0.5。虚拟节点的CPU值在0和20之间随机分布，而虚拟链路的带宽值是在0到Bw，max之间随机分布，其中Bw，max默认取50。整个虚网生存周期取10，拒绝次数取3次。在研究链路占用率反馈技术对映射时间的影响时，Bw，max的取值范围为10～90。
图3显示当Nneigh就近系数取1，即不考虑就近因素时，虚网接收率明显较低，且随着时间窗的增加，虚网请求不断到来，虚网接收率持续降低，直到在8～10个时间窗后，部分映射成功的虚网完成映射周期，结束映射并释放出物理资源，虚网接收率才逐步稳定在0.75至0.8之间。而当Nneigh取2或3时，虚网优先映射相邻的节点，所以链路映射成功率较高，虚网接收率始终维持在较高的0.9，说明虚网所能承受的最大虚网个数提高了，在8～10个时间窗内，还没有虚网释放物理资源的时候，物理网络仍然能较好地映射新到的虚网请求，并且2和3的曲线十分接近，说明Nneigh的值不需要过高，过高对映射性能没有太大的改观。
图4显示当Ooccupy占用系数取1，即不考虑节点占用率反馈的时候，虚网接收率开始较高，然后随着虚网的不断加入，有一个轻微下滑的过程，最终稳定在0.89左右，而当引入节点占用率反馈机制，并取Ooccupy为0.75时，虚网接收率的一直稳定维持在0.91左右，这说明随着虚网的加入，节点占有率反馈机制很好地分散了节点负载压力，有效缓解了资源瓶颈的产生。但是，若取Ooccupy为0.5，可以看出虚网接收率明顯较低，且有一个明显的下滑过程。经过分析，这是由于Ooccupy系数取得过小，映射算法过于追求将节点分散映射，而导致将底层物理网资源碎片化，从而大幅降低映射成功率。这一现象在虚网请求数量较多的时候尤为明显。
图5显示各映射算法在虚网链路带宽最大值Bw，max从10增加到90时对算法运行时间的影响.当Bw，max小于30时，底层物理链路资源充足，所有链路映射几乎都是一次成功，所以时间很短，但随着虚网链路继续增加，虽然总体趋势都是映射时间大幅增加，但是相比于隐藏跳数算法[14]、基于网络拓扑结构[1516]的映射算法、k短路径的映射算法[11]等其他算法，基于占有率反馈的映射算法在Bw，max在50到70之间的映射时间明显较短，在这一阶段，虽然链路资源已经相对不足，但所有映射成功的链路基本都是在前几次映射中就成功的，所以本文提出的算法耗时较短。
图6显示各映射算法的物理节点CPU利用率随时间窗增加的变化情况.从图6中看出各个算法的底层物理节点利用率随着每个时间窗中虚网请求的到来而不断上升，并最终趋于稳定。其中基于就近原则的映射算法[10]的节点CPU利用率最高，基于占有率反馈的映射算法次之，相较于前者，基于占有率反馈的映射在优化目标上牺牲了部分节点资源利用率以换取物理节点的负载平衡。基于网络拓扑结构的映射算法[1516]和普通的k短路径映射算法[11]相对于以上两种算法的节点CPU利用率则更低。 3 結束语
本文分析了传统映射算法的特点和可能存在的缺陷，提出了基于占有率反馈的虚拟网络资源映射方法，详细介绍了该算法的主要流程和改进的技术特点，并在仿真实验中给出了该方法的映射性能的展示。本文所提出的算法在节点映射阶段，在追求节点CPU资源的同时，创新性地考虑了节点的负载平衡，在基于就近原则的虚网映射算法的基础上，引入节点负载平衡的反馈机制，从而引导各个虚网请求更加均匀地映射到底层物理网络中，避免了物理网络中的核心节点资源被过早耗尽。在链路映射阶段，本算法在k短路径算法机制中引入了当前链路资源占有率作为评价参考标准，这样做可以尽可能均匀地分散链路压力，同时在检验链路资源是否满足虚网请求的过程中，由于优先选中的链路资源占有率低，剩余资源较多，算法映射成功率高，耗时更短，虚拟网络映射的效率得到了极大提高。
参考文献
References
[1] Lu J，Turner J.Efficient mapping of virtual networks onto a shared substrate[J].Washington University in St Louis，2006，35：24552462
[2] Zhu Y，Ammar M.Algorithms for assigning substrate network resources to virtual network components[C]∥Proceedings of 25th IEEE International Conference on Computer Communications，2006：112
[3] Chen X H，Li C Z，Jiang Y L.A feedback control approach for energy efficient virtual network embedding[J].Computer Communications，2016，80（15）：1632
[4] Hu X B，Wang M，Hu D，et al.A ripplespreading algorithm for the k shortest paths problem[C]∥The 3rd Global Congress on Intelligent Systems，2012：202208
[5] Ciciriello P，Mottola L，Picco G P.Efficient routing from multiple sources to multiple sinks in wireless sensor networks[C]∥Proceedings of 4th European Conference on Wireless Sensor Networks，2007：3450
[6] Kareche S，Ductor S，Guessoum Z，et al.A new robust heuristic for assigning substrate network resources to virtual networks[C]∥International Conference on Advanced Networking Distributed Systems and Applications，2014：4752
[7] Fan J L，Ammar M H.Dynamic topology configuration in service overlay networks：A study of reconfiguration policies[C]∥Proceedings of 25th IEEE International Conference on Computer Communications，2006：112
[8] Wei X H，Li H L，Yang K，et al.Topology aware partial virtual cluster mapping algorithm on shared distributed infrastructures[C]∥IEEE Transactions on Parallel and Distributed Systems，2014，25（10）：27212730
[9] Cai Z P，Liu F，Xiao N，et al.Virtual network embedding for evolving networks[C]∥IEEE Global Telecommunications Conference，2010：15
[10] Liu J，Huang T，Chen J Y，et al.A new algorithm based on the proximity principle for the virtual networking embedding problem[J].Journal of Zhejiang University（Science C），2011，12（11）：910918
[11] Wang F，Man Y，Man L C.Intelligent optimization approach for the k shortest paths problem based on genetic algorithm[C]∥10th International Conference on Natural Computation，2014：219224
[12] Gonzlez A，Barra E，Beghelli A，et al.A subgraph mappingbased algorithm for virtual network allocation over flexible grid networks[C]∥17th International Conference on Transparent Optical Network，2015：14
[13] Zegura E W，Calvert K L，Bhattacharjee S.How to model an internetwork[C]∥Proc 15th IEEE International Conference on Computer Communications，1996：594602
[14] Botero J F，Hesselbach X，Fischer A，et al.Optimal mapping of virtual ne tworks with hidden hops[J].Telecommunication Systems，2012，51（4）：273282
[15] Dhanapala D C，Jayasumana A P.Topology preserving maps extracting layout maps of wireless sensor networks from virtual coordinates[J].IEEE/ACM Transactions on Networking，2014，22（3）：784797
[16] Wang Z M，Wu J X，Wang Y，et al.Survivable virtual network mapping using optimal back up topology in virtualized SDN[J].China Communications，2014，11（2）：2637
网络虚拟化技术通过对物理资源的抽象，可以有效解决现有互联网架构中存在的网络结构僵化、可扩展性差等问题。虚拟网络映射问题是指将用户发送的所有虚网请求映射到底层物理网络中，同时还要满足虚网请求中对各个资源的限制要求（如节点计算能力、链路带宽等）。从节点负载平衡的角度出发，在基于就近原则的虚网映射算法基础上，引入节点负载平衡的反馈机制，引导各个虚网请求更均匀地映射到底层物理网络中。另外，在k短路径算法机制中引入了当前链路资源占有率作为评价参考标准，这样可以尽可能均匀地分散链路压力。同时，在检验链路资源是否满足虚网请求的过程中，由于优先选中的链路资源占有率低，所以算法映射成功率高，映射耗时更短，虚拟网络映射效率得到了有效提高。关键词网络虚拟化；虚网映射；占有率反馈；负载平衡；链路映射
中图分类号TP242
文献标志码A
收稿日期20160725
资助项目国家自然科学基金（61372103）；中兴通讯产学研项目（2015ZTE0413）
作者简介
王慕阳，男，硕士生，主要研究方向为虚拟网络映射机制与算法。wangmuyang@seu.edu.cn
陈立全（通信作者），男，博士，副教授，博士生导师，主要研究方向为网络与信息安全.Lqchen@seu.edu.cn
1东南大学信息科学与工程学院，南京，210096
2中兴通讯股份有限公司，深圳，518057
0 引言
网络虚拟化是为解决网络结构僵化问题而提出的新兴网络技术。
网络虚拟化技术的核心是虚拟网络中节点和链路到物理网络的映射。在实际应用中，底层物理网络承载多个虚拟网络，需要消耗相应的物理资源，包括节点CPU资源、链路带宽等。当有一个新的虚拟网络请求需要映射到底层物理网络上时，有些物理节点和链路已经无法满足新到来的虚网请求的资源需求，无法在其上映射此虚拟网络。而且，如果虚拟网络映射不合理，可能会出现各个节点之间的数据流量需要经过多个节点的转发，增加额外的带宽资源消耗，甚至会因为所选节点之间的链路已经没有足够的带宽，而导致映射失败。可见，当前虚拟网络发展急需要设计高效的虚拟网络映射算法来将虚拟网络的各个节点和链路映射到物理网络上，并希望在满足虚网请求的资源需求的同时，尽可能地提高物理网络的资源利用率，降低虚网映射的成本。
传统的虚网映射算法较多是基于启发式的两步映射算法[13]。它们一般先进行节点映射，再进行链路映射。但目前的虚网映射算法大多基于对节点CPU和链路资源的贪心算法，这就导致物理网中具有较高CPU资源的节点及其周边节点会被优先映射，从而导致该部分节点已经饱和而其他节点还尚未映射的情况发生，甚至会发生所有虚网竞争同一片物理网资源的情况，这对某一区域会形成较大的负载压力。
除此之外，在两步映射算法中，优化方案的重点往往放在了节点映射算法中，对于链路映射算法，如果不支持路径切割，则通常采用k短路径算法作为最常见的链路算法模型[4]。k短路径算法一般选取路径最短的前k个映射方案，再依次验证这些路径是否满足虚网请求中的链路资源要求来实现算法。当底层网络支持路径切割时，链路映射算法大多是基于多商品流的线性规划进行求解[5]。
针对各种拓扑结构，文献[6]提出了一种针对星状拓扑的离线的两阶段映射方案，文献[7]提出了针对流量矩阵的在线的两阶段映射算法，文献[8]提出了针对星状和辐射状拓扑结构的离线的一阶段映射算法。这三种算法都是以减少映射开销为优化目标，且在各自的拓扑结构中都能取得不错的效果，但是在其他拓扑结构，或无明顯拓扑特征的网络中，上述方法的算法性能并不理想。
文献[9]提出了重映射的概念，这是一种在线的一阶段映射算法。它的优化目标是当底层物
理网不再满足虚网需求，或虚网需求发生改变时，尽可能地降低虚网重新映射的代价。
为了解决上述问题，本文从节点负载平衡的角度出发，在基于就近原则的虚网映射算法[10]的基础上，引入节点负载平衡的反馈机制，引导各个虚网请求更加均匀地映射到底层物理网络中，从而有效避免节点映射阶段资源瓶颈的发生。另外该算法在k短路径算法机制[11]中引入了当前链路资源占有率作为路径长度的评价参考标准。这样，在计算路径长度的时候，就会将剩余链路资源较多的物理路径优先映射，就可以尽可能均匀地分散链路压力。同时，在检验链路资源是否满足虚网请求的过程中，由于优先选中的链路资源占有率低，剩余资源较多，所以算法映射成功率高，耗时较短，虚拟网络映射的效率得到了有效的提高。
1 基于占有率反馈的虚拟网络映射
1.1 节点映射方法
完整的节点映射算法流程如图1所示。在本文提出的基于占有率反馈的虚拟网络映射算法中，首先根据当前的虚网请求，计算虚网请求中各个虚网节点的请求值（rv），将虚网节点按照其请求值（rv）从大到小顺序进行节点映射。请求值（rv）是指虚网节点映射所需的物理资源，其定义为
其中Bw是指虚拟链路lv的带宽需求，Ccpu指的是虚网节点nv的CPU容量需求，L（nv）是指与虚网节点nv相连的虚拟链路lv的集合，α和β是用于平衡CPU和带宽的权重调节参数，一般情况下，α和β的取值范围在1～3之间，默认α和β取1。式（1）定义了虚网请求中一个虚拟节点的请求值rv，它象征了这个虚拟节点在虚网请求中的重要程度，也一定程度上代表了该节点映射的困难程度。因此在节点映射过程中，将会优先映射rv值较高的虚拟节点。
在虚网请求中，不断选取尚未映射的虚网节点进行节点映射，选取的顺序就按照rv值从高到低选取。每次节点映射时，先从底层物理网中选择出剩余CPU资源大于此虚网节点所需CPU资源的所有物理节点，作为可供映射的物理节点，然后计算所有选出的物理网节点的加权资源值（rwv），将选出的物理网节点按照加权资源值（rwv）从大到小排序，并将加权资源值（rwv）最大的物理节点作为当前虚网节点的映射对象。这样该节点的映射过程就算成功了，接着进入下一节点的映射工作。加权资源值（rwv）是指物理节点提供资源的能力： 其中，Nneigh是针对底层物理网节点ns的相关系数，Nneigh为大于1的实数，该参数用来定义两个物理节点的相近程度，指数m 表示当前虚网请求中已经映射成功并且映射的物理节点与ns有直接连接的虚网节点个数.一个物理节点的Nmneigh值越高，说明该节点与当前虚网请求中已经映射的物理节点集合距离较近，联系更密切，有较好的带宽资源。所以在映射过程中，设计的算法会更倾向于映射该节点，以提高之后的链路映射的成功率。Ooccupy表示物理节点ns已经被其他虚网请求占用的相关参数，Ooccupy为0到1之间的实数，且随着Ooccupy的减小，反馈作用得到加强。n表示物理节点被其他虚网请求占用的次数，一个物理节点Onoccupy的值越小，说明该节点已经被其他虚网请求映射的次数越多。出于负载平衡的考虑，设计的算法将更倾向于不再映射该节点，而是选择其他尚未被映射的物理节点。
当无法找到满足虚网节点CPU需求的物理节点时，该节点映射失败，整个虚网节点映射失败。当所有节点都完成节点映射时，该虚网节点映射成功，准备进入链路映射阶段。
1.2 链路映射方法
在链路映射阶段，如图2所示，首先选择当前未链路映射的虚网请求，计算其虚网链路的链路带宽Rbw，并从大到小进行排序，其中链路带宽Rbw为虚网请求中，虚网链路所需的通信带宽大小。
根据链路带宽Rbw的排序，依次对每条虚网链路进行映射。每次链路映射时，先计算底层物理网中任意两个直接相连的物理节点的链路占用系数，将该系数作为这两个物理节点的路径距离，构成一个新的无向图Gs′（Ns，Ls，Rls ′）。然后找出待映射链路的两个端点节点，虚拟节点1和虚拟节点2，再分别找到其映射的物理节点1 和物理节点2，将这两个节点作为源节点和目标节点在无向
图G′s中进行k短路径的求解，寻找出路径最短的前k条路径。
最后，依次判断这前k条最短路径是否满足虚网链路的带宽需求。如果满足，则将满足带宽条件的最短路径作为虚拟链路的映射对象，该虚拟链路映射成功，继续对下一条虚拟链路进行映射。如果在链路映射过程中，无法找到满足虚网链路带宽需求的路径，则此次虚网链路映射失败。如果虚网中所有的虚拟链路都映射成功，则该虚网链路映射成功。
在上述链路映射算法中，链路占用系数定义为：链路占用系数=1-链路可用带宽链路总带宽+ε，其中ε根据需要取大于零的值，建议取0.5。无向图Gs′（Ns，Ls，Rls′）中，Ns为底层物理节点的集合，Ls为底层物理链路的集合，Rls′为底层物理链路l的路径距离，其大小为链路占用系数的值。
2 仿真实验与结果分析
在Matlab上建立仿真环境。模拟的底层物理网络共有100个物理节点，任意两个物理节点之间存在链路的概率为0.5。这些节点的CPU资源和链路的带宽值在50和100之间随机分布。虚拟网络请求的参数设置参照文献[1213]。虚网请求的到达频率是每个时间窗5个请求。对于每个虚网请求，虚拟节点的数目在2至10之间随机生成。虚拟网络中每两个节点之间的联通概率为0.5。虚拟节点的CPU值在0和20之间随机分布，而虚拟链路的带宽值是在0到Bw，max之间随机分布，其中Bw，max默认取50。整个虚网生存周期取10，拒绝次数取3次。在研究链路占用率反馈技术对映射时间的影响时，Bw，max的取值范围为10～90。
图3显示当Nneigh就近系数取1，即不考虑就近因素时，虚网接收率明显较低，且随着时间窗的增加，虚网请求不断到来，虚网接收率持续降低，直到在8～10个时间窗后，部分映射成功的虚网完成映射周期，结束映射并释放出物理资源，虚网接收率才逐步稳定在0.75至0.8之间。而当Nneigh取2或3时，虚网优先映射相邻的节点，所以链路映射成功率较高，虚网接收率始终维持在较高的0.9，说明虚网所能承受的最大虚网个数提高了，在8～10个时间窗内，还没有虚网释放物理资源的时候，物理网络仍然能较好地映射新到的虚网请求，并且2和3的曲线十分接近，说明Nneigh的值不需要过高，过高对映射性能没有太大的改观。
图4显示当Ooccupy占用系数取1，即不考虑节点占用率反馈的时候，虚网接收率开始较高，然后随着虚网的不断加入，有一个轻微下滑的过程，最终稳定在0.89左右，而当引入节点占用率反馈机制，并取Ooccupy为0.75时，虚网接收率的一直稳定维持在0.91左右，这说明随着虚网的加入，节点占有率反馈机制很好地分散了节点负载压力，有效缓解了资源瓶颈的产生。但是，若取Ooccupy为0.5，可以看出虚网接收率明顯较低，且有一个明显的下滑过程。经过分析，这是由于Ooccupy系数取得过小，映射算法过于追求将节点分散映射，而导致将底层物理网资源碎片化，从而大幅降低映射成功率。这一现象在虚网请求数量较多的时候尤为明显。
图5显示各映射算法在虚网链路带宽最大值Bw，max从10增加到90时对算法运行时间的影响.当Bw，max小于30时，底层物理链路资源充足，所有链路映射几乎都是一次成功，所以时间很短，但随着虚网链路继续增加，虽然总体趋势都是映射时间大幅增加，但是相比于隐藏跳数算法[14]、基于网络拓扑结构[1516]的映射算法、k短路径的映射算法[11]等其他算法，基于占有率反馈的映射算法在Bw，max在50到70之间的映射时间明显较短，在这一阶段，虽然链路资源已经相对不足，但所有映射成功的链路基本都是在前几次映射中就成功的，所以本文提出的算法耗时较短。
图6显示各映射算法的物理节点CPU利用率随时间窗增加的变化情况.从图6中看出各个算法的底层物理节点利用率随着每个时间窗中虚网请求的到来而不断上升，并最终趋于稳定。其中基于就近原则的映射算法[10]的节点CPU利用率最高，基于占有率反馈的映射算法次之，相较于前者，基于占有率反馈的映射在优化目标上牺牲了部分节点资源利用率以换取物理节点的负载平衡。基于网络拓扑结构的映射算法[1516]和普通的k短路径映射算法[11]相对于以上两种算法的节点CPU利用率则更低。 3 結束语
本文分析了传统映射算法的特点和可能存在的缺陷，提出了基于占有率反馈的虚拟网络资源映射方法，详细介绍了该算法的主要流程和改进的技术特点，并在仿真实验中给出了该方法的映射性能的展示。本文所提出的算法在节点映射阶段，在追求节点CPU资源的同时，创新性地考虑了节点的负载平衡，在基于就近原则的虚网映射算法的基础上，引入节点负载平衡的反馈机制，从而引导各个虚网请求更加均匀地映射到底层物理网络中，避免了物理网络中的核心节点资源被过早耗尽。在链路映射阶段，本算法在k短路径算法机制中引入了当前链路资源占有率作为评价参考标准，这样做可以尽可能均匀地分散链路压力，同时在检验链路资源是否满足虚网请求的过程中，由于优先选中的链路资源占有率低，剩余资源较多，算法映射成功率高，耗时更短，虚拟网络映射的效率得到了极大提高。
参考文献
References
[1] Lu J，Turner J.Efficient mapping of virtual networks onto a shared substrate[J].Washington University in St Louis，2006，35：24552462
[2] Zhu Y，Ammar M.Algorithms for assigning substrate network resources to virtual network components[C]∥Proceedings of 25th IEEE International Conference on Computer Communications，2006：112
[3] Chen X H，Li C Z，Jiang Y L.A feedback control approach for energy efficient virtual network embedding[J].Computer Communications，2016，80（15）：1632
[4] Hu X B，Wang M，Hu D，et al.A ripplespreading algorithm for the k shortest paths problem[C]∥The 3rd Global Congress on Intelligent Systems，2012：202208
[5] Ciciriello P，Mottola L，Picco G P.Efficient routing from multiple sources to multiple sinks in wireless sensor networks[C]∥Proceedings of 4th European Conference on Wireless Sensor Networks，2007：3450
[6] Kareche S，Ductor S，Guessoum Z，et al.A new robust heuristic for assigning substrate network resources to virtual networks[C]∥International Conference on Advanced Networking Distributed Systems and Applications，2014：4752
[7] Fan J L，Ammar M H.Dynamic topology configuration in service overlay networks：A study of reconfiguration policies[C]∥Proceedings of 25th IEEE International Conference on Computer Communications，2006：112
[8] Wei X H，Li H L，Yang K，et al.Topology aware partial virtual cluster mapping algorithm on shared distributed infrastructures[C]∥IEEE Transactions on Parallel and Distributed Systems，2014，25（10）：27212730
[9] Cai Z P，Liu F，Xiao N，et al.Virtual network embedding for evolving networks[C]∥IEEE Global Telecommunications Conference，2010：15
[10] Liu J，Huang T，Chen J Y，et al.A new algorithm based on the proximity principle for the virtual networking embedding problem[J].Journal of Zhejiang University（Science C），2011，12（11）：910918
[11] Wang F，Man Y，Man L C.Intelligent optimization approach for the k shortest paths problem based on genetic algorithm[C]∥10th International Conference on Natural Computation，2014：219224
[12] Gonzlez A，Barra E，Beghelli A，et al.A subgraph mappingbased algorithm for virtual network allocation over flexible grid networks[C]∥17th International Conference on Transparent Optical Network，2015：14
[13] Zegura E W，Calvert K L，Bhattacharjee S.How to model an internetwork[C]∥Proc 15th IEEE International Conference on Computer Communications，1996：594602
[14] Botero J F，Hesselbach X，Fischer A，et al.Optimal mapping of virtual ne tworks with hidden hops[J].Telecommunication Systems，2012，51（4）：273282
[15] Dhanapala D C，Jayasumana A P.Topology preserving maps extracting layout maps of wireless sensor networks from virtual coordinates[J].IEEE/ACM Transactions on Networking，2014，22（3）：784797
[16] Wang Z M，Wu J X，Wang Y，et al.Survivable virtual network mapping using optimal back up topology in virtualized SDN[J].China Communications，2014，11（2）：2637