（光学工程专业论文）智能光网络中实现qos保证关键技术的研究.pdf

南京邮电大学硕士研究生学位论文 摘要 智能光网络中实现q o s 保证关键技术的研究 摘要 在智能光网络的q o s ( j 艮务质量) 问题中，r w a ( 路由和波长分配) p l 题是最为核心、最 为关键的问题。 本论文主要研究了网络的静态规划、生存性处理以及动态规划中影响网络服务质量的 各种主要因素，采用c 语言设计并实现了规划和生存性处理的仿真，对仿真结果进行了统 计分析，得到各种因素的影响规律。 论文首先分析了r w a 问题中的主要研究方法、基本思想以及r w a 仿真问题的c 语 言设计结构，给出了最短路由、负载均衡、准静态的选路算法和波长选择算法的基本流程。 在静态规划研究中，对各种因素( 例如业务的排队、业务的波长请求、业务的服务等级、 网络中链路上的波长数、波长的一致性问题等) 的影响进行了仿真和统计分析，得到了一些 改善网络服务质量的有益结论：比较了路由算法对仿真结果和网络服务质量的影响，结果 表明，一定的网络条件下，使用负载均衡的方法能够提高网络资源的利用率，降低网络的 拥塞率，从而提高网络的服务质量；最后针对业务的路由进行了优化处理，从结果中可以 看出，该措施将有助于降低网络中链路上的总负荷数，提高网络服务质量。 在生存性处理研究中，给出了网络生存性处理的四种方案，以及网络中业务恢复时间 和恢复率的计算公式。对各种因素( 例如业务恢复的机制、业务的等级、网络中链路上的波 长数、生存性处理的不同方案等) 的影响进行了仿真和统计分析，得到了改善网络服务质量 的一些结论。最后进一步探讨了网络的生存性处理对静态规划的影响等问题。 在动态规划研究中，对各种因素( 例如系统仿真的时间、使用的随机函数、仿真中业务 请求的服务时间、业务随机到达的时间间隔、业务的波长需求、业务的服务等级、网络中 链路上提供的波长数等 ) 的影响进行了仿真和统计分析，得到了一些改善网络服务质量结 论。最后针对不同的网络拓扑，比较了最短路由、负载均衡和准静态选路算法对服务质量 的影响，结果表明，使用负载均衡和准静态的选路方法得到的网络拥塞率小于同样条件下 使用最短路由方法得到的网络拥塞率，具有较高的网络服务质量；而且准静态选路思想是 最短路由思想的一个很好的补充，能够提高最短路由算法的灵活性，提高网络的服务质量。 关键词： q o s ， r w a ， 负载均衡，服务等级，规划，保护恢复，强度因子， 准静态选路 南京邮电大学硕士研究生学位论文 a b s t r a c t s t u d y o nk e y t e c h n i q u e sf o rq o s g u a r a n t e e i nt h e i n t e l l i g e n to p t i c a ln e t w o r k a b s t r a c t t h er w a ( 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 ) p r o b l e mi st h ek e yp r o b l e mi nt h e i n t e l l i g e n to p t i c a ln e t w o r kq o s ( q u a l i t y o fs e r v i c e ) t h i st h e s i sm a i n l ys t u d i e ss e v e r a lf u n d a m e n t a lf a c t o r si n f l u e n c i n gt h eq o so ft h eo p t i c a l n e t w o r kw i t ht h es t a t i cp r o g r a m m i n g ，t h es u r v i v a b i l i t ys t r a t e g ya n dt h ed y n a m i cp r o g r a m m i n g ， w h i c ha r ed e s i g n e da n do b t a i n e du s i n gs i m u l a t i o n si ncl a n g u a g e t h er u l eo fe v e r yi n f l u e n c e f a c t o r sa l eg o a e ni nt h es t a t i s t i c a l l ya n a l y z i n gt h er e s u l t so fs i m u l a t i o n s t h em a i na p p r o a c h e sf o rr w a ，f u n d a m e n t a li d e a si nt h er w ap r o b l e m s ，a n dt h e s i m u l a t i o n - s t r u c t u r e si ncl a n g u a g eo ft h er w aa r ea n a l y z e df i r s t l yi nt h i st h e s i s ，a n dt h e n f o l l o w e dw i t hp r e s e n t i n gt h ef l o w so ft h es h o r t e s tr o u t i n g ，t h el o a d b a l a n c e dr o u t i n g ，t h e s e m i - s t a t i cr o u t i n g ，a n dt h ew a v e l e n g t hs e l e c t i n ga l g o r i t h m s i nt h es t a t i cp r o g r a m m i n ga p p r o a c h ，s o m ef a c t o r si n c l u d i n gt h eq u e u i n gf o rt h ec o n n e c t i o n s ， t h ew a v e l e n g t hd e m a n do fe a c hc o n n e c t i o n ，t h ep r i o r i t yo fe a c hc o n n e c t i o n ，t h en u m b e ro f w a v e l e n g t h e so nt h el i n k ，t h ew a v e l e n g t hc o n s i s t e n c y , a n ds oo n , w h i c hi n f l u e n c et h en e t w o r k p e r f o r m a n c e s ，a r es i m u l a t e da n da n a l y z e ds t a t i s t i c a l l y s o m ec o n c l u s i o n sa l eo b t a i n e dt og e t b e t t e rp e r f o r m a n c ei nt e r m so ft h eq o s b yc o m p a r i n gt h ei n f l u e n c e s 、析md i f f e r e n tr o u t i n g a l g o r i t h m so nt h es i m u l a t i o nr e s u l t sa n dq o s ，i tc a l l b es e e nt h a to ns o m ec o n d i t i o nt h e l o a d - b a l a n c e di d e ah a sa na d v a n t a g eo fi n c r e a s i n gt h eu t i l i z i n gn e t w o r kr e s o u r c e sa n dd e c r e a s i n g t h en e t w o r kc o n g e s t i o nr a t e ，w h i c hw i l li m p r o v et h eq o so ft h en e t w o r k i na d d i t i o n ，t h e o p t i m i z i n gp r o c e s si sc a r r i e do nt h em a i nr o u t so ft h ec o n n e c t i o n s a c c o r d i n gt ot h es i m u l a t i o n r e s u l t s ，i ti sc l e a rt h a tt h i sp r o c e s sh e l p st od e c r e a s et h et o t a ln u m b e ro fl o a d so na l lt h el i n k so f t h en e t w o r kt os o m ed e g r e e ，w h i c hi m p r o v e st h eq o s i no r d e rt oh a n d l e 谢廿1t h es u r v i v a b i l i t yo ft h eo p t i c a ln e t w o r k ，f o u rs t r a t e g i e sa r ep r e s e n t e d a n dt h ef o r m u l a sa b o u tr e s t o r a t i o n - t i m e sa n dr e s t o r a t i o n - r a t e sa r ed e d u c t e d b ys i m u l a t i n ga n d a n a l y z i n gs t a t i s t i c a l l yt h ei n f l u e n c e so f s o m ef a c t o r s ，s u c ha st h er e s t o r i n ga p p r o a c h ，t h ep r i o r i t y o fe a c hc o n n e c t i o n , t h ew a v e l e n g t h e so nt h el i n k ，t h ed i f f e r e n ts c h e m e s ，a n ds oo n ，s o m eu s e f u l 、 c o n c l u s i o n sw h i c hw i l le n h a n c et h eq o so ft h en e t w o r k sa r eo b t a i n e d f u r t h e r m o r e ，t h e i n f l u e n c e so ft h es u r v i v a b i l i t yo nt h es t a t i cp r o g r a m m i n ga r ed i s c u s s e d i nt h es t u d yo fd y n a m i cp r o g r a m m i n g ，t h es i m u l a t i o n sa n da n a l y s e so ns o m ef a c t o r s ，s u c h i t 南京邮电大学硕士研究生学位论文 a st h el e n g t ho fs i m u l a t i n g ，t h er a n d o mf u n c t i o n s ，t h es e r v i c et i m ea s k e db yt h ec o n n e c t i o n ，t h e i n t e r v a lo ft h et w or a n d o mf o r e a n d - a f tc o n n e c t i o nr e q u e s t s ，t h ew a v e l e n g t hd e m a n d ，t h e c o n n e c t i o np r i o r i t y , t h ew a v e l e n g t ho nt h el i n k , a n ds oo n , a g ep e r f o r m e d ，t h r o u g hw h i c hs o m e u s e f u lc o n c l u s i o n sc a nb eo b t a i n e d m o r e o v e r , f o rd i f f e r e n tn e t w o r kt o p o l o g i e s ，t h ei n f l u e n c e s f o r d i f f e r e n tr o u t i n ga l g o r i t h ma st h es h o r t e s tr o u t i n g ，t h el o a d b a l a n c e dr o u t i n g ，a n dt h e s e m i - s t a t i cr o u t i n go nt h eq o s ，a r ec o m p a r e d t h er e s u l t ss h o wn l a tt h ec o n g e s t i o n - r a t e su s i n g t h el o a d - b a l a n c e dr o u t i n ga n dt h es e m i - s t a t i ca r ca l w a y sl e s st h a nt h eo n e su s i n gt h es h o r t e s t r o u t i n ga p p r o a c h , p r o v i d e do t h e rc o n d i t i o n sa l es a m e f u r t h e r m o r e ，t h es e m i s t a t i cr o u t i n gi d e a i sag o o dc o m p l e m e n tt ot h es h o r t e s tr o u t i n ga p p r o a c h , w h i c hi m p r o v e st h en e t w o r kf l e x i b i l i t y , a n di m p r o v e st h eq o so ft h eo p t i c a ln e t w o r ka sw e l l k e y w o r d s ：q o s ， r w a ，l o a d b a l a n c e d ，s e r v i c el e v e l ，p r o g l a n m i n g ， p r o t e c t i o na n dr e s t o r a t i o n ， s t r e n g t hf a c t o r ， s e m i s t a t i cr o u t i n g m 一 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意o 研究生签名： 日期：与磕移 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名： 导师签名：姓日期： 南京邮电大学硕士研究生学位论文 第一章服务质量与路由和波长分配问题 第一章服务质量与路由和波长分配问题 1 1 智能光网络 1 1 1 光网络的现状 光通信技术经过几十年的发展，在光传输、光交换、光接入、光联网及核心器件与模 块等多个方面取得了巨大的进步和成功，不仅为通信网络提供了巨大的传输带宽，而且极 大地增加了网络结点的吞吐容量，目前已经成为传送网中最主要的技术手段【1 1 。 随着信息化的加快，数据业务在骨干网上持续爆炸性增长，尤其是对i p 业务需求的激 增，人们对现有的光网络提出了更高的要求。i p 业务具有突发、多变、不确定、不可预见 等特点，采用目前的s d h 、w d m 网络已经无法充分利用光纤带宽，而且网络配置缓慢、 操作复杂。因此，网络运营商不仅要解决带宽问题，更需要具有灵活提供带宽的能力；同 时，市场的开放和竞争都要求有一种创新的光联网技术，以支持未来大容量的数据业务。 从传送平面看，以d w d m 为基础的光网络基于可持续发展的网络结构，可提供巨大而廉 价的网络带宽，且可透明支持任何业务和信号，因而是理想的传送平台。然而，目前主要 基于点到点通信的d w d m 系统只具有原始的传输带宽，组网不灵活。因此，应该进一步 挖掘光网络的带宽，发展具有光层灵活联网功能的智能光网络。为此，人们提出了智能光 网络的概念，希望能将光传送网由人工配置转变为自动控制，i t u t 提出的自动交换光网 络( a s o n ) 体系极大地推动了智能光网络的标准化，得到了业界的广泛认可 2 1 。 1 1 2 智能光网络的提出 所谓智能光网络，就是网络的管理和控制具有智能化的特点，能够动态地、自动地、 完成端到端光通道的建立、拆除和修改，并且当网络出现故障时，能够根据网络拓扑信息、 可用资源信息、配置信息等动态地配置最佳恢复路由f 3 】。a s o n 实质上可以看作是自动交 换传送网( a s t n ) 技术在光网络中的一种应用实例。而a s t n 是一种更通用的网络概念，它 与具体的技术无关，并能提供一系列支持在传送网络上建立和释放连接的控制功能。采用 a s o n 技术之后，原来复杂的多层网络结构变得简单和扁平化，从光网络层开始直接承载 业务，避免了传统网络中业务升级时受到的多重限制。智能光网络技术的核心特点就是支 持电子交换设备( 如p 路由器等) 动态地向光网络申请带宽资源。电子交换设备可以根据网 南京邮电大学硕士研究生学位论文 第一章服务质量与路由和波长分配问题 络中业务分布模式动态变化的需求，通过信令系统或者管理平面自动地建立和拆除光通 道，不需要人工干预。可以说a s o n 代表了光通信网络技术新的发展阶段和未来的演进方 向【4 】。 1 1 3a s o n 的构架 i t u t 提出的a s o n 体系结构模型中，整个网络包括三个平面，即控制平面、管理平 面和传送平面，三个平面之间通过数据通信网( d c n ) 联系，d c n 是负责实现控制信令消息 和管理信息传送的信令网络。控制平面是a s o n 的核心层面，它负责完成网络连接的动态 建立以及网络资源的动态分配，这也是a s o n 区别于传统光网络的特点所在。控制平面的 基本功能是呼叫和连接控制。 1 2 光网络中的结点 尽管a s o n 的核心是控制平面，但是其物理功能的实现离不开传送平面光结点的支撑。 从光网络的组网来看，构成光网络结点的设备主要有针对本地网络只提供上路和下路功能 的光分插复用器( o a d m ) 和主要应用于网间交叉互连的光交叉连接器( o x c ) 以及提供业务 接入和业务汇聚的网关结点( 即混合结点：同时具有o x c 和o a d m 功能的结点) 等【3 】。 1 2 1o x c 的功能结构 o x c 结点的功能类似于s d h 网络中的数字交叉连接器( d x c ) ，只不过在光域上实现， 无需进行光电电光转换和电信号处理。主要用于骨干网间互联和业务流量较大的网络结点 处。o x c 的功能结构如图1 1 所示，其应具备的主要功能有：( 1 ) 路由和交叉连接；( 2 ) 连 接和带宽管理；( 3 ) 波长指配；( 4 ) 保护和恢复功能；( 5 ) 波长汇聚合并能力( w a v e l e n g t h g r o o m i n g ) ：( 6 ) 通道汇聚能力；( 7 ) 上下路功能；( 8 ) 波长变换功能；( 9 ) 信号监控预告警；( 1 0 ) 通道控制接口功能等。o x c 在光层对波长通道的交叉连接能力极大地提高了信号重新选 择路由的速度和精度，对于网络的高速传输和快速恢复都具有重要的意义。o x c 算法的实 质是r w a ( 路由和波长分配) ，它与o x c 结点结构密切相关，如结点是否支持全交叉、是 否支持波长变化、是否具有波长调谐能力等【1 】【3 】。 1 2 2o a d m 的功能结构 o a d m 结点的功能类似于s d h 网络中的分插复用器( a d v 0 ，是将各通道按光波长来 南京邮电大学硕士研究生学位论文第一章服务质量与路由和波长分配问题 合波或分波，而不是简单的功率分配。o a d m 的功能主要是从传输设备中下路( d r o p ) 通往 本地的信号，同时上路( a d d ) 本地用户发往另一个结点的其他用户的信号到w d m 信号中， 那些非本地信号在以光的形式直接通过( b y p a s s ) 上下路的同时不能影响其他波长通道的传 输，即o a d m 在光域内实现了传统的s d h 设备中的电分插复用器( a d m ) 在时域中的功能， 而且它更具有透明性，可以处理任何格式和速率的信号，克服了传统网络中的结点电子瓶 颈问题。o a d m 的功能结构如图1 2 所示，其应具备的主要功能有：( 1 ) 可以有选择地按需 上厂f 路波长；( 2 ) 每一次上下路波长都不影响直通波长；( 3 ) 具有波长转换能力；( 4 ) 具有功 率均衡能力；( 5 ) 具有对频率隙进行管理的开销处理能力等。o a d m 可以看作是o x c 功能 的简化【1 】【3 】。 图1 - 1o x c 功能结构图图1 - 2o a d m 功能结构图 1 2 3 网关结点 网关结点的主要功能是把低速的本地网络、城域网络连接到高速的骨干网络上。在把 多个低速业务汇总到一个高速数据流再转换为光信号发出去的同时，还应该能够把骨干网 络上的高速信号分解为本地网络或者城域网络中能够处理的低速信号流。 1 3 光网络中的服务质量问题 1 3 1 服务质量 随着网络的飞速发展，人们对网络的要求也越来越高。越来越多对带宽、延迟、抖动 敏感且实时型强的语音、图像等重要数据在网上传输，为此引入了如何保证服务质量的问 题。解决这个问题的一个途径是增加网络的带宽，但带宽的增加毕竟是有限的，而且代价 昂贵，只能在一定程度上缓解这个问题。保证服务质量的另一种有效的手段是通过拥塞管 理、拥塞避免、流量整形以及相关问题的网络规划等策略对网络上的流量进行管理。 服务质量( q o s ，q u a l i t yo f s e r v i c e ) 就是针对不同的需求，为承载在各种网络( 如局域网、 南京邮电大学硕士研究生学位论文 第一章服务质量与路由和波长分配问题 帧中继、i p 网络、光网络等) 上的网络流量提供不同质量的服务。q o s 也是网络的一种安 全机制，是用来解决网络阻塞等问题的一种技术，当网络过载或拥塞时，q o s 能确保重要 业务量不受延迟或丢弃，同时保证网络的高效运行。 1 3 2 流量疏导 、 波长汇聚( 波长整饰) ，是指在o x c 结点上将不同速率或者相同速率的、去往相同方向 的低速波长信号进行汇聚，形成一个更高速率的波长信号在网络中进一步传输。这时可能 出现两种情况：一种是进入o x c 的低速信号在同一终端进行电的终结；另一种是进入o x c 的低速信号去往相同的方向，可能在中间的某个结点再一次分开，分别进行各自的传输。 通道汇聚( 通道整饰) ，是指在光网络的边缘通过将几路进入结点的低速率信号进行合 并处理，转换成一个高速率的光信号进一步在光网络中进行传输。这些低速率的信号往往 具有相同的目的结点，或者在很长的距离上有相同的路径。这种方法可以让多协议的子波 长通道在一个波长中传输。通道汇聚的颗粒一般都比较大【3 】。 1 3 3 多层生存性 多层保护恢复能提供一个灵活的保护恢复机制，也能给用户和网络运营商提供更多 的业务选择。一种有效的多层保护策略是在光网络层提供光纤级的保护恢复和光通道保护 恢复技术，对级别高的业务通过光纤级专用通道来保护业务，避开网络故障：对于低优先 级的业务则通过为业务重新建立光通道来保护业务；对于那些不能通过以上两种方式恢复 的业务，交由i p m p l s 层来处理。对于已有单独保护恢复机制的上层业务，最简单的方 法就是给该业务提供光层上分离的主用和保护两条光通道，上层业务的保护通过它自身的 保护恢复能力在两条光通道上切换以完成保护【2 】。 1 3 4r 、a 问题 在传统的电路交换的网络中，只涉及到为连接请求建立路由的问题，所有的交换电路 都是平等的而且是完全一样的。而在w d m 网络中却存在着“波长连续性”限制因素和“同 根光纤必须不同波长 ( 所有共享同一根光纤的光路径必须分配不同的波长) 的通道分配 约束等因素。在给定一个连接请求后，需要为之建立路由并在路由上分配波长( 即路由和波 长分配：r w a ，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 ) ，因而两者的区别很大，从而也要求在 光网络中必须采用科学合理的选路算法和波长分配算法来优化网络性能、减小波长的阻塞 南京邮电大学硕士研究生学位论文第一章服务质量与路由和波长分配问题 和减少对结点设备的端口数的要求，以降低运营和设备成本。 1 4 光网络中的r w a 问题 1 4 1 波长转换与波长的一致性约束 波长转换能力是光网络的r w a 问题中必须考虑的一个问题。在光网络里，如果网络 结点不具备波长转换能力，网络就必须在一个光通道上端到端地保证波长连续性，即波长 的一致性约束，这就使得通道计算变得更为复杂，因此在路由选择过程中必须考虑波长资 源状况。而如果网络结点具备波长转换功能，则会使得r w a 问题变得简单许多。 如果光网络结点具备波长转换功能，那么r w a 就不存在波长连续性问题的考虑，这 时的路由问题就等同于常规的电路交换网络，而仅仅受到每一条链路上可用波长数的限 制。若要求一条路由经过的所有链路上都必须保持相同的波长，这就是r w a 必须满足的 波长连续性条件。这种约束条件使得波长的利用率降低、拥塞率增大。假如存在一条空闲 的路由，但是由于该路由上链路段的波长不能保持一致，那么该路由还是不可使用的。因 此r w a 问题是光网络中所有问题中最为重要的基本问题。 1 4 2 波长通道与虚波长通道 光网络是由光通道将波长路由器和端结点相互连接而构成的。虽然每条链路都可支持 多种信号格式，但他们都被限制在波长粒度上。根据结点是否提供波长转换功能，光通道 可以分为波长通道和虚波长通道( 也称作逻辑波长通道，可以看作波长通道的特例) 。所谓 波长通道是指o x c 不具备波长转换能力，光通道在不同的光纤中必须使用同一波长，这 样为了建立一条波长通道，光通道层必须找到一条路由，该路由上的所有链路都必须存在 一个共同的空闲的波长。如果找不到这样的一条路由，则该传送的业务请求将失败，发生 拥塞。虚波长通道是指利用o x c 的波长转换功能，使光通道在一条路由的不同链路上可 以占用不同的波长，从而可以有效地利用各条链路上的空闲资源来传送业务请求，提高资 源的利用率。建立虚波长通道时，光通道只需要找到一条路由，而该路由上的所有链路都 有空闲可用的波长就可以，从而提高了波长的利用率，降低了阻塞发生的概率【1 】【3 】。由于 复杂网络中的任何两个结点之间都有可能存在多条路由，因此需要有一种有效的路由选择 和波长分配算法，根据网络的目前状况，为业务分配光通道。 南京邮电大学硕士研究生学位论文第一章服务质量与路由和波长分配问题 1 4 3 控制和管理机制 网络控制与管理的目标是：( 1 ) 使得连接请求的阻塞概率最小；( 2 ) 使得连接建立时间最 小；( 3 ) 使得控制开销的带宽最小；( 4 ) 使得网络可升级性最大。控制和管理机制中有两种常 用的机制：基于链路状态和基于分布式路由两种。 基于链路状态的机制通常采用的是开放最短路径( 路由) 算法，每个结点都保留着整个 网络的拓扑信息，包括每一条链路及其波长。当收到连接建立请求时，结点就根据其上保 留的拓扑信息来选定合适的路由和波长，然后结点向所有其他相关结点发出波长预留请 求。如果各个相关结点能预留这个已选定的波长，就向原结点发出”s e t u p ”消息，从而建 立连接通道。如果某个中间结点不能预留该波长，就向原结点发t a k e d o w n 消息，指 明波长预留失败。每次建立和释放一个光通道，各个结点就更新所保留拓扑信息并广播给 其他结点。本论文中使用的控制管理方法类似于该机制。 在基于分布式路由的机制中，每个结点并不保留整个网络的拓扑信息，而只是保留“下 一跳 信息，包括最短路径及波长，然后把连接请求逐级续传给下一跳结点。每次执行一 跳直到目的结点收到连接建立请求，然后沿着连接请求的路由向各个相关结点回传确认消 息，进而各个相关结点依次配置o x c 交换状态，则通道就可以建立起来。若某个中间结 点不能预留波长链路，则会向源结点发出拒绝连接消息，于是源结点尝试着以其他波长来 建立该通信的通道。当然，最后可能通道建立不起来的情况，从而业务请求就被阻塞。每 次建立和释放一条链路，结点就更新它的下一条信息，并广播给他的邻近结点。 1 4 4r w r a 问题的分类 在研究r w a 问题中，通常将网络支持的业务分为两类：静态业务和动态业务。静态 业务是在网络规划中事先给定的一组连接建立的请求，相应的r w a 问题就是需要为这些 请求寻求路由并在其路由上分配波长，以使得某些性能指标达到最优( 如网络的吞吐量大， 所需的波长数少等) ；动态业务是指网络中随机到达和离开网络的连接请求，相应的性能指 标通常是网络的阻塞率( 拥塞率) 。因此r w a 问题可划分为静态r w a 和动态r w a 问题 3 1 。 1 4 5a s o n 中的三种连接方式 a s o n 主要由传送平面、控制平面和管理平面三大平面组成，他们之间相互联系，从 而实现了三种连接方式：永久连接( p c ) 、软永久连接( s p c ) 和交换连接( s c ) 。每一种连接都 南京邮电大学硕士研究生学位论文第一章服务质量与路由和波长分配问题 是根据用户和业务的不同需求，由不同层面负责完成的【4 j 。 0 ) p c 与传统光网络中建立连接的方式相同，其连接路由的计算通过管理平面( 即网管 系统) 完成。永久连接的特点是相对来说比较固定，因此其路由一般都是事先规划好的，属 于静态r w a 问题。 ( 2 ) s c 是通过用户请求发起，完全由控制平面建立的一种连接形式。快速、自动建立 连接的方式体现了智能光网络的优势，具有实时性，属于动态r w a 问题。 ( 3 ) s p c 是通过控制平面和管理平面共同完成的，是两种连接方式的过渡，它由管理平 面向控制平面下达连接请求，由控制平面负责完成连接的建立，其r w a 算法介于前面的 两者之间。 1 5 论文的主要工作 根据前面的分析，了解到在光网络的服务质量问题中，r w a 问题是最为核心、最为关 键的问题。本文将就r w a 问题相关的静态规划、网络( 本文今后在不引起歧异的情况下， 简称光网络为网络) 的生存性处理以及动态规划等问题使用c 语言进行详细的仿真设计、 并讨论各种仿真中网络服务质量的主要影响因素。 论文首先对光网络的现状和发展作了简要的概述，并对r w a 问题作了简单的介绍。 在第二章中，主要讨论了本文在研究r w a 问题中的主要方法和基本思想，以及在实 现r w a 相关问题仿真过程中程序所考虑的主要问题。在第二章中详细讨论了本人r w a 仿 真问题的设计结构和对r w a 算法的理解，给出了负载均衡选路算法和波长选择算法的基 本程序流程，以及准静态选路算法的思想：并对使用到的主要数据结构、变量和仿真模型 中的业务排队、业务请求的处理等问题作了简要的讲解，以便在后面的章节中进一步进行 具体仿真的讨论。 在第三章中，主要研究静态规划中影响网络服务质量的主要因素，采用c 语言设计并 实现了静态业务规划的仿真。在一定的网络条件下，对影响静态规划结果的各种影响因素 的相应仿真结果进行了统计分析；为研究路由算法的影响，还分别采用了最短路由算法和 负载均衡算法进行了仿真和比较分析；最后，根据上述的分析和结果，讨论了负载均衡算 法下静态规划的优化处理方案。 在第四章中，主要研究了网络中单条链路发生故障时，网络的生存性问题及生存性问 题中影响网络恢复率和服务质量的主要因素。给出了网络生存性处理的四种方案，以及网 南京邮电大学硕士研究生学位论文第一章服务质量与路由和波长分配问题 络中业务恢复时间和相关恢复率的计算公式，采用c 语言设计并实现了网络生存性处理仿 真。在一定的网络条件下，对各种影响因素的仿真结果进行了详细地分析和讨论。最后进 一步探讨了网络的生存性处理对静态规划的影响等问题。 在第五章中，主要研究动态规划中影响网络服务质量的主要因素，采用c 语言设计并 实现了动态业务规划的仿真。在一定的网络条件下，对影响动态规划结果的各种因素的相 应仿真结果进行了详细的分析和讨论，并给出了强度因子等的具体定义；最后为研究路由 算法对规划结果和网络服务质量的影响，还分别采用了最短路由算法、负载均衡算法和准 静态算法针对不同的网络拓扑进行了仿真、比较和分析。 第六章中，对前面章节的主要工作出简要的总结。 本论文的论述结构主要是：首先按照章节介绍每章处理问题的思想，然后介绍相关算 法及仿真的设计流程，接着对影响仿真结果和网络服务质量的因素通过详细的理论和数据 进行分析，并得出相应的结论。 南京邮电大学硕士研究生学位论文 第二章r w a 问题及其仿真设计的基本结构 第二章r w a 问题及其仿真设计的基本结构 r w a 问题是光网络的核心之一，也是光网络服务质量中最重要的问题。该问题中的 r w a 算法主要是解决如何寻找一条合适的路由并合理地分配波长从而建立光通道，使有限 的资源充分发挥作用，以提供尽可能大的通信容量。当网络系统收到业务的连接建立请求 后，系统必须为业务选择合适的路由、分配波长、并配置网络中相关的o x c 交换结点， 此外还要提供网络状态的更新信息，如果业务得到通道的服务，则业务将获得业务提供的 服务，否则业务将因得不到网络资源而发生拥塞，影响网络提供的服务质量。 本章主要讨论了本文在研究r w a 问题中的主要方法和基本思想，以及在实现r w a 相 关问题仿真过程中程序所考虑的主要问题。文中详细讨论了r w a 仿真问题的设计结构和 对r w a 算法的理解，给出了负载均衡选路算法和波长选择算法的基本程序流程，以及准 静态选路算法的思想；并对使用到的主要数据结构、变量和仿真模型中的业务排队、业务 请求的处理等问题作了简要的讲解，以便在后面的章节中进一步讨论。 2 1 1r w a 问题的分类 在研究r w a 的问题中，通常将网络支持的业务分为两类：静态业务和动态业务。静 态业务是在网络规划中事先给定的一组连接建立请求，相应的r w a 问题就是需要为这些 请求寻找路由并在其路由上分配波长，以使得某些性能指标达到最优( 如网络的吞吐量大， 所需的波长数少等) ；动态业务是指网络中随机到达和离开网络的连接请求，在网络提供一 定的服务时间后才将业务拆除，因而业务光通道的建立和拆除也是动态的，要求实时地寻 找路由和分配波长，相应的性能指标通常是网络的阻塞率( 拥塞率) 。因此r w a 问题可划分 为静态r w a 问题和动态r w a 问题。 在建立一个业务连接请求的时候，需要考虑路由和波长的分配问题，因此r w a 问题 可以理解为：给定一个网络的拓扑结构，对需要建立光通道的业务连接请求进行路由的寻 找和波长的分配。本文对网络中静态业务的r w a 问题的设计和处理称为静态规划，对网 络中动态业务的r w a 问题的设计和处理称为动态规划。 从总体上看，r w a 问题中的选路和波长分配问题是不可分割的问题。但是仅仅其中的 波长分配问题就是一个n p c ( 非确定性多项式完备) 问题，要在合理的运算时间内解决大 9 南京邮电大学硕士研究生学位论文第二章r w a 问题及其仿真设计的基本结构 型网络的r w a 问题常常是不可能的。尽管光网络r w a 中包含的选路和波长分配是不可分 割的，但是考虑到计算的复杂性，通常将r w a 问题拆分成两个独立的子问题：选路问题 和波长分配问题，分别加以解决。 2 1 2 常用的选路算法和路由选择模式 1 - 常用的选路算法 路由选择的方法有很多种，目前常见的选路算法有： ( 1 ) 固定路由( f r ，f i x e dr o u t i n g ) ：选路是事先进行的，网络拓扑结构已知后，按照标 准的最短路径算法为每个结点对分配固定的光通道，业务请求到达时，将按照这条最短的 路由来请求波长分配。缺点是无法有效地利用网络的资源。 ( 2 ) 固定备选路由( f a r ，f i x e d - a l t e r n a t er o u t i n g ) ：为每一个结点维护一张路由表，里 面包含该结点到其他结点的多条路由，其中包括工作路由和备用路由，备用路由一般是链 路分离、边分离或者结点分离的。 ( 3 ) 备选选路( a r ，a l t e r n a t er o u t i n g ) ：是一种根据网络状态而动态选路的方法。分为受 限a r 和非受限a r 。受限的a r 是预先为每一对源宿结点对建立备选路由集合，而集合中 的排列是无序的，当需要建立连接的时候，根据当前的网络状态选择最合适的一条路由， 通常有最小负载路f l 了( l l r ，l e a s tl o a d e dr o u t i n g ) 、最小拥塞通路优先( f p l c ，f i r s tp a t hl e a s t c o n g e s t ) 等。而非受限a r ( a u r ，a l t e r n a t eu n c o n s t r a i n e dr o u t i n g ) 贝, t j 不事先建立备用的路由 集合，而是在请求到达时完全动态地计算出一个连接请求的一条路由来，常用的有 s p r e a d 、p a c k 等。 ( 4 ) 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 ) ：是一种常用的选路和波长分配算法，但适用于有 波长转换或者无波长转换的小型网络。 2 路由选择模式 、 众所周知，目前光网络是面向连接的交换网络，而i p 网络是基于分组交换的无连接网 络，因此，光网络的路由功能将具有不同于传统d 路由的特点。在i p 网络中，数据包的 转发是逐跳完成的，每个路由器基于数据包的目的地址进行独立的路由和转发判决，因此 为了防止路由环路的产生，网络中的每个结点必须具有对网络拓扑一致的视图，并需要使 用相同的路由算法。而在光网络中，数据传送是以端到端的方式完成的，在数据传送之前 需要提前建立所需的连接通道。光路由的计算是网络的边缘结点在接收到来自客户端的业 南京邮电大学硕士研究生学位论文第二章r w a 问题及其仿真设计的基本结构 务请求后进行的，采用源路由的方式，因此不会导致路由环路的产生。 2 1 3 常用的波长分配算法 波长分配的方法有很多种，常见的波长分配算法有： 1 静态的波长分配方法 静态波长分配方法常用图的着色法，该方法的优化目标是使得网络波长需求最小。 2 动态的波长分配方法 常用的动态的波长分配方法有： ( 1 ) 波长随机分配法( r a n d o m ) ：在可用波长集合中随机选择一条可以使用的波长来建立 光通道。 ( 2 ) 首次适应法( f f ，f i r s t f i t ) ：全网的波长按照一定的顺序进行排列，选择波长的时候， 就在可用的波长集合中选择第一条可以使用的波长来建立光通道。 ( 3 ) 最小负荷( l l ，l e a s tl o a d e d ) ：这是一种针对多纤网络的方案。 此外还有最少使用法( l e a s tu s e d ) 、最多使用法( m o s t - u s e d ) 、最小乘积法( m i n p r o d u c t ) 、 最轻承载法( l e a s t - l o a d e d ) 、最大和法( m a x - s u m ) 等。 2 2r w a 问题仿真设计中的网络模型及数据结构 根据本论文c 语言仿真程序设计的特点，在仿真的网络模型中将首先给出网格状( m e s h ) 网络的拓扑结构，包括网络中的结点数、链路上波长数、链路上的代价；对于每个需要服 务的业务，程序中设定的属性包括业务的源结点和目的结点，业务请求服务的波长数，业 务请求的服务级别等，动态规划中还包括多项时间信息；对于某个业务，根据当前的网络 状态，需要执行r w a 算法，为业务选择可用的路由和波长通道。如果网络中的资源足以 提供业务的需求，则业务的光通道得以建立，业务得到服务，否则业务将发生拥塞。 本论文的仿真内容包括r w a 问题中的静态规划