WDM光网络虚拟映射协同RWA算法研究

何 源，侯韶华

(南京邮电大学 电子科学与工程学院，江苏 南京 210003)

WDM光网络虚拟映射协同RWA算法研究

何 源，侯韶华

(南京邮电大学 电子科学与工程学院，江苏 南京 210003)

当前，物联网与云计算等产业的发展，使得波分复用(WDM)光网络地位越来越重要。在WDM光网络中的关键技术是网络虚拟化及路由与波长分配(RWA)。然而，性能优越的虚拟网络(VN)映射和RWA算法有众多约束条件，这使得目标求解成为了一个NP-hard问题，因而更多的研究是将其分为VN映射、RWA子问题进行研究。基于此，研究了将光网络虚拟化映射与RWA相结合的方案，并提出最小路由跳数以及最小波长平面的两种启发式算法。算法主要分析VN映射对路由及波长总数的需求。将这两种算法与将VN映射、RWA作为子问题研究的Two-Step方案进行对比，并进行性能仿真。仿真结果表明，提出的方案比Two-Step方案性能优越，同时自适应虚拟网络节点映射性能优于固定节点映射的性能。

波分复用；网络虚拟化；启发式算法；映射算法；波长分配

0 引 言

随着全球LTE网络大规模部署，物联网、云计算[1]等产业的不断完善，越来越多的数据中心连接到物理网络基础设施，给当前通信网络的业务流量带来指数级的增长，使得信息产业向宽带化方向发展。光网络技术的发展，为高带宽应用提供了海量带宽资源，然而现有光网络可用波长资源有限[2]，故而其带宽资源利用率低。而目前网络僵化[3]越来越严重，导致现有网络架构已经难以满足互联网业务的多样性需求，给当前光传送网带来了巨大压力，网络的可持续发展面临严峻挑战。光网络虚拟化[4]可将虚拟网络与底层物理光网络有效隔离，使得网络资源配置更加灵活，从而有效提升网络的整体性能。因此光网络虚拟化被认为是打破这一僵局的关键技术之一。

当前，在底层网络上已有众多基于分组交换网络的虚拟网络(VN)映射研究，但在WDM光网络中，如何合理映射虚拟网络是一个富有挑战的问题，也是—个NP-hard问题[5-6]。为了降低WDM网络虚拟化问题的复杂度，当前最被认同且应用最广泛的方法是将VN映射和RWA作为两个独立的子问题[7]来考虑。然而这种方法有链路映射失败或者映射的物理路径长度过大的缺点，从而浪费物理链路带宽资源，最终降低VN映射的接收率。

针对虚拟网络映射问题，文中提出光网络虚拟化映射协同路由波长分配(RWA)的方案。最近在控制平面上对软件定义网络(SDN)[8]的研究，显示出这种方案是可行的。根据该方案提出了两种启发式算法[9-10]，为了尽量减少对网络资源的需求，对算法中的候选节点的选择加上一定的限制条件，并进行仿真。仿真结果表明，该算法对VN映射的接收率有明显的提升作用。

1 虚拟网络映射启发式算法

主要目标是搜索每个虚拟节点的虚拟映射，寻找每条虚拟链路的路由并进行波长分配，使WDM网络中使用的总波长数尽可能小，同时尽量使每个物理节点的计算资源负载均衡[11]。在进行算法研究之前，设定前提条件如下：

一个WDM网络与一组光纤链路E，每条光纤链路有W个波长，一组物理节点N，每物理节点拥有一定的计算资源。用无向加权图G=(N,E)对此网络进行建模。此外，给定一组VN请求，其中每个虚拟节点v需一定的计算资源，并且可以被映射到一组候选物理节点上，每条虚拟链路需一条光链路。

文中所讨论的映射与路由分配算法所受约束如下：

(1)一个VN节点只能被映射到一个物理网络(SN)节点；

(2)同一个VN中的两个节点不能同时被映射到同一个SN的节点上；

(3)一条虚链路映射到一条物理光通道上，且受波长连续性影响；

(4)两节点间的光路流量受光路的总容量约束；

(5)同一个VN请求的节点资源需求不超过SN节点所具有的资源总和；

(6)同一根光纤中不同的光通道必须使用不同的波长，且同一条光纤链路的总光路不超过这条光纤链路的容量W。

为了提高映射成功率，在对一组VN请求进行映射前，先将这组中的每一个VN请求以虚拟链路的总数进行降序排序，然后以降序的顺序对这组VN依次映射。在对具体的一个VN请求进行映射时，将这个VN请求中虚拟节点以节点度降序排序，然后依次映射。对于首个节点映射，利用贪婪算法[12]，将它映射到物理网络中可用计算资源值最大的节点上，然后以此节点为中心节点，设为nv，给出其余候选节点到nv的距离dv，利用dv值来控制候选节点平均数量。

为了提高映射效率，在VN映射前对映射所需要的候选物理节点进行筛选，将满足条件的物理节点作为候选物理节点集，它能提供的可用计算资源需大于等于虚拟节点v的所需要求。接着在这些节点集中选出候选物理节点，映射之后，更新物理节点可用计算资源，如式(1)所示：

restNodeComputionn=preNodeComputionn-nodeComputionn

(1)

其中，restNodeComputionn为物理节点n剩余可用计算资源；preNodeComputionn为节点n映射前所具有的计算资源；nodeComputionn为当前映射的节点所需计算资源。

提出的两种启发式算法为最小路由跳数(Min_Span)算法和最小波长平面(Min_W)算法。这两种算法都基于分层图法[13-14]，即在每个波长平面网络中进行搜索符合条件映射。

Min_Span算法：试图找到最小路由跳数的VN映射。流程如下：

(1)对于每个VN请求，根据网络拓扑规模以及虚拟网络请求设定路由跳数i的范围。

(2)当i=1时，在波长平面j=1上开始节点映射，搜索符合约束条件的路由，如果搜索到满足条件的映射，算法停止，执行步骤(4)。如果没有满足条件的映射，那么在j=2的平面上搜索，直到j达到最大值。

(3)当i=1，j已到达波长平面最大值时，没有找到符合条件的映射，那么在所有波长平面搜索i=2的映射，如果找到符合条件的映射，则执行步骤(4)。当i达到最大值时，依然没找到满足要求的映射，则请求阻塞，执行步骤(4)。

(4)回到步骤(2)，进行下一个VN映射请求。

该算法的缺点是，在所有波长平面中搜索最少路由跳数映射，可能无法使网络效益最大化。

Min_W算法：试图找到使波长平面以及波长跳数尽量小的一个VN映射。流程如下：

(1)动态设置每个VN映射所允许的最大路由跳数值i，以及最大波长平面数(maxLayer)的最小值j。

(2)依次执行Min_Span方法的步骤(2)～(4)，并返回请求阻塞的VN映射。

(3)对于步骤(2)中阻塞的请求，在剩余的W-j波长平面范围内再次寻找这个映射。如果没有找到一个映射满足条件，那么请求阻塞，继续搜索步骤(2)中返回的其他VN请求。

文中提出的算法对文献[5]中的递归和穷举算法的i跳路由映射步骤做了一个改进：如图1(c)所示有序的候选节点映射，虚拟节点11映射到物理节点B上。但是，连续虚拟节点映射(14，C)变得无效，因为虚拟链接(11，14)上不存在单跳路径。算法退回到上一步，重新选择11的映射节点。若无论节点11如何映射，均无法满足条件，那么继续退回到上一步，直至找到满足条件的点。

图1 虚拟网络映射

与文献[5]的另一个区别是，针对每个虚拟节点v，算法对其候选物理节点n按照式(2)定义的节点资源量(mn)进行降序排序，以减少WDM网络资源的需求，并实现物理节点的计算资源负载均衡。

(2)

2 仿真与结果分析

将所提出的方案与将VN映射和RWA分步进行的方案做了比较。对于VN映射方案，首先在基础网络中应用文献[6]中提供的方法进行VN映射，然后在WDM网络中应用分层图方案进行波长分配。对于RWA的分步进行，模拟了一个场景：一种是同时对链接和节点进行负载均衡(Two_Step)，这与使WDM网络中使用的波长数最少具有类似的目的。上述方案固定了任意两个物理节点的最短路由。

使用如图2所示的网络拓扑结构，此处假设每条链路拥有64个可用波长。现在有一组VN请求，每个VN请求的虚拟节点的数量在[3,5]范围上随机生成。每个虚拟节点度范围在[1,3]，也为随机生成，dv为预先定值。每个实验重复20次，数据源为随机生成，然后得出结果。可以通过调整dv的平均值大小来控制虚拟节点的候选节点数(cv)的取值范围。

图2 20节点网络拓扑图

图3展示了在cv=8情况下，随着VN请求数增加时的网络资源需求情况。

图3 cv=8的虚拟网络映射性能对比

在图3中，相对Two_Step而言，Min_W使得波长指数最大值(Wmax)更低、波长跨越更少。例如，当VN请求的数目是100时，Min_W比Two_Step需要的波长平面数少30%，同时少约30%的波长跳数，且Two-Step需要的波长数已超过40个。从仿真结果可以看出，Min_W具有最低的Wmax，但路由跳数比Min_Span略多，因为Min_Span主要是要求路由跳数最小，而Min_W侧重于maxLayer最小。

图4展示了虚拟节点映射的灵活性增加对网络资源的影响。

图4(a)和(b)展示了Wmax以及每个虚拟链路的平均波长跳数。例如，对于固定的节点映射(cv=1)，Wmax值在64，此时用尽了所有可用波长，每个虚拟链路平均路由跳数约为3.3。当一个虚拟节点具有最大的弹性分配(cv=20时，所有节点将存在于网络中)时，Min_W的Wmax为17，如果波长足够多，其值比固定节点映射少了近78%，同时Min_W的每个虚拟链路的平均路由跳数约为1.2，比固定节点映射少60%。图4(c)表明，cv值为1时，三种算法均会发生阻塞，因为没有足够的波长资源，但是Two_Step的阻塞率更高些。在Two_Step为2时，虽然Min_Span还是使用了所有波长，但是并没有发生阻塞现象。此时Min_Span尽可能增加路由跳数来满足业务请求。当cv值在[2,8]这一范围时，Two_Step请求还是可能会被阻塞，即使网络有足够的网络和计算资源，这是因为两个虚拟节点不能被映射到同一个物理节点上，而且Two_Step没有回溯机制。

图4 灵活虚拟网络映射性能对比

3 结束语

提出的启发式算法协同考虑WDM光网络的虚拟网络映射以及RWA问题。仿真结果表明，该方案比将VN映射与RWA分开进行的方案要好，可以节约高达30%的光网络资源。同时还证明，相对固定节点映射，利用灵活可变的自适应虚拟节点映射，可以有效地利用光网络资源，以及充分利用网络虚拟化的优点。

[1] 陈 全,邓倩妮.云计算及其关键技术[J].计算机应用,2009,29(9):2562-2567.

[2] 肖萍萍,吴健学,周 芳,等.SDH原理与技术[M].北京:北京邮电大学出版社,2002:186-197.

[3]AndersonT,PetersonL,ShenkerS,etal.OvercomingtheInternetimpassethroughvirtualization[J].Computer,2005,38(4):34-41.

[4]ZhangS,ShiL,VadrevuCSK,etal.NetworkvirtualizationoverWDMnetworks[C]//IEEE5thinternationalconferenceonadvancednetworksandtelecommunicationsystems.[s.l.]:IEEE,2011:1-3.

[5]LischkaJ,KarlH.Avirtualnetworkmappingalgorithmbasedonsubgraphisomorphismdetection[C]//ACMSIGCOMMVISA.[s.l.]:ACM,2009.

[6]ZhuY,AmmarM.Algorithmsforassigningsubstratenetworkresourcestovirtualnetworkcomponents[C]//ProceedingsofINFOCOM.[s.l.]:IEEE,2006.

[7]YangH,ZhaoY,ZhangJ,etal.Crossstratumoptimizationofapplicationandnetworkresourcebasedongloballoadbalancingstrategyindynamicopticalnetworks[C]//OFC.[s.l.]:[s.n.],2012.

[8] 张 成.软件定义网络的研究及应用[D].广州:华南理工大学,2014.

[9] 卿苏德.网络虚拟化映射算法研究[D].北京:北京邮电大学,2013.

[10] 雷德明.多标智能优化算法及其应用[M].北京:科学出版社,2009.

[11] 宋绍义.未来互联网络资源负载均衡研究[D].北京:北京邮电大学,2014.

[12] 高 玲.光网络虚拟化带宽调度技术研究[D].南京:南京邮电大学,2015.

[13] 徐世中,李乐民,王 晟.多光纤波分复用网动态路由和波长分配算法[J].电子学报,2000,28(7):23-27.

[14] 王汝言,张普钊,隆克平,等.WDM网络中一种基于分层图模型的RWA算法[J].光通信技术,2007,31(10):4-6.

Research on Virtual Network Mapping Combined with RWA inWDM Optical Network

HE Yuan，HOU Shao-hua

(College of Electronic Science and Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Recently,with the development of the Internet of Things and Cloud Computing,the optical Wavelength Division Multiplexing (WDM) network becomes more and more important.Virtualization Network (VN) and Routing Wavelength Assignment (RWA) are the key technologies of WDM optical network.However,the superior performance of the VN mapping and RWA,which contains many constraints,is a NP hard problem to the target solving.Therefore,in order to simplify the problem,more research is just based on the subproblem of VN mapping and RWA.Jointly considering problems of VN mapping and RWA in WDM networks,the Min_Span and Min_wavelength algorithm are proposed based on heuristic algorithms.The two algorithms mainly analyzes the total demand of VN mapping in routing spans and the wavelengths,which is simulated and compared with the Two_Step scheme algorithms.The simulation results show that the scheme proposed is better than Two_Step.It also shows that the network design with flexible virtual node mapping can efficiently utilize optical network resources compared to fixed node mapping.

WDM;network virtualization;heuristic algorithm;mapping algorithm;RWA

2016-04-16

2016-08-11

时间：2017-02-17

何 源(1988-)，男，硕士研究生，研究方向为光网络与光通信；侯韶华，副教授，硕士研究生导师，研究方向为光通信与光波技术。

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

TP301.6

A

1673-629X(2017)03-0122-04

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