Resources Balancing Algorithm Based on the Time-frequency Fragment Awareness for Virtual Optical Network Mapping

1.   引言

近年来，随着云计算、网络视频，智能家居以及物联网等快速发展，给传输带宽资源有限的通信骨干网带来巨大挑战。传统粗粒度的波分复用网络不能满足日益增长的业务带宽需求，而弹性光网络(Elastic Optical Networks, EONs)凭借其特有的优点被认为是下一代极具前景的光传送网^[1,2]。此外，业务的快速发展使互联网构架越来越无法满足网络运营、管理、扩展、业务部署的需求，要在全球范围内部署一套类似规模的新网络是相当困难的，网络实际部署会因为他们之间复杂的商业关系而阻碍重重，网络陷入了“僵化”的局面，因此网络虚拟化技术被引入到EONs中来解决互联网僵化问题^[3,4]。

目前，用户产生的虚拟光网络(Virtual Optical Network, VON)通常由带有资源约束条件的虚拟节点(Virtual Node, VN)和虚拟光链路(Virtual Optical Link, VOL)组成^[5]，如何在底层网络为虚拟业务提供有效的资源分配被称作为虚拟网络映射问题，且已被证明是NP-hard问题^[6]。

为了降低阻塞率，提高资源利用率，研究者们已经做了许多研究。文献[7]提出了传统映射方法(Largest Computing resources requirement versus the Largest Computing resources provisioning, LCLC)，并在此基础上提出了高效的生存性虚拟光网络映射方法。文献[8]针对静态多播业务映射采用集成遗传算法和模拟退火算法，来减少消耗的频谱数。针对现有网络中动态到来的业务，文献[9]提出了基于频谱连续度的不透明虚拟网络映射算法(Spectrum Consecutiveness-Opaque Virtual Optical Network Mapping-ALgorithm, SC-OVONM-AL)，通过计算虚拟业务中每个节点的资源请求，进行排序，同时计算每个物理节点周围链路上的频谱连续度。文献[10]针对不透明光网络提出了整数线性规划模型(Integer Linear Program, ILP)，并在此基础上考虑链路上频谱资源提出了基于资源连续度感知的启发式算法(Consecutiveness aware Local Resource Capacity-K Shortest-Path-First Fit, CaLRC-KSP-FF)。但是文献[9]和文献[10]在分配频谱时采用的是传统的首次命中策略，在进行路由频谱分配时没有考虑网络中的碎片程度，导致网络中碎片化程度加重，增加阻塞率。文献[11]提出了节点转化能力和链路碎片化丢失概念，来降低网络中的阻塞率。

由于业务动态到达和离开，增加了网络的频谱碎片，传统首次命中(First Fit, FF)频谱分配算法未考虑相邻业务之间离开时间而产生不同程度频谱碎片，导致业务阻塞率增加。针对此问题，本文提出基于时间域-频谱域碎片感知的虚拟网络映射(FA-VNM)算法最小化频谱资源消耗。在路由频谱分配时，若路径上空闲频谱块满足业务请求频隙数，选择剩余持续时间方差小的频谱块传输业务，否则计算路径上的频谱聚合程度，选择频谱聚合度较高的路径传输业务。针对FA-VNM算法没有考虑底层网络的物理节点连通度数分布不均衡，导致网络资源使用不均衡，提出基于节点度数的负载均衡感知虚拟网络映射(LB-VNM)算法，设计节点的平均资源承载能力计算路径频谱聚合程度，依此对K条路径排序，均衡负载。

2.   虚拟网络映射问题描述

2.1   网络模型

在描述网络模型之前介绍第2节用到的参数，如表1所示。

表  1  参数对照表

参数	参数表达的含义		参数	参数表达的含义
$\vartheta _f^l$	二进制变量，如果链路l上第f个频谱的使用情况，空 闲则为1，否则为0		${\varphi _{e^{\rm{r}}},{p^{\rm{{s}}}}$	二进制变量，如果虚拟链路 ${e^{\rm{r}}}$ 映射在物理光路 ${p^{\rm{s}}}$ 上，则为1，否则为0
${\xi _{{i^{\rm{r}}},{j^{\rm{s}}}}}$	二进制变量，如果虚拟节点 ${i^{\rm{r}}}$ 映射在物理节点 ${j^{\rm{s}}}$ 则为1，否则为0		${\sigma _{e_1^{\rm{r}},e_2^{\rm{r}}}}$	二进制变量，如果虚拟链路 $e_1^{\rm{r}}$ 和虚拟链路 $e_2^{\rm{r}}$ 使用相同的物理链路则为1，否则为0
$C_i^{\rm{r}}$	虚拟节点 i 请求的计算资源		${W_{{e^{\rm{r}}}}}$	整型变量，分配给虚拟链路 ${e^{\rm{r}}}$ 的连续频谱块的开始索引值
$C_j^{\rm{s}}$	物理节点 j 具有的计算资源		${{{P}}^{{s}}}$	物理拓扑图中预先计算的路径集合
${Z_{{e^{\rm{r}}}}}$	整型变量，分配给虚拟链路 ${e^{\rm{r}}}$ 的连续频谱块的结束索 引值		${\rho _{e_1^{\rm{r}},e_2^{\rm{r}}}}$	二进制变量，如果分配给虚拟链路 $e_1^{\rm{r}}$ 的连续频谱块的开始索引值小于分配给虚拟链路 $e_2^{\rm{r}}$ 则为1，否则为0

下载: 导出CSV 

| 显示表格

底层EONs使用加权无向图表示为G^s(V^s, E ^s)，其中V ^s为底层物理节点集合，E ^s为底层物理链路集合，每一个底层物理节点和物理链路分别包含一定计算资源和带宽容量，如图1(a)所示。相似地，VONs也用无向图表示：G ^r(V ^r, E ^r)，其中V ^r表示VN集合，E ^r表示VOL集合，每个VN和VOL分别请求一定的计算资源和带宽资源，如图1(b)所示。图1(c)表示VON映射模型，即图中每个VN分别映射在物理节点1,3,4上，虚拟链路A-B映射在物理链路1-3上，虚拟链路A-C映射在物理链路3-4上。

图  1  底层网络和虚拟业务模型

下载: 全尺寸图片 幻灯片

2.2   约束条件

一般虚拟网络映射问题可分解为节点映射和链路映射两个子问题，且分别遵循相应的约束条件。

2.2.1   节点约束条件

式(1)，式(2)确保每一个虚拟节点都映射在唯一一个物理节点上。

式(3)，式(4)确保底层物理节点的可用计算资源满足被映射的虚拟节点请求的计算资源。

2.2.2   链路约束条件

式(5)确保分配给每条虚拟链路频隙数满足其虚拟链路请求。式(6)～式(9)确保了路径上的频谱一致性和连续性约束。

3.   基于时频联合碎片感知的资源均衡虚拟光网络映射算法

本文针对弹性光网络中虚拟网络映射的频谱碎片问题以及网络中资源分布不均问题，首先提出了FA-VNM算法，联合考虑频隙在时间域和频谱域碎片程度，解决底层网络中频谱碎片问题，降低网络中阻塞率。此外，本文针对FA-VNM算法没有考虑底层网络物理节点连通度数分布不均衡，导致网络资源使用不均衡的问题，提出了LB-VNM算法，以此均衡网络中资源分配情况，进一步降低阻塞率。

3.1   FA-VNM算法

根据FA-VNM算法，在节点映射阶段，首先将物理节点按照其资源可用性排序，并在路由频谱分配时，预先计算K条最短路径，先寻找与业务所需频隙数相同的频谱块并计算连续被占用的频谱块的剩余持续时间方差，选择被占用频谱块剩余持续时间方差小的频谱块，如果没有找到相同的频谱块，再寻找大于业务所需要的频隙数的频谱块，并计算路径频谱的聚合程度，从而降低阻塞率，提高资源利用率。

3.1.1   物理节点资源可用性排序

由于底层物理资源有限，针对请求资源多的虚拟节点应优先映射在底层资源充足的物理节点上，因此定义物理节点i的可用资源AvR(i)，可由式(10)计算，AvR(i)越大表示物理节点的可用资源越多。

其中，L为与节点i相连的物理链路集合， ${\rm{con}}(l)$ 表示链路l上空闲的频谱块之间的频隙连接度。

3.1.2   时间域碎片

持续时间不一致的业务动态到来与离去使得传统FF算法产生不同程度的频谱碎片。基于此，本文考虑业务持续时间方差，将持续时间相近的业务放在同一频谱段内传输来减少时间域上的碎片。

如图2所示，需要一个频隙的业务请求6在分配频谱时，可以将业务分配在连续频谱块块1或块2，由图可知，分配在频谱S5上，可以让业务离开的时间尽可能一致，则会减少时间域上碎片。为了减少频谱在时间域上的碎片，定义时间域碎片公式如式(14)：

其中，|B_k|表示连续被占用的频谱块上频隙的数目，d_j^s表示频隙在第j个频谱块剩余持续时间， ${\rm{a}}{{\rm{v}}^{{B_k}}}(l)$ 表示链路l上连续频谱块的平均持续时间， $\phi _{\displaystyle{_t}}^{{B_k}}(l)$ 表示链路l上连续B_k的剩余时间方差，则 ${\phi _t}(p)$ 表示路径上连续占用的频谱块剩余时间方差，方差越小说明频谱块的持续时间相当，离开时间越一致，时间域碎片越少。

图  2  时间域碎片示意图

下载: 全尺寸图片 幻灯片

3.1.3   频谱域碎片

在频谱资源分配的过程中，为了进一步减少频谱资源在频谱域上的碎片，定义频谱域碎片如式(16)所示，频谱碎片差值SFD如式(17)所示。

其中，c(l)为链路l上频谱聚合度，c(p)为路径p上频谱聚合度，c(p)_be表示没有为业务分配之前的路径频谱聚合度，c(p)_af表示为业务分配之后的路径频谱聚合度。

如图3所示，路径A-B-C上c(p)_be=1.30，现有新业务请求需要两个频隙，频谱块1和频谱块2都可以用来传输业务，频谱块1的c(p)_af=1.00，频谱块2的c(p)_af=1.17，则频谱块1的SFD=1.30–1.00=0.3，频谱块2的SFD值为1.30–1.17=0.13，由此可以看出频谱块2更适合传输业务。

图  3  频谱聚合程度示意图

下载: 全尺寸图片 幻灯片

FA-VNM算法详细步骤如表2所示。

表  2  FA-VNM算法

步骤1　虚拟业务到来，记录虚拟链路数L，令l表示第l条虚拟链路，l初始值为1，并按照每个虚拟节点所请求的计算资源 $C_i^{\rm{r}}$ 将节点降序排 序VR={vr1,vr2,···,vrn},vri表示第i个虚拟节点，i初始值为1；
步骤2　根据式(10)计算物理节点的资源可用性排序，并将物理节点按照降序排序，记为集合VS={vs1,vs2,···,vsn},vsi表示第i个物理节 点，i初始值为1；
步骤3　判断物理节点vsi可用计算资源是否大于等于虚拟节点vri请求的计算资源，如大于等于则将vri映射在vsi上，转至步骤4；否则标记 业务阻塞；
步骤4　将vri从集合VR删除，判断VR是否为空，若是，则转至步骤5，否则将i+1，转至步骤3；
步骤5　对第l虚拟链路(其中，l $\in$ [1, L])，根据虚拟节点映射的情况，根据Dijkstra算法计算找到对应映射的物理节点对之间的K条最短路 径，令k表示第k条传输路径，k初始值取1，转步骤6；
步骤6　若k>K，标记业务阻塞转至步骤1；否则转至步骤7；
步骤7　检查第k条(k $\in$ [1, K])光路上各链路频谱资源使用情况，根据业务所需频隙数选出大小等于业务所需频隙数的空闲频谱块作为可用 频谱块，加入可用频谱块集合 ${{ASB}}_k^{} = \left\{ {{\rm{as}}{{\rm{b}}_{\rm{1}}},{\rm{ as}}{{\rm{b}}_{\rm{2}}},·\!··,{\rm{ as}}{{\rm{b}}_n}} \right\}$ ，表示第k条路径上的可用频谱资源集合，asbm(m $\in$ [1, n])表示集合中 m第个可用频谱块，调用式(14)计算连续被占用的频谱块的剩余时间方差，选择剩余时间方差小的频谱块asbm分配业务，若 ${{ASB}}_k^{}$ 为空，转步骤8；
步骤8　检查第k条 (其中，k $\in$ [1, K])光路上各链路的频谱资源使用情况，再根据业务所需的频隙数，选出大小大于业务所需频隙数的空闲 频谱块，作为可用频谱块，加入到可用频谱块集合中，记作 ${{BSB}}_k^{}{\rm{ = }}\left\{ {{\rm{bs}}{{\rm{b}}_{\rm{1}}},{\rm{ bs}} {{\rm{b}}_{\rm{2}}},·\!·\!·,{\rm{ bs}}{{\rm{b}}_n}} \right\}$ ，表示第k条路径上的可用频谱资源集合， bsbm(m $\in$ [1, n])表示集合中第m个可用频谱块，并调用式(17)计算路径上的频谱碎片差值，选择聚频谱碎片差值小的频谱块bsbm分 配该虚拟链路，若集合ASBk和BSBk都为空，将k加1，转至步骤6；否则转至步骤9；
步骤9　判断l是否等于L，若等于则标记业务成功传输，转至步骤1；否则将l加1，转至步骤5。

下载: 导出CSV 

| 显示表格

3.2   LB-VNM算法

由于算法FA-VNM没有考虑网络拓扑形状，因此本文在LB-VNM算法中针对物理拓扑中节点度数分布不均匀特点，提出了节点平均资源承载能力的概念，并在路由频谱分配时，将K条路径按照路径平均资源聚合程度排序，使网络中的资源达到均衡的目的。

3.2.1   节点平均资源承载能力

为了评估物理节点平均资源承载能力，最大化利用物理网络中资源，定义AvRank如式(18)：

其中， ${\rm{dev}}(i)$ 表示物理节点i的度数，AvRank(i)值越大，表示节点i的平均承载能力越大。

3.2.2   路径平均资源聚合度

虚拟节点映射完成时，根据Dijkstra算法计算映射的物理节点的K条最短路径，计算每条路径的资源聚合度，并定义式(19)计算每条路径的平均资源聚合度，值越大表示这条链路上的频谱资源越充足。

其中， $\displaystyle\sum\nolimits_{l \in p} {\sum\nolimits_{f = 1}^{{F^{\rm{s}}}} {\vartheta _f^l} }$ 表示为路径p的资源聚合度， ${\rm{hop}}(p)$ 表示组成路径p的链路数。

LB-VNM算法具体步骤如表3所示。

表  3  LB-VNM算法

步骤1　虚拟业务到来，记录虚拟链路数L，令l表示第l条虚拟链路，l初始值为1，并按照每个虚拟节点所请求的计算资源将节点降序排序 VR={vr1,vr2,···,vrn},vri表示第i个虚拟节点，i初始值为1；
步骤2　调用式(18)计算每个物理节点的资源可用性AvRank，并将物理节点按照降序排序，记为集合Vs={vs1,vs2,···,vsn},vsi表示第i个虚 拟节点，i初始值为1；
步骤3　判断物理节点vsi可用计算资源是否大于等于虚拟节点vri请求的计算资源，如大于等于则将vri映射在vsi上，转至步骤4；否则标记 业务阻塞；
步骤4　将vri从VR删除，判断集合VR是否为空，若是，则转至步骤5，否则将i+1，转至步骤3；
步骤5　对第l虚拟链路，l $\in$ [1, L]，根据虚拟节点映射的情况，根据Dijkstra算法计算找到对应映射的物理节点对之间的K条最短路径，调 用式(19)分别计算K条路径的平均聚合程度 ${\rm{avc}}(p)$ ，按照路径的平均聚合程度avc(p)对k条候选路径进行降序排序，令k表示第k条传 输路径，k初始值取1，转至步骤6；
步骤6　若k>K，标记业务阻塞转至步骤1；否则转至步骤7；
步骤7　检查第k条 (其中，k $\in$ [1, K])光路上各链路的频谱资源使用情况，再根据业务所需的频隙数，选出等于业务所需频隙数的空闲频谱 块，作为可用频谱块，加入到可用频谱块集合中，记作 ${{CSB}}_k^{} = \left\{ {{\rm{cs}}{{\rm{b}}_{\rm{1}}},{\rm{ cs}}{{\rm{b}}_{\rm{2}}},·\!··,{\rm{ cs}}{{\rm{b}}_n}} \right\}$ ，表示第k条路径上的可用频谱资源集合，csbm (m $\in$ [1, n])表示集合中第m个可用频谱块，并调用式(14)计算连续被占用的频谱块的剩余时间方差，选择剩余时间方差小的频谱块 csbm分配业务，若集合CSB为空，转至步骤8；
步骤8　检查第k条 (其中，k $\in$ [1, K])光路上各链路的频谱资源使用情况，再根据业务所需的频隙数，选出大于业务所需频隙数的空闲频谱 块，作为可用频谱块，加入到可用频谱块集合中，记作 ${{DSB}}_k^{} \!=\! \left\{ {{\rm{ds}}{{\rm{b}}_{\rm{1}}},{\rm{ ds}}{{\rm{b}}_{\rm{2}}},·\!··,{\rm{ ds}}{{\rm{b}}_n}} \right\}$ ，表示第k条路径上的可用频谱资源集合，dsbm (m $\in$ [1, n])表示集合中第m个可用频谱块，若集合CSB和DSB为空，将k加1，转至步骤6，否则转至步骤9；
步骤9　记录所选择的传输路径k，并按频谱索引值从小到大的顺序，选择第1个可用的频谱块dfsm进行频谱分配，转至步骤10；
步骤10　判断l是否等于L，若等于则标记业务成功传输，转至步骤1；否则将l加1，转至步骤5。

下载: 导出CSV 

| 显示表格

4.   算法仿真结果分析

为验证本文所提算法FA-VNM和LB-VNM性能，算法分别在具有15节点26条链路的Topo15拓扑、14节点23条链路DT拓扑以及24节点43链路的USNET拓扑中进行仿真验证。每个物理节点初始计算资源200单位，每条链路初始分配150个频隙，候选路径K=3。虚拟业务请求到达服从参数为 $\lambda$ 泊松分布，虚拟节点数随机分布在[3～5]，每个虚拟节点计算资源随机分布在[1～3]，虚拟节点之间连通概率为0.5，每条虚拟链路请求的带宽要求在[1～5]随机产生，业务的持续时间服从参数为u的负指数分布。对比算法为LCLC^[7], CaLRC-KSP-FF^[10]。仿真指标为网络带宽阻塞率，频谱利用率和虚拟业务阻塞率。

图4所示为4种算法在不同网络环境中的带宽阻塞率，由于Topo15的连通度高于其余两个拓扑图，故相同负载下，Topo15的阻塞率最低，在Topo15拓扑，DT拓扑以及USNET拓扑图中，本文提出的FA-VNM算法和LB-VNM算法相比于对比算法有更低的阻塞率，主要原因为FA-VNM算法在路由频谱分配时考虑了时间域和频谱域的碎片程度，减少了路径上的频谱碎片从而降低了阻塞率。LB-VNM算法在节点映射时考虑了物理节点的平均资源承载能力，并在链路分配时考虑了路径的平均聚合程度，从而均衡了网络中的资源，最大化利用网络中的资源，且在Topo15和DT拓扑图中，LB-VNM算法比FA-VNM算法具有更低的阻塞率，这是因为Topo15和DT拓扑图相对于USNET拓扑网络中的物理节点度数分配更不均衡，所提的LB-VNM算法能更好地均衡网络中的资源，从而进一步降低阻塞率。

图  4  4种算法在不同网络中的带宽阻塞率

下载: 全尺寸图片 幻灯片

图5分析了4种算法在两种网络环境中不同负载下频谱资源利用率的变化情况，可以看出4种算法的频谱资源利用率都随负载的增大而增大。本文所提的FA-VNM和LB-VNM算法获得了更高的频谱利用率，这是因为本文所提的FA-VNM算法考虑了业务的持续时间，因此减少网络中的频谱在时间域上的碎片，从而更好地利用网络中频谱资源，LB-VNM算法则考虑了物理节点和物理路径上的资源负载情况，实现了更好的资源负载均衡，提高了频谱利用率。

图  5  4种算法在不同网络中的频谱利用率

下载: 全尺寸图片 幻灯片

图  6  4种算法在不同网络中的业务阻塞率

下载: 全尺寸图片 幻灯片

图6表示了4种算法在Topo15网络、DT网络以及USNET网络的业务阻塞率，由图可知本文所提的算法FA-VNM和LB-VNM相对于对比算法可以服务更多业务，这是因为本文所提的算法可以更好地利用网络中的碎片，且LB-VNM考虑了不同网络的网络拓扑结构，选路时考虑了负载均衡。在网络中传输相同业务时，本文所提算法既降低了业务阻塞率，又提高了频谱利用率。

5.   结束语

本文研究了弹性光网络中虚拟网络映射算法，提出了基于时间域-频谱域碎片感知的虚拟网络映射算法，通过联合时间域和频谱域有效地降低网络中的阻塞率。在此基础上，针对物理拓扑图的节点度数不均匀的特点导致底层物理资源分配不均衡，提出了基于节点度数的负载均衡感知虚拟网络映射算法。在该算法中，考虑物理节点和物理链路上的可用资源对全网的影响，设计节点和链路平均可用资源公式，达到负载均衡的目的，以此降低阻塞率。仿真结果表明，所提算法能有效降低阻塞率，提高资源利用率。