（电磁场与微波技术专业论文）wdm光网络路由和波长分配技术研究.pdf

j 匕京邮电大学硕士论文摘要 w d m 光网络路由和波长分配技术研究 摘要 随着信息化社会的发展，宽带视频、多媒体等业务的需求不断增 长，特别是i n t e m e t 网的爆炸式发展，使得扩大广域骨干通信网的容 量成为迫切的要求。现有多种技术可用于扩大基于光纤通信的骨干网 的容量。其中采用光路交换、波长选路的波分复用( w a v e l e n g t h d i v i s i o nm u l t i p l e x i n g ，w d m ) 光传送网的实现技术是相对简单的一 项技术，并且特有的波长空分重用能力使其具有良好的可扩展性，因 此波长选路的波分复用光传送网被视为是下一代高速广域骨干网最 具竞争力的候选者。 w d m 光传送网络是由网络节点和链接节点的单纤或多纤构成， 光网络的节点能交叉连接输入和输出的光信道，具有动态重构光网络 的特性。当客户层业务到达时，w d m 光网络需要给每条业务在接入 点间分配路由和选择波长，建立光传送通道传送业务。我们称为到达 的业务选择路由和分配波长的问题为路由和波长分配( r o u t i n ga n d w a v e l e n g t ha s s i g n m e n t ) 问题，简称r w a 问题。由于光网络承载的 业务需求正成爆炸式增长，而目前光网络的可用资源( 波长光纤等) 有限，因此，如何在有限资源网络中为业务选择合适的路由和分配优 化的波长将直接影响到网络的传输效率。路由和波长分配算法成为重 要的研究课题。仡今为止，关于w d m 光传送网中r w a 算法的研究 一直是国际上的一个热点。虽然在该领域内仍然没有得出一个最有说 服力的结论，但其在全光网中具有十分重要的地位，对于改善光网络 的性能、节省建网的投资、优化网络的配置等都具有举足轻重的作用。 作为w d m 光传送网中的核心技术之一，r w a 问题的研究对网络资 源的利用，网络管理和控制都有很大的影响。 笔者所在的课题组一直致力于w d m 网络中r w a 技术的研究。 笔者在攻读硕士学位期间，参加了以下项目： 1 国家自然科学基金重大项目“w d m 全光网基础研究”子项目 “光网络模拟软件”； 2 中兴通信公司技术中心横向合作项目“o x c 节点技术研究”； 3 横向合作项目“光网络生存性的研究”； 北京邮电大学硕士论文摘要 4 信息产业部电信规划院横向合作项目“w d m 网络规划和优化 软件”。 依托以上项目的资助，本论文以w d m 光网络中路由和波长分配 技术为研究对象，通过实验仿真和理论分析，重点研究了目前r w a 算法的几个热点，取得了以下成果： 1 对不同类型业务的r w a 算法进行了研究和比较分析，与课题 组的同事一起提出了一些新的r w a 算法，如用于解决路由问 题的单环优化算法、b s p 算法、m i n s u m 算法以及用于解决波 长分配问题的r c i 算法； 2 研究与波长变换相结合的r w a 算法，重点分析了影响波长变 换增益的因素以及波长变换器放置问题； 3 研究生存性限制下的r w a 问题，主要研究针对共享容量保护 的r w a 算法、恢复中的r w a 机制以及考虑业务等级约定 ( s e r v i c el e v e la g r e e m e n t ，s l a ) 时的r w a 问题： 4 研究自动交换光网络( a u t o m a t i c a l l y s w i t c h e d o p t i c a l n e t w o r k ，a s o n ) 中r w a 算法的新特点和具体实现机制： 5 结合项目中实现r w a 算法仿真平台r w a l 0 与n e t p l a n l 0 的 经验，对建立r w a 算法平台时需要考虑的因素、仿真的方法 及实验数据分析的方式进行了总结。 关键词：波分复用路由和波长分配波长变换生存性业务等级约定 自动交换光网络 j 匕京虐# 电大掌硕士论文摘要 t h et e c h n o l o g yo fr o u t i n g a n d ( a v e l e n g t ha s s i g n m e n t i nw d mn e t w o r k a b s t r a c t w l t ht h e d e v e l o p m e n to fi n f o r m a t i o ns o c i e t y a n dt h e e x p l o s i v e g r o w t ho fi n t e r n e t ，t h er e q u i r e m e n t so f n e t w o r k c a p a c i t yh a v ei n c r e a s e d d r a m a t i c a l l y , w h i c ha r ep r o m o t i n gt h ec o n s t r u c t i o no fb r o a d b a n dt r u n k n e t w o r k n o w a d a y sm a n yp a t h sc a r lb eu s e dt oe n l a r g et h ec a p a c i t yo f t r u n kn e t w o r kb a s e do n f i b e r s ，a m o n g w h i c h a l l o p t i c a l n e t w o r k s e m p l o y i n g t h ec o n c e p to fw d ma n dw a v e l e n g t hr o u t i n ga r ec o n s i d e r e d a st h et r a n s p o r tn e t w o r k sf o rt h ef u t u r e i ns u c hn e t w o r k s ，t w o a d j a c e n tn o d e s a r ec o n n e c t e d b yo n eo r m u l t i p l ef i b e r s e a c hn o d eh a sad y n a m i c a l l yc o n f i g u r a b l eo p t i c a ls w i t c h w h i c hs u p p o r t sf i b e r ss w i t c h i n ga n dw a v e l e n g t hs w i t c h i n g ，i e ，t h ed a t a o na s p e c i f i e di n p u tf i b e ra n dw a v e l e n g t hc a nb es w i t c h e d t oas p e c i f i e d o u t p u t f i b e ro nt h es a m ew a v e l e n g t h w h e nt r a f f i cf r o mc l i e n t l a y e r c o m e s ，t h ew d m n e t w o r km u s ts e l e c to n er o u t eo u ta n da s s i g no n e a v a i l a b l ew a v e l e n g t hi no r d e rt oe s t a b l i s ho n ea v a i l a b l el i g h t p a t h ，w h i c h i sc a l l e dr o u t i n ga n dw a v e l e n g t h ( r w a ) p r o b l e m t h er w a p r o b l e mi nw d m n e t w o r ki so n ee v e r l a s t i n gp r o b l e m b e c a u s et h e r ei s a l w a y st h eg a pb e t w e e nt h el i m i t e dr e s o u r c e ，s u c ha s w a v e l e n g t ha n df i b e r s ，a n dt h eb o o m i n g t r a f f i cr e q u i r e m e n t b yf a r , t h e r e s u l to ft h er e s e a r c hh a sp r o v e dt h a to u ra l g o r i t h mc a n b r i n gs i g n i f i c a n t e f f e c t sf o r i m p r o v i n g t h e p e r f o r m a n c e o fw d mn e t w o r k ，b o t hi n r e d u c i n g t h ei n v e s t m e n ta n di n o p t i m i z i n g t h e c o n f i g u r a t i o n o ft h i s n e t w o r k c o n s i d e r i n gt h en a t u r er e l a t i o n s h i pb e t w e e nn e t w o r kp l a n n i n g a n dn e t w o r ko p e r a t i o n ，i th a sa l s ob e e np r o v e dt h er w a p r o b l e m i sa l s o v e r yh e l p f u lf o ro p t i m i z i n go p e r a t i o n ，c o n t r o la n dm a n a g e m e n t ， t h ea u t h o ra n dh i st a s kg r o u pt a k eu pw i t ht h er e s e a r c ho ft h er w a 北京邮电大学硕士论文 摘要 t e c h n o l o g y i nw d mn e t w o r kf o r a l o n g t i m e t h ed i s s e r t a t i o n i s s u p p o r t e db y s u c h p r o j e c t s ： 1 t h en a t i o n a ls c i e n c ef o u n d a t i o n p r o j e c t t i t l e d 死pb a s i c r e s e a r c ho f t h ew d ma l lo p t i c a ln e t w o r k 2 一t h e p r o j e c t t i t l e do x cn o a e t e c h n o l o g ys p o n s o r e db y z h o n g x i n gt e l e c o m m u n i c a t i o ne q u i p m e n tt e c h n o l o g y c e n t e r 3 t h e p r o j e c tt i f f e dk e yt e c h n o l o g i e s o i lt h es u r v i v a b i l i t yo f m e s h o p t i c a l n e t w o r k s 4 t h ep r o j e c tt i t l e dt h es o f t w a r ef o rp l a n n i n ga n do p t i m i z i n g o p t i c a l n e t w o r kf i n a n c e d b y t e l e c o m m u n i c a t i o n p l a n n i n g r e s e a r c hi n s t i t u t eo f m i i s u p p o s e db yt h e s ep r o j e c t s ，t h i s d i s s e r t a t i o na n a l y s e st h er o u t i n g a n d w a v e l e n g t ha s s i g n m e n tp r o b l e m i nw d mn e t w o r k ，e s p e c i a l l y f o c u s i n gt h ea t t e n t i o no ns e v e r a lh o t s p o t s t h em a i n c o n t r i b u t i o n so f t h i s d i s s e r t a t i o na r ei n c l u d i n g ： 1 s t u d i e da n dc o m p a r e ds e v e r a ld i f f e r e n tr w aa l g o r i t h m sw i t h d i f f e r e n t t y p e s o ft r a 髓cm o d e s o m en o v e lr o u t i n g a n d w a v e l e n g t ha l g o r i t h m s ，s u c h a sb s p a l g o r i t h m ，m i n s u m a l g o r i t h m a n dr c i a l g o r i t h m a r e p r o p o s e d 2 s t u d i e dd i f f e r e n tr o u t i n ga l g o r i t h m s e f f e c tu n d e rt h ec o n d i t i o n o fw a v e l e n g t hc o n v e r s i o n ，a l s os t u d i e dt h ew a v e l e n g t hc o n v e r t e r p l a c e m e n tp r o b l e ma n da n a l y z e d t h ef a c t o r sw h i c he f f e c t i n g w a v e l e n g t hc o n v e r t i n gp l u s 3 s t u d i e dt h er w a a l g o r i t h m sc o n s i d e r i n g t h el i m i to f s u r v i v a b i l i t ya n ds e r v i c el e v e la g r e e m e n t 4 a n a l y z e d 出er ；：i 缇p r o b l e m i n a u t o m a t i c a l l ys w i t c h e do p f i c a l n e t w ( ) r k 5 b a s e do nt h er w as i m u l m i o ns o f t w a r e ( n e t p l a n 1 0a n d r w a l o ) ，d i f f e r e n tf a c t o r si ni m p l e m e n t i n gt h er w ap l a t f o r m ， s i m u l a t i o nw a y sa n d p r o c e s s i n g d a t aa r es u m m a r i z e d k e yw o r d s ：w 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 ，r o u t i n g a n d w a v e l e n g t ha s s i g n m e n t ，w a v e l e n g t hc o n v e r s i o n ，s u r v i v a b i l i t y , s e r v i c e l e v e l a g r e e m e n t ，a u t o m a t i c a l l y s w i t c h e do p t i c a ln e t w o r k 独创性声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：垒墨塑日期： 塑鳢：i ：! 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅：学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。 本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 垒：l 蛰 ，到堕蝗 日期：墅5 f ：i ：f f 日期：型。3 ：! 北京邮电大学硕士论文 第一章绪论 第一章绪论 1 。1w d m 光网络技术的发展 随着全球“信息高速公路”的发展，以及宽带视频、多媒体业务的日益兴起， 特别是i n t e r a c t 业务的快速增长，对广域骨干网的带宽提出了越来越高的要求。 由于光纤具有巨大的潜在带宽( 接近5 0 t b s ) ，同时还具有成本低、信号失真和 衰减低( 可小于o 2 d b k m ) 、功率要求低以及空间要求小等优点，因此，目前在 骨干网中大多使用光纤链路来传输数据。但是，由于传统的s d h s o n e t ( s y n c h r o n o u sd i g i t a lh i e r a r c h y s y n c h r o n o u so p t i c a ln e t w o r k ) 技术只能以特定的 传输速率( 如2 5 g b i t s ) 在光纤中的单个波长信道上传输数据，此时要增加传输 带宽只能单纯依靠提高单波长的传输速率的来实现。从理论上看，单路波长的传 输速率上限主要受限于集成电路硅材料和镓砷材料的电子迁移率；其次，还受限 于传输媒质的色散和极化模色散以及所开发系统的性能价格比是否合算。目前看 来，材料问题已不是主要限制，已有人在进行1 6 0 g b i t s 速率的试验；但是，后两 项限制使这一速率的实用化前景变得十分暗淡，目前认为4 0 g b i t s 为单路波长的 最高实用化速率。可见，采用电的时分复用( t i m ed i v i s i o nm u l t i p l e x i n g ，t 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 d m ) 方式。波 分复用技术是节省光纤链路，提升传输容量的现实最优技术。它具有传输容量大， 对高层协议和技术适应性强，以及易于扩展等优点，采用w d m 技术可以将每根 光纤的巨大带宽分成许多互不重叠的波长信道，每个信道都可以并行、异步和高 速地按当前电子处理数据的极限速率来传输数据，从而可以充分利用光纤的巨大 带宽，提供丰富而廉价的带宽资源。 尽管w d m 技术可以充分利用光纤的潜在带宽，从而能够极大地提高线路的 传输能力，但是，由于目前的传送网中，光技术仅仅局限在点到点的应用，在节 点上采用的是电时分复用技术，还需要进行光电转换，这大大限制了网络的速度 和灵活性。另外，目前电子交换的发展已逼近电子速率的极限，为了摆脱电层交 换瓶颈的制约，引入光交换技术己成为必然趋势。光交换技术分为【4 1 光路交换 ( o p t i c a lc i r c u i ts w i t c h i n g ) 、光突发交换( o p t i c a l b u r s ts w i t c h i n g ) 和光分组交换 ( o p t i c a l p a c k e ts w i t c h i n g ) 三种。由于受到成本和技术方面一些问题的制约，如 北京邮电大掌硕士论文 第一章绪论 缺少光随机访问存储介质以及对光分组头的同步比较困难等，直接在全光域中完 成分组级交换的实用化还需待以时日。 换。相对光分组交换和光突发交换而言 目前受到青睐的是光路交换和光突发交 基于光路交换的w d m 光传送网更容易 实现，而且其特有的波长重用( w a v e l e n g t hr e u s e ) 能力也使它具有良好的可扩展 性。因此，采用光分插复用器( o p t i c a la d d d r o pm u l t i p l e x i n g ，o a d m ) 和光交 叉连接设备( o p t i c a lc r o s s c o n n e c t ，o x c ) ，提供可调度光路的w d m 光传送网 ( o p t i c a lt r a n s p o r tn e t w o r k ，o t n ) 将逐渐在骨干网中占据主导地位，被认为是 以下一代i n t e m e t 的极具竞争力的候选者。 w d m 光传送网是基于光域的组网形式，是具有波长选路功能的w d m 网络。 w d m 光传送网利用波长选路和光交换技术，由光层网络的节点直接提供对高速 光数据流进行透明的交叉连接功能，而电层网络用于形成高速光数据流并对其中 复用的低速和中速比特流实现交叉连接。由于光、电系统互为补充，相辅相成， 从而避免了大量的不必要的针对转接业务的解复用、复用处理操作，简化了节点 交换结构的规模。w d m 光传送网络是由网络节点和链接节点的单纤或多纤构成， 光网络的节点能交叉连接输入和输出的光信道，具有动态重构光网络的特性。当 客户层业务到达时，w d m 光网络需要给每条业务在接入点间分配路由和选择波 长，建立光传送通道传送业务。我们称为到达的业务选择路由和分配波长的问题 为路由和波长分配( r o u t i n g a n dw a v e l e n g t h a s s i g n m e n t ) 问题，简称r w a 问题。 由于光网络承载的业务需求正成爆炸式增长，而目前光网络的可用资源( 波长 光纤等) 有限，因此，如何在有限资源网络中为业务选择合适的路由和分配优化 的波长将直接影响到网络的传输效率。路由和波长分配算法成为重要的研究课 题。仡今为止，关于w d m 光传送网中r w a 算法的研究一直是国际上的一个热 点。虽然在该领域内仍然没有得出一个最有说服力的结论，但其在全光网中具有 十分重要的地位，对于改善光网络的性能、节省建网的投资、优化网络的配置等 都具有举足轻重的作用。作为w d m 光传送网中的核心技术之一，r w a 问题的 研究对网络资源的利用，网络管理和控制都有很大的影响。 1 2r w a 的概念和定义 由于在w d m 网络中，可用波长数量限制了网络能够提供的最大端到端的连 接数量，而光纤链路上的波长信道间隔、光收发机的调谐能力等物理约束都限制 了可用信道的数量。此外，给每一个信道分配波长时，并没有考虑带宽需求量等 因素，所以带宽粒度问题也同样限制了波长通道的带宽利用率。也就是说，现有 北京邮电大掌硪士论文 第一章绪论 的光网络虽然已经有了巨大的进步，但由于各种物理的、技术的限制因素，使得 光网络还不能够提供所有我们所要求物理性能，因此就存在对现有可用资源的高 效利用和优化问题。为了实现我们所需要的连接率，所需要的波长数目与网络规 模和网络节点之间的函数关系，就成为一个重要的必须研究的问题，因为可得到 的光纤的带宽不是无限的，而且现有光技术也大大限制了可得到的波长的分割程 度。 由于光网络存在这些限制条件，为了优化光网络性能就必须使用路由与波长 分配( r 、 7 a ) 算法。在传统的电路交换网络中，所有交换电路都是平等的而且是 完全一样的，而在波长选路网络中却存在着“波长连续性”限制因素和“同纤必 须不同波长”( 所有共享同一根光纤的光路径必须分配不同的波长) 的信道分配 原则的约束等，因而二者有很大区别，也就导致了在波长选路网络中必须采用一 种科学的、合理的波长选路算法和波长分配算法来优化网络性能、减小波长的阻 塞和减少对节点设备的端口数要求，从而大大降低运营和设备成本。这时由波长 选路算法来决定具体采用哪一条路径，一旦发现了一条路径，就按照波长分配算 法给它分配一个波长。 如果光网络节点( 交换机或路由器) 具有波长变换功能，那么就不存在波长 连续性问题，这时的路由问题就等同于常规的电路交换网络，而仅仅受每一条链 路上的可用信道的限制。如果要求一条端到端连接上的所有波长都相同，那就是 说路由与波长分配( r 、张) 必须满足波长连续性条件。这种约束条件使得波长信 道的利用率降低和阻塞概率增大。例如，即使存在一条空闲路由，但由于不能使 沿着该路由的所有链路段上的波长相同，则该路由还是不可用路由。因此，如果 要使光网络在给定业务模型的条件下通过优化路由和分配波长获得最大的吞吐 量，那么r w a 问题就成为波长路由光嗣络中至关重要的技术问题了。 从整体来看，r w a 可定义为：在给定一套需要在网络上建立的光通道，和给 定最大可用波长数量限制的情况下，如何来决定具体的路由和分配合适的波长以 使可建立的光连接最多( 或使所需的波长数量最少或使连接的拥塞概率最低) 。 在研究r w a 问题的文献中，通常将网络支持的业务分为两类【5 】：( 1 ) 静态业务： 给定一组连接建立请求，需要为这些请求寻找路由并在其路由上分配波长，以使 某些性能指标达到最优( 如全网吞吐量最大，所需波长数或光纤数最少等等) ；( 2 ) 动态业务：光路请求随机到达和离开网络，相应性能指标通常是光路的阻塞率。 按照所支持的业务类型分，r w a 问题可分为静态r w a 和动态r w a 问题。 从个体来看，在建立一个光连接时，必须考虑路由和信道的分配问题。给定 一个网络的物理拓扑和一套需要在网络上建立的端到端光信道，而为每一个带宽 北京邮电大掌硕士论文 第一章绪论 需求决定路由和分配波长就是路由和波长分配问题。波长信道分配( 通常在波长 信道子层完成) 包括给一个连接分配一个可得的波长并且把发射机和接收机调谐 到给定的波长上。而路由分配过程( 通常在光通路子层中执行) 首先为分配的波 长信道指定一个光通道并通过设置网络节点中的光开关来建立这个通道。应该指 出的是在波长选路网络中的一个光通道与一个特定的波长有关，因此只有先分配 波长才能建立一条波长通道。 从总体上来看，r w a 问题中的选路和波长分配是一个不可分割的问题。但是， 仅仅其中的波长分配问题就是一个非确定多项式完全( n o n d e t e r m i n i s t i c p o l y n o m i a l c o m p l e t e ，n p c ) 问题，要在合理的运算时间内解决大型网络的r w a 问题常常是不可能的。常用的解决方法是将r w a 问题强行拆成两个独立的子问 题，选路子问题和波长分配子问题，分别加以解决。 1 3 本论文的主要工作 本人在攻读硕士学位期间，参加了以下项目： 国家自然科学基金重大项目“w d m 全光网基础研究”子项目“光网络 模拟软件” 中兴通信公司技术中心横向合作项目“o x c 节点技术研究” 横向合作项目“光网络生存性的研究” 信息产业部电信规划院横向合作项目“w d m 网络规划和优化软件” 依托以上项目的资助，本论文以w d m 光网络中路由和波长分配技术为研究 对象，对不同类型业务的r w a 算法进行了研究和比较分析。同时对于目前r w a 算法的几个研究热点，如与波长变换相结合的r w a 算法、考虑生存性、业务等 级约定( s e r v i c el e v e la g r e e m e n t ，s l a ) 限制的r w a 算法以及自动交换光网络 ( a u t o m a t i c a l l y s w i t c h e do p t i c a ln e t w o r k ，a s o n ) 中的r w a 算法，也都进行了 较为全面的探讨。结合不同应用领域的特点，笔者与课题组的同学一起提出了几 种性能良好的新的r w a 算法，并开发了r w a 仿真软件，该软件在自然基金项目 鉴定时受到很高的评价。此外结合项目中实现r w a 算法仿真平台( r w a l 0 与 n e 中l a n l o ) 的经验，对建立r w a 算法平台时需要考虑的因素、仿真的方法及实 验数据分析的方式也进行了讨论。 参考文献 北京邮电大学硕士论文 第一章绪论 1 2 】 3 顾畹仪李国瑞编著，光纤通信系统，北京邮电大学出版社，1 9 9 9 顾畹仪张杰编著，全光通信网，北京邮电大学出版社，1 9 9 9 t h o m a se s t e mk r i s h n ab a l a 著，徐荣龚倩译，多波长光网络，人民邮电 出版社，2 0 0 t 4 徐荣龚倩编著，高速宽带光互联网技术，人民邮电出版社，2 0 0 2 【5 】r a m a s w a m ir ，e ta 1 ，“r o u t i n g a n d w a v e l e n g t ha s s i g n m e n t i n a l l o p t i c a l n e t w o r k s ，”i e e e a c m t r a n s n e t w o r k i n g ，v 0 1 3 ，n o 5 ，19 9 5 ，p p 4 8 9 5 0 0 6 k gr a m a k r i s h n a na n dm a r o d r i g u e s ，“o p t i m a lr o u t i n gi ns h o r t e s t p a t h d a t a n e t w o r k s ，”b e l l l a b st e c h n i c a l j o u r n a l ，v 0 1 6 ，n o 1 ，j a n 一j u n ，2 0 0 1 ， p p 1 1 7 - 1 3 8 j 匕京邮电大学硕士论文第二章r w a 算法的分类和比较 第二章r w a 算法的分类和比较 2 。1 概述 在本章中，根据业务类型的不同，我们将r w a 算法分为静态r w a 算法和动 态r w a 算法，综述在这一领域的最新研究成果。对于静态r w a 算法，将着重介 绍笔者在“w d m 网络规划和优化软件”中应用和改进的算法( 如最大概率算法、 单环优化算法和着色图算法) ；对于动态r w a 算法，将着重介绍笔者在国家自然 科学基金重大项目“w d m 全光网基础研究”子项目“光网络模拟软件”中实现 的算法( 如d i j k s t r a 算法、f p l c 算法和f f 算法) 以及课题组提出的算法( 如b s p 算法、m i n s u m 算法和r c i 算法) 。 2 1 1 静态r w a 算法简介 静态业务流量是指所有节点对之间的连接请求是预先给定且不随时间变化 的，即源节点和目的节点的连接关系是给定不变的。当所有连接建立好后，连接 将保持不变。此时网络不会建立新的连接，也不会拆除已建好的连接。 如果预先知道了业务流的格式，即已预先知道所有连接请求的接入顺序( 该 顺序是固定的而不是随机的) ，则最有效的分配光纤资源( 通道、波长波带和信 道) 的途径就是采用静态r w a 算法，以支持这些静态业务需求。它可以进一步 分为两类p j ：支持电路交换业务的静态r w a 算法和支持分组交换业务的虚拓扑设 计。前者的业务需求矩阵给出了每对结点间需要支持的光路数，而后者的业务需 求矩阵中存放的则是结点对之间归一化的平均分组业务强度。 在解决静态r w a 问题时，所得到的是逻辑拓扑( l o g i c a lt o p o l o g y ) ，又常称 为虚拓扑( v i r t u a l t o p o l o g y ) 。它以网络物理拓扑的节点为节点，由光路实现的虚 链路连接而成。 o 支持电路交换业务的静态r w a 算法简介 对于支持电路交换的静态r w a 算法，由于同时实现业务需求的路由选择和 波长分配计算时间较长，不适合应用于大型的网络，因此在研究的过程中常常将 其分为路由和波长分配两个子问题。对于路由子问题，又可以分为路由搜索和路 由选择两个步骤，前者为业务需求计算可达路由，后者则按照一定的顺序为各业 北京邮电大学硕士论文第二章r w a 算法的分类和比较 务需求选择一条适合的路由：对于波长分配子问题，也可以分为搜索和选择两步， 前者在业务路由上搜索可用波长，后者则根据一定的规则在其中选择一个波长， 在其上建立一个光通道。本章将基于这一基本框架，对其中涉及到的各类算法进 行介绍和研究。 支持分组交换业务的静态r w a 算法简介 如果光传送网用于传送分组型业务，因为分组业务和电路业务有着本质的区 别，所以在光层网络的优化目标和优化策略方面存在明显不同。这时的主要研究 对象是在纯粹的光网络上还另外叠加有电交换层的重叠多层网络结构，对应的算 法设计的核心是解决最优化网络虚拓扑的问题。由于缺乏相应的仿真环境，因此 仅在此对虚拓扑设计的相关因素进行一个简略的介绍： 成本因素：因为对于分组交换业务，可以看作业务需求是来源于电层而 不是光层，此时业务需求不再是以单一波分信道的容量为单位，其容量 的差别很大且变化频繁。因此对于支持分组业务的光传送网，不可能在 所有的业务节点对之间都建立光的通路。如何在满足业务需求的情况下， 建立相对少的光通路，从而降低发射机、接收机等器件的成本，是必须 考虑的一个重要因素。 拥塞因素：由于分组交换业务具有突发性，对于平均分组业务强度较大 的节点对，更容易出现分组发生拥塞的情况，因此在虚拓扑设计时，应 该尽量用虚链路连接分组业务强度较大的节点对，从而提高网络的吞吐 量，改善业务非均匀分布时网络的性能。 时延因素：虽然无论是针对电路交换业务还是分组交换业务，静态r w a 算法最终得到的结果都是一个虚拓扑。但由于前者的业务需求都是以单 一波分信道的容量为单位，因此所有的业务需求对应于虚拓扑上的通路 均为单跳通路( 即在整个通路上只有一个光发射机和光接收机，光电变 换和电光变换均只进行一次，因此在电域上只有一跳) ；而对于后者，由 于业务容量变化很大，因此许多业务需求对应于虚拓扑上的通路为多跳 通路( 即一对节点间的分组可能需要经过一条或多条虚链路。中间节点 配置的a t m 交换机或口路由器负责将分组由一条虚链路转发到另一条 虚链路上，在电域上为多跳) 。而在电域上每增加一跳，就会增加分组的 传输时延，为避免分组的时延超过用户能忍受的极限的情况，在设计算 法时必须考虑到路由跳数的限制。为解决此问题，可以在目标函数中引 入路由代价，使之倾向于使用最短路由。该方法不仅能降低通路的平均 北京邮电大学硕士论文第二章r w a 算法的分类和比较 长度，还能降低分组的传输时延。 映射因素：这个因素主要是考虑如何实现虚拓扑对物理拓扑的映射的问 题。这个问题和前面谈到的电路交换业务的静态r w a 问题在本质上是一 致的，一般的优化目标是使所用的波长数或光纤数最少，同时考虑资源 使用的均衡性。 2 1 2 动态r w a 算法简介 动态业务流量是指节点对之间的连接请求不是预先给定的，而是随着时间交 化动态到来的，当连接建立好并保持一段时间后又会被拆除。即不断有连接请求 到来，也不断有已建立好的连接被拆除。目前通常假设连接请求的到达符合泊松 过程，连接的保持时间符合指数分布。这种动态业务通常在下列情形下可能出现： 当业务分布出现较大变化，或者链路、节点出现故障，需要对网络进行 重新配置时； 随着宽带业务( 如w d m 光网上的专用虚拟网，i s p 租用速率超过2 5 g b s 的线路) 的出现和增长，这种业务需求有可能随时间而改变。 对随机业务流量而言，因为它要求对资源的分配具有更高的灵活性和有效 性，因此按照动态路由与波长分配规则来执行应是首选方案。在动态业务下，逻 辑连接( l c ) 的顺序要求以某种随机的方式到达网络控制器，而且这些要求是否 能够被接纳依赖于网络的现行状态。网络状态由所有的有效连接和它们所占用的 光通道配置( 路由和波长) 组成。网络的状态在时间上是随机变化的，这是由于 新的连接不断被接纳，而目前有效的连接不断被释放的结果。在动态业务条件下 所要实现的路由和信道( 波长) 分配问题必须有一种算法，它能够实时地对每一 个连接请求进行响应，当然该连接必须是可行的。如果一个要求不能被接受( 可 能由于物理的限制或允许控制限制) ，这样就发生了阻塞。由于问题的实时性， 动态业务环境下的r w a 算法必须菲常简单。因此在本章中，我们采用了分解法 的思路，将路由子问题和波长分配子问题以相对简化的方式分别加以处理，具体 讨论适合动态业务环境的各种r 算法和w 算法。 2 2 静态r w a 算法 在w d m 光传送网中，解决r w a 问题就是为每一个光连接发现一个光通道。 这意味着不但要发现一个光纤通道( 路由) 而且还要寻找一个波长( 信道或波长 北京邮电大学硕士论文第二章r w a 算法的分类和比较 分配) 。对于静态业务，就是在假设已知网络的物理连接拓扑的条件下，对一组 确定的、需要建立的光通道选择路由并分配波长，其实质是通过使用各种各样的 成本函数来对资源进行的优化问题。众所周知，r w a 问题是一种n p c 的问题。 r w a 问题可分为两个子问题：路由问题和波长分配问题，每一个子问题又是一种 n p c 问题，路由和波长分配二者密切相关。在解决静态r w a 问题时，常见的有 两种方式： 1 ) 结合法：将路由选择和波长分配同时加以考虑，在解决路由选择问题的 同时波长分配问题也得到了解决。如各类文献中常提到的分层图法，就 是将r w a 问题构建成一个三维模型分层图，分层图上每一层对应一个 波长，也称为一个波长平面，此时相应的r w a 问题简化为在分层图中寻 找从源到目的节点的最小代价通路问题。结合法资源优化效果较好，但 在解决大型网络问题时耗费时间较长。 2 ) 分离法：将路由选择和波长分配分别处理，一般是先处理路由选择子问 题，再解决波长分配子问题，虽然这种分离方法所获得的路由结果一般 并不太理想，但它易于实现而且也能满足一般工程要求，因此本文将主 要解决分解法。下面讨论时采用分解法中比较常见的思路，将r w a 问题 分为两步来处理，第一步计算路由，第二步进行波长分配。而每一步又 分为两个过程：搜索和选择。具体分类如图2 1 所示： 北京邮电大学硕士论文第二章r 、a 算法的分类和比较 图2 - 1 路由与波长分配算法分类 下面两节我们将分别介绍静态r w a 问题中的路由和波长分配两个子问题。 2 2 1 路由子问题 从图一可知，路由问题可以分为搜索和选择两个部分，关于路由算法的搜索 功能，实际上就是为业务需求计算路由的过程，比较常见的思路【2 】有： 最短路径( s p ) ：最短路径算法在给定的网络图中为给定的源和目的节点 寻找最短路径。该路径的连接成本比其它任何路径都低。成本函数往往 就是通道上所有边的权重的总合。一般情况下，通道的权重是静态的而 且与链路上路由数量无关。因为最短路径算法所产生的路由与其它任何 路由都是无关的，因此，s p 不需要任何的搜索次序或选择规则，计算的 结果就是最后的唯一选择。 基于权重的最短路径( w s p ) ：权重最短路径算法是一种最短路径算法， 但是链路成本可能根据已经建立的路由数量而动态地进行调节。因此， 该算法需要按照一定的搜索次序来执行。例如：最大业务流量策略或按 随机次序进行搜索。 k 最短路径( k s p ) ：该算法为每一对源和目的节点都寻找不止一条的 光通道。k 条可替换通道增加了路由选择的灵活性。然而它将路由问题 转化为了多路由选择问题，通过在k 条通道中进行选择来获得所需的最 小成本( 总跳数或总链路成本最小) 的连接通道，从而不仅增加路由搜 索的计算量，也额外增加了路由选择的计算量。 而关于选择功能，又可以分为顺序选择和混合优化选择两种方法。顺序选择 ( 渴望算法) 算法分为选择次序和选择规则两个部分，首先第一步确定选择顺序， 即各业务需求的选择顺序，先为哪一条业务确定路由，常见的方式有： 随机顺序选择 固定顺序选择( 如最大业务流量优先等等) 然后是选择规则，即对于某业务需求的多条可用路由，按照何种规则为其确 定一条路由，常见的规则有： 随机选择：随机在可用路由中选择一条。 首次命中( f i r s t 。f i t ) 策略：在所有可用路由中选择第一个满足条件的。 按照使用概率选择：在所有可用路由中根据使用概率进行选择。 最小权重链路优先：选择包含最小数量的已建立路由的链路。 对于混合优化选择，可