高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

弹性光网络中时延感知的降级恢复路由与频谱分配算法

于存谦 张黎 何荣希 李靖宇

于存谦, 张黎, 何荣希, 李靖宇. 弹性光网络中时延感知的降级恢复路由与频谱分配算法[J]. 电子与信息学报, 2020, 42(10): 2420-2428. doi: 10.11999/JEIT190759
引用本文: 于存谦, 张黎, 何荣希, 李靖宇. 弹性光网络中时延感知的降级恢复路由与频谱分配算法[J]. 电子与信息学报, 2020, 42(10): 2420-2428. doi: 10.11999/JEIT190759
Cunqian YU, Li ZHANG, Rongxi HE, Jingyu LI. Delay-aware Degradation-recovery Routing and Spectrum Allocation Algorithm in Elastic Optical Networks[J]. Journal of Electronics and Information Technology, 2020, 42(10): 2420-2428. doi: 10.11999/JEIT190759
Citation: Cunqian YU, Li ZHANG, Rongxi HE, Jingyu LI. Delay-aware Degradation-recovery Routing and Spectrum Allocation Algorithm in Elastic Optical Networks[J]. Journal of Electronics and Information Technology, 2020, 42(10): 2420-2428. doi: 10.11999/JEIT190759

弹性光网络中时延感知的降级恢复路由与频谱分配算法

doi: 10.11999/JEIT190759
基金项目: 国家自然科学基金(61371091, 61801074),中国博士后科学面上基金(2019M661074),辽宁省自然科学基金(2019-BS-021),中央高校基本科研业务费(3132020205, 3132019221)
详细信息
    作者简介:

    于存谦:男,1983年生,博士,副教授,研究方向为光数据中心网络

    张黎:女,1992年生,硕士,研究方向为弹性光网络

    何荣希:男,1971年生,博士,教授,研究方向为光网络和无线网络技术

    李靖宇:女,1995年生,硕士生,研究方向光数据中心网络

    通讯作者:

    何荣希 hrx@dlmu.edu.cn

  • 中图分类号: TN929.11

Delay-aware Degradation-recovery Routing and Spectrum Allocation Algorithm in Elastic Optical Networks

Funds: The National Natural Science Foundation of China (61371091, 61801074), Chian General Fundation for Postdoctoral Science (2019M661074), The Natural Science Foundation of Liaoning Province (2019-BS-021), The Fundamental Research Funds for The Central Universities (3132020205, 3132019221)
  • 摘要: 移动云计算、人工智能(AI)、5G等新兴技术应用促使弹性光网络(EON)在骨干传输网中发挥更重要的角色,降级服务(DS)技术为降低EON的业务阻塞率、提高频谱利用率提供了新途径。该文首先对现有DS算法的资源分配不公、忽略低等级业务的体验质量(QoE)等问题,建立了以最小化降级频次、降级等级与传输时延损失(TDL)为联合优化目标的混合整数线性规划(MILP)模型,并提出一种时延感知的降级恢复路由与频谱分配(DDR-RSA)算法。为提高降级业务的QoE和运营商收益,在算法的最优DS窗口选择阶段中融入降级恢复策略,在保障传输数据量不变的前提下,将降级业务向空闲频域复原,从而提高频谱效率、减小降级业务TDL和最大化网络收益。最后,通过仿真证明了所提算法在业务阻塞率、网络收益和降级业务成功率等方面的优势。
  • 图  1  降级恢复举例

    图  2  4种算法的数据量阻塞率

    图  3  3种算法的降级服务成功率

    图  4  3种算法的平均延迟时间

    图  5  4种算法的网络收益

    图  6  3种算法的降级等级占比

    表  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}$的空闲频谱窗口,其频谱槽首、末序号为be,时长为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
  • [1] 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
    [2] 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.
    [3] 朱丹, 徐威远, 陈文娟, 等. 基于光波分复用网络的分布式多目标定位系统[J]. 雷达学报, 2019, 8(2): 171–177. doi:  10.12000/JR19028

    ZHU 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
    [4] 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.
    [5] 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
    [6] 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
    [7] 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
    [8] 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.
    [9] 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.
    [10] 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.
    [11] 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
    [12] 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.
    [13] 于存谦, 张黎, 何荣希. 弹性光网络基于区分降级服务和自适应调制的动态路由与频谱分配算法[J]. 电子与信息学报, 2019, 41(1): 38–45. doi:  10.11999/JEIT180075

    YU 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
    [14] 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
    [15] 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.
    [16] 张海波, 李虎, 陈善学, 等. 超密集网络中基于移动边缘计算的任务卸载和资源优化[J]. 电子与信息学报, 2019, 41(5): 1194–1201. doi:  10.11999/JEIT180592

    ZHANG 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
  • [1] 刘焕淋, 杜理想, 陈勇, 胡会霞.  串扰感知的空分弹性光网络频谱转换器稀疏配置和资源分配方法, 电子与信息学报. doi: 10.11999/JEIT190533
    [2] 刘焕淋, 杜理想, 陈勇, 王展鹏.  基于灾难预测多区域故障的虚拟光网络生存性映射, 电子与信息学报. doi: 10.11999/JEIT190561
    [3] 刘焕淋, 胡浩, 熊翠连, 陈勇, 向敏, 马跃.  基于时频联合碎片感知的资源均衡虚拟光网络映射算法, 电子与信息学报. doi: 10.11999/JEIT171208
    [4] 刘焕淋, 吕磊, 陈勇, 蔚承英, 胡浩.  节点重要性感知的透明虚拟光网络协同映射策略, 电子与信息学报. doi: 10.11999/JEIT171096
    [5] 刘焕淋, 易鹏飞, 张明佳, 陈勇.  最小故障风险损失的弹性光网络多链路故障概率保护策略, 电子与信息学报. doi: 10.11999/JEIT161159
    [6] 刘焕淋, 张明佳, 陈勇, 王欣.  频谱可用性和保护带宽共享度感知的弹性光网络生存性多路径策略, 电子与信息学报. doi: 10.11999/JEIT161374
    [7] 刘焕淋, 杜君丹, 易鹏飞, 陈勇, 张明佳.  弹性光网络中面向可靠性的链路故障概率保护与保护资源重配置策略, 电子与信息学报. doi: 10.11999/JEIT170150
    [8] 刘焕淋, 熊翠连, 陈勇.  频谱效率优先的任播路由冲突感知的弹性光网络资源重配置, 电子与信息学报. doi: 10.11999/JEIT161093
    [9] 刘焕淋, 李瑞艳, 孔德谦, 陈勇.  基于多目标遗传算法优化弹性光网络的多路径保护机制, 电子与信息学报. doi: 10.11999/JEIT151384
    [10] 刘焕淋, 徐一帆, 陈勇.  基于频谱感知的业务分割-合并的弹性光网络资源分配策略, 电子与信息学报. doi: 10.11999/JEIT150842
    [11] 田铭, 邬江兴, 兰巨龙, 马腾.  信息中心网络元模块承载的差异化服务模型, 电子与信息学报. doi: 10.11999/JEIT160105
    [12] 蒋小杰, 芮兰兰, 郭少勇, 邱雪松.  一种基于信誉的移动自组网区分服务激励机制, 电子与信息学报. doi: 10.3724/SP.J.1146.2011.01168
    [13] 高昂, 慕德俊, 胡延苏.  Web集群的区分服务与负载均衡策略研究, 电子与信息学报. doi: 10.3724/SP.J.1146.2010.00409
    [14] 甄皓琮, 方旭明, 朱龙杰.  一种基于无线多媒体业务的可升降级QoS动态带宽分配与优化策略, 电子与信息学报.
    [15] 史琰, 刘增基, 盛敏.  区分服务网络中确保业务端到端时延的接纳控制算法研究, 电子与信息学报.
    [16] 魏蛟龙, 肖艳华, 张驰.  一种新的实现区分服务的可扩展缓存管理算法, 电子与信息学报.
    [17] 刘正蓝, 朱淼良, 董亚波.  区分服务中一种TCP友好的公平数据包标记算法, 电子与信息学报.
    [18] 刘金梅, 王思明.  区分服务中AF类的一种调度算法, 电子与信息学报.
    [19] 王茜, 隆克平, 程时端, 张润彤.  区分服务网络的协作可调整RED算法, 电子与信息学报.
    [20] 邬海涛, 隆克平, 程时端, 张润彤.  区分服务网络中的TCP友好公平体系, 电子与信息学报.
  • 加载中
  • 图(6) / 表ll (3)
    计量
    • 文章访问数:  165
    • HTML全文浏览量:  90
    • PDF下载量:  6
    • 被引次数: 0
    出版历程
    • 收稿日期:  2019-09-13
    • 修回日期:  2020-06-15
    • 网络出版日期:  2020-07-17
    • 刊出日期:  2020-10-13

    目录

      /

      返回文章
      返回

      官方微信,欢迎关注