一种基于健壮型映射树的虚拟网络映射算法

蒋燕燕，杨龙祥，成聿伦

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

一种基于健壮型映射树的虚拟网络映射算法

蒋燕燕，杨龙祥，成聿伦

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

针对虚拟网络映射存在的资源开销大、虚拟网络请求接收率低等问题，文中提出了一种基于健壮型映射树的虚拟网络映射算法。该算法通过划分虚拟网络、估算物理节点资源、初始化映射树和比较启发式函数，实现对虚拟网络请求的映射。该算法的主要目的在于尽可能大地提高请求接收率，优化资源利用，同时增加映射收益。文中将该算法与传统的虚拟网络映射算法进行仿真相比，结果表明，该算法在虚拟网络映射接收率和平均收益方面优于传统虚拟网络映射算法，以及在映射较多的虚拟网络请求的同时减少了物理资源的使用。

网络虚拟化；映射树；接收率；资源利用率

0 引 言

近年来，网络虚拟化技术受到普遍关注,被视为构建未来网络的重要技术之一。利用网络虚拟化技术将未来网络划分为多个虚拟网络，这些虚拟网络共享同一个物理网络，从而完成虚拟网络请求。网络虚拟化主要问题是如何将虚拟网络映射到物理网络上，该过程称为VNE(Virtual Network Embedding)问题。由于应用场景、资源条件约束和动态在线请求等因素，使得虚拟网络映射问题变得难以解决，所以VNE问题是一个NP-hard问题[1]。

针对虚拟网络映射问题，VNE算法已有一些研究。这些算法根据映射过程大致可以分为两类：节点和链路同时映射、节点和链路分两步单独映射。文献[2]中提出了VNE-Least算法，使用贪婪算法进行节点映射，最短路径算法进行链路映射，由于假设物理资源是无限的，所以控制条件不足，无法用于实际场景中。文献[3]中提出给予分布式协作虚拟网络映射算法，将虚拟网络划分为若干个星型拓扑网络，采用基于多代理系统同时完成节点和链路映射，为保证算法性能，假设物理资源是无限的。文献[4]中提出支持对物理网络路径分割，但求解复杂，开销很大。文献[5]中采用蚁群算法VNE-AC，旨在减少虚拟网络请求的拒绝率，算法派出工蜂寻找最优路径，虽然减少了链路的利用率，但会引起部分链路发生拥塞现象。文献[6]中采用贪婪算法进行节点映射，路径分割进行链路映射，该方法容易造成部分节点过载。

通过以上分析，在实际应用场景中，物理网络资源不为无限可用，除了考虑算法效率外，还需考虑网络负载均衡，不能造成局部网络拥塞[7]。文中主要研究基于映射树拓扑同时完成节点和链路映射的虚拟网络映射算法VNE-RMT(Robust Mapping Tree)，算法主要分为四步：

(1)划分虚拟网络；

(2)选出候选物理节点；

(3)初始化映射树；

(4)选出最佳映射方案。

该研究的目的在于尽可能提高虚拟网络请求的接收率和减少物理资源的开销。

1 网络模型及映射问题描述

1.1 物理网络模型

物理网络用加权无向图GS=(NS,LS)表示，NS表示物理节点，LS表示物理链路。每个物理节点nS∈NS，C(nS)表示物理节点可用的CPU资源，memory(nS)表示物理节点的可用内存。每条物理链路lS(i,j)∈LS,lS(i,j)表示物理节点i和j之间的物理链路,B(lS(i,j))表示物理链路的可用带宽资源，u(lS(i,j))表示物理链路的成本、时延的均值。

1.2 虚拟网络模型

虚拟网络用加权无向图GV=(NV,LV)表示，NV表示虚拟节点，LV表示虚拟链路。每个虚拟节点nV∈NV，C(nV)表示网络请求对节点的CPU资源的约束,memory(nV)表示请求对节点的内存约束。每条虚拟链路lV(i,j)∈LV，lV(i,j)表示虚拟节点i和j之间的虚拟链路，B(lV(i,j))表示虚拟网络请求对链路的带宽约束，u(lV(i,j))表示请求对链路的成本、时延的均值约束。

1.3 映射问题描述

图1给出了虚拟网络映射到物理网络上的过程，包括节点映射和链路映射。

图1 虚拟网络映射示意图

2 评价指标

虚拟网络映射算法的目标是用尽可能少的物理资源获得最大的收益，而且为了保证服务质量，请求接收率也是网络映射的重要指标之一。因此，这里考虑的评价指标有：网络收益、映射成本、收益成本、收益成本比和请求接收率[8]。

(1)网络收益。

(1)

(2)映射成本。

(2)

式中，β表示CPU和带宽之间的均衡权值。

(3)收益成本比值。

(3)

式中，R/C的比值表示物理网络的资源利用率，可以直接反映基础设施提供商的利润。

(4)请求接收率。

虚拟网络的映射接收率表示为成功映射的虚拟网络请求数VNR-S(t)与该时间段内到达的虚拟网络请求总数VNR-A(t)的比值，即

(4)

3 算法描述

3.1 选择参数

物理网络节点nS的综合资源可以表示为：

(5)

同样，虚拟节点nV的综合资源可以表示为：

(6)

3.2 VNE-RMT算法描述

(1)划分虚拟网络。

把虚拟网络划分为多个小型虚拟网络[9]，计算每个小型虚拟网络中的每个虚拟节点的IR(nV)值，把具有最大综合资源的虚拟节点作为根节点root，与之相邻的虚拟节点按照IR(nV)值降序排列。

(2)选出候选物理节点。

计算物理网络中每个物理节点的综合资源IR(nS)。先估算物理网络承载虚拟网络请求的能力[10]。用矩阵Mat(i,j)表示每个虚拟节点的映射候选物理节点，i表示物理节点的数目，j表示虚拟节点的数目。

(7)

因此，这个步骤是处理物理节点能承载的虚拟节点。通过比较可用节点和请求节点的综合资源参数，选出每个虚拟节点的候选映射物理节点。如果虚拟节点j的Mat(i,j)<0，算法将把负值返回给请求的虚拟网络，将不为该节点进行映射分配物理节点。只要虚拟节点有一个候选物理节点，算法将保留该虚拟节点。

(3)初始化映射树。

如图2所示，在划分好的小型虚拟网络中，建立映射树TM。每个映射树的等级代表第j级虚拟节点分配，节点和树枝分别代表候选物理节点和节点间的链路[11-13]。虚拟网络中从源节点到目的节点的路径中的节点和链路的分配方式取决于启发式函数。启发式函数是一个有真实数值的函数，决定哪个节点作为最佳节点去生成映射树，直到所有节点完成分配。该映射树有n级，n为每个小型虚拟网络总虚拟节点的数目，每个虚拟节点的映射方案对应搜索树的每一级。映射树的节点表示候选物理节点，节点之间的树枝表示两节点间链路的映射方案。通过启发式函数实现从root节点到节点映射，该过程同时考虑了节点和链路的映射分配方案。在映射分配时，如果下一级节点没有可映射的物理节点，算法将回到上一级分配节点，从候选物理节点选出最佳节点。

图2 虚拟网络树形拓扑

(4)选择最佳映射方案。

通过估算资源能力，启发式函数为每个物理节点选出映射树的节点，物理节点nS启发式函数表示如下：

f(nS)=g(nS)+h(nS)

(8)

假设最小的f值表示构建方案的最佳节点。当发生回溯现象时，选择发生不能映射的最近一级的节点[14]。启发式函数的第一部分是：

g(nS)=(n-i)*2n-i，n=NV，i是当前虚拟节点

(9)

h(nS)=1/Mat(i,j)+1

(10)

其中，函数g表示现在节点和最末节点树叶之间的距离。最末节点树叶定义为最后一个被映射的虚拟节点，该节点下面不再有分支节点。启发式函数f可以用最快的速度完成搜索过程，完成所有节点和链路的映射，允许映射过程发生无法再映射情况时回溯到上一级节点。函数h是为现在的虚拟节点估算候选物理节点的能力。Mat(i,j)是一个整数值，表示每个虚拟节点的物理候选节点，假设没有约束条件的节点优于有约束条件的节点。

从式(9)和式(10)得到：

f(nS)=(n-i)*2n-i+1/Mat(i,j)+1

(11)

对当前虚拟节点，选择启发式函数f值最小的候选物理节点为映射树每一级的最佳候选节点。必须确认从一个物理节点到另一个物理节点间的路径链路满足请求所需的带宽。如果这样的路径存在，就进行下一个虚拟节点分配，否则算法将回溯到上一级节点，直到找到最佳分配方案。一旦路径找到，物理网络资源将被分配一段时间，用完后释放资源。当分配或释放资源发生时，将更新物理资源。

4 仿真与分析

文中使用GT-ITM拓扑生成器生成物理网络和虚拟网络请求[6]。物理网络是一个具有100个节点和约500条链路的初始拓扑，每对节点连接的概率是0.5，物理节点的CPU资源、内存资源和链路带宽资源都符合[50,100]的均匀分布，虚拟网络请求的到达强度符合100个时间单元平均到达4个的泊松分布。假定有10个虚拟网络请求的节点个数符合[2,10]的均匀分布。

把VNE-RMT算法与VNE-Least[2]、G-MCF[6]进行比较。对虚拟网络请求接收率、物理网络节点和链路资源的平均利用率和虚拟网络映射平均收益进行分析比较。仿真过程假设式(1)和(2)中的CPU与带宽影响相同，即设α=β=1。

图3的实验结果表明，VNE-RMT算法的虚拟网络请求接收率比其他两种算法高，随着时间的推移，稳定在0.74，这得益于预先对虚拟请求节点进行综合资源估算，避免了局部拥塞。

图3 虚拟网络请求接收率

图4的实验结果表明，与其他两种算法比较，VNE-RMT算法在映射较多的虚拟网络请求的同时使用较少的物理网络节点和链路资源。

图4 资源平均利用率

图5的实验结果表明，VNE-RMT算法在物理网络上的平均收益比其他两种算法有明显优势，随着时间的推移稳定在30左右。

图5 平均收益

5 结束语

网络虚拟化问题主要是有效的资源分配问题。文中使用基于健壮型映射树算法来同时完成节点和链路映射。该算法的主要目标是提高虚拟网络请求接收率和映射平均收益，且更高效地利用物理网络节点和链路资源。该算法将虚拟网络简化为映射树拓扑结构，使用启发式函数来确定资源分配方案，达到网络负载均衡。

随着网络规模的不断扩大，中心结构使得计算缓慢，造成严重时延。下一步研究工作将围绕应用多代理系统的虚拟网络映射算法展开。

[1]FischerA,BoteroJF,TillBH,etal.Virtualnetworkembedding:asurvey[J].IEEECommunicationsSurveys&Tutorials,2013,15(4):1888-1906.

[2]ZhuY,AmmarM.Algorithmsforassigningsubstratenetworkresourcestovirtualnetworkcomponents[C]//ProcofIEEEINFOCOM.[s.l.]:IEEE,2006:1-12.

[3]LouatiHW,ZeghlacheD.Adistributedvirtualnetworkmappingalgorithm[C]//ProcofICC’08.[s.l.]:IEEE,2008:5634-5640.

[4]ChowdhuryM,RahmanMR,BoutabaR.ViNEYard:virtualnetworkembeddingalgorithmswithcoordinatednodeandlinkmapping[J].IEEE/ACMTransactionsonNetworking,2012,20(1):206-219.

[5]FajjariI,SaadiNA,PujolleG,etal.VNE-AC:virtualnetworkembeddingalgorithmbasedonantcolonymetaheuristic[C]//ProcofICC.[s.l.]:IEEE,2011:1-6.

[6]YuM,YiY,RexfordJ,etal.Rethinkingvirtualnetworkembedding:substratesupportforpathsplittingandmigration[J].SIGCOMMComputCommunRev,2008,38(2):17-29.

[7] 朱 军，许 倩，易辉跃，等.节点删除法的虚拟网络映射算法[J]．安徽大学学报:自然科学版，2014,38(5):37-43.

[8] 朱 强，王慧强，冯光升，等.VNE-ABC:基于人工蜂群的网络虚拟化映射算法[J].北京工业大学学报，2014,40(1):68-73.

[9]DongZ.Astudyonvirtualnetworkdecomposingmappingalgorithmbasedonnetworkbalance[C]//Procoffourthinternationalconferenceoncomputationalandinformationsciences.[s.l.]:[s.n.],2012:880-883.

[10]DiH,YuH,AnandV,etal.Efficientonlinevirtualnetworkmappingusingresourceevaluation[J].JournalofNetworkandSystemsManagement,2012,20(4):468-488.

[11]HuangTao,LiuJiang,ChenJiangya,etal.Atopology-cognitivealgorithmframeworkforvirtualnetworkembeddingproblem[J].ChinaCommunications,2014(4):73-84.

[12]CuiHongyan,TangShaohua,HuangXu,etal.Anovelmethodofvirtualnetworkembeddingbasedontopologyconvergence-degree[C]//ProcofIEEEinternationalconferenceoncommunicationsworkshops.[s.l.]:IEEE,2013:246-250.

[13]ButtNF,ChowdhuryM,BoutabaR.Topologyawarenessandreoptimizationmechanismforvirtualnetworkembedding[J].Networking,2010,6091:27-39.

[14]LiWen,WuChunming,ChenJian,etal.Virtualnetworkmappingalgorithmwithrepeatablemappingoversubstratenodes[J].JournalofElectronicsandInformationTechnology,2011,33(4):908-914.

A Virtual Network Embedding Algorithm Based on Robust Mapping Tree

JIANG Yan-yan,YANG Long-xiang,CHENG Yu-lun

(College of Communication and Information Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

To overcome the high cost and low accepted rate faced by virtual network embedding,a virtual network embedding algorithm based on robust mapping tree is proposed.This algorithm realizes virtual network embedding through dividing the virtual network,estimation of substrate node resource,initialization of mapping tree and comparison of heuristic function.The objective of this algorithm is to maximize the accepted rate,optimize resource utilization and increase the average revenue.In this paper,the algorithm is compared with the traditional virtual network embedding algorithms.Simulation results show that the accepted rate and average revenue of virtual networks requests are increased,and the usage of substrate network resources is reduced as realizations of virtual network request are increased compared with the traditional virtual network embedding algorithms.

network virtualization;mapping tree;accepted rate;usage of resources

2015-05-11

2015-08-14

时间：2016-01-26

国家自然科学基金资助项目(61271237，61372124);国家“863”高技术发展计划项目(2013CB329104)

蒋燕燕(1991-)，女，硕士，研究方向为移动通信与无线技术;杨龙祥，教授,博士生导师，研究方向为移动无线通信系统和物联网。

http://www.cnki.net/kcms/detail/61.1450.TP.20160126.1520.036.html

TP301.6

A

1673-629X(2016)02-0069-04

10.3969/j.issn.1673-629X.2016.02.016