ISSN 
Time Division Multiplexing Elastic Waveband Switching Algorithm Based on Markov Prediction
-
摘要: 研究了时分复用弹性光网络中的业务疏导、路由与频谱分配问题，提出了基于马尔科夫的时隙占用预测机制，设计了相应的时分复用弹性波带交换算法。主要包括：基于端到端同构波带融合和时分复用的路由、频谱、波带与调制格式分配算法RSBMA-EEU-TDM，基于子路径异构波带融合和时分复用的RSBMA算法RSBMA-SBN-TDM，以及基于时分复用均衡的RSBMA算法RSBMA-Balance-TDM。仿真结果表明，基于马尔科夫预测的时分复用弹性波带交换启发式算法表现出良好性能。Abstract: The traffic grooming, routing and spectrum assignment in time-division-multiplexing elastic optical networks are investigated in this paper. The Markov-based mechanism for predicting the future status of consumed time slots is proposed. and the corresponding time-division-multiplexing elastic waveband switching algorithms are designed, including RSBMA-EEU-TDM (Routing, Spectrum, Band and Modulation Allocation based on End-to-End Uniform band merging and Time Division Multiplexing), RSBMA-SBN-TDM (RSBMA based on SuBpath Non-uniform band merging and TDM), and RSBMA-Balance-TDM (RSBMA based on Balance and TDM). Simulation results show the proposed heuristics, Markov-based TDM elastic waveband switching performs well.
-
Keywords:
- elastic optical network /
- Markov prediction /
- TDM /
- waveband switching
-
弹性光网络中，频谱被分割成许多粒度小、相互正交的子载波。通过分配适量子载波完成业务传输，包括业务疏导、路由和频谱分配[1-10]。其中，业务疏导能够实现多个细粒度业务(一组业务)对同一载波资源的共享。此外，为实现更加高效利用频谱的业务疏导，在时分复用弹性光网络中，可为多个业务组分配不同的时隙，使各业务组在不同时间段内占用相同的载波，进一步优化资源利用。
马尔科夫预测模型指出未来情况只与当前状态有关。对于时分复用弹性光网络，在已知业务连接保持时间前提下，通过此模型预测未来业务占用时隙数，方可优化路由与频谱分配。此外，波带交换[11-15]在实现业务疏导、路由和频谱分配基础上，以“多业务信道捆绑”方式，减少光交换端口数量。现有针对弹性光网络业务疏导、路由和频谱分配的工作均未考虑时间预测模型与波带交换的技术融合优势。为此，本文建立基于马尔科夫的时隙占用预测机制，给出相应的时分复用弹性波带交换算法。通过时间预测及波带交换进一步优化时分复用弹性光网络的业务疏导、路由和频谱分配性能。
1. 基于马尔科夫的时隙占用预测机制
动态业务连接请求是随时建立和释放的，这导致频谱占用状态可在业务连接保持时间内变化。可根据离开事件历史信息去预测未来业务占用时隙数，进而完成时隙分配。
占用波带$b'$子载波${F'_s}$的第i个业务连接剩余时间如式(1)所示。其中，$\langle t_a^{i,{{F'}_s},b'},t_h^{i,{{F'}_s},b'}\rangle $分别表示占用波带$b'$子载波${F'_s}$的第i个业务连接建立和保持时间；$\langle {T_a},{T_h}\rangle $分别表示即将到达业务连接建立和保持时间。
$$ \begin{array}{c} {h_{i,{{F'}_s},b'}} = \\ \left\{ \begin{array}{l} t_a^{i,{{F'}_s},b'} + t_h^{i,{{F'}_s},b'} - {T_a}{\rm{ 若}}(t_a^{i,{{F'}_s},b'} + t_h^{i,{{F'}_s},b'}) \le ({T_a} + {T_h})\\ {T_h}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{否则}} \end{array} \right. \end{array} $$ (1) 对业务连接剩余时间$h_{i,{{F'}_s},b'}^{}$排序(值小者为最先离开事件)，则波带$b'$子载波${F'_s}$上即将到达业务连接保持时间${T_h}$内的离开事件序列${\tau _{{{F'}_s},b'}} = \left\{ {0,{h_{1,{{F'}_s},b'}},{h_{2,{{F'}_s},b'}}, \cdots ,{h_{\left| L \right|,{{F'}_s},b'}}} \right\}{\rm{ = }}\{ {\tau _{0,{{F'}_s},b'}},{\tau _{1,{{F'}_s},b''}},{\tau _{2,{{F'}_s},b'}}, \cdots ,$${\tau _{\left| L \right|,{{F'}_s},b'}}\} $。在波带$b'$子载波${F'_s}$上两个离开事件时间间隔$\Delta {\tau _{k,{{F'}_s},b'}} = ({\tau _{k,{{F'}_s},b'}} - {\tau _{k - 1,{{F'}_s},b'}})$。$\Delta {\tau _{k,{{F'}_s},b'}}$内子载波${F'_s}$上时隙占用情况${v_{{{F'}_s},b'}}(\Delta {\tau _{k,{{F'}_s},b'}})$与链路(u, v)开销$C_{u,v}^{{{F'}_s},b'}(\Delta {\tau _{k,{{F'}_s},b'}})$随请求离开而实时更新。
为预测时隙占用情况，用马尔科夫链描述业务连接请求的到达与离开，如图 1所示。
用$XX = \left\{ {XX(t):t \geqslant 0} \right\}$表示在波带$b'$子载波${F'_s}$上描述时隙占用进程的均匀连续马尔科夫链。转移矩阵为${\mathit{\boldsymbol{Q}}^{{{F'}_s},b'}}$，$q_{ij}^{{{F'}_s},b'}$表示${\mathit{\boldsymbol{Q}}^{{{F'}_s},b'}}$的第$(i,j)$个元素。式(2)中的$q_i^{{{F'}_s},b'}$表示状态i的速率。
$$q_i^{{{F'}_s},b'} = \sum\limits_{i \ne j} {q_{ij}^{{{F'}_s},b'}} $$ (2) $$\mathit{\boldsymbol{P}}_{u,v}^{{{F'}_s},b'} = \mathit{\boldsymbol{I}} + {\mathit{\boldsymbol{Q}}^{{{F'}_s},b'}}/{\mathit{\boldsymbol{ \boldsymbol{\varLambda} }}_{{{F'}_s},b'}}$$ (3) $$\begin{array}{c} \mathit{\boldsymbol{P}}_{u,v}^{{{F'}_s},b'} = \\ \left[ {\begin{array}{*{20}{c}} {1 - \frac{{\lambda _{u,v}^{b'}}}{{{\Lambda _{{{F'}_s},b'}}}}}&{\frac{{\lambda _{u,v}^{b'}}}{{{\Lambda _{{{F'}_s},b'}}}}}&0& \cdots &0\\ {\frac{\mu }{{{\Lambda _{{{F'}_s},b'}}}}}&{1 - \frac{{\mu + \lambda _{u,v}^{b'}}}{{{\Lambda _{{{F'}_s},b'}}}}}&{\frac{{\lambda _{u,v}^b}}{{{\Lambda _{{{F'}_s},b'}}}}}& \cdots &0\\ {{\kern 1pt} \vdots {\kern 1pt} }&{ \cdots {\kern 1pt} }& \cdots & \cdots &{}\\ 0& \cdots &0&{\frac{{({T_s})\mu }}{{{\Lambda _{{{F'}_s},b'}}}}}&{1 - \frac{{({T_s})\mu }}{{{\Lambda _{{{F'}_s},b'}}}}} \end{array}} \right] \end{array}$$ (4) 用$ZZ = \{ Z{Z_n}:n = 0,1, \cdots \} $表示占用链路$(u,v)$波带$b'$子载波${F'_s}$的离散时间马尔科夫链。在相同状态空间下，它的转移概率矩阵$\mathit{\boldsymbol{P}}_{u,v}^{{{F'}_s},b'}$如式(3)所示，其中${\Lambda _{{{F'}_s},b'}} = {\max _i}\left\{ {q_i^{{{F'}_s},b'}} \right\}$。则$\mathit{\boldsymbol{P}}_{u,v}^{{{F'}_s},b'}$可由式(4)得到。$\lambda _{u,v}^{b'}$表示占用波带$b'$的业务连接请求平均到达率，1/μ表示业务连接保持时间均值，${T_s}$表示每个子载波包含的时隙数，I为单位矩阵。
假设业务$N = \left\{ {N(t):t \geqslant 0} \right\}$到达服从泊松分布，连接保持时间服从指数分布。由于保持时间是独立于连续与离散马尔科夫链的，则有$XX = \{ XX(t):$ $t \geqslant 0\} $与$ZZ = \left\{ {Z{Z_n}:n = 0,1, \cdots } \right\}$等价。
定义$V_{u,v}^{{{F'}_s},b'}(n,j)$为经过n次状态转移后业务占用链路$(u,v)$波带$b'$子载波${F'_s}$上的第$(u,v)$个时隙概率，如式(5)所示。这里，$v(0)$表示初始状态概率，$\mathit{\boldsymbol{P}}_{u,v}^{(n){{F'}_s},b'}$表示占用链路$(u,v)$波带$b'$子载波$(u,v)$的业务n次时隙转移概率矩阵。给出矢量$(u,v)$表示业务在时刻t占用链路$(u,v)$波带$b'$子载波${F'_s}$上的第j个时隙概率。通过对$(u,v)$次转移的业务占用时隙概率求和得出业务在时刻t占用链路$(u,v)$波带$b'$子载波${F'_s}$上的第$j$个时隙概率，如式(6)。
$$V_{u,v}^{{{F'}_s},b'}(n,j) = V(0){P^{(n)\;}}_{u,v}^{{{F'}_s},b'}$$ (5) $$\prod\limits_{u,v}^{{{F'}_s},b'} {(t,j)} = \sum\limits_{n = 0}^\infty {{{\rm{e}}^{ - {\Lambda _{{{F'}_s},b'}}(t)}}} \frac{{{{[{\Lambda _{{{F'}_s},b'}}(t)]}^n}}}{{n!}}V_{u,v}^{{{F'}_s},b'}(n,j)$$ (6) 在时间间隔$\Delta {\tau _{k,Fs',b'}}$内，通过简单递归计算可求得第$j$个时隙平均瞬时转移概率为：
$$\begin{array}{c} \prod\limits_{j,u,v}^{{{F'}_s},b'} {(\Delta {\tau _{k,{{F'}_s},b'}})} = \\ \frac{{\int_{\Delta {\tau _{k,{{F'}_s},b'}}} {\sum\limits_{n = 0}^\infty {{{\rm{e}}^{ - {\Lambda _{{{F'}_s},b'}}(t)}}\frac{{{{[{\Lambda _{{{F'}_s},b'}}(t)]}^n}}}{{n!}}} V_{u,v}^{{{F'}_s},b'}(n,j){\rm{d}}t} }}{{\Delta {\tau _{k,{{F'}_s},b'}}}} = \\ {\kern 1pt} \frac{{\sum\limits_{n = 0}^\infty {\frac{{V_{u,v}^{{{F'}_s},b'}(n,j)}}{{n!}}} \int_{\Delta {\tau _{k,{{F'}_s},b'}}} {{{\rm{e}}^{ - {\Lambda _{{{F'}_s},b'}}(t)}}{{[{\Lambda _{{{F'}_s},b'}}(t)]}^n}} {\rm{d}}t}}{{\Delta {\tau _{k,{{F'}_s},b'}}}} = \\ {\kern 1pt} \frac{{\sum\limits_{n = 0}^\infty {\frac{{V_{u,v}^{{{F'}_s},b'}(n,j)}}{{n!}}} \left\{ {1 - {{\rm{e}}^{ - {\Lambda _{{{F'}_s},b'}}(t)}}\sum\limits_{i = 0}^n {\frac{{{{[{\Lambda _{{{F'}_s},b'}}(t)\Delta {\tau _{k,{{F'}_s},b'}}]}^{(n - i)}}}}{{(n - i)!}}} } \right\}}}{{\Delta {\tau _{k,{{F'}_s},b'}}}}\\ \forall k \end{array}$$ (7) 式中，$\prod\limits_{j,u,v}^{{{F'}_s},b'} {(\Delta {\tau _{k,{{F'}_s},b'}})} $表示在$\Delta {\tau _{k,{{F'}_s},b'}}$时间间隔内第j个时隙的平均瞬时转移概率。那么，子载波状态转移期望为：
$$E_{u,v}^{{{F'}_s},b'}(\Delta {\tau _{k,{{F'}_s},b'}}) = \frac{{\sum\limits_{j = 0}^{{T_s}} {\prod\limits_{j,u,v}^{{{F'}_s},b'} {(\Delta {\tau _{k,{{F'}_s},b'}}) \cdot j} } }}{{{T_s}}}$$ (8) 将每个时间间隔内的子载波占用期望求和，可得链路$(u,v)$波带$b'$子载波${F'_s}$上即将到达业务连接保持时间${T_h}$内可能占用的时隙数为：
$$ \frac{{\sum\limits_{k = 1}^{\left| L \right|} {[E_{u,v}^{{{F'}_s},b'}(\Delta {\tau _{k,{{F'}_s},b'}})\Delta {\tau _{k,{{F'}_s},b'}}]} }}{{{T_h}}} $$ (9) 2. 基于马尔科夫预测的波带交换算法
根据式(9)预测即将到达业务连接保持时间${T_h}$内可能占用的时隙数，并结合系统中已有业务连接求得链路负载。此外，根据式(10)计算链路$(u,v)$负载时，考虑了未来可能占用时隙数及链路中已有业务连接。这里，${\delta _1}$，${\delta _2}$分别表示占用时隙数${\rm{FWU}}_{u,v}^{b',{{F'}_s}}$与链路固有负载${\rm{LD}}_{u,v}^{b',{{F'}_s}}$的权重系数。整条路径开销则可通过式(11)计算。
$$C_{u,v}^{{{F'}_s},b'}({T_h}) = {\delta _1}{\rm{FWU}}_{u,v}^{b',{{F'}_s}} + {\delta _2}({\rm{LD}}_{u,v}^{b',{{F'}_s}} + 1)$$ (10) $$C_l^{{{F'}_s},b'} = \sum\limits_{(u,v) \in l} {C_{u,v}^{{{F'}_s},b'}} ({T_h})$$ (11) 显然，链路开销小者越易被选中。若δ1小于δ2，则优先选择多个业务在不同时隙共享载波资源的链路，则算法所采用的时分复用性能优势更加明显；反之，则优先选择更多业务被同一波带所承载的链路，则算法所采用的波带交换性能优势更加明显。
RSBMA-EEU-TDM算法步骤如下：
1) 输入网络拓扑及网络状态信息。
2) 等待业务连接建立请求。
3) 通过式(9)计算未来可能占用时隙数，从而计算链路负载。通过Dijkstra，根据式(11)为业务计算最短路径，并记录路径长度。
4) 根据路径长度，并结合表 1，选择恰当的最高调制级别。同时根据业务请求速率计算所占用的频隙数。
表 1 调制方式对应最大路径长度关系[7]调制方式 子载波容量/Gbit-1 最大路径长度/km BPSK 12.5 4 000 QPSK 25 2 000 8-QAM 37.5 1 000 16-QAM 50 500 32-QAM 62.5 250 64-QAM 75 125 5) 为业务分配频隙，若频隙不足，则阻塞该业务，并返回步骤2)。
6) 将源与目的节点完全相同的业务传输路径捆绑进同一个波带中，并改变固定(波带)粒度N(波带能容纳的最多业务数)。
7) 计算占用光端口总数及业务阻塞率。
RSBMA-SBN-TDM算法与RSBMA-EEU-TDM算法的步骤类似，仅在步骤6)中将具有相同子路径的业务传输路径捆绑进同一个波带中。
RSBMA-Balance-TDM算法同样采用上述步骤，但根据步骤7)和8)自适应调整波带融合策略。
8) 设置不同的($W$)权重系数，如(0.9, 0.1)(0.6, 0.4)，(0.4, 0.6)及(0.1, 0.9)等，统计综合反映占用光端口总数及频隙占用的性能参数$W$。$W$由式(12)得到。这里，$P$和$Q$分别表示采用和未采用波带融合的占用光端口总数，$\eta $表示占用频隙总数。
$$W{\rm{ = }}\beta \eta {\rm{ + }}\alpha \frac{P}{Q}$$ (12) 9) 比较不同N值下$W$大小，得出使W最小的N值，最优化RSBMA-Balance-TDM算法性能。
注意，融入波带的多条传输路径相互独立，即分配给路径的调制格式和时隙不受其他路径影响。该约束可通过多粒度光交叉器的解/复用器来实现。
3. 实验评估
由于算法求解过程是NP完全的，为了评估所提算法的性能，本文采用如图 2所示的、具有14节点和21条光纤链路的NSFNET拓扑进行仿真实验。基准比较算法是考虑业务疏导的RSA算法[8]。仿真中，本文假定δ1=δ2=0.5，即时分复用和波带交换对算法性能的提升同等重要。
图 3a和图 3b分别为设置权重系数$(\beta ,\alpha )$为$(0.4,0.6)$及$(0.6,0.4)$情况下，综合性能参数W随业务规模增加的变化情况。当$(\beta ,\alpha )$分别为$(0.4,0.6)$和$(0.6,0.4)$时，固定(波带)粒度N取为6的综合性能参数W最小，即系统的综合性能最优。
由于已证明N=6时的RSBMA-Balance-TDM算法可使系统综合性能最优，在随后对RSBMA- Balance-TDM算法的性能分析中，取N=6。
图 3c给出业务请求带宽在12.5～72.5 Gb/s之间随机选取，业务规模在10～50之间变化情况下，RSBMA-EEU-TDM，RSBMA-SBN-TDM，RSBMA- Balance-TDM 3种算法使用的光端口总数的变化情况。由于具有足够的频谱资源为业务提供服务，随着业务规模的逐渐增加，3种算法所使用的光端口总数均呈线性增长趋势。其中，RSBMA-SBN-TDM算法使用的光端口总数最少，而RSBMA-EEU-TDM算法使用的光端口最多。
业务规模在10～100之间的情况下各种算法的业务平均阻塞率如图 3d所示。由图中可以看到，与传统RSA算法及普通RSBMA算法组相比，基于TDM的RSBMA算法组业务平均阻塞率相对较低，其平均改善率可达10%左右。
4. 结束语
本文提出了基于3种不同波带融合策略的时分复用弹性波带交换启发式算法，并进行了仿真分析。仿真数据表明，调整波带粒度可使算法性能(即综合性能参数$W$)达到最优。同时，相比于其他算法，基于相同子路径波带融合策略的算法在使用光端口数量及业务阻塞率方面表现最优，但操作较复杂。通过RSBMA算法组与基于TDM的RSBMA算法组和传统RSA算法的性能对比，证明了基于TDM的RSBMA算法组能更加有效地降低业务阻塞率。
-
[1] ZHANG Liang, ANSARI N, KHREISHAH A. Anycast planning in space division multiplexing elastic optical networks with multi-core fibers[J]. IEEE Communications Letters, 2016, 20(10):1983-1986. DOI: 10.1109/LCOMM.2016.2593479
[2] EIRA A, PEDRO J, PIRES O. Optimized design of shared restoration in flexible-grid transparent optical networks[C]//Proc OFC: the Optical Fiber Communication Conference and Exhibition. [S. l. ]: IEEE, 2012: 1-3.
[3] CHEN Bo-wen, ZHANG Jie, ZHAO Yong-li, et al. Multi-link failure restoration with dynamic load balancing in spectrum-elastic optical path networks[J]. Optical Fiber Technology, 2012, 18(1):21-28. DOI: 10.1016/j.yofte.2011.10.002
[4] GUO Hong, SHEN Gang-xiang, BOSE S K. Routing and spectrum assignment for dual failure path protected elastic optical networks[J]. IEEE ACCESS, 2016, 4:5143-5160. DOI: 10.1109/ACCESS.2016.2599511
[5] SHAO Xu, YEO Y K, XU Zhao-wen, et al. Shared-path protection in OFDM-based optical networks with elastic bandwidth allocation[C]//Proc OFC: the Optical Fiber Communication Conference and Exhibition. [S. l. ]: IEEE, 2012: 1-3.
[6] ZHANG Guo-ying, LEENHEER M D, MOREA A. A survey on ofdm-based elastic core optical networking[J]. IEEE Communications Surveys & Tutorials, 2013, 15(1):65-87.
[7] CAI An-linag, GUO Jun, LIN Rong-ping, et al. Multicast routing and distance-adaptive spectrum allocation in elastic optical networks with shared protection[J]. IEEE/OSA Journal of Lightwave Technology, 2016, 34(17):4076-4088. DOI: 10.1109/JLT.2016.2592999
[8] ROTTONDI C, TORNATORE M, PATTAVINA A. Traffic grooming and spectrum assignment for coherent transceivers in metro-flexible networks[J]. IEEE Photonics Technology Letters, 2013, 25(12):183-186.
[9] VIZCAíNO J L, YE Ya-bin, MONROY I T. Energy efficiency analysis for flexible-grid OFDM-based optical networks[J]. Computer Networks, 2012, 16(2):2400-2419.
[10] OHBA T, ARAKAEA S, MURATA M. Virtual network reconfiguration in elastic optical path networks for future bandwidth allocation[J]. IEEE/OSA Journal of Optical Communications and Networking, 2016, 8(9):633-644. DOI: 10.1364/JOCN.8.000633
[11] WANG Yang, CAO Xiao-jun. Multi-granular optical switching:a classified overview for the past and future[J]. IEEE Communication Survey & Tutorials, 2012, 14(3):698-713. https://www.researchgate.net/publication/224140674_Distributive_waveband_assignment_in_multi-granular_optical_networks
[12] KARUBE R, TAKANO K, ITO T, et al. The impact of waveband size on the number of ports of cross-connect in waveband switching networks[C]//Proc ACP: 2010 Asia Communications and Photonics Conference and Exhibition. [S. l. ]: IEEE, 2010: 254-255.
[13] VARMA S, JUE J P. Spectrum and waveband assignment in elastic optical waveband networks[C]//Proc GLOBECOM: 2012 IEEE Global Communications Conference. [S. l. ]: IEEE, 2012: 2901-2906.
[14] HOU W, NING Z L, GUO Z, et al. Novel framework of risk-aware virtual network embedding in optical data center networks[J]. IEEE Systems Journal, DOI: 10.1109/JSYST.2017.2673828.
[15] HOU W, NING Z L, GUO Z, et al. Green survivable collaborative edge computing in smart cities[J]. IEEE Transactions on Industrial Informatics, DOI: 10.1109/TⅡ.2018.2797922.
-
期刊类型引用(0)
其他类型引用(1)
下载:
计量
- 文章访问数: 5085
- HTML全文浏览量: 1583
- PDF下载量: 144
- 被引次数: 1