（通信与信息系统专业论文）动态变化业务量情况下wdm网络的设计方法研究.pdf

摘要 w d m 光传送网是下一代高速广域骨干网的最具竞争力的候选者，但是，w d m 网 络存在的一个重要问题是在w d m 网络上运行的业务量是动态变化的，这造成的结 果是晟初通过搭建光路设计好的光网络虚拓扑在新的业务量矩阵下它的性能如网 络平均权重路由跳数，网络负载均衡性，网络拥塞等性能指标都有可能下降，这 显然是各个网络运营商和网络用户所不能忍受的。 本文针对动态变化业务量情况下的w d m 网络设计方法划分为两个主要的研究 方向，第一个方向的研究出发点是可以在最初的虚拓扑设计过程中根据物理拓扑 情况设计出一种虚拓扑出来，该虚拓扑是负载均衡的，在这种虚拓扑上跑的业务 量矩阵特征只要存某种范围以内，无论它怎样动态变化，网络都不会出现拥塞， 但这种虚拓扑设计算法v l b s 的一个缺陷是它只能适用于同构网络，即每个节点所 拥有的容量大小都相等，在第二章中，本文提出了一种更通用的负载均衡的光网 络虚拓扑设计算法g v l b s ，该算法与传统的负载均衡算法v l b s 不同之处在于v l b s 算法只能适用于同构网络而g v l b s 算法既可以适用于同构网络，又可以适用于异 构网络，在本章中将给出了g v l b s 算法的的详细推导和数值分析。 第二个研究方向的研究出发点是我们最初在一个物理拓扑上按照一个业务量 矩阵设计出一个虚拓扑出来，随着业务量矩阵的动态变化，网络的性能指标可能 会下降，不再最优。针对这种情况，在第三章中，我们研究了降低平均权重路由 跳数的虚拓扑重配置算法，它参照新的业务量矩阵，当前的虚拓扑和物理拓扑情 况在某些约束条件下( 可以改变的光路条数) 进行虚拓扑的重配置，得到一个新的 虚拓扑使网络的性能指标( 单位业务量的平均路由跳数) 得到提高，在本章中作 者独立实现了该算法并着重考虑了该算法过程中尝试建立光路过程与找到待拆光 路组集合这两个过程的步骤细节，本章最后给出了该算法性能仿真和算法结果分 析。 我们通过虚拓扑重配置算法得到了一个新的虚拓扑，但新旧虚拓扑的过渡仍 然是一个很关键的问题，因为在新旧虚拓扑的过渡过程中会对上层的业务产生很 大的业务中断影响，因此找到一个合适的w d m 光网络拆建光路的信令顺序也是非 常必要和具有现实意义的，本文第四章我们对一种光网络虚拓扑过渡过程算法进 摘要 行了研究和算法实现，该算法可以给出一种合适的拆建光路的信令顺序，采用该 信令顺序进行虚拓扑过渡，需要直接拆掉正在工作的光路的条数将会显著减少， 从而显著提高了光网络虚拓扑重配置过程的性能，在本章中先详细的介绍了该算 法中五个重要步骤的细节与整体流程，最后给出了该算法性能仿真结果和分析。 在第五章中，动态变化的业务量形式从业务量矩阵变成了动态到达和离去的 源宿节点对的光路连接请求了，在这种业务量请求是动态到达和离去的情况下一 般采用单路径波长路由算法为光路连接请求找路，针对请求的业务量大小有可能 是多个波长的情况，本章提出了一种新的带保护的多路径波长路由算法来为动态 到达的光路连接请求找出和建立光路。先详细介绍作者所提出的该算法的步骤， 并对该算法进行仿真和与普通的单路径波长路由算法进行性能比较，最后可以看 出，该算法比起单路径波长路由算法相比确实可以提高网络的负载均衡性。 针对第二个研究方向中第三，四，五章动态变化业务量的w d m 光网络不同的 设计算法进行性能测试，在第六章中，作者使用v s n e t ，s t l 和b o o s t 开发出一个 w i ) m 光网络算法的仿真平台，作者首先介绍该仿真平台的总体框架，然后分别介绍 了在该框架下的各个模块设计实现和相关的核心代码。 关键词：w d m 光传送网动态变化业务量虚拓扑重配置负载均衡多路径路由 a b s t r a c t a b s t r a c t t h c r ei sa ni m p o r t a n tp r o b l e mf o rt h ew d mn e t w o r kw h i c hi st h et r a f f i co nt h e w d mn e t w o r ki sd y n a m i c a l l yv a r i a b l e a sar e s u l t i f t h et r a f f i co nt h ev i r t u a lt o p o l o g y h a sc h a n g e d ，t h ep e r f o r m e n c eo ft h en e t w o r ks u c ha sa v e r a g en t m a b e ro fw e i g h t e dh o p s ， t h et h r o u g h p u to ft h en e t w o r k ，t h ec o n g e s t i o no ft h en e t w o r kw i l ld e c l i n e ，o b v i o u s l y , t h i si sn o ta c c e p t a b l ef o rb o t ht h en e t w o r ka d m i n i s t r a t o r sa n dn e t w o r kc l i e n t s i nt h i st h e s i s ，t h er e s e a r c ho ft h ep l a no ft h ew d mn e t w o r ku n d e rd y n a m i c a l l y v a r i a b l et r a f f i cc a l lb ec l a s s i f i e di n t ot w om a i nd i r e c t i o n s t h eb e g i n n i n gp o i n to ft h e f i r s tr e s e a r c h d i r e c t i o n i s t h a t w e d e s i g na t y p eo f l o a d - b a l a n c i n g v i r t u a l t o p o l o g y w h i c h i si n s e n s i t i v et ot h et r a f f i c , s u c hp l a nm e t h o dh a sb e e np r o p o s e dw h o s en m t f l ei s v l b s ( v a l i a n tl o a d b a l a n c i n gs c h e m e n 0 ，t h ed i s a d v a n t a g eo f v l b si st h a ti tc a no n l y b ea p p l i e dt ot h eh o m o g e n e o u sn e t w o r ki nw h i c he a c hn o d eh a st h es a l n ec a p a c i t y , i n c h a p t e r 2 ，am o r eg e n e r a lv a l i a n tl o a d - b a l a n c i n gs c h e m e ( g v l b s ) h a sb e e np r o p o s e d ， t h ea d v a n t a g eo ft h eg v l b si st h a ti tc a l lb eu s e db o t ho nt h eh o m o g e n e o u sn e t w o r k a n dh e t e r o g e o u sn e t w o r k ，i nt h i sc h a p t e r , w ew i l lg i v et h ed e t a i ld e r i v a t i o np r o c e s sa n d n u m e r i c a la n a l y s i s t h eb e g i n n i n gp o m to ft h es e c o n dr e s e a r c hd i r e c t i o ni st h a tw ef i r s td e s i g na v i r t u a lt o p o l o g yf o rt h ep h y s i c a lt o p o l o g yu n d e ras p e c i f i ct r a f f i cm a t r i x ，f o raw h i l e ，t h e t r a f f i ch a sc h a n g e d ，t h en e t w o r kp e r f o r m e n c ew i l ld e c l i n e u n d e rs u c hc o n d i t i o n ，i n c h p a t e r3 ，av i r t u a lt o p o l o g yr e c o n f i g u r a t i o na l g o r i t h m1 ss t u d i e dw h i c hc a l ld e c r e a s e t h ea v e r a g ew e i g h t e dh o p s i tu s e st h en e wt r a f f i cm a t r i x ，c u r r e n tv i r t 2 1 a lt o p o l o g y s i t u a t i o na n dp h y s i c a lt o p o l o g ys i t u a t i o na si n p u t ，c o m p u t ean e wv i r t u a lt o p o l o g ya s o u t p u tu n d e rt h ec o n s t r a i n tw h i c hi st h en u m b e ro ft h ed i f f e r e n tl i g h t p a h t sb e t w e e nt h e o l da n dn e wv i r t u a lt o p o l o g i e si sn o tl a r g e rt h a nt h ep a r a m e t e rn r a n g e i nt h i sc h a p t e r , ih a v ei m p l e m e n t e dt h ea l g o r i t h mb ym y s e l fa n dat h o u g h f u l ls t u d yo ft w ok e y p r o c e d u r e s h a sb e e ns t u d i e da n dt h er e s u l to ft h ea l g o r i t h ms i m u l a t i o nh a sb e e n a n a l y z e d w ec a i l g e t an e wv i r t u a lt o p o l o g yb yt h ev i r t u a lt o p o l o g yr e c o n f i g m a t i o n a b s t r a c t a l g n r i t h m ，h o w e v e r , h o wt ot r a n s f e rt h eo l dv i r t u a lt o p o l o g yi n t ot h el l e wo n ei sa l s o v e r t yi m p o r t a n tb e c a u s et h et r a n s f e rp r o c e s sb e t w e e nt h eo l da n dn e wv i r t u a lt o p o l o g i e s w i l lh a v eg r e a ti n f l u e n c eo nt h et r a f f i co ft h eh i # e rl a y e r s ，t h et r a f f i co ft h eh i g h e r l a y e r sw i l lb ed i s t u r b e db yt h ed i r e c td e l e t i o no ft h ew o r k i n gl i g h t p a h s s o ，t of i n da p r o p e rs e q u e n c eo fd e l e t i o na n da d d i t i o n o ft h el i g h t p a t h si sv e r yi m p o r t a n ta n d m e a n i n g f u l i n c h a p t e r4 ，a no p t i c a ln e t w o r kr e c o n f i g u r a t i o np r o c e s sa l g o r i t h mh a s b e e ns t u d i e d ，b yu s i n gs u c ha l g o r i t h m ，ap r o p e rl i g h t p a t hd e l e t i o na n da d d i t i o ns e q u e n c e j w i l lb e 百v e i la n dt h en u m b e ro f t h el i g h t p a b t sw h i c ha r en e e d e dt ob ed e l e t e dd i r e c t l yi n t h er e c o n f i g u r a t i o np r o c e s sw i l lb eg r e a t l yd e c r e a s e da n dt h ep e r f o r m e n c eo ft h e r e c o n f i g u a r t o nw i l lb ei m p r o v e d i nt h i sc h a p t e gt h er e c o n f i g u r ep r o c e s sa l g o r i t h mh a s b e e nd e t a i l e da n di m p l e m e n t e d ，at h r o u 曲f u lt e s to ft h ea l g o r i t h mh a sb e e nc o n d u c t e d a n dt h er e s u l to f t h es i m u l a t i o nh a sb e e na n a l y s e d i nc h a p t e r5 ，t h ef o r mo ft h ed y n a m i c a l l yv a r i a b l et r a f f i ch a sb e e nc h a n g e df r o m t r a f f i cm a t r i xt od i f f e r e n ts o u r c ea n dd e s tc o n n e c t i o nr e q u e s t f o rs u c hk i n do f d y n a m i c a l l yv a r i a b l et r a f f i cr e q u e s t ，t r a d i t i o n a ls o l u t i o n i ss i n g l ep a t hw a v e l e n g t h r o u t i n ga l g o r i t h m ，i nt h i sc h a p t e r , an e wm u f f - p a t hw a v e l e n g t hr o u t i n gp r o t e c t i o n a l g o r i t h mh a sb e e np r o p o s e dw h i c hc a nb r i n gb e t t e rp e r f o r m a n c e si nt h el o a d - b a l a n c i n g o fo p t i c a ln e t w o r k ，t h en e t w o r kr o b u s t n e s s ，t h eu t i l i z a t i o ne f f i c i e n c yo ft h eb a c k u p r e s o u r c e ss u c ht h r e ea s p e c t s r e s u l t so ft h es i m u l a t i o no fe x p e r i m e n t a t i o na i m e da t c o m p a r i n gs i n g l ep a t hw a v e l e n g t hr o u t i n ga l g o r i t h ma n dm u l t i - p a t hw a v e l e n g t hr o u t i n g a l g o r i t h ma r ea n a l y z e d ，w h i c hf e t c h e so u tt h ec o n c l u s i o nt h a tm u l t i p a t hw a v e l e n g t h r o u t i n gp r o t e c t i o na l g o r i t h mc a ni m p r o v et h el o a d - b a l a n c i n gp e r f o r m a n c eo ft h ew d m n e t w o r k t ov e r i 句a n de v a l u a t et h o s et h r e ea l g o r i t h m si nt h ep r e v i o u st h r e ec h a p t e r s r e s p e c t i v e l y , a no p t i c a ln e t w o r ka l g o r i t h i ns i m u l a t o np l a t f o r mh a sb e e nd e v e l o p e db y u s i n gv s n e t ，s t la n db o o s t , i nc h a p t e r6 ，f i r s t ，w ew i l lb r i e f t h ef r a m e w o r ko ft h e p l a t f o r m ，s e c o n d ，t h ed e s i g n a t i o na n dd a t as t r n c t m - e so f d i f f e r e n tm o d u l e sw i l lb eg i v e n k e ? w o r d ：w d mt r a n s m i s s i o nn e t w o r k ，d y n a m i c a l l yv a r i a b l et r a f f i c ，v i r t u a lt o p o l o g y r e c o n f i g u r a f i o n ，l o a db a l a n c i n g , m u l t i - p a t hr o u t i n g 简略字表 w d m a t m i p s d h q a d m o x c o t n i s p f d m i l p s r l g v l b s 简略宇表 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 a s y n c h r o n o u st r a n s f e rm o d e i n t e r n e t p r o t o c o l 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 d p t i c a la d d d r o pm u l t i p l e x e r o p t i c a lc r o s sc o n n e c t o p t i e a lt r a n s p o r tn e t w o r k i n t e r n e ts e r v i c ep r o v i d e r f r e q u e n c yd i v i s i o nm u l t i p l e x i n g i n t e g r a ll i n e a rp r o g r a m m i n g s h a r e dr i s kl i n kg r o u p v a l i a n tl o a db a l a n c i n gs c h e m e g v l b sg e n e r a lv a l i a n tl o a d b a l a n c i n gs c h e m e r w a s d a s v t t a d l l r i p o s p f s t l b g l 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 s i m p l ed e s i g na l g o r i t h m s i m p l ev i r t u a lt o p o l o g yt r a n s i t i o n h l g a r i t h m d y n a m i cl i n kl i b r a r y r o u t i n gi n f o r m a t i o np r o t o c o l o p e ns h o r t e s tp a t hf i r s t s t a n d a r dt e m p l a t el i b r a r y b o o s tg r a p h1 i b r a r y 波分复用技术 异步传输模式 因特网协议 同步数字体系 光分插复用器 光交叉连接器 光传送蚓络 因特网服务提供商 频分复用 整数线性规划 共享风险链路组 v a l i a n t 负载均衡算法 通用的v a l i a n t 负载均 衡算法 路由与波长分配 简单设计算法 简单虚拓扑过渡算法 动态链接库 路由选择信息协议 开放最短路径优先 标准模板库 b o o s t 图形库 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。1 訇专 签名：豸觉日期：2 。占年乡月踟 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名；辑导师签名：监 日期：函乜年6 月子日 第一章绪论 1 1w d m 光网络概述 1 1 1w d m 技术简介 第一章绪论 全球网络用户的大量增长和大容量业务的发展，使得带宽需求量成线性增长， 如何有效地增加骨干网的传输能力成为众多i s p 服务提供商( i n t e r n e ts e r v i c e p r o v i d e r ) 必须面对的重要问题。虽然目前的骨干网多数己使用光纤链路来传输数 据，但是传统的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 l n e t w o r k ) 技术只能以特定的传输速率( 如2 5 g b i t s s ) 在光纤中的单个波长通道上 传输数据，单纯依靠增加单波长传输速率的方法，例如使用更高速的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 ) 技术，将碰到诸如因传输速率逼近电层处理极 限而使设备成本迅速增加等问题。然而，一根光纤可提供的理论传输带宽约为 5 0 t h z ，可见光纤的容量还远远没有得到充分利用。w d m 波分复用( 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 ) 实质是光域上的f d m 频分复用( f r e q u e n c yd i v i s i o n m u l t i p l e x i n g ) 技术，每个波长通路通过频域的分割实现，每个波长通路占用一段 光纤的带宽。w d m 技术使用独立的电比特流调制各自的光载波，经复用后在同一根 光纤上传送。由于它们的光谱成分不同，在大气传输中是各不干扰的。在接收端 使用解复用器( 等效于光通带滤波器) 将各种载波上的光信号分开。 图卜1w d m 波分复用系统 电子科技大学硕士学位论文 w d m 技术在光传输网中的典型应用如图卜1 所示。1 。w d m 系统由光合波器( 光复 用器) 和可以提取独立光波长的光分波器( 光解复用器) 组成。发射端的发射机发出 光波长不同且精度和稳定度能满足一定要求的光信号，经过光合波器、掺铒光纤 放大器，送入光纤中传输( 光纤线路巾可根据需要设置光线路放大器) 。到达接收 端后，经光纤前置放大器放大，通过光分波器恢复成原来的各路光信号。 w d m 使单波长传输变成多波长同时传输，从而可咀大大增加光纤的传输容量。 例如，如果每个波长的传输速率为2 5 g b s ，在一根光纤中同时使用4 个波长，则 光纤总的传输容量就可达到2 5 4 = l o g b s 。一根光纤可以传输几卣个甚至几千 个信道，因此，w d m 技术可以充分利用光纤的巨大带宽资源( 多于5 0 t h z 的理论可 用带宽) ，使一根光纤的传输容量比单波长传输时的容量增加几倍、几十倍甚至几 百倍，可以认为w d m 技术将为光传输网的发展提供几乎取之不尽的资源。 1 1 2w d m 技术特点 w d m 技术具有下述特点： 1 传输容量大，可节约宝贵的光纤资源。对单波长光纤系统而言，收发一个 信号需要使用一对光纤，而对于w d m 系统，不管有多少个信号，整个复用系 统只需要一对光纤。 2 对各类业务信号“透明”，可以传输不同类型的信号，如数字信号、模拟信 号等，并能对其进行合成和分解。 3 网络扩容时不需要敷设更多的光纤，也不需要使用高速的网络部件，只需 要换端机和增加一个附加光波长就可以引入任意新业务或扩充容量，因此w d m 技术是理想的扩容手段。 4 组建动态可重构的光网络，在网络节点使用光分插复用器( d a d 岫或者使用 光交叉连接设备( o x c ) ，可以组成具有高度灵活性、高可靠性、高生存性的全 光网络。 正是因为w d m 技术的上述特点，使其在近几年得到了迅猛的发展，并且随着 研究的不断深入，w d m 技术将更广泛地应用于未来超高速的传输网中。 1 2 帅m 网络结构与节点设备 如图l 一2 所示，现有的传输网络由接入网络和w i ) i f i 核心网络两部分组成。其 巾具有w d m 接口的边缘节点构成了接入网络，而由o x c 波长路由核心节点通过光 第一章绪论 纤互连瓜成为w d m 核心网络。边缘节点具有会聚业务量的功能，因此需要能汇聚 各种小粒度业务量的电处理设备，来实现业务汇聚。核心网中的o x c 节点具有多 个标准的光纤接口，可对任一光纤信号或其波长信号与其他光纤信号进行可控的 连接，它可能具有波长转换能力，不过只能以波长级的粒度交换业务。通常w d m 网络结构指的就是w d m 核心网络这部分。 w d m 网络中的节点o a d m i 和o x c 设备，通常由w d m 复用解复用器、光交换矩阵 ( 由光开关和控制部分组成) 、波长转换器和节点管理系统组成，主要完成光路上 下、光层的带宽管理、光网络的保护、恢复和动态重构等功能。 圈卜2 接入网络和w d m 核心网络 1 3w d m 网络虚拓扑及其设计 按照研究网络的角度的不同，w d m 光网络具有两种拓扑结构，物理拓扑和虚拓 扑，虚拓扑又叫逻辑拓扑。物理拓扑表征光网络节点之间物理连接关系，虚拓扑 表征网络节点间业务联系情况 1 3 1 物理拓扑 网络的物理拓扑就是网络节点的物理连接关系，从构成上看，它是网络节点 与光缆链路的集合。在w d m 网络中当两个o x c 节点间有一条光纤链路连接时，对 应的物理拓扑的两个节点间就有一条边相连。物理拓扑的设计一般是在网络的建 立阶段，根据业务流量需求等因素静态规划的。在波分复用技术发展的早期，点 到点的连接是唯一的应用方式。随着节点技术的发展，o a d m 和o x c 设备的出现使 各种物理拓扑的实现成为可能。除简单的点到点的连接方式外，常见的物理拓扑 电子科技大学硕士学位论文 有线形、星形、环形、树形和网孔形等。一般来说，网络的物理拓扑一h 确定了 就不轻易改变了。 1 3 2 虚拓扑 在w d m 光网络中，一对通信节点在进行数据传输之前必须建立连接，即建立 一条从源节点到目的节点的光路( 1 i g h t p a t h ) ”1 。所谓光路就是指两个节点间的一 条全光通道，它可能经过一条或者多条光纤链路，数据在光路上进行透明传输， 光路上的任何中间节点不进行任何的电层存储转发或者交换处理，从而可以大大 提高网络的数据吞吐能力，简化网络的管理和减少电层的网络设备。光路可以看 作是光通路层上的端到端的连接，它形成电通路层的虚连接。一个经过优化的光 通路层网络，不仅可以用来建立适应给定的业务需；求得最佳电通路层拓扑，而 且可以通过光通路层的恢复和保护机制直接解决由于光纤切断或节点故障等物理 层原因造成的通信中断问题，而不必改变电通路层的拓扑结构。这种光通路层的 连接被称为网络的逻辑拓扑，也叫虚拓扑”1 。 物理拓扑 虚拓扑 图l 一3 虚拓扑的形成 如图i - 3 所示，当我们在物理拓扑的2 斗1 和4 _ 3 斗2 间分别搭建一条光路 后，在对应的虚拓扑上2 与i 和4 与2 间就各自增加了一条有向逻辑边，处于上 层的i p 路由器就会看到2 与1 是相邻的，4 与2 是相邻的，从节点2 发出的i p 包 只需要一跳就可以到达节点1 ，从节点4 发出的i p 包也只需要一跳就可以到达节 点2 。 第一章绪论 1 33 虚拓扑设计问题 给定一个w d m 网络的物理拓扑，波长复用数目，资源限制( 节点的收发器数目) 和业务量矩阵，如何在这个物理拓扑上通过建光路搭建虚拓扑以使网络的拥塞， 信息延时等网络性能指标优化就是虚拓扑的设计问题。在文献。“”中虚拓扑的设计 问题可以被陈述为混合整数线性问题，分别给出了波长路由w d m 光网络虚拓扑设 计问题的线性描述。 由于在文献“6 ”3 中虚拓扑的设计都是假设业务量矩阵是预先知道而且是恒 定的但在实际的网络中，由于业务量情况随着时间是动态变化的。”1 ，因此虚拓 扑的性能随着时间的变化将会下降，为了改善虚拓扑的性能，将引入下一节的问 题，虚拓扑重配置。 1 4 虚拓扑重配置 我们在最初的物理拓扑上按照某种策略依据当时的节点业务量矩阵情况进行 的虚拓扑设计得到的虚拓扑，然后在上面运行业务量，随着时间的推移，节点之 问的业务量矩阵发生了变化，如果仍然在当前旧的虚拓扑上运行新的业务量矩阵 的话，网络的某些性能指标( 如单位大小业务量需要路由的平均跳数、全网吞吐量、 所需波长数目、总代价等) 将会下降，因此我们有必要对当前的虚拓扑进行修改以 适应新的业务量矩阵，优化网络的性能，这就是虚拓扑重配置。 如上所述，虚拓扑的重配置问题是给定一组新的光路连接需求( 新的业务量矩 阵) 、原有的光路配置、网络物理拓扑结构( 链路状态信息) ，要求为新的需求确定 路由并分配波长，以使某些性能指标( 如全网吞吐量、所需波长数目、总代价等) 达到最优，同时对原有的配置影响最小。 虚拓扑的重配置需要删掉一些现有拓扑的光路，增加一些新的光路，这对上 层业务量将会产生中断影响。业务的中断对可靠性要求较高的网络来说，带来的 影响是致命的“”“。因此，在文献“”1 里面重配置的原则都是既要使新的虚拓扑 与旧的虚拓扑差异不是很大，同时又要使网络的的性能尽可能的得到提高。 1 5 本文的主要贡献既内容安排 本文的主要贡献是对在动态变化业务量情况下w d m 网络的设计方法的研究， w d m 网络存在的一个重要问题是由于w d m 网络服务的业务量总是动态变化的，最初 电子科技大学硕士学位论文 通过搭建光路设计好的光网络虚拓扑在新的业务量矩阵下它的性能如网络平均权 重路由，网络负载均衡性，网络拥塞等性能指标就有可能下降。 解决此问题有两个研究方向，第一个方向是可以在最初的虚拓扑的设计过程 中设计出种虚拓扑出来，该虚拓扑是一种负载均衡的虚拓扑，在这种虚拓扑上 运行的业务量矩阵特征只要在某种范围以内，无论它怎样动态变化，网络都不会 出现拥塞，但相关文献所提出这种的虚拓扑设计算法v l b s ( v a l i a n t l o a d b a l a n c i n gs c h e m e ) 只能适用于同构网络，即每个节点所拥有的容量大小都 相等，在第二章中，作者提出了一种新的更通用的负载均衡的光网络虚拓扑设计 算法g v l b s ( g e n e r a lv a l i a n tl o a db a l a n c i n gs c h e m e ) ，该算法与传统的负载均 衡算法v l b s 不同之处在于v l b s 算法只能适用于同构网络而g v l b s 算法既可以适 用于同构网络，又可以适用于异构网络，在本章中将给出了g v l b s 算法的的详细 推导和数值分析。 解决此问题的第二个研究方向是我们最初在一个物理拓扑上按照一个业务量 矩阵设计出一个虚拓扑出来，随着业务量矩阵的动态变化，网络的性能指标可能 会下降，不再最优，我们可以参照新的业务量矩阵，当前的虚拓扑和物理拓扑情 况在某些约束条件下( 如可以改变的光路条数) 进行虚拓扑的重配置，使网络的性 能指标( 如单位业务量的平均路由跳数) 提高，本文的第三章研究并实现了该虚 拓扑重配置算法。 我们通过虚拓扑重配置算法得到了一个新的虚拓扑，但如何把当前旧的虚拓 扑过渡到新的目标虚拓扑也是一个很关键的问题，这是个拆掉旧光路搭建新光 路的过程，而由于在这个过程中w d m 光网络上面仍然运行着业务，直接拆掉正在 工作的光路对上面的业务( 如i p 业务) 影响会很大，因此设法找出一个合适的w d m 光网络拆建光路的信令顺序也是非常必要和具有现实意义的，本文第四章研究并 实现了一种光网络虚拓扑重配置过渡过程算法，该算法可以给出一种w 1 ) m 光网络 新旧虚拓扑过渡过程中合适的拆建光路的信令顺序，采用这种信令顺序进行虚拓 扑过渡，需要直接拆掉正在工作的光路的条数将会显著减少，从而极大的提高了 光网络虚拓扑重配置过程的性能，该算法也做成了算法d l l 动态链接库( d y n a m i c l i n kl i b r a r y ) 模块加载到光纤重点实验室自主开发的“光网络业务量工程软件t e ” 以供其他同学进行二次开发使用了，本章中将给出该算法的详细过程说明和算法 性能仿真及结果分析。 在第五章中，针对动态到达和离去的多个波长业务量的光路连接请求，作者 提出了一种新的带保护的多路径波长路由算法。在这一章里面，动态变化的业务 第一章绪论 量形式从业务量矩阵变成了动态到达和离去的源宿节点对光路连接请求了，在这 种业务量请求是动态到达和离去的情况下一般采用单路径波长路由算法为光路连 接请求找路，针对请求的业务量大小有可能是多个波长的情况，本章提出采用新 的带保护的多路径波长路由算法为动态到达的光路连接请求找出和建立光路。本 章首先介绍所提算法的详细步骤，并对该算法进行仿真和与普通的单路径波长路 由算法进行性能比较，可以看出，该算法比起单路径波长路由算法相比确实可以 提高网络的负载均衡性。 在本文的第六章中介绍了作者为了对第三，四，五章的针对动态变化业务量 的w d m 光网络不同的设计算法进行性能仿真和测试而开发的一个w d m 光网络算法 仿真平台，作者首先介绍该仿真平台的总体框架，然后分别介绍在该框架下的各 个模块设计实现以及相关的核心代码。 第七章对整个毕业论文各章内容进行了总结。 电子科技大学硕士学位论文 第二章一种更通用的负载均衡的光网络虚拓扑设计算法 2 1 研究背景 w d m 波分复用技术可以充分利用光纤的低损耗带宽，在一根光纤中的不同波长 上异步、高速地传输各种格式的信号，是挖掘光纤巨大带宽资源的最佳技术。w d m 光网络也成为了目前公认的骨干传输网络。但是w d m 光网络的虚拓扑设计却存在 两个主要困难，一个是对未来业务量需求的不确定性使我们现在设计好的虚拓扑 在未来的业务量情况下性能可能要降低，出现网络拥塞“，另外，对在出现故障 情况下网络备份资源的合理安排也比较困难。因此，为了使设汁好的光网络虚拓 扑能够在未来较长时间内有效运行使用，常常需要付出极大的链路容量资源，造 成网络资源的浪费。 最近，在光网络虚拓扑设计领域出现了一种新的称之为v a l i a n t 负载均衡网 络设计方法“”，v a lja n tl o a d b a l a n c i n gs c h e m e 简称v l b s ，采用v l b s 方法设计 出来的光网络虚拓扑将对业务量矩阵的变化不再敏感，甚至在一定数目下的链路 故障和节点故障情况下仍然可以无拥塞正常工作。但是v l b s 有一个缺陷就是它所 针对的网络类型必须是同构网络，每个网络节点从接入网中所吸纳的业务量必须 是一样的，这个要求与实际网络情况是不同的。那有没有可能找出一种既可以在 同构网络中使用，又可以在异构网络中使用的负载均衡虚拓扑设计方法呢? 本章将提出一种新的更通用的负载均衡光网络虚拓扑设计算法g e n e r a l v a l i a n tl o a d b a l a n c i n gs c h e m e ，简称g v l b s ，采用该算法可以对异构的光网络 进行虚拓扑设计。 本章的结构如下，首先将简要介绍v a l i a n t 负载均衡光网络设计方法( v l b s ) ， 然后在此基础上介绍本章提出的新的更通用的负载均衡光网络虚拓扑设计算法 g v l b s ，将详细介绍该算法的推导过程，同时给出使用g v l b s 的数值计算结果以及 分析。 2 2v l b s 文献o ”详细的介绍了负载均衡网络的思想以及v l b s 算法的推导，本章将简单 第二章一种更通用的负载均衡的光网络虚拓扑设计算法 介绍一下负载均衡网络的基本思想以及v l b s 算法的中的公式结果，它们也是推导 g v l b s 的基础。 2 2 1 负载均衡思想 负载均衡思想最初是由计算机领域里面的v a l i a n t 针对多处理器互连网络提 出来的“，该思想在性能保证的可扩展路由器设计上也得到了应用 t 7 2 i 8 在文献 ”中，负载均衡又被应用到网络设计之中了。该方法首先假设所设计的骨干网 络是一个具有个节点的全连接的网状网络，如图2 1 所示，每个节点拥有，的容 量，该容量定义为该节点服务的接入网的容量之和。这就意味着节点可以收到其 它骨干节点的总共为，的业务量。 图2 - 1 一个具有个节点的网状网络 该网络在节点间拥有全连接的结构，进入网络的包分两步进行转发，第一步， 每个节点统一的把要发送的业务量负载均衡到个节点上去，而不管每个包真正 的目的节点，这可以是包到包的负载均衡，也可以流到流的负载均衡，这样每个 节点都收到从节点发出的业务量的1 。第二步，所有的包都被转发到最终的目的 地。因为每个节点收到的业务量最大为r ，该业务量被负载均衡到个节点，由第 一步来说所收到的实际业务量最多为d n ，第二个步骤是第一步的对偶，因为每 个节点所能够收到的速率最大为r ，它收到从每个节点业务量的1 n ，所以由第二 部路由所收到的业务量最多为，。因此每条链路容量达到2 r n 的网络能够 1 0 0 保证一个有效业务量矩阵的需求。 因为基本上每个包都需要经过两跳转发才能到达最终的目的节点，这看起来 好像网络的效率不是很高，但是该网络任一节点对间的链路所需容量仅为2 t i n 但 却可以承受任意一个从源节点到目的节点业务量为r 的业务量矩阵。不采用负载均 衡的话，相同的业务量矩阵，如果所有的业务只需通过一跳到达目的地的话，则 需要建一个全连接网络，并且每条链路的容量要达到r 。从这里可以看出，如果要 电子科技大学硕士学位论文 服务所有的有效业务量矩阵的话，采用负载均衡思想将可以得到n 2 的收