（计算机软件与理论专业论文）光网络中的路由及波长分配问题研究.pdf

山东师范大学硕士学位论文 摘要 随着全球信息化的发展，我们的生活发生了巨大的改变，对信息的需求和依赖越 来越强。宽带视频、多媒体等业务的日益兴起，特别是因特网业务的快速增长，对广 域骨干网的带宽提出了越来越高的要求。光纤上的波分复用技术( w d m ) 以它的传输 容量火、技术适应性强、以及易于扩展等优点而备受青睐。因此，使用w d m 传输技 术和路由及波长分配( r w a ) 技术的光传送网将是下一代调整广域骨干网的最具竞争 力的候选者。 由于同一条光纤中复用的波长数目有限，在网络中无波长转换节点的情况下，源、 目的节点间的通信连接必须始终承载在同一波长通道上，即波长连续性限制。优化光 通道的路由及波长分配( r w a ) 是网络设计的核心问题之，其主要任务是寻找一条合 适的光路并为之合理地分配波长，使有限的网络资源充分发挥作用，尽量降低网络阻 塞率，以提供尽可能大的通信容量。 目前，大规模的全光网络还不易实现，研究中小规模的全光网络的r w a 问题及其 工程应用问题，具有重要的理论和实际意义。为此，本文对光网络r w a 技术进行了详 细研究，主要工作包括： 1 介绍了光网络的概念和w d m 技术，以及近年来国内外主要的光网络实验室及光 网络应用现状，展望下一代光网络的前景。 2 阐述了r w a 的概念及研究的意义，根据连接请求业务类型不同，分静态r w a 和动态r w a 分别进行研究，对已有的典型算法进行了分析比较。 3 由于受波长转换器技术及价格的限制，如何在光网络中配置较少的波长转换器而 使得光网络性能有较大的提高，是目前的一个研究热点。因此对光网络中的波长转换 器的放置算法做了研究分类，并着重研究了具有稀疏波长转换功能的光网络中的波长 分配问题，提出一种启发式波长分配算法。为了验证该算法，在o w n s 环境下进行了 模拟实验，并与另外两种波长分配算法进行比较，实验结果表明文中提出的算法性能 较优，较另外两种波长分配算法降低了网络阻塞率。 4 初步研究了基于光互联的并行算法的波长指派问题，对矩阵乘法的并行通信模式 进行了初步的研究，分析其通信模式，有助于进一步的深入研究。 关键词：光网络路由和波长分配波长转换 中图分类号：t n 9 1 3 山东临范大学硕士学位论文 a b s t r a c t w i t ht h e d e v e l o p m e n t o fi n f o r m a n t i o n s o c i e t y a n dt h e e x p l o s i v eg r o w t h o f i n t e r a c t ，g r e a tc h a n g e sh a st a k e np l a c ei no u rl i f e i n f o r m a t i o ni sm o r ea n dm o r ei m p o r t a n tt o u s w i t ht h ec o m i n go f t h e “i n t e r n e te r a ，ai o to f n e wi n f o r m a n t i o ns e r v i c ew i l lb ei nu s e a n dt h en e e d so fb a n d w i d t hw i l lb e c o m em o r ea n dm o r e t h u se m e r g e sa na c u t en e e df o r v e r yh i g b b a n d w i d t ht r a n s p o r tn e t w o r kf a c i l i t i e s ，w h o s ec a p a b i l i t i e sa r em u c hb e y o n dt h o s e t h a tc u r r e n th i g h s p e e dn e t w o r kc a np r o v i d e ，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 ) i s i l o 、, vc o m i n gi n t oo u rs i g h tt os a t i s 黟t h eu r g e n tn e e d s b e c a u s et h ew d m t e c h n o l o g yc a n l h l l yu t i l i z et h ee l _ 1 0 r n l o u sb a n d w i d t ho ft h eo p t i c a lf i b e r , t h ec a p a c i t yo ft h en e t w o r ki s g r e a t l yi m p r o v e d w d mt e c h n o l o g yi sn o wb e i n gt h em o s ta t t r a c t a b l et e c h n o l o g yi nw i d e b a c k b o n en e t w o r k ，a l l o p t i c a ln e t w o r kb a s e do nt h ec o n c e p to fw d ma n dw a v e l e n g t h r o u t i n gi sc o n s i d e r e da sac a n d i d a t ef o rt h en e x tg e n e r a t i o nt r a n s p o r tn e t w o r k b e c a u s et h en u m b e ro ft h ew a v e l e n g t h sw h i c ha r em u l t i p l e x e di nas i n g l ef i b e ri s 1 i m i t e d ，w i t h o u tw a v e l e n g t hc o n v e r s i o n ，a l lt h ec o m m u n i c a t i o no f t h er o u t er o u s tu s et h es a m e 、, a v e l e n g t h ，n a m e l yw a v e l e n g t hc o n t i n u i t yl i m i t e d o n eo ft h ek e yi s s u e si no p t i c a ln e t w o r k d e s i g ni st oo p t i m i z er 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 ) f o rl i g h t p a t h s rm 4 s o l v e s h o wt of i n do u ta na p p r o p r i a t el i g h t p a t ha n da s s i g naw a v e l e n g t hr e s o n a b l yi no r d e rt om a k e f u l lu s eo ft h el i m i t e dr e s o u r c ea n dp r o v i d ec o m m u n i c a t i o nc a p a b i l i t ya sl a r g ea sp o s s i b l e s ow em u s tp e r f o i t ne f f e c t i v er 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 ) t om a k et h eb e s t u s eo ft h es o u r c e si nt h en e t w o r k a sp r e s e n t ，l a r g e - s c a l ea l lo p t i c a ln e t w o r ki sn o te a s i l yr e a l i z e d ，s ot h es t u d yo fr w aa n d i t se n g i n e e r i n gp r o b l e m so ns m a l l - s c a l ea n dm i d d l e - s c a l eo p t i c a ln e t w o r kh a si m p o r t a n t a c a d e m i ca n dr e a l i s t i cs i g n i f i c a n c e t h em a j o rr e s e a r c hw o r k si nt h i sp a p e ra r e ： 1 t oi n t r o d u c et h eo p t i c a ln e t w o r k ，t h et e c h o n o l o g yo fw d ma n ds o m ei m p o r t a n t o p t i c a ll a b o r a t o r i e sa b r o a d 2 t oi n t r o d u c et h ec o n c e p to fr w aa n ds i g n i f i c a n c eo fr e s e a r c h ；t or e s e a r c hd i f f e r e n t t y p eo fr w a - - s t a t i ca n dd y n a m i c ，c l a s s i f ya n dc o m p a r es o m ep a r t i c u l a r l ya s s i g n m e n t s 3 i nw d mn e t w o r k ，w a v e l e n g t hc o n v e r s i o ni sak e yt e c h n o l o g y l i m i t e db yt h e t e c h n o l o g ya n dc o s to ft h ew a v e l e n g t hc o n v e r s i o n ，h o w t og e th i g h e re f f e c t i v eo ft h eo p t i c a l n e t w o r kb yp l a c i n gl e s sw a v e l e n g t hc o n v e r s i o ni si m p o r t a n t 。t h i sp a p e rp r o p o s e dah e u r i s t i c w a v e l e n g t ha s s i g n m e n t ( w a ) w h i c hm i n i m i z et h en u m b e ro fw a v e l e n g t hc o n v e r s i o nf o r w d mo p t i c a ln e t w o r kw i t hs p a r s e l i m i t e dw a v e l e n g t hc o n v e r s i o n t h ea n a l y t i c a la n d s i m u l a t i o nr e s u l t ss h o wt h a tw h e nt h et r a f f i ci sh e a v y ，t h ep r o p o s e dw ac a np r o v i d eam u c h l o w e rb l o c k i n gp r o b a b i l i t yt h a ns o m eo t h e rp r e v i o u s l yp r o p o s e dw aa l g o r i t h m s 4 t om a k es o m er e s e a r c ho nw ao fp a r a l l e la l g o r i t h m so no p t i c a ln e t w o r k ，a n a l y z et h e 山东师范大学硕士学位论文 c o m m u n i c a t i o np a t t e r n so f p a r a l l e la l g o r i t h m so f m a t r i xm u l t i p l i c a t i o n k e yw o r d s ：o p t i c a ln e t w o r k ，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 h c o n v e r s i o n 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得( 注：如没有其他需要特 别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的 同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名：豹绪 导师签字 学位论文版权使用授权书 砉协该 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权堂 圭巫可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：弛 签字目期：2 0 0 年r 月抛日 导师签字： 刘循 签字日期：2 0 0 年j 月扫日 山东师范大学硕士学位论文 1 1 光网络的历史 第一章绪论 光通信的历史最早可以追溯到数千年前，中国古代昀烽火台以及欧洲人使用的旗 语等传递信息的方式，都是运用光进行通信的例子。直到1 8 3 5 年，莫尔斯发明了电 报以后，这种光通信方式才渐渐退出历史舞台。 第二阶段是初始的光电传输阶段，发明了电话机的美国学者亚力山大格雷厄姆 贝尔在1 8 8 0 年进行了光电实验。在实验中，光在大气中传输，通过改变光的反射系 数柬调制光进行通信，但是没有进入实际应用领域。这主要是由于以下两点原因： 1 没有合适的光源，不具有无线电波那样的频率单一、方向性强的优点。 2 在大气中传输距离太短。 但科学家一直没有放弃对光通信的研究。到了2 0 世纪6 0 年代，激光器的发明解 决了光通信中的光源问题；1 9 7 0 年美国康宁公司制成了第一根低损耗的光纤，从而更 加激发了研究者及公众对全光信息高速公路的兴趣。1 9 7 6 年，第一条传输速率为 4 4 m b i t s 的光通信系统在美国亚特兰大诞生，并很快投入商用：1 9 8 8 年铺设了第一条 横跨大西洋的海底光缆( 使用电中继器) 。在8 0 年代后期，由于掺饵光纤放大器e d f a ( e r b i u m d o p e df i b e ra m pl i f i e r ) 的出现，几乎一夜之间光纤衰减造成的传输距离受 限的情况就消失了，人们对使用e d f a 进行长距离光传输的兴趣在飞速增长，光通信 在全世界蓬勃发展起来。 为了提高光纤的传输速率，已提出的包括光时分复用( o t d m ) 、光波分复用 ( w d m ) 、光频分复用( o f d m ) 以及光码分复用( o c d m ) 等技术，其中，w d m 技术最为 成熟。 1 2w d m 光网络概述 光网络是一种以光纤作为基本传输链路，充分利用光纤所具有的非常独特的特性 而组成的一种通信体系网络结构。 尽管从2 0 世纪7 0 年代的早期开始，光纤通信就成为最活跃的研究领域之一，而 且从8 0 年代以来，光纤传输设备也得到了大力开发和广泛应用，但是直到9 0 年代初， 研究最活跃的全光互连网络仍没有达到或超出实验室水平。因特网上业务的飞速增长 以及随之而来的对通信带宽的无穷尽渴求，给传统信息网络基础设施的通信容量造成 巨大压力，其导致的最直接的后果是出现了所谓的“光纤耗尽”现象和对带宽的“无 限渴求”的现象，迫切需要增大骨干通信网络的容量。 在这种背景下，波分复用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 d m 技术是光纤通信中的一种传输技术，它利用了一根光纤可以同时传输多个不同 波长的光载波的特点，把光纤可能应用的波长范围划分成若干个波段，每个波段用作 一个独立的通道传输一种预定波长的光信号。它为了高效地利用光纤，利用波分复用 器将许多并发的光波长信号同时加载到一根光纤中进行传输，并发的每个信号都占用 互不相同的一个波长，实现带宽的有效利用。如图】。通过使用这种技术，可以达 到不需要增加光缆就t ；l 以使传输容量得到几倍、几十倍甚至上百倍的提高。 图1 1 w d m 系统原理图 w d m 技术首先是散为一种点到点的传输技术而提出的，自9 0 年代中期投入商 用以来，发展极为迅速并且很快趋向成熟，已成为实现大容量长途传输的主流手段， 在骨干光纤网上得到了广泛的应用。现阶段w d m 主要用在点对点的长途传输上，联 网依然在s d h 电层上完成。采用一些新技术，以1 0 g b i t s 为基础的w d m 系统的全 光传输距离可以提高到数千公里之远。w d m 技术也在从长途传输领域向城域应用领 域推进。在城域网中，由于传输距离短，容量要求不是很大，因此可以采用较为低廉 的器件来降低密集波分复用( d w d m ) 设备成本，或采用稀疏波分复用( c w d m ) 技术。在光纤资源较为丰富的情况下，短期内w d m 技术还不会大范围进入城域应用， 但对于光缆资源缺乏或铺设光纤难度较大的地方，采用w d m 技术进行城域传输网的 规划和建设是非常有意义的，尤其是可以采用高性价比的c w d m 系统。 w d m 光网络必须遵守不同信道分配限制的原则( d i s t i n c tc h a n n e la s s i g n m e n t ) ， 即所有共享同一根光纤的连接必须被分配不同的波长。 w d m 光网络主要具有以下优点： 1 充分利用光纤的巨大带宽资源，极大地提高了光纤的传输容量，可以缓解光纤 带宽耗尽的问题。 2 w d m 系统多用于大容量长距离传输，以便多信道复用光放大器，简化系统结 构和设计，节省网元设备，减少投资和维护费用。 3 w d m 技术对数据格式是透明的，即与信号速率及电调制方式无关。w d m 系 统完成的是透明传输，对于“业务”层信号来说，w d m 的每个波长就象“虚拟”的 光纤一样。 4 只需要增加复用光通路数量与设备，就可以提高系统的传输容量，可以实现平 嚣 一器一 鬈 警萼 山东师范大学硕士学位论文 滑升级扩容。w d m 也是引入宽带新业务( 例如c a t v 、h d t v 和b i s d n 等) 的方 便手段，只需增加一个附加波长即可引入想要的新业务或新容量。 5 波长复用使得保护方法也更加灵活，网络生存性好。 w d m 光传送网中的重要网元主要包括光交叉连接设备o x c ( o p t i c a lc r o s s c o n n e c t ) ，光分插复用设备o a d m ( o p t i c a l a d d d r o pm u l t i p l e x e r ) ： 1 光交叉连接设备o x c o x c 是w d m 光传送网中的核心网元，它在网络节点处，对光波长进行交义互连， 从而有效地利用波长资源，实现波长复用。当光纤中断或业务失效时，o x c 能够自 动完成故障隔离、重新选择路由和网络、重新配置等操作，使业务不中断。即它具有 高速光信号的路由选择、网络恢复等功能，同时，它也具有上下光路的能力。 2 光分插复用设备o a d m o a d m 具有选择性，可以从传输设备中选择下路信号或上路信号，或仅仅通过某 个波长信号，但不影响其他波长信道的传输。o a d m 在光域内实现了同步数字序列 s d h ( 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 ) 中的分插复用器在时域内完成的功能，且具有 光域透明性，可以处理任何格式和速率的信号。o a d m 的应用大大提高了全光网设 计的灵活性，可用构建多种网络形式。 w d m 传送网可分为三层结构：电路层、通道层和传输媒质层。其中光通道o p ( o p t i c a lp a t h ) 技术是关键技术。由于目前的光存储还不成熟，无法采用电网络中的 存储转发技术，对于光网络的业务必须事先从源节点到目的节点预留资源，即在源、 目的节点之间建立一条光连接，也可称为一条光通道，建立光通道就必须涉及到路由 的选择和波长资源的分配。因此，路由选择和波长分配是光网络的一个核心问题，是 光网络高效、可靠运行的保证。 w d m 光网络目前的研究热点： 1 节点交换技术的革新。传输系统容量的快速增长带来的是对交换系统发展的压 力，光交换技术的引入并取代目前的电子交换设备，可以更好地适应未来的信息交换 需求。目前，光信号在通过交换单元时，一般需要经过的光电、电光转换的瓶颈，因 此对光交换技术的研究和开发显得非常迫切。 2 w d m 光传送网的路由选择和波长分配问题( r 、a ) 。这也是本文要重点讨论的 问题。 3 波长通道、虚波长通道与部分虚波长通道的问题。光网络中引入波长转换器， 以克服波长连续性的限制，建立虚波长通道v w p ( v i r t u a lw a v e l e n g t hp a t h ) ，从而降 低网络的阻塞率。但由于受波长转换器技术和价格的限制，折中提出了部分虚波长通 道p v w p ( p a r t i a lv i r t u a lw a v e l e n g t hp a t h ) 。如何实旋p v w p 方案，使得既能有效提高 网络性能又能节约成本，也是一个研究热点。 4 网络自愈生存技术的研究。探索如何能在尽可能短的时间内为被中断的业务寻 找新的传输路由和自愈方案，包括恢复技术、控制管理技术等。 山东师范大学硕士学位论文 5 w d m 光传送网的q o s 问题。由于各种网元的局限，对同一源、目的节点经过 不同网元可能具有不同等级的传输质量；上层不同用户对光路的服务质量的需求也不 尽相同。这两个原因使得w d m 光传送网的q o s 问题受到关注。 11 3国际上的主要光网络实验平台 美困的光网络试验项目起初受助于d a r p a ( d e f e n s ea d v a n c e dr e s e a r c hp r o j e c t s a g e n c y ) 。 第一阶段主要着眼于验证光网络的技术可行性。1 9 9 2 年，由d a r p a 给予资金支 持，成立了光网络技术协会o n t c ( o p t i c a ln e t w o r k st e c h n o l o g yc o n s o r t i u m ) ，其主 要成员为大学、实验室和电信设备厂。在1 9 9 5 年的国际光纤通信会议上，该协会宣 布他们成功地验证了一个4 波长的w d m 光网络，以及他们的研究成果。1 9 9 3 年， 也是在d a r p a 的资助下，全光网络联盟a o n ( a l lo p t i c a ln e t w o r k ) 成立。该联盟 包括a 1 t 、贝尔实验室、d e c 和m h 。其目标是开发研究高速w d m 网络的结构 组成和关键技术。 第二阶段主要着眼子器件技术、网络结构、网络管理与控制等领域，始于上世纪 九十年代中期。新兴的研究集团有1 9 9 5 年成立的多波长光网络m o n e j 、 ( m u l t i w a v e l e n g t ho p t i c a l ：n e t w o r k ) 和国家透明光网络联盟n t o n c ( n a t i o n a l t r a n s p a r e n to p t i c a ln e t w o r kc o n s o r t i u m ) 等。 m o n e t 项目的试验目标是把网络结构、先进的技术、网络管理以及网络成本综 合在一起，以实现一种高性能的、经济有效的、可靠的多波长光网络，并且把网络的 规模最终扩展为覆盖全国的网络。m o n e t 的观点认为未来的通信网络应该是分层结 构。底层是基于w d m 的光层，它完全受控于网络管理与控制系统，可以进行光通道 的动态重构，用于支持电层的业务传送；电子层包括a t m 、s o n e t s d h 等传统格式 或未来可能格式的电传送信号，最上层是应用层。 欧洲的光网络试验项目主要集中在r a c e ( r e s e a r c ha n dd e v e l o p m e n t i n a d v a n c e d c o m m u n i c a t i o n st e c h n o l o g i e si n e u r o p e ) 和a c t s ( a d v a n c e dc o m m u n i c a t i o n s t e c h n o l o g i e sa n ds e r v i c e s ) 研究计划。r a c e 着眼于建设光网络的基础技术开发，通 过对关键器件的研制和测试证实它们在通信系统中的应用。r a c e 的多波长传输网 m w t n 项目是世界上第一个成功验证波长路由原理的光网络研究项目。a c t s 着眼于 光网络的应用技术领域，主要有泛欧光网络o p e n ( o p t i c a lp a n e u r o p en e t w o r k ) 、泛 欧光子传输网p h o f o n ( p a n - e u r o p ep h o t o n i ct r a n s p a r e n to v e r l a yn e t w o r k ) 。o p e n 实验平台设计之初，计划在现场环境下开发和演示波长交叉连接的网状结构，建立多 波长的试验平台，在网络中演示波长的保护恢复功能；并试图在关键技术一一由波长 互换型o x c 节点实现的虚波长通道v 、p ( v i t u a lw a v e l e n g t hp a t h ) 路由方案、全光 波长转换技术以及光时分复用o t d m 和w d m 技术结合的传输终端方面取得进展。 山东师范大学硕士学位论文 日本有n t t 的企业光纤骨干c o b n e t ，n e c 和富士通等公司和实验室也在进行 着光网络的研究开发项目；法国、德国、意大利和英国同时也在做全光网络方面的研 究。 我国自1 9 9 6 年开始设立国家级项目研究波分复用光传送网络。1 9 9 8 年5 月，国 家自然科学基金委员会发布了“重大w d m 全光网基础研究”。1 9 9 9 年6 月，8 6 3 计 划发布了信息技术领域跨主题重大研究项目“中国高速信息示范网研究开发项目 ( c a i n o e n t ) ”。2 0 0 3 年5 月，我国由苏、浙、沪共建长江三角洲科技创新体系的 一个具体项目一长三角信息高速公路的示范建设启动。长三角信息高速公路采用全 光网络，带宽容量大，力求大容量信息在传输时的实时和畅通。 1 4 光网络的演进趋势 1 向大容量传输演进 追求更大容量、更民距离，一直是光通信发展的基本方向，近年数据、视频等业 务的快速增长更为传输网向更高速率、更长距离演进增添了新的动力。从现有技术上 看，由于4 0 g b i f f s 系统的实现成本较高，目前大规模投入商用还有较大障碍。现阶段 还是重点依赖w d m 技术来满足传输网更大容量的需求。 2 向网络智能化演进 网络智能化是光网络发展的必然趋势。传统的光网络业务配置一般都是依赖人工 的方式进行，耗时费力，且易出错。一种新型的具有智能性的光网络模型一一自动交 换光网络( a s o n ) 应运而生。它不同于传统光网络，a s o n 的组成增加了一个新的 层面一一控制平面，并相应地在控制平面中引入了路由、信令和链路管理等机制，以 实现连接自动管理。在光网络中，引入a s o n 有很多好处，主要体现在可实现业务快 速提供和扩展、网络资源的动态优化、业务光层的快速恢复和提供新型的业务类型， 如按需分配带宽、波长出租业务和光虚拟专网( o v p n ) 等。 国际上目前有三个组织，即i t u t ，i e t f 和o i f 进行相关的a s o n 标准化工作， 三个组织侧重点不同，都取得了相当的进展。 3 向传送距离超长化演进 随着光网络规模的逐渐扩展，如何实现低成本的超长距离传输( 大于2 0 0 0 公里) 也是下一代光网络需要着重考虑的问题之一，而且这也是也a s o n 网络的动态选路问 题和成本问题有关。随着各种超长传送技术的不断成熟和完善，超长传送将是下一代 光网络的主要特点之一。 1 5r w a 的概念及意义 w d m 传输系统通过o a d m 、o x c 节点设备联网组成可重构的光网络，网络是以 波长通道为基本单位面向连接的。由手技术限制，一根光纤中不可能同时容纳太多的 山东师范大学硕士学位论文 波长信道( 目前投入商用的为几十条，实验室可达到上千条波长) 。在大规模网络中， 同时可能会有大量的通信业务请求，为满足这些请求，如何进行路由选择并将有限的 波长分配给这些请求是一个重要问题，这就是路由及波长分配r w a ( 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 ) n 题。 r w a 是在光网络上为光路连接请求寻找从源节点到目的节点的路由并给这个路 由分配空闲的波长。这个问题解决的好坏，将直接影响网络性能。路由及波长分配问 题是w d m 光网络的核心问题之一，是光网络高效可靠运行的保证。 通常光路请求业务被分为两类：其一是静态业务请求，即给定一组呼叫请求，需 要为这些呼叫寻找路由并在萁路由上分配波长，以使菜些性能指标达到最优，这种分 配可以是离线的，不需要实时处理。其二是动态业务请求，即呼叫随机到达和离开网 络，要为每一个请求做实时路由与波长分配计算，性能指标通常是降低呼叫阻塞率。 r w a 是一个完全不确定多项式( n p c ) 问题，也就是说还没有找到任意复杂度 r w a 问题的时闻算法。由于计算资源有限，只能对规模有限的网络优化做也r w a 问 题的解答。根据不同的分类标准，r w a 算法可分为不同的类型：按照所支持的业务 类型划分。r w a 可分为静态r w a 和动态r w a 。根据解决问题的不同方式，r w a 可 分为分解算法和并行算法。分解算法，是将r w a 问题分解成路由选择和波长分配两 个子问题来解决，这两个子问题仍然是n p c 问题，但分解算法可以降低整卜问题的 复杂度。分解算法首先为光路连接请求计算恰当的路由，然后在该路由上分配波长： 并行算法是同时解决路由和波长分配问题，一般利用光网络中波长复用的特性采用辅 助分层图法。在考虑到技术条件和网络建设成本的条件下，设计出一个好的r w a 算 法，对减少网络的阻塞率、提高资源利用率及网络抗毁能力是有重要意义的。 1 6 本文的组织结构 本文共分五章，各章安排如下： 第一章绪言 第二章静态路由与波长分配算法 第三章动态路由与波长分配算法 第四章具有稀疏波长转换功能的光网络中的r w a 第五章基于光互联的并行算法的波长指派同题 第六章结束语 山东师范大学硕士学位论文 第二章静态路由与波长分配算法 2 i 静态r w a 概述 静态连接请求，是指整个网络节点问所有连接请求事先知道，对各个连接的路由 和波长分配可以是非实时的( o f f - l i n e ) 。此时r w a 需要解决的是从全局优化的角度， 为一组预先确定的需要建立的光连接请求选择路由并分配波长，从而使整个资源优化 效果达到最佳。 优化目标：在满足所有连接请求的前提下，使用的波长数目最少，或者在波长数 目给定的情况下，满足尽可能多的连接请求。 2 2 静态r w a 最优化问题 静态r w a 问题可以归结为一种规划问题，通常可以用整数线性规划i l p ( i n t e g e r l i n e a rp r o g r a m m i n g ) 方法进行描述，针对该问题的数学描述已经被充分讨论。在静 态r w a 问题中，规划的优化目标可以归结为两类：波长优化和业务优化。波长优化 是指在给定的网络物理拓扑结构和业务连接请求的情况下，将建立这些业务连接所需 光纤中的波长数量最少作为优化目标。而业务优化则是对于给定的网络物理拓扑结构 和链路的光纤数目、波长数目，尽可能多地满足业务需求。这两类优化其实是属于同 一类问题，分别从两个方面进行考虑的。以波长优化为例给出静态r w a 问题的规划。 在这里，假设网络中的链路为单纤链路。网络物理拓扑用有向图g 仍目表示，其 中v 为网络的端点集合，v - - v j ，端点个数为n ，e 为边集，庐 p 。 ，边是有向的， 其中e 。表示从节点v 。到的边，边的个数为m 。 令v 。d w 代表源目的节点对s , d 之间，波长为w 的光通道，由于在单纤网络中，每 个链路波长只能分配一次，因此0 4v s d w5 1 。 v d 代表源目的节点对s , d 之间需建立的光通道总数。 芦代表链路上，源目的节点对s , d 之间，波长为w 的光通道数目，由于在单 纤网络中，每个链路波长只能分配一次，因此o 芦5 l 。 = “警车矿代表网络中各链路上通过的最大光通道数目。 则静态r w a 问题可规划如下： 优化目标：r a i n 函 需满足的限制条件： 7 山东师范大学硕士学位论文 1 容量限制条件：对于单纤阕络，每个链路波长只能分配一次。刀“1 jd 2 流守t 瞰条件：对网络中任意节点，流出该节点的业务量与流入该节点的业务量 的差值等于该节点引入的业务承。 矿。 pf i ( r ) rv 。“ 如果v 习 石“： 一v m如果旷d 、， 、0 其它 其 1 ：f ( v ，) - l ：e q c e 2 ( v ) 2 u ：p ，f 2e ) 3 业务限制条件：每个什点对s , d 之n u 的、肛务数给定v 。= 、l ，。e 应川上述公式，叮以使它们成为：白效的优化工具。其基本思想为首先选择一个可 行解，计箅其相应的目标甬数值根抛定的判决条件，判断它是否为最优解，若不 是，转 受刘另一个可彳，解，并使目标函数的值逐渐增大。当日标函数达到最大值时， 最优解被找到。但i 是，如果没有任何限制以减小其复杂性，即便对小规模的r 棚络，变 量的数量乜会交得 ：常巨大。静态r w a 线- 附：规划万法的一个难点在i f 二解决方法小是 唯一的，解决方法的不唯一t l ：千】时会严重破坏优化算法。 2 3 几种典型的静态r w a 算法 当删络规模较大时，无法在合理的时间内得到最优解，所以目前研究集中于采 用各种启发式算法，来得到问题的次最优解。 2 3 ，1 辅助分层图算法 辅助分层图算法是利用光刚络的多波跃特性建立起波长分层图模型，借助辅助分 层图的方法同时解决路由与波长分配问题。 首先将网络的物理拓扑转换为分层图，即把全光网络物理拓扑复制w 份( w 为 光网络中可复用的波长数目) ，分层图的每一层对应于一个波长，其拓扑与f 6 4 络物理 拓扑- 样，这样物理拓扑中的个节点以映射成分层图中的w 个节点。如图2 1 表示网络的物理拓扑，图2 2 表示由物理拓扑建立的辅助分层图。r w a 问题就可以转 化为在分层图中寻找路由的问题。这样，当对源、目的节点寻找到路由后，根掘它 所在的分层图，对应的波长也能同时得到。 山东师范大学硕士学位论文 j | 2i 网! ； ；打i 扑h 图2 , 2 辅l 约分从罔 存辅助分层图算法中，静态r w a 川题转化为在辅助分层图中从源至0 目的节点对 川寻找最小代价路山问题。 实验表明，在网络 j i l 模较小的情况卜，使用辅助分层剀够法解决r w am 题，效 果较女，。对】：大型网络、光纤中波长复用数目较多的情况卜，由t ：节点数目过多，辅 助分层矧算法复杂度太高，不适合使用这种算涮、。 2 3 2 图着色法 图着色浚：足将r w a 问题分成路由和波长分配两个子题，之后一统一进t i - 谢v 优化，从而得到最优解。该算法将路由和波长的分配问题简化为埘通道十二涉图“，中 项点的着色l d 题。 对 个给定的物理拓扑和预发的连接集含 c ， ，苗先为连接请求确定路，在此 越础上，引入通道干涉图“h ，图中每个顶点ir 成连接请求的一条可行光路由，如果 条光蹄由和其他的光路由苁用同光纤链路，则相应的顶点f n 7 相连。通道t - 涉图 g 建立后，分配波长的思路为：在通道罔中为各项点着色，由于在同光纤内1 ：i 司 光通道必须分配不同的波长，凶此要求相连的顶，囊不能使用相同颜色。从而将m 题转 化为阁的着色问题，这是图论q t 的一个传统n p c 题，实际所需的波长数等于圈中 顶点的颜色数 _ | 。例如在陶23 中，连接请求集合为： ( a ，c ) ，( a ，i 一( a ，f ) ，( ( ：， e ) 假设允许最小跳距通道，则可行光路由为： ( a ，c ) ：a b ( a ，f ) ：a d t ：c c f ( a ，e ) ：c e ，a d ( c ，e ) ：b d 山东师范大学硕士学位论文 f f 占_ 一占 、 。叫 l a f 崮23 旧络托扑眨博14 逋j 箜f 涉目 图示表明，在选中通道的情况f 所；焉要的波k 数目w 最少，w = ! ， 这与利川有限割原理计算得出的波长下限桐i 州。在这种简印的情况r ，路l h 和波k 数 f j 最小化问题可以通过检a 而容易地得到解决。图着色法晌般步骤为： 1 根据连接请求，确定路山，任意选择g p 内的点以实蛾连接请求。组成由这! 点所组成的g n ，了图。 2 判断子图的颜色数：带， 3 重复一卜述过程得到的所有的选择，并选择一个具有最少颜色的路l l i 袋合。 1 算出皱选j ，图的最小着色数，即算法所需的最少波长数f 1 。 但是图着色法只适用二 光阳络舰模较小的情况下的静态波长分配，因为随莉刚 络中节点和光纤数最的增加，其可能的通道数量呈指数规律增长，而且图符色法小身 也足一个相肖复杂的问题。 2 3 3 最小跳距启发式算法 似设有m 个连接请求，算法的路由选择部分试图使光纤拥塞r 在任何一根光纤中 的通道数量) 最少，u p 使需要的波k 数景最少。算法如f ： 1 列出所有的连接请求，并为每个连接计算所有的最小跳距路由。 2 为每个连接安排任一最小跳距路由。 0 对每个连接，只要有一个最小跳距路由的拥塞情况小于已经安排的那个最小跳 距路由的拥塞情况，那么就用这个最小跳距蹄由来替换已经为给定连接安排的那个最 小跳距路由。 4 重复上述步骤，直到没有町以替换的最小跳距路由为l l ：。 一日安排了所有的路由连接，就相当r 执行了一个波k 路由算法；首先为最长的 路由百己置波长。步骤如卜： 1 将棚同长度的路山并入同一个集合，并按照长度的降序排列各集合。为每个波 长进行编号。 山东师范大学硕士学位论文 2 随机地为第一个集合选择一个路由。 3 在选定路由的任一链路上为该路由安排还没有被利用的编号最小的波长。 4 继续该波长配置算法，以便为第一个集合中所有通道安排波长。然后重复上述 步骤依次为其他的集合中的通道安排波长。 这种算法在各种测试中展示了优良的性能，同时计算是也是非常简单有效的，该 路由和波长分配算法的复杂性是o ( m ) 。 目前关于静态r w a 算法的研究，主要集中于分解算法，即将问题分为选路子问 题和波长分配子问题。具体的选路算法和波长分配算法主要集中在第三章中进行分类 研究。 2 4 静态r w a 算法综述 目前已有大量的静态分解r w a 算法，按照算法所共有的特征对其进行分类，以 总结研究现状，对进一步研究更优性能的算法具有启发意义。 算法分类结果如图2 5 所示，首先按照实际中的求解过程把问题分成选路和波长 分配两个子问题。每一个子问题中又分成两步，即寻找与选择，最后按照所用的具体 算法进行分类。当采用最短路由或加权最短路由算法时，直接得到每一个连接的唯一 路由，没有路由选择问题。当采用替换路由算法时，在源、目的节点间得到了若干条 各选的路由，需要从中选择一条合适路由，即图2 5 中“选择路由”框以下的算法。 在波长分配中，所有可用的波长都是需要进行选择的对象。 选路和波长分配r w a 选路子问题ll 波长分配予问题 选择波长 = 土麦 组合算法 贪婪式算法li 启发式算法ll 优化算法 图2 5 静态r w a 算法 选路子问题中的顺序算法( 贪婪算法) ( s e q u e n t i a la l g o r i t h m ) 包括选择 惫 一条一 山东师范大学硕士学位论文 顺序和选择规则，选择顺序是指先