基于节点可靠性感知和共享路径保护的虚拟网映射算法研究

刘光远，安秀芳，苏森

（1. 石家庄铁道大学信息科学与技术学院，河北 石家庄 050043；2. 北京邮电大学网络与交换技术国家重点实验室，北京100876）

基于节点可靠性感知和共享路径保护的虚拟网映射算法研究

刘光远1，安秀芳1，苏森2

（1. 石家庄铁道大学信息科学与技术学院，河北 石家庄 050043；2. 北京邮电大学网络与交换技术国家重点实验室，北京100876）

网络虚拟化技术为目前的网络架构提供了一种有效的扩展手段。近年来，底层网络基础设施失效事件频发，因此如何提高虚拟网络的可靠性成为目前该领域一个研究热点。对在保证虚拟网络可靠性的同时如何最小化底层网络映射开销问题进行研究，设计了一个新的启发式算法对其进行求解。实验表明，相比其他算法，所提算法网络带宽资源开销更低。

网络虚拟化；虚拟网络映射；启发式

1 引言

目前，互联网应用在人们的日常生活中发挥了重要作用[1]，但是其固有的设计规则和多服务提供商的特征，使评估和部署新的网络应用变得越来越难。近年来，人们提出了网络虚拟化技术，用来解决“网络僵化”问题[2,3]。该技术允许多个异构的虚拟网络共享一个底层物理网络，因此得到了越来越多的应用，但是虚拟网络仍需面临不可预测的底层网络节点或链路失效问题，严重的会导致虚拟网络不再可用。

虚拟网络映射问题已被证明为 NP难题[4]，早期的虚拟网研究[5～7]以底层网络资源利用最优为目标，设计不同的启发式算法，但是均没有考虑底层网络节点或链路失效时虚拟网络的可靠性问题。在映射的过程中加入虚拟网络可靠性约束无疑使该问题变得更加复杂。由于提供虚拟网络可靠性保证需要消耗更多的底层网络资源，因此所设计的算法应该在虚拟网络可靠性和底层网络资源消耗之间做一个权衡。文献[8～10]基于完全冗余机制对底层链路或节点失效进行了保护，但是资源使用效率还有待提高。本文提出了一个新的可靠虚拟网络映射算法RVNM，目的是在保证虚拟网络可靠性的同时最小化底层网络资源开销。在节点映射阶段，该方法不预留底层网络保护资源，将底层物理节点按照可靠性和资源负载平衡综合进行评估并排序，然后将虚拟节点映射到具有高评估值的底层物理节点上，实验表明该机制可以大大提高虚拟节点的抗毁性。在链路映射阶段，本文设计了一个新的链路映射机制，该机制基于共享路径保护策略。实验表明，该机制可在底层网络带宽使用方面接近最优。

2 相关工作

由于虚拟节点和虚拟链路的约束限制，虚拟网络映射问题已被证明为NP难题。Yu等[5]重新对底层网络进行设计，通过路径分裂和路径迁移机制使映射问题简化。Chowdhury等[6]考虑虚拟节点位置需求，为该问题建立一个混合线性规划模型，并利用线性松弛技术对其进行求解。Lischka等[7]基于子图同构理论提出了一种虚拟网映射算法以提高虚拟网络请求接受率。CHENG等[11]基于 PageRank理论提出了一种拓扑感知的虚拟网络映射算法，该算法提高了底层网络运营商的收益。尽管如此，以上研究主要将目光集中在底层网络资源的高效利用上，忽视了由于底层网络节点和链路失效带来的虚拟网络可靠性保护问题，因此，虚拟网络在底层资源失效后无法快速得到恢复，可能造成严重的经济损失。

近年来，有关可靠虚拟网络映射的相关研究逐渐增多。针对底层网络单链路失效情境，Rahman等[8]基于快速重路由策略，提出了一种1∶1确定性后备链路恢复机制，该机制在考虑最大化长期收益的同时尽可能最小化长期惩罚代价，但底层网络带宽使用效率较低。针对相似的问题情境，Chen等[9]基于路径共享机制提出一种主动链路保护方法，该方法所消耗的底层网络带宽比文献[8]低，但还有进一步优化的空间，此外该论文仅考虑了链路保护的情形而忽略了节点可靠性保护问题。针对底层节点失效情境，Yeow等[10]提出冗余资源共享池的方法，该方法可以达到n：k的冗余保护，但是该方法仍旧消耗了许多底层网络保护资源。事实上，在真实的网络中，底层网络节点失效的可行性很小，所以没有必要为它们预留那么多的底层保护资源。因此，本文提出了一个新的节点映射机制，该机制在不预留底层网络保护资源的情况下仍能提高虚拟节点的抗毁性，而且本文所提出的链路映射算法，相比文献[8,9]算法，在底层网络带宽资源使用方面接近最优。本文的研究对资源有限的底层网络来说有重要意义。

3 问题描述

3.1 底层网络

本文采用文献[1]给出的虚拟网络映射模型描述。底层物理网络拓扑可用带权无向图表示，其中，N和E分别表示底层物理网ss节点和链路的集合，和分别表示物理网节点的计算能力和链路带宽。底层物理网络可以是电信网络或者数据中心网络资源。图1(a)给出了一个底层物理网络拓扑实例，节点附近方框中的数字表示可用的计算资源，链路附近的数字表示可用的带宽资源。

图1 虚拟网络映射实例

3.2 虚拟网络请求

3.3 带有可靠性保护需求的虚拟网络映射问题

对于可靠的虚拟网络节点映射，由于本文的目标是尽可能减少底层网络资源消耗，所以本文没有设计基于预留底层保护资源的映射方法，而是设计了不预留底层网络资源，提高虚拟节点抗毁性的虚拟节点映射方法。对于可靠的虚拟链路映射，在完成底层网络基本虚拟链路映射以后，需要针对底层链路失效情境，为每个虚拟链路选择保护路径。给定一个虚拟链路euv，首先，应该保证主链路和相应保护链路不共享任何底层的物理链路或节点。直观上说，本文可以简单采用冗余机制选取2条底层不相交的路径进行映射，但是这个方法会浪费大量的底层网络资源。事实上，由于链路保护资源存在共享使用的可能性，所以保护路径不一定必须预留和主路径相等的带宽资源。通常情况下，会被设置为2条可共享保护路径的主路径带宽的最大值，而不是它们2个带宽之和。本文对简单的共享路径保护机制进行改进，其带宽消耗大大低于现有算法。值得注意的是，相关研究表明单链路失效数量占所有失效数量的70%[2,3]，所以本文主要针对单链路失效保护问题进行研究。

3.4 目标

本文设计了基于底层网络资源约束的在线可靠虚拟网络映射算法。主要目标是在保证虚拟网络可靠性的同时最小化底层网路资源开销。因为更少的资源开销表示底层网络可以节省更多资源以用于接受更多的虚拟网络请求。下面给出后面实验中用到的性能参数及说明，包括平均网络带宽消耗、长期带宽资源利用率、虚拟网络请求接受率和长期收益开销比（）。

1)平均网络带宽消耗定义为

其中，BW表示底层网络带宽消耗。

2)长期带宽资源利用率定义为

其中，RBW表示预留的保护带宽资源，PBW表示主带宽资源。

3)参考文献[3,4]的工作，虚拟网络请求接受率被定义为

其中，VNR表示虚拟网络请求， VNRa表示底层网络成功接受了虚拟网络请求。

4）长期收益开销比通常表示资源使用的效率，被定义为

4 RVNM启发式算法

本节对本文设计的可靠虚拟网络映射算法进行描述。该算法包括底层节点可靠性感知的节点映射机制和优化共享路径保护链路映射机制。

4.1 抗毁的虚拟网络节点映射机制

该算法首先基于底层节点先前的失效次数对底层物理节点进行可靠性评估，失效次数越多表明这个底层节点的可靠性越低。除此之外，算法还考虑了节点负载状态，因为节点hot-spot问题会导致虚拟网络请求拒绝数量的增加。而且，当底层hot-spot节点失效后，被影响的虚拟网络数量通常要多于其他失效节点所带来的影响。所以，节点映射算法综合考虑了底层节点可靠性和资源使用负载平衡这2个方面。因此本文给出如下定义

其中，FT(ns)表示节点 ns∈Ns的失效次数，PR(ns)表示节点 ns上已使用资源的百分比。值得注意的是，这里所说的节点资源包括 CPU能力和与节点ns相连的所有链路带宽资源。k表示节点ns上已经映射的虚拟网络的数量。

在虚拟网络节点映射阶段，算法首先计算每个底层网络节点的R(ns)值，并对其进行降序排列。然后将虚拟节点依次映射到具有高 R(ns)值的底层网络节点上，且该节点必须满足虚拟节点 CPU能力和链路能力需求。

4.2 优化共享保护虚拟网络链路映射机制

如 3.1节所述，将虚拟节点全部映射到底层物理节点后，RVNM需要为每个虚拟链路选择一个底层主路径进行映射。但是即使虚拟节点已经固定，虚拟链路最优映射问题仍是 NP难的。因此，为了简单起见，本文工作集中于底层网络不支持路径分裂的情形，通过最短路径算法找到最小带宽消耗（最小跳数）的主路径。本文的工作成果也可应用于其他情境，仅需要底层网络支持路径分裂即可。

由于本文考虑的是底层单链路失效的虚拟网络可靠性保护问题，所以为主路径预留的保护路径资源有可能实现共享。如果它们的保护路径占用同样的链路，则必须保证这2个保护路径对应的主路径不相交。

算法的最终目标是要找到最小化底层链路映射消耗的映射方案，即满足的主链路和保护链路的映射方案。

链路映射算法的主程序如算法1所示。S 表示最终的链路映射结果。如果没有可用的映射方案，算法返回NULL。

算法中用到的变量说明如下。

L：表示所有的底层链路集合。

BW：表示链路j上的带宽总能力。

Cj：表示链路j 上的可用带宽能力。

pj：表示链路j上所有主带宽使用资源。

rj：表示链路j上所有保护带宽使用资源。

pi：承载虚拟链路 i 的主路径。

ri：承载虚拟链路 i 的保护路径。

M：迭代限制次数。

cj：表示计算最小带宽消耗。

算法1主路径和保护路径选择策略

步骤1按照式(6)计算最小带宽消耗对应的主路径pi；如果pi存在，则执行步骤2。

否则，拒绝映射当前虚拟网络请求，算法返回NULL。

步骤2如果Tgt;M，执行步骤6。

否则，固定主路径pi、按照式(7)计算最小消耗对应的保护路径ri。

如果ri存在，则执行步骤3。

否则，执行步骤6。

步骤3计算当前主路径pi和保护路径ri资源消耗之和C。

步骤4固定保护路径ri，按照式(8)重新计算新的最小花费对应的主路径

否则，执行步骤6。

如果C*＜C,则且返回执行步骤2。

否则，执行步骤 6。

步骤6如果S=NULL，算法返回NULL。

否则，按照方案S更新所有的链资源分配并将结果返回。

算法中变量T和S初始化分别被设置为1和NULL。式(6)表示一个计算链路消耗函数，链路存在更多空闲资源表示其链路消耗更低。此外，如果主路径占用这些链路，则底层链路资源消耗会更平均，更能达到负载均衡的目的。式(7)中表示链路j上预留的保护资源需求，假设j∈ri,∀n∈L}，其中，表示虚拟链路的集合，该集合中元素的主路径为n，保护路径为j。容易看出，在已经分配了保护路径的链路上分配新的保护路径会占被认为更低的链路消耗，从而使保护资源利用率提高。在式(9)中，ε表示一个极小门限值（例如ε=10−3），表示链路 l上的保护资源需求。其中，表示虚拟链路的集合，该集合中元素的主路径为 n，保护路径为l。

为了更好地说明算法，现举一实例，在某时刻，需要映射虚拟链路L，按照RVNM算法执行流程。首先通过最短路径算法为该虚拟链路选择底层网络映射的主路径和保护路径。然后将保护路径固定，重新计算一个新的主路径。如果这个新的主路径可以使链路使用总资源消耗更少（按照算法 1中的公式计算，实质为可以实现保护链路共享，从而降低资源消耗），则保留并更新现有的链路映射方案。接着再固定主路径，按照类似的思路重新计算保护路径以使带宽资源使用更优（按照算法和计算公式进行执行，由于每个阶段都对所有可能的映射方案进行了比较，因此通过迭代可以得到全局最优解，即最优带宽资源消耗值）。当新的结果比先前结果差或者到达了限定的迭代次数（由于迭代次数或时间的限制，该结果接近最优值），重映射过程就停止。

5 性能评估

本节首先对模拟实验设置进行了描述，然后给出了实验数据和分析评估结果。

5.1 实验设置

为了验证RVNM的有效性，在先前工作开发的虚拟网络映射模拟平台上[11]对算法进行了测试。与早期工作[11～14]相似，底层网络拓扑由GT-ITM[15]生成，包含100个节点和500条链路。底层网络的节点 CPU能力和链路带宽能力为40～90均匀分布。虚拟节点个数服从 2～7均匀分布。虚拟节点的CPU能力需求为0～15均匀分布，带宽能力需求在0～40。此外，虚拟网络请求的到达频率服从每100个时间单位到达率为4的泊松分布。虚拟网络的平均生存时间为500个时间单位。模拟实验共运行大约50 000个时间单位，在这期间大约有2 500个虚拟网络请求。实验中算法迭代限制参数M设为6。

实验中，本文比较了许多参数指标，包括式(1)中定义的平均网络带宽花费、式(2)定义的长期带宽资源利用率、式(3)定义的虚拟网络请求接受率、式(4)定义的长期收益开销比和算法成功接受一个虚拟网络请求的平均时间花费。

实验中被比较的算法如表1所示，且所有算法都采用相同的输入。实验硬件平台配置为Intel 4.0 GHz内核CPU、8 GB内存、1 TB硬盘,Linux OS 2.8。

表1 比较的算法

5.2 实验结果及分析

由于采用了新的虚拟网络节点映射策略，实验表明，在不预留底层网络资源的情况下，RVNM提高了虚拟网络节点的抗毁性，其他2个算法仅考虑了链路保护而忽略了节点保护。此外，算法的收益和花费是本文工作主要考虑的因素。下面给出具体的实验结果和分析。

1)RVNM相比其他2个算法，大大降低了底层网络带宽消耗

图2和图3分别给出了3个算法的网络带宽消耗和带宽资源利用率的实验数据结果。HYBIRD算法由于采用确定性路径保护方法，其带宽资源消耗明显高于其他2个基于共享路径保护的算法，所以在图3中只比较了另2种算法。相比PARDALIS，RVNM明显节省了网络带宽资源，如图3所示，其保护资源使用率比PARDALIS 平均降低了10.7%，原因是RVNM算法采用了优化共享链路映射机制，更多地保护带宽能够被共享，所以底层网络带宽能够得到更好的利用。

图2 平均网络资源消耗

图3 长期带宽资源利用率

2)RVNM 相比其他算法能获得更高的虚拟网络请求接受率和长期收益开销比

如图4所示，RVNM算法的虚拟网络请求接受率高于PARDALIS和HYBRID算法，结果平均分别高出9.6% 和 18.3%。这是因为RVNM算法更好地节省了网络带宽资源，从而使更多的空闲资源被用于后续的虚拟网络请求。

图4 虚拟网络请求接受率

如图5所示，本文提出的算法由最少的资源带宽消耗，获得了最好的收益开销比，从而证明了网络资源使用的有效性。HYBRID算法由于无视带宽共享获得了最差的比较结果。

图5 长期收益开销比

3)RVNM 算法在执行时间和资源消耗之间做一平衡

图6描述了各个算法成功映射一个虚拟网络请求平均所花费的时间。RVNM的执行结果高于其他2个算法，这主要是因为节点可靠性计算和优化路径的选择，但1.8 s的时间复杂度是可以满足在线虚拟网络请求的。更重要的是，相比 PARDALIS和HYBRID算法，RVNM算法能提高虚拟节点的抗毁性而不用预留底层保护资源，同时在网络链路映射开销上分别降低了10%和19%左右，为底层运营商节省了更多的宝贵资源。

图6 一个虚拟请求的平均完成时间

6 结束语

本文研究了可靠的虚拟网络映射问题，针对单链路失效情境提出了一个新的启发式算法RVNM。该算法通过节点可靠性感知策略，在不预留底层保护资源的情况下提高了虚拟节点的抗毁性。此外，算法设计的优化共享保护链路机制能最小化底层网络带宽消耗。实验表明，该算法是一种有效的可靠虚拟网络映射算法。今后的工作将进一步研究跨域虚拟网络映射可靠性问题。

[1]MEEKER M. Internet Trends 2016[EB/OL].http://www. kpcb.com/internet-trends,2016-06-01.

[2]CHOWDHURY N M M K,BOUTABA R. Network virtualization:state of the art and research challenges[J]. Communications Magazine,IEEE,2009,47(7): 20-26.

[3]SU S,ZHANG Z,LIU A X,et al. Energy-aware virtual network embedding[J]. IEEE/ACM Transactions on Networking,2014,22(5):1607-1620.

[4]肖蔼玲,王颖,孟洛明,等. 基于知识描述和遗传算法的跨域虚拟网络映射[J]. 软件学报,2014,25(10): 2189-2205.XIAO A L,WANG Y,MENG L M,et al. Knowledge description and genetic algorithm based multi-domain virtual network embedding [J].Journal of Software,2014,25(10): 2189-2205.

[5]YU M,YI Y,REXFORD J,et al. Rethinking virtual network embed-ding: substrate support for path splitting and migration[J]. ACM Sigcomm Computer Communication Review,2008,38(2): 17-29.

[6]CHOWDHURY M,RAHMAN M R,BOUTABA R. ViNEYard:virtual network embedding algorithms with coordinated node and link mapping[J]. IEEE Transactions on Networking,2012,20(1):206-219 .

[7]LISCHKA J,KARL H. A virtual network mapping algorithm based on subgraph isomorphism detection[C]//The 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures. c2009: 81-88.

[8]RAHMAN M,AIB I,BOUTABA R. SVNE: survivable virtual network embedding algorithms for network virtualization[J]. IEEE Transactions on Network and Service Management,2014,10 (2): 105-118.

[9]CHEN Y,LI J,WO T,et al. Resilient virtual network service provision in network virtualization environments[C]//IEEE ICPADS. c2010: 51-58.

[10]YEOW W L,WESTPHAL C,KOZAT U. Designing and embedding reliable virtual infrastructures[J]. ACM Sigcomm Computer Communication Review,2011,41(2): 57-64.

[11]CHENG X,SU S,ZHANG Z,et al. Virtual network embedding through topology-aware node ranking[J]. ACM Sigcomm Computer Communication Review,2011,41(2): 39-47.

[12]CHENG X,SU S,ZHANG Z,et al. Virtual network embedding through topology awareness and optimization[J]. Elsevier Computer Networks,2012,56(6): 1797-1813.

[13]SU S,CHENG X,ZHANG Z,et al. Virtual network embedding with survivable routing[J]. Journal of Internet Technology,2014,14(5):741-750.

[14]刘光远,双锴,苏森. 区分服务 QoP的可生存虚拟网络映射算法研究[J]. 通信学报,2013,34(12):79-84.LIU G Y,SHUANG K,SU S. Survivable virtual network mapping with differentiated services QoP[J]. Journal on Communications,2013,34(12):79-84.

[15]ZEGURA E W,CALVERT K L,BHATTACHARJEE S. How to model an Internet work[C]//IEEE Infocom,c1996: 594-602.

Virtual network mapping algorithm with node reliability awareness and shared-path protection

LIU Guang-yuan1,AN Xiu-fang1,SU Sen2

(1.School of Information Science and Technology,Shijiazhuang Tiedao University,Shijiazhuang 050043,China;2. State Key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications,Beijing 100876,China)

Network virtualization has been proposed as a promising way for expanding the network architecture. However,how to provide reliable VN against substrate infrastructure failures has become an increasingly important issue. Meanwhile the substrate network resource cost should be minimized under VN reliability guarantees to maximize the revenue for the infrastructure providers (InP). A novel heuristic VN mapping algorithm was presented. Simulation results show that proposed algorithm can gain near optimal network bandwidth usage compared to the previous algorithms.

network virtualization,virtual network mapping,heuristic

s:The National Natural Science Foundation of China (No.61170274,No.61373160),Colleges and Universities in Hebei Province Science and Technology Research Fund (No.QN2016270),Undergraduate Training Programs for Innovation and Entrepreneurship (No.201510107098)

TP393.1

A

2015-10-21；

2016-06-13

国家自然科学基金资助项目（No.61170274,No.61373160）；河北省高等学校科学技术研究基金资助项目（No.QN2016270）；大学生创新创业基金资助项目（No.201510107098）

10.11959/j.issn.1000-436x.2016155

刘光远（1981-），男，河北石家庄人，博士，石家庄铁道大学讲师，主要研究方向为下一代互联网与云计算技术。

安秀芳（1993-），女，河北沧州人，主要研究方向为云计算技术。

苏森（1971-），男，山东菏泽人，北京邮电大学教授、博士生导师，主要研究方向为服务计算、云计算、大数据处理。