（信号与信息处理专业论文）wdm光网络中动态波长分配算法的研究.pdf

浙江工业大学硕士学位论文 w d m 光网络中动态波长分配算法的研究 摘要 w d m 光网络由于其高带宽、高速率、组网灵活等各种优越性 被认为是未来骨干网的发展方向。波长资源是影响w d m 光网络性 能的主要因素，而波长分配算法是解决网络资源合理配置和提高网 络运行效率的重要途径，所以研究波长分配算法具有十分重要的意 义。本文把动态波长分配算法分成单纤和多纤两个不同的数学模型 进行总结和改进，单纤光网络中波长分配算法以均衡波长数为目标， 多纤光网络中波长分配算法以均衡每个波长的信道容量为目标。在 研究方法上，针对改进的算法建立网络模型，通过软件仿真来比较 不同算法的性能。本文主要分成以下四个方面： 1 从数学模型、理论算法等角度分析了单纤和多纤光网络的波 长分配问题，并且介绍了当前比较常见的波长分配算法，分析了常 见算法的思路和优劣性。针对软件仿真介绍了两种不同的业务量模 型，并分别给出了生成方法。 2 基于光网络单纤数学模型提出了两种改进型的波长分配启发 式算法。第一种是从预选波长角度出发，通过对路由子问题进行约 束，提高波长使用率；第二种是运用波长分集重用思想，对不同q o s 要求的业务设置不同的分配策略，在保证公平性的同时改善了网络 浙江工业大学硕士学位论文 效率。 3 基于光网络多纤数学模型提出了两种改进型的波长分配启发 式算法。第一种基于均衡波长信道容量思想的波长分配算法，通过 保护瓶颈链路容量，降低全网的拥塞概率；第二种是同时控制优先 级和业务均衡的双优化目标算法。 4 介绍了论文作者设计开发的波长路由算法集成软件 w r o n - r w a ，着重介绍了t o p o l o g yd e s i g n 组件和b l o c k i n g p r o b a b i l i t y 组件。 关键词：w d m 光网络，波长分配，均衡策略，优先级，启发 式算法 浙江工业大学硕士学位论文 1 叵r e s e a r c ho fd y n a m cw a 吼e n g t h a s s i g n 匝n ta l g o r i t h m i nw d m0 p t i c a ln e t w o r k s a b s t r a c t d u et oi t se n o f n l o u $ b a n d w i d t h ，h i g h - s p e e d ，f l e x i b l ep e r f o r m a n c e a n do t h e rs u p e r i o r i t y , w d mo p t i c a ln e t w o r ki sc o n s i d e r e dt h ef u t u r eo f b a c k b o n e n e t w o r k w a v e l e n g t h r e s o u r c ei st h e m a j o r f a c t o ro n i m p a c t i n gw d mo p t i c a l n e t w o r k s p e r f o r m a n c e ，a n dw a v e l e n g t h a s s i g n m e n ta l g o r i t h mi s a l li m p o r t a n ta p p r o a c ht oa l l o c a t er e s o u r c e r e a s o n a b l ya n di m p r o v et h en e t w o r ke f f i c i e n c y , t h e r e f o r ei ti sc r u c i a lt o s t u d yt h ew a v e l e n g t ha s s i g n m e n ta l g o r i t h m i nt h i st h e s i s ，w a v e l e n g t h a s s i g n m e n ta l g o r i t h m i s a n a l y z e d i nt w om a t h e m a t i c a lm o d e l s s i n g l e f i b e r ( s f ) m o d e l a n dm u l t i - f i b e r ( m f ) m o d e l s fm o d e l s o b j e c t i v ei st ob a l a n c en u m b e ro fw a v e l e n g t h s m fm o d e l so b j e c t i v ei s t ob a l a n c ep a t hc a p a c i t yo fe v e r yw a v e l e n g t h i nt h er e s e a r c h , m o d e l b u i l d i n ga n ds o f t w a r es i m u l a t i o ni su s e dt oc o m p a r et h ep e r f o r m a n c eo f d i f f e r e n ta l g o r i t h m s t h i st h e s i si sd i v i d e di n t o4p a r t s 1 t h es fa n dm f w a v e l e n g t ha s s i g n m e n ta r ea n a l y z e d ，i n c l u d i n g 皿 浙江工业大学硕士学位论文 t h em a t h e m a t i c a lm o d e la n dt h e o r e t i c a l a l g o r i t h m t h e a u t h o r s u m m a r i z e st h ew a v e l e n g t ha s s i g n m e n ta l g o r i t h m sw h i c hc a nb eo f t e n s e e ni nt h el i t e r a t u r e s ，a n d i n t e r p r e t st h e i ri d e a sa n dp e r f o r m a n c e b e s i d e s ，t h ea u t h o ra l s oi n t r o d u c e st w ot r a f f i cl o a dm o d e la n de x p l a i n s h o wt og e n e r a t et h e m 2 t w oi m p r o v e dh e u r i s t i cw a v e l e n g t ha s s i g n m e n ta l g o r i t h mb a s e d o n s i n g l e f i b e rm o d e la r ep r o p o s e d t h e f i r s to n ei sb a s e do n p r e - s e l e c t i n gw a v e l e n g t hi d e a ，i tr e s t r i c t sr o u t ep r o b l e mb yr e s o u r c ea n d i m p r o v e sw a v e l e n g t hu t i l i z a t i o n sr a t e t h eo t h e ro n eu s et h ei d e an a m e d w a v e l e n g t h s e t , i ta l l o c a t e sd i f f e r e n ts t r a t e g yf o rt h ed i f f e r e n tq o s t r a f f i cs ot h a tf a i r n e s sc a nb ei m p r o v e d 3 t w oi m p r o v e dh e u r i s t i cw a v e l e n g t ha s s i g n m e n ta l g o r i t h mb a s e d o nm u l t i f i b e rm o d e la r ep r o p o s e d t h ef i r s to n ep a y sa t t e n t i o no nt h e b a l a n c i n gs t r a t e g y t h eo t h e ro n es e t st w oo p t i m i z e do b j e c t i v e si nt h e a l g o r i t h m ，t h a ta r ec o n t r o l l i n gp r i o r i 够a n db a l a n c i n gt r a f f i c 4 s o f t w a r ew r o n - r w ai sd e v e l o p e dt oe v a l u a t et h ei m p r o v e d a l g o r i t h m t h e a u t h o r sm a i nc o n t r i b u t i o n sa r e t h e w a v e l e n g t h a s s i g n m e n tp a r t ，t o p o l o g yd e s i g nc o m p o n e n t sa n db l o c k i n gp r o b a b i l i t y k e y - w o r d s ：w d mo p t i c a l n e t w o r k , w a v e l e n g t ha s s i g n m e n t ， b a l a n c i n gs t r a t e g y , p r i o r i t yc l a s s ，h e u r i s t i ca l g o r i t h m i v 塑堡三些盔兰堕主兰垡笙塞 图列 图1 - 1 波长路由w d m 光网络结构示例2 图2 1 单纤光网络分集波长重用的结构图1 3 图2 - 2 波长图结构，一一1 4 图2 - 3 多纤链路模型 1 5 图2 4o n o f f 模型产生自相似业务量2 0 图3 - 1 稀缺波长模型。2 2 固3 - 26 节点网络拓扑2 3 图3 - 3c e r n e t 网络拓扑 2 4 囤3 - 4p w a 算法和其他算法拥塞概率比较2 5 图3 - 5 全网平均带宽2 5 图3 缶不同波长转换比例性能比较2 6 图3 7 有强状态生灭过程的状态转移国一2 7 图3 - 8 第f 类业务的状态转移圈 2 8 图3 - 9 单类业务波长集分配示意图2 8 固3 - 1 0 两个优先级波长集分配示意国2 9 图3 - 11 两个优先级业务状态转移图2 9 图3 - 1 2 基于q o s 的动态共享算法示意圉3 2 图3 1 3 门限共享池状态转移示意图3 3 图3 - 1 44 x 4 网格型网络一一” 图3 ，1 5 在业务负载增太情况下不回算法的性能比铰一3 5 图3 q 6 轻业务负载情况下算法对于不同优先级的影响，一一，一3 j 图3 1 7 主波长集波长数对拥塞概率的影响 3 6 图3 - 1 8 不同算法的公平性分析3 6 图4 - 1 光纤模拟图。4 l 图4 - 2 仿真用4 x 4 的网格网络，4 2 图4 - 3 三种算法在网络拥塞概率性能上的比较4 3 图4 4 算法在不同波长数的拥塞概率：一4 3 图4 。53 2 光通道不同波长数下算法比较4 卑 图4 - 66 4 光通道不同波长数下算法比较4 4 图4 7 优先级控制的示意图4 6 图4 s 两个优先鲡状态转移图一4 8 图4 - 9 用于均衡策略的波长模型 4 9 固4 1 0 n s f n e t 网络一，5 0 图4 - 1 不同波长分配算法的的捆塞概率比较，“5 0 图4 - 1 2 相同负载下不同优先级自q 拥塞概率比较一，5 1 图4 1 3 不同优先级的波长利用率比较5 1 图5 - 1 波长分配算法架构示意图山 5 5 囝5 - 2r w a 算法菜单。，5 6 图5 - 3 w r o n r w a i 0 版本界面 5 6 图5 - 4 菜单视图。5 7 图5 - 5 工具栏。 图5 - 6 自定义拓扑5 7 浙江工业大学硕士学位论文 图5 7 设置节点编号视图。5 7 图5 - 8 设置权重视图5 8 图5 - 9 自定义n s f n e t 拓扑5 9 图5 一1 0 算法选择和路由输出5 8 图5 - 1i 动态显示路由5 9 图5 1 2b l o c k i n gp r o b a b i l i t y 组件界面5 9 图5 1 3 位图保存6 0 v 埘 浙江工业大学硕士学位论文 表列 表1 - 1 对于r w a 问题的算法总结。4 表3 - 1 全网波匠均衡计算2 3 表3 - 2 不同基于优先级波长分配算法的比较3 3 表4 1 各个波长的路径容量i 4 l 表4 - 2 各种算法选取波长的比较4 1 表4 3 计算时间复杂度比较4 5 表4 4 多重判决准则的比较4 9 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工 作所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个 人或集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育 机构的学位证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均 己在文中以明确方式标明。本人承担本声明的法律责任。 作者签名： 体叙 隰川年p 月v f 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密彤 ( 请在以上相应方框内打“”) 日期：- 7 年j 月动r 日 日期：卿年l p 月才日 浙江工业大学硕士学位论文 1 1 研究内容和研究意义 第一章绪论 随着互联网业务的爆炸性增长和光网络器件的快速发展，w d m 光网络被 认为是下一代高速广域骨干网的最有竞争力的候选者l l 】1 2 j 。从光纤通信的历史 上来看，上世纪八十年代初光纤传输系统投入商用以来，光纤通信的技术、经 济优势迅速使光纤传输代替铜缆传输而成为核心网的主要传输手段，第一代光 网络随之发展起来。而到了上世纪的九十年代末，以掺铒光纤放大器( e d f a ， e r b i u m d o p e df i b e r a m p l i f i e r ) 为代表的光纤放大技术和以阵列波导光栅( a w q a r m yw a v e g u i d eg r a t 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 ) 和密集波分复用技术( d w d m ， d e n s ew 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 层， 第二代光网络也随之走向成熟【3 】。目前所说的“光网络”概念是由高性能的光 电转换设备连接众多的全光透明子网的集合，是i t u t 有关“光传送网”( o t n ， o p t i c a lt r a n s p o r tn e t w o r k ) 概念的通俗说法。光传送网是在现有的传送网中加 入光层，提供光交叉连接( o x c ，o p t i c a lc r o s s c o n n e c t ) 和光分插复用( 0 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 ) 功能，提供有关客户层信号的传送、复用、选路、 管理、监控和生存性功能。由于全光通信网在光域进行交叉连接和分插复用， 从而减轻电交换节点的压力，大大提高整个网络的传输容量和节点的吞吐容量。 光传送网成为2 0 世纪9 0 年代中期以后光网络的研究热点，也是网络升级的优 选方案【3 1 。 w i ) m 光传送网是基于光域的组网形式，一般分为广播与选择网( b r o a d c a s t a n ds e l e c tn e t w o r k ) 和波长路由网( w a v e l e n g t hr o u t e d n e t w o r k ) 。本文讨论的 是具有波长路由功能的w d m 光网络。这种w d m 光传送网利用波长路由和光 交换技术，由光层网络的节点直接提供对高速光数据流进行透明的交叉连接功 能，而电层网络的节点用于形成高速光数据流并对其中复用的低速和中速比特 流实现交叉连接。由于光、电系统互为补充，相辅相成，从而避免了大量的不 必要的针对转接业务的复用、解复用处理操作，简化了节点交换结构的规模。 波长路由光网络是由网络节点和链接节点的单纤或多纤构成，光网络的节点能 交叉连接输入和输出的光信道，具有动态重构光网络的特性。当客户层业务到 l 浙江工业大学硕士学位论文 达时，w d m 光网络需要给每条业务在接入点间分配路由和选择波长，建立光 传送通道传送业务。 相对传统s d h 而言，i t u t 所定义的基于波长路由的o t n 的主要优势在 于【1 】： 具备更强的前向纠错能力。o t n 的带外前向纠错比s d h 的带内前向纠 锗可以改进纠错能力3 - 7 d b ： 具有多级串联连接监视功能。监视连接可以是嵌套式、重叠式或级联式， 而s d h 只允许单级； 支持客户信号的透明传送。s d h 只能支持单一的s d h 客户信号，而 o t n 可以透明支持所有客户信号； 交换能力上的扩展性。s d h 主要分两个交换级别，即2mb i f f s 和1 5 5 m b i f f s 。而o t n 可以随着线路速率的增加而增加任意级别的交换速率， 与具体每个波长信号的比特率无关。 所以波长路由的w d m 光网络在组网上更加具有灵活性，它的透明性还可 以使其支持各种客户层信号，功耗较小，有更高效的多端口交换能力，具有更 长远的技术寿命。 然而波长路由在进行选路和分配波长的时候需要满足不同波长限制条件 ( 如果两条光通道同时使用了同一条物理链接，那么这两个光通道在这条物理 链接中必须被分配不同的波长) 。在没有波长转换器的情况下，还必须满足波长 连续性限制条件( 一条光通道在一条物理链接中会被分配一个特定的波长) 1 3 】。 比如图1 1 中f 到b 的光通道和g 到c 的光通道就满足波长连续性限制，而且 在两个光通道存在共享链路，所以必须使用不同的波长。对于带有波长转换器 的光通道则不必满足波长连续性限制，比如图中e 到d 的光通道。 图l - 1 波长路由w d m 光网络结构示例 在考虑成本的情况下，网络单元的功能依然会受到限制( 例如：网络节点 2 浙江工业大学硕士学位论文 是否具有波长变换功能) ，网络中实际可以使用的网络资源也非常有限( 例如： 波长和收发器数目) ，因此在网络的所有接入节点之间建立直接的光通道连接是 非常困难的。鉴于光网络存在上述这些因素的限制，为了合理进行网络优化设 计，合理利用网络波长资源就需要使用路由与波长分配( r w a ，r o u t i n ga n d w a v e l e n g t h a s s i g n m e n t ) 算法。路由与波长分配问题就是研究在波长路由w d m 光网中如何选择一条合理的路由并给该路由分配一个选定的波长的问题”“，波 长分配算法正是解决资源合理配置，均衡业务量的主要途径。光网络不同链路 上的波长资源对业务请求的路由选择也有影响，所以要合理的建立光通道，路 由选择必须是在波长资源合理配置基础上进行的。在动态业务量下，波长分配 算法还要考虑波长分配的公平性和优先级。所以说研究w d m 光网络中动态波 长分配算法对合理构建光网络，提高光网络的整体性能具有十分重要的意义。 对于一些网络规划单位，可以通过考察一个网络中的波长需求量来制定其相应 的网络设计方案，通过研究已有网络的波长负载来制定相应的网络扩容方案； 对于设备而言，针对不同业务量的波长分配算法被各大设备制造商用于其软件 中。业务量尽量均衡地分配在网络资源中已经成为评价设备水平和性能的标准， 所以对w d m 光网络中波长分配算法的研究已经成为光通信研究机构和光通信 设备制造商关注的热点。 1 2 国内外研究现状 国内外研究人员通常按照连接请求不同属性把r w a 问题分成两种情况： 1 静态r w a 静态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 ) 【3 】。它以网络物理拓扑的节点为节点，由光路实现的虚链路连接而 成。所以可以说静态的r w a 算法为逻辑拓扑的生成架构了一个理论基础。 2 动态r 、a 动态r w a 问题是相对于动态业务量而言的。动态业务流量是指节点对之 间的连接请求不是预先给定的，而是随着时间变化动态到来的，当连接建立好 并保持一段时间后又会被拆除。即不断有连接请求到来，也不断有己建立好的 连接被拆除。目前通常假设连接请求的到达符合泊松过程，连接的保持时间符 合指数分布。 浙江工业大学硕士学位论文 解决动态r w a 问题时，般都是在光网络边缘节点进行r w a 计算，选择 合理路由并分配可用波长，也就是选择光通道。研究动态的r 队算法就是要 研究路由和波长的重构算法，让网络资源进行必要地均衡和分散，解决网络的 拥塞问题，改善网络的性能。 一个具体的r w a 问题，可以通过波长分层图算法直接解得最优解，但是 当网络结构趋向复杂的时候，这种算法的计算时间复杂度迅速加大，因此研究 人员通常把r w a 问题分成路由子问题和波长分配子问题，通过分别求解来求 得满足条件的近似解。从目前文献中提出或者讨论的r w a 算法来看，有两种 类型的路由和波长分配问题的优化解决办法：( 1 ) 基于线性规划模型；( 2 ) 快 速有效的启发式算法。 对于基于线性规划( l p ) 模型的路由和波长分配解决方案，目前已经提出 了许多整数线性规划( i l p ) 公式或者是混合整数线性规划( m i l p ) 公式1 7 。， 例如针对单跳波长路由光网和多跳波长路由光网。虽然线性规划模型可以很好 地对波长路由光网进行描述，获得网络的最优解，但是由于路由和波长分配问 题是一个非特定多项式完全性( 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 ) 问题，也就是说，路由和波长分配问题不能够在多项式时闻内完成问题的求解。 对于这样的问题，用整数线性规划方法需要进行大量的运算，根据目前的计算 资源，这类方法往往只适于中小规模的波长路由光网的优化设计。为了解决该 问题，目前有些文献考虑通过放松或是取消一定的约束条件使问题简化，从而 获得问题的近似解。 由于波长路由光网的路由和波长分配问题是一个n p c 问题，虽然线性规划 方法能够获得准确的最优解，但是由于它计算复杂，花费的代价高，不适合应 用于大通信负荷或是大规模网络的设计。在这种情况下往往需要采用近似优化 的启发式算法，这是因为启发式算法强调的是得到“满意解”，在实际问题的决 策过程中，往往不去苛求最优性和探索最优解。启发式算法是在研究问题模型 和优化解之间内在联系的基础上获得启发而建立的。它的优点在于：计算步骤 简单，易于实现；计算量小，能够在短时间内获得问题的求解；易于将定性分 析和定量分析相结合。因而启发式算法具有很大的实用性，对于波长路由光网 中启发式算法的研究已经得n y 广泛的重视。下表是对具体算法的总结【9 】。 表1 - i 对于r w a 问题的算法总结 问题 解决方法 0 彤o nl i n e文献评价 静态r w a 整数线性规划 o f f l i n e n p c 整数线性规划 o f f l i n en p c 动态路由 固定路由相同的算法思想可以用较 0 伍，o nl i n e 备用路由多的资源换取较好性能 浙江工业大学硕士学位论文 续表1 1 对于r w a 问题的总结 问题解决方法 o f f o nl i n e 文献评价 动态路由自适应路由 o n l i n e 比较复杂 着色法 一般波长分配 o f f o nl i n en p c 整数线性规划 r a n d o m f f m u l u 启发式算法，基于均衡的思 动态波固定路由+ 启 m a x s u m o n l i n e想是所有算法的核心，也是 长分配发式波长分配 r c l 理论的突破口 l l l i r u 结合o b s 的思路，采用预 其他波长分配 r s v l ro n i i n e 约资源方法 在研究方法上，一般分为建立试验网和理论建模仿真两种。 1 试验网方法，一般用于比较成熟的网络。国内外一般通过构建光网络试 验网来研究光网络的特性，然后通过大量实验数据来比较所采用算法的优劣。 特别是近年来，波长路由光网已成为研究的热点。欧洲己经在其r a c e 计划中 将多波长传送网列为研究目标。在后续的a c t s 计划中，又在欧洲各地建立一 系列实验性的w d m 波长路由光网络，如o p e n ，p h o t o n 和m e t o n 等。美 国在国防部高级研究计划局( d a r p a ) 的资助下，组建了多个研究团体，建立 了系列光传送网，用于实验和验证各种新技术。日本则是以大公司的投资建 设为主，如n t t 建立的o p n 。i t u t 也在积极制定有关光传送网的建议。我 国的一些单位也开展了光传送网的研究工作。1 9 9 8 年5 月，国家自然科学基金 委员会发布了重大项目“w d m 全光网基础研究”。1 9 9 9 年6 月，国家高技术 研究发展计划( 8 6 3 计划) 发布了信息技术领域跨主题重大研究项目“中国高 速信息示范网研究开发项目( c a i n o n e t ) 。此外作为国家8 6 3 计划“十五” 期间的一个专项的高性能宽带信息网( 3 t n e t ) ，它采用核心网加边缘网的网 络框架。在核心网使用电路交换的自动交换光网络( a s o n ，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 ) ，支持t 比特传输；边缘网采用电路和分组混合的交 换体制。3 t n e t 具有t b p s 交换容量、多类型业务接入、动态资源分配、自动 连接控制和网络保护恢复等功能；链路层具有突发交换式连接、组播。该项目 旨在探索满足端到端带宽达到4 0 m b p s 的实用化、可管理、可运营的广域高性 浙江工业大学硕士学位论文 能宽带信息网的方法和途径1 4 j 。 2 理论建模仿真方法，一般用于实验室仿真阶段。对于一个新型算法需要 验算其可行性，建模仿真具有速度快、代价小、可重复演算等优势。仿真内容 可以是一个大型网络，也可以是单个节点性能。即使要建立试验网进行研究， 也必须经过充分的仿真，以降低可能的投资。目前国外比较有名的光网络仿真 软件有v p i 公司的v p i 系列软件，o p n e t 公司的o p n e t m o d e l e r 软件，开源 软件n s 2 和能同时仿真光器件和光网络的p 1 d s 软件。这些软件的仿真功能都 比较强大，但是大多数成套的软件非常昂贵，而且对于研究者来说碰到新问题 都需要重新建模，所以自行开发小规模的软件来进行仿真是非常必要的。对于 启发式算法，运用逻辑描述简便的c 或者j a v a 等开发语言进行仿真具有很高的 执行效率m j 。 1 3 主要工作和论文内容安排 本文主要研究w d m 光网络中动态波长分配算法，分为以下几个部分：分 析波长分配问题，归纳了光网络中波长分配算法的数学模型以及文献中已有的 基本算法；提出了两种单纤光网络的改进波长分配算法；提出了两种多纤光网 络的改进波长分配算法；介绍了论文作者编写的软件w r o n r w a ，包括两种 实用的组件。论文分章节安排如下： 第二章通过对光网络的资源进行定量的数学分析，分别对单纤光网络和多 纤光网络归纳了不同的数学模型，并基于模型归纳各种不同的波长分配算法。 最后对业务量仿真模型进行了概括，提出了种自相似业务量模型的产生方法。 第三章以单纤光网络研究模型，分别从比例模型和波长分集重用两个方面 进行了研究，提出了两种改进的动态波长分配算法：基于预选波长的全网均衡 算法和基于q o s 动态共享算法。通过网络仿真比较了不同算法的性能。 第四章主要介绍了两种新型的多纤波长分配启发式算法。第一种是最大剩 余瓶颈容量算法；第二种是基于优先级和均衡策略的波长分配算法。两种算法 分别以单目标参数和双目标参数进行了优化。 第五章介绍了论文作者所在的研究组开发的一个集成多种r w a 算法的软 件平台w r o n r w a ，通过该平台可以验算已有的1 6 种r w a 算法的性能。 w r o n r w a 的1 0 版本和2 0 版本均己获得软件著作权的授权。论文作者主要 负责其中波长分配算法的实现，并负责开发了2 o 版本中t o p o l o g yd e s i g n 组件 和b l o c k i n gp r o b a b i l i t y 组件的开发。 第六章是对论文的总结和对迸一步研究的展望。 6 浙江工业大学硕士学位论文 第二章光网络的波长分配问题 本章主要介绍光网络中波长分配算法的具体情况，包括光网络的业务分类， 单纤光网络的网络模型和已有波长分配算法思路，多纤光网络的网络模型和已 有算法思路，具体仿真时用到的仿真模型。波长路由在进行选路和分配波长的 时候需要满足不同波长限制条件( 如果两条光通道同时使用了同一条物理链接， 那么这两个光通道在这条物理链接中必须被分配不同的波长) 。在没有波长转换 器的情况下，还必须满足波长连续性限制( 一条光通道在条物理链接中会被 分配个特定的波长) ，所以波长路由光网络的研究重点就是通过波长资源的优 化配置使得网络的效率提高，网络的性能得到改善，这就是光网络的波长分配 问题。本章通过对光网络的波长资源进行定量数学分析，分别对单纤光网络和 多纤光网络归纳了不同的数学模型，并基于模型归纳各种不同的波长分配算法。 最后对业务量仿真模型进行了概括，提出了一种自相似业务量模型的产生方法。 2 1 光网络的业务分类 2 1 1 光网络静态业务量 静态业务量是指类似于传统电路交换的网络业务量，业务连接固定，业务 量到达和持续时间相对稳定1 3 】。静态业务量通常理解为离线的业务量估算，一 般用于网络规划阶段，可以使用支持电路交换的静态r w a 算法，由于同时实 现业务需求的路由选择和波长分配计算时间较长，不适合应用于大型的网络， 因此在研究的过程中常常将其分为路由和波长分配两个子问题。对于路由子问 题，又可以分为路由搜索和路由选择两个步骤，前者为业务需求计算可达路由， 后者则按照一定的顺序为各业务需求选择一条适合的路由；对于波长分配子问 题，也可以分为搜索和选择两步，前者在业务路由上搜索可用波长，后者则根 据一定的规则在其中选择一个波长，在其上建立一个光通道。而这些决定的网 络结构参数( 逻辑度、对称性、最大波长数、最大跳数) 也是拓扑优化配置的 基础。在解决静态r w a 问题时，最终目标是得到一个满足需求的逻辑拓扑。 2 1 2 光网络动态业务量 动态业务量是指类似于传送分组型业务的网络业务量，业务连接不固定， 分组随机到达，分组大小不固定，服务持续时间不固定【3 】。因为分组业务和电 7 浙江工业大学硕士学位论文 路业务有着本质的区别，所以在光层网络的优化目标和优化策略方面存在明显 不同。解决动态业务量问题可以使用支持分组交换的动态r 1 瞩，a 算法，对应算 法设计的核心是解决均衡网络业务量的问题，所以相应的算法之间性能的比较 也是在均衡业务量，改善优先级等方面的比较。在进行r w a 算法设计时要考 虑以下因素： 成本因素：因为对于分组交换业务，可以看作业务需求是来源于电层而不 是光层，此时业务需求不再是以单一波分信道的容量为单位，其容量的差别很 大且变化频繁。因此对于支持分组业务的光传送网，不可能在所有的业务节点 对之间都建立光的通路。如何在满足业务需求的情况下，建立相对少的光通路， 从而降低光发射器、光接收器等器件的成本，是必须考虑的一个重要因素。 拥塞因素：由于分组交换业务具有突发性，对于平均分组业务强度较大的 节点对，更容易出现分组发生拥塞的情况，因此动态r w a 设计时，应该尽量 多分配光通道给分组业务强度较大的节点对，从而提高网络的吞吐量，改善网 络业务非均匀分布时的性能。 业务因素：对于动态的分组业务量，各种r w a 算法最终都可以计算网络 的拥塞概率，对于业务容量变化很大的节点，如何自适应地动态地分配网络资 源都会影响到最后网络的拥塞情况。同时由于网络之中各种业务量的优先级也 不尽相同，所以在考虑公平性的基础上，要对特殊需求的业务量分配更多的网 络资源来保证其性能。业务量因素对r w a 算法的影响，可以直接通过波长分 配算法来改善，也可以通过把业务量因素转换成路由算法中的路由代价函数来 改善，比如可以使用波长使用率作为路由的代价函数，用最短路由计算即可得 到一条相对均衡的连接路由。 2 2 单纤光网络的波长分配问题 本文所指的单纤光网络是指在光网络中有物理连接的两个光节点之间为双 工单纤或者单工的一对光纤。在没有特殊说明的情况下，本文提到的光网络不 含有波长转换器。单纤波长分配问题在已有的文献中通常描述为根据已知路由 按需要分配波长，使得网络的拥塞概率最小或者建立的光通道数最大。因为单 纤光网络不存在同波长信道分离，所以不存在均衡信道容量的问题。 2 2 1 单纤光网络数学模型 2 2 1 1 整数线性规划模型 整数线性规划是一种线性优化方法，是在一系列以线性方程为约束条件的 基础上求得某个线性函数的最大化或者最小化。单纤光网络的波长分配问题可 以通过整数线性规划模型进行求解，其计算目标是使网络中拥塞最小、波长需 8 堑坚三些查兰堡主堂垡丝苎 求最小。 波长分配问题的约束可以描述为： 1 整个网络拓扑结构g 中，共享一个物理链路的必须使用不同的波长。 2 单纤的波长总数为矿。 3 每条光通道必须满足波长一致性条件( 无波长转换器) 。 4 在拓扑结构中g 中，每个节点的收发器数目相同即有相同是逻辑度。 5 每个节点的业务量是守恒的，即流入一个节点和流出这个节点的流量相 等。 下面我们对整数线性规划( m i l p ) 进行数学描述i s ) 。部分标识符定义如下： 乃表示节点i 到节点，之问动态到达的分组数据业务量； b 表示节点i 到节点j 之间建立的光通道数目； 表示节点f 到节点，之问光通道的最大跳数； c r 表示节点i 到节点，之间占用波长_ i 的光通道； c ( ，州) 表示节点f 到节点 ，之间占用从，到m 链路上的波长七的光通道。 这里我们设定的优化目标是使网络拥塞概率最小化，即 m i n 丑。= m a x , ，v i ，j 。其约束条件的数学描述为： 1 逻辑度约束条件：z 和r 。分别表示节点i 的发送器和接收器。 i 壹屯墨 弦1 2 流量约束条件：每个节点的业务量是守恒的，即流入一个节点和流出这 个节点的流量相等。 乃，穹，k o , v i ，j ( 2 - 2 ) 九九。，v f ， ( 2 3 ) 乃= 口 v f ，j ( 2 - 4 ) 筏 0 ( 2 1 0 ) 絮孚( 如) 2 w ( 2 - 1 1 ) m 哆( l ) p = 肘破( 刁) ( 2 一1 2 ) 比例模型求解网络效率的最大值可以使用遗传算法来计算最优解，比例模 型本身是对整数线性规划模型的一个优化，放宽了接收器和发送器数量的限制， 同时增加了对路由上的选择，使得计算的复杂度大大降低。特别对于规则网络 模型( 比如4 4 的网格型网络) ，在最小跳数相对统一的情况下，求解将变得 非常简单。但是对于不规则网络，当网络本身需要建立光通道的节点对又比较 复杂的时候，计算求解难度仍旧会很大。 2 2 2 单纤光网络的动态波长分配算法 单纤光网络的波长分配问题是一个n p c 问题，对于实际运用中需要采用启 发式算法来解决。各种启发式算法都是借鉴一般的数学模型，然后根据网络的 特殊情况有针对的提出算法。在单纤光网络中启发式算法大致分为基于统计概 率的波长分配算法，基于分集波长重用的波长分配算法和基于波长图的波长分 配算法。 2 2 2 1 基于统计概率的波长分配算法 基于统计概率的波长分配算法是把网络中波长资源的信息进行统计，然后 按照指定的原则进行分配波长。这种算法方法简单，但是统计全网资源的计算 时间复杂度比较大。根据对全网信息的依赖程度大致可以分为以下几类： 随机分配算法( r a n d o m ，r a n d o m w a v e l e n g t h a s s i g n m e n t ) ：首先搜索所有 波长的集合，找出可用波长集，再从中随机选择波长分配给光通道。这种算法 简单，所有波长被选中的概率一样，并且对不需要知道整个网络的状态信息。 首次命中( f f ，f i r s t f i t ) 算法：将所有波长编号，按编号从d , n 大的顺序 搜索可用波长，最先找到的那个可用波长被分配给光通道。与随机分配法相比， f f 算法不必搜索全部波长，而是找到可用波长就停止，计算量更小，分配速度 浙江工业大学硕士学位论文 也较快。f f 算法也不依赖整个网络的状态信息。 最大使用( m u ，m o s t u s e d ) 算法：首先统计全网中所有波长的使用率， 然后优先选择使用率最大的可用波长。这种算法有利于