孙卫强，袁巍，李津生，洪佩琳
（中国科学技术大学电子工程与信息科学系 安徽 合肥 230027） 摘 要：本文综述了波长路由网络中的动态路由机制，分析了波长交换网络中寻路问题的特点和实现全动态路由的关键问题，并给出了一种新的半动态寻路机制。该机制考虑了连接建立时间，控制消息负载，网络阻塞概率等指标，本文通过仿真和讨论证明该机制有较好的性能。
关键词：波长路由网络，动态寻路，网络仿真，信令协议，多选路由
中图分类号：TN929.11
1. 引言
DWDM 技术将一根光纤的带宽划分为若干互不干扰的波长信道，这些信道可以用来向客户网络提供跨越骨干网络的通道。传统网络中类似通道的建立需要大量手工配置，费时费力，而且难于管理。新出现的带宽和业务需求对下一代光网络提出了更高的要求，建立一个可以快速便捷、稳定可靠地向用户提供服务的控制面，成了构建下一代光网络的关键问题。图1示出了一个智能光节点的结构。图中控制面完成节 点上的寻路、控制，管理和错误恢复等功能，数据面则完成业务数据的交换，两者之间通过管理接口交互。数据面和控制面可以位于同一个设备中，也可以位于物理上分离的两个设备，并通过一定的管理接口相连。其中
链路管理协议（LMP ：Link Management Protocol ）
完成故障隔离，链路连接性和质量的管理等。
混凝土泊松比
OSPF-TE 完成光网络中的寻路。RSVP-TE 和
CR-LDP 是信令协议，完成光网络中光路的建立、拆
除，管理和故障恢复等。用以传送控制信息的网络
控水系统（控制网络）可以是和数据传送网络物理上分离的
电网络。两者也可以是同一个网络，控制网络占用
相应的控制信道（波长），在节点处进行光电转换。下文中的信令过程都在节点的控制面完成，而具体
和节点资源相关的操作例如波长分配和释放等在数据面完成。
寻路与波长选择问题（RW A 问题）和信令机制是IP ／DWDM 控制面的研究的重点[1][2]。信令机制依据寻路和波长选择模块提供的连接参数建立／拆除连接，并提供一定的保护／恢复措施。光路建立过程中可以从始至终都使用同一个波长，也即满足波长连续性条件，也可以在中间节点处进行波长转换。目前由于波长转换设备成本较高，因而在研究中较少被讨论。在没有波长转换的网络中，边缘节点路由和波长选择算法的好坏对于网络性能影响重大。在寻路和波长选择问题中，路由的选取对性能的影响更为显著[1]，因而建立一种有效的路由机制成为了构建IP ／DWDM 控制面的关键。本文的研究的对象是无波长转换的波长交换网络中动态路由机制。本文第2部分回顾了现有的动态寻路算法；第3、4部分总结了波长交换光网络中寻路问题的特点并讨论了了实现动态寻路的关键问题所在；第5部分提出了基于多选路由的半动态寻路算法，并给出了分析和仿真；最后在第6部分总结全文。
2. 相关工作
Mei 等[5]给出了光路建立过程中的两种资源预留方法：源节点发起的预留方法和目的节点发起的预留，也就是通常所说的前向预留和反向预留方法。Ramaswami 等[6]
定义了波长
交换网络中用以维护连接的连接交换表，并给出了连接建立和交换表更新的规程以及网络拓扑结构更新协议。该协议要求光网络中每个节点都维护其它所有节点上的连接情况信息，并定期地或者由某些事件触发来相互交换拓扑信息从而保持拓扑结构的一致性。这两个文献中提到的连接建立规程成为后续一些文献中的算法或协议的原型。Mokhtar等[7]提出了一种用于波长交换网络的动态寻路机制。该机制把一个DWDM网络看成是一个多层的网络，一个具有W个波长的光网络可以认为是W个具有相同物理拓扑结构的网络的叠加。在各层网络上分别利用最短路径算法进行寻路，直至到一个合适的波长，该波长对应的网络层可以用来建立连接。这种多层图（Multi Layered Graph）为综合解决RW A问题提供了一个成功的范例，在后续的研究中被广泛地引用和比较。Li等[8]提出的固定路径最低负载寻路算法依赖于并行的探测过程。这个探测过程要求被探测路径上的所有节点都参与，容易导致网络控制面的计算负载和控制消息负载增加。和多选路由相对，Jason等[11]提出了一种多选链路的方法，该方法和光分组交换网络中的偏转路由（Deflection Routing）类似，在每个节点上都会为特定的目的节点设置首选和备用两个输出接口。当连接请求到达一个节点时，节点首先尝试使用首选输出接口，如果首选接口上没有可用波长时，则使用备用接口。多选链路和多选路由的差别在于：多选链路方法
吊车梁安装
将路径选择本地化并且逐跳地进行（hop-by-hop），因而选择所依赖的信息也仅仅是首选或者备用输出接口上的波长可用信息。其缺陷在于多选链路的设置较为复杂，并且逐跳的选路方法难以提供一个全局较优的路径。Ho等[15]给出了一种选择网络中源宿节点对之间多选路由的方法C-BAR，该方法可以使得业务较为均匀地分布在网络中，从而使得网络阻塞概率较低。该方法假设针对一特定的网络拓扑结构，任意源宿节点之间已经存在k条最短的路径。
总而言之，现有的全动态选路方法使用最短路径算法，通过后面的分析可知，在波长路由光网络中，此类算法要达到较好的性能，必须保持节点维护的信息得到及时的更新，这可能会导致控制面消息负载过重，并且在波长数目较多的情况下，进行全动态路由在计算复杂度上难以接受。使用多选路由是全动态路由和静态路由之间良好的折衷。但是目前基于多选路由的选路算法的讨论均比较简单，尚没有完整的状态信息更新和选路算法细节的描述。通过下文的分析可知，基于多选路由的选路算法有其自身的特点，利用这些特点可以用较低的控制消息负载和计算复杂度实现较好的性能。家用供暖系统
3.波长交换网络中寻路问题的特点
（1）光路建立过程对资源可用信息的准确性要求高
由于波长交换光网络中资源粒度较大，在建立连接的过程中对信息的准确性要求很高。不准确的或者是过期的资源信息会导致网络阻塞概率升高。Zhou等[10]通过仿真说明使用链路状态协议来进行光网
络的寻路，在链路状态更新定时器超时较慢时会严重影响启发式寻路和波长选择（RW A）算法的性能。因此各种启发式RWA算法的使用必须依赖于更加有效的资源信息交换机制。也就是说，要使光网络具有较好的性能，信令模块在建立光路的过程中必须具有网络那一时刻非常准确的资源信息。
（2）一些应用对光路建立时间有严格要求
新的网络结构（例如WR-OBS[14]，[19]）需要控制面可以在确定的时间内建立连接（或者获知连接不能建立的信息）。对于这样的应用，入口节点需要掌握准确的资源可用信息，从而在连接请求到达时可以进行准确的路由选择，保证信令过程在确知的之间内结束（不管连接建立成功与否）。在传统的应用中进行故障恢复也需要尽量降低连接建立的时延。（3）寻路模块和信令模块的强烈耦合
从前面的讨论可以看出，在波长交换光网络中，寻路模块和信令模块必须相互适配，才能够以最低的控制消息负载来获取最佳的网络性能。单纯地考虑RW A算法虽然理论上可以
到达很优化的性能，但是可能导致控制网络不堪重负。而信令模块可以通过选取适当的RW A 算法交互，以较小的复杂度实现较好的网络性能。
（4）基于多选路由的选路算法的特点
和全动态路由方式不同，基于源路由（包括多选路由）的选路算法的路由决策由入口节点完成，并且
该决策只受与之相关的多选路由上的状态改变有关。因而在这种方式下，中间节点无需维护其它节点或链路的状态，也无需进行路由计算，边缘节点也只需要维护始于本节点的多选路由上各链路的状态。
在源路由的情况下，入口节点和出口节点维护了始于本节点的多选路由，并且可以通过信令模块获知每条光路建立时所使用的波长，所以边缘节点有条件以光路为单位向其它节点公告状态改变指示。和传统的以链路为单位的状态改变指示相比，这样做可以大大降低状态更新消息给控制网络带来的负载。
4.实现全光网络中的动态波长路由的关键问题
（1）链路状态的管理方式
和传统的网络一样，全光网络的资源信息管理可以有两种方式，即集中控制式和分布式。
集中式的控制方式较为简单，全网所有的资源信息由一个控制节点来维护。集中式的资源信息管理框架下光路可以通过两种方法建立。第一种方法下控制节点向网络中的光节点提供资源可用信息的查询和修改接口。当连接请求到达边缘节点时，边缘节点向该控制节点发出查询，获取相关的资源可用信息以建立光路；当连接需要被建立或者被拆除时，边缘节点向控制节点发出修改相应资源状态的指示。
第二种方法下所有的连接请求都被直接提交给控制节点，控制节点按照其维护的信息选择合适的路径和波长，然后通知网络中相应的节点进行资源预留；连接需要被拆除时，控制节点向相关节点发出资源释放指示[3][4]。前一种方法下控制节点只需要维护网络中的资源可用性信息（例如所有链路上的波长使用状况），而光路的建立和拆除，光路的管理由光节点上的信令协议（存在于光节点之间和光节点和边缘节点之间）来完成，后一种方法下控制节点还需要维护全网所有的光路，而光网络的信令过程（实际上只存光节点和控制节点之间）在于相对比较简单。这两种集中式的方法下控制节点可以维护准确的全网资源可用性信息，可以全局的计算最佳的路由，从而使网络具有最好的性能。
分布式的方法由于其可扩展性和稳健性较好而得到了很大的关注。按照寻路方式的不同，分布式的资源信息管理又可以分为边缘节点管理和所有节点管理两种。在源路由的模式下[5][6][9]，由于中间节点不需要进行路由选择，因而不需要维护网络中其它节点上的资源信息。网络的边缘节点（也就是光路建立时的源节点）维护了全网所有（或者部分）节点（或者链路）上的资源可用信息。连接请求到达时，边缘节点按照其维护的信息进行路由计算，并选择合适的波长来建立光路。在逐跳路由的模式下[11][12]，路由决策逐跳进行，所以网络中的每个节点都需要维护其它所有节点或者邻居节点的资源可用信息。这两种模式下，节点上维护的资源信息都需要通过某种方式更新。
集中式的资源信息管理方法实现简单，运行维护较为方便，但是其可扩展性不强，随着网络规模的扩大和网络动态性的增加，仅仅使用一个节点来维护所有的信息可能导致该控制节点不堪重负。另外，
在这种方式下存在单点故障（Single Point of Failure），一旦控制节点崩溃，则光网络无法继续提供服务。分布式方法实现较为复杂，运行和维护费用高，但是可扩展性和容错性较好。采用何种管理方式取决于网络规模，网络动态性等因素。由于光网络中的集中式资源管理方法和传统网络有较为类似，所以下文将着重讨论分布式的资源信息管理方法和寻路方法。
（2）分布式方法下链路状态的更新方式
链路状态信息更新的方法有如下几种：
边缘节点在收到连接请求以后向该连接请求的下游节点发出探询请求，把探询的结果作为最新的链路状态信息来使用；
节点周期性地向其它所有节点发出状态公告，以让其它节点更新各自的状态信息；
边缘节点周期性地沿着所有始于本节点的多选路由向所有可能的目的节点发出探询请求，以更新状态信息；
由信令事件触发，向相关节点发出状态改变通告，以更新这些节点上的状态信息。
从第3部分的讨论可知，由于光网络本身的特点，采用事件触发的状态信息更新方式较为合理。
（3）路由选择
在波长交换网络中路由选择有两种方式：1)依据全网资源信息动态计算（Dynamic Routing）[7][10][11][12]；2)网络初始化时配置一条（Fixed Routing）或者多条（Fixed Alternate）固定路由[8][9] [15][16][18]。如前所述，分布式的全动态路由方法的性能依赖于准确的链路状态信息，这些信息通过扩展后的寻路协议例如OSPF-TE来更新，节点依据这些信息，使用最短路径算法计算获得优化的路由，这种方法的计算和控制消息负载开销均较大。固定多选路由是在源和目的节点之间设置多条可选的路径。连接请求到达时，源节点按照一定的规则选择其中的一条并尝试建立光路。这种方法事实上是将路由的计算离线完成，因而实现较为简单，另外由于路由决策由源节点完成，因而网络中的其它节点无需维护除本节点以外的节点的资源信息，故而开销小。[18]中Ramamurthy等指出固定多选路由在性能上线性逼近全动态路由。所以可以说固定多选路由是复杂性和性能上一个很好的折衷。
5.基于固定多选路由的半动态寻路机制
基于以上的讨论，我们提出一种基于固定多选路由的半动态寻路算法。本算法的基本原理是：每个边缘节点维护了始于本节点的所有可能的光路的状态；以光路的建立与拆除等为条件，触发边缘节点向其它所有边缘节点发送状态更新消息。
（1）光路状态的维护
假设和某边缘节点具有源宿节点对关系的节点数目为N，每个源宿节点对之间的多选路由数目为M，所有路径中最长的跳数为H，每根光纤上复用的波长数目为W，则该边缘节点将所有的可能的光路（也就是所有可能的路径和波长的组合）的状态组织成一个（N×M ×W）行H列的位图B，并在最左侧增加一列。B的每一行表示一条可能的光路，每一行中的第一个元素表示该光路是否可用，其余的元素依次表示该光路所经过的各链路上相应波长的可用状态。当光路状态发生变化时（被建立或者拆除），该光路的源节点就向其它所有边缘节点发出相应链路状态改变的通告，收到通告的边缘节点修改B中的相应元素。
当连接请求到达边缘节点时，边缘节点首先在B中到与所请求的目的节点相对应的行，并计算通往目的节点的各多选路由上面可用的光路的数目，然后选取其中可用光路数目最大的多选路由，并选择一个波长用以建立光路。
（2）基于事件的触发更新机制
位于网络边缘的节点在获知连接建立或者拆除时，向其它所有的边缘节点发出一个状态改变指示。该指示包含三元组（R,λ,OP），其中：R为该光路所使用的路由，依次包含该路由上所有节点的编号；λ为光路使用的波长；OP是在光路上的操作，包括建立和拆除。对于对光纤的网络，λ扩充为光纤号和波长号的组合，用以标识特定光纤上的某个波长。注意这里一条光路状态的改变（而不是链路状态改
变）只触发一次更新消息。除了正常的信令消息，来自LMP[20]的消息也可以被添加到触发更新中来。这样在网络发生部分故障时，所有
节点都将相应的光路设置为不可用，待故障恢复时重新启用。
虽然有较多的文献提到基于事件的更新机制[5][6][7][11][17]，但是已提及的基于事件的更新机制只是基于定时器的更新机制的简单扩充，因而它们所谓的事件是链路事件而非光路事件。由于波长交换网络中状态变化的相关性较强，基于光路事件的触发比起基于链路事件的触发，更新消息的负载要低得多。
（3） 状态更新和选路机制
边缘节点收到（R ,λ,OP ）三元组后，遍历本地多选路由表，到受影响的多选路由，并修改B 中相应的光路状态。
当去向目的节点d 的连接请求到达边缘节点s 时，s 首先利用B 计算（s,d ）之间各多选路由上可用的光路的数目，然后选择如下的多选路由之一：
塑料拖把头最小负载路由：可用光路数目最多的多选路由；
最大负载路由：可用光路数目最少的多选路由；
首条满足条件的路由：第一条可用光路数目大于某一阈值的路由。
路由选定以后，就可以在该路由上按照现有的波长选择算法[1][2]选择一个波长，并提交信令模块开始建立光路。
（4） 捆绑更新和波长集合
为了进一步降低更新消息负载，可以考虑使用捆绑更新机制。每个边缘节点只有在适当数目的光路状态发生改变以后，才向其它边缘节点发送状态更新消息。但是这样做会导致边缘节点上维护的状态信息得不到及时的更新，从而提高光路建立过程中发生资源冲突的概率，解决的方法是采用光路集合（或者称为波长集合）。如（3）中所述，在选定路由以后，边缘节点按照既有的算法选择一个波长用以建立连接。为了降低捆绑更新的影响，可以让信令协议携带一个波长集合，该集合包含了一个或者多个上游所有节点上可用的波长，每到一个节点就和该节点上可用的波长集合取交集。如果到达出口节点时该波长集合还不为空，则出口节点按照一定的规则（例如First Fit 或者Random ）选取其中的一个，然后反向建立连接。仿真结果表明，使用波长集合对于消除捆绑更新带来的链路状态不准确性比较有效。
（5） 仿真结果
图2给出了捆绑2个或者三个光路事件更新时，是否使用波长集合对选路准确性的影响。Blocked_x_y 表示一次更新绑定x 个光路事件，并使用y 个波长来初始化波长集合时，连接请求在中间或者出口节点处被阻塞的比例，failed_x_y 表示一次更新绑定x 个光路事件，并使用y 个波长来初始化波长集合时，连接请求在入口节点被阻塞的比例，这两个比例之间的相互关系反映了边缘节点选路的准确程度。可见在使用捆绑更新的情况下，如果波长集合中
P e r c e n t a g e Network Load (Erlang)
图 2波长集合对消除捆绑更新
带来的不准确性的影响
B l o c k i n g P p r o b a b i l i t y Network Load (Erlang)
防水微动开关图 3捆绑更新和波长集合对 阻塞概率的影响
的波长数为1，则选路准确性大大下降；如果增加波长集合中波长的数目，则可以非常有效地提高选路的准确性。
图3给出了结合使用捆绑更新和波长集合对于网络阻塞概率的影响。LL_x_y表示在使用最小负载路由算法的情况下，一个更新绑定x个光路事件，并使用y个波长来初始化波长集合。可以看出，虽然捆绑更新会一定程度上降低选路准确性，从而提高连接请求被阻塞的概率，但是波长集合完全可以弥补这一问题。捆绑更新和波长集合的结合使用可以在不牺牲网络性能的前提下，降低更新消息负载。
6.结束语
控制面是构建下一代波长交换光网络的关键。本文综述了波长交换网络中现有的动态寻路算法，讨论了波长交换网络中寻路问题的特点和实现动态寻路算法的关键问题，并给出了一种基于固定多选路由
的寻路算法。该寻路算法充分考虑了波长交换网络的特点，利用光路事件作为触发更新的条件，并使用捆绑更新和波长集合，使用较小的控制消息负载就可以达到比较好的网络性能。
参考文献
[1]Zang H., Jue J. and Mukherjeey B, A review of routing and wavelength assignment
approaches for wavelength routed optical WDM networks [J]. Optical Networks, 2000, 1:47-60
[2]Assi et.al. Optical networking and real-time provisioning: an integrated vision for the
next-generation internet [J]. IEEE Network, 2001, 15(4):36-44.
[3]Ramu Ramamurthy, Sudipta Sengupta, Sid Chaudhuri, Comparison of centralized and
distributed provisioning of lightpaths in optical networks [A], the Proceedings of OFC 2001, Oceanport, NJ, USA, Mar. 2001, MH4-1 -MH4-3
[4]James Cai, Andrea Fumagalli and Chi Guan, Centralized vs. Distributed On-Demand
Bandwidth Reservation Mechanisms in WDM Ring, the Proceedings of OFC 2001, Oceanport, NJ, U
SA, Mar. 2001, MH2-1 –MH2-3
[5]Yousong Mei and Chunming Qiao, Efficient distributed control protocols for WDM
all-optical networks [A], the Proceeding of Sixth International Conference on Computer Communications and Networks [C], Las Vegas, NV, USA, Sep. 1997, pp150-153
[6]Rajiv Ramaswami and Adrian Segall, Distributed Network Control for Optical Networks [J],
IEEE/ACM Transactions on Networking, Vol. 5, No. 6, Dec. 1997, pp936-943
[7]Ahmed Mokhtar and Murat Azizoglu, Adaptive Wavelength Routing in All-Optical Networks
[J], IEEE/ACM Transactions on Networking, Vol. 6, No. 2, Apr. 1998, pp197-206
[8]Ling Li and Arun K. Somani, Dynamic Wavelength Routing Using Congestion and
Neighborhood Information [J]. IEEE/ACM Transactions on Networking, Vol. 7, No. 5, Oct.
1999, pp779-786
[9]Pin-Han Ho and Hussein T. Mouftah, A Novel Distributed Control Protocol in Dynamic
Wavelength-Routed Optical Networks [J]. IEEE Communications, Dec. 2002
[10]Jun Zhou and Xin Yuan, A Study of Dynamic Routing and Wavelength Assignment with
Imprecise Network State Information [A], Proceedings of ICPPW'02 [C], Vancouver, Canada, 2002, pp.207-213.
[11]Jason P. Jue and Gaoxi Xiao, An adaptive routing algorithm for wavelength-routed optical
networks with a distributed control scheme [A], Proceedings of the Ninth International
