（信号与信息处理专业论文）ip+over+wdm网络的联合优化路由算法研究.pdf

重庆邮电大学硕十论文摘要 摘要 口技术简单灵活，具有良好的扩展性和智能性，而w d m 技术则提供了巨大的 带宽，己成为传送网中最主要的传输技术，因此i p o v e r w d m 的应用与发展势在必 行。但是i po v e rw d m 独特的两层结构，以及g m p l s 强大的路由信令功能及其在 统一控制平面上的应用，使得传统的路由和波长分配算法已不能满足网络发展的要 求，i po v e rw d m 网络中的联合路由算法因此成为研究的重点之一。本文主要对 i p g m p l so v e rw d m 网络对等模型下的联合路由优化问题进行研究。 文章首先介绍了i p g m p l so v e rw d m 技术的相关研究背景，讨论了在 i p g m p l so v e rw d m 网络中实现联合路由策略需要具备的条件。接着对球层和 w d m 层的路由算法进行了详细描述。根据w d m 网络中的分层图模型提出了适用 于i p g m p l so v e rw d m 网络中算法研究的集成辅助图模型，然后在该模型上对联 合路由算法中的三种l s p 建立策略( m c p ，m t a ，i o l f ) 进行比较，并讨论了当 节点对间存在多条虚链路时的三种处理方案( m i n b f ，m a x b f ，f f ) ，同时分析了带 宽碎片和瓶颈链路造成的网络阻塞问题。在以上分析的基础上，提出了一种以代价 函数来实现网络资源分配的联合优化路由算法。最后进行了仿真验证。仿真结果表 明：1 ) m c p 算法较好的处理了l s p 建立过程中对m 层和w d m 层路由的取舍策略。 2 ) m i n b f 有效的降低了带宽碎片对网络阻塞的影响，提高了后续业务请求的连接成 功率。3 ) c i r 实现了口层和w d m 层两层信息的综合考虑，控制了带宽碎片和瓶颈 链路造成的阻塞，能够优化网络资源利用，承载更多连接请求，更有效的减少网络 阻塞率。 总体来看，本文主要贡献点如下： 在改进的集成辅助图上，提出了基于光路造价和负载均衡的l s p 建立策略 m c p ，为虚拓扑和物理拓扑在l s p 建立的优先权问题上提供了一种有效的 解决方案。 针对联合路由的优化，提出了最小带宽优先法m i n b f 来减少带宽碎片的影 响，同时设计了预处理机制来控制瓶颈链路，减少网络阻塞率。 基于上述机制，提出了一种新型的联合优化路由算法，即c i r 基于代价匠 数的联合路由算法。该算法综合考虑了网络拓扑结构和对等模型中两层网 络的资源利用信息，通过调整c i r 设定的代价函数使光路代价值最优，从 而解决瓶颈链路和波长碎片带来的资源浪费问题。 关键词：i p g m p l so v e r w d m ，联合路由，阻塞率，带宽碎片 重庆邮电大学硕士论文 a b s t r a c t a b s t r a c t i pt e c h n o l o g yo f f e r s h i g hf l e x i b i l i t y a n d i n t e l l i g e n c e ，a n d w d mp r o v i d e s t m p r e c e d e n t e dl e v e l so f b a n d w i d t hs c a l a b i l i t y , s ot h ea p p l i c a t i o na n dd e v e l o p m e n to fi p o v e rw d mi si m p e r a t i v e d u et ot h es p e c i a la r c h i t e c t u r eo ft w o - l a y e ri ni po v e rw d m n e t w o r k , t o g e t h e r 诚t l lg m p l s sp o w e r f u lr o u t i n ga n ds i g n a l i n gf u n c t i o n sa n dn l c i m p l e m e n t a t i o ni nt h eu n i f i e dc o n t r o lp l a n e ，i tm a k e st h et r a d i t i o f t a lr 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 ) c a l ln o tb em a t c h e d s ot h e1 r ( i n t e g r a t e dr o u t i n g ) a l g o r i t h r ni s t h eh o ts p o ti ni p g m p l so v e rw d mn e t w o r k t h i sp a p e rm a i n l ya i m sa tr e s e a r c h i n g h o wt oo p t i m i z et h ei ra l g o r i t h mi ni p g m p l so v e rw d mn e t w o r kf o rp e e rm o d e l t h i sp a p e rf l r s t l yi n t r o d u c e st h eb a c k g r o u r l do fr e s e a r c h i n go nt h ei po v e rw d m n e t w o r k , a n dd i s c u s s e st h er e q u i r e m e n t sf o rt h et e r m st oc a r r yo u ti ra l g o r i t h mo ni t , t h e n g i v e st h ed i f f e r e n c eo fr o u t i n ga l g o r i t h mb e t w e e ni pl a y e ra n dw d ml a y e r b a s e do nt h e i m p r o v e di a g ( i n t e g r a t e da u x i l i a r yg r a p h ) m o d e lf r o ml a y e r e d - g r a p h , t h r e el s p e s t a b l i s h i n gs t r a t e g i e s ( m c p , m t a , i o l f ) a n dt h r e ev i r t u a ll i n ks e l e c t i n gs c h e m e s ( m i n b f , m a x b f , f f ) a r ec o m p a r e d , a n di n c l u d i n gt h eb l o c k i n gp r o b a b i l i t y ( b p ) c a u s e db y b a n d w i d t hf r a g m e n ta n db o t t l e n e c kl i n k a tl a s t , b yt a k i n gt h e s ed i s c u s s i o n sa b o v ei n t o o p t i m i z a t i o no ft h en e t w o r kr e s o u r c e s ，an o v e li ra l g o r i t h mi ni p g m p l so v e rw d m n e t w o r k si sp r o p o s e d ，c a l l e dc i r ( i e ，c o s t - b a s e di n t e g r a t e dr o u t i n g ) t h es i m u l a t i o n r e s u l t ss h o wt h a t ：1 ) t h ep r i o r i t yb e t w e e ni pl a y e ra n dw d m l a y e ri nm c ps t r a t e g y p e r f o r m a n c e sb e s to ft h e m 2 ) m i n b fs c h e m ec a nr e d u c en e t w o r kb pe f f e c t u a l l y , a n d m a k et h el a t er e q u e s t sp r o b a b i l i t yo fs u c c e s sh i g h e r 3 ) c i rh a saf u l lo v e r v i e wo fl p l a y e ra n dw d ml a y e r , d e c r e a s e st h ed i s a d v a n t a g eo fb a l l d w i d t hf r a g m e n ta n db o t t l e n e c k l i n k i tc a l lo p t i m i z et h en e t w o r kr e s o u r c eu t i l i z a t i o nt oa c c e p tm o r ec o n n e c t i o nr e q u e s t s a n dr e d u c et r a f f i cb pe f f i c i e n t l y t h ec o n t r i b u t i o n so ft h i sp a p e ra r ea sf o l l o w i n g ： t h r o u g hi m p r o v e di a mm o d e l ，t h el s pe s t a b l i s h i n gs t r a t e g y - m c pb a s e do nt h e c o s to fl i g h t p a t ha n dl o a d i n gb a l a n c ep o l i c yi sp r o p o s e d ，w h i c hp r o v i d e sa l l e f f e c t i v es c h e m eo np r i o r i t yb e t w e e ni pl a y e ra n dw d m l a y e r i no r d e rt oo p t i m i z ei ra l g o r i t h m ，m i n b f ( m i n i m a lb a n d w i d t hf i r s tp o l i c y ) i s s u p p o s e dt or e d u e et h ep r o b l e mo fb a n d w i d t hf r a g m e n t , a n dt h ep r e p r o e e s s i n g s y s t e mi sd e s i g n e dt od e a lw i t hb o t t l e n e c kl i n k t h e yb o md e c r e a s et h en e t w o d | 【 i i 重庆邮电大学硕士论文 a b s t r a c t b 只 c o n s i d e r i n ga l lo ft h ed i s c u s s i o n s ，t h i sp a p e rp r o p o s e s a l li n t e g r a t e dr o u t i n g a l g o r i t h mn a m e dc i r f o ri p g m p l so v e rw d mn e t w o r k s ，w h i c hc a l lt a k ei n t o a c c o u n tt h en e t w o r kt o p o l o g ya n dr e s o u r c eu s a g ei n f o r m a t i o nb o mo ni pa n d 、v d ml a y e r s f o c u s i n go nt h ep r o b l e m so fb o t t l e n e c ka n db a n d w i d t hf r a g m e n t , a c o s tf u n c t i o no fl i g h t p a t hi no u ra l g o r i t h mi sd e s i g n e d 嬲t h em a i ni m p l e m e n tt o s o l v et h e m i tc a nr e d u c et h en e t w o r kb l o c k i n gp r o b a b i l i t ya n dd e p l o yn e t w o r k r e s o u r c ee f f i c i e n t l yb yt h em i n i m u mc o s tv a l u e k e yw o r d s ：i p g m p l s o v e r w d m ，i n t e g r a t e dr o u t i n g ，b l o c k i n gp r o b a b i l i t y , b a n d w i d t hf r a g m e n t i i i 重庆邮电人学硕士论文第一章绪论 1 1 研究背景 第一章绪论 近年来，传统话音业务的年增长率只有5 一1 0 ，而以i n t c m e t 为代表的数据 业务的年增长率达到2 0 0 p 3 0 。数据通信业务量持续高速增长最直接的动力来色 i n t e m e t 业务量的持续指数增长。口网络通信业务量的爆炸式增长已成为世界注目的 焦点和推动全球信息业发展的主要力量。为了提高通信系统的性价比和经济有效性， 满足不断增长的电信和i n t e m e t 业务的需求，如何提高通信系统的带宽( 系统容量： 便成为焦点【1 1 1 2 。因此随着p 数据业务的急剧增长，必然需要一种全新的能够提供 大容量、长距离传送能力的、适合p 业务特点的经济型承载网络来解决传统数据网 络所面临的上述问题。与此需求相对应，目前蓬勃发展的波分复用( w d m ) 传输 技术与其它传输技术相比具有明显的优势，因此采用w d m 网络承载数据业务( p o v e rw d m ) 的技术应运而生。w d m 网络是由光网络的节点和连接节点的单纤或多 纤光缆构成，不同波长的光信道复用在同一根光纤中传输，其通信是面向连接通信， 通信双方在通信之前需要首先建立一条光路。所谓光路，是在具有光交叉连接设备 ( o x c ) 的w d m 网络中，为了把数据从源端传到目的端，必须在光层上建立连接， 这就需要在二者间建立一条路径，并且在路径上的各条链路上找到一条空闲波长， 这样的一条路径称为光路( 1 i g h t p a t h ) 。 i po v e rw d m 也叫光因特网或光口网【3 j 。在i po v e rw d m 网中，高性能路由器 通过光a d m 或w d m 藕合器直接连至w d m 光纤，光纤内各波长是链路层互连的。 高性能路由器取代传统的基于电路交换概念的a t m 和s d h 电交换与复用设备，成 为关键的统计复用设备，用作主要的交换= 选路设备，由它控制波长接入、交换、选 路和保护。 i po v e rw d m 能够简化网络的设备，它的体系结构简单，降低了管理的复杂性， 减少了功能的重叠。它的最大优势在于w d m 拥有巨大的带宽潜力，w d m 具有若 干个波长信道，很容易兼容不同性质的业务，做到多业务融合，它还可以利用保护 光纤上的空闲带宽吸收突发业务量。另外口层和w d m 层都具备各自的保护，恢复 功能，可以将它们综合在一起，实现快速，高效的保护恢复功能。 1 2i p 层与光网络的智能结合发展状态 基于w d m 技术的光传送网已在世界范围内引起了广泛关注。由于p 是目前通 重庆邮电大学硕士论文第一章绪论 信业务的主要增长点，而且i p 业已经成为公认的未来通信的统一平台，因此，建设 基于口的宽带通信骨干网采用何种技术路线，即p 网络的核心设备如何支持物理 层中的光纤通信技术，成为通信技术界议论的热点。历史上曾出现过多种不同的解 决方案【4 】，但是大家都一致认为，简化i p 层到光层的适配过程是未来的发展趋势。 其协议层次如图1 1 所示。 图1 1i p o v e r o p t i o n s 其中i po v e r a t m ，i po v e rs d h 和i po v e rw d m 这三种技术最为关注【5 j 。 i po v e ra t m 以及i po v e rs d h 都是在已广泛应用的技术基础上提供对i p 业务的 传输，但它们的最初设计目标不是针对口业务。随着光网络技术的进步，在光层上 实现类似于s d h 中分插复用器a d m ( a d d d r o pm u l t i p l e x e r ) 和数字交叉连接器 d x c ( d i g i t a lc r o s sc o n n e c t s ) 功能的光分插复用器o a d m ( o p t i c a la d d d r o p m u l t i p l e x e r ) 和光交叉连接器o x c ( o p t i c a lc r o s s c o n n e c t ) 设备已经出现，使w d m 具有了灵活的组网能力和带宽提供能力，从而使w d m 取代s d h 直接承载i p 流量 成为可能，并且为i po v e rw d m 网络突破上述局限性提供了技术基础。 与i po v e r a t m 相比，a t m 网在综合传送各种业务时是最优的，但对m 业务而 言，a t m 不是最优的。a t m 在网络工程设计方面有高度灵活性，易于支持v p n 和 各种服务类别。a t m 在流量工程方面也有很强的能力，它允许我们为不同的业务类 型建立“清晰 的通道，根据业务负荷、拥塞及其它情况提供各种链路，但付出的 代价是复杂性。a t m 的另一不利因素是由于s v c 建立时间长而损失了带宽利用率。 因为s v c 的建立时间比网络转接时间长，在其建立时间内要在s v c 上传送的数据 必须缓存到s v c 建立之后，故在此期间即使网上有容量，也无法用来传数据。随着 带宽越来越大，s v c 建立时间所代表的空闲带宽也就越大，甚至超过了原来要传的 数据量。因此，如与兆兆比路由器相比，a t m 过于复杂，在吞吐量方面又没有特别 改善，那么在大型骨干网中i po v e ra t m 就没有优势了。如果主导业务是i p ，那么 a t m 网只能增加复杂性，使网络提供者在管理方面增加成本。因此，直接把路由器 2 第一章绪论 和w d m 光纤相连的i p o v e r w d m 网就变得更有利了。 与i po v e rs d h 相比，s d h 的一大优点是它的恢复能力，但需要复杂的链路管 理。在i p o v e r w d m 网中，s d h 层中的复杂链路管理就未必需要。因为保护和恢复 能力是因特网固有的分布式存活能力的一部分，因此如果i p 层能单独承担存活能 力，就不需要在因特网结构底下再设一层存活能力。另外，当初开发s d h 网的一 个愿意是使整个网络同步，更加牢靠。现在利用g p s 也能经济地达到同步目的。而 且随着i p 技术的渗透，网络变得越来越能容忍定时差错，因此可以省去s d h 这一 中间层。在光因特网中，让路由器直接与w d m 波长相连有一很大的优点，即路由 器可在光纤环的两侧使用几个波长，对i p 业务进行负荷分担，有可能使因特网链路 的带宽利用率加倍，而增加的成本很少。万一光纤断路，可以把疋业务放到一条能 用的光纤上去送，或者放到另一条完全不同的路径上去重新选路，由于因特网数据 具有自相似性，故光纤断裂的后果在数据网环境下不如在传统电信网环境下严重， 可以通过流量控制、缓存和重新选路等技术来加以补偿。此外，在i po v e rw d m 网 络中，路由器可以建立不对称的收发波长，来平衡出入网络的业务。s d h 网在设胡 时总是考虑收发业务是平衡的，因此对不对称业务它不是最优的。 与基于电路交换的w d m 光交换网相比，在i p o v e rw d m 网中，处于网络边缘 的路由器，而不是处于网络和新的光交换设备将成为对分组进行选路和交换的主要 智能设备。所以将来引入光交换时不必使用过于复杂的交换技术，可缩短光电路的 建立时间，网络管理也相对简单。 通过以上的论述及比较分析，我们可以发现，在高性能、带宽的m 业务方面， i po v e rs d h 技术由于去掉了a t m 设备，投资少、见效快而且线路利用率高。因而 就目前而言，发展高性能口业务，i po v e rs d h 是较好选择。而i po v e r a t m 技术则 充分利用已经存在的a t m 网络和技术，发挥a t m 网络的技术优势，适合于提供高 性能的综合通信服务，因为它能够避免不必要的重复投资，提供v o i c e 、v i d e o 、d a t a 多项业务，是传统电信服务商的较好选择。对于i po v e rw d m 技术，它能够极大地 拓展现有的网络带宽，最大限度地提高线路利用率，并且在外围网络以干兆以太网 成为主流的情况下，这种技术能真正地实现无缝接入。应该说，i po v e rw d m 代表 了宽带p 主干网的明天。 1 3i po v e rw d m 网络中的路由策略问题 由1 2 节的分析可知，虽然a t m 、s d h 技术在现实中已经得到了广泛的应用， 但是它们不是适配i p 层和w d m 层最合适的选择，因此，为了简化传统口网络的 选路过程从而实现快速有效的转发，i e t f ( i n t e m e te n g i n e e r i n gt a s kf o r c e ) 建议采 3 重庆邮电大学硕士论文 第一章绪论 用m p l s ( m u l t i p r o t o c o ll a b e ls w i t c h ) 技术将到达网络边缘路由器的业务分组映射 为不同的转发等价类( f o r w a r d i n ge q u i v a l e n c ec l a s s ，f e c ) ，并贴上相应的标签，然 后通过显式路f l ：l ( e x p l i c i tr o u t i n g ) 建立的标签交换路径( l a b e ls w i t c hp a t h ，l s p ) 进 行转发。由于w d m 网络中的光路建立问题与上述l s p 建立问题具有许多共同之处 特别是为了在i po v e rw d m 网中能够采用统一的控制平面以及信令协议，i e t f 结 合光网络的具体特点对m p l s 进行扩展，提出更通用的g m p l s ( g e n e r a l i z e d m u l t i p r o t o c o ll a b e ls w i t c h i n g ) 协议族1 6 j ，从而可以将i po v e rw d m 网络中各层的 控制平面最终融合为一体。目前，基于g m p l s 的i po v e rw d m 网络体系正在日趋 成熟。 在i p g m p l so v e r w d m 网络中，i p g m p l s 层负责向终端用户提供具有q o s 保证( 支持流量工程t e ，s i a l ，v p n ，a a a 等功能) 的丰富的数据业务和多媒体应用， 而w d m 传送层则负责为i p 层提供r o b u s t ，s c a l a b l e 并且功能强大的传送网络功能， i p g m p l so v e rw d m 网络根据控制平面的集成度不同分为重叠模型( o v e r l a y m o d e l ) 和对等模型( p e e rm o d e l ) ，还有一种过渡的增强模型( a u g m e n t e dm o d e l ) r l t s l 。 由于i p g m p l so v e rw d m 是正在形成中的网络体系架构，对其资源分配策略了解 和研究还不是很多，尤其在对等模型下，由于到达边缘路由器的每个业务流主干 ( t r a 伍ct r u n k ) 可能有不同的带宽要求，也就是说在为这些业务请求建立l s p 时 并不是恰好都占用一个波长粒度( g r a n u l a r i t y ) 的带宽，这将导致已经建立的光路 上可能会剩余一些带宽资源。这些带宽资源可以被后续的l s p 使用。在源路由器为 每个业务流主干建立l s p 时，既可以通过ip 层面建立在已经存在的虚拓扑上( 先 前已经建立的光路) ，也可以在w d m 层为它新建立一条光路，定义为i po v e r w d m 网中的联合路由( i n t e g r a t e dr o u t i n g ) 问题。这与传统的r w a 问题大不一样。在传 统的r w a 算法中，往往将m 层的路由问题与w d m 层的波长路由问题分开解决， w d m 层的波长路由仅仅建立虚拓扑，提供给i p 层建立m 路由使用。对全网的资 源利用率而言，这种分离的方法无疑是不足的。联合路由策略可以很好的弥补上述 缺陷。结合i p 层和光层的拓扑资源信息的动态综合路d d ( i n t e g r a t e dr o u t i n g ) 还是一 个新兴的领域例，因此本文将对其中涉及到的网络体系，路由策略以及优化方案进 行研究。这里的动态是指无论p 业务、标签交换路径( l a b e ls w i t c h e dp a t h ，l s p ) ， 还是由此形成的对于光层的光通道( l i g h t p a t h ，或称为光路) 的连接请求均是动态到 达的。 1 4 论文结构 全文主要研究了i p g m p l so v e rw d m 网络中的联合路由策略，集中解决了该 4 重庆邮电大学硕士论文第一章绪论 网络模型下动态选路和波长分配问题，以及针对带宽碎片和瓶颈链路等考虑因素对 网络阻塞率影响的优化问题。 本文后续各章的结构安排如下： 第二章，描述了w d m 光网络基础知识及其3 个抽象描述模型，在后面章节将 对这些模型进行扩展，并在其基础上进行算法描述。概述了w d m 网络中的路由和 波长分配( r 、张) 问题的基础知识，给出了已有的常见r w a 算法。 第三章，讨论了在m ，g m p l so v e rw d m 网络的对等模型下，基于集成图辅助 模型进行动态选路和波长分配所面临的一些关键问题，提出了种新的以光路代价 函数为调节因子的联合路由优化策略即c i r ( i e ，c o s t - b a s e di n t e g r a t e dr o u t i n g ) 。构 建了i p g m p l so v e rw d m 网络中的集成辅助图模型，详细描述了基于该模型的l s p 建立过程和虚链路选择策略，还分别讨论了带宽碎片和瓶颈链路对整个网络阻塞性 能的影响，并基于光路代价函数给出了解决方案。 第四章，利用o p n e t 仿真工具对i p g m p l so v e rw d m 网络中联合优化路由 策略的有效性进行了仿真验证，分别对l s p 建立机制，虚链路选择策略和c i r 优化 算法的仿真性能进行了分析和讨论。 第五章对全文进行总结并描述了未来的工作。 5 重庆邮电大学硕士论文第二章i p 与w d m 网络中路由问题的研究 第二章i p 与w d m 网络中路由问题的研究 路由问题是从源端到目的端的路径选择问题。在交通运输网与通信网的规划与 运营中都要遇到这一问题。在数据通信网中，路由问题可具体描述为：为发送端发送 的数据包在网络中寻找合适的通路，使其顺利到达接收端。 由于口和w d m 都有自己的路由机制，在波分复用i p 光网络中，如何将二者 有机结合，提高网络的性能，是目前m 光网络急需解决的一个问题。本章在考察目 前的p 路由与波长路由的基础上，为进一步探讨i po v c rw d m 综合路由问题奠定 基础。 2 1i p 路由 2 1 1i s o 模型 在计算机网络刚刚出现的时候，网络通信还没有统一的标准，数据通信仅能在 同一厂商生产的计算机之间进行。为了打破这一网络互联的限制，国际标准化组织 ( i n t e r n a t i o n a lo r g a n i z a t i o nf o rs t a n d a r d i z a t i o n 简称i s o ) 于2 0 世纪7 0 年代末制定了“开 放互联( o p e ns y s t e m si n t e r c o n n e c t i o n ，简称o s l ) 模型鼽 1 0 1 。这一模型的提出，是为 了帮助不同的网络设备制造商生产出可互操作的网络设备，使不同厂商的计算机用 户之间可以进行数据通信。o s i 模型从逻辑上把所有互联的开放系统划分为功能上 相对独立的七层： 第七层：应用层( t h ea p p l i c a t i o nl a y e r ) ，提供用户界面； 第六层：表示层( t h ep r e s e n t a t i o nl a y e r ) ，对数据进行封装、压缩和转换； 第五层：会话层( t h es e s s i o nl a y e r ) ，在通信过程中，对网络设备间的对话进行 控制； 第四层：传输层( t h et r a n s p o r tl a y e r ) ，提供端到端的连接服务； 第三层：网络层( t h en e t w o r kl a y e r ) ，提供网络逻辑地址，负责路由选择操作： 第二层：数据链路层( t h ed a t al i n kl a y e r ) ，将数据包映射进数据帧，匹配物理 层的特性，并供错误检测与纠错； 第一层：物理层( t h ep h y s i c a ll a y e r ) ，规定网络物理接口特性，提供透明的比特 流传送服务。通过分层，将复杂的网络操作划分为一些易于管理的功能层，在实际 应用中，如要完善其中一层的功能，只需在这一层进行改造，而不必改动所有的功 能层，方便了网络设备的开发与互联。 6 重庆邮电大学硕士论文第二章i p 与w d m 网络中路由问题的研究 2 1 2i p 路由的原理 i p 是一种可路由的协议，口路由的操作是属于o s i 模型中第三层( l a y e r3 ) 的功 能。在i n t e m e t 中，每个网络设备或主机都有一个唯一的母地址，在通信过程中， 一个i p 分组包含了有效信息载荷和信头开销。礤分组的信头开销包含路由该数据 包的必要信息( 源地址与目的地址等) ；有效载荷承载着实际要传输的数据。p 业务 流在所有途经的路由器中都要进行分析处理，然后将业务分组传送到下一路由器， 直至到达目的地。 i p 路由是建立在下层提供的网络拓扑之上的，第三层之下的网络虚拟拓扑在传 统的口路由模式下，使用的是静态设置方式，如静态虚电路、静态波长通道等，它 们是在网络规划或配置时设定好的。对于不同规模与要求的口网络，在实际运行时， 路由的需求有静态与动态之分，这些功能完全由口层( 第三层) 来控制。如果要运行 动态i p 路由，系统只在m 层执行动态寻由操作。这时，m 层根据网络链路的带宽， 路由的跳数、时延等动态地选择路径，完成数据的传输。常见的动态p 路由协议 有：o s p f , b g p , i g r p 等【l l 】。 。 2 2w d m 网络中的r w a 算法 w d m 网络是由光网络的节点和连接节点的单纤或多纤光缆构成，不同波长的 光信道复用在同一根光纤中传输，其通信是面向连接通信，通信双方在通信之前需 要首先建立一条光路。所谓光路，是在具有光交叉连接设备( o x c ) 的w d m 网络中， 为了把数据从源端传到目的端，必须在光层上建立连接，这就需要在二者间建立一 条路径，并且在路径上的各条链路上找到一条空闲波长，这样的一条路径称为光通 道( 1 i g h t p a t h 或c l e a rc h a n n e l ) 。也就是说，当客户层业务到达时，w d m 光网络需要 在业务接入点间选择一条路由，并在该路由的每条链路上分配波长，建立光传送通 道以传送业务，为客户层到达的业务选择路由并分配波长的问题称为路由和波长分 配( 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 问题。 由于光网络承载的业务需求，特别是p 业务，正呈爆炸式增长，而日前光网络 的可用资源( 波长、光纤等) 有限，如何在有限资源网络中为业务选择合适的路出和 分配优化的波长将直接影响到网络的传输效率；同时，目前w d m 网络中的几个研 究热点问题：虚拓扑重构、业务量疏导、多播、抗毁网络等都要涉及到r w a 问题 的求解l l z j 。因此，路内和波长分配( i m ，a ) 算法成为重要的研究课题，人们在此基 础上提出了很多算法来解决这个问题【l 引。 7 重庆邮电大学硕士论文第二章l p 与w d m 网络中路由问题的研究 2 2 1 路由选路策略 由于r w a 问题是n p 完备问题，随着网络资源的增加计算时间呈现指数增长； 因此通常将r w a 问题分解为成路由子问题和波长分配子问题。路由选路策略是为 了给新到达的业务请求选择一条优化的物理路由，是连接请求得到满足，并使网络 资源得到充分的利用。可以分为【l 列： 1 ) 固定路由选路策略( f i x e dr o u t i n g ) 这是一种最简单直接的选路策略，该策略是在业务到达前，为任意两个节 点对确定一条固定的可用路由。一般采用最短路算法( 比如d i i l 哑r a 算法和 b e l l m a n - f o r d 算法) 为每个节点对分配固定不变光通道。该策略简单、速度快，但 容易导致网络中的瓶颈链路的产生，阻塞率上升，并且不具有容错功能。 2 ) 固定的备用路由选路策略( f i x e d a l t e r n a t e dr o u t i n g ) 该策略是对任意两个节点对间预先确定多条备用路由，并按一定的优先级 顺序排列。排在最前面的为主路由，其它则为备用路由。当业务到达时，则从多条 备用路由中依优先级顺序选择一条最优路由。 目前确定备用路由常用的几类方法如下： a 以某种算法( 例如d i j k s t r a 算法) 计算两节点间的最短路由、次短路由 和第三短路由等作为备用路由； b 基于链路或节点无关的路由； c 设定最大跳数，跳数小于这个值的路由都作为备用路由。 固定备用路由可使网络的请求阻塞率大大降低，文献 1 3 】中的参考文献也提 到了在一定网络条件下，具有两个备用路由的网络阻塞率明显低于具有全波长转换 能力的固定路由，也显示了路由子问题在r w a 算法中的重要性。 3 ) 自适应的备用路由选路策略 该策略可以预先确定节点对间的多条备用路由，然后根据网络的状态动态 确定备用路由的优先级，或者根据网络状态确定备用路由，再从中选择最优路由。 自适应的备用路由选路策略可以利用网络的当前状态，在计算路由时融入一些 特定参数，如：波长转换能力权重、网络各链路负载等【1 4 】，所以阻塞率较低，但时 间复杂度较高，因此在采用适应性路由方案时应当综合权衡性能和效率 2 2 2 静态路由和波长分配算法 w d m 光网络中的业务请求一般为静态和动态。在静态业务请求时，是针对已 有业务量进行优化，目标为在满足已有业务量下，尽量减少网络资源的开销，如： 波长数、光纤数等；或者为在已有网络资源情况下，尽量满足更多的业务请求。这 8 重庆邮电大学硕士论文第二章i p 与w d m 网络中路由问题的研究 时的r w a 问题也称为s t a t i cl i g h t p a t he s t a b l i s h m e n t ( s l e ) 问题。在动态业务请求 时，优化目标为尽量降低请求的阻塞率。 静态r w a 是对于一组预先确定的需要建立的光连接请求选择路由并分配波长。 由于其静态特性，对算法的时间效率要求不高，主要侧重在优化程度上。作为一个 n p 完备问题，可以将其分解为路由子问题和波长分配子问题，但对于小规模网络， 也可以统一进行优化，将路由和波长分配统一解决。如： 1 ) 整数线性规划( i n t e g e rl i n e a rp r o g r a m m i n g ，i l p ) ，i l l 整数线性规划方法 是一种线性性能优化方法。同时考虑路由和波长分配同时考虑，结果更加优化，但算 法时间复杂度高，解i l p 方程属于n p 完备问题，只能在有限范围内得出解答，适 用于较小规模的网络； 2 ) 基于分层图模型的算法，一种启发式算法，采用前面提到的分层图模型， 将路由和波长分配统一考虑，由于在分层图上每一层代表一个波长片面，因此 r w a 问题被简化为在分层图上寻找源节点到目的节点的最小代价通路的问题，资源 优化效果较好，适用于较小规模的网络。 同时人们也提出了一些启发式算法将其分解为路由和波长分配来求解，简 单分为： 1 ) 定序路由、波长分配算法，将业务按某种策略排序，按序确定业务的路由、 波长，在波长分配时可以采用动态r w a 中的算法； 2 ) 图着色算法，这类算法考虑到了选路和波长分配在r w a 问题求解过程中 的不可分性，采取了先分拆求解，之后统一迭代的思路，优化性能很好，但是时间 复杂度高，对于大型网络很耗时间。 2 2 3 动态路由和波长分配算法 动态r w a 是在实时业务条件下的通路选择和波长分配优化问题。此时的业务 请求是随机到达，并在持续一段时间后自动撤销。通常将其分解为路由和波长分配 子问题通过启发式算法求解，以优化业务请求阻塞率为目的，路由算法前面已经介 绍，这里主要介绍动态波长分配算法l 1 3 1 1 ”】。 设定网络图g ( e ，l ) 及算法相关定义，e 为顶点集，l 为链路集合；考虑多光纤 情形，每个光纤支持w 个波长，每条链路f 根光纤。刖切：通路p 所包含的链路宾 合；州卅：链路l 在波长彳上的剩余信道数，任意通路p 在波长彳上的可用信道数为 只( p ，五) = m i n t e l ( | 口) 厶( ，力) ；p 为新到达业务请求对应的路由，4 ( p ) 为通路p 上的 可用波长集，“( pj 代表与p 有共享链路，且具有可用信道的通路集合；d ( a ，召) 为 指示函数，当a = b 时取值为1 ，否则取值为0 ；u j 为单位阶跃函数，当a 0 时 9 重庆邮电大学硕士论文第二章i p 与w d m 网络中路由问题的研究 取值为l ，否则取值为o 。 瓶颈链路：针对波长号 ，对某通路上的所有链路所包含的 ，波长数进行排 序，其最小值为本通路上的 可分配波长数，包含的以波长数等于该最小值的链路 为本通路上的瓶颈链路，有可能有多个。 1 ) 随机分配( r a n d o mw a v e l e n g t ha s s i g n m e n t ：r ) 随机分配波长算法的思路是：首先遍历所有波长，确定所选路由上的可用波长 集合，从可用波长集合中随机等概率地选取一个波长作为波长选择结果。它不 考虑目前的各链路上的各波长的使用情况，所有对网络的性能改善不是很明显，但 其实现简单，时间复杂度低，可表示为o ( w ) 。 2 ) 首次命中( f i r s t f i t ：f f ) 首次命中波长分配算法的思想为：对所有波长统一编号，可以按波长频率大小 顺序编号，也可以随机编号，并选择可用波长集中的波长号最小的波长来建立光路。 同随机分配一样，也不考虑网络的资源使用情况，但其阻塞性能优于随机分配，时 间复杂度的最差情况才与随机分配相同，为o ( w ) 。 3 ) 最小使用( l e a s t - u s e d ：l u ) 最小使用波长分配算法思想为：统计目前各波长的使用情况，将波长按波长使 用率升序排列，在已定路由上按序检查波长，直到找到一个可用波长。由于每次都 选择使用率最低的可用波长，此算法趋向于使各波长的使用率平均。由于这样的趋 势，路由跳数较多的光路上更容易的产生了瓶颈链路，而只有路由跳数小的光路较 容易被建立成功，使业务在建立光路时更容易被阻塞，其性能低于随机分配算法， 时间复杂度也大得多，为：o ( w l f ) ，因而很少在实际中采用。 4 ) 最大使用( m o s t u s e d ：m u ) 最大使用分配算法思想与最小使用正好相反，在统计了波长使用情况后，选择 使用率最高的可用波长。它的性能要优于l u ，将业务请求尽量汇集在部分波长上， 为后来到达请求保留一些未经常使用的波长，时间复杂度为：o ( w l f ) 。 5 ) 最小乘积( m i n - p r o d u c t ：m p ) 最小乘积分配算法主要针对多纤网络设计，在单纤中相当于首次命中。根据网 络目前状态计算出业务已选定路由上各段链路的各波长已被占用的信道的乘积，并 选取具有最小乘积的空闲波长建立光路。令为波长j 在链路l 上的已使用信道数， 则选择波长力满足：mi n 丌d ， 式(