-
文中提出的基于强化学习的深度路由波长分配算法DeepRWA总体结构如图2所示,算法采用SDN架构,由光网络模块、 控制器、强化学习模块三部分组成。SDN本地控制器作为核心,首先根据数据平面获得网络状态和光路请求,利用深度强化学习算法生成RWA策略然后下发至数据平面。光网络模块主要由光分叉复用器作为节点,节点间相互连接形成拓扑;SDN控制器是光网络模块和强化学习模块的桥梁,可以感知光网络信息、波长使用情况、业务请求信息,为光网络提供高效的路由与波长分配策略;强化学习模块利用控制器收集的信息进行训练,把生成包括路由路径和选用波长的动作发送至控制器模块。DeepRWA工作过程是通过SDN智能控制光传送网的数据平面, DeepRWA具体实现步骤如下:
(1) SDN本地代理首先收到主机发出的光路请求Rt;
(2) SDN控制器获得网络拓扑信息和光路请求信息,调用特征处理模型产生DeepRWA的状态信息,其中包括可选路由和每条路由的波长使用信息;
(3) DeepRWA强化学习模块通过神经网络读取状态st ,利用A3C算法迭代训练,将神经网络的输出作为RWA策略发送至SDN控制器;
(4)控制器将RWA策略下发至本地代理,由本地代理执行相应的路由和波长分配策略,即DeepRWA的动作;
(5)奖励系统将获得以往的历史奖励作为反馈和生成DeepRWA的即时奖励rt;
(6)存储即时奖励、动作和状态三个元素数据至经验池;
(7)利用经验池的数据训练策略神经网络和价值神经网络,更新神经网络的参数,利用策略神经网络获取RWA策略。RWA策略是选择策略神经网络中概率最大的动作。
-
文中提出DeepRWA的核心是基于强化学习的路由波长优化算法,而强化学习关键是设计状态、动作和奖励,文中具体设计如下:
(1)状态:针对拓扑中的单业务请求,使用特定的矩阵表示状态st信息和候选路径的波长使用情况,文中状态设定如图3所示,其中图3(a)为光网络拓扑;图3(b)为光网络链路的波长使用示意图,定义状态为1×(2 |V|+1+2JK)大小的矩阵,如公式(1)所示:
$$ s_{t}=\left\{o, d, \tau,\left\{z^{1, j}_{\,\,\,\,\,\,\, k}, z_{\,\,\,\,\,\,\,k}^{2, j}\right\}\right\} $$ 式中:o、d和τ表示业务请求的源节点、目的节点和服务时长;k∈[1, 2, ··· , K],j∈[1, 2, ··· , J],K为业务请求的所有候选路由数(如图3(a)虚线部分),J表示某条路由所有可用波长段(单个可用波长段至少包含一个可用波长且波长段内的所有波长位置连续,如图3(b)中白色部分),V表示拓扑的节点数。候选路由数目的不同会导致状态的不同,因此需采用一个固定的候选路由数目。强化学习可以通过探索多条候选路由获得更大的收益,然而收敛时间也会更长。候选路由数太少,强化学习的收益较小;候选路由数太多,算法收敛速度慢,文中参考文献[15]的设置,即K=5。
$\left\{z_{\,\,\,\,\,\,\, k}^{1, j}, z_{\,\,\,\,\,\,\, k}^{2, j}\right\}$ 表示业务请求某条候选路由的未占用波长分布情况,$z^{1, j}_{\,\,\,\,\,\,\, k},$ 表示第k条路由第j段波长可用波长的数量,$z^{2, j}_{\,\,\,\,\,\,\, k},$ 表示第k条路由第j段波长第一个可用波长的索引。具体实例见图3(a)中,假设业务有两条路由可选,1-2-4为路由1 (k=1),1-3-5-4为路由2 (k=2)。图3(b)中两条路由1、2的波长使用情形分上下两部分,上方路由1的第1段波长可用波长数量$z_{\,\,\,\,1}^{1,1}= 3$ ,路由1的第1段波长可用波长集合的起始索引$z_{\,\,\,\,1}^{2,1}=0 $ ;路由1的第2段波长可用波长数量$z_{\,\,\,\,1}^{1,2} =3$ ,路由1的第2段波长可用波长集合的起始索引$z_{\,\,\,\,1}^{2,2}=9 $ ;下方路由2第1段波长的可用波长数量$z_{\,\,\,\,2}^{1,1}=4$ ,路由2第1段波长的可用波长集合的起始索引$z_{\,\,\,\,2 }^{2,1}=2$ ;路由2第2段波长的可用波长数量$z_{\,\,\,\,2}^{1,2}=4$ ,路由2第2段波长的可用波长集合的起始索引$z_{\,\,\,\,2}^{2,2}=8 $ 。因此图3的状态表示为:$S_{t}= \left\{o, d, \tau , z_{\,\,\,\,1}^{1,1} \sim z_{\,\,\,\,1}^{2,2}, \quad z_{\,\,\,\,2}^{1,1} \sim z_{\,\,\,\,2}^{2,2}\right\}$ 。(2)动作:动作空间需要对光网络中业务的路由和波长进行部署,每一个动作就是代表一种路由与波长分配方案。对于一个业务请求,DeepRWA算法从光网路拓扑的K条候选路径选择一个路由路径,根据状态计算可选波长数I,从I个可选波长选择一个可用波长传输数据,因此动作空间包含K*I个动作。
(3)奖励:奖励的设定对算法的收敛速度和动作决策都有很大影响。由于动态RWA问题的优化目标是最小化阻塞率,所以用业务的成功率衡量该动作的价值。即时奖励作为一个标记,记录当前业务请求是否成功。DeepRWA算法如果成功地使一个业务通过光网络传输,即路由与波长分配成功,此时即时奖励rt=1,否则rt=−1。即时奖励为1时,表明代理在状态S下执行动作a策略会更好,有助于策略的收敛;即时奖励为−1时,表明代理在状态S下执行动作a策略比较差,不利于策略的收敛。DeepRWA中神经网络不断迭代使累积收益Γ最大化,累积收益如公式(2)所示:
$$ {\varGamma _t} = {\displaystyle \sum\limits_{t' \in [t,\infty ]} \gamma ^{t' - t}} \cdot {r_{t'}} $$ (2) 式中:γ∈[0,1]是未来收益的折扣因子;t'表示未来某个时刻;t表示当前时刻。
-
文中从阻塞率、资源利用率、策略熵、价值损失和运行时间及收敛速度五个方面评价DeepRWA算法的性能。并与现有的算法KSP-FF对比,验证所提出算法的有效性,借鉴参考文献[16]的参数设置,KSP-FF算法的备选路径设为5条,即K=5,下面实验中KSP-FF参数均采用上述设置。
-
仿真实验采用如图4所示的14节点NSFNET拓扑,链路间的数字代表节点间的距离(单位:km)。实验采用动态的业务模型,业务服从泊松分布,服务时间遵循指数分布,具体参数如表1所示,软件配置操作系统选用Ubuntu16.04,GPU为NVIDIAGeforce1080 Ti,CPU为i7-6700 k,程序设计采用python3.7,tensorflow版本为1.14.0。
表 1 仿真实验业务参数
Table 1. Serve parameters of simulation experiment
Parameters Value Average arrival time of dynamic service/s 1/12 Continuing times of dynamic service/s 13 Available wavelength of channel 18 -
(1)阻塞率
动态RWA问题的目标是最小化阻塞率,对比了DeepRWA算法和KSP-FF算法阻塞率指标随业务数变化情况。图5给出了上述两种算法随着业务数增加的变化曲线。从图5可以看出,业务请求数较小时DeepRWA阻塞率较大,为0.16左右。这是因为业务请求数较少时,DeepRWA训练次数较少,没有学习到理想的路由与波长分配策略。当业务请求数达到370000个后,经训练的DeepRWA路由和波长分配方案的阻塞率降到0.01,比KSP-FF算法的阻塞概率近似低0.06。原因是KSP-FF寻找路由只考虑最短路径,遇到无可用波长的链路就会发生阻塞;而DeepRWA在选路过程中考虑路径的跳数及波长占用情况,综合考虑选择一条路径,尽可能避开了拥塞链路。因此,DeepRWA较KSP-FF算法具有更低的(业务)阻塞率。
(2)资源利用率
资源利用率表示被业务利用的资源占总资源的比例,资源利用率越大,代表网络中被充分利用,算法性能会更好。图6比较了DeepRWA算法和KSP-FF算法资源利用率随业务数变化的性能曲线。从图6可以看出,DeepRWA算法资源利用率在训练过程中逐步提高最后趋于稳定。起初资源利用率较低且波动较大,因为随着业务请求数增多,要想服务这些业务,就要不断地分配波长,网络的资源利用率必然呈上升趋势。在训练过程中,业务数较小时资源利用率为0.51,当业务数达到150000后,DeepRWA资源利用率上升至0.59,表1中设定的18个波长平均有10.6个波长被利用;而在KSP-FF算法下,设定的18个波长中平均有10.1个波长被利用。可见DeepRWA的路由和波长策略使光网络中资源利用率超过了KSP-FF算法。图7表示实验环境的其它参数不变,资源利用率随着信道波长数变化关系曲线图。随着信道波长数增加,资源利用率逐渐降低。由于业务强度一定,当信道波长数增加时,链路间空闲信道明显增加。根据资源利用率的定义,它会逐渐降低,使网络拥塞问题有所改善。
(3)策略熵
图8描绘了DeepRWA算法随着业务强度增加策略熵的变化曲线,熵值的变化可以反映所提出的算法是否进行了有效的学习。熵值越大说明算法得到的路由和波长策略不确定性越强;策略熵收敛表明算法的随机性降到最低,模型已经训练完成。当业务强度较小时,熵值较大,生成的路由与波长决策随机性较大;随着业务请求数量的增加,当该算法通过3000000个业务请求后,策略熵收敛,熵值从1.5下降至0.15,说明DeepRWA已经学习到一些规则并可以做出随机性相对较小的路由与波长决策。
(4)价值损失
价值损失函数用于计算价值神经网络预估值和真实值的差距,从而指导下一步的训练向正确的方向进行。价值损失描述的是累积收益与价值函数预测值的接近程度,用于评价算法的优劣。图9描述了价值损失随着训练过程的变化曲线,训练过程中价值损失逐渐降低,训练逐渐稳定。当业务数较少时,选择的路由与波长策略的预测值与累积收益差距较大。随着业务数的增加,训练后算法的预测值逐渐接近于累积收益,当通过450000个业务请求后训练算法的价值损失减少至2.5左右,预测值和累积收益比较接近,表明采取的路由与波长策略比较合适。
(5)运行时间及收敛速度
运行时间是衡量算法时间复杂度的评价指标,运行时间越短表明算法的时间复杂度越小、适应性越好。针对单个业务请求,在业务服从泊松分布、到达率和服务时长的设置同表1时,对比了DeepRWA算法和KSP-FF算法运行时间随波长数变化情况,如图10(a)所示。由图10(a)可知,当信道波长数增加时,两种算法运行时间均明显增加。因为当信道波长数增加时,路由与波长分配策略复杂度增加。但是,随波长数增加,DeepRWA算法运行时间增长的速度明显慢于KSP-FF。当信道中包含18个波长时,与KSP-FF算法相比,DeepRWA算法运行时间增加了0.12 ms;当信道中包含的波长数增加至45时,两种算法的运行时间大致相同;之后,DeepRWA算法运时间优势逐渐明显,当信道中包含的波长数增加至58时,与KSP-FF算法相比,DeepRWA算法运行时间减少了0.07 ms。因此,DeepRWA较KSP-FF算法更适应于波长数较多的光网络。
算法的收敛速度反应了智能体使网络达到最低阻塞率需要的训练时长,也即算法收敛需要的业务数量。使用多线程训练神经网络,线程数的不同也会影响网络收敛速度。文中采用A3C算法,业务服从泊松分布,到达率、服务时长和信道波长数的设置同表1,仿真得到算法收敛所需业务数随线程数变化曲线如图10(b)所示,可以看出当线程数增加时,算法训练至收敛需要的业务数呈指数式减少。当线程数为2时,算法需要690000个业务进行训练;当线程数增加至8时,算法收敛所需的业务数已减少至190000。由此可知,在CPU/GPU支持的最大线程范围内,增加线程数可以明显减少算法的训练时间。
Optimization of routing and wavelength optimization algorithm for optical transport network based on reinforcement learning
-
摘要: 针对光传送网中动态业务的路由和波长问题,提出一种基于强化学习的深度路由波长分配算法DeepRWA。算法基于软件定义网络架构,通过强化学习灵活地调整控制光传送网,实现光网络路由波长分配策略优化。针对路由选择问题,结合链路上的波长使用情况,使用A3C算法选择合适的路由,使得阻塞率最小;针对波长分配问题,使用首次命中算法选择波长。考虑阻塞率、资源利用率、策略熵、价值损失、运行时间及收敛速度等多个指标,利用14节点NSFNET网络拓扑仿真实验。结果表明:当信道中包含18个波长时,与传统KSP-FF算法相比,所提出的路由波长分配算法的阻塞率降低了0.06,资源利用率提高了0.02,但运行时间有增加;在波长数超过45以后,与传统KSP-FF算法相比,所提算法保持阻塞率和资源利用率的同时,运行时间开始降低;当信道中包含波长数为58时,与传统KSP-FF算法相比,所提算法运行时间减少了0.07 ms。由此可见,提出的算法使路由选择和波长分配得到了优化。Abstract: Aiming at the routing and wavelength problems of dynamic services in optical transport network, a deep routing wavelength assignment algorithm based on reinforcement learning is proposed. The algorithm is based on a software defined network architecture, flexibly adjusts and controls the optical transport network through reinforcement learning, and realizes the optimization of the optical network routing wavelength assignment strategy. For the problem of routing selection, combined with the wavelength usage on the link, the A3C algorithm is used to select the appropriate route to minimize the blocking rate; for the problem of wavelength assignment, the first fit algorithm is used to select the wavelength. Considering multiple indicators such as blocking rate, resource utilization, policy entropy, value loss, execution time, and speed of algorithm convergence, the 14-node NSFNET network topology simulation experiment is implemented. The results show that when the channel contains 18 wavelengths, compared with the traditional KSP-FF algorithm, the blocking rate of this routing wavelength assignment algorithm is reduced by 0.06, and the resource utilization rate is increased by 0.02, but the execution time is increased. When the number of wavelengths exceeds 45, compared with KSP-FF, the proposed algorithm maintains the blocking rate and resource utilization, while the execution time begins to decrease. When the number of wavelengths is 58, compared with KSP-FF, the proposed algorithm's execution time is reduced by 0.07 ms. It can be seen that the proposed algorithm optimizes the routing and wavelength assignment.
-
表 1 仿真实验业务参数
Table 1. Serve parameters of simulation experiment
Parameters Value Average arrival time of dynamic service/s 1/12 Continuing times of dynamic service/s 13 Available wavelength of channel 18 -
[1] Nath P K, Venkatesh T. Lightpath routing and wavelength assignment for static demand in translucent optical networks [J]. Photonic Network Communications, 2020, 39(7): 103-119. [2] Yang Xiuqing, Chen Haiyan. Application of optical communication technique in the internet of things [J]. Chinese Optics, 2014, 7(6): 889-896. (in Chinese) [3] Li Haitao. Technical approach analysis and development prospects of optical communication technology in China deep space TT&C network [J]. Infrared and Laser Engineering, 2020, 49(5): 20201003. (in Chinese) doi: 10.3788/IRLA20201003 [4] Yang Junbo, Yang Jiankun, Li Xiujian, et al. Choice and control of routes in crossover optical interconnection network [J]. Optics and Precision Engineering, 2010, 18(6): 1249-1257. (in Chinese) [5] Sun Zhaowei, Liu Xuekui, Wu Xiande, et al. Path planning based on ant colony and genetic fusion algorithm for communication supporting spacecraft [J]. Optics and Precision Engineering, 2013, 21(12): 3308-3316. (in Chinese) doi: 10.3788/OPE.20132112.3308 [6] Guo Xiuzhen, Hou Lixin, Yin Zhaotai, et al. All-optical routing control based on coherently induced high reflection band and high transmission band in a medium of cold atoms [J]. Chinese Optics, 2011, 4(4): 355-362. (in Chinese) [7] Zhang Min, Xu Bo, Cai Yi, et al. Routing and wavelength assignment based on genetic algorithm in large scale WDM network [J]. Optical Communication Technology, 2018, 42(11): 1-4. (in Chinese) [8] Wang Weilong, Li Yongjun, Zhao Shanghong, et al. Routing and wavelength assignment based on load balance for optical satellite network [J]. Laser & Optoelectronics Progress, 2021, 58(7): 0706004. (in Chinese) [9] Shi Xiaodong, Li Yongjun, Zhao Shanghong, et al. Ant colony optimization routing and wavelength technology for software-defined satellite optical networks [J]. Infrared and Laser Engineering, 2021, 51(7): 20200125. (in Chinese) doi: 10.3788/IRLA20200125 [10] Martín I, Troia S, Hernández J A, et al. Machine learning based routing -and wavelength assignment in software-defined optical networks [J]. IEEE Transactions on Network and Service Management, 2019, 16(3): 871-883. doi: 10.1109/TNSM.2019.2927867 [11] Mnih V, Kavukcuoglu K, Silver D, et al. Human level control through deep reinforcement learning. [J]. Nature, 2015, 518(7540): 529-533. doi: 10.1038/nature14236 [12] Li Zhongtao. Wireless communication node coverage optimization based double deep Q-learning [J]. Electronic Technology & Software Engineering, 2021(14): 1-3. (in Chinese) [13] Rao Ning, Xu Hua, Qi Zisen, et al. Communication interference resource allocation method of deep reinforcement learning based on maximum policy entropy [J]. Journal of Northwestern Polytechnical University, 2021, 39(5): 1077-1086. (in Chinese) doi: 10.1051/jnwpu/20213951077 [14] Zhao Zipiao, Zhao Yongli, Ma Haoli, et al. Cost-efficient routing, modulation, wavelength and port assignment using reinforcement learning in optical transport networks [J]. Optical Fiber Technology, 2021, 64: 102571. [15] Li Xin, Zhao Yongli, Li Yajie, et al. Multi-objective routing and resource allocation based on reinforcement learning in optical transport networks[C]//2020 Asia Communications and Photonics Conference (ACP) and International Conference on Information Photonics and Optical Communications (IPOC), 2020: 1-3. [16] Chen Xiaoliang, Li Baojia, Proietti Roberto, et al. DeepRMSA: A deep reinforcement learning framework for routing, modulation and spectrum assignment in elastic optical networks [J]. Journal of Lightwave Technology, 2019, 37(16): 4155-4163. doi: 10.1109/JLT.2019.2923615