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

业务汇聚端口是指存在多个请求利用该端口实现业务的汇 图 2 光通道和光通路
聚操作。具体约束如式（6）所示。当存在请求q 1 ,q 2 ∈Q都部署
在链路(u,v)的λ波长上，即 f q1,(u,v),λ =f q2,(u,v) ,λ=1,并且存在
其相邻链路(m,u)的λ波长上仅存在请求q1，即f q1,(m,u),λ =1，
f q2,(m, u), λ =0。此时，请求q1在经过网元u时发生了汇聚操作，
则需要在网元u上为链路(u,v)的λ波长部署OEO端口，即o (u,
v),λ =1。
在本文中，定义在一条链路上单个波长所建立的信号传
输通道为光通道；光通路是由一个或多个相邻链路上波长相同
且无OEO端口部署的光通道组成的。如图2所示，链路(a,b)和
链路(b,c)上的光通道1，由于前后两个通道的波长一致并且承
（6）业务拆分端口约束
载的业务也一致，则业务在通过这两个光通道传输时，不需要
业务拆分端口是指存在多个请求利用该端口实现了业务的
跳波、汇聚或拆分，所以可以将这两个光通道拼接成光通路
拆分操作，其约束和汇聚端口约束类似，如式（7）所示。
1：p (a,c,1) ={(a,b), (b,c)}1。链路(a,b)和链路(b,c)上的光
通道2，由于两个通道中承载的业务发生了变化，所以无法拼
接成一条连续的光通路。因此链路(a,b)和链路(b,c)上光通道
只能被表示成两个独立的光通路，分别为p (a,b,2) ={(a,b)}2和
（7）复杂度分析和证明
p (b,c,2) ={(b,c)}2。
从上述ILP模型可知，该问题的变量和约束条件数量都比
辅助图WA算法根据负载均衡算法的路由结果以及该路径
较多、求解难度大。当忽略掉该问题的约束条件（式（5）～式
上的资源占用情况，得到该路径上的光通路信息，然后将光通
（7））时，即将OEO端口约束松弛。此时，该模型能够被归约
路映射成虚拟链路，从而构造出辅助图G'(V',E')。辅助图构
成多商品流问题，而多商品流问题已经被证明为NP-hard问题
[12] 造方法如图3所示。请求q通过负载均衡路由算法得到传输路
。基于此，可以证明本文提出的基于OEO端口成本感知的RWA
径 p={(a,b),(b,c)}，网络中已经存在4组业务，根据光通路
问题同样为NP-hard问题。由于NP-hard问题不存在多项式时间
的定义可得该路径上存在3条光通路，分别为p (a,c,1) 、p (a,b,2) 和
内的最优解算法，因此本文提出了两种启发式算法对该问题进
p (a,c,3) 。如果将请求部署在p (a,c,1) 上，由于p (a,c,1) 上已经为业务1
行求解。
部署了两个OEO端口，则不需要部署额外的端口即可以保证业务
q的传输需求，因此将辅助图中对应光通路1的虚拟链路(a,c,1)
四、OEO-RWA 算法和 SA-RWA 算法 的权值设置为0。如果将请求q部署在光通道p (a,b,2) 时，则需要
1.OEO-RWA 算法 分别在网元b上部署两个OEO端口，实现业务q和业务2的拆分操
目前，很多研究会将RWA问题分成路由（R）和波长分配
作，因此将虚拟链路(a,b,2)的权值定义为2，同理可得，虚拟
（WA）两个子问题，并分别求解。本文提出的OEO-RWA算法同
链路(a,c,3)的链路权值也为2。此外，在链路(a,b)和(b,c)上
样使用了上述策略，但不同的是，OEO-RWA算法具备以下两点优
均存在一个未被占用的波长4，因此可以额外建立一条虚拟链路
势：
(a,c,4)。如果请求部署在(a,c,4)上，则需要在业务的原宿节
一方面通过负载均衡路由算法保证了OTN的资源利用；另一
点分别部署一个OEO端口，因此虚拟链路(a,c,4)的权值为2。同
方面，通过辅助图算法实现波长分配，保证了业务部署时新增
时，链路(a,b)和(b,c)上波长4还可以被抽象成两条独立的虚拟
的OEO端口尽量少。
链路(a,b,4)和(b,c,4)，且权值均为2。
1.1 负载均衡路由算法
针对 OTNG(V,E,Λ)，其中Λ e ⊆Λ表示链路e上的波长占用 图 3 WA 辅助图构造方法
情况，|Λ e |表示链路e上的剩余波长数，|Λ e,total |表示链路e上
的初始波长数。另外，c e,λ 表示链路e上波长为λ的光通道的剩
余带宽，c e,λ 表示链路e上波长为λ的光通道的初始总带宽。如
果波长λ未被占用，则C e,λ =0。基于上述信息，定义链路e∈E
上权值设置为me，如式（8）所示，并通过Dijkstra算法计算
权值最短的可行路径。如果链路上剩余的波长或者带宽资源较
多时，则链路的权值me将越小，因此在使用Dijkstra算法路由
时，将更倾向经过该链路，从而保证OTN的资源部署相对均衡。

OTN拓扑经过上述转换后得到辅助图G'(V',E')，其中V'
1.2 辅助图WA算法

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