面向动态环境的虚拟光网络资源优化算法*

2024-03-26张顺利邵苏杰

电讯技术 2024年3期

张顺利,邵苏杰

(1.晋中学院信息技术与工程系,山西晋中 030619;2.北京邮电大学计算机学院,北京 100876)

0 引言

随着5G、设备到设备通信等技术的快速发展和应用[1-3],网络带宽的需求量快速增加。采用网络虚拟化技术构建的新型弹性光网络(Elastic Optical Networks,EONs),逐渐成为下一代极具前景的光传送网[4]。在EONs环境下,服务提供商(Service Provider,SP) 通过从底层设施提供商(Infrastructure Provider,InP) 租用光网络资源,也称为底层网络(Substrate Network,SN) 资源,创建虚拟网络(Virtual Network,VN)为最终用户提供定制服务,无需对底层设施进行大量投资[5]。所以,EONs环境下的资源分配是一个研究重点。文献[6]基于光纤的并行传输特性,提高了光网络的资源利用率。文献[7]采用动态定价策略,从经济学角度提升了资源的经济收益。文献[8]针对空分复用弹性光数据中心网络,提出了基于链路和节点特征的资源分配算法。文献[9-11]分别从光路可靠性、多业务部署维度提升了网络的可用性、安全性以及服务质量。但是,随着EONs应用范围的增加,虚拟网络及其承载服务的规模、数量、复杂度也快速增加。例如,部分虚拟网服务的流量需求与日期、业务成熟度等因素相关,文献[6-11]不能有效解决流量需求变化场景下的资源分配问题。为解决所需资源与获得资源不匹配问题,文献[12]设计了资源感知的虚拟网络重构策略。为解决高密度网络环境下资源分配效率低的问题,文献[13]根据容量和可行性比率构建虚拟网链路缩减网络模型,提出了贪婪链路缩减算法。但是,在虚拟网链路缩减阶段,需要多次迭代计算虚拟网链路容量和可行性比率,时间复杂度较高。尤其是在网络动态环境下,增加了资源分配算法的复杂度。同时,当虚拟网络生命周期结束,网络资源的数量和利用率都会发生动态变化,容易造成虚拟网服务不可用、部分底层网络资源负载过重、网络资源浪费等问题。

为解决此问题,本文提出了面向动态环境的虚拟光网络资源优化算法(Resource Optimization Algorithm for Virtual Optical Networks under Dynamic Environment,ROAVONDE)。为实现虚拟网络之间更好的协调,获得最优化的虚拟网络映射拓扑,引入人工链路来重建底层网络拓扑,并基于此将虚拟节点连接到其等价类中选定的底层节点,提出随机舍入优化算法对虚拟节点最优迁移策略进行求解。为降低算法时间复杂度,充分利用节点之间的竞争关系,提出一种虚拟网络划分算法,将所有虚拟网络拓扑划分为k个子VN。与已有算法的比较结果验证了本文算法较好地提升了底层网络的资源利用率和虚拟网的映射成功率。

1 问题描述

1.1 底层网络

图1 虚拟网络资源分配示意Fig.1 Virtual network resource allocation

1.2 虚拟网络请求

底层节点nS的剩余CPU容量RN(nS)和底层链路eS的剩余带宽容量RE(eS)定义如公式(1)和公式(2)所示:

RN(nS)=c(nS)-∑∀nV↓nSc(nV)

(1)

RE(eS)=b(eS)-∑∀eV↓eSb(eV)

(2)

式中:nV↓nS表示nV的资源由nS分配;eV↓eS表示eV的资源由eS分配。

1.3 资源分配

虚拟网络映射定义如公式(3)所示,表示虚拟网GV(NV,EV)资源由底层网络GS(NS,ES)分配。虚拟网络映射可分解为节点映射和链路映射[12-13]。

M:GV(NV,EV)⟹GS(NS,ES)

(3)

节点映射的形式化描述如公式(4)所示,约束条件如公式(5)和公式(6)所示,其中dis(i,j)表示两个节点i和j位置之间的物理距离。

MN(nV)∈NS

(4)

c(nV)≤RN(MN(nV))

(5)

dis(loc(nV),loc(MN(nV)))≤D(nV)

(6)

(7)

(8)

2 线性规划模型

2.1 网络重构

虚拟节点选择底层节点的约束包括资源约束和位置约束。为协调所有虚拟网络以获得最优的虚拟网络映射拓扑结构,以虚拟节点的位置和资源需求为约束来重构底层网络[14-15]。本文以位置约束作为资源竞争特征,为每个虚拟节点构建等价类,从而为每个虚拟节点选择最优的底层节点。

EC(nV)={nS∈NS|dis(loc(nV),loc(nS))≤D(nV)}

(9)

2.2 线性规划模型

虚拟网映射拓扑优化问题可以表述为线性规划商品流问题。一个具有源节点si∈NV和目的节点ti∈NV的商品流就等于一条虚拟链路eV(i,j)∈EV。最优VN 映射拓扑的线性规划公式(Linear Programming Formulation for Optimal VN mapping Topologies,LPF_OVNT)的目标函数如公式(10)所示:

(10)

s.t. C1:RN(m)≥δwmc(w),∀w∈NV,∀m∈NS

C6:δwm≥0,∀w∈NV,m∈NS

3 优化算法

资源优化算法包括无划分的随机舍入优化算法、带划分的随机舍入优化算法两种,下面进行详细描述。

3.1 无划分的随机舍入优化算法

无划分的随机舍入优化算法具体描述如下:

1 重建底层和虚拟网络,得到新网络GS′=(NS′,ES′)

2 使用模拟退火算法求解满足LPF_OVNT约束的公式(10)的解

8 end for

9psum←∑x∈EC(nV)px

12 end for

13 使用px取值最大的底层节点为当前虚拟节点分配资源

14 end for

15 使用多商品流算法映射迁移的虚拟节点的虚拟链路

16 更新 SN 剩余资源容量

3.2 带划分的随机舍入优化算法

为了利用小型拓扑的灵活性,将所有 VN 分解为多个子虚拟网络(subVN)。为实现这个目标,本文将有资源竞争的VN节点放置在同一个subVN中,提出带划分的随机舍入优化算法(ROAVONDE-with-Divide)(subVN的数量设置为k)。

带划分的随机舍入优化算法包括4个关键步骤:

步骤1为虚拟节点生成备选底层节点集合(算法第1～7行)。首先根据节点坐标范围为每个虚拟节点寻找底层节点集,然后按照资源容量对每个底层节点集进行排序。

步骤2将所有虚拟节点划分为k个子网(算法第8～24行):①根据资源的竞争关系,连接所有虚拟节点。每个链路的权重表示两个虚拟节点的竞争实力。因为两个底层节点在各自集合中的序号之和表示链路的权重。序号越小,表明这两个节点在各种集合的顺序越前。所以链路的权重越小,竞争力越强(第8～14行)。②将虚拟节点划分为k个集合(第 15～24 行)。首先,将所有虚拟节点按节点度数递减排序,然后取出度数最大的虚拟节点和它的连接节点,创建一个新的集合并放入其中。重复这样做,直到创建了k个新集合。最后,将剩余的虚拟节点根据与k个集合中所有中心节点的距离放入最近的集合中。

步骤3将虚拟链路放入相关子网(算法第25～29行)。将属于单个子网的链路放入对应的子网内,将不属于单个子网的链路放入待映射链路集合Erest。

步骤4执行节点映射和链路映射(第30～33行),根据无划分的随机舍入优化算法为每个subVN分配底层网络资源,最后使用多商品流算法映射Erest中的虚拟链路。

带划分的随机舍入优化算法具体描述如下:

步骤1 为虚拟节点生成备选底层节点集合

2 fornS∈NV

5 end for

6 end for

步骤2 将所有虚拟节点划分为k个子网

10 if这两个底层节点是相同的

11X=这两个底层节点在各自集合中的序号之和

13 end for

14 end for

15 form=0 tok-1

19k++;

20 end for

24 end for

步骤3 将虚拟链路放入相关子网

27 else

29 end for

步骤4 执行节点映射和链路映射

30 for each subVN

31 使用无划分的随机舍入优化算法分配资源

32 end for

33 使用多商品流算法映射Erest中的虚拟链路

4 仿真与分析

4.1 仿真环境

本文实现了一个 VN 嵌入模拟器来评估算法。底层和虚拟拓扑以及VN到达过程参数与已有研究类似[13-15]。随机舍入优化算法中的线性规划问题使用 GLPK 来解决。使用GT-ITM拓扑生成器来生成网络拓扑[16]。从边等于100的正方形区域中随机提取底层网络的位置。底层网络配置为每次实验有100个节点,每对底层节点以0.5的概率随机连接。节点的CPU和链路的带宽资源遵循50～100个单位的均匀分布。每个VN请求中,从边等于100的正方形区域中随机抽取虚拟网络的位置。VN节点的数量由2～10之间的均匀分布随机确定,每对虚拟节点以0.5的概率随机连接,节点上的 CPU 资源遵循1～20的均匀分布。链路上的带宽资源遵循1～50的均匀分布。VN 请求的到达服从泊松分布,每个请求的平均时间窗口为 1.5,请求的持续时间遵循平均20个时间窗口的指数分布,每个时间窗口的时长为10 s。

表1列出了用于性能分析对比的4种算法。算法ROAVONDE-without-Divide和算法ROAVONDE-with-Divide用于分析基于资源竞争特征重构底层网络以及网络划分对算法性能的影响,算法RDVNFE(Reducing Dense Virtual Networks for Fast Embedding)是根据网络特征进行网络重构的最新研究成果[13],算法RDVNFEO(Reducing Dense Virtual Networks for Fast Embedding and Optimization)在文献[13]的基础上采用经典的优化策略对网络资源进行优化。

表1 评估算法Tab.1 Evaluation algorithms

4.2 算法运行时长分析

将虚拟网划分为3～6个子网络,分析算法VONROADE-with-Divide的性能可知,划分数量为4时算法的性能较优。算法RDVNFE不对底层网络上的资源进行重新优化,算法RDVNFEO周期性地对利用率超过阈值的底层资源上承载的虚拟网络资源进行重分配,不需要对网络进行重构和求解,所以,将划分数量为4的算法VONROADE-with-Divide与算法VONROADE-without-Divide进行比较,分析虚拟网划分对网络优化时长的影响。

算法运行时长结果如图2所示,可知随着虚拟节点数量的增加两种算法的运行时长都在增加,说明虚拟节点数量增加后,需要优化的网络资源数量也快速增加;算法VONROADE-without-Divide的运行时间较长,而且随着网络规模增加,运行时间增加较快;算法VONROADE-with-Divide运行时间较短,而且随着网络规模增加,运行时间的增加比较缓慢,说明算法VONROADE-with-Divide可以降低网络优化的时间开销。

图2 算法运行时长Fig.2 Algorithm runtime analysis

4.3 网络优化性能分析

对于每个网络场景,性能分析的结果是20个随机实例的平均值。算法性能指标与时间的关系如图3～7所示。平均收益是所有已映射的虚拟网计算资源和带宽资源的加权求和与时长的比值,平均开销是为完成虚拟网资源分配而使用所有底层网络的计算资源和带宽资源加权求和与时长的比值。平均收益、平均开销的单位都使用“a.u.”(arbitrary units的缩写),表示任意单位。

图3 随时间变化的VN请求接受率Fig.3 VN request acceptance rate over time

图4 资源分配的平均收益Fig.4 Average revenue on resource allocation

图5 资源分配的平均开销Fig.5 Average cost of resource allocation

通过对实验结果的分析,本文总结了下面5个主要观察结果:

1)算法ROAVONDE-without-Divide和算法ROAVONDE-with-Divide通过协调所有虚拟网络获得最优的虚拟网络映射拓扑,可以获得更高的接受率和收益。从图3可以看出,本文算法ROAVONDE-without-Divide下虚拟网请求的平均接受率收敛均值约62%,算法 RDVNFE 的平均接受率收敛均值约56%,所以算法ROAVONDE-without-Divide的平均接受率比算法 RDVNFE 提升了约11%。更高的收入和更好的接受率表明本文算法可以将底层网络资源分配给更多的虚拟网络请求。

2)在图3～5中,成本增加率低于VN请求接受率和平均收益的增加率。由于本文算法ROAVONDE-without-Divide和算法ROAVONDE-with-Divide可以协调所有虚拟网络以获得最优的虚拟网络映射拓扑,使得虚拟网络能够被分配到最优的底层网络资源,从而降低了底层网络资源的成本。

3)从图6和图7可以看出,本文算法提高了网络资源的利用率。本文算法ROAVONDE-without-Divide和算法ROAVONDE-with-Divide比算法 RDVNFE和算法RDVNFEO提高了节点利用率和链路利用率,原因是本文算法ROAVONDE-without-Divide和算法ROAVONDE-with-Divide提高了VN请求接受率,使用了更多的底层网络资源。相比现有算法 RDVNFE,本文算法ROAVONDE-without-Divide下节点资源均利用率提升了约 61%,链路资源平均利用率提升了约27%,说明本文算法ROAVONDE-without-Divide可以为虚拟网络分配更加优化的链路资源。

图6 随时间变化的节点资源平均利用率Fig.Average utilization rate of node resources over time

图7 随时间变化的链路资源平均利用率Fig.7 Average utilization rate of link resources over time

4)算法ROAVONDE-with-Divide 在 VN 请求接受率和平均收益方面不如算法 ROAVONDE-without-Divide,但算法ROAVONDE-with-Divide在VN请求接受率和平均收益方面优于算法RDVNFE和RDVNFEO。在算法运行时间方面,算法ROAVONDE-with-Divide优于算法ROAVONDE-without-Divide。因此,如果网络规模较大,可以使用算法ROAVONDE-with-Divide提升虚拟网映射的效率。