（通信与信息系统专业论文）wdm网络负载均衡路由算法及其用于保护的研究.pdf

摘摘要随着信息化社会的发展，宽带视频、多媒体等业务的需求不断增长，特别是i n t e r n e t 网业务的爆炸式发展，迫切要求扩大广域骨干通信网的容量。光纤上的波分复用技术( 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 ) 以它的传输容量大，对高层协议透明，以及易于扩展等优点而倍受青睐。因此，利用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 ) 技术的光传送网将是下一代高速广域骨干网的最具竞争力的候选者。随着o x c ( o p t i c a lc r o s sc o n n e c t ，光交叉连接设备) 、o a d m ( o p t i c a la d d d r o pm u l t i p l e x e r ，光分插复用设备) 技术的不断成熟，基于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 网络中引入业务量工程技术。业务量工程技术就是按用户的要求把业务量映射到网络的物理拓扑上，从而达到优化网络资源利用率、避免拥塞和提高网络可靠性的目的。在光传送网中采用基于g m p l s 的控制平面来实现业务量工程时，网络操作者可以依据一定的策略赋予业务流主干( t r a f f i ct r u n k ) 不同的业务量工程属性，然后根据这些属性为业务进行选路并分配资源。本文研究的负载均衡算法就是业务量工程在采用了m p l s 技术的w d m 网络中的实现。目的是提高网络的资源利用率，降低业务阻塞率，提高网络可靠性。在第二章研究了i po v e rw d m 网中基于链路负载均衡的资源分配算法。通过分析影响网络的链路负载均衡的因素，比如源一目的节点间的最大流，通过每条链路的最大流，源一目的节点间的路径数目，通过每条链路的路径数目，以及链路的剩余容量等，提出了快捷动态路由算法f d r a 和关键性链路路由算法c l r a ，通过仿真，与最小跳算法( m h a ) 、最宽最短路径( w s p ) 算法、最小干扰路由算法( m i r a ) 相比较，提出的两种算法在业务阻塞率、资源利用率以及重路由性能方面都有很好的效果。第三章研究负载均衡在网络保护中的应用。尽管m p l s 具有强大的业务量工程能力，但在i po v e rw d m 网中进行保护设计时，还很少有文献涉及到这一点。摘要基于此，为了在网络中出现单链路故障时1 0 0 地保护受影响的业务，同时保证链路负载分布的平衡性。提出了一种考虑链路负载平衡的共享通路式保护算法。在为动态到达的请求进行波长分配及路由选择时，考虑了以下几点：( 1 ) 仔细考虑业务请求的带宽需求，力争大大降低残留在网络内的带宽碎片：( 2 ) 路由器能以较细的粒度处理业务及波长转换的能力；( 3 ) 链路负载分布的平衡性；( 4 ) 保护通路的资源共享。仿真结果表明，算法在链路负载分布的平衡性、( 给定业务需求量时的) 业务丢弃特性，( 业务动态到达时的) 网络平均阻塞性能均要优于通常采用的d i j k s t r a 算法。本文的第四章详细介绍了仿真和计算工作，对仿真程序进行了简要的介绍，给出本文提出的各种算法的流程图。最后是全文总结。关键词：业务量工程，链路负载均衡，w d m 网络，m p l s 技术，网络保护1 ia 廿b l k ，、l ia b s t r a c tw i t ht h ed e v e l o p m e n to fi n f o r m a t i o ns o c i e t ya n dt h ee x p l o s i v eg r o w t ho fi n t e r n e t ，t h er e q u i r e m e n t so fn e t w o r kc a p a c i t yh a v ei n c r e a s e dd r a m a t i c a l l y , w h i c ha r ep r o m o t i n gt h ec o n s t r u c t i o no fb r o a d b a n dt r u n kn e t w o r k 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 sap r o m i s i n ga p p r o a c ht h a tc a ne x p l o i tt h ee n o r m o u sb a n d w i d t ho ft h eo p t i c a lf i b e r as i n g l ef i b e rc a nb ee m p l o y e df o rm u l t i p l ed a t as t r e a m ss i m u l t a n e o u s l y a l l - o p t i c a ln e t w o r k se m p l o y i n gt h ec o n c e p to fw d ma n dw a v e l e n g t hr o u t i n ga r ec o n s i d e r e da st h et r a n s p o r tn e t w o r k sf o rt h ef u t u r e w i t ht h ed e v e l o p m e n to fo x ca n do a d m ，t h eo p t i c a lt r a n s m i s s i o nn e t w o r kb a s e do nw d mi sn o tc o n f i n e dt op o i n t t o p o i n tt r a n s m i s s i o n s o , t h e r em u s tb et h ea s s i g n m e n ta n do p t i m i z a t i o no fn e t w o r kr e s o u r c eo nd e m a n d t h i sm e a n sa l l o c a t i n gn e t w o r kr e s o u r c ea c c o r d i n gt ou s e r sd e m a n d ，c o n f i g u r i n gn e t w o r kr e s o u r c ea sr e a s o n a b l ea sp o s s i b l e ，a n dd e c r e a s i n gt h en e t w o r kb l o c k i n gr a t e a f t e ra l l ，w em u s tu s et r a f f i ce n g i n e e r i n gt os o l v et h e s eq u e s t i o n s t r a f f i ce n g i n e e r i n gm a p st r a f f i ci n t on e t w o r k sp h y s i c a lt o p o l o g ya c c o r d i n gt ou s e r sc o m m a n d ，f o ro p t i m i z i n gn e t w o r kr e s o u r c e sa l l o c a t i n g ，a v o i d i n gn e t w o r kc o n g e s t i o na n di n c r e a s i n gn e t w o r kr o b u s t n e s s at r a f f i ct r u n kc a nb ec h a r a c t e r i z e db ya d m i n i s t r a t o ri no p t i c a lt r a f f i ce n g i n e e r i n gw i t hg m p l s ，a n da na t t r i b u t eo fat r a f f i ct r u n ki sap a r a m e t e ra s s i g n e dt oi tw h i c hi n f l u e n c e si t sr o u t i n ga n dr e s o u r c ea s s i g n m e n t l o a db a l a n c i n ga l g o r i t h mr e s e a r c h e di nt h ep a p e ri st oi m p l e m e n tt r a f f i ce n g i n e e r i n gi nt h ew d mn e t w o r kw h i c hu s e sm p l st e c h n o l o g y t h ea i mi st oi n c r e a s et h er e s o u r c eu t i l i z a t i o no fn e t w o r k ，r e d u c et r a f f i cb l o c k ，e n h a n c er e l i a b i l i t yo fn e t w o r k i nc h a p t e r2 ，w es t u d yr e s o u r c ea s s i g n m e n ta l g o r i t h m so fl o a db a l a n c i n go fl i n k s t oa n a l y z et h ef a c t o r so fi m p a c t i n gl o a db a l a n c i n go fl i n k s ，w h i c hi si n c l u d i n gt h en u m b e ro fr o u t e sb e t w e e ns o u r c en o d ea n dd e s t i n a t i o nn o d e ，t h en u m b e ro fr o u t e st h r o u g he v e r yl i n k ，t h em a x i m u mf l o wb e t w e e ns o u r c en o d ea n dd e s t i n a t i o nn o d e ，t h em a x i m u mf l o wt h r o u g he v e r yl i n k ，t h ef r e eb a n d w i d t ho fe v e r yl i n ka n ds oo n ，w ep r e s e n tt h ef a s td y n a m i cr o u t i n ga l g o r i t h m ( f d r a ) a n dt h ec r i t i c a ll i n kr o u t i n ga l g o r i t h m ( c l r a ) s i m u l a t i o nr e s u l t ss h o wp r e s e n t e da l g o r i t h m si nt h ep a p e ra r eb e t t e rt h a no t h e ra l g o r i t h m si nr e j e c tr a t i oo ft h et r a f f i cr e q u e s t sa n dp e r f o r m a n c eo fa b s t r a c tr e r o u t i n gt h et r a f f i cr e q u e s t sw h e nal i n ki sf a i l u r e ，e s p e c i a l l yi nc o m p u t i n gt i m ec o s t i nc h a p t e r3w es t u d ya p p l i c a t i o no ft r a f f i ce n g i n e e r i n gi nt h ep r o t e c t i o no fn e t w o r k s t oo b t a i np a r t i a li n f o r m a t i o no fn e t w o r k sr e s o u r c e s ，w h i c hi n d i c a t e sw h a tf r a c t i o no fe a c hl i n k sb a n d w i d t h ，i sc u r r e n t l yu s e db yw o r k i n gp a t h s ，a n di su s e db yp r o t e c t i o np a t h s ，i sf e a s i b l ei ni po v e rw d mn e t w o r k su s i n gm p l st e c h n o l o g y i nt h i sp a r t i a li n f o r m a t i o ns c e n a r i o ，w ep r e s e n tan e wd y n a m i cr o u t i n ga l g o r i t h mo fp r o t e c t i o nd e s i g nf o ri po v e rw d mn e t w o r k s f o rw o r k i n gp a t h ss e l e c t i o n ，t h ea l g o r i t h mm a k e sat r a d e o f fb e t w e e nt h er o u t i n gc o s t sa n dt h ec o r r e s p o n d i n gt r a n s m i t t i n gl e n g t h a sf o rp r o t e c t i o np a t h ss e l e c t i o n ，at r a d e o f fb e t w e e nt h es h a r i n go ft h ep r o t e c t i o np a t h sa n dt h ea s s o c i a t e dt r a n s m i t t i n gl e n g t hi sm a d e t h u st h ed e v e l o p e dr o u t i n gs c h e m ei sb e n e f i c i a lt oh a v eag o o dl i n kl o a db a l a n c i n g s i m u l a t i o nr e s u l t ss h o wt h a tt h ed e v e l o p e ds c h e m ep e r f o r m sw e l li nt e r m so fp e r f o r m a n c em e t r i c ss u c ha s ( 1 ) t h en u m b e ro fr e j e c t e dr e q u e s t s ( 2 ) l i n kl o a db a l a n c i n go fn e t w o r k ，( 3 ) a v e r a g eb l o c k i n gp r o b a b i l i t yo fn e t w o r k i nc h a p t e r4w ei n t r o d u c es i m u l a t i o np r o f f a m st h ep r e s e n t e da l g o r i t h m si nc h a p t e r2a n dc h a p t e r3 a n dw ed r a wf l o wc h a r t so fa l g o r i t h m s f i n a l l y , w es u m m a r i z et h ep a d e lk e y w o r d ：t r a f f i ce n g i n e e r i n g ，l o a db a l a n c i n go fl i n k s ，w d mn e t w o r k ，m p l st e c h n o l o g y , n e t w o r kp r o t e c t i o n间峪子表b g pc l r ae g pf d r a简略字表b o r d e rg a t e w a yp r o t o c o l边际网管协议c r i t i c a ll i n kr o u t i n ga l g o r i t h m关键性链路路由算法e x t e r n a lg a t e w a yp r o t o c o l外部网关协议f a s td y n a m i cr o u t i n g a l g o r i t h m快速动态路由算法g m p l sg e n e r a lm p l si e r fi g pi pi s pl s pm h am i r am p l s通用多协议波长交换i n t e r n e te n g i n e e r i n g t a s kf o r c e因特网工程任务组i n t e r i o rg a t e w a yp r o t o c o l s内部网关协议i n t e m e tp r o t o c o li n t e m e ts e r v i c ep r o v i d e rl a b e ls w i t c h i n gp a t h因特网协议因特网服务提供商标签交换路径m i n i m u mh o pa l g o r i t h m最小跳算法m i n i m u mi n t e r f e r e n c er o u t i n g a l g o r i t h m 最小干扰路由算法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多协议标签交换o a d mo p t i c a l a d d d r o pm u l t i p l e x e r光分插复用器o s p f0 x co p e ns h o r t e s tp a t hf i r s to p t i c a lc r o s sc o n n e c t丌放最短路径优先光交叉连接简略字表0 0 s月伟爿s d ht ew d mw s pq u a l i t yo fs e r v i c e s服务质量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路由与波长分配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同步数字序列t r a f f i ce n g i n e e r i n g业务量( 流量) 工程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 i d e s ts h o r t e s tp a t hx最宽最短路径独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。签名：趁丝警日期：如e 年广月巧日关于论文使用授权的说明本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后应遵守此规定)签名：逭谧量导师签名：孝卑氏日期：山“年月二日第一章绪论第一章绪论随着经济的发展和科技的进步，计算机的普及和i n t e r n e t 业务的庞大，造成了传输网络的扩大和传输数据的剧增，使得网络数据传输在骨干网中采用传输容量巨大的w d m 技术以及使用各种价格昂贵的网络设备，而网络运营商为了降低成本，不可能无限制地扩大网络规模，希望能充分利用网络资源，并且提高网络运行的可靠性。从这个角度出发，本文针对骨干传输网进行业务量工程路由算法和网络保护算法的研究，以使得在充分利用网络资源的同时，提高网络运行的可靠性。1 1w d m 技术的发展随着全球“信息高速公路”的发展，以及宽带视频、多媒体、网络游戏等业务的日益兴起，特别是i n t e r n e t 业务的快速增长，对广域骨干网的带宽提出了越来越高的要求。由于光纤具有巨大的潜在带宽( 接近5 0 t b s ) ，同时还具有成本低、信号失真和衰减低( 可达0 2 d b k m ) 、功率要求低以及空间要求低等优，因此，目前在骨干网中大多使用光纤链路来传输数据。但是，由于传统的s d h s o n e t( 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 s y n c h r o n o u so p t i c a ln e t w o r k ) 技术只能以特定的传输速率( 如2 5 g b s ) 在光纤中的单个波长信道上传输数据，此时要增加传输带宽只能单纯依靠提高单波长的传输速率来实现。s o n e t s d h 技术需要电的时分复用( t d m ：t i m ed i v i s i o nm u l t i p l e x i n g ) ，而电领域的处理速度由于受量子理论的限制，提高的速度有限，目前认为4 0 g b s 是单个波长最高实用化的速率，这些都使传统的s o n e t s d h 技术越来越不能适应数据网络发展的要求。光的波分复用( 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 技术可以将每根光纤的巨大带宽分成许多互不重叠的波长信道，每个信道都可以并行、异步和高速地按当前电子处理数据的极限速率来传输数据，从而可以充分利用光纤的巨大带宽，提供丰富而且廉价的带宽资源。因此，使用光分插复用器电子科技大学硕士学位论文( o p t i c a la d d d r o pm u l t i p l e x i n g ，o a d m ) 和光交叉连接设备( o p t i c a lc r o s s c o n n e c t ，o x c ) 的w d m 光传送网( o p t i c a lt r a n s p o r tn e t w o r k ，o t n ) 将逐渐在骨干网中占据主导地位。经过近十年的发展，w d m 技术已经取得了巨大的突破，目前在单光纤上的容量可达6 4 t b s 甚至1 6 t b s ，在单根光纤上的波分复用数可达1 0 2 2 个。欧洲的i 一2 l网络中，采用w d m 技术使一条路由上的通信容量高达1 0 0 0 t b s 。目前点到点的w d m传送技术已经成熟，并且已经大量在长途干线和海底光缆系统中使用。全球实际铺设的w d m 系统己超过5 0 0 0 个，一些产品，如日本h i t a c h i 的a m n 6 0 0 0 、l u c e n t的w a v e s t a ro l s 4 0 0 g 以及n o r t e l 的m u l t i w a v e l e n g t ho p t i c a lr e p e a t e r ( m o r )p l u ss y s t e m 等都可以处理高达3 2 0 g b s 或4 0 0 g b s 的数据传输率。自1 9 9 5 年以来，美国各大长途电话公司已经在其干线网络中逐步引入w d m 设备，到1 9 9 9 年底其干线上已经基本实现w d m 传输。我国从1 9 9 7 年开始引入w d m 设备，目前光通信的发展已经初具规模。我国在多条省级光缆干线上已经使用了w d m 技术，在2 0 0 0 2 0 0 4 年间又采用w d m 技术对我国“八纵八横”光缆网进行改造、扩容和升级。2 0 0 0 年1 0 月2 8 日，中国网通开通宽带高速互联网c n c n e t ，该工程一期工程己建成8 4 9 0 公里，1 0 6 个中继站，1 7 个节点，贯通了东南部的1 7 个重点城市，网络总传输带宽高达4 0 g b s 。采用w d m 技术虽然可以充分利用光纤的潜在带宽，从而能够极大地提高线路的传输能力，但是，由于目前的传送网中，光技术仅仅局限在点到点的应用，在节点上采用的是电时分复用技术，还需要进行光一电转换，这大大限制了网络的速度和灵活性。另外，目前电子交换的发展已逼近电子速率的极限，为了摆脱电层交换瓶颈的制约，引入光交换技术已成为必然趋势。光交换技术分为光路交换( o p t i c a lc i r c u i ts w i t c h i n g ) 、光突发交换( o p t i c a lb u r s ts w i t c h i n g ) 和光分组交换( o p t i c a lp a c k e ts w i t c h i n g ) 三种。由于受到成本和技术方面一些问题的制约，如缺少光随机访问存储介质以及对光分组头的同步比较困难等，直接在全光域中完成分组级交换的实用化还需待以时日。目前受到青睐的是光路交换和光突发交换。相对光分组交换和光突发交换而言，基于光路交换的w d m 光传送网更容易实现，而且其特有的波长重用( w a v e l e n g t hr e u s e )能力也使它具有良好的可扩展性。因此采用光交叉连接设备( o x c ) 和光分插复用器( o a d m ) ，提供可调度光路的w d m 光传送网被认为是下一代i n t e r n e t 的极具竞争力的候选者，这也是本文的研究对象。从9 0 年代以来，w d m 光传送网一直是网络界的研究热点。早在8 0 年代末期，2竹一音按协欧洲就已经在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 ) 等。9 0 年代以来，美国d a r p a ( 国防部高级研究计划局) 资助了全光网( a o n ) 、光网技术联盟( o n t c ) 、多波长光网络( m o n e t ) 、国家透明光网( n t o n ) 等几个大的研究项目，建立了一系列光传送实验网，如连接美国新泽西和华盛顿的m o n e t ( 多波长光网络) 等，用于实验和验证各种新技术。加拿大政府资助在1 9 9 7 年开始建设加拿大研究和教育i n t e r n e t骨干网c a + n e t 3 ，其中采用的高速路由器和w d m 设备直接相连的i po v e rw d m 结构，开创了光互联网( o p t i c a li n t e r n e t w o r k i n g ) 建设的先例。现在已经在建设c a + n e t 4 。日本则是以大公司的投资建设为主，如n t t 建立的o p n ，国际标准化组织i t u t 也正在积极制定有关光传送网的建议。从1 9 9 8 年丌始，w d m 光联网开始进入示范和实用化推广阶段。我国的一些研究机构也开展了光传送网的研究工作。“七五”和“八五”期间，中国“8 6 3 ”主题开展了光交换基础技术的研究工作，在“十五”8 6 3 计划中又开展了光通信技术专题研究。1 9 9 8 年5 月，国家自然科学基金委员会又发布了重大项目“w d m 全光网基础研究”，由我国的一些知名高校，如清华大学、北京大学等，以及其它一些单位共同承担，这些单位在各自的领域都取得了可喜的成果，这无疑将为我国全面推广w d m 光传送网技术奠定坚实的理论基础。1 9 9 9 年6 月，国家高技术项目智能计算机主题、光电子主题和通信主题联合提出实施“中国高速信息示范网( c a i n o n e t ) ”研究开发项目，建立一个基于光因特网技术的高速信息网实验环境，为以光因特网技术为代表的先进网络技术的研究、开发和测试提供一个实验平台。2 0 0 5 年初，华为、北邮承担的8 6 3 重大项目“自动交换光网络分层路由技术”在深圳通过验收。华为公司的a s o n 曾通过国际性的互通测试，参加的厂商还有思科、北电、阿尔卡特、c i e n a 、富士通、马可尼和s y c a m o r e 等。2 0 0 5年，烽火科技和上交大承担的8 6 3 项目“自动交换光网络节点设备研制与系统”也通过了验收。此外，在8 6 3 支持下，清华大学的“大规模自动交换光网络试验平台”通过了鉴定，中兴通讯公司也研制了a s o n 的节点设备。从上面的介绍可以看出，随着光分插复用器( o a d m ) 和光交叉连接设备( o x c )的出现，己经使w d m 技术从最初的点到点传输技术逐渐转变为种网络技术。基于w d m 技术的光传送网已在世界范围内引起了广泛关注。w d m 宽带光联网已经成为继s o n 电联网之后的又一次新的光通信发展高潮。而且近年来在w d m 传输技术、吉比特以太网以及吉比特太比特交换路由技术等方面的长足进步，都为基于i p3电子科技火学硕士学位论文业务的w d m 光联网的发展创造了极好的条件。1 2i po v e rw d m 网络资源分配问题由于i po v e rw d m 相关技术的标准化工作尚在完善之中，到底最终会采用何种技术路线以保证其q o s 性能、抗毁性能及可升级性能等等，还值得研究。对于网络资源分配问题，是i po v e rw d m 网中的热点研究问题，下面予以具体讨论。目前，对于i po v e rw d m 网络资源分配问题的研究大致可以分为两大类【2 1 ：一是基于光层的方法，即给定一组光路连接请求，通过波长选路和波长分配算法( 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 d m 信道的建立拆除，并提供一定级别的保护恢复能力，另外，该层还可能引入另外的帧定位功能，以取代s d h 类型的帧定位；另一种是基于m p l s 的l a m b d a 交换方法，此方法最大的长处在于其具有较好的业务量工程能力，这也是本论文研究的重点。不管采用何种方法，都需要考虑：如何保证业务的q o s 性能；如何节省带宽资源；如何保证网络业务量工程能力；可升级性( s c a l a b i l i t y ) ：网络生存性问题等等。下面对这两种方法分别予以讨论。1 2 1 基于光层的方法光层的主要任务是解决上层应用所产生的波长信道请求，执行路由计算并在w d m 网络中预留相应的资源。这里，有两个问题是密切相关的【3 】：逻辑拓扑设计和r w a 问题。前者类似于数据网络的逻辑拓扑( l o g i c a lt o p o l o g y ，也叫虚拓扑，v i r t u a lt o p o l o g y ) 设计问题，即对于给定的网络物理拓扑，业务需求矩阵，节点资源及其它限制等，设计出网络不同节点间的连接关系。而r w a 问题要解决的是光节点之间的信道建立。由于逻辑拓扑指定了将要建立的信道，常常关注的是连接的长期性，在某种意义决定了r w a 采用的机制。r w a 问题按业务类型的不同，可以分为静态业务的r w a 问题和动态业务的r w a 问题。对于静态类型( s t a t i c ) 的业务，由于节点间的所有连接请求已事先知道，所以光路的选路和波长分配可以用离线( o f f 一1 i n e ) 方式完成。典型的优化目标可以是：在物理拓扑和所有连接请求给定的情况下，使用最少的波长或光纤建立光路，以满足所有4弟一覃箱化的连接请求。也可以是：在物理拓扑和网络中可用的波长数给定的情况下，建立尽可能多的光路以使连接请求的阻塞率最低。在解决后一优化目标时，可能会引发“公平性”问题，即光路跳数越短的连接请求相比跳数越长的光路连接请求，可能会有更低的阻塞性能。静态r w a 问题还可以进一步分成两大类，一是支持电路型的静态r w a 问题，该类型的业务需求矩阵给出了每对节点问需要支持的光路数，可以用整形线性规划( 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 ) 的方法来描述。典型的目标函数可以是全网使用的波长数最少等。由于静态r w a 的光路建立问题己被证明是n p - c 问题，所以对于规模较大的网络，常常借助于启发式算法( h e u r i s t i c ) 来得到问题的次最优解。并且，同时解决路出和波长分配问题一般比较困难，因此，通常的作法是将r w a 问题拆分成选路子问题和波长分配予问题，然后分别解决。静态选路算法一般分为两类：固定选路( f i x e dr o u t i n g )算法和备用选路( a l t e r n a t er o u t i n g ) 算法，前者在为给定的源一目的节点的连接建立光路时，通常使用d i j k s t r a 算法或b e l l m a n - - f o r d 算法根据最小代价准则( 例如光路跳数最小) 得到最短路径( s h o r t e s t p a t h ) 。故实现起来较为简单，网络的路由一旦确定以后，网络的性能主要受波长分配算法的影响。而备用选路算法在为一对节点对之间建立光路时，考虑的是多条路由，然后，根据链路资源状况和优化目标选择其中的一条作为待建立光路的路由。显然，该路由方法比固定路由算法灵活得多，可以取得更好的网络性能；另一类是支持分组型交换业务的逻辑拓扑设计问题。该类型的业务需求矩阵存放的是节点对间归一化的平均分组业务强度。为了更好的支持上层业务，最具代表性的作法是使用逻辑拓扑直接支持i p 分组流，分组业务流在抵达目的节点前尽可能远地在光领域中传送，只在必要的时候才通过中间节点进行电领域的交换或路由，如源一目的节点之间没有光路直接相连。中间节点需要完成：( 1 ) 光一电转换，将光路信号转换成电层的分组或信元：( 2 ) 电层的路由或交换能力，如配置i p 路由器；( 3 ) 电一光转换，将分组转发到另一条光路上。由于i p 业务的高突发( b u r s t y ) 性或称为自相似性，业务分布常常出现较大的变化，因此，更需要研究动态业务的设计问题。动态业务和静态业务的光路建立问题，在处理方法上有很大不同。这是因为，静态业务面对的连接请求事先已经知道，算法主要进行全局的优化和配置，因此可以采用离线方式。而动态业务面对的连接请求事先并不知道，算法在某一时刻确定的逻辑拓扑不一定适合或适用于另一时刻的连接请求。所以，基于离线方式的静态业务逻辑拓扑可以采用针对业务矩阵而求解的路由固定路由算法，而基于在线( o n l i n e ) 方式的动态业务的路由必须时刻关注网络的链路资源使用5电子科技人学硕士学位论文情况，宜采用白适应选路( a d a p t i v er o u t i n g ) 算法，即根据当前网络j 状态确定物理链路的代价并执行动态的最短路由算法以选择合适的路由。网络状态由当前正在处理的所有光路共同决定。在业务动态变化的环境，一个研究目标是如何使逻辑拓扑变更不太频繁，即保持逻辑拓扑在短时间内尽可能的相似性，使网络内正在接受服务的业务的损失被降低到一定程度。因此，有必要研究如何在光域和数据域之间如何快速有效的进行拓扑和资源利用信息的交互。r w a 算法按照控制方式来划分，还可以分为集中方式的r w a 算法、分布式的r w a 算法及采用混合( 分布式和集中式结合使用) 技术的控制方式。集中方式要考虑所有节点对的路出，因此资源的分配比较有效。但由于算法计算时间的限制，该方式只适用于网络规模较小，光路请求不太频繁的情况；与集中方式不同，分步式方式更关注的是当前节点对的连接请求的性能优化，常常采用最短径算法。由于不是从全局资源的状态考虑路由，因此不一定是资源有效的：混合方式弥补了这两种方式的不足。宏观地说，快速的、动态的连接请求宜采用分布式方法以减少计算时间的复杂度，当连接请求建立以后，出于资源利用的有效性，需要进行重选路由( r e r o u t i n g )时，则采用集中式的控制方式。目前，尚无标准化的r w a 算法，此问题可能会留给运营商来解决，亦即，只要制定相关接口标准及网络总体结构的标准化就够了。对于基于光层的方法，由于光节点需要有一套建立光路路由的机制。因此存在地址解析问题。对于规模较小的w d m 网络，采用简单的一级地址机制可能是足够的。然而，对于地域分布较大的大规模网络，可能需要多级地址。并且，由于w d m子网络可能属于不同的机构，每一个都有其自己的操作考虑，这就需要额外的多域管理，从而增加了协议的复杂性，也影响了网络的可升级性能。1 2 2 基于m p l s 的i a m b d a 标签方法为了解决基于光层方法存在的问题，同时也为了尽快解决运营商( 所架构的网络) 之间的可交互性( i n t e r o p e r a b i l i t y ) ，提出了基于多协议标签交换m p l s技术的方法一一l a m b d a 标签( 1 a b e l l i n g ) 。基于m p l s 的标记交换路由器( l a b e l s w i t c hr o u t e r ，l s r ) 节点使用分组标签在网络中建立标记交换通道( l a b e ls w i t c h e dp a t h ，l s p ) ，简化了转发和选路过程。l s r 节点检查分组上的标记值以确定必要的处理过程。m p l s 的标签交换路径l s p 路由可以通过两种方法确定：显式路由( e x p l i c i tr o u t i n g ，e r ) 和逐跳分配( h o p b y h o pa s s i g n m e n t ) 路由。l a m b d a 标签方法把m p l s 控制平台放在光w r o x c 设备上并6第一章绪论把这些设备视作m p l s 节点o l s r 节点，并对基于m p l s 的标签和w d m 波长信道进行扩展，从而允许m p l s 信令规划光路。这样，端到端的光路就等价于个离散粒度的l s p 一1 a m b d al s p 。0 一l s r 节点将标签分配“翻译”成相应的波长分配并利用本地的控制接口与w r o x c 设备建立光路。利用m p l s 技术，还能够进行光路规划及保护，因而包含了前述光层方法的主要功能。m p l s 方式封装的i p分组要么直接被发送，要么使用在电域进行监测的“子层( s u b l a y e r ) ”成帧，毋需要任何新的光层协议。另外，由于o - l s r 节点被分配了i p 地址，不存在前述光层方法的地址解析问题。可见，基于m p l s 的方法将数据层和光层更好地进行了整合( i n t e g r a t i o n ) ，能更好的利用网络资源拓扑信息，因而获得了更好的性能。当然，由于l a m b d a 标记方法是一个控制框架( c o n t r o 卜f r a m e w o r k ) ，现存的、传统的光路规划中存在的问题( 如算法复杂度) 在l a m b d a 标签方法中也有待于进一步研究，后续章节主要研究基于m p l s 技术的路由问题和保护问题。1 3 业务量工程在研究业务量工程之前，先给出几个定义。所谓流，就是将资源由一个地点传送到另一个地点。而流分析的问题主要是按照某种最优化标准( 时间最少、费用最低、路程最短或运送量最大等) 设计传送方案。业务量工程则是关注网络的性能评价和性能优化。它包含业务量的测量、描述、建模和控制的技术和科学原理的应用。具体实现是指将业务量映射到现有的网络物理拓扑上的一种行为。业务量工程( 或称流量工程) 是指为了平衡网络中的各个链路、路由器和交换机上的业务量，根据具体的数据业务量来选择路径的过程【4 1 。业务量工程可有效的增强网络的运行性能，它的目标是增加流量性能的同时优化网络资源，主要的性能目标包括：面向流量的性能指标( t r a f f i co r i e n t e d ) ：面向流量的性能指标包含流量的服务质量0 0 s 的一系列指标。在单一类型的尽力传输机制的因特网服务模型中，面向流量的性能目标主要包括：对分组丢失的最小化，对时延的最小化，对吞吐量的最大化和服务水平约定( s e r v i c el e v e la g r e e m e n t ，s l a ) 的实施。在这一业务模型中，使分组丢失最小化是最重要的性能目标。面向资源的性能指标( r e s o u r c eo r j