基于距离自适应的高效灵活光网络虚拟化映射启发式算法研究

杨福涛,王宏宇

(鞍山师范学院 物理科学与技术学院,辽宁 鞍山 114007)

基于距离自适应的高效灵活光网络虚拟化映射启发式算法研究

杨福涛,王宏宇

(鞍山师范学院 物理科学与技术学院,辽宁 鞍山 114007)

提出了一种基于距离自适应的灵活光网路虚拟化映射算法及其改进算法.各种仿真结果表明，可以较好地解决网络虚拟化映射问题，本算法及其改进算法可以取得较低的网络阻塞率和较高的资源利用效率，效果令人满意.

灵活光网络；距离自适应；映射算法

为满足以数据中心互联和云计算为代表的新兴网络业务的带宽需求，迫切需要新的能提高网络资源利用率的网络技术来满足这种需求，网络虚拟化技术正是这些技术中的一个杰出代表.网络虚拟化技术可以让服务提供商在一个物理网络上为各类网络服务提供逻辑上相互隔离的、按需提供资源的虚拟网络，以解决传统技术难以兼容异构网络和服务差别化不充分的问题.一个虚拟网络包括若干虚拟节点和若干虚拟链路，可以依照客户的需求按特定拓扑结果连接在一起.同时，目前的灵活光网络已经大规模部署了多调制格式可编程光收发器，这为虚拟化映射的效率提高提供了有利的条件[1～3].

在实际应用中，很多具体的虚拟化映射问题都存在着一定的约束条件，如，物理节点的地理位置的约束或是归属权的约束等.例如，一个视频会议系统服务提供商，为了降低分组传输的延迟，有效的解决办法就是使服务器的地理位置与被服务者的地理位置足够靠近.本文从实际从发，以这种约束条件为前提，结合距离自适应策略，提出了一种高效的灵活网络虚拟化映射算法.以往，针对灵活光网路的虚拟化映射算法已有相当数量的研究，如，文献[4,5]都提出了相应的算法，但是，文献[4]中提出的是一种贪婪(ES)算法,虽然通过穷举的办法可以得到相对较好的映射结果，但是当物理网络的规模比较大时，这种算法的计算时间将变得非常巨大.文献[5]中提出了一种在所有最大开销中选择最小的一种的(MMCP)算法，但是这种算法仅考虑预映射时各种最大开销情况，而没有综合地考虑各种开销情况，所以难以达到全局优化的目的.本文提出的算法，目的在于从全局出发，综合考虑预映射的综合开销，以此为依据，完成映射节点的确定，使其更加具备全局优化的优势，从而提高网络的资源利用率.

1 算法描述

图1展现的是一个虚拟网请求，其中有3个虚拟节点和3条虚拟链路，同时，每个虚拟节点都有一个候选映射节点集合(可以映射到的物理节点的集合).如图1所示，虚拟节点1的候选映射节点结合是{A,B},虚拟节点2的候选映射节点集合是{C,D},虚拟节点3的候选映射节点结合是{E,F}.其中，A,B,C,D,E,F是如图2所示的物理网络上的物理节点，物理网络拓扑中每条链路上的数字表示本链路的长度(单位为km).

假设本场景下，每个节点收发机有2种调制格式，为保证信号的误码率，在距离小于300 km时，选择调制格式一，传送40 Gbps信息需要1个频隙(slot)；而当距离大于300 km时，选择调制格式二，传送40 Gbps信息需要2个频隙(slot).同时本文假设此虚拟网的需求中，每个虚拟链路上的信息速率需求是40 Gbps.本算法首先确定每个虚拟映射节点应该映射到哪个物理节点上，其具体过程是：对于某个映射节点(如虚拟节点1)，对于其候选映射节点中的每一个候选物理节点(如物理节点A或B)，按虚拟网的拓扑结构，计算其到直接连接的其他虚拟节点(虚拟节点2或3)的候选物理节点集合中的每个物理节点(物理节点C、D或物理节点E、F)的频隙(slot)开销，这种连接是按K最短路径算法(KSP算法，即在给定拓扑中求特定的两点间的前K条最短路径的算法)计算得到可以用的最短路径连接.具体的计算过程描述如下：集合{A,B}中，分别计算A到集合{C,D}和{E,F}的开销，再计算B在此情况下的开销，因为A点的综合开销大于B点的综合开销，所以本算法选择B点作为虚拟节点1 的映射节点.其它虚拟节点的映射物理节点也同样用这个方法计算得到.具体的计算过程可参见表1.本文将本算法称为综合代价最小映射(MTCE)算法.

表1 利用综合开销选择映射物理节点的计算过程表

图3显示了映射结果，其中虚拟节点1映射到物理节点B，虚拟节点2映射到物理节点D，虚拟节点3映射到物理节点E.对于各虚拟节点间的虚拟链路，其映射结果用加粗的虚线在图3中反映.具体来说，虚拟链路(1,2)映射到物理路径(B,D),虚拟链路(2,3)映射到物理路径(D,E),虚拟路径(3,1)映射到物理路径(E,B).

图1 虚拟网的需求

图2 物理网路

2 启发式算法步骤

图3 映射结果

(1)利用K最短路径算法，为每对节点计算K条最短路径.

(2)用MTCE算法，按照(1)中K条路径长度顺序，为需要计算开销的两点间选择可用的最短路径，依次计算一个物理节点集合中的所有物理节点的总开销，选择其中总开销最小的那个物理节点，作为本集合中被选中的映射节点.

(3)每个虚拟链路两端的虚拟节点所选择的映射物理节点间的可用最短路径就是相应的虚拟链路映射结果.

以上部分为MTCE算法的基本步骤，在特定情况下，在步骤(1)用K最短路径算法求得的K条路径可能都已无资源可用，这时其它路径也许还有比较多的资源没有利用，鉴于这种情况，可以将MTCE算法进行优化，在K条路径均不可用的情况下，去掉无资源可用的所有物理链路(link)，重新计算两点间的K条路径，具体方法见步骤4.

(4)当某个需求被拒绝，算法将当前已经被利用满的链路从物理拓扑图中去除掉，然后重新进行步骤(1)～(3)，如果依然无法满足需求，则拒绝此虚拟网络的请求.

本文将加入了步骤(4)的算法称为加强的MTCE算法，简称IMTCE算法.

3 仿真验证

仿真试验将24个节点43条链路的USNET作为物理网络，并且，我们把24个节点划分为8个不同的集合(同一个集合的节点用相同的数字标识)，作为8个不同的候选映射集合(每个集合有3个物理节点)，如图4所示.对于需求的拓扑结构，每个需求随机拥有M个节点(M大于3)，每个节点的度的范围为(1，M-1)内随机，拓扑内每条链路上的速率需求相等，都为1 Tbps,如果距离小于300 km，本仿真试验选用DP-16QAM调制格式，需要20个频隙(slot)来满足传输需要，若距离大于300 km，本仿真试验选用DP-QPSK调制格式，则需要40个频隙(slot)来满足传输需要.

为了表示不同算法的资源利用率情况，本文定义需求阻塞率和开销比率两个表征参数来比较不同算法的效果.这里，需求阻塞率={(被拒绝的需求个数)/(所有需求的个数)}，而开销比率={某个算法满足一个需求时需要用的频隙(slot)数目/用贪婪算法(ES)满足这个需求所需要的(slot)数目}.显然，阻塞率和开销比率最小说明算法的效果越好.

图4 USNET

首先，本仿真试验假设每条链路上的资源都是无限多的，即每条物理链路有无限多的频隙(slot),图5(a)是在每个需求的拓扑随机地有3～6个节点的情况下，输入6,8,10,12个需求时，MMCP和MTCE两种算法开销比的对比图，从图5(a)中不难看出，随着输入需求的增加，MTCE算法的开销比增加非常缓慢，而MMCP算法的开销比增速高于MTCE算法，同时，在所有需求个数条件下，MMCP的开销比都比MTCE算法高很多.图5(b)是在输入需求个数为10的情况下，每个需求的节点个数在(3，X)范围内随机(其中X为4,5…8)的情况下，MTCE和MMCP两种算法的比较，其结果与图5(a)的情况大致相同，MTCE算法在开销比方面明显优于MMCP算法.

图5 开销比

再假设每条链路有350个频隙(slot)，如图6所示，在输入为10个需求的情况下，每个需求的节点个数在(3，X)(其中X为4,5…7)范围内随机的情况下，MTCE和IMTCE两种算法的阻塞率比较，从图6中不难看出，在不同X条件下，IMTCE均明显优于MTCE，这说明IMTCE算法在资源利用方面明显优于MTCE算法.

图6 阻塞率

4 结论

本文提出了一种灵活光网络的虚拟化映射算法及其改进算法，通过比较各节点的综合开销，找到合适的物理映射节点，同时，计算过程中用到的可用最小路径就是相应的虚拟链路映射结果.各种仿真结果表明，本算法及其改进算法具有更好的资源利用效率，是高效的灵活光网络虚拟化映射算法.

[1] Zhang Q,Xie W,She Q.RWA for network virtualization in optical WDM networks[C]//Optical Fiber Communication Conference and Exposition and the National Fiber Optic Engineers Conference,2013:1-3.

[2] Hammad A,Nejabati R,Simeonidou D.Novel approaches for composition of online virtual optical networks utilizing O-OFDM technology[C]//European Conference and Exhibition on Optical Communication,2013:1-3.

[3] Peng S,Nejabati R,Channegowda M,et al.Application-aware and adaptive virtual data centre infrastructure provisioning over elastic optical OFDM networks[C]//European Conference and Exhibition on Optical Communication,2013:7721-7729.

[4] Wang X,Zhang Q,Kim I,et al.Flexible virtual network provisioning over distance-adaptive flex-grid optical networks[C]//Optical Fiber Communication Conference,2014:1-3.

[5] Zhu Y,Goo K K,Liang Y,et al.Scalable virtual network provisioning over distance-adaptive flexible grid optical networks[C]//Optical Fiber Communications Conference and Exhibition.IEEE,2015.

(责任编辑：张冬冬)

Novel virtual network mapping heuristic algorithms over distance-adaptive flexible grid optical network

YANG Futao，WANG Hongyu

(SchoolofPhysicalScienceandTechnology，AnshanNormalUniversity,AnshanLiaoning114007,China)

We propose a novel heuristic algorithm and its improved algorithm about virtual network embedding over flex-grid optical network.Evaluation shows it can address the virtualization mapping issue effectively.The heuristic algorithm and its improved algorithm achieve lower blocking probability and improve the utilization efficiency of physical network,which satisfies with the network demands well.

flexible grid optical;distance-adaptive;mapping algorithm

2016-10-19

杨福涛(1978-)，男，辽宁沈阳人，鞍山师范学院物理科学与技术学院讲师.

TN911．8

A

1008-2441(2016)06-0062-04