光网络选路和波长分配研究

李乐民

　　摘要：文章在叙述了光网络中选路和波长分配(RWA)要解决的基本问题后，对有关方面的近年研究作了综述，主要包括：虚拓扑重构、业务量疏导的RWA、多播RWA、抗毁网络的RWA。抗毁问题涉及WDM网络的抗毁选路、区分可靠性、网状网的快速恢复、多故障下的抗毁。

　　关键词：选路和波长分配；虚拓扑重构；业务量疏导；多播；网络抗毁

　　Abstract: Basic problems that should be solved for routing and wavelength assignment (RWA) in optical networks are presented. After that, an overview of research achievements in recent years is presented, including virtual topology reconfiguration, RWA in traffic grooming, RWA in multicasting, and RWA in survivable networks. For network survivability, it includes survivable routing in WDM networks, differentiated reliability, fast recovery in mesh networks, and multi-link failures.

　　Key words:routing and wavelength assignment; virtual topology reconfiguration; traffic grooming; multicasting; network survivability

　　采用波分复用(WDM)传输系统、光分插复用器(OADM)和光交叉连接器(OXC)可构成光传送网(OTN)，提供可调度的光路。为了进一步智能化，OTN演进为自动交换光网络/自动交换传送网(ASON/ASTN)。选路和波长分配(RWA)是ASON控制面的重要功能之一[1]。RWA算法可由具体网络设计公司自行掌握，这样，各公司提供的ASON虽然在标准上不易显出自己的特色，但在RWA软件性能等方面却可以显出特色和技术高低。

　　1 光层的选路和波长分配


　　在ASON/ASTN中，对于光层，需根据要求提供光路。所谓光路，是指一条采用某个波长的光通道。例如，一个波长上的信号，从甲地出发，经过WDM传输系统到了一个有OXC的节点，经OXC交叉连接，可转发到连向目的地的输出端口，中间还可以经过其他的OXC，最后到达乙地。这样，甲、乙两地之间就沟通一条光路。若采用无波长变换的OXC，则这条光路上只采用一个不变的波长，称为波长连续性限制。若有波长变换，这条光路上的不同段可以采用不同的波长。根据所提出的光路需求，为其选取物理路由并分配相应的波长，称为选路和波长分配(RWA)。


　　光路的RWA算法文献[1，2]已作了基本介绍。光路需求的提出，有静态和动态两种。静态RWA问题是预先给出多条光路连接需求，计算路由和分配波长，计算可以是离线的，即不需要实时计算；对于动态情况，光路需求逐条地提出，但一条光路持续一段时间后又被拆除，要为每一条光路做实时RWA计算。ASON中，两种情况都有需要。

　　RWA算法涉及优化问题，有些优化方法的复杂性随网络规模的增大而急剧增加，因此，工程上常将RWA问题拆成选路子问题和波长分配子问题，分两步求解。拿动态RWA算法来说，首先进行选路，可分为3类：固定路由、备用路由、自适应路由(自适应路由也可纳入前两类中，即分为两类)。固定路由通常采用最短路径算法。备用路由可采用多条最短路径，在首条路径上波长资源不够时，换一条再试，与固定路由相比减小了阻塞率。采用简单的最短路径的缺点是有时会使网络中某些部分过于拥挤，使阻塞率加大。改进的方法是采用自适应路由，在每次选路时，根据网络的状态使各条光纤上的光路数(使用波长数)尽量平衡，这样做可显著减小阻塞率。ASON中的资源管理信息为自适应路由创造了条件。选定一条路由后，分配波长有多种方法[1，2]。例如，将波长编号，从低到高依次观察是否在该路由上的已建光路使用，首先找到的波长就被使用，称为首先适合算法(FF)。又如按分配波长后网络中仍可容纳的光路数最大为目标来分配波长，称为最大-总数算法(Max-Sum)。Max-Sum算法的阻塞率优于FF算法，但有时差别不大，代价是增加了复杂性。

　　对于将选路和波长分配分两步进行的算法，仿真表明，影响阻塞率的主要是选路算法。

　　采用分层图的方法可以将选路和波长分配一步完成。文献[3]提出了两种基于分层图的多光纤WDM网的动态选路和波长分配算法，称为PACK和SPREAD，仿真表明它们的性能比传统的将选路和波长分配割裂的方法性能好，即阻塞率较小。
对于RWA，近年还有一些改进性的研究，例如在WDM网络中如何稀疏地设置波长变换器以减小动态情况下的阻塞率[4]。

　　2 虚拓扑重构


　　上节讨论的是给定物理拓扑和光路需求，为光路进行选路和分配波长。实用中，经常遇到给定物理拓扑和各节点中电设备(例如路由器)间的业务量矩阵，要设计网络，使网络的性能和经济性尽量好。这种情况下，光网络提供光路，供路由器使用。与上节不同的是没有给出具体光路需求，而要在优化中确定。路由器面对的是光路，光路的集合称为虚拓扑，也称逻辑拓扑。两个路由器间若没有直达光路，则需经其他路由器进行电的多跳连接。文献[2]叙述了虚拓扑设计问题，包括确定光路和RWA。

　　实际应用中，业务量矩阵常随时间缓慢变化，因此，需要使虚拓扑随着业务量变化而重构。虚拓扑重构要考虑3个问题：确定在什么情况下需要重构的策略；确定新的虚拓扑，既考虑满足新的业务量需求，同时又使原来的虚拓扑改变尽量少；如何切换到新的虚拓扑结构而又不使正在运行的分组数据有任何损伤(或损伤小)，即实现无损伤重构。文献[5]综述了重构问题。

　　文献[6]提出一种在动态业务量下WDM网状网的虚拓扑自适应调整方案，采用定期的在线测量来观察当前每条光路上业务量的变化。在测量周期之末，根据情况增加或拆除一条光路。具体地，当一条或多条光路上的业务量大于一个较大门限值时，说明将发生拥塞，就增加一条新的光路；当一条光路上的业务量小于一个较小门限值时，就拆除这条光路，当然，要将这条光路上的业务量转移到另外的光路上后才拆除，以达到无损伤重构。

　　文献[7]认为因特网上的业务量变化可以预测，虚拓扑的重构应紧跟业务量的变化。将随时间变化的调整过程看作一个多级调整过程，为了使启发式算法能及时跟上网络的变化，引入了预测机制，提出了一种基于预测的多级重构算法。文献[8]从重构成本角度进行了研究。

　　3 业务量疏导的RWA


　　由WDM光纤链路和OXC(或OADM)构成的WDM网络可提供光路。一个波长上传输的通信速率常较高，例如2.5 Gb/s、10 Gb/s或40 Gb/s。这样，WDM光网络的光层提供的速率或带宽是粗粒度，即以波长数为单位。实际应用中，每个业务的通信速率与一个波长上的可通信速率相比常是较低的，若为每个业务提供一个专用波长显然不经济。为了提供细粒度的速率或带宽需求，方法之一是用电的时分复用将多个低速的业务流合起来在一个波长上传输。网络中除有OADM、OXC外，还有与其相连的电的ADM和数字交叉连接器(DXC)。这样，低速业务流通过ADM或DXC汇入某些波长，称为业务量疏导。

　　除了采用SDH设备如ADM、DXC来提供细粒度带宽外，也可以不用SDH，而采用多协议标记交换(MPLS)路由器，即采用分组(包)复用将多个低速的业务流合起来在一个波长上传输。。近年来，提出了通用多协议标记交换(GMPLS)协议。GMPLS可将MPLS扩展到光层(也可用于SDH)。采用GMPLS后，可以实现IP over WDM的对等模型，即采用统一的控制面。这样，可以用MPLS路由器和OADM或OXC来构成智能光网络，利用标记交换路径(LSP)提供细粒度带宽的通路。这里遇到了业务量疏导问题。

　　光网络的业务量疏导问题可以描述如下：给定一个网络配置，包括物理链路、每个网络节点的光收发器数目、每根光纤的波长数目以及波长容量，业务量疏导就是为一组具有各种低速带宽粒度的业务连接请求建立光路，同时优化网络的性能和成本。低速业务流可以通过一条光路到达目的地(单跳)，也可以通过多跳光路，即依靠中间节点的电设备转接，到达目的地。

　　业务量疏导可分为静态和动态。静态业务量疏导是预先给出所有低速业务连接需求，计算光路由并分配波长以及低速业务流的选路。与第一节中所述的光层RWA不同之处是增加了低速流的选路，可称为静态GRWA(Grooming RWA)。根据第二节所述，静态业务量疏导也是一个特殊的虚拓扑(逻辑拓扑)设计问题，即为已知的低速业务流建立合理的光路集(虚拓扑)。

　　通常把静态业务量疏导分为3个子问题加以解决：


　　(1)虚拓扑子问题，确定物理拓扑上需要建立的一组光路需求。


　　 (2)光路路由与波长分配子问题，为上述子问题中的光路需求解决相应的RWA。


　　(3)低速业务流选路子问题(疏导子问题)，在虚拓扑上实现。物理拓扑可有不同结构，如环状、网状。

　　 在动态业务量疏导中，低速业务连接请求随机到达网络，要求进行实时GRWA计算，一个连接维持一段有限时间后又被拆除。动态业务量疏导目标一般都是有效地选择疏导路由和合理分配网络资源，使业务连接的阻塞率最低。

　　文献[9]对光网络中的业务量疏导作了综述。文献[10]针对节点不具有波长变换能力以及光收发器数目受限的WDM网状网，基于疏导图模型和综合疏导算法，提出了抗毁的动态业务量疏导算法。

　　本文叙述的业务量疏导是建立多个低速率路由。近年来，也有反过来研究将多个波长合成一个波段来交换，可节省OXC的端口数[11]。对于光纤来说，也是一种业务量疏导。

　　4 多播RWA

　　第1节中讲的光路是从一个源节点到一个目的节点间构成一条光的通道，中间可经过多个OXC，属于单播。在光层实现多播，也就是一个源节点送出的光要同时送到多个目的节点，需建立一个光树。在光树的分叉点若要全光实现，可采用分光器。为了补偿分光引起的损耗，需增设光放大器。具有分光和传送(SaD)模块的OXC称为支持多播的OXC(MC-OXC)[1 2]。

　　在具有MC-OXC的光网络中，根据光树的需求，要为光树选路和分配波长，称为多播RWA(MC-RWA)。有关算法比单播RWA更为复杂[12]。 实际应用中，为了节省成本，不宜为每个光节点都配置MC-OXC，也就是有分光器稀疏配置的约束。此外，还有波长变换器配置约束(无波长变换器时为波长连续性约束)、传输损伤约束等。
上面讲的是光层的MC-RWA，如果再考虑电设备的运用以提供细粒度带宽，则成为多播业务量疏导问题，需进一步研究。

　　5 抗毁网络的RWA

　　光网络的抗毁可以有两种考虑。一种是考虑其上层有IP运用，而IP层也有抗毁能力。这种依靠IP层抗毁的优点是节省光网络资源，但恢复时间较长。另一种考虑是使光网络本身有抗毁能力。两种考虑都涉及选路与波长分配问题。光网络的抗毁已有较多研究，较新的研究有：抗毁虚拓扑设计、区分可靠性和网状网的快速恢复等等。

　　5.1 抗毁选路——抗毁虚拓扑设计


　　第2节讲过虚拓扑。路由器通过虚拓扑互相连接，从路由器考虑，为了增加生存性，希望有一条逻辑链路受损时，能够通过其他的逻辑链路迂回多跳连接。虚拓扑如果设计不好，可能会发生一根光纤断裂时可通的链路同时断开。因此，虚拓扑设计时要额外考虑约束条件，文献[13，14]中称为保护设计[13]或抗毁选路[14]。文献[13]提出了LG-VTMPD算法，用分层图法同时处理选路和分配波长，考虑了网络的负载均衡和波长数的限制，适于无波长变换的场合，较其他算法有更好的性能，同时还提出了一种有效放置波长变换器的算法。

　　5.2 区分可靠性


　　实际应用中，各种业务对抗毁性能要求不同，付的费用也不同，设计时可对不同业务采用不同的抗毁措施，能更好地利用网络资源[15]。

　　5.3 网状网的快速恢复


　　抗毁环状自愈网较易实现快速恢复。抗毁网状网虽较节省资源，但在快速恢复方面还需要进一步进行研究。方法之一是在网状网中构造虚拟自愈环。

　　文献[16]中提出了采用预配置环(Pre-configured Cycle)的思路，有利于网状网的快速恢复。

　　5.4 多故障下的网络抗毁


　　目前已有的研究大多限于单故障下的抗毁。对安全性要求很高的网络，近年展开了多故障下的抗毁研究，文献[17]对此进行了综述。

　　6 结束语


　　上面综述了光网络中选路和波长分配的有关研究。在ASON中，RWA是控制面的一个部分，要和其他部分配合工作[1]。

　　7 参考文献

　　[1] 张杰. 自动交换光网络ASON [M]. 人民邮电出版社, 2004.

　　[2] 李乐民. WDM光传送网的选路和波长分配算法 [J]. 中兴通讯技术，2001, 7(6):4—7.

　　[3] Xu S, Li L, Wang S. Dynamic Routing and Assignment of Wavelength Algorithms in Multifiber Wavelength Division Multiplexing Networks [J]. IEEE J Selected Areas in Comm. 2000, 18(10):2130—2137.

　　[4] Chu X, Li B, Chlamtac I. Wavelength Converter Placement Under Different RWA Algorithms in Wavelength Routed All Optical Networks [J]. IEEE Trans. on Communications, 2003, 51(4):607—617.

　　[5] Golab W, Boutaba R. Policy Driven Automated Reconfiguration for Performance Management in WDM Optical Networks [J]. IEEE Communications Magazine, 2004, 42(1):44—51.

　　[6] Genecata A, Mukherjee B. Virtual Topology Adaptation for WDM Mesh Networks Under Dynamic Traffic. IEEE/ACM Trans. on Networking [J], 2003, 11(2):234—247.

　　[7] Lee K. An Adaptive Virtual Topology Reconfiguration Policy in Multi-Wavelength Optical Internet. European Transactions on Telecommunications [J], 2003, 14(5):417—422.

　　[8] Manohar P. Multiperiod Virtual Topology Design in Wavelength Routed Optical Networks [J]. IEEE Proceedings G-Circuit, Devices and Systems, 2003, 150(6):516—520.

　　[9] Zhu K, Mukherijee B. A Review of Traffic Grooming in WDM Optical Networks: Architectures and Challenges [J]. Optical Networks Magazine, 2003, 4(2):55—64.

　　[10] Wen H, Li L. Dynamic Grooming Algorithms for Survivable WDM Mesh Networks [J]. Photonic Network Communications, 2003, 6(3):253—263.

　　[11] Parthiban R, Tucker R S. Waveband Grooming Algorithms for Survivable WDM Mesh Networks [J] Journal of Lightwave Technology, 2003, 21(11):2476—2488.

　　[12] Rouskas G N. Optical Layer Multicast: Rationale, Building Blocks, and Challenges [J]. IEEE Network, 2003, 17(1):60—65.

　　[13] Wang Y, Li L, Wang S. A New Algorithm of Design Protection for Wavelength Routed Networks and Efficient Wavelength Converter Placement [C]. IEEE International Conference on Communications, Helsinki, Finland, 2001:807—811.

　　[14] Sen A, Hao B, Shen B H. Survivable Routing in WDM Networks [C]. Seventh International Symposium on Computers and Communications, ISCC 2002:726—731.

　　[15] 温海波, 李乐民. 支持不同可靠性要求的WDM网状网业务量疏导算法 [J]. 通信学报, 2004,25(3):1—10.

　　[16] Sack A, Grover W D. Hamiltonian P-Cycles for Fiber-Level Protection in Homogeneous and Semi-Homogeneous Optical Networks [J]. IEEE Network, 2004, 18(2):49—56.

　　[17] He W, Semani A K. Path Based Protection for Surviving Double-Link Failures in Mesh-Restorable Optical Networks [C]. IEEE Global Telecommunications Conference 2003, GLOBECOM´03, 2003,(5):2558—2563.

　　作者简介：

　　李乐民，中国工程院院士，电子科技大学教授，博士生导师。1952年毕业于上海交通大学电机系电讯专业。研究方向为信息传输与通信网，近年侧重于宽带通信网络。已发表论文200余篇。
摘自　中兴通讯技术