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

《基于节点可靠性感知和共享路径保护的虚拟网映射算法研究-刘光远.pdf》由会员分享，可在线阅读，更多相关《基于节点可靠性感知和共享路径保护的虚拟网映射算法研究-刘光远.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第37卷第8期2016年8月通信学报Journal on Communications、b137 NO8August 2016doi：1011959jissn1000-436x2016155基于节点可靠性感知和共享路径保护的虚拟网映射算法研究刘光远1，安秀芳1，苏森2(1石家庄铁道大学信息科学与技术学院，河北石家庄050043；2北京邮电大学网络与交换技术国家重点实验室，北京100876)摘要：网络虚拟化技术为目前的网络架构提供了一种有效的扩展手段。近年来，底层网络基础设施失效事件频发，因此如何提高虚拟网络的可靠性成为目前该领域一个研究热点。对在保证虚拟网络可靠性的同时如何最小化底层网络映射开

2、销问题进行研究，设计了一个新的启发式算法对其进行求解。实验表明，相比其他算法，所提算法网络带宽资源开销更低。关键词：网络虚拟化虚拟网络映射；启发式中图分类号：TP3931 文献标识码：AVirtual network mapping algorithm with nodereliability awareness and shared-path protecfi(nessan rotecuon-LIU Guangyuanl，AN Xiufan91，SU Sen2(1School ofInformation Science and Technology,Shijiazhuang Tiedao U

3、niversity,Shijiazhuang 050043，China；2State Key Laboratory ofNetworking and Switching Technology,Beijing Univemity ofPosts and Telecommunications，Beijing 100876，China)Abstract：Network virtualization has been proposed as a promising way for expanding the network architectureHowever,how to provide reli

4、able VN against substrate infrastructure failures has become an increasingly important issueMeanwhilethe substrate network resource cost should be minimized under VN reliability guarantees to maximize the rever!ue for the infrastructure providers(InP)A novel heuristic VN mapping algorithm Was presen

5、tedSimulation results show that proposedalgorithm can gain near optimal network bandwidth usage compared to the previous algorithmsKey words：network virtualization，virtual network mapping，heuristic1引言目前，互联网应用在人们的日常生活中发挥了重要作用【l J，但是其固有的设计规则和多服务提供商的特征，使评估和部署新的网络应用变得越来越难。近年来，人们提出了网络虚拟化技术，用来解决“网络僵化”问题【2

6、3J。该技术允许多个异构的虚拟网络共享一个底层物理网络，因此得到了越来越多的应用，但是虚拟网络仍需面临不可预测的底层网络节点或链路失效问题，严重的会导致虚拟网络不再可用。虚拟网络映射问题已被证明为NP难题【4J，早期的虚拟网研究【57】以底层网络资源利用最优为目标，设计不同的启发式算法，但是均没有考虑底层网络节点或链路失效时虚拟网络的可靠性问题。在映射的过程中加入虚拟网络可靠性约束无疑使该问题变得更加复杂。由于提供虚拟网络可靠性保证需要消耗更多的底层网络资源，因此所设计的算法应该在虚拟网络可靠性和底层网络资源消耗之间做一个权衡。文献810基于完全冗余机制对底层链路或节点失效进行了保护，但是资源

7、使用效率还有待提高。本文提出了一个新的可靠虚拟网络映射收稿日期：20151021；修回日期：20160613基金项目：国家自然科学基金资助项目(No61170274，No61373160)；河北省高等学校科学技术研究基金资助项目(NoQN2016270)；大学生创新创业基金资助项目(No201510107098)Foundation Items：The National Natural Science Foundation ofChina(No61170274，No61373160)，Colleges and Universities inHebei Province Science and

8、Technology Research Fund(NoQN20 1 6270)，Undergraduate Training Programs for Innovation andEntrepreneurship(No201510107098)万方数据通信学报 第37卷算法RVNM，目的是在保证虚拟网络可靠性的同时最小化底层网络资源开销。在节点映射阶段，该方法不预留底层网络保护资源，将底层物理节点按照可靠性和资源负载平衡综合进行评估并排序，然后将虚拟节点映射到具有高评估值的底层物理节点上，实验表明该机制可以大大提高虚拟节点的抗毁性。在链路映射阶段，本文设计了一个新的链路映射机制，该机制基于共享

9、路径保护策略。实验表明，该机制可在底层网络带宽使用方面接近最优。2相关工作由于虚拟节点和虚拟链路的约束限制，虚拟网络映射问题已被证明为NP难题。Yu等【5】重新对底层网络进行设计，通过路径分裂和路径迁移机制使映射问题简化。Chowdhury掣6J考虑虚拟节点位置需求，为该问题建立一个混合线性规划模型，并利用线性松弛技术对其进行求解。Lischka等【7J基于子图同构理论提出了一种虚拟网映射算法以提高虚拟网络请求接受率。CHENG等【ll】基于PageRank理论提出了一种拓扑感知的虚拟网络映射算法，该算法提高了底层网络运营商的收益。尽管如此，以上研究主要将目光集中在底层网络资源的高效利用上，忽

10、视了由于底层网络节点和链路失效带来的虚拟网络可靠性保护问题，因此，虚拟网络在底层资源失效后无法快速得到恢复，可能造成严重的经济损失。近年来，有关可靠虚拟网络映射的相关研究逐渐增多。针对底层网络单链路失效情境，Rahman等【8J基于快速重路由策略，提出了一种l：1确定性后备链路恢复机制，该机制在考虑最大化长期收益的同时尽可能最小化长期惩罚代价，但底层网络带宽使用效率较低。针对相似的问题情境，Chen等一1基于路径共享机制提出一种主动链路保护方法，该方法所消耗的底层网络带宽比文献8】低，但还有进一步优化的空间，此外该论文仅考虑了链路保护的情形而忽略了节点可靠性保护问题。针对底层节点失效情境，Ye

11、ow等【l 0J提出冗余资源共享池的方法，该方法可以达到胛：k的冗余保护，但是该方法仍旧消耗了许多底层网络保护资源。事实上，在真实的网络中，底层网络节点失效的可行性很小，所以没有必要为它们预留那么多的底层保护资源。因此，本文提出了一个新的节点映射机制，该机制在不预留底层网络保护资源的情况下仍能提高虚拟节点的抗毁性，而且本文所提出的链路映射算法，相比文献8，9】算法，在底层网络带宽资源使用方面接近最优。本文的研究对资源有限的底层网络来说有重要意义。3 问题描述31底层网络本文采用文献1给出的虚拟网络映射模型描述。底层物理网络拓扑可用带权无向图GS=(s，韪，G，q)表示，其中，s和最分别表示底层

12、物理网节点和链路的集合，C和d分别表示物理网节点的计算能力和链路带宽。底层物理网络可以是电信网络或者数据中心网络资源。图l(a)给出了一个底层物理网络拓扑实例，节点附近方框中的数字表示可用的计算资源，链路附近的数字表示可用的带宽资源。(a)底层网络拓扑圈 圈圈 囹(b)虚拟网络请求I回 回(c)虚拟网络请求2回32虚拟网络请求本文用类似的带权无向图Gv=(v，E，群，)来表示虚拟拓扑。其中，1，和巨，分别表示虚拟网节点和虚拟链路的集合，彤和分别表示虚拟节点能力和虚拟链路带宽资源需求。图1(b)和图1(c)分别表示2个虚拟网络请求实例。万方数据第8期 刘光远等：基于节点可靠性感知和共享路径保护的

13、虚拟网映射算法研究 5333带有可靠性保护需求的虚拟网络映射问题虚拟网络映射问题被定义为M：Gv(v，E)jG(M，最)，包括节点和链路映射这2个方面。图l(a)为2个虚拟网络请求给出了一种可行的映射方案。如图1所示，第1个虚拟网络请求的节点映射结果为(口鲥，6jE cj功，链路映射结果为(口，6)一口，曰)，(a，c)一似，D，(6，c)一，C，D)。第2个虚拟网请求的节点映射和链路映射结果分别为(出刃，Hc产四和(Z P卜徊，C)，力一p，司)。对于可靠的虚拟网络节点映射，由于本文的目标是尽可能减少底层网络资源消耗，所以本文没有设计基于预留底层保护资源的映射方法，而是设计了不预留底层网络资

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

15、注意的是，相关研究表明单链路失效数量占所有失效数量的70【2，3J，所以本文主要针对单链路失效保护问题进行研究。34目标本文设计了基于底层网络资源约束的在线可靠虚拟网络映射算法。主要目标是在保证虚拟网络可靠性的同时最小化底层网路资源开销。因为更少的资源开销表示底层网络可以节省更多资源以用于接受更多的虚拟网络请求。下面给出后面实验中用到的性能参数及说明，包括平均网络带宽消耗、长期带宽资源利用率、虚拟网络请求接受率和长期D收益开销比(竺)。C1)平均网络带宽消耗定义为其中，BW表不底层网络带宽消耗。2)长期带宽资源利用率定义为丁咫形(f)limr一等一(2)PBW(t)t=O其中，RBW表示预留的

16、保护带宽资源，PBW表示主带宽资源。3)参考文献3，4的工作，虚拟网络请求接受率被定义为r佩(f)limr一号一 (3)rsR(t)t=0其中，VNR表示虚拟网络请求，VNRa表示底层网络成功接受了虚拟网络请求。4)长期收益开销比通常表示资源使用的效率，被定义为rR(f)limr一等L一 (4)c(f)4 RVNM启发式算法本节对本文设计的可靠虚拟网络映射算法进行描述。该算法包括底层节点可靠性感知的节点映射机制和优化共享路径保护链路映射机制。41抗毁的虚拟网络节点映射机制该算法首先基于底层节点先前的失效次数对底层物理节点进行可靠性评估，失效次数越多表明这个底层节点的可靠性越低。除此之外，算法还

17、考虑了节点负载状态，因为节点hotspot问题会导致虚拟网络请求拒绝数量的增加。而且，当底层hotspot节点失效后，被影响的虚拟网络数量通常要多于其他失效节点所带来的影响。所以，节点映射算法综合考虑了底层节点可靠性和资源使用负载平衡这2个方面。因此本文给出如下定义酬2而PR(万ns)k翠T 萋tg,FT(摇n8嚣焉嚣譬裂1 是，这里所说的节点资源包括CPU能力和与节点万方数据通信学报 第37卷，z。相连的所有链路带宽资源。k表示节点n。上已经映射的虚拟网络的数量。在虚拟网络节点映射阶段，算法首先计算每个底层网络节点的R(n。)值，并对其进行降序排列。然后将虚拟节点依次映射到具有高R(n。)值

18、的底层网络节点上，且该节点必须满足虚拟节点CPU能力和链路能力需求。42优化共享保护虚拟网络链路映射机制如31节所述，将虚拟节点全部映射到底层物理节点后，RVNM需要为每个虚拟链路选择一个底层主路径进行映射。但是即使虚拟节点已经固定，虚拟链路最优映射问题仍是NP难的。因此，为了简单起见，本文工作集中于底层网络不支持路径分裂的情形，通过最短路径算法找到最小带宽消耗(最小跳数)的主路径。本文的工作成果也可应用于其他情境，仅需要底层网络支持路径分裂即可。由于本文考虑的是底层单链路失效的虚拟网络可靠性保护问题，所以为主路径预留的保护路径资源有可能实现共享。如果它们的保护路径占用同样的链路，则必须保证这

19、2个保护路径对应的主路径不相交。算法的最终目标是要找到最小化底层链路映H射消耗的映射方案，即满足miny(n+，；)的主链 冒。路和保护链路的映射方案。链路映射算法的主程序如算法1所示。s表示最终的链路映射结果。如果没有可用的映射方案，算法返回NULL。算法中用到的变量说明如下。三：表示所有的底层链路集合。BW：表示链路，上的带宽总能力。G：表示链路i上的可用带宽能力。Pi：表示链路，上所有主带宽使用资源。n：表示链路，上所有保护带宽使用资源。P，：承载虚拟链路i的主路径。n：承载虚拟链路i的保护路径。坛迭代限制次数。c，：表示计算最小带宽消耗。算法1主路径和保护路径选择策略步骤1 按照式(6

20、)计算最小带宽消耗对应的主路径P，；如果Pf存在，则执行步骤2。否则，拒绝映射当前虚拟网络请求，算法返回NULL。步骤2如果丁M执行步骤6。否则，固定主路径Pi、按照式(7)计算最小消耗对应的保护路径m如果n存在，则执行步骤3。否则，执行步骤6。步骤3计算当前主路径P，和保护路径rf资源消耗之和C。步骤4 固定保护路径n，按照式(8)重新计算新的最小花费对应的主路径P：。如果P：存在，执行步骤5。否则，执行步骤6。步骤5计算当前主路径Pj和保护路径n消耗带宽资源之和C+。如果C+C，则s_(pj，)，T=T+I且返回执行步骤2。否则，执行步骤6。步骤6如果S=NULL，算法返回NULL。否则，

21、按照方案S更新所有的链资源分配并将结果返回。旷1芝，其他 【 B形foo， je Pi,Cj+ovj+旷1血，其他 。BW7、。旷仨嚣(6)(7)(8)c：占，i，。杉+V，e。巧 (9)。o。，其他算法中变量丁和S初始化分别被设置为1和NULL。式(6)表示一个计算链路消耗函数，链路存在更多空闲资源表示其链路消耗更低。此外，如果主路径占用这些链路，则底层链路资源消耗会更平均，更能达到负载均衡的目的。式(7)中v：表示链路，上预留的保护资源需求，v：=maxl v?I，假设l，VnL)，其中，v?表示虚拟链路的集合，该。 J集合中元素的主路径为行，保护路径为，。容易看出，万方数据第8期 刘光远

22、等：基于节点可靠性感知和共享路径保护的虚拟网映射算法研究 55在已经分配了保护路径的链路上分配新的保护路径会占被认为更低的链路消耗，从而使保护资源利用率提高。在式(9)中，表示一个极小门限值(例如e=10-3)，+表示链路，上的保护资源需求。v+=maxII，je P，Vne L，其中，表示虚拟链路的集合，该集合中元素的主路径为n，保护路径为，。为了更好地说明算法，现举一实例，在某时刻，需要映射虚拟链路，按照RVNM算法执行流程。首先通过最短路径算法为该虚拟链路选择底层网络映射的主路径和保护路径。然后将保护路径固定，重新计算一个新的主路径。如果这个新的主路径可以使链路使用总资源消耗更少(按照算

23、法1中的公式计算，实质为可以实现保护链路共享，从而降低资源消耗)，则保留并更新现有的链路映射方案。接着再固定主路径，按照类似的思路重新计算保护路径以使带宽资源使用更优(按照算法和计算公式进行执行，由于每个阶段都对所有可能的映射方案进行了比较，因此通过迭代可以得到全局最优解，即最优带宽资源消耗值)。当新的结果比先前结果差或者到达了限定的迭代次数(由于迭代次数或时间的限制，该结果接近最优值)，重映射过程就停止。5性能评估本节首先对模拟实验设置进行了描述，然后给出了实验数据和分析评估结果。51实验设置为了验证RVNM的有效性，在先前工作开发的虚拟网络映射模拟平台上1l】对算法进行了测试。与早期工作【

24、1114】相似，底层网络拓扑由GT_ITM1 51生成，包含100个节点和500条链路。底层网络的节点CPU能力和链路带宽能力为4090均匀分布。虚拟节点个数服从27均匀分布。虚拟节点的CPU能力需求为015均匀分布，带宽能力需求在040。此外，虚拟网络请求的到达频率服从每100个时间单位到达率为4的泊松分布。虚拟网络的平均生存时间为500个时间单位。模拟实验共运行大约50 000个时间单位，在这期间大约有2 500个虚拟网络请求。实验中算法迭代限制参数M设为6。实验中，本文比较了许多参数指标，包括式(1)中定义的平均网络带宽花费、式(2)定义的长期带宽资源利用率、式(3)定义的虚拟网络请求接

25、受率、式(4)定义的长期收益开销比和算法成功接受一个虚拟网络请求的平均时间花费。实验中被比较的算法如表1所示，且所有算法都采用相同的输入。实验硬件平台配置为Intel 40 GHz内核CPU、8 GB内存、l TB硬盘。Linux OS 28。表1 比较的算法算法 算法描述本文所提出的启发式算法文献9】提出的基于共享链路保护的可靠虚拟网络映射算法文献【8提出的确定性链路保护的可靠虚拟网络映射算法52实验结果及分析由于采用了新的虚拟网络节点映射策略，实验表明，在不预留底层网络资源的情况下，RVNM提高了虚拟网络节点的抗毁性，其他2个算法仅考虑了链路保护而忽略了节点保护。此外，算法的收益和花费是本

26、文工作主要考虑的因素。下面给出具体的实验结果和分析。1)RVNM相比其他2个算法，大大降低了底层网络带宽消耗图2和图3分别给出了3个算法的网络带宽消耗和带宽资源利用率的实验数据结果。HYBIRD算法由于采用确定性路径保护方法，其带宽资源消耗明显高于其他2个基于共享路径保护的算法，所以在图3中只比较了另2种算法。相比PARDALIS，RVNM明显节省了网络带宽资源，如图3所示，其保护资源使用率比PARDALIS平均降低了107，原因是RVNM算法采用了优化共享链路映射机制，更多地保护带宽能够被共享，所以底层网络带宽能够得到更好的利用。ll万方数据通信学报 第37卷图3 长期带宽资源利用率2)RV

27、NM相比其他算法能获得更高的虚拟网络请求接受率和长期收益开销比如图4所示，RVNM算法的虚拟网络请求接受率高于PARDALIS和HYBRID算法，结果平均分别高出96和183。这是因为RVNM算法更好地节省了网络带宽资源，从而使更多的空闲资源被用于后续的虚拟网络请求。图4虚拟网络请求接受率如图5所示，本文提出的算法由最少的资源带宽消耗，获得了最好的收益开销比，从而证明了网络资源使用的有效性。HYBRID算法由于无视带宽共享获得了最差的比较结果。时间(1 ooolt#间单位)图5长期收益开销比3)RVNM算法在执行时间和资源消耗之间做一平衡图6描述了各个算法成功映射一个虚拟网络请求平均所花费的时

28、间。RVNM的执行结果高于其他2个算法，这主要是因为节点可靠性计算和优化路径的选择，但18 S的时间复杂度是可以满足在线虚拟网络请求的。更重要的是，相比PARDALIS和HYBRID算法，RVNM算法能提高虚拟节点的抗毁性而不用预留底层保护资源，同时在网络链路映射开销上分别降低了10和19左右，为底层运营商节省了更多的宝贵资源。图6一个虚拟请求的平均完成时问6结束语本文研究了可靠的虚拟网络映射问题，针对单链路失效情境提出了一个新的启发式算法RVNM。该算法通过节点可靠性感知策略，在不预留底层保护资源的情况下提高了虚拟节点的抗毁性。此外，算法设计的优化共享保护链路机制能最小化底层网络带宽消耗。实

29、验表明，该算法是一种有效的可靠虚拟网络映射算法。今后的工作将进一步研究跨域虚拟网络映射可靠性问题。参考文献：1】MEEKER MInternet仉ndS 2016EBOLhttp：wwwkpebtomintemet-trends，2016-06-012CHOWDHURY N M M K，BOUTABA RNetwork virtualization：state of the art and research challengesJCommunications Magazine，IEEE，2009，47(7)：2026【3】 SU S，zHANG z，LIU A X，et a1Energy-aw

30、are virtual network em-bedd魄明IEEEACM Transactions On Networking,2014，22(5)：160716204】 肖蔼玲，王颖，孟洛明，等基于知识描述和遗传算法的跨域虚拟网络映射硼软件学报，2014，25(10)：21892205XIAO A L，WANG Y MENG L M，et a1Knowledge description andgenetic algorithm based multi-domain virtual network embedding册Journal ofSoftware，2014，25(10)：2189220

31、5【5】YU M，Y，REXFORD J，et a1Rethinking virtual network embed-万方数据第8期 刘光远等：基于节点可靠性感知和共享路径保护的虚拟网映射算法研究 57ding：substrate support for path splitting and migrationJ】ACM Sigcomm Computer Communication Review,2008，38(2)：1 7296】 CHOWDHURY M，R AndN M R BOUTABA&V心mYard：virtual network embedding algorithms with

32、coordinated node and linkmappingJIEEE Transactions on Networking，2012，20(1)：2062197LISCHKA J，KARL HA virtual network mapping algorithm based onsubgraph isomorphism detectionCThe 1st ACM Workshop on Vi卜tualized Infrastructure Systems and Architecturesc2009：8188【8】RAHMAN M，AIB I，BOUTABA RSVNE：survivab

33、le virtual networkembedding Mgorithms for network virtualizationJIEEE Transactionson Network and Service Management,2014，10(2)：105一1189】CHEN Y LI J，WO T，et a1Resilient virtual network service provision innetworkvirtualization environmentsCIEEE ICPADSc2010：5158【10YEOW W L，WESTPHAL C，KOZAT UDesigning

34、and embeddingreliable virtual infrastructuresJACM Sigcomm Computer Communication Review,201 1，4l(2)：57一“11】CHENG X，SU S，ZHANG z，et a1Vmual network embeddingthrough topologyaware node rankingJACM Sigeomm ComputerCommunication Review,201 l，41(2)：394712】CHENG X，SU S，ZHANG Z，et a1VLrtual network embeddi

35、ngthrough topology awareness and optimization叨Elsevier ComputerNetworks，2012，56(6)：1797181313】SU S，CHENG X，ZHANG z，et a1Virtual network embedding withsurvivable routingJJournal of Intemet Technology,2014，14(5)：74l一75014】刘光远，双锴，苏森区分服务Qoa的可生存虚拟网络映射算法研究叨通信学报，2013，34(12)：7984LIU G YSHUANG K，SU SSurvivab

36、le virtual network mappingwith differentiated services QoPJJournal on Communications，2013，34(12)：798415ZEGURA E W，CALVERT K L，BHATTACHARJEE SHow tomodel an Intemet workCIEEE lnfocom,c1996：594-602作者简介：20161557刘光远(1981)，男，河北石家庄人，博士，石家庄铁道大学讲师，主要研究方向为下一代互联网与云计算技术。安秀芳(1993)，女，河北沧卅1人，主要研究方向为云计算技术。苏森(1971)，男，山东菏泽人，北京邮电大学教授、博士生导师，主要研究方向为服务计算、云计算、大数据处理。万方数据