Resources Balancing Algorithm Based on the Time-frequency Fragment Awareness for Virtual Optical Network Mapping
-
摘要: 为了解决虚拟光网络映射中带宽阻塞率较高以及底层资源消耗不均匀问题，论文提出一种基于时间域-频谱域碎片感知的虚拟网络映射(FA-VNM)算法。该文综合考虑频隙在时间域和频谱域上的碎片问题，设计时频联合碎片公式最小化分配过程中的频谱碎片。进一步，为了均衡网络中的资源消耗，在FA-VNM算法基础上提出基于节点度数的负载均衡感知虚拟网络映射(LB-VNM)算法，设计物理节点平均资源承载能力的公式，优先映射物理节点平均资源承载能力大的节点；为了均衡路径上资源使用，考虑路径权重值，并根据每条路径的权重值对虚拟链路进行映射，从而降低阻塞率。仿真结果表明，所提算法能有效降低阻塞率，提高资源利用率。Abstract: In order to address the problems of the high bandwidth blocking probability and imbalance resources consumption in physical network during virtual optical network mapping, Fragmentation-Aware based on time and spectrum domain of Virtual Network Mapping (FA-VNM) algorithm is proposed. In the FA-VNM algorithm, the fragments problem in the time domain and the spectrum domain is considered. Fragment formula jointly considering the time fragment and spectrum fragment is devised to minimize the spectrum fragments. Further, in order to balance the network resources consumption, based on the FA-VNM, Load Balancing based on degree of Virtual Network Mapping (LB-VNM) algorithm is proposed. In the stage of node mapping, physical node average resource carrying capacity is introduced and the physical node with larger average resources carrying capacity is mapped first. In order to balance the resource consumption in physical path, weight value of physical path is calculated in the stage of link mapping. Then, according to the weight value of each physical path, virtual links are mapped to achieve the purpose of load balancing for reduce the blocking rate. Simulation results show that the algorithms can effectively reduce the blocking rate and improve the resources utilization.
-
表 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
表 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 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
-
刘焕淋, 岁蒙, 徐一帆, 等. 基于距离自适应和有效共享路径感知的光疏导方法[J]. 电子与信息学报, 2015, 37(8): 1955–1970 doi: 10.11999/JEIT141442LIU Huanlin, SUI Meng, XU Yifang, et al. Method of optical grooming for distance-adaptive and effective sharing path-aware[J]. Journal of Electronics&Information Technology, 2015, 37(8): 1955–1970 doi: 10.11999/JEIT141442 刘焕淋, 李瑞艳, 孔德谦, 等. 基于多目标遗传算法优化弹性光网络的多路径保护机制[J]. 电子与信息学报, 2016, 38(9): 2261–2267 doi: 10.11999/JEIT151384LIU Huanlin, LI Ruiyan, KONG Deqian, et al. Optimization survivable multipath provisioning based on NSGA-II algorithm for elastic optical networks[J]. Journal of Electronics&Information Technology, 2016, 38(9): 2261–2267 doi: 10.11999/JEIT151384 PAOLUCCI F, CUGINI F, FRESI F, et al. Super filter technique in SDN-controlled elastic optical networks[Invited][J].Journal of Optical Communications and Networking, 2015, 7(2): A285–A292 doi: 10.1364/JOCN.7.00A285 WANG Yan, JIN Yaohui, GUO Wei, et al. Virtualized optical network services across multiple domains for grid applications[J]. IEEE Communications Magazine, 2011, 49(5): 92–101 doi: 10.1109/MCOM.2011.5762804 YE Zelong, ZHU Yuqing, JI P N, et al. Virtual infrastructure mapping in software-defined elastic optical networks[J]. Photonic Network Communications, 2016, 34(1): 1–11 doi: 10.1007/s11107-016-0678-4 DUBOIS D J and CALSE G. Autonomic provisioning and application mapping on spot cloud resource[C]. International Conference on Cloud and Autonomic Computing, Boston, USA, 2015: 57–68. CHEN Bowen, ZHANG Jie, XIE Weisheng, et al. Cost-effective survivable virtual optical network mapping in flexible bandwidth optical networks[J]. Journal of Lightwave Technology, 2016, 34(10): 2398–2412 doi: 10.1109/JLT.2016.2530846 GAO Xiujiao, YE Zelong, ZHONG Weida, et al. Multicast service-oriented virtual network mapping over elastic optical networks[C]. IEEE International Conference on Communications, London, UK, 2015: 5174–5179 WANG Hongxiang, ZHAO Jingxi, LI Hui, et al. Opaque virtual optical network mapping algorithms based on available spectrum adjacency for elastic optical networks[J]. Science China Information Sciences, 2016, 59(4): 1–11 doi: 10.1107/s11432-016-5525-9 GONG Long and ZHU Zuqing. Virtual Optical Network Embedding (VONE) over elastic optical networks[J]. Journal of Lightwave Technology, 2014, 32(3): 450–460 doi: 10.1109/JLT.2013.2294389 WANGH Hongxiong, XIN Xin, ZHANG Jiawei, et al. Dynamic virtual optical network mapping based on switching capability and spectrum fragmentation in elastic optical networks[C]. Optoelectronics and Communications Conference, Niigata, Japan, 2016: 3–7. -
下载:
图(6) / 表(3)
计量
- 文章访问数: 2149
- HTML全文浏览量: 427
- PDF下载量: 48
- 被引次数: 0
