Delay-aware Degradation-recovery Routing and Spectrum Allocation Algorithm in Elastic Optical Networks
-
摘要: 移动云计算、人工智能(AI)、5G等新兴技术应用促使弹性光网络(EON)在骨干传输网中发挥更重要的角色，降级服务(DS)技术为降低EON的业务阻塞率、提高频谱利用率提供了新途径。该文首先对现有DS算法的资源分配不公、忽略低等级业务的体验质量(QoE)等问题，建立了以最小化降级频次、降级等级与传输时延损失(TDL)为联合优化目标的混合整数线性规划(MILP)模型，并提出一种时延感知的降级恢复路由与频谱分配(DDR-RSA)算法。为提高降级业务的QoE和运营商收益，在算法的最优DS窗口选择阶段中融入降级恢复策略，在保障传输数据量不变的前提下，将降级业务向空闲频域复原，从而提高频谱效率、减小降级业务TDL和最大化网络收益。最后，通过仿真证明了所提算法在业务阻塞率、网络收益和降级业务成功率等方面的优势。Abstract: Emerging technology applications such as mobile cloud computing, Artificial Intelligence (AI) and 5G promot Elastic Optical Network (EON) to play an important role in the backbone transmission network. Degraded Service (DS) technology can provide a new way to reduce traffic congestion and improve spectrum utilization in EON. Firstly, considering the problems of unfair resource allocation and neglecting the Quality of Experience (QoE) of low-priority services in existing DS algorithms, a Mixed Integer Linear Program (MILP) model with the joint objective of minimizing downgrade frequency, downgrade level and Transmission Delay Loss (TDL) is established. A Delay-aware Degradation-Recovery Routing and Spectrum Assignment (DRR-RSA) algorithm for degraded recovery is proposed. In order to improve the QoE of downgraded services and the revenue of operators, the strategy of degradation recovery is integrated in the optimal DS-window selection phase of the algorithm. Under the premise of guaranteeing the transmission data quantity unchanged, the degradable services are restored to the free spectrum domain, so as to increase the spectrum efficiency, reduce degraded service TDL and maximize revenue. Finally, the simulation results tesfity that the proposed algorithm has advantages in terms of traffic congestion, revenue and degraded service success-rate.
-
表 1 RSA问题符号定义
变量 定义内容 $\overline \omega $ 正整数，$\psi $中的业务优先级上界； ${w_r}$ 正整数，$r$所在的起始频谱槽序号； $f_{u,v}^r$ 二值变量，若$r$经过光纤链路$e(u,v) \in E$，则$f_{u,v}^r = 1$；否则$f_{u,v}^r = 0$； ${\rho _{i,j}}$ 二值变量，若${r_i}$和${r_j}$经过同一段光纤链路，且${w_i}$比${w_j}$小，则${\rho _{i,j}} = 1$；否则${\rho _{i,j}} = 0$； $\xi _{s,u}^r$ 二值变量，若$r$的源节点为$u \in N$，则$\xi _{s,u}^r = 1$；否则，$\xi _{s,u}^1 = 0$； $\xi _{d,v}^r$ 二值变量，若$r$的目的节点为$v \in N$，则$\xi _{d,v}^r = 1$；否则，$\xi _{d,v}^r = 0$； ${\delta _r}$ 二值变量，若$r$降级，则${\delta _r} = 1$；否则，${\delta _r}{\rm{ = 0}}$； ${\chi _r}$ 正整数，r释放的频谱槽数； ${\beta _r}$ 正整数，r恢复的频谱槽数； ${v_r}$${z_r}$ 正整数，DR后r首/尾频谱槽序号； $q_k^e$ 正实数，第k个频谱槽可被r用来DR的起始时间； $t_r^{{\rm{end}}'}$ 正实数，r被降级后的离开时间。 
下载: 导出CSV
表 2 启发式算法部分的变量
变量 定义内容 $u_{t,c}^{l,k}$ 二值变量，若${p_k}$中第$l$条链路的第$c$位频谱槽的第t时隙被占用，则$u_{t,c}^{l,k} = 1$；否则$u_{t,c}^{l,k} = 0$； $u_{t,c}^p$ 二值变量，若${p_k}$的第$c$位频谱槽的第$t$时隙被占用，则$u_{t,c}^p = 1$；否则，$u_{t,c}^p = 0$； $B_{b,e}^{k,h}$ ${p_k}$的空闲频谱窗口，其频谱槽首、末序号为b、e，时长为h，含频谱槽数为$n_{b,e}^{k,h} = e - b + 1$； $\tau _{b,e}^{k,h}$ 正整数，$B_{b,e}^{k,h}$为满足$r$的带宽尚需的频谱槽数； ${\chi _{r'}}$ 正实数，降级业务$r'$释放的频谱槽数； $\tau _{b,e}^{{\rm{left}},l}$,$\tau _{b,e}^{{\rm{right}},l}$ 正整数，$B_{b,e}^{k,h}$的每条链路上$[b - \tau _{b,e}^{k,h},b)$或$(e,e + \tau _{b,e}^{k,h}]$内最少可释放的频谱槽数，$l \in {p_k}$； $\tau _{b,e}^{{\rm{left}}}$,$\tau _{b,e}^{{\rm{right}}}$ 正整数，$B_{b,e}^{k,h}$所在路径上$[b - \tau _{b,e}^{k,h},b)$或$(e,e + \tau _{b,e}^{k,h}]$内可释放的频谱槽数； ${b_{r'}}$ 正整数，可降级业务$r'$占用的带宽； ${\rm{ho}}{{\rm{p}}_{r'}}$ 正整数，$r'$所在路径的链路数； $\theta _{r'}^{{\chi _{r'}}}$ 正实数，$r'$释放的数据量； $\left[ {s,d} \right]$ $r'$占用的频谱，有$d - s + 1 = {b_{r'}}$； $\theta _t^{r'}$ 正实数，$r'$在第t时隙可恢复的数据量； $\theta _{r'}'$ 正实数，$r'$可恢复数据量之和； $t_{r'}^{{\rm{end}}'}$ 正实数，$r'$降级后的离去时间。 $[b - \tau _{b,e}^{k,h},b),$$(e,e + \tau _{b,e}^{k,h}]$ $B_{b,e}^{k,h}$的左/右两侧的降级备选区间； $[s - {\chi _{r'}},d - {\chi _{r'}}],$$[s + {\chi _{r'}},d + {\chi _{r'}}]$ $r'$左/右两侧分别可恢复的频域；
下载: 导出CSV
表 3 DR策略伪码
输入：$\psi $, ${{G}}\left( {N,E,C} \right)$. 输出：$t_{r'}^{{\rm{end}}'}$ and ${\chi _{r'}}$. (1) if ${o_{r'}} < {o_r}$ then (2) $t_{r'}^{{\rm{end}}'} \leftarrow t_{r'}^{{\rm{end}}}$, ${\chi _{r'}} \leftarrow 0$; calculate ${\chi _{r'}}$, $\theta _{r'}^{{\chi _{r'}}}$ in
$[b - \tau _{b,e}^{k,h},b) \cup (e,e + \tau _{b,e}^{k,h}]$;(3) ${\left[ {{{S}}_k^p} \right]_{{\rm{T}} \times \left| {\rm{C}} \right|}} \leftarrow {\left[ {{{U}}_k^l} \right]_{{\rm{T}} \times \left| {\rm{C}} \right|}}$ in
$\left[ {s + {\chi _{r'}},d + {\chi _{r'}}} \right] \cup \left[ {s - {\chi _{r'}},d - {\chi _{r'}}} \right]$;(4) while $t \ge t_r^a$ and $t \le {\overline \alpha _{r'} }$ do (5) for $u_{t,c}^{{p_{r'}}} = 0$ do $\theta _t^{r'} \leftarrow $ Eq.24, $c + + $; end for (6) if $u_{t,c}^{{p_{r'}}} = 1$ then (7) if $c \ge c'$ in $u_{t - 1,c'}^{{p_{r'}}} = 1$ then calculate
$\theta _{r'}' \leftarrow $Eq.25, t++;(8) else then (9) $\theta _{r'}' \leftarrow $ Eqs. 24-25($\left( {c,d - {\chi _{r'}}} \right]$ or
$\left[ {s + {\chi _{r'}},c} \right)$), t++;(10) end if (11) end if (12) if $\theta _{r'}' \ge \theta _{r'}^{ {\chi _{r'} } }$ then return $t_{r'}^{{\rm{end}}'}$ and ${\chi _{r'}}$; end if (13) end while (14) if $\theta _{r'}' < \theta _{r'}^{{\chi _{r'}}}$ then set${\chi _{r'}} = {\chi _{r'}} - 1$; jump to
Line 1; end if(15) if ${\chi _{r'}} = = 0$ then return 0; end if (16) end if
下载: 导出CSV
-
ZHU Zuqing, LU Wei, ZHANG Liang, et al. Dynamic service provisioning in elastic optical networks with hybrid single-/multi-path routing[J]. Journal of Lightwave Technology, 2013, 31(1): 15–22. doi: 10.1109/JLT.2012.2227683 GU Yamei, YUAN Xin, and YOU Shanhong. Blocking performances for fixed/flexible-grid and sub-band conversion in optical networks[C]. 2014 IEEE/CIC International Conference on Communications in China, Shanghai, China, 2014: 116–120. doi: 10.1109/ICCChina.2014.7008254. 朱丹, 徐威远, 陈文娟, 等. 基于光波分复用网络的分布式多目标定位系统[J]. 雷达学报, 2019, 8(2): 171–177. doi: 10.12000/JR19028ZHU Dan, XU Weiyuan, CHEN Wenjuan, et al. Distributed multi-target localization system based on optical wavelength division multiplexing network[J]. Journal of Radars, 2019, 8(2): 171–177. doi: 10.12000/JR19028 SAVAS S S, HABIB M F, TORNATORE M, et al. Exploiting degraded-service tolerance to improve performance of telecom networks[C]. Optical Fiber Communication Conference, San Francisco, USA, 2014: W2A. 31. doi: 10.1364/OFC.2014.W2A.31. MUHAMMAD A, CAVDAR C, WOSINSKA L, et al. Service differentiated provisioning in dynamic WDM networks based on set-up delay tolerance[J]. Journal of Optical Communications and Networking, 2013, 5(11): 1250–1261. doi: 10.1364/JOCN.5.001250 SAVAS S S, HABIB M F, TORNATORE M, et al. Network adaptability to disaster disruptions by exploiting degraded-service tolerance[J]. IEEE Communications Magazine, 2014, 52(12): 58–65. doi: 10.1109/MCOM.2014.6979953 VADREVU C S K, WANG Rui, TORNATORE M, et al. Degraded service provisioning in mixed-line-rate WDM backbone networks using multipath routing[J]. IEEE/ACM Transactions on Networking, 2014, 22(3): 840–849. doi: 10.1109/TNET.2013.2259638 ZHONG Zhizhen, LI Jipu, HUA Nan, et al. On QoS-assured degraded provisioning in service-differentiated multi-layer elastic optical networks[C]. 2016 IEEE Global Communications Conference, Washington, USA, 2016: 1–5. doi: 10.1109/GLOCOM.2016.7842043. SANTOS A S, HOROTA A K, ZHONG Zhizhen, et al. An online strategy for service degradation with proportional QoS in elastic optical networks[C]. 2018 IEEE International Conference on Communications, Kansas City, USA, 2018: 1–6. doi: 10.1109/ICC.2018.8422781. HOU Weigang, GUO Lei, NING Zhaolong, et al. Appropriate service degradability for virtualized inter-data-center optical networks[C]. 2018 IEEE Global Communications Conference, Abu Dhabi, UAE, 2018: 206–212. doi: 10.1109/GLOCOM.2018.8647198. HOU Weigang, NING Zhaolong, GUO Lei, et al. Service degradability supported by forecasting system in optical data center networks[J]. IEEE Systems Journal, 2019, 13(2): 1514–1525. doi: 10.1109/JSYST.2018.2821714 ROJAS J S, GALLÓN Á R, and CORRALES J C. Personalized service degradation policies on OTT applications based on the consumption behavior of users[C]. The 18th International Conference on Computational Science and Its Applications, Melbourne, Australia, 2018: 543–557. doi: 10.1007/978-3-319-95168-3_37. 于存谦, 张黎, 何荣希. 弹性光网络基于区分降级服务和自适应调制的动态路由与频谱分配算法[J]. 电子与信息学报, 2019, 41(1): 38–45. doi: 10.11999/JEIT180075YU Cunqian, ZHANG Li, and HE Rongxi. Dynamic routing and spectrum assignment algorithm based on differentiated degraded-service and adaptive modulation in elastic optical networks[J]. Journal of Electronics &Information Technology, 2019, 41(1): 38–45. doi: 10.11999/JEIT180075 YANG Anjia, WENG Jian, CHENG Nan, et al. DeQoS attack: Degrading quality of service in VANETs and its mitigation[J]. IEEE Transactions on Vehicular Technology, 2019, 68(5): 4834–4845. doi: 10.1109/TVT.2019.2905522 PROTO S, VENTURA F, APILETTI D, et al. PREMISES, a scalable data-driven service to predict alarms in slowly-degrading multi-cycle industrial processes[C]. 2019 IEEE International Congress on Big Data, Milan, Italy, 2019: 139–143. doi: 10.1109/BigDataCongress.2019.00032. 张海波, 李虎, 陈善学, 等. 超密集网络中基于移动边缘计算的任务卸载和资源优化[J]. 电子与信息学报, 2019, 41(5): 1194–1201. doi: 10.11999/JEIT180592ZHANG Haibo, LI Hu, CHEN Shanxue, et al. Computing offloading and resource optimization in ultra-dense networks with mobile edge computation[J]. Journal of Electronics &Information Technology, 2019, 41(5): 1194–1201. doi: 10.11999/JEIT180592 -
下载:
图(6) / 表(3)
计量
- 文章访问数: 1815
- HTML全文浏览量: 483
- PDF下载量: 49
- 被引次数: 0
