（物理电子学专业论文）智能光网络中波长路由以及结构优化问题的研究.pdf

华中科技大学硕士学位论文 摘要 波长路由光网络( w r o n ) 是非常适合下一代高速广域网使用的一种网络。由于波 长资源有限，如何利用有限的波长资源，最大限度地提高网络的吞吐量以改善网络的阻 塞性能，成为w r o n 的核心问题之一。通过优化路由选择和波长分配( r w a ) 以及通 过合理引入波长转换技术是目前解决这个问题的两种方法。本文对它们开展了深入的研 究，提出了若干新方案，获得了一些创新研究成果。概括全文，主要工作以及成果有： ( 1 ) 查阅国内外文献，阐述路由与波长分配和波长转换在全光网中的重要作用和对 w r o n 光网络性能的影响，总结前人所得出的算法、模型和结果。 ( 2 ) 对光网络的路由和波长分配问题进行了深入研究。在现有算法的基础上，分别 对在静态网络和动态网络情况下的路由和波长分配提出了新的算法。通过与现有算法比 较，得出了本论文的算法性能要优于国外学者所提出的优化算法的性能。创新静态算法 通过消除波长关系图中孤岛和减少易阻塞节点度数使图的所有节点的度比较均衡而使 算法性能提高。集中式动态算法创新点在于根据网络中流量负荷，动态调节链路权值， 修正路由信息表，减少阻塞。分布式动态算法创新点在于引入提前释放机制和超时释放 机制能更有效地释放波长资源。 ( 3 ) 在前人研究的基础上，提出稀疏部分波长转换器在光网络中的最优化配置的数 学模型，利用优化改进的遗传算法有效地解决波长转换器在光网络节点中优化配置的 n p 完备性问题。同时分析了波长转换与波长路由之间的关系。其中遗传算法创新在于 通过自我调节变异和交叉因子的值，形成正反馈机制，加速对解空间的搜索速度和收敛 速度。 ( 4 ) 提出了一种新型全光波长路由器的专利结构，利用光开关搭建一个具有全光波 长低阻塞路由结构。通过放置波长转换器，从而使得系统克服了波长一致性的限制，大 大提高了波长重用率和降低了波长阻塞率。同时设计了套完整的光波长路由控制系 统，开发了实际使用的路由控制软件模块，构建了一个完整的光波长路由器系统。 关键词，波长路由光网络路由与波长分配波长转换 全光波长路由器结构遗传算法 阻塞概率 华中科技大学硕士学位论文 a b s t r a c t w a v e l e n g t hr o u t i n go p t i c a ln e t w o r k ( w r o n ) i s a p r a c t i c a b l et e c h n o l o g y f o r n e x t g e n e r a t i o nh i g h s p e e d b a c k b o n en e t w o r k s d u et ot h el i m i t a t i o no f w a v e l e n g t hr e s o u r c e 。 i ti sa ni m p o r t a n tp r o b l e mi nw r o nt h a th o wt ou t i l i z el i m i t e dw a v e l e n g t hr e s o u r c e sa n d i m p r o v e t h eb l o c k i n gp r o b a b i l i t yo ft h en e t w o r k sb y i m p r o v i n g t h ec a p a c i t yo ft h en e t w o r k s t h e r ea r et w om e t h o d st os o l v et h ea b o v ep r o b l e m o n ei s b yu s i n go p t i m a lr 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 ) ，t h eo t h e ri sb yu s i n go p t i m a lc o n f i g u r a t i o no fw a v e l e n g t h c o n v e r s i o n t h i st h e s i sc o n t a i n sw i d er e s e a r c ho n o p t i m a lr 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 a n do p t i m a l p l a c e m e n to f w a v e l e n g t hc o n v e r t e r s t h em a i np a r t sa r ea sf o l l o w s ： ( 1 ) b a s e d o nt h el e a m i n go f r e f e r e n c e s ，t h ei m p o r t a n c ea n dt h ee f f e c tt ow d mo f r w a a n dw a v e l e n g t hc o n v e r s i o nw e r ed i s c u s s e d t h e a l g o r i t h m s ，a n a l y t i cm o d e l s ，a n dr e s u l t s o b t a i n e db yo t h e rr e s e a r c h e r sw e r es u m m a r i z e d ( 2 ) w e h a v ed e e p l ys t u d i e dr w a p r o b l e mi na l l - o p t i c a ln e t w o r k sa n ds u b m i t t e dn o v e l o r i g i n a la l g o r i t h m so f s t a t i ca n dd y n a m i cr w a c o m p a r e dw i t hn o r m a la l g o r i t h m s ，w ef o u n d t h a tt h ep e r f o r m a n c eo fo u ra l g o r i t h m sw a sv e r ye x c e l l e n ta n dw a sb e a e rt h a nt h a to f o p t i m a l a l g o r i t h m ss u b m i t t e db yo t h e r s b ye l i m i n a t i n gt h el o n e l yi s l a n da n dr e d u c i n gt h ed e g r e eo f s o m en o d e se a s i l yb l o c k e d ，n o v e ls t a t i c a l g o r i t h mb a l a n c e dg r a p hc o n n e c t i v i t yt oi m p r o v e a l g o r i t h mp e r f o r m a n c e b a s e d o nt r a f f i cl o a di n n e t w o r k s ，n o v e lc e n t r a l i z e d d y n a m i c a l g o r i t h md y n a m i c a l l ya d j u s t e dp a t hc o s ta n dr e v i s e dr o u t i n gp a t ht a b l et or e d u c eb l o c k i n g p r o b a b i l i t y b yi n t r o d u c i n gp r e r e l e a s i n g s c h e m ea n d o v e n i m e - r e l e a s i n gs c h e m e ，n o v e l d i s t r i b u t e dd y n a m i c a l g o r i t h mc o u l de f f e c t i v e l yr e l e a s ew a v e l e n g t hr e s o u r c e ( 3 ) b a s e do np r e v i o u sm o d e l s ，w ee x t e n d e dt h a ta n dd e r i v e da na n a l y t i c a le x p r e s s i o nt o c o m p u t et h eb l o c k i n gp r o b a b i l i t i e si no p t i c a ln e t w o r k s t h e nw ep r e s e n t e do u ro p t i m a l c o n v e r t e rp l a c e m e n ta 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 mt os o l v et h i sn p - cp r o b l e ma n d a n a l y z e dr e l a t i o n s h i pb e t w e e nw a v e l e n g t hc o n v e r s i o na n dr w a b ya a j u s t i n gm u t a t i o nv a l u e a n dc r o s s o v e rv a l u e ，n o v e l g e n e t i ca l g o r i t h mf o r m e dap o s i t i v ef e e d b a c kt oa c c e l e r a t e s e a r c h i n gs p e e da n dc o n v e r g e n c es p e e d ( 4 ) b yu s i n go p t i c a ls w i t c h e s ，w ep r o p o s e dan e wk i n do f w a v e l e n g t hr o u t e ra r c h i t e c t u r e i to v e r c a m et h ew a v e l e n g t hc o n t i n u i t yc o n s t r a i n ta n dg r e a t l yi n c r e a s e dr a t i oo f w a v e l e n g t h i i 华中科技大学硕士学位论文 r e u s ea n dd e c r e a s e dt h e b l o c k i n gp r o b a b i l i t yb yp l a c i n gw a v e l e n g t h c o n v e r t e r s s i m u l t a n e o u s l y , w ed e s i g n e do u rw a v e l e n g t hr o u t e rc o n t r o ls y s t e ma n dd e v e l o p e dr o u t e r s o f t w a r ec o n t r o lm o d u l e w er e a l i z e daw h o l e w a v e l e n g t h r o u t e rs y s t e m k e y w o r d s ：w a v e l e n g t hr o u t i n go p t i c a ln e t w o r k s ( w r o n ) 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 ) w a v e l e n g t h c o n v e r s i o n a l l - o p t i c a lw a v e l e n g t hr o u t e ra r c h i t e c t u r e g e n e t i ca l g o r i t h m s b l o c k i n gp r o b a b i l i t y i i i 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 胸鹭 日期：伽垆年r 月$ 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密阢在 !年解密后适用本授权书。 本论文属于 不保密口。 ( 请在以上方框内打“4 ”) 学位论文作者签名： 佰晕 日期：劲牛年 月男日 指导教师签名： 日期：a 一濞 华中科技大学硕士学位论文 1 1引言 l 绪论 随着人类步入2 1 世纪，信息革命所带来的机遇和挑战正在不断的改变人们的现实 生活。人们生活的各个领域正面临着网络化的挑战。人们希望能够实现无论何时、无论 何地、无论通过何种方式都能够方便地获取需要的信息，这些刺激了全球通信业务的快 速增长，而这种快速增长的最直接后果是出现了所谓的对代表通信容量的带宽的“无限 渴求”现象。目前，商用化的电子设备速率只达到几十g b i t s 甚至更高，而光通信带宽 则可达到几十t b “s 。这样导致了目前光纤所能传输信息的带宽已远远大于现有电子路 由( 交换) 器处理信息的能力，致使由电子路由器构成的网络节点成为基于密集波分复 用( d w d m ) 技术川【2 】的宽带光网络信息传输的“电子瓶颈”。而光子技术可以有效的 克服电子技术的缺陷( 无r c 延时、电磁干扰等) ，所以必须考虑直接利用光来进行交 换。 目前的光通信网络的复用技术有波长复用( w d m ) 、时分复用( t d m ) 和码分复用 ( c d m ) 等多种形式。其中t d m 和c d m 对电子器件的速率要求很高，而在w d m 中， 电子设备的速率只需是一个波长信道的速率即可( 波长信道速率在理论上可以是任选 的) 。因为w d m 对电子速率没有特别的要求，所以它成为最吸引人的光域复用技术。 w d m 技术在光纤网中的应用正在经历一个从“线”到“面”的发展过程，即从点 对点的d w d m 系统，到环形网，再到网状网型的方向发展。普通的点对点波分复用通 信系统尽管有巨大的传输容量，但只提供了原始的传输带宽，需要有灵活的节点才能实 现高效的灵活组网能力。目前业界关注的焦点是智能光节点，即光分插复用( o a d m ) 和光交叉连接器( o x c ) ，靠光层面上的波长连接来解决节点的容量扩展问题，即能直 接在光路上对不同波长的信号实现上下和交叉连接功能。这样光网络节点( o n n ) 实现 了交换和选路功能，他们控制光信号路径，分配路径和创建希望的源和目的之间的连接。 1 2 波长路由网 在波长路由光网络中，光分插复用器( o a d m ) 、光交叉连接器( o x c ) 等节点设 备和光链路互相连接组成任意的拓扑结构，每个终端用户都通过光链路连接到o x c 等 华中科技大学硕士学位论文 节点设备上，终端用户与其相应o x c 的组合就是一个网络节点。 波长路由网络 2 1 是通过光通道( 1 i g h t p a t h ) 来实现通信的。光通道就是网络节点之 间的全光通信信道，可以跨越多个光链路。一条光通道上中间节点处的o x c 负责为光 通道提供光域的路由。光通道的终端节点则接收波长信号或将发射器调谐到特定波长 上，以建立波长信道。当一条光通道建立后，完全由此连接占用，不能分配给其它的连 接。只有当连接结束，这条光通道撤销后被它所占用的波长才能在这条光通道所包含 的光链路上再次变得空闲。这是因为波长路由网络的基本要求是同一光纤链路上的不同 光信道必须具有不同波长，以免通道间互相干扰。 在没有波长转换器的w d m 网络中，一条光通道输入端口和输出端口上的波长应该 相同，这一点就被称为波长连续性限制。而带有波长转换器的光网络，则不必满足这一 限制。虽然在配有波长转换器的全光网中，由于克服了波长连续性限制，使得连接建立 的可能性大大提高，但是这是以转换延迟、信号畸变、信噪比变差等为代价的。 无论是否使用波长转换器，源节点与目的节点在进行通信前必须建立光路。 幽i 1 波长选路过程举例 以图1 1 为例，它表示由两个光波长路由节点( s 1 和s 2 ) 和五个端点a 、b 、c 、 d 、e 构成的波长路由网络。若节点a 要同时发送信号到节点b 和节点c ，则a 到b 的信号传输可采用波长五，a 到c 的信号传输采用 、，经过波分复用送到s l 。s 1 先用 解复用器将z 。和 ：分离出来，分别送到b 和s 2 路由器上。兄，经s 2 处理后送到节点c 。 与此同时，若节点d 要送信号到e ，则仍可使用丑。，依靠s 2 的选路功能完成d 到e 的 光路连接，而不会发生在同一根光纤上因使用同一波长传送两路信号而导致的冲突。在 2 华中科技大学硕士学位论文 这个例子中，三条通信光路只使用了两个波长，这是因为用了波长路由器而实现了波长 重用的结果。这说明，波长路由网可以用较少的波长支持较多节点间的通信。因此在 w d m 网络中建立两点间的连接，若选择一条最佳路由和合适的波长，可极大的提高网 络效率，减少波长的阻塞，通过优化网络的路由和波长，还可减少节点设备的端口数， 降低网络成本。 1 3 光网络的路由和波长分配 波长路由为波长为高容量的光信号提供路由，其间对光信号不做任何光电变换或电 处理。波长路由光网络中，o x c 等节点设备与光链路互相连接组成任意的拓扑结构。 波长路由网络是通过光通道来实现通信的。在有n 个节点的电路交换光网络中，若 每个节点配置n l 套接收器和发射器，就有足够的波长分配给所有链路，则每对节点 都可通过专用的光通道互联，因此不存在互联问题。但是，如果因为收发器成本高而仅 给每个节点配置有限的收发器，或由于技术限制不能给网络提供足够的波长，那么网络 中的光波长通道数目就有限了。由于路由限制而不能建立某些光通道，因此造成某些波 长的“阻塞”，此情况下就出现了互联问题，即在给定的光通道数目和给定的波长数下， 如何分配波长、如何建立通道以使光网络路由最优化。这些问题就是所谓的路由和波长 分配r w a 问题 4 1 1 5 1 1 。 r w a 问题是一类n p 完备性问题( n p - - c o m p l e t e ) 【3 】【“。n p 完备性问题是非特定 多项式( n p ) 问题中的一类，具有下述性质：1 ) 这类问题中任何一个问题至今未找到 多项式时间算法；2 ) 如果这类问题中存在一个问题有多项式时间算法，那么这类问题 就有多项式时间的算法。根据n p 完备性问题的性质可知，无法找到关于任意复杂度 r w a 问题的时间算法。由于计算资源有限，只能对规模有限的网络优化做出r w a 问题 的解答。对大型网络，求其完全的解非常耗时间，通常将r w a 问题强行分为路由子问 题和波长分配子问题，如图1 2 所示。求解它的计算量随着网络规模的增大以指数方式 增加，随着节点变多求解最优解变得更加困难。在实际的算法研究中可以分解成两步骤： 第一：按照某种优化目标，寻找从源节点到目的节点的路由： 第二：在满足一定优化性能的情况下为这些路由分配波长； 有时上述两个过程要反复进行，直到得到最优的网络配置。 华中科技大学硕士学位论文 选路与波长分l l g o i w a ) 选路子甜、早嘲选路子问题波长分i e 早问题 i 寻找路由 i “、 i 一个路由多个路由i l 选择路由 选择波长 幽1 2r w a 算法分解为两个子问题分别求解示意图 r w a 问题根据网络连接的状态，可分为静态r w a 和动态r w a 两种。在静态情况 下，整个网络的连接是事先已知的。静态r w a 问题归结为：在尽可能少占用波长和光 纤等网络资源的情况下，为已知的连接请求建立光通道。换句话说，就是在给定的光纤 和波长等网络资源上建立尽可能多的光通道，所以静态r w a 问题又叫做静态光通道建 立( s l e ) 问题。 在动态情况下，连接请求不是预知的，网络需要即时为刚到达的连接请求建立光通 道，并在通信结束后拆除光通道。动态r w a 问题归结为：根据连接请求建立光通道并 分配波长，使连接阻塞概率最小或使连接数最大。动态r w a 问题又叫做动态光通道建 立( d l e ) 问题。动态r w a 较之静态r w a 具有更大的灵活性，但它必须能够适应网 络形状和流量的改变，所以d l e 问题求解比较复杂。 下面就来介绍一下常用的几种选路算法和波长分配算法。 1 3 1 常用选路算法【6 】 ( 1 ) 固定路由算法( f i x e d r o u t i n g ) ：这是最直接最简单的选路算法，网络总是为同 一节点对提供固定不变的光通道。选路是事先进行的，网络拓扑结构已知后，按照标准 最短路径算法( 如d i j k s t r a 算法) 为每个节点分配固定的光通道。网络运行中，每个节 点对之间的通信连接总是建立在预先设定好的路由上。如图1 3 所示，节点0 到节点2 的工作路由依次经过o 、1 、2 三个节点。这种方法虽然简单，却需要较多的波长资源。 4 华中科技大学硕士学位论文 在动态流量情况下，如果出现波长冲突，则会导致严重的流量阻塞。因为没有替代路由， 所以这种算法下网络不具备链路故障恢复能力。 图1 3 固定路由算法 图i 4 固定可选路由算法 图i 5 适应性最小开销路径路由算法 ( 2 ) 固定可选路由算法( f i x e d - a l t e r n a t e r o u t i n g ) ：网络中每个节点维护一张路由表， 里面罗列着它到其他节点的系列路由，其中包括作为工作光通道的最短路由和作为备 用光通道的路由。备用路由一般不跨越工作路由的链路段，即它们在物理上是分离的， 所以这种机制又叫做链路分离或边分离枫制。当节点收到连接请求对，先按照工作路由 华中科技大学硕士学位论文 建立光通道，若工作路由已被占用或失效，则在备用路由中选择次最短路由。如图1 4 所示，节点0 到节点2 的备用路由依次经过0 、5 、4 、2 节点。这种选路法的优点是简 单且具有链路故障恢复机制。与固定路由算法相比，流量被阻塞的概率显著减少。 ( 3 ) 适应性最小开销路径路由算法( a d a p t i v es h o r t e s t c o s t p a t hr o u t i n g ) ：这是一种 根据网络状态而动态选路的方法。每条未被占用的链路的c o s t 标记为1 ，已被占用的链 路的c o s t 标记为，具有波长转化能力的链路的c o s t 标记为c ，如图1 5 所示。当节点 收到连接请求时，首先建立c o s t 最小的路由。如果这样的路由有多条，那么随机选择其 中一条。可见，这种选路方法适用于具有波长转换功能的网络，当波长发生冲突时，可 以用波长转换来解决，光通道不必满足波长一致性条件。 1 3 2 常用波长分配算法 假设每条链路支持的光纤数为f ，每根光纤支持的波长数为w ，l ( p ) 代表通路p 的 链路集合。( f ，五) 代表链路，上波长兄剩余的可用信道数，只= ( p ，五) 代表通路p 上波 长为丑的最小可用信道数，称为通路p 上波长a 的瓶颈数，p 为新到达的呼叫对应路由 a ( p 。) 代表尸路由上对应的可用波长集，g ( p ) 代表与通路p 具有公共链路的固定路 由集合，称通路p ( p g ( e ) 为通路p 的相邻通路。常用波长分配算法主要有： ( 1 ) 图的着色法：这是一种静态波长分配算法，优化目标是使得网络波长需求最小。 首先把网络拓扑映射成着色辅助图，即光通道为辅助图的顶点，被多个光通道共享的链 路为辅助的无向弧，然后按一定的顺序给各个顶点着色，使得相邻顶点颜色不同。这样 就把波长分配问题转化为着色问题。辅助图中的颜色总数就是网络的波长需求。 ( 2 ) 波长随机分配法( r ：r a n d o m ) ：首先搜索所有波长集合，找出可用波长子集， 再从中随机选取波长分配给光通道。这种算法简单，并且不必知道整个网络的状态信息。 ( 3 ) 首次命中( f f ，f i r s t - - f i t ) 算法i ”：该算法将波长在可用波长集a ( p ) 中按固 定顺序排列波长( 如按由4 , n 大顺序排列) ，对新到达业务通路尸，每次选择波长时 均从a ( p ) 中按固定顺序选择可用波长。与随机分配法相比，f f 法不必搜索全部波长， 而是找到可用波长就停止，计算量更小，分配速度也较快。f f 法也不必知道整个网络 6 华中科技大学硕士学位论文 的状态信息。 ( 4 ) 最小4 e 用( l u ，l e a s t u s e d ) 算法【8 】：该算法统计网络中所有波长的使用率，并选 择波长使用率最小的可用波长分配给p 。即根据波长被占用的情况的统计，优先选取 被最少链路占用的波长。这种算法的出发点是使网络流量均匀分摊到各个波长上。但是 在l u 算法下，较长的光通道( 即跨越链路数较多的光通道) 往往被拆开，只有较短的 光通道容易保持波长一致性。除了计算复杂外，还需要设置专门的存储单元记录波长使 用信息，因此这种方法很少被采用。 ( 5 ) 最大使用( m u ，m o s t - - u s e d ) 算法【9 】：这种算法与l u 法正相反，优先选用被 最多链路占用的波长。实践证明这种算法的效率明显优于前三种算法，它有助于将流量 集中在少数波长上，这样可以减少网络的波长需求。 ( 6 ) 最大总和( m s ，m a x - - s u m ) 算法f 加1 ：经该算法选择波长后，网络中其它通路 的剩余可用信道数总和最大，其优化目标函数为： 蹄，( ，聚( 蹦) ) 其中p ( 尸，五) 代表分配波长五后，通路p 上波长为五的最小可用信道数。这是一 种既适用于单纤网络又适用于多纤网络的算法。 ( 7 ) 最小影响( l i ，l e a s ti n f l u e n c e ) 算法【“1 ：经该算法选择波长，对全网其它通路 的影响最小( 对相关通路造成的瓶颈总和最小) 。其优化目标函数为： ( d ( 上。( ，五) ，只( j p ，五) ) ) ( 1 2 ) 其中。c t c ，五，p c ( p ，a ，= 乏孑2 i 置 芜 ( 8 ) 相对容量损失( r c l ，r e l a t i v e c a p a c i t yl o s s ) 算法：该算法选取的优化目标函 数为： 船，b 一 ( 1 3 ) ( 1 3 ) 式中u ( a ) 为单位阶跃函数，当a 0 时取值为l ，否则取值为0 。它类似于 华中科技大学硕士学位论文 m s 算法，m s 算法致力于将绝对空闲容量最大化，r c l 则致力于将相对空闲容量最大 化。它们都适用于流量非标准的网络，r c l 算法的效果更好些。 ( 9 ) 相对最小影响( r l i ，r e l a t i v el e a s ei n f l u e n c e ) 算法：该算法选择的优化目标函 数为： d ( l 。( ， ) ，只( 尸， ) ) 勰协，鲤鼍丽矿一i 4 l 2 j ( 1 ，4 ) 式中，d ( l 。( ，丑) ，p a p ，兄) ) 定义同( 1 2 ) 。 目前，已提出的算法中，性能较好的算法为r c l 和r l i 算法。在r c l 算法中，当分 配波长给j d 时，优化目标中考虑了相对的容量损失，故能区分p 的所有相邻固定路由 中具有相同容量损失的情形。因此，相对值比绝对值更准确地描述了网络的状态，r c l 算法优于其之前的算法。r l i 算法在r c l 算法的基础上，记录了当分配波长给p 时，所 有瓶颈链路造成影响的相对值，因此r l i 算法描述的网络状态比r c l 更准确，其性能也 优于r c l 算法。 在第二章中，将详细介绍本论文提出的几种新的路由算法和波长分配算法，包括静 态和动态算法。 1 4 波长转换在波长路由网络中的作用。i 7 】 在光网络中，无论如何优化配置网络资源，也不可能完全使得网络中不发生波长冲 突，即要同时去往同一个输出端的来自两条入纤的光信号占用同样的波长。 解决波长冲突的方法有光缓存法、偏射路由法和波长转换法。因为受限于光器件的 发展水平，光缓存法的应用有限；偏射路由法要占用额外的网络资源，且常会影响其他 链路上的业务；相比之下，用波长转换技术解决波长冲突既简单又有效。 波长转换的引入，为光网络中的光波长通道提供了一种新的虚波长通道模式。虚波 长通道是指利用o x c 的波长转换能力，使光通道在不同的波长复用段可以占用不同的 波长，从而可以有效的利用各波长复用段的空闲波长来建立传送请求。提高波长的利用 率，降低了光网络的阻塞率。建立虚波长通道时，光通道层只需找到一条链路，其中每 个波长复用段都有空闲波长即可。在虚波长通道运作方式下，确定通道的传送链路后， 华中科技大学硕士学位论文 各波长复用段的波长可以逐个分配，因此可以进行分布式控制。这种方法可以大大降低 光通道层选路的复杂性。 一般波长通道方案存在波长全局分配的问题，增加了光通道实现的复杂性：虚波长 通道方案不存在这一问题。从网络和通道的扩展能力上看，虚波长技术优于波长通道技 术。采用虚波长技术的网络，波长的重利用率和路由选择的自由度都要高于采用波长通 道技术的网络。所以，在某一物理网络中建立相同数量的光通道，与虚波长通道方案相 比，波长通道方案需要使用更多的波长。换句话说，对同一物理网络结构和同样数目的 波长，虚波长通道网络可以建立更多的光通道。从通道波长的管理角度比较，波长通道 方案要求对全网进行集中式控制，而虚波长通道方案可以采取链路到链路的分布式控 制。在整个网络范围内，波长通道技术要求波长绝对精确，虚波长通道技术只要保证波 长从链路到链路相对精确即可。波长通道方案中，如果无法找到一条从源节点到目的节 点有相同空闲波长的光通道，就发生了波长阻塞，而使通道建立请求失败；而虚波长通 道方案只在通道中某个链路没有空闲的波长通道时才会令波长建立请求失败。 可见，引入波长转换技术，可以实现波长的再利用，解决o x c 中的波长的竞争问 题，可以有效的进行路由的选择，降低网络阻塞率，从而提高w d m 网的灵活性和可扩 展性。同时，也有利于网络的运行、管理和控制以及光通道的保护倒换。 虽然引入波长转换技术可以显著提高网络性能，但是全光波段的透明波长转换器实 现起来远比结构相对简单的合波器、分波器、_ 丌关和滤波器更困难，并且代价也更昂贵： 并且目前全光波长转换器的价格还非常昂贵，在网络中的所有节点都使用波长转换功能 是不经济的。虽然可以在光网络中通过使用波长转换器减少连接阻塞概率而使网络性能 得到重大的改善，但出于上述原因，在目前，所有节点均具有全光波长转换功能是不太 可能的，而且也并不是网络中所使用的波长转换器越多网络的性能就越优化。 这样就产生了一个值得研究的问题，即在w d m 波长路由网络中，如何在所使用的 波长转换器数量不多的情况下，通过优化配置波长转换器使网络获得性能最优化，即如 何在w d m 全光网络中放置波长转换节点，达到对网络性能改善的最佳效果。 波长转换节点在网络中的放置问题已经被证明为也是一种n p 完备性问题，对这类 复杂的问题，随着问题规模的增大，问题的搜索空间也急剧扩大，在目前的计算机上用 枚举法很难或甚至不可能求出其精确的最优解。目前已经提出来许多启发式算法来解决 这个n p 完备性问题，如模拟退火算法，图着色法，遗传算法等。 9 华中科技大学硕士学位论文 在第三章中，本论文将提出基于部分波长转换的稀疏波长转换器网络数学模型，并 根据这个模型给出了基于遗传算法的波长转换器最优配置算法。 1 5 本论文主要的研究内容 本文围绕在w r o n 网络中优化路由选择与波长分配( r w a ) 和优化配置波长转换 器这两个关键问题，开展了深入而广泛的研究工作，提出了若干新方案，并取得的创新 研究成果。 全文的内容组织如下： 第一章概述介绍了波长路由光网络的概念，阐述了所做研究的重要性；简要说明了 路由与波长分配和波长转换在全光网中的重要作用和对w d m 全光网络性能的影响；并 总结了前人在这两个问题上所得出的算法、模型和结果。 第二章介绍了相关网络拓扑学中图论知识和后面研究所用到的光网络的拓扑结构， 以及相关约定。 第三章将对静态情况下的光网络路由和波长分配问题进行了深入的研究，提出具有 很强创新性的静态情况下的路由和波长分配算法，根据对几个具体网络的计算，得出优 化结果，并和现有算法进行比较。 第四章将对动态情况下的光网络路由和波长分配问题进行了深入的研究，将分别提 出集中式和分布式两种动态算法，对具体网络计算动态算法的性能，并与现有算法性能 进行比较，得出结论。 第五章详细讨论如何在任意网络拓扑下，求解稀疏部分波长转换器在光网络中的最 优放置问题，并且讨论了波长转换和波长路由间的关系。 第六章将提出了一种新式具有波长转换能力的全光波长路由器专利结构，并且分析 了它的性能。同时本论文给出了详细的控制信令结构和完整的控制系统构造。 第七章总结了课题的研究工作。并在最后列出了参考文献和攻读硕士学位期间发表 的学术文章。 0 华中科技大学硕士学位论文 2 有关r w a 问题的基础知识 2 1引言 波分复用全光网以不同的波长作为传输信道，并且按照波长路由的方式进行交换和 网络重构，因此波长资源是网络中最重要的资源。由于掺铒光纤放大器( e d f a ) 增益 平坦带宽有限以及光纤中的非线性效应的限制，网络中能使用的波长数目是有限的。而 且，随着波长数目的增加，网络节点所需器件的规模和成本也会很快的增加，同时也增 加了网络管理的难度。因此，对于一个网络，如何合理的进行路由和波长分配是一个很 重要的课题。目前主要有两种类型的r w a 方式：静态r w a 方式和动态r w a 方式。 在静态过程中路由路径和波长是预先给定的，在任意时刻都不依赖于网络中的通信 过程，其建立时间短，而且改变不大，比较适合集中管理。一旦路径和波长设置被定义， 路由器可通过编程来建立预先设置的光路，分配不同的预定波长给共享同一根光纤的光 路。静态路由方式的缺点是波长利用率很低，因为即使两个通信过程不是在同一过程中 共享一根光纤，它们也必须使用不同的波长。因此，静态路由方式是一种基于吞吐量的 规则，它提供每个节点在同一时间与所有其他节点在同一时间通信所需的容量，它提供 了一种在现实中几乎从不使用的能力。 动态路由方式是一种基于需求的规则，光通路是根据两个节点的需要动态的建立， 在需要时建立，通信结束时解除，路由和波长的分配依赖于其它通信过程中所使用的连 接和波长。与静态方式相比，动态路由方式需要一定的建立时间来建立诸如上面提到的 满足w d m 约束的光通路。 在给出r w a 算法之前，先介绍文中所用到的通信网络拓扑学的有关图论知识和要 涉及的网络拓扑结构以及光网络拓扑模型和一些约定。 2 2 图论相关知识 通信网络的拓扑结构可以用图论学的知识来描述。 一个图由两部分组成：一部分是节点，图的术语中也称之为顶点：另一部分是顶点 的偶对，称之为边。通常，图的任意一对顶点间都允许有一条边。树和链表也可看作受 限图，从某种意义上说，图是最基本的数据结构。 华中科技大学硕士学位论文 图可用g = 缈，e ) 来表示，每个图都包括一个顶点集合v ( v = 扣。，v ：，_ ，v 。 ) 和一 个边集合e ( e = k ，e ：，e 。 ) ，其中e 中每条边都是v 中某一对顶点的连接。顶点总 数记为i v i ，边的总数记为吲。边数较少的图称为稀疏图，边数较多的图称为密集图。 如果图中的边限定为一个顶点指向另一个顶点，则此图称为有向图。如果图中的边 没有方向性，则称之为无向图。光网络中由于每条链路，都可在其连接的两个节点间的 任一方向进行通信，因此，代表它的图应是无向图。 如果图中各顶点均带有标号，则称之为标号图。通过某条边连接的两个顶点是相邻 的，称它们为邻接点。连接一对邻接点u 、v 的边被称为与顶点u 、v 相关联的边，记作 ，、 博，”j 。每条边都可能附有权值。边上标有权值的图称为带权图。由于光传输系统的高速 性，物理链路的长度可以使用链路通过的节点跳数( h o p s ) 直接表示。 如果从顶点v ，到顶点v 。( j s f k ) 的边均存在，则称顶点序列卜，v ，。j 构成 一条长度为k j l 的路径。如果路径上各顶点均不同，则称此路径为简单路径。路径 长度是指路径包含的边的数目。如果一条路径将某个顶点连接到它本身，且其长度大于 等于3 ，称此路径为回路。 图中某节点i 的度数等于与该节点相关联的边数。如果一个节点的度数为零，称它 为孤岛。一个具有n 个顶点的图g ，在去掉任意k - 1 个顶点后( 1 = k = n ) 所得的子图仍 连通，而去掉k 个顶点后的图不连通，则称图g 是连通的，k 称作图g 的点连通度。 当给定光网络的物理拓扑结构，可以用一个无向图g = ( v ，e ) 来表示。每个顶点对 应实际网络中的光交叉连接节点，而边对应连接两个节点间的一组光纤对。假设每条光 纤有 个波长的集合，巩表示网络中源目的节点对之间的总通道数。 2 3 网络拓扑模型和相关约定 本节将给出文中所研究的典型的光网络的拓扑结构。如图2 1 所示是一个5 节点的 简单示范网络；如图2 2 所示是1 0 节点中国教育和科研计算机网( c e r n e t ) ：如图2 3 所示是1 4 节点美国自然科学基金网( n s f n e t ) ；如图2 4 所示是1 9 节点泛欧洲光网络 ( e o n ) 。 华中科技大学硕士学位论文 图2 15 节点示范网络拓扑图 图2 2 1 0 节点中国教育平| j 科研计算机网拓扑图 图2 - 3 1 4 节点美国自然科学基金网拓扑图 图2 4 1 9 节点泛欧洲光网络拓扑图 1 3 7 i 1 lt，；3 f 华中科技大学硕士学位论文 文中所研究的光网络拓扑模型是基于以下几个公认约定： ( 1 ) 网络中包含n 个节点和l 个双向光纤。每个节点包含一个终端节点和一个路由 节点，终端节点发射和接受光路( 实现上下路的功能) ，而路由节点则是把光路从源节 点路由到终端节点( 实现交叉互连的功能) 。 ( 2 ) 任意直接相连的两个节点之间包含一对方向相反的单向光纤或一个双向的光 纤，这被称为一个物理链路( l i l l l ( ) 。由于光传输系统的高速性，物理链路的长度可以 使用链路通过的节点跳数( h o p s ) 直接表示。 ( 3 ) 任意两个节点之间的通信都占用且只占用一个波长信道。 ( 4 ) 均匀通信流量，所有的通信在网络上均匀分布。来自网络上每个源节点的通信 数目相同，所有通信的目的节点平均分布在网络上。网络中源目的节点对( s , d ) 与( d , s ) 分配同样的路由，因此网络总的光通道数为n ( n 1 ) 2 个光路。 ( 5 ) 光网络使用波长数量预先给定。 ( 6 ) 利用最短路径路由算法来找到源节点和目的节点之间的光通道。如果几条光通 道的跳( h o p s ) 的数目是一样的，那么路由的选择就是随机的。 ( 7 ) 呼叫的到达服从泊松分布，占用时间服从指数分布。 ( 8 ) 噪音，信号功率衰减，物理层故障等，在仿真系统中不加以考虑。 2 4 小结 本节主要介绍了相关网络拓扑学的图论知识和后面研究所用到的光网络的拓扑结 构，以及研究中所用到的相关约定。 4 华中科技大学硕士学位论文 3 静态情况下路由与波长分配算法 3 1 引言 已经证明w d m 全光网中路由和波长分配问题是一个n p 完备性问题口1 i 们，因此只 能用启发式算法进行求解，一般将其分解为两个子问题即路由问题和波长分配问题分别 求解，但是路由与波长分配问题之间是有联系的，如果分开来分析结果并不是最优，因 此认为应该同时考虑，基本思想是首先初始化路由，得到系统初始状态，然后进行波长 分配问题的分析，然后通过分析结果的反馈来修正初始路由，如此几次，最后就得到了 性能更好的问题解。 本章详细介绍本论文提出的静态路由与波长分配算法，用图2 1 所示简单示范网详 细说明算法原理，通过计算在图2 2 、图2 - 3 、图2 4 三个网络中的算法性能并与已有算 法比较，得出结论。 3 2 静态路由算法 第一章中已经介绍了许多静态路由算法，目前最常用的静态算法是最短路径算法 ( d i j k s t r a 算法和f l o y d 算法) 【i b l ，本论文根据图论的知识结合波长分配，改进了d i j k s t r a 最短路径算法，提高了算法性能，降低了网络阻塞概率。 首先介绍d i j k s t r a 路由算法。 所谓路由算法，就是确定从源节点到目的节点有向路径的一种规则。d i j k s t r a 算法 ( 简称d 算法) 是求解一个指定节点到其余所有节点间的最短有向路径的一种有效算