WDM光传送网的选路和波长分配算法

为了克服电处理的速率“瓶颈”，宽带网络向光网络发展。目前，光突发交换、光分组(包)交换正在积极研究中，但是距商用还较远。已可商用的是具有光分插复用器(OADM,Optical Add－Drop Multiplexer)和光交叉连接器(OXC,Optical Cross－Connect)的波分复用(WDM)网络。由于是提供可调度的传送用光路，称这种网络为WDM光传送网(OTN,Optical Transport Network)。

　　1 网络结构

　　图1是网络物理结构的一个例子，虚线内为光传送网。图中有5个OXC：A，B，C，D，E；5个具有光接口的电设备：S1～S5；6个将OXC相连的物理链路：l1～l6。一般一条物理链路包含一对光纤供双向运用，有的OXC间没有物理链路相连。但更多的情况是一条物理链路包含多根光纤供不同方向运用。一根光纤上可采用多个波长。

图1　网络物理结构举例

　　一般情况下，OXC不直接和电设备相连，只起光交叉连接作用。

　　OXC可分为无波长变换和有波长变换(也可以是部分端口有波长变换或波长变换的范围有限)两种：无波长变换的OXC的作用是将一根输入光纤上的某一波长信号连到另一根输出光纤的同一波长上，即波长是连续的；有波长变换则是将一根输入光纤上的某一波长信号连到另一根输出光纤的另一波长上。适当地安排路由和分配波长，可为电设备间建立光路(optical path)。在一根光纤上，不能为不同光路分配相同波长。图2(a)为图1建立的光路例子。将图2(a)的光路连接用图2(b)来表示，称为逻辑结构，也称逻辑拓扑或虚拓扑。例如，图2(a)中，节点B与E间的光路是经节点A中的OXC转接的，在图2(b)中用O4表示。图2(b)中，O6、O4、O1都是中间有OXC转接的。O2、O3、O5是直接光路。

图2　光路举例

　　这样建立的光路对信号是透明的，即信号可以是任意方式。

　　实际设计中，一种需求情况是：提出所需建立的光路，为这种光路选取物理路由并分配相应的波长[1,2]。例如，图2(b)中提出要建立6条光路，图2(a)就是一种选路和波长分配方案。

　　网络向分组化发展，图1中的电设备可以是ATM交换机或IP路由器。例如，连在端口B2的路由器可以通过光路O6和连在端口C3的路由器相连。B2到C3可有多条路径，O6是最近的，也可以经过O4-O5-O3或O4-O5-O1-O2连接，但需要路由器转接，即电的多跳连接。A与B间没有光路，至少需经C电跳连接一次。

　　实际设计中另一种需求情况是：提出各路由器间的所需业务量强度；设计出逻辑拓扑并为其光路选取物理路由和分配波长[2－4]。与根据光路需求情况进行设计相比，增加了要考虑电的多跳。

　　下面分别叙述两种需求情况下的选路和波长分配(RWA)算法。

　　2 基于光路的RWA算法

　　光路需求的提出有3类：静态的、递增的和动态的。静态RWA问题是预先给出多条光路连接需求，计算路由和分配波长。这种计算可以是离线(off－line)的，即不需要实时计算。在递增情况，光路需求逐条地提出，需要为每一条作实时在线RWA计算。光路数增加到一定值后，就不再增加。对于动态情况，光路需求逐条地提出，但一条光路持续一段时间后又被拆除，要为每一条作实时RWA计算。这里所谓的动态，实用中常是缓慢变化的，例如几小时甚至几天才有一次新的需求。后两类情况的RWA算法常相同，只是性能评价指标不同，将在2.2节合在一起叙述。
　　
　　2.1 基于光路的静态RWA算法

　　基于光路的静态RWA算法是给定多条光路的连接需求和物理拓扑后为每条光路选取路由并分配波长。设计时的优化目标可以是使所用的资源如波长数最小。这个优化问题可用整数线性规划法求解[1]。若OXC无波长变换，则将波长连续作为约束条件。这个问题的反过来是在一定的波长数下使连接的光路数最大。这种优化方法的复杂性随网络规模的增大而急剧增加，因此，工程上常将RWA问题拆成选路子问题和波长分配子问题，分两步求解。

　　(1)为每条光路选取路由

　　选路方案有两类：固定路由和备用路由(alternate routing)。
　　固定路由是为每条光路选取一条固定的路由。通常可用熟知的最短路径算法。但是，最短路径算法的缺点是有时会使网络中某些部分过于拥挤，即某些光纤上经过的光路数过多，在波长数有限情况下会造成波长不够分配。改进的方法是采用能使负载平衡的选路算法。可以采用整数线性规划的优化方法使网络中一根光纤上的光路数尽量小，这为减小波长数创造了条件，但这种方法在网络规模较大时较复杂。为此，可采用使网络负载平衡的启发式路由算法。启发式算法是根据概念推出的优化算法，能得到较优的结果，但不一定最优。例如，可以按某种合适次序逐条地为光路选取路由，每一条均采用某种优化的动态路由算法[5]。

　　备用路由是为每条光路选取多条路由，最简单的方法是选取k条最短路径。为多条光路的一组路由分配波长时，若发生波长数不够用，则通过置换备用路由构成另一组路由，再分配波长，直到完成要求。如何从备用路由集选择合适的路由也是需要考虑的[2]。

　　(2)分配波长

　　若OXC没有波长变换，则波长分配的约束条件是每条经OXC连接的光路应是波长连续的，并且在一根光纤上不同光路需分配不同波长，优化目标是使采用的波长数量最小。这个问题可以转化为一个辅助图G(V,E)的着色问题[1]，V为节点集，E为边集。V中的每个节点相应于一条光路，这条光路如果和某些其他的光路处于同一根光纤内，则相应的节点间就有边相连。波长分配相当于为G的节点着色，约束条件是相连的节点不能采用同一颜色，优化目标是使采用的颜色数最小。这个着色问题已有有效的算法[1]，但较复杂。为了简化，可以采用一些启发式算法，对多条路由逐条分配波长。

　　2.2 基于光路的动态RWA算法

　　对于上面讲过的递增情况，在给定的物理拓扑和最大波长数条件下，要为每一条新增光路选取路由并分配波长，优化目标为被拒绝(由于波长数不够)的百分比(相对于总增加数)尽量小；对于动态的连接请求和拆除情况，优化目标为被拒绝(或称阻塞)的概率尽量小。这两类情况的RWA算法是在线的，当网络规模较大时，为了减小复杂性，常将选路和波长分配分两步进行；当网络规模不太大时，可以采用分层图的方法将选路和波长分配合在一起考虑[6]。

　　若首先进行选路，可分为3类：固定路由、备用路由和自适应路由(自适应路由也可纳入前两类中，即只分成两类)。固定路由通常采用最短路径。备用路由可采用多条最短路径，在首条路由上波长资源不够时，换一条再试，与固定路由相比减小了阻塞率。采用最短路径的缺点是有时会使网络中某些部分过于拥挤，阻塞率加大。改进的方法是采用自适应路由[1]，在每次选路时，根据网络的状态，使各条光纤上的光路数尽量平衡。

　　选定一条路由后，要为它分配波长，有多种方法[1,2]。第一种方法是从该路由上已建光路所使用的波长之外，随机地另选一个波长，称为随机波长分配算法(R算法)；第二种是将波长编号，从低到高依次观察是否已在该路由上建光路使用，首先找到的波长就被使用，称为首先适合算法(FF)。仿真表明，采用FF算法的阻塞率比采用R算法时小。R和FF算法只考虑一条路由上的局部情形，还有一种最大－总数算法(Max－Sum)[1,2]，其思路是按分配波长后网络中仍可容纳的光路数最大为目标来分配波长。采用Max－Sum算法的阻塞率优于FF算法(但有时差别不大)，代价是增加复杂性。文献1还叙述了其他8种波长分配算法。

　　对于将选路和波长分配分两步进行的算法，仿真表明，影响阻塞率的主要是选路算法。好的选路算法会显著地减小阻塞率，而各种波长分配算法的性能差别不大。因此，在工程上可采用一种自适应路由算法加简易的FF波长分配算法。

　　采用分层图(layered－graph)的方法可以将选路和波长分配一步完成[6]。OXC中的光开关是空间域的连接，波长分配是频率域的连接，从提供通道的角度看，空域和频域的作用是一致的。分层图将空域和频域结合起来，绘出一张新的通道图，动态RWA问题成为在分层图中选取一条通道的问题。各种动态选路的算法都可考虑，目标是使阻塞率最小。仿真表明，采用较好选路算法的分层图法比将选路和波长分配割裂的方法阻塞率小。

　　3 基于运送分组业务的RWA算法

　　图1所示是电设备(例如路由器或ATM交换机)通过光路进行连接。可以将所有的光路部分称为光层，其中有光交叉连接。如果光路已经给定，则分组业务运行遇到的是一般的选路问题，但是实用中会遇到给定各分组通信设备间的业务量矩阵，要设计光路结构(称为逻辑拓扑或虚拓扑)的问题[2-4,7]。对于电设备来说，最好是各自间都建有一条光路，但是，这样设计不经济。有的电设备间的连接可以经过其他的电设备转接，从而节省光路，图2(b)中A与B间就没有光路。基于运送分组业务的选路和波长分配(RWA)算法是根据运送分组业务的需求来设计网络，也可分为静态和动态两种。

　　3.1 基于运送分组业务的静态RWA算法

　　基于运送分组业务的静态选路和波长分配(RWA)算法是在给定物理拓扑和各分组电设备间的业务量矩阵情况下设计网络，使网络性能和经济性尽量好。从理论上说，优先目标一直要考虑所用的光纤数最小，使用的波长数最小等问题，但是这样经常很复杂。可将问题割裂分为几步考虑，首先进行虚拓扑设计[3,4]，再为虚拓扑中的光路进行选路和分配波长，最后可能反过来对第一步设计进行调整。在设计中，也可以将光路的选路放在第一步中。
　　
　　3.2 基于运送分组业务的动态RWA算法

　　在IP over WDM网络中，可以采用MPLS(多协议标记交换)技术来实现业务量工程，解决有效利用网络资源和保证QoS(服务质量)的问题。在MPLS网络中，需在线建立保证带宽的路径，最好的解决方法是采用综合的动态IP与波长选路算法[8]。这种算法是将IP网络的QoS路由技术进一步推广到IP over WDM网络。

　　4 RWA设计中要考虑的附加问题

　　上面从概念上说明了有关RWA算法。最基本的情况是采用无波长变换的OXC，即对一条经OXC构成的光路有波长连续性限制。下面对引入波长变换、抗毁、服务策略等问题作概要叙述。

　　4.1 波长变换问题

　　引入波长变换可使在一条光路上分配波长时更灵活，动态建立光路时阻塞率减小。引入波长变换与无波长变换相比的得益程度与具体情况有关，有时明显，有时并不明显。波长变换器价格较贵，而且技术上有限制。文献2中研究了各种不同的配置情况：网络中只有少数节点配置有完全波长变换的OXC，称为稀疏波长变换；OXC只有部分端口具有波长变换；波长变换范围有限，如只能在几个波长间变换。上述3种情况可相互组合。对于不同的配置，除了要解决RWA问题外，还要解决如何最佳配置问题。

　　4.2 抗毁问题

　　光网络的抗毁十分重要。一种情况是只考虑光传送网本身抗毁，可以分成保护和恢复两种机制[9]：保护机制是为每一条工作光路准备一条备用光路，要求这两条光路不会在一根光纤断裂时同时失效，解决的算法类似于第2节中的备用路由算法；恢复机制是在网络有故障造成某一条光路失效时，根据网络状态实时地重新构造一条光路，这种方法实现较复杂，同时也需要网络有一定的冗余容量。

　　另一种情况是考虑IP over WDM网络的抗毁，涉及光层和IP层，可参考文献9。
　　
　　4.3 服务策略问题

　　网络运行时可以引入各种策略，例如引入优先级，某些光路必须经过某节点，某些光路不能经过某节点等。要解决这些额外要求情况下的RWA算法[10]。上面4.1至4.3节叙述的问题可能同时存在，也需要有相应的RWA算法[11]。

　　5 结束语

　　本文综述了WDM光传送网的RWA算法。可以看到，光传送网的RWA算法有多种应用情况，并要考虑多种问题，是较复杂的。今后人们还可能提出一些新的算法。算法研究如何投入工程应用，也需要做进一步的工作。

参考文献

1 Zang H, Jue J P, Mukherjee B. A review of routing and wavelength assignment approaches for wavelength routed optical WDM networks. Optical Networks Magazine, 2000, 1(1): 47－60
2 徐世中,王晟,李乐民. DWDM光传送网中选路和波长分配. 通信学报, 2001, 22(4): 51－57
3 Leonardi E, Mellia M, Marsan M A. Algorithms for the logical topology design in WDM all optical networks. Optical Networks Magazine, 2000, 1(1): 35－46
4 Dutta R, Rouskas G N. A survey of virtual topology design algorithms for wavelength routed optical networks. Optical Networks Magazine, 2000, 1(1): 73－89
5 Kodialam M, Lakshman T V. Minimum interference routing with application to MPLS traffic engineering. IEEE INFOCOM, Tel－Aviv, Israel, 2000
6 Xu S, Li L, Wang S. Dynamic routing and assignment of wavelength algorithms in multifiber wavelength division multiplexing networks. IEEE J, Selected Areas in Commun, 2000, 18(10): 2130－2137
7 Harai H, Kubota F, Nakazato H. Design of reconfigurable lightpaths in IP over WDM networks. IEICE Trans Commun, 2000, E83－B(10): 2234－2244
8 Kodialam M, Lakshman T V. Integrated dynamic IP and wavelength routing in IP over WDM networks. IEEE INFOCOM, Anchorage, Alaska, 2001
9 王烨,李乐民,王晟. IP over WDM网络结构和生存性研究. 电信科学, 2000, 16(11): 25－30
10 何荣希,李乐民,徐世中. WDM光传送网中支持优先级的波长分配算法. 通信学报, 2001, 22(3): 27－32
11 王烨,李乐民等. 抗毁WDM网络中支持多优先级的波长分配算法. 电子学报, 2001, 29(1): 27－31

[摘要] 文章综述了波分复用(WDM)光传送网的选路和波长分配(RWA)算法；考虑了两种需求情况：一种是从建立光路的需求出发，另一种是从运送分组业务的需求出发；还概述了RWA设计中要考虑的附加问题，包括波长变换、抗毁和服务策略。

[关键词] 波分复用 光传送网 选路和波长分配

[Abstract] A review of routing and wavelength assignment (RWA) algorithms for WDM optical transport networks is presented. Two cases of requirements are considered: One is the requirement of establishing optical paths and the other is the requirement of transporting packet services. Related problems including wavelength converting, survivability and policy of services in RWA design are also briefly discussed.

[Keywords] Wavelength division multiplex Optical transport network Routing and wavelength assignment