（计算机应用技术专业论文）波长路由光网络拓扑结构研究.pdf

波长路由光网络拓扑结构研究 摘要 近年来随着因特网用户人数的增多，因特网通讯的体积迅速增长，这就要求越来越 多的网络带宽。为适应因特网通讯，骨干网的容量已由w d m ( 波分复用) 技术提高基于 w d m 技术的波长路由光网络已成为下一代光网络的一种大有前途的网络基础结构 波长路由网络中的节点用被称为光路( 1 i g h t p a t h ) 的专门虚拟电路连接通过配置光 路，波长路由网络的逻辑拓扑结构被构建其中光路是通过给路上的每条链分配一个专 门的波长而建立起来例如如果要定义从节点z 到节点y 的一条光路，节点z 必须以波 长a 舢广播光信号到光连接器且节点y 通过调整它的接收器到相同的波长k 管必须能够 接收到这个光信号因此，光路是建立和实现光通信的前提建立光通路的原则是：在 交换中心，当收到一个建立光通路的请求后，便查寻在目的节点所用的光信道中是否有 空闲通路，如果有就建立该连接，反之则丢弃该申请 波长路由网络可以分为单跳网和多跳网单跳网允许任意源目的对之间用一条单 个的光路从源点到目的点通讯在多跳网络中，利用一个由许多光路组成的复合光路完成 从源点到目的点的通讯而且在多跳网络中，信息可以通过不同的路径到达目的节点 如何使各节点发出的信息均能找到一条较短的路径到达目的节点，从而使整个网络的传 输时延最小，该问题的研究是目前波长路由网络研究的热点之一大量研究表明，网络 所具有的特性在很大程度上是由逻辑拓扑结构来决定的，不同的拓扑结构会导致网络性 能的差异，所以在研究网络的时候最值得关心的一个问题当然是网络拓扑了优化网络 拓扑结构，可以减少网络通讯延迟和网络拥塞现象的出现 逻辑拓扑结构通常由有向图g = ( ve ) ( y 是结点集，e 是边集) 来表示，g 的每个 结点表示物理拓扑结构的一个节点，每条边( t t t ，) 表示从节点u 到节点u 的一条全光 光路在多跳网络的逻辑拓扑结构的图表示中，从仳到v 通讯，我们能通过图论上的路 径u _ z 1 一z 2 一_ x k 一1 - u 来表示由光路l o ，工1 ，三知一1 组成的复合光路l 为了满 足低费用和高速通讯，我们要求图有小的结点度，简单的路由模式和小直径 本文研究了波长路由光网络的结构和性质，并得到了一些结果共分为五章 在本论文的第一章绪论中说明了论文研究的背景及问题的提出和论文的组织结构； 第二章介绍了波长路由光网络的组成结构，性质及设计的相关问题；第三章研究了多跳 波长路由光网络的一些典型的拓扑结构，并且分析和比较了它们各自的性能；第四章设 计了多跳波长路由光网络的灵活的，可扩展的拓扑结构并证明了其相关性质；第五章给 出总结并展望下一步要做的工作 关键词：波长路由光网络，w d m ，拓扑结构，直径，路由 a b s t r a c t r e c e n t l yt h ev o l u m eo ft h ei n t e r n e tt r a f f i ch a sb e e ni n c r e a s i n gr a p i d l ya st h eg r o w t h o ft h ep o p u l a t i o no fi n t c r n e tu s e r s ，w h i c hi sr e q u i r i n gm o r ea n dm o r en e t w o r kb a n d w i d t h t oa c c o m m o d a t et h ei n t e r n e tt r a f f i c ，t h ec a p a c i t yo fb a c k b o n en e t w o r k sh a sb e e ne n h a n c e d b yw 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 b a s e dw a v e l e n g t h r o u t e do p t i c a ln e t w o r k sh a v eb e e nw i d e l yc o n s i d e r e dap r o m i s i n gn e t w o r ki n f r a s t r u c t u r ef o rn e x t g e n e r a t i o n o p t i c a ln e t w o r k s t h en o d e si nw a v e l e n g t h - r o u t e do p t i c a ln c t w o r ka r cc o n n c c t c dw i t hd e d i c a t e dv i r t u a l c i r c u i t sc a l l e dh 曲t p a t h s b yc o n f i g u r i n gl i g h t p a t h s ，al o g i c a lt o p o l o g yi sc o n s t r u c t e dt ) v i ta w a v e l e n g t h - r o u t e dn c t w o r kw h e r el i g h t p a t hi ss e t u pb ya s s i g n i n gad e d i c a t e dw a v e l e n g t ht o i to ne a c hl i n ki ni t sp a t h f o re x a m p l e ，t od e f i n ea l i g h t p a t hf r o mn o d ez t on o d e y ，t h en o d e zm u s tb r o a d c a s tt ot h ep a s s i v eo p t i c a lc o u p l c ra taw a v e l e n g t ha z 分a n dt h en o d e ym u s tb c c a p a b l eo fr c c c i v i n gt h i so p t i c a ls i g n a lb yt u n i n gi t sr e c e i v e rt ot h es a m ew a v e l e n g t h 九! ，s o l i g h t p a t hi st h ep r e c o n d i t i o no fl i g h t w a v cc o m m u n i c a t i o ni no p t i c a ln e t w o r k s t h ep r i n c i p l c s o fs e t u p i n gt h el i g h t p a t h sa r e ：i ns w i t c h i n gc e n t e r ，a f t e rr e c e i v i n ga ne s t a b l i s h m e n tr e q u e s t ， t h e ns e a r c hw h c t h c rt h e r ei saf r e ec h a n n e li nt h el i g h tc h a n n e lw h i c ht h ee n d n o d e su s e i f t h e r ei so n c ，t h e ne s t a b l i s ht h i sc o n n e c t i o n ，o t h e r w i s ed i s c a r dt h i sa p p l i c a t i o n w a v e l e n g t h - r o u t e do p t i c a ln e t w o r km a yb cc a t e g o r i z e da ss i n g l e h o po rm u l t i h o pn e t w o r k s as i n g l e - h o pn c t w o r ka l l o w sc o m m u n i c a t i o nb c t w c c na n ys o u r c e d e s t i n a t i o np a i r u s i n gas i n g l el i g h t p a t hf r o mt h es o u r c et ot h ed e s t i n a t i o n i nam u l t i h o pn e t w o r k t o c o m m u n i c a t ef r o mas o u r c et oad e s t i n a t i o n ，i ti s n e c e s s a r yt ou s eac o m p o s i t el i g h t p a t h c o n s i s t i n go fan u m b c ro fl i g h t p a t h s a n di nam u l t i h o pn e t w o r k t h ei n f o r m a t i o nc a l lr e a c h t h ed e s t i n a t i o nt h r o u g ht h ed i f f e r e n tp a t h s h o wt oe n a b l et h ei n f o r m a t i o nw h i c he v e r y n o d es e n d so u tt of i n das h o r t e s tp a t ht or e a c ht h ed e s t i n a t i o n8 0t h a tt h et r a n s m i s s i o n d e l a yo ft h ee n t i r en c t w o r ki st h em i n i m u m t h i sq u t 粥t i o nh a sb e e no n eo fh o tt o p i c so f w a v e l e n g t h - r o u t e do p t i c a ln e t w o r kr e s e a r c h m a n yi n v e s t i g a t i o n si n d i c a t ct h a tt h ep c r f o r m a n c eo fan e t w o r ki sl a r g e l yd e c i d e db yi t st o p o l o g y s i n c ed i f f e r e n tt o p o l o g i e sm a yr e s u l t i nt h ed i f f e r e n c ei np e r f o r m a n c e ，t h em o s ti m p o r t a n tp r o b l e mi sc e r t a i n l yt h et o p o l o g ya s s t u d y i n gt h et h ep c x f o r m a n c eo fn e t w o r k o p t i m i z i n gt h et o p o l o g yo fn e t w o r kw i l lr e d u c e t h et r a n s m i s s i o nd e l a ya n dc o n g e s t i o no fn e t w o r k t h el o g i c a lt o p o l o g yi su s u a l l yr e p r e s e n t e db yad i r e c t e dg r a p hg = ( v e ) ( w h c r cv i st h es e to fn o d e sa n dei st h es e to fe d g e s ) w i t he a c hn o d eo fg r e p r e s e n t i n gan o d eo f t h ep h y s i c a lt o p o l o g ya n de a c he d g e ( d e n o t e db yu 一 ) r e p r e s e n t i n gad i r c c t a 1 1 o p t i c a l l i g h t p a t hf r o mn o d eut on o d eu i nt h eg r a p hr e p r c s c n t a t i o no ft h el o g i c a lt o p o l o g yo fa m u l t i h 。1 ) n c t w o r k ，f 1 ) rc 。m m i m i c a t i 。nf r o m 乱t 。钉，w c c a nr c p r c s c n tt h ec o m p 。s i t c1 1 9 h t p a t n 三c o n s i s t i l l go ft h cl i g h t p a t h sl o ，k ，l k 一1b y t h eg r a p h - t h c o r c t i cp a t _ z 1 一勋_ 一z k 一1 一秽t h cg r a p h i sd e s i r c dt oh a v es m a l ln o d a l d e g r c c ，s i m p l cr o u t i n gs c h c m ca n d s m a l ld i a m c t c rf o rl o wc o s ta n dh i g h - s p e e dc o m m u n i e a t i o n， i nt h ct h c s i s ，w cm a i n l ys t u d yt h es t r u c t u r e sa n d t h ep r o p e m c so fw 删k n g t h 叮? 毗叫 。d t i c a ln e t w o r k a n do b t a i ns o m ci n t c r 训n gr c s u l t s f i v ec h a p t e r s a r ci n c l u d c di nt h et h c s l s w ci l l u i n j n a t ct h c r c s c 盯c hb a c k g r o u n d ，p u tf o r w a r do ft h ep r o l b l c 衄a n dg w c t h e s t r u c - t u r e 。ft h ct h c s i si nc h a p t c r1 i nc h a p t c r2 ，w c i n t r o d u c ct h c s t r u c t u r e s , p r o p e r t i e s 。a n d t h cc o h c s p o n d i n gd c s i g i li s s u c sf o rw a v d c n g t h r o u t e d 。p t i c a l n c 佃毗nm 锄印t e r3 一 m a i n l ys t u d ys 。m ct y p i c a lt o p 。l o g i c s o fm u l t i h o pw a v c l c n 昏n r o u t c d 。p t 记a 1n ? 。】：譬a n 三 a n a l v z ca n dc 。m p 缸ct h c i rp c r f o r m a n c c s ，r c s p c c t i v c l y i nc h a p t e r4 ，w ed e s i 印f l e b l e a n d s c a l 孟l ct o p 。1 0 9 i c s 。fw a v e l c n g t h - r o u t c d 。p t i c a ln c t w o r k s ，a n dp r o v c 恤眦0 玎唧o n d i n g p r 咿 t t 记st h ef ) n o w i n gp r o b l c m sf o rf u t u r er e s e a r c ha r eg i v e ni nc h a p t e r 5 k e yw 。r d s ：w 删c n g t h r 。u t e do p t i c a ln c t w o r k s ，w d m ，t o p o l o g y , d i a m c c r ，r 。砒i n g l n 曲阜师范大学博士硕士学位论文原创性说明 ( 在口划“刀) ， 本人郑重声明：此处所提交的博士口硕士曰论文波长路由 光网络拓扑结构研究，是本人在导师指导下，在曲阜师范大学攻读 博士口硕士囱学位期间独立进行研究工作所取得的成果。论文中除 注明部分外不包含他人已经发表或撰写的研究成果。对本文的研究工 作做出重要贡献的个人和集体，均已在文中已明确的方式注明。本声 明的法律结果将完全由本人承担。 作者签名：蓝晓鼍日期：划1 ) 哆， 曲阜师范大学博士硕士学位论文使用授权书 ( 在口划“”) 波长路由光网络拓扑结构研究系本人在曲阜师范大学攻读博士口 硕士囱学位期间，在导师指导下完成的博士口硕士日学位论文。本 论文的研究成果归曲阜师范大学所有，本论文的研究内容不得以其他 单位的名义发表。本人完全了解曲阜师范大学关于保存、使用学位论 文的规定，同意学校保留并向有关部门送交论文的复印件和电子版 本，允许论文被查阅和借阅。本人授权曲阜师范大学，可以采用影印 或其他复制手段保存论文，可以公开发表论文的全部或部分内容。 作者签名：蓝屯砉 日期：到噼如g 导师签名：函 参1 飘 日期：为访t t c i 波长路由光网络拓扑结构研究 1 1 研究背景和问题的提出 第一章绪论 因特网用户数目的增长以及这些用户对一些应用和服务( 如w w w ，语音聊天， 视频流，p 2 p 文件共享和网格计算等) 要求更大的带宽，导致因特网通讯的体积迅速 增长【1 ，2 】为了满足带宽需求，大量的研究集中在新兴的技术w d m ( 波分复用) 【3 上w d m 是允许在单个光纤上复合和传送不同光波长信号的技术( 如图1 1 ) 它使得 数据传输速度和容量获得倍增，充分利用单模光纤的低损耗区的巨大带宽资源，采用合 波器，在发送端将不同波长的光载波进行合并，然后传入单模光纤，在接收部分再由分 波器将不同波长的光载波分开，由于不同波长的光载波是相互独立的，所以双向传输问 题，迎刃而解 一， 卜- bc d n e t w o r k 川好一 口 y r e e d i i a r f l 互 匕 厂 。一，。一。、 。i l n ， l a p i n p 图1 1w d m 传送系统 l o c “a “t s l o c a la c c 矗 图1 2 光交叉连接器o x c 经由光纤传送的光信号必须转换成电信号光信号的发射器把电信息包和数据流转 换成光的形式并且发送给光纤，而接收器把接收到的光信号转换成电的形式且使它们穿 过电路由器或交换机当发射器与接收器之间是多跳距离时，很难在每个中间结点都进 行信号的光和电形式间的转换为了省略中间结点的光一电电一光的转换和防止中间 波长路由光网络拓扑结构研究 结点成为瓶颈，在每个结点安装o x c ( 光交叉连接器) o x c 是能动态地配置连接给 定输入端口与任意输出端口的装置图1 2 给出了度为2 的o x c 的结构从输入光纤复 合的光信号被分成两个波长知和a 。所有知的输入信号进入一个光交换机，这个光交 换机改变输入信号的方向到输出光纤，如图1 3 所示通过配置o x c ，信号的路由被确 定波长信号的通过o x c 或光交换机的改道称为波长路由由光纤和o x c 组成的光网 络称为波长路由网络 4 】 o p t i c a ls w i t c h i n p u t 0 u t p 畦 _ n p u tj照0 u 中u t i n p u t 2汰o u t p 蜓 图1 3 光交换机 在w d m 波长路由光网络中，信息的传输是通过光路( 1 i g h t p a t h ) 完成的，其中光路 是两个节点之间的回路转换连接，它通过给路上的每条链分配一个专门的波长而建立起 来例如，如果要定义从节点x 到节点的一条光路，节点x 必须以波长九 广播光信 号到光连接器且节点y 通过调整它的接收器到相同的波长k ，却必须能够接收到这个光信 号因此，光路( 1 i g h t p a t h ) 是建立和实现光通信的前提建立光通路的原则是：在交换 中心，当收到一个建立光通路的请求后，便查寻在目的节点所使用的光信道中是否有空 闲通路，如果有就建立该连接，反之则丢弃该申请 o x co n 。d c f m c r - - l i g h t p a t h 图1 4 波长路由网络 图1 5 逻辑拓扑结构 2 波长路由光网络拓扑结构研究 在波长路由网络中，通过配置o x c 为每个波长配置虚拟的回路来传送数据，这些 虚拟的回路称为光路由于在光路通过的中间节点处没有信息包的电处理，一条光路的 两个节点直接连接因此，通过在波长路由网络中配置光路，光路的集合组成了基于物 理拓扑结构之上的逻辑拓扑结构图1 4 给出了一个由6 个0 x c 和7 条光纤组成的波长 路由网络每个o x c 与一个访问节点相连图中的箭头是波长分别为伽和a ，的光路 在这种情况下，访问节点层的逻辑拓扑结构如图1 5 所示物理拓扑结构中不相邻的节 点对( a ，d ) ，( 月，e ) 和( b ，c ) 通过光路a 1 直接连接 w d m 波长路由光网络可以分为单跳网和多跳网单跳网允许任意源目的对之间 用一条单个的光路从源点到目的点通讯在多跳网络中，利用一个由许多光路组成的复 合光路完成从源点到目的点的通讯而且在多跳网络中，信息可以通过不同的路径到达 目的节点为了完成从源点到目的点通讯，我们利用一个由许多光路组成的复合光路完 成从源点到目的点的通讯换句话说，为了完成从源点u 到目的点v 通讯，我们必须选 择节点x 1 ，z 2 ，x 矗一1 使得从节点u 到节点z l 有一条光路三o ，从节点x 1 到节点x 2 有一 条光路上。，从节点z 知一。到节点可有一条光路l 庇一。从节点u 到节点v 通讯的复 合光路三由光路o ，三。，厶一。组成为了利用这个复合光路从u 到u 发送某个数据， 这个数据将在节点x 。处用电媒体缓存直到从节点x 。到节点z ：的光路l 。是可用的当 l 。是可用的，数据将通过光路l 。传送到节点z ：这个过程将继续直到数据最后从节点 x 矗一。传送到目的点u 在这种情况下我们说这次通讯需要k 条光路，因此是k 跳在光 网络中，利用单个光路通讯相对快，在中间节点用电媒体缓冲的过程相对缓慢在中间 节点x 。，z 。，孤一，的每一步电缓冲在通讯中增加了一个额外的延迟，限制了从源点饥到 目的点v 的数据通讯的速度 在理想的情况下，在一个个节点的网络中，我们想要建立所有( 一1 ) 个节点 对之间的光路然而，这通常是不可能的，因为两个原因：首先，可用的波长数目限制了 有多少光路能被建立例如，在文献 5 】中，作者证明了随机选择的有1 2 8 个节点平均的 度为4 的网络能用3 2 个波长平均建立6 4 0 条全光光路第二，是由能被提供的硬件数量 和节点能处理的信息数量决定在一个有个节点的网络中，如果每个节点配有一1 个收发器并且如果在所有的光纤链路上有足够的波长，那么每个节点都能被一条光路连 接但是考虑到收发器的费用问题，我们只能对每个节点配几个收发器，结果把光纤中 w d m 通道的数目限制到一个很小的值d 因此，网络中只能有有限数目的光路 由于两个不同的光路如果共享相同的光纤的话就不能被指定相同的w d m 通道【6 】， 因此，如果许多光路必须共享相同的光纤，对每个光纤上的通道数目要求就更高因为 在多跳网络中源目的之间的路径长度受到直径( 网络中最远两个节点间的距离) 限制， 所以小直径的拓扑结构对每个光纤上的通道数目的需求小另外，在多跳环境下，通讯 延迟与中间路由器的数目成比例，数据包从源点到目的点必须通过这些路由器，因此， 在这样的环境下，一个小直径的拓扑结构很有用如何使各节点发出的信息均能找到一 条较短的路径到达目的节点，从而使整个网络的传输时延最小，该问题的研究是目前波 3 波长路由光网络拓扑结构研究 长路由光网络研究的热点之一大量研究表明，网络所具有的特性在很大程度上是由网 络拓扑来决定的，不同的拓扑结构会导致网络性能的差异，所以在研究网络的时候最值 得关心的一个问题当然是网络拓扑了优化网络拓扑结构，可以减少网络通讯延迟、减 少网络拥塞现象的出现 逻辑拓扑结构( 7 】通常由有向图g = ( v e ) ( y 是结点集，e 是边集) 来表示，g 的 每个结点表示物理拓扑结构的一个节点，每条边( 仳_ y ) 表示从节点u 到节点u 的一条 全光光路在多跳网络的逻辑拓扑结构的图表示中，从u 到u 通讯，我们能通过图论上的 路径u _ x 1 一x 2 一一x 矗一1 _ 秒来表示由光路工o ，l 1 l k l 组成的复合光路l 因 此，为了满足高吞吐量，低费用和高速通讯，我们要求逻辑拓扑结构g 满足以下要求： g 有小的直径 g 有低的平均跳距 每个结点的出度和入度要小 1 2 论文组织结构 第一章 第二章 第三章 第四章 性质 第五章 绪论中简要介绍了波长路由光网络的相关知识及文章的组织结构 介绍波长路由光网络的设计问题 研究了多跳波长路由光网络的拓扑结构并给出相关分析 设计了多跳波长路由光网络的灵活的，可扩展的拓扑结构并证明其相关的 提出需要进一步解决的问题 4 波长路由光网络拓扑结构研究 第二章波长路由光网络的设计问题 在波长路由网络中，因为每条光纤上的波长数目有限且光路上分配的波长是专门 的，所以在何处路由光路和哪个波长分配给这些光路是有效利用波长资源的重要问题 另外，对建立光路有一个限制，即为建立一条路上的光路，该路上的每一跳必须保留同 样的波长，这就是我们所知道的波长连续性限制 8 】尽管波长转换器能把一个波长转换 成另一个波长来解决这个限制，然而，由于利用波长转换器的费用相当高，网络工作者 在设计网络时尽量避免使用它所以，为了达到高的资源利用，如何设计波长路由网络 是一个相当重要的问题 波长路由网络由数据平面和控制平面组成【g ，1 0 ，1 1 】光路建立在包括光交换机和光 纤的数据平面上而那些光路由控制平面管理波长路由网络有两个标准的控制体系结 构，g m p l s ( 通用多协议标签交换) 和a s o n ( 自动交换光网络) 【1 2 ，1 3 1 这些体系结构被 设计来互连多个波长路由网络这些结构的标准化的发展增长波长路由网络的规模结 果，大规模波长路由网络形成由于这种扩大，网络通讯的体积增加因为网络组件数 目的增加，网络故障发生的概率增加此外，管理网络的信息的数量也增加因此，灵 活性，可靠性和可扩展性对大规模波长路由网络来说是很重要的问题 灵活性应对网络中不断变化的通讯，可靠性应对网络故障，可扩展性应对网络规模 本章我们将从灵活性，可靠性和可扩展性这三个方面来讨论波长路由网络的设计问题 2 1 灵活性 波长路由网络逻辑拓扑结构设计的方法在很多论文中研究过( 1 4 ，1 5 】，通常认为通信 要求提前知道然而，实际上，由于网络中开始新的服务等因素，如视频流和容量传输 服务，很难精确地预测通信需求的变化随着网络规模变大，通信需求的模式改变得更 迅速因此，当逻辑拓扑结构不符合通信模式时，要求适应通信需求的波长数目将迅速 增加因此，灵活的网络设计是比静态网络设计更重要的方法1 1 6 1 我们通过对当前的通讯请求重新应用设计方法将当前运行的拓扑结构重新配置成最 优的( 或次优的) 逻辑拓扑结构然而逻辑拓扑结构的重新配置过程中，由于旧光路的删 除可能发生信息包的丢失或延迟到达，这将导致通信的丢失和网络性能的衰减f 1 7 1 为减少删除光路产生的影响，在【1 8 】中，分支交换方法被提出这种方法通过减少 重新配置中要求的步数来尽力最小化通信损失s h i n y ai s h i d a 等人在【1 9 】中提出了波 长路由网状网的一种重新配置算法来提供灵活的骨干网其基本思想是利用预留给不 总是被利用的备用光路的波长资源该算法依次应用五个程序：转换( s w i t c h ) ，附加 ( a p p e n d ) ，备用( b a c k u p ) ，释放( r e l e a s e ) 和删除( d e l e t e ) ，来构造出一个 5 波长路由光网络拓扑结构研究 新的逻辑拓扑结构这些程序主要集中在利用空闲波长资源和备用光路资源其中定义 数据信息传输的当前运行的逻辑拓扑结构上的光路为运行的光路( w o r k i n gl i g h t p a t h ) ， 定义通过某个逻辑拓扑结构设计算法得到的新逻辑拓扑结构的光路为目标光路( t a r g e t l i g h t p a t h ) 下面我们将介绍这个算法 2 1 1 符号 首先我们解释算法中用到的符号： ：网络中的节点数目 w z 波长复用的度 。当前逻辑拓扑结构中运行的光路的集合 三2 ，目标逻辑拓扑结构中目标光路的集合 6 ( 2 ) s ( z ) d ( 1 ) 入( z ) 一条光路z 的备用光路 一条光路z 的源节点 一条光路2 的目的节点 分配给光路z 的波长，1 a ( 2 ) w 2 1 2 五个程序 1 sw l 1 1 c hp r o c e d u r el s t c p l 。为目标光路1 2 预留波长资源，其中s ( z - ) = s ( z 2 ) ，d ( 1 。) = d ( 1 2 ) ，即运行的光 路的源节点和目的节点与目标光路的源节点和目的节点相同如果资源预留成功，转到 s t e p 2 ，否则，退出程序 s t e p 2 ，设置目标光路? 2 ，转s t e p 3 s t e p 3 ：运行的光路z l 上的通信转到目标光路2 2 上，转s t e p 4 s t e p 4 ：运行的光路z l 上最后的信息包到达目的节点d ( z 1 ) ，转s t e p 5 s t e p 5 ：删除运行的光路z l 和它的备用光路6 ( z 1 ) 图2 1 1 详细描述了s w i t c h 程序的过程 2 a p p e n dp r o c e d u r e ： s t e p l ，为目标光路1 2 预留波长资源，如果资源预留成功，转到s t e p 2 ，否则，退出 程序 s t e p 2 ，设置目标光路1 2 3 b a c k u pp r o c e d u r el s t e p l ：为运行的初始光路z 1 的备用光路6 ( 2 1 ) 预留波长资源，转s t e p 2 s t e p 2 ；设置备用光路6 ( z 1 ) ，转s t c p 3 s t e p 3t 将运行的光路2 1 上的通信转到它的备用光路6 ( z 1 ) 上，转s t e p 4 6 波长路由光网络拓扑结构研究 s t c p 4 ；如果运行的光路上最后的信息包到达目的节点d ( 2 1 ) ，转s t c p 5 s t c p 5 ：删除运行的光路1 1 图2 1 2 详细描述了b a c k u p 程序的过程 ，卧曰鱼! 虮警岫埔 i - j $ t c p l i c ) s t e p 3 圳卧口她吩絮呻伯 一 w o r k l n l ：i l g b f p a t h i d js t e p 4 ( i ) s t e p 5 图2 1 1s w i t c h 程序 - js t c p l ( c js t e p 3 4 r e l e a s ep r o c e d u r e ： i h js t e p | f d js t e p 4 f c js t e p 5 t i r g c l “扣t p i n 臼 图2 1 2b a k t p 程序 u pi i | h t p a t h r e l e a s e 程序释放为运行的光路的备用光路预留的波长资源 7 t h 波长路由光网络拓扑结构研究 5 d e l e t ep r o c e d u r e ： d e l e t e 程序释放为运行的光路预留的波长资源 2 1 3 重新配置算法 在重新配置算法中，用一个变量p 来存储每次重复执行时，s w i t c h ，a p p e n d ， b a c k u p 程序调用的次数定义c 作为与目标光路配对的候选的运行光路的集合算 法的具体流程如下， s t c p l ：对每个目标光路z 2 l 2 ，如果有一个运行的光路z 1 l l 与z 2 有相同的路 线和波长，删除三l 和如中的元素，p 卜0 ，c 卜0 ，转s t e p 2 s t e p 2 ：对每个目标光路z 2 ，运行以下几步，以后，转s t e p 3 s t e p 2 1 ：增加运行的光路2 l l 。到c 中，要求满足条件：s ( z 1 ) = s ( 1 2 ) ，d ( z 1 ) = d ( z 2 ) 且z l 不保留z 2 要求的波长资源如果c 0 ，转s t e p 2 2 否则，转s t e p 2 3 s t e p 2 2 ：在c 的元素中选择一条运行的光路z ；，它的初始的和备用的光路的波长 资源大部分用来建立l 2 中的目标光路执行s w i t c h ( i ，z 2 ) 分别从l 。和l 2 中删除 如和z 2 p 卜p + l ，c 卜仍回到s t c p 2 s t e p 2 3 ：执行a p p e n d ( 2 ) 从2 中删除z 2 尸卜p + 1 ，转s t e p 3 s t e p 3 ；如果l 2 = 仍，转s t e p 6 否则，转s t e p 4 s t e p 4 ；对每个满足没有目标光路? 2 l 2 使得s ( 1 1 ) = s ( 1 2 ) ，d ( 1 1 ) = d ( 1 2 ) 的运行的光 路z l l 1 ，执行b a c k u p ( 1 ) 且如果成功，从工1 中删除z l ，p 卜p + 1 ，转s t e p 5 s t c p 5 ：如果p 0 ，p 卜0 且回到s t e p 2 否则，转s t c p 5 1 s t e p 5 1 ：如果有运行的光路其备用光路没有被释放，转s t e p 5 2 否则，转s t e p 5 3 s t e p 5 2z 选择一条运行的光路2 l ，它的备用光路6 ( 2 。) 的波长资源大多数用来建立 l 2 中的目标光路执行r e l e a s e ( 1 ) ，p 卜0 ，回到s t e p 2 s t e p 5 3 ：选择一条运行的光路z l ，它的初始光路的波长资源大多数用来建立l 2 中 的目标光路执行d e l e t e ( 1 1 ) 从l 1 中删除z 1 ，尸卜o ，回到s t c p 2 s t c p 6 ，删除l l 中剩下的所有运行的光路和那些备用光路，转s t c p 7 s t c p 7 ：把目标光路再分配的波长恢复到原始的波长，转s t c p 8 s t c p 8 ：保留目标光路的备用光路的波长资源 2 2 可靠性 波长路由网络由于其本身的性质能传送大量的数据通信只是单个光纤缺口就能使 得该光纤上的通信中断而引起巨大的经济损失因此，发生故障的光路连接被修复的快 慢是可靠的波长路由网络的一项重要的性能度量为确保波长路由网络的可靠性，引入 了很多修复模式光路修复模式分为两类：保护和修复【2 0 ，2 1 】 8 波长路由光网络拓扑结构研究 图2 2 1 几种保护方案对比 保护是指利用节点间预先分配的容量实施网络保护，即当一个运行的光路发生故障 时，利用备用设备的倒换，使工作信号通过保护通路维持正常传输下面我们以图2 2 1 ( a ) 为例，在最常见的单纤故障情况下介绍几种保护方案 1 1 + l 保护 1 + 1 保护为每一条光路连接都提供1 + 1 的备份保护，即在一条光路被建立的同 时，另一条专用于保护该路由上通信的且与该光路不相交的备用光路也同步被建立起来 了一旦运行的光路出现链路故障，端节点就利用备用光路和波长恢复通信 2 基于链路的恢复 如果网络的某条链路中断，受影响的连接就从链路中的一个节点出发绕过故障链 路，从别的链路到达另一个节点连接所通过的其它链路不变这种保护方案具有本地 性，因此参与保护倒换的节点少，恢复速度较快，但也由于它的本地性，它无法有效地利 用资源，如图2 2 1 ( b ) 所示，当链路1 3 发生故障以后，节点1 到5 的连接路径从1 3 5 变为l 一2 4 3 5 ，而节点1 到节点4 的连接路径从1 3 4 变为1 2 4 3 4 ， 节点4 通过了两次这种保护方法要求在链路的两个端节点就能识别故障路径 3 基于通道的恢复 当网络中的一条通道的某段链路发生故障，受影响的连接将全部转换到保护通道 上，保护通道除了不能含有故障链路以外，没有其它的限制，如图2 2 1 ( c ) 所示，此保护 方案由于在整个网络范围中选择最优保护通道，而且还可以释放工作通道上未出现故障 的链路资源，因而可以有效地利用资源，更不会出现链路保护的资源重复使用现象但 连接所通过的每条链路都有相应的保护通道，因此在最差的情况下，每个连接需存储与 其通过的链路数相同个数的保护通道的数据另外，其保护转换需要更多的节点参与， 9 波长路由光网络拓扑结构研究 而且需要故障定位，以便切换到相应的保护通道上 4 边不相交通道恢复 此种方案是通道保护方案的特例要求保护通道与工作通道除了源节点和目的节点 外，不能有相同的节点和链路，如图2 2 1 ( d ) 所示无论工作通道上何处出故障，连接都 转换到边不相交保护通道上，因而每个连接也只需要存储一条保护通道的数据，同时保 护转换也不需要故障定位，与通道保护相比能更快地恢复，但由于选择保护通道的边不 相交限制，以及无故障定位导致无法释放工作通道上的正常资源，使得此保护方案需要 更多的保护资源 保护模式为运行的光路的备用光路预留额外的波长资源【2 1 ，2 2 】当运行的光路发生 网络故障时，这些光路上的通信被转移到它们的备用光路上因此，只要对应的备用光 路不发生故障，保护模式就能确保从运行的光路上的1 0 0 的修复然而，由于波长数 目有限，保护模式降低了波长资源的利用，可以通过共享运行光路中的后备波长资源来 避免这个问题【2 3 】然而，这种共享对于被共享的波长一次只有一条光路被恢复而降低 了保护的效率 恢复模式在运行的光路发生故障后积极地寻找一条新的路径且保留波长恢复模式 提供更灵活的故障修复然而，恢复模式花费时间来发送信号且时间的增加与终端节点 间距离成比例此外，节点为故障恢复同时发送故障通知和链路状态信息，大量的控制 消息涌入控制平面，这导致传输延迟和消息丢失率的增加，影响与故障无关的光路 s h i n y ai s h i d a 等人在【2 4 】中提出了适合各种故障且减少恢复过程中控制消息数目的 恢复模式该恢复模式的主要思想是计算出一个被称为分水圈的圈来封闭网络中发生故 障的部分且转移圈上被破坏的光路，主要由以下四部分组成： 1 把网络拓扑结构划分成圈 【2 4 】中恢复方案首先把拓扑结构划分成圈为了制止网络故障影响的扩展，这些圈 的规模要求尽可能的小详细的划分过程见【2 4 】中算法 2 给圈分配控制器 对初始划分集合中的每个圈分配属于该圈的一个或更多控制器被分配给一个圈的 控制器在圈上建立经由普通控制网络到达o x c 的控制通道每个控制器包含关于控制 器和圈联合的信息在被分配给每个圈的控制器中挑选有最小控制器i d 的控制器作为 该圈的主要控制器，其它控制器为备用控制器 如果与节点数目相比链的数目太大，那么在初始划分中包括的圈的数目比控制器的 数目大在这种情况下，分配控制器前需要一些圈的合并 3 设定一个封闭故障部分的分水圈 当大规模故障发生在网络中时，共享故障节点的圈的主要控制器互相达成协议然后 把它们的圈合并成封闭故障区域的一个圈关于这个圈合并的算法，可以参见文献【2 4 】 每个检测到故障的控制器来设定一个封闭故障部分的分水圈：控制器发送合并消息 给共享故障部分的邻接圈的主要控制器在传送合并请求消息时，每个主要的控制器记 1 0 波长路由光网络拓扑结构研究 录它的圈的标志符，故障部分的边界链和请求中运行的部位被传送的请求最终回到它 们的产生器当产生器收到它们的合并请求消息时，就能断定要合并的圈和分水圈的大 体轮廓 4 沿着分水圈变更光路路线 分水圈的主要控制器通过分配波长把所有发生故障的部位转