Page 42 - 网络电信2020年5月刊下

光 通 信

表示已知路由的节点集合，E'表示根据光通路构造的虚拟链路 1. 小规模网络仿真结果
集合。由于虚拟链路上的权值表示业务在该链路上传输时所需 在小规模网络仿真中，本文基于SCIP开源软件实现了上述
要部署的OEO端口数量，所以根据辅助图G'(V',E')，可以利用 的ILP模型，模拟了6个节点、11条双向链路的小规模网络，每
Dijkstra算法计算出新增OEO端口数量最少的波长分配方案。 个链路上设置3个可用波长。仿真结果见表1和表2。
2. SA-RWA 算法
表 1 ILP 模型和启发式算法的端口数量结果对比（单位：个）
使用OEO-RWA算法只能够保证单个请求尽可能地选择一条
负载均衡且新增OEO端口较少的路由和频谱分配方案，但无法保
证全网批量请求的收益最大。因此，提出一种改进的模退火算
法（SA-RWA），该算法将对OEO-RWA算法结果进一步优化，如
算法1所示：步骤（1）～步骤（4）表示遍历所有的请求，并
调用OEO-RWA算法计算请求的初始路由方案，并扣除请求所需资
源，从而得到初始解。步骤（5）～步骤（21）为局部搜索过
程，I为总迭代次数。每次迭代过程中，算法会从请求中随机搜
索批量请求Q i ，请求的数量可以由迭代次数、收敛程度等因素 表1是ILP模型和启发式算法的端口数量对比。从表1中能够
决定。另外，请求被选择的概率可以根据请求的带宽、所需的 看出，在小规模网络下，启发式算法计算出的端口数量和ILP模
OEO端口成本等因素决定。步骤（8）～步骤（10）表示将被选 型基本一致。表2为ILP模型和启发式算法的耗时对比。虽然通
择请求所占用的资源释放。步骤（11）～步骤（14）表示遍历 过ILP能够得到最优解，但是通过表2能够看出，随着请求数量
请求集合Q i ，并重新进行路由和波长分配。步骤（15）～步骤 的增加，ILP求解耗时也急剧增加，这也进一步验证了本文所提
（20）表示将新得到的路由结果和原来的路由结果进行对比， 问题的复杂度。因此，ILP求解算法无法适用于大规模网络和批
其中，r(P)为收益函数。如果新产生的解收益较大，则选择该 量请求场景。本文所提的两种启发式算法，均能够在毫秒级完
解作为下一轮迭代的初始解。 成运算，相比ILP求解算法，具备更高的实用性。
算法1基于模拟退火的RWA优化算法输入请求集合Q，拓扑信 表 2 ILP 模型和启发式算法的求解耗时对比（单位：s）
息G(V, E,Λ)输出 请求的路由和频谱分配结果P
（1） for each q∈Qdo
（2） p q =f rwa (G(V, E,Λ),q)
（3） 为请求q分配频谱资源
（4） end for
（5） for i in [1, I] do
（6） 随机选择批量请求集合Q i
（7） G'(V, E,Λ)= G(V, E,Λ)
（8） for each q∈Q i do
（9） 释放请求q占用的资源 2. 大规模网络仿真结果
（10）end for 为了进一步验证启发式算法的有效性，采用了国外某运营
（11）for each q∈Q i do 商的真实网络数据，如图4所示的174节点OTN拓扑。同时，构
（12）p'q=frwa(G'(V, E,Λ),q) 造了15组随机请求集合，每组请求集合包中含4000多个业务请
（13）根据新计算的结果p'q重新分配资源 求。
（14）end for
图 4 仿真拓扑
（15）if r(P)>r(P') then
（16）for each q∈Qi do
（17）p q = p'q
（18）end for
（19）G'(V, E, Λ)= G(V, E, Λ)
（20）end if
（21）end for 此外，本文实现了满足波长一致性的RWA算法（Con-
（22）return P={ p q |q∈Q} RWA）、只允许波长跳波的RWA算法（Diff-RWA）以及基于业务
跳波和汇聚的RWA算法（Ran-RWA）作为对比算法，并分别从请
五、仿真结果和分析 求阻塞率、端口数量和网络收益3个方面对比OEO-RWA和SA-RWA
本文基于小规模网络，使用开源软件SCIP对ILP模型进行求 算法的性能。上述3种对比算法在路由时均采用了负载均衡策
解，验证问题的复杂度。然后基于174节点的大规模网络验证两 略，在频谱分配时优先使用First-Fit算法。在Diff-RWA算法和
种启发式算法（OEO-RWA和SA-RWA）的可行性和有效性。 Ran-RWA算法中，针对跳波和汇聚的业务采用深度优先算法实现

70 网络电信 二零二零年五月