（信号与信息处理专业论文）波长路由光网络中路由问题研究.pdf

浙江 业大学硕士学位论文 波长路由光网络中路由问题研究 摘要 随着光网络技术的快速发展，光纤通信己从单纯的传输技术逐步 演化为重要的组网手段。以波分复用( w d m ) 技术为基础的光传送网络 由于其大容量和良好的灵活性而成为目前光通信领域研究的焦点。r w a 是w i ) m 光网络中的关键问题，它是指光网络中某节点对间有光路建立请 求时，如何寻找从源节点到目的节点的路由并在该路由上分配波长的 问题。 本论文主要研究w d m 光网络的路由选择优化算法，以有效的改善网 络性能为目标。首先研究了路由算法中最重要的链路权重定义，在一 般权重定义方法基础上提出了两种改进的权重定义方法，新定义法能 考虑波长分配等多方面因素，通过分析和仿真说明了新定义法的优点。 然后针对小规模光网络，给出了路由问题的最短路径算法和混合整数 线性规划算法，并用l i n g o 软件对算法编程求解，得出满足给定条件的 网络路由设计方案。接下来针对网络规模较大的情况，研究了基于遗 传算法的路由优化算法，算法以最短路径为优化目标寻求最佳的路由 方案，需求分析后用v c + + 进行编程实现，并通过对n s f n e t 网络路由的 优化设计来验证算法的正确性和优越性。最后针对实际光网络中业务 连接请求小于一个波长粒度的情况，在小粒度的光连接层面考虑了网 络的路由问题。以最大化网络的吞吐量为目标给出了w d m 网状网中基于 塑垩! 些查兰堡主兰堡堡苎 共享风险链路组( s h a r e dr i s kl i n kg r o u p ) 的共享保护备用路由算法 和专用保护备用路由算法，两算法都支持业务量的优先级，具有网络 的抗毁性，通过仿真证明这两种路由算法有效降低了网络的阻塞率， 提高了波长利用效率。 关键词：波分复用，波长路由分配( r w a ) ，链路权重，混合整数 线性规划( m i l p ) ，遗传算法，保护备用路由 浙江 业大学硕士学位论文 t h es t u d yo fr o u t i n gp r o b l e mi nr w an e t w o r k s a b s t r a c t w i t ht h ed e v e l o p m e n to fo p t i c a ln e t w o r k i n gt e c h n o l o g i e s ，o p t i c a l f i b e rc o m m u n i c a t i o nh a sb e e na l li m p o r t a n tw a yf o rc o n s t r u c t i n gt h e b r o a d b a n db a c k b o n en e t w o r k s o p t i c a ln e t w o r kt h a tb a s e so nw a v e l e n g t h d i v i s i o n m u l t i p l e x i n g ( w d m ) i s t ob et h ef o c u so ft h e o p t i c a l c o m m u n i c a t i o nr e s e a r c ha r e ab e c a u s eo fi t se n o r m o u sb a n d w i d t ha n d f l e x i b i l i t y r o u t i n ga n dw a v e l e n g t ha s s i g n m e n t ( r w a ) i sc o n s i d e r dt ob e ak e yp r o b l e mi ns u c hw d mn e t w o r k s g i v e nac a l lo rl i g h t p a t ht ob e e s t a b l i s h e db e t w e e nt w on o d e s ，t h er w a p r o b l e mi st of i n dar o u t ef r o m t h es o u r c en o d et ot h ed e s t i n a t i o nn o d ea n dt h e na s s i g naw a v e l e n g t ht o n l i sr o u t e i nt h i sp a p e rw es t u d yt h er o u t es u b - p r o b l e mo fw d mn e t w o r k si n o r d e rt oi m p r o v et h en e t w o r kp e r f o r m a n c e s t h eg e n e r a lr w aw e i g h t d e f i n i t i o n sa r es t u d i e df i r s t l y t h e nb a s e do nt h e s ed e f i n i t i o n s ，t w on e w w e i g h td e f i n i t i o n sa r ep r e s e n t e d n e wd e f i n i t i o n st a k em o r ef a c t ss u c ha s w a v e l e n g t ha s s i g n m e n ti n t oa c c o u n t a n dt h en e ww e i g h t sa r ee v a l u a t e d b ys i m u l a t i o n sa n da n a l y s i s a f t e r w a r d s ，ar e s e a r c ho ns m a l ln e t w o r k r o u t i n gp r o b l e mi sf o c u s e do nt h es h o r t e s tr o u t i n ga l g o r i t h m sa n dm i x e d i n t e g e rl i n e a rp r o g r a m m i n ga l g o r i t h m so fr w a n e t w o r k s t h eo p t i m i z e d 猫 浙江工业大学硕士学位论文 r o u t em e t h o d sa r es o l v e da n de v a l u a t e di ns i m u l a t i o n sb yt h em a t h e m a t i c a l s o r w a r el i n g o t h e nar o u t ea l g o r i t h mb a s e do ng e n e t i ca l g o r i t h mi s p r o p o s e df o rl a r g e rn e t w o r k s t h i sa l g o r i t h mi sa i m e da tc h o o s i n gt h e s h o r t e s tr o u t e a n di sr e a l i z e db yv c 抖p r o g r a m s t h ec o l t e c t n e 豁a n d a d v a n t a g eo ft h i sa l g o r i t h ma r ep r o v e di nt h en s f n e tn e t w o r kr o u t e p r o b l e m s a tl a s t ，b e c a u s et h eg r a n u l a r i t yo fc o n n e c t i o nr e q u e s ti sm u c h s m a l l e rt h a nt h eg r a n u l a r i t yo fo n ew a v e l e n g t h ，t h er o u t ep r o b l e ma tt h e c o n n e c t i o nl e v e li sc o n s i d e r e d f o rt h eg i v e nm e s hn e t w o r kr e s o u r c e s ，t h e s h a r e dp r o t e c t i o na l t e r n a t er o u t i n ga l g o r i t h ma n dd e d i c a t e d p r o t e c t i o n a l t e r n a t er o u t i n ga l g o r i t h mu n d e rt h es h a r e dr i s k l i n kg r o u p s ( s r l o ) c o n s t r a i n t sa r ep r e s e n t e d b o t ho ft h et w o a l g o r i t h m ss u p p o r td i f f e r e n t p r i o r i t yo f t h et r a f f i ca n dt h eo b j e c t i v ei st om a x i m i z en e t w o r kt h r o u g h p u t t h es i m u l a t i o nr e s u l t sb a s e do nn s f n e tn e t w o r ks h o wt h a tt h e p e r f o r m a n c e so ft h et w oa l g o r i t h m sw ep r o p o s e da l ei m p r o v e d ，e s p e c i a l l y f o rb l o c k i n gp r o b a b i l i t ya n d w a v e l e n g t hu s a g e k e yw o r d s ：w a v e l e n g t hd i v i s i o nm u l t i p l e x i n g ( w d m ) ，r o u t i n ga n d -j w a v e l e n g t ha s s i g n m e n t ( r w a ) ， w e i g h t ， m i x e d i n t e g e r l i n e a r p r o g r a m m i n g ，g e n e t i ca l g o r i t h m ，p r o t e c t i o na l t e m a t er o u t i n g 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研 究工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文不 包含其他个人或集体已经发表或撰写过的研究成果，也不含为获得浙江工 业大学或其它教育机构的学位证书而使用过的材料。对本文的研究作出重 要贡献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法 律责任。 作者签名：日期：矽4 年月y e t 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内容 编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和 汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保盔弘 ( 请在以上相应方框内打“母) 作者签名： 导师签名： 日期：“年j 矿月7 阳 日期：州年f 矿月矿p 日 浙江工业大学硕士学位论文 第一章绪论 1 1 波分复用( w d m ) 技术的应用和发展 1 1 1w 1 ) m 的产生 随着网络化时代的到来，全球“信息高速公路”的发展，以及宽带视频、多 媒体业务的日益兴起，特别是i n t e r n e t 业务的快速增长，对广域骨干网的带宽提 出了越来越高的要求“，建设高速大容量的宽带综合业务传输平台已经成为现代 信息技术发展的必然趋势。 由于光纤具有巨大的潜在带宽( 接近5 0 t b s ) ，同时还具有成本低、信号失真 和衰减小( 可小于0 2 d b k m ) 、功率要求低以及空间要求小等优点，因此，目前在 骨干网中基本上都使用光纤链路来传输数据。 单个波长的传输速率上限主要受限于集成电路硅材料和稼砷材料的电子迁移 率，还受限于传输媒质的色散以及所开发系统的性能价格比是否合算。采用电学 时分复用( t 嗍，t i m ed i v i s i o nm u l t i p l e x i n g ) 技术来提高传输容量的做法己经逐 渐接近极限，没有太多潜力可挖。因而唯一现实的出路是转向光学波分复用 ( w d m ，w a v e l e n g t hd i v i s i o nm u l t i p l e x i n g ) 方式。w 1 ) m 以波长为单位将光纤带宽 分成细粒度的信道，可以很好的弥补电设备与光设备的性能差别。采用光的波分 复用( w d m ) 的光网络以其宽带宽、组网灵活、扩容简单、透明传输和可以升级等特 点，越来越受到人们的青睐。典型的w d m 点对点系统是由发射机、波分复用器、波 分解复用器、掺饵光纤放大器( e d f a ) 、光纤和光接收机等设备组成。 1 1 2w d m 技术的发展 w d m 就是指在一根光纤中同时传输多个波长光信号的一项技术。其基本原理是 在发送端将不同波长的光信号组合起来( 复用) ，并耦合到光纤中进行传输，在接 收端将组合波长的光信号分开( 解复用) ，并作进一步处理，恢复出原信号后送入 不同的终端。其突出优点为：能在一根光纤中同时传输不同波长的几个甚至成百 浙江工业大学硕士学位论文 上千个光载波信号，不仅具有传输容量大，能充分利用光纤的带宽资源，提高系 统的经济效益。而且具有对高层协议适应性强，以及易于扩展等优点。 采用w d m 技术可以将每根光纤的巨大带宽分成许多互不重叠的波长信道，每个 信道都可以并行、异步和高速地按当前电子处理数据的极限速率来传输数据，从 而可以充分利用光纤的巨大带宽，提供丰富而廉价的带宽资源。 随着光通信技术的不断发展，目前己经可以做到在一根光纤中加载1 0 0 多个波 长的光信号。现在的密集波分复用系统( d w d m ，d e n s ew a v e l e n g t hd i v i s i o n m u l t i p l e x i n g ) 常用的复用波长数量是8 ，1 6 ，3 2 ，6 4 乃至更多，单通道速率多为 2 5 g b i t s 和1 0 6 b i t s ，单波长4 0 g b i t s 的系统也即将开始商业化“。 w d m 从提出到今天，短短数年，一直保持强劲的增长势头。经过数年的发展和 应用，波分复用( w d m ) 技术己趋于成熟，而且越来越成为现代通信系统中不可替代 的传输技术。目前，w d m 系统的传输容量正以极快的速度向前发展，直接基于w i ) m 传输的业务也越来越多。w d m 技术正对光通信的发展起着重要的作用，其作为现代 超大容量传输规模的复用技术的优越性将体现得越来越为明显。 1 2w d m 光网络中的路由与波长分配问题 w d m 光网络被认为是构建下一代光网络的有力候选者之一”。但是由于网络资 源有限( 如波长数，收发器数目等) ，不可能在网络中为每一对节点对都建立一条 直接相连的光路。因此针对于不同的网络需求，需要考虑对现有可用资源进行高 效利用和优化设计。 w i ) m 光网络的核心问题是优化设计光路的选路和波长分配( r w a ，r o u t i n ga n d w a v e l e n g ha s s i g n m e n t ) ，寻找一条合适的光路并为之合理地分配波长，使有限的 资源充分发挥作用，以提供尽可能大的通信容量。 从总体上看，r w a 中的路由和波长分配是不可分割的，但是由于r w a 是个 n p - c ( 非确定型多项式一完全，n o n d e t e r m i n i s t i cp o l y n o m i a l c o m p l e t e ) 问题， 要在合理的运算时间内解决大型网络的r w a 问题是不可能的，只能对规模有限的网 络优化作出r w a 问题的解答，所以r w a 问题经常被分解为路由子问题和波长分配子 问题。通常先为光网络选路，即先解决路由子问题，然后在满足一定优化性能的 情况下逐一为光路分配波长。它们大多建立在传统的电路交换网络无向多图 ( u n d i r e c t e dm u l t i g r a p h ) 的模型之上，在该模型中首先为每个光路请求找出最佳 路由，然后分配波长。本文主要研究的是路由问题，对波长分配算法不做深入研 究，对路由选择中涉及到的波长分配问题基本都采用最常用的波长分配算法，如 浙江工业大学硕士学位论文 f i r s t f i t 算法”。其中f i r s t f i t ( f f ) 算法的思路是将所有的波长编号，按照 编号从小到大的顺序搜索可用的波长，最先找到的那个可用波长被分配给光通道。 光路路由问题是确定光路经过哪些光纤链路，从整体上讲它可以分为基于全 网信息和基于局部信息的两种方式，这两种方式将会在第二章的权重定义和后面 的选路算法中得到体现。所谓基于全网信息是指做出路由决策的节点维护有全网 每一条链路的资源信息。这种方式既可适应于集中式控制的网络，也可适应于分 布式控制的网络。基于全网信息的路由策略是基于端到端的通路来选择路由的， 而基于局部信息的路由方式是以逐跳方式确定路由的。与基于全局信息的路由策 略相比，基于局部信息的路由策略更为灵活，具有很强的可扩展性，但其缺点是 连接建立的时间较长，信令过程比较复杂。目前，基于全网信息的路由方式是一 种较为成熟的路由策略，因此本文着重讨论这种路由策略中的各种算法。 1 3 光网络的拓扑结构 删光网络本质上是一组节点和一组点到点的光纤链路的集合。拓扑结构就是 网络的形状。任何通信网络都存在两种拓扑结构：物理拓扑和逻辑拓扑( 也称为 虚拓扑) 盯。其中物理拓扑表征网络节点的物理结构，从组成上讲，它是网络节点 与光纤链路的集合。逻辑拓扑则表征网络节点间业务的分布情况。 1 3 1 物理拓扑 在w d m 技术发展的早期，点到点的连接是唯一的应用方式。随着节点技术的发 展，各种物理拓扑的实现成为可能。除简单的点到点的连接方式外，基本的物理 拓扑有线形、星形、环形、树形和网孔形，分别如图1 1 所示。 浙江工业大学硕士学位论文 o o o ( a ) 线形 ( b ) 星形 c c ) 环形 ( d ) 树形( e ) 网孔形 图1 1 光网络基本的物理拓扑结构 各种拓扑结构各有特点，在选用时，应根据建设成本、站点分布、业务需求 以及网络的可扩展性等多方面因素综合考虑。 1 3 2 逻辑拓扑 逻辑拓扑与物理拓扑紧密关联，常见结构有星形、平衡式拓扑和网状拓扑， 如图1 2 所示。星形逻辑拓扑有单星形和双星形两种。在单星形结构中( 如图卜2 ( a ) 所示) ，存在一个中心节点负责与其他节点沟通。这样，除中心节点外，其他节点 之间的所有通信联系都要经过中心节点中转。图卜2 ( b ) 所示为双星形结构，在这 种配置中，所有节点都与两个中心节点有通信联系，同时中心节点之间也有通信 联系。平衡形拓扑只存在于线形与环形物理拓扑的网络中。网状拓扑有很强的生 存能力，但相应的控制和管理相当复杂。综上所述，w d m 网络的物理拓扑与光缆线 路的敷设路由直接相关，通常不可能随业务改变而随时改变。利用光路概念构成 的逻辑拓扑与节点之间的业务分布情况紧密相关，可以由软件配置而比较容易改 变。 浙江工业大学硕士学位论文 ( a ) 单星形 ( c ) 平衡形( d ) 网孔形 图l - 2 光网络基本的逻辑拓扑结构 1 4 w d m 光网络路由问题的研究现状 选路和波长分配( r w a ) 问题经常被分解为路由子问题和波长分配子问题。通常 先为光网络选路，然后逐一为光路分配波长。目前解决路由子问题的方法大致如 下： 固定路由选路法( f r ，f i x e dr o u t i n g ) ：固定路由是最简单的，它的选路是 事先进行的，网络拓扑结构己知后，按照标准最短路径算法( 比如d i j k s t r a 算法和 b e l l m a n f o r d 算法) 为每个节点对分配固定的光路。当光路请求到达时，源、目的 节点对之间的通信连接总是建立在预定好的路由上。如果存在多个符合要求的路 径，则在其中随机选取一个，并在相应的固定路由上分配波长以建立光路。如果 采用f r 路由，r w a 问题就可以简化为波长分配问题，从而大大简化网络的控制和管 理。但是如果在一个设计的通道上没有可利用的波长，这个连接都将被阻塞。而 且无法随网络业务的动态变换自适应调节节点对之间的路由，因此会导致网络性 能的劣化，阻塞率较高，同时在该算法下网络不具备链路故障恢复能力。 固定备用路由选路法”。( f a r ，f i x e d - a l t e r n a t er o u t i n g ) ：其基本思想是为 每个节点对预先确定多条备用路由，并按一定的优先级顺序排列。排在最前面的 称为主路由，其他的视为备用路由。当业务到达时，按照工作路由建立光通路， 当工作路由已被占用或失效时，选择次优路由。与固定路由方案相比，这种选路 滁渤 浙江工业大学硕士学位论文 法的优点是使网络的阻塞率大大降低，并且使网络具有故障恢复能力，但其时间 复杂度也有所提高。本论文最后一章会讨论备用路由算法，提出基于共享风险链 路组( s r l g ，s h a r e dr i s k l i n kg r o u p ) 的共享保护备用路由算法和专用保护备用 路由算法，两种算法都能有效降低高业务量、高优先级的光路连接的阻塞率。 自适应选路法( a r ，a d a p t i v er o u t i n g ) ：自适应路由的基本思路是路由根 据网络的状态动态地确定。它的实现可采用以下两类方法，第一类是预先为节点 对之间确定多条备用路由，与固定备用路由方案类似，当连接请求到达时，从备 用路由中依据网络状态动态选择一条路由，并将其确定为主用路由。第二类方法 是不预先为节点对确定备选路由，当连接请求到达时根据网络状态为其确定路由。 由于自适应路由方案根据网络的实际状态动态选择路由，所以业务的阻塞率同前 两种方案相比最低，但其时间复杂度也大大提高，因此在需要自适应路由方案时 要综合考虑性能和效率两个方面的因素。 整数线性规划法( m p ) ”1 ；是一种常用的选路和波长分配算法，可分为基于流 的i l p 和基于通道的i l p 。该算法的基本思路是：列写优化目标方程一列写约束条 件方程斗求解线性规划。这种方法选路灵活，适用于有或无波长转换功能的小型 网络，网络可以具有或不具有故障恢复机制。本文后面会讨论用l i n g o 工具对光 网络拓扑设计的整数线性规划方程进行求解，最终求得优化路由的方法。 路由扩展方法：这是一种局部的方法，基本思想是在一段链路中插入一个节 点，用新节点与原链路两端节点构成的两段链路来替换原来的一段链路，这样就 构成了一个新路由，利用逐步扩展思想来构造节点之间所有的可能连接方式“”。 此方法既可以用于网络的实际拓扑，也可以用于网络虚拓扑情况。在网络实际拓 扑上扩展得到的路由是网络节点之间的物理连接关系，而以虚拓扑为基础得到的 扩展路由则是节点之间的波长连接关系。它在路由的创建，维护过程中有重要的 应用。比如在网络故障条件下，就可以使用路由的扩展方法来进行局部的恢复路 由搜索，以最快的速度完成业务的恢复。 1 5 本文的主要研究内容和结构安排 本文主要研究的是路由问题，为了简化r w a 问题的复杂性，在没有特殊说明 的情况下假设所有的o x c 节点都提供波长转换功能，即研究的是虚波长通路的选 路问题。 第一章介绍了w 1 ) m 光网络的应用和发展、光网络的拓扑结构，详细分析了当 前光网络路由问题的研究现状。 浙江工业大学硕士学位论文 第二章首先介绍波长路由光网络的基本术语，然后对网络路由问题中的权重 定义进行研究，在传统定义法基础上给出了两种改进型的权重定义方法，然后证 明新定义方法能综合考虑光网络多方面的因素，具有相对的科学性，并能改善网 络性能。 第三章针对小规模光网络，首先研究了经典的最短路径路由算法，还用规划 方法求解了最短路由问题，然后针对光网络的特殊性给出了双向光纤的最短路由 问题。在图论网络规划的基础上，以最小化网络的拥塞下限为优化目标，给出了 光网络路由的混合整数线性规划( m i l p ) 模型来解决虚波长通道( v w p ，v i r t u a l w a v e l e n g t hp a t h ) 光网络拓扑设计问题。算法用一个专用规划软件_ i i n g o 进 行编程实现，具有一定的研究价值和应用价值。 第四章针对中大规模网络，从整个网络的状态来考虑路由选择，给出了基于 遗传算法的路由优化算法，然后进行需求分析，对此算法进行编程实现。算法程 序具有通用性并且体现现实工程需求。通过对此算法优化后的路由结果进行分析， 证明了此算法的正确性和优越性。 第五章针对实际网络中业务流请求小于一个波长粒度的情况，从小业务量的 光连接( c o n n e c t i o n ) 层面考虑网络细粒度的路由问题。以最大化网络的吞吐量 为目标提出了w d m 网状网中基于共享风险链路组( s r l g ，s h a r e dr i s kl i n kg r o u p ) 的共享保护备用路由算法和专用保护备用路由算法，然后通过仿真证明两种算法 都能有效保证业务的可靠性要求，同时也表明了两种算法的性能。 浙江工业大学硕士学位论文 第二章r w a 光网络中权重问题的研究 2 1 波长路由的术语 光网络中的路由算法与研究一般的网络拓扑的路由算法不一样，在光网络中 的节点和链路有其特定的意义，因此有必要对光网络中的路由算法中涉及到的节 点和链路等术语进行介绍。 节点( n o d e ) ：光网络中的节点指的是o x c o a d m 或者波长路由器。在网络图论 中节点被抽象成顶点( v e r t e x ) 。 链路( 1 i n k ) ：网络中连接节点的线路，是承载信息流的通路。在光网络中， 由于连接两个节点的光纤都是成对出现的，因此在研究光网络的波长路由算法的 时候，都是将光网络中的链路作为无向边来处理。 信道( c h a n n e l ) ：链路中承载信息流传送单位的通路。即一条链路中有多条信 道，每一条信道承载一个信息流单位。光网络中信道特指波长信道。 通道( p a t h ) ：开始于光连接请求的源节点，结束于光连接请求的终节点，由 一条或多条信道首尾相连构成的传送数据流的通路。一条通道经过的首尾相连的 链路就构成了一条路径。 节点的度( d e g r e e ) ：与该节点相连链路的数量。 网络连接度a ：它的定义为网络中链路的数目和全连接( 每两个节点之间都有 光纤直接连接) 网络中链路数的比。一个节点数为n 的网络，其全连接时链路数是 n * ( n - 1 ) 2 ，网络连接度为：a = 2 * l n ( n 一1 ) ，l 是实际链路数目。很显然，a 越大 则网络中链路数越大，a = l 就是全连接网。为了保证网络的全连通，网络中的链路 数不能少于旷l ，因此a 2 n 。 波长通道( w p ，w a v e l e n g t hp a t h ) ：是指o x c 节点没有波长转换功能，在波长 路由光网络中，在光空闲信道所有链路( l i n k ) 上都要分配相同的波长，这样建立 起来的光路满足波长连续性的限制。如果在它所经过的所有链路中，找不到一条 有一个共同空闲波长信道的路由，就会发生波长阻塞。 虚波长通道( v w p ，v i r t u a lw a v e l e n g t hp a t h ) ：是指o x c 节点具有波长转换功 能，在波长路由光网络中，在光空闲信道的所有链路( l i n k ) 中可以分配不同频率 的波长，这样建立起来的的光路不受波长连续性的限制。 链路、光纤和信道：w d m 光网络中，每个链路包含多个光纤对，其中每个光纤 浙江工业大学硕士学位论文 对由两个相向的单向光纤组成，每根光纤复用多个波长信道。 波长连续性限制：每一个光连接的波长在它从源到目的终端所经过的所有链 路上均保持不变。 不同波长限制：所有共享同一个光纤的连接必须被分配不同的波长信道。 波长路由光网络由于存在着“波长连续性”限制因素和“不同波长”的信道 分配原则等约束，所以在波长选路网络中必须采用一种科学的、合理的选路算法 和波长分配算法来优化网络性能、减少波长的阻塞和对节点设备的端口数要求。 而且由于路由波长问题问题是个n p - c 问题“，要在合理的运算时间内解决大型网 络的r w a 问题常常是不可能的，所以通常将r a w 问题强行拆分成路由予问题和波长 分配子问题分别加以解决。一般的路由选择问题大多基于最短路径算法，通过设 置不同的链路权重，可以得出不同的路由优化目标。可见权重和路由问题密切相 关，在光网络r w a 问题中有十分重要地位，所以有必要对它进行系统地研究和改进。 本章首先就一般路由算法中涉及的权重定义法进行研究分析，结果发现常用 的传统权重定义法虽能简化问题的复杂性，降低计算复杂度，但却忽略一些重要 的因素，而某些时候这些因素的忽略将导致网络模型的不确切性和过大的误差， 因此需要对这类权重定义法进行改进。针对这个问题，本章在传统定义法的基础 上给出了两种改进的权重的定义方法。 2 2 传统的权重定义法 一般的路由问题大多基于最短路径算法，虽然可以有不同优化目标，但基本 上都跟链路权重有关。所以先介绍一些传统常用的权重定义方法及其相应的算法： 1 以跳数或距离作为权重：如果网络的总负载较重，那么一般根据节点问的 实际距离或节点间跳数设定链路权重。跳数可以看做距离的特殊形式，即设每条 链路的长度都为l 的时候，距离问题就变成跳数问题。对应的算法如最小跳数路由、 最短距离路由，由于此类算法尽可能少地占用网络资源，因而在网络上能建立尽 可能多的连接。 2 以负荷量作为权重：如果网络总负载较轻，则根据链路上所承载的负荷量 ( 流量) 设定链路权重。算法往往选择具有最大空闲容量和的路由以保证总负载 平衡。具体算法如二部图法( b i p a r t i t eg r a p h ) “等。 3 以链路衰减作为权重：如果网络需要重点考虑功率和噪声限制因素，链路 权重的选择可以正比于链路的衰减，算法目标是得到链路总衰减最低的路由。 4 以时延作为权重：时延反映了信息在光路或物理链路上传播时所用的时间 或在节点处等候的时间。如果网络需要重点考虑时延，这时权重的取值可以采用 。9 浙江工业大学硕士学位论文 各链路的传输时延和节点的排队时延。 5 还有一种常用的权重定义法是把空闲信道边权值都设置为1 ( 或者规定为 某一定值c ) ，把被占用信道边权值设置为一“。这种定义法适用的算法有 a d a p t i v es h o r e s t c o s t p a t hr o u t i n g 算法“、不相交子图( d i s j i o n ts u b g r a p h ) 模型算法1 “、分层图模型法嘲等等。 2 3 改进的权重定义方法 由上文我们看到已经提出的大多数r w a 算法中权重定义方法比较简单，但也反 映出它的局限性，它们大都只是考虑了某一个方面的优化问题。比如最短路径或 是最小跳数算法考虑的是网络占用资源最少和通讯的延时最短，忽略了负载的平 衡，从而导致某些链路上过于拥挤，使得全网的总阻塞率升高。而负载平衡算法 过于强调业务量的均衡分配，忽略了通讯时延和网络资源有限所带来的性能下降， 在网络负载较重的情况下导致总阻塞率上升。同时r w a 算法的规则使得长通道遇到 阻塞的可能性大于短的通道，这便导致相对较远的节点对之间连接的不公平对待 问题。为了能有效解决以上各个方面的不足，我们提出了两种改进型的权重定义 法，通过改进，更合理地综合考虑了其他各方面的因素，从而能选择更合适的路 由路径。 2 3 1 “最大概率路径”定义法 这种新的权重定义法适用于v w p ( 虚波长通道) 网络，由于v w p 网络中波长是 逐段链路进行分配的，所以某一路由和波长分配方案中所需的波长数等于链路上 所能容纳的通道数，因而v w p 网络中路由和波长分配算法的目的就是采用一定的优 化策略使各个链路上分布的通道数尽可能平均。为了使光路尽可能的在网络中均 匀分布，这里引入一种改进的链路权值的定义： 以：幺二墨 ( 2 一i ) 以= 二土 ( 2 一) 其中f 眦为每条链路上的波长数目( 可以为固定值) ，e 为链路上通过的光路 数，以为链路的权重。则权重的定义相当于链路被选中的概率，它的范围为 0 ，i 】， 这样某条链路上通过的通道数越少，那么该链路被选中的概率就越大，链路的权 0 1 0 浙江工业大学硕士学位论文 值也就越大。选择路由时的算法可以采用近似于最短路径算法的d i j k s t r a 算法， 但需要把d i j k s t r a 算法求和步骤改为求积、最小化比较操作改为最大化比较操作 “”。因为在为通道寻找路由时，遵循使路由经过的路径中所有链路权值的乘积最 大原则，故把这样的路由方法称为“最大概率路径”法，它可以看作是求最短路 径问题的一个变种。通过此定义法能更好的为光路选路，又能使光路尽可能地均 匀分布。 2 3 2 “分散策略”定义法 针对当信道空闲时边权值设置为l ，信道被占用时边权值设置为o 。的定义方法 ( 这里称之为集中策略) ，可以把它归纳为： f1 ，当链路还有空闲信道时( 2 - 2 ) m ( ) 2 l 其他 其中0 表示节点i 与j 之间的链路，( ) 表示链路的权重。 这里对之进行改进，把改进的定义法称为分散策略。 l1 + 血d 以) 当 d ) f 时 ( 2 3 ) ( 屯) ： l c o 当口( 0 ) = f 时 其中d ( 毛) 表示当前时刻链路毛上已占用的信道数，显然o ( 屯) 的取值范围为 0 ，1 ，fj ，其中f 为每条边上的最大信道总数，c 为常数。 之所以称之为分散策略，是因为这种改进法鼓励将光路所占用的资源尽可能 地分散到整个网络中，以促使光路尽可能均匀地分布到各链路上。 下面简单说明以上两种策略的区别：假定节点a 和b 在某一通路p 上建立了一条 光路，且沿这条通路p 仍有空闲信道。对集中策略而言，p 上每条弧的代价仍保持 为1 ，而分散策略将每条弧的代价增加缸。如果下一个请求仍在节点a 、b 间建立 光路，则集中策略将仍在p 上建立光路，而采用分散策略的算法则是先对整个网的 状态进行刷新，然后根据刷新后全网的状态( 链路的新权重) 来确定把新光路建立 在哪一条通路上，因此它不一定仍在p 上建立光路，从而使资源更平均地分散开来， 这样能有效降低网络的阻塞概率。 分散策略的判定规则与集中策略一样，当节点收到连接请求时，通过执行最 短路算法( 比如d i j k s t r a j 算法) ，试图建立权值和最小的路由，如果得到的最佳路 径的权和为有限值，贝完成了一个新到达的连接请求的光路建立：否则光路请求 l l 浙江工业大学硕士学位论文 被拒绝。 2 4 传统的权重定义法与改进的权重定义法的比较 2 4 1 “最大概率路径”定义法优点 本节首先给出两种权重定义方法，如下所示： m l ( i ) = 只= f m p j i = 1 ，2 ，n 喇) = 警= 1 - p i ( 2 0 ) ( 2 5 ) 这里p l = ： ( 2 - 6 ) ( 2 - 4 ) 式给出的“链路权值”的一种定义，属于传统的权重定义法，它是以 当前每一条链路上分布的通道数目为该链路的权重；( 2 5 ) 式为2 3 1 节提出的第 一种改进型的链路权重定义，它的物理意义可以理解为当前该链路能够被任意路 由选择的概率。 这里把( 2 - 4 ) 式给出的方案称为策略i ，( 2 - 5 ) 式给出的求最大概率路径的 方案称为策略i i ，下面比较一下这两种策略的差别。 1 与策略i 相比，策略i i 在取舍路由时除了需要考虑路由所经历的各条链路 上已经分布的通道数目外，还与当前最大链路上的通道数目有关。 2 给定一条通道，如果通道上某一条链路容纳的通道数目变化了一个单位， 那么在策略i 中，这种改变无论发生在该通道所经历的哪一条链路上，对整个通道 优化测度的影响都是相同的。而在策略i i 中，可以明显地看到如果这种改变发生 在分布通道数目多的链路上，那么它对整个通道优化测度的影响要比发生在分布 路径数目少的链路要小。 3 策略i 这种优化方案形式简单、计算方便，但是存在一些问题，譬如利用 最短路径算法进行路由规划，发现某一段链路经过的光路特别多，这样导致那段 光链路过早发生拥塞，要想继续通过此链路进行路由，势必要增加该通道选路所 需要的波长数目。而策略i i 因为权重会随着光路数的变化而变化，这样使得后面 的连接请求可以绕过已经拥挤的光链路，因此在重选路由时不会发生增加所需波 长数目的情况。 浙江工业大学硕士学位论文 2 4 2 “分散策略”定义法优点 2 3 2 节提出的集中策略和分散策略的权重定义法，本节借助分层图模型的多 光纤网的动态r w a 算法，对这两种策略进行性能上的比较。采用计算机仿真的 方法，仿真时采用如图2 - 1 所示的物理拓扑。该网络类似于中国教育与科研计算机 网( c e r n e t ) 的拓扑，原本连接到清华的部分地区节点被改连到了北大和北邮，共 1 0 个节点，1 6 条链路，c e r n e t 网络采用多环结构，使得任意两个节点之间都具有 多条线路，属于比较典型的广域网”。 东北大 清华 东南大 华中理 西交大电科大华南理 图2 - l 仿真用的网络模型 模拟时假定连接建立请求按参数为九的泊松过程到达网络，即全网的总到达 率为 。光路建立后的服务时间( 保持时间) 服从均值为l u 的负指数分布，则全 网的总负载b = 入“。全网所有节点对之间的业务强度都相同，即支持的业务为 均匀业务。允许一对节点之间同时存在多条光路。一旦连接建立请求被拒绝，则 立即被丢弃，即无等待队列。为了确保网络运行进入平稳状态，对每种网络的每 个到达率，都生成了1 0 。个连接建立请求。 仿真给出了类c e r n e t 网，在每条链路的信道总数为1 6 时，两种算法的阻塞率 性能，在不同的波长数、光纤数下，全网总负载由小到大时集中策略和分散策略 的阻塞率性能( 被拒绝的请求数与总的请求数的比值) 的曲线。 浙江工业大学硕士学位论文 垒同总煎羹 图2 - 2 八波长双光纤时两种策略的性能比较 蠹一慧羹t 图2 3四波长四光纤时两种策略的性能比较 全同总负蓑 图2 _ 4 二波长八光纤时两种策略的性能比较 1 4 浙江工业大学硕士学位论文 图2 2 至图2 - 4 分别为类c e r n e t 网中八波长双光纤，四波长四光纤和二波长八 光纤集中策略和分散策略的性能比较。图中显示，采用资源尽可能均匀分配的分 散策略优于资源使用尽量集中的集中策略。并且分散策略较集中策略的性能改善 程度随着光纤数的增加而增加。例如，在阻塞率为0 0 0 1 时，八波长双光纤情况下， 分散策略与集中策略的吞吐量的比值为1 0 4 0 ；而四波长四光纤情况下比值为 1 0 5 4 ；双波长八光纤下比值为1 0 9 2 。 2 5 本章小结 链路权重选取问题是路由问题中需要首先考虑的，它的定义的好坏将直接影 响网络路由选取的优劣，从而也会影响到整体网络的性能，所以本章首先研究了 r w a 光网络路由选择问题中权重的传统定义方法，然后针对传统定义方法存在的某 些不足提出了两种改进型的权重定义方法，它们综合考虑了光网络多方面的因素， 是相对科学的定义方法。最后通过分析和仿真比较了我们提出的改进型定义法与 其对应的传统定义法的性能，证明了改进型定义法的优越性。 浙江工业大学硕士学位论文 第三章w d m 光网络的路由模型及l in g o 实现 许多路由算法理论上已经比较成熟，但基本还只局限在理论研究上，没有找 到好的工具对算法进行实现。本章一开始研究了经典的d i j k s t r a 最短路径路由算 法，再用规划方法求解了最短路由问题。然后针对光网络的特殊性对算法进行了 改进，给出了双向光纤的最短路由问题。在图论网络规划的基础上，以最小化网 络的拥塞下限为优化目标，给出了光网络路由的混合整数线性规划( m i l p ) 模型来 解决v w p 光网络拓扑设计问题。本章利用一个专用规划软件一l i n g o 对算法进行 编程实现，使得算法超越了理论层面，已经能在实际网络中应用。涉及的这几个 路由算法的效率高，算法简单，运算速度快，适合求解小规模光网络中的路由问 题。 l i n g o 是种专门用于求解数学规划问题的软件。由于l i n g o 执行速度快，易 于方便地输入、求解和分析数学规划问题，因此在教学、科研和工业界得到广泛 应用。l i n g o 的功能主要用于求解大规模线性、非线性和整数规划，它提供的内部 建模语言能够自然地描述各种规划问题，使大规模数学规划的求解不再困难。 l i n g o 中包含了一种建模语言和许多常用的数学