（电磁场与微波技术专业论文）光网络传送规划方案的研究与比较.pdf

光网络传送规划方案的研究与比较 摘要 随着社会信息化程度的不断提高，对通信的需求呈现加速增长的 趋势。从网络经济性的角度出发，以尽可能低的价格为用户提供尽可 能多的高质量的通信服务，是通信网发展所必须遵循的原则。面对通 信业务量迅猛增长、业务形式日趋多样的挑战，未来的通信网应当是 一个宽带、高速、灵活、可靠的智能化综合业务网络。 如何规划w d m 的网络拓扑以使既能满足网络传送的需要，保证传 输性能又能达到网络构建的成本最小，在波长变换技术越来越成为解 决波长冲突、减小网络阻塞率的重要手段时，又如何在网络中分配波 长变换器成为当前网络规划中研究的热点。 w d m 光网的结构设计包含两层含义：一是物理拓扑结构的设计， 二是逻辑拓扑结构的设计。逻辑拓扑即是节点之间的逻辑连接，而物 理拓扑关注的是节点之间是怎样实现物理连接的。一般来说，在w d m 网络中逻辑拓扑是独立于物理拓扑的，这就使拓扑的设计成为两个不 同的课题。本文把重点放在物理拓扑上。 在w d m 全光网中，源宿节点间通过建立光通道以实现光域内的 数据交换，一条光通道可以跨越多条链路以及多个节点，如果节点不 具备波长变换能力，则光通道必须满足波长连续性限制。如果节点具 有波长变换能力，则在一条光通道的不同链路上可以使用不同的波 长。波长变换技术的引入使波长冲突的问题得到有效的解决。 本文在第二章中提出了两种物理拓扑的规划方式：支撑网络收缩 算法和二阶饱和边算法。并用仿真的方式比较了在七个节点的情况 下，应用两种算法的规划结果，得出了后者先进与前者的结论。 在第三章中，分析了前人设计的算法的局限性后，提出了一种全 新的波长变换器在网络中分配的算法，这种算法可以计算出具体在节 点中分配的变换器的数量，比以前的算法更灵活，更经济。 由于本文主要是研究了在网络规划中解决具体问题的算法，为了 对算法的性能进行评估和比较，笔者在还参与编制了w d m 网络规划仿 真软件，在第四章中，主要对软件的设计和开发做了简单的介绍。 关键词w d m 光网络光网络规划算法物理拓扑波长变换器 分配f w c s t u d y i n ga n dc o m p a r i n go f p r o j e c to n o p t i c a ln e t w o r kt r a n s m i s s i o n a b s t r a c t i n f o r m a t i o np l a ym o r ea n dm o r ei m p o r t a n tr o l ei no u rd a i l yl i f e ， n e e df o rc o m m u n i c a t i o ni n c r e a s e s q u i c k l y s e e i n g f r o mn e t w o r k c o s t , p r o v i d i n gm o r ee n o u g hh i g hq u a l i t yc o m m u n i c a t i o ns e r v i c ew i t h l o we n o u g hp r i c ei sh o tp o i n tp e o p l ec a r e c o n f r o n t i n gc h a l l e n g e so f q u i c ki n c r e a s e i nc o m m u n i c a t i o nt r a f f i ca n da p p e a r a n c eo fm o r ea n d m o r en e wt r a f f i cf o r m ，t h ef u t u r eo fn e t w o r ks h o u l db ea ni n t e l l i g e n t i n t e g r a t e ds e r v i c en e t w o r kw h i c h i sw i d e b a n df a s ta g i l i t ya n dc r e d i b l e h o wt od e s i g nw d mn e t w o r kt o p o l o g yt of u l f i l lt h en e e do ft r a f f i c t r a n s m i s s i o n ， e n s u r et r a n s m i s s i o np e r f o r m a n c ea n dm a k en e t w o r kc o s t t h es m a l l e s t ；h o wt oa l l o c a t ew c si nn e t w o r kw h e nt e c h n o l o g yo fw c b e c o m e sa ni m p o r t a n tm e t h o dt os o l v ew a v e l e n g t hc o n f l i c ta n dd e c r e a s e b l o c kp r o b a b i l i t yt u mt ob eh o tp o i n ti nt h ec o u r s eo fn e t w o r kp l a n w d mn e t w o r ks t r u c t u r ed e s i g ni n c l u d et w om e a n i n g s ：o n ei sd e s i g n o fp h y s i c a lt o p o l o g y , t h eo t h e ri sd e s i g no fl o g i c a lt o p o l o g y t h el o g i c a l t o p o l o g ys p e c i f i e st h el o g i c a li n t e r c o n n e c t i o na m o n g t h en o d e s ，a n dt h e p h y s i c a lt o p o l o g ys p e c i f i e sh o wt h en o d e sa r e i n t e r c o n n e c t e db yt h e p h y s i c a ll i n k s g e n e r a l l y , t h el o g i c a lt o p o l o g i e sa r ei n d e p e n d e n to f t h e i r p h y s i c a lt o p o l o g i e s s od e s i g n o fn e t w o r k t o p o l o g yb e c o m e st w o d i f f e r e n tp r o b l e m s o u rp a p e ro n l yc a r e sf o rp h y s i c a lt o p o l o g y i nw d ma l l o p t i c a ln e t w o r k , as o u r c e - t o - d e s t i n a t i o np a t hu s u a l l y c o n s i s t so fm u l t i p l e h o p s i fa t r a n s m i s s i o nc a l l o c c u p y t h es a r r l e w a v e l e n g t ho ne v e r yh o p ，i tc a nr e m a i ni no p t i c a lf o r mw i t h i nt h e n e t w o r k o t h e r w i s e ，i te n c o u n t e r sw a v e l e n g t hc o n f l i c ta n di th a st ob e b l o c k e d t or e d u c et h eb l o c k i n gp r o b a b i l i t y ，w ec a ne q u i pt h en e t w o r k , n o d e sw i t hw a v e l e n g t hc o n v e r t e r st or e s o l v e w a v e l e n g t h c o n f l i c t s p e c i f i c a l l y ，w h e nat r a n s m i s s i o ne n c o u n t e r saw a v e l e n g t hc o n f l i c to na h o p ，w ec a n u s eaw c t oc o n v e ai t sw a v e l e n g t ht oa n o t h e ro n e ，s ot h a ti t c a nr e m a i ni no p t i c a lf o r mo nt h i sh o p t h ei n t r o d u c t i o no fw a v e l e n g t h c o n v e r s i o nt e c h n o l o g yr e v o l v e sw a v e l e n g t hc o n f l i c te f f i c i e n t l y i nc h a p t e ri i ，w ep r o p o s et w op h y s i c a ln e t w o r kt o p o l o g yp l a n a l g o r i t h m sn a m e dt h es u p p o r t i n gn e t w o r ks h r i n k i n ga l g o r i t h ma n d t w o s t a g ec u ts a t u r a t i o na l g o r i t h m t h e nw ea p p l yt h et w oa l g o r i t h m si n an e t w o r kp l a ne x a m p l ew i t hs e v e nn o d e st h r o u g hc o m p u t e rs i m u l a t i o n a n df i n dt h a tt h el a t e ri sm o r ea d v a n c e dt h a nt h ef o r m e r c h a p t e r a n a l y z et h ee x i t i n ga l g o r i t h m sf o ra l l o c a t i n gw a v e l e n g t h c o n v e r t e r si na l l o p t i c a ln e t w o r k s ，a n dp r o p o s ea na l ln e wo n ew h i c hc a l l d e t e r m i n et h en u m b e ro ff w c si nt h ef w cb a n ko fe v e r yn o d e ，w h i c h i sm o r ea g i l ea n dm o r ec o s t l yt h a na l lt h ee x i t i n go n e s m yp a p e rm a i n l ys t u d i e st h ea l g o r i t h m si nn e t w o r kp l a n ，t oe v a l u a t e a n dc o m p a r e p e r f o r m a n c eo ft h e m ，t h ea u t h o rh a v ep a r t i c i p a t e di n c o m p i l et h ew d mn e t w o r ks i m u l a t i o np l a t f o r m ，s oi nc h a p t e ri v ，w e s i m p l yi n t r o d u c et h ed e s i g na n dd e v e l o p m e n to f t h ep l a t f o r m k e yw o r d sw d mo p t i c a ln e t w o r k o p t i c a l n e t w o r kp l a n a l g o r i t h mp h y s i c a lt o p o l o g yp l a nw a v e l e n g t hc o n v e r t e ra l l o c a t i o n 一 一一j i 一 f w 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本入签名：曼鱼塑之 日期： 2 0 0 5 ，5 1 3 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生在校 攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国家有关部 门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论 文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后遵守此规定) 本学位论文属于保密范围，在l 年解密后适用本授权书。 本人签名： 边至：童曼臣 日期： 导师签名：主益丝日期： 2 0 0 5 , 5 i ) 7 卵f 了j2 , - 北京邮电大学硕士论文第一章概述 第一章概述 随着社会信息化程度的不断提高，对通信的需求呈现加速增长的趋势。各类 新型的信息服务，包括计算机互连网络和多媒体通信业务，在全球范围内得到迅 速发展和普及。从网络经济性的角度出发，以尽可能低的价格为用户提供尽可能 多的高质量的通信服务，是通信网发展所必须遵循的原则。面对通信业务量迅猛 增长、业务形式日趋多样的挑战，未来的通信网应当是一个宽带、高速、灵活、 可靠的智能化综合业务网络。 1 。1 光联网技术的介绍 现代通信网中，先进的光纤通信技术以其高速、带宽的明显特征而为世人瞩 目。目前，光网络已达到了7 t b i 讹的系统容量，随着光纤性能的不断优化，可 以想象，未来光网络继续朝着t b i t s 速率乃至更高的速率发展已成必然。从系统 角度来看，支撑t b i t s 光网络的关键技术又基本上可分为光纤技术、光器件技术、 光节点技术和光联网技术四大类。本文主要研究光联网技术中地相关课题，所以 我们在下面将主要对这个问题进行介绍。 光联网技术涉及面广，技术难度大，但其作为宽带信息网络的基石，已为 世人瞩目。这项技术又可以分成如下的几个子问题： 1 光传送网分层结构。w d m 光传送网是用光波长作为最基本交换单元的交 换技术，即客户信号是以波长为最基本单位来完成传送、复用、路由、和管理。 w d m 光传送网是随着w d m 技术的发展，在s d h 网络的基础上发展起来的，通过引 入光节点，在原有的分层结构中引入了光层，它又可以细分成三个子层：从上到 下依次为光信道层( o c h ) 、光复用段层o m s 和光传输段层o t s ，相邻的层网络 形成所谓的客户朋艮务者关系，每一层网络为相邻上一层网络提供传送服务，同 时又使用相邻的下一层网络所提供的传送服务。这种分层结构为t b i t s w d m 光联 网提供了必要的统一规范与实施策略。 北京邮电大学硕士论文 第一章概述 2 w d m 光网中的路由选择波长分配。在w d m 光网的实现中，如何合理地规 划网络波长资源并采用合理的路由算法，是决定网络资源利用效率的关键问题， w d m 光网的路由选择和波长分配( r a w ) 是重要的应用基础性研究问题，它解决 怎样通过o x c 或其它设备构成运载信号的光通道，并合理地分配通道所使用的波 长，使有限资源能提供尽量大的通信容量。r a w 问题由两部分组成：其一是如何 为每个源节点寻找到达目的节点的路径；其二是在这些路径上如何分配波长。r a w 问题可分为动态r a w 和静态r a w 。动态r a w 一般是考虑建立光连接的请求随机到 达，静态r a w 则是考虑在进行路由和波长分配前已知所有的希望建立的光连接。 另外根据o x c 节点是否提供波长转换功能，光通路可以分为波长通路 ( w a v e l e n g t hp a t h ) 和虚波长通路( v i r t u a lw a v e l e n g t hp a t h ) 。 3 w d m 光网的结构设计。w d m 光网的结构设计包含两层含义：一是物理拓扑 结构的设计，二是逻辑拓扑结构的设计。因此整个网络的设计问题就变成了对这 两个不同层面的优化问题。在对这两层的优化过程中，必须考虑彼此之间的限制 与支持。特别是逻辑拓扑结构的设计，既要考虑到下层w d m 光层特性与物理拓扑 结构因素，也要考虑到上层所运载的业务特性因素。因此设计逻辑拓扑结构时， 要考虑的已不再仅仅是业务流量情况，还包括对下涉及物理结构( 波分复用技术 所产生的波长数的限制，器件的限制等) 和对上涉及网络所提供的性能指标( 时 延敏感，可靠性等) 。另外设计逻辑拓扑结构还涉及到许多全网优化的指标，如 节点交换能力的利用率、网络的最大拥塞率、平均传输时延、波长复用因子等。 4 光网络的生存性。网络生存性泛指网络遭受各种故障仍能维持可接受的 业务质量的能力。光网具有极高的传输速率，同时其”模拟网络”的特性与s d h ” 数字网络”的特性又有所不同，因此探索能在尽可能短的时间内为被中断的业务 寻找新的传输路由和自愈方案是十分必要的。网络生存性策略包括保护与恢复技 术、控制管理技术等，保护与恢复技术包括保护倒换、重选路由等自愈技术，涉 及到通信系统的许多方面，相关参量包括恢复率、恢复时间、冗余度、开销及复 杂度等。 5 光传送网的管理技术。由于光网中客户信号的传送、复用、选路、监测 等处理功能都是在光域上进行，因此光网络的管理方式必须适应光层管理的特点 和要求。如对光交叉连接( o x c ) 和光分插复用( o a d m ) 设备的管理；自身的管 2 北京邮电大学硕士论文第一章概述 理信息结构和开销方案；尤其是光网究竟需要哪些运行、管理和维护o a m 信息， 以及这些信息如何传送，如何与现有的s d h a t m 传送网管理进行协调与配合等。 光网的管理既可以采取集中方式，也可以采取分布方式。分布式管理方案通常比 集中式管理方案更为健壮，但从维持网络数据库的一致性和实现网络局部或全网 的分布恢复的角度分析，分布式管理方案更加复杂。光网的管理协议( o n m p ) 主 要解决自动拓扑发现和资源更新、带宽管理、分布式信令、光信道计算、光通路 保护与恢复等，而管理的一些功能则可通过数字包封技术来解决。 6 业务的接入与适配。由于目前普遍采用了统一的t c p i p 协议，因此在光 网上能否接入以i p 为基础的各种数据业务已成关键。从长远看，i po v e ra t m ， i po v e rs d h 都将最终发展为i po v e rw d m o p t i c a l ，因此对于今后的长期应用 来说，为了实现在光纤上直接传输i p 数据包，最关键的问题之一是需要设计出 一种合理的帧格式( 物理层接口) ，即规范出一种新的、最佳的i p 对光路的适 配接口，但在目前情况下，考虑到多种因素，主要使用以下两种帧格式来实现两 种不同的技术路线：s d h 帧格式( 或简化) 和千兆比以太网帧格式，即i p s d h w d m 和i p e t h e r n e t w d m 。另外目前已有一些研究机构提出了一些其他的优化解决方 案与具体的实现方法。 基于以上问题的分类方式，我们研究的内容属于“w d m 光网的结构设计”这 个子问题。 1 2 论文期间所作的工作 在读研究生期间，我参加了国家自然科学基金项目“下一代光网络业务和资 源管理体系的研究”，在项目中承担对光网络传送规划方案研究与部分算法的实 现工作，主要针对其中的两个问题进行了系统的研究：光网络传送物理拓扑的规 划问题和光网络规划中波长变换器位置分配问题。 本文在第二章中提出了两种w d m 传送网络物理拓扑的规划算法：支撑网络 收缩算法和二阶饱和边算法。并用仿真的方式比较了在七个节点的情况下，应用 两种算法的规划结果，得出结论。 在第三章中，简单介绍了现有波长分配算法的研究状况，提出了一种全新的 波长变换器在网络中分配的算法，这种算法可以计算在节点中分配的变换器的具 北京邮电大学硕士论文 第一章概述 体的数量，通过计算机仿真分配后网络的性能的出算法比现存的分配算法更灵 活，更经济。 在第四章中，主要介绍了实验室自主研发的w d m 网络规划仿真软件的设 计、结构及功能等情况。 论文的主要成果是对两个问题的发展现状进行了系统的阐述，提出了先进的 规划算法，并开发仿真软件。对算法在仿真后的性能进行比较和总结，论证了算 法的先进性和实用性。 4 北京邮电大学硕士论文第二章光传送网规划不同方案的提出与比较 第二章光传送网规划不同方案的提出与比较 光网络传送规划问题属于光联网技术w d m 光网的结构设计的一个子问题， 目前国内外普遍关注和研究，并取得了一系列相应的成果，对于实际的网络修建 起到了辅助和参考的作用。w d m 光网的结构设计包含两层含义：一是物理拓扑 结构的设计，二是逻辑拓扑结构的设计。因此整个网络的设计问题就变成了对这 两个不同层面的优化问题。在进行拓扑规划的同时，一般还会遇到另外一种规划 问题，就是通道规划。 对于拓扑规划，主要是根据业务矩阵的情况，物理光缆资源的情况，确定节 点位置，选择合适的光纤线路，组成某种形式的网络，如环网，格网( 注，以上 还只是单层的规划问题，如仅是s d h 层的规划或者仅是w d m 层的规划) 对于通路规划，则是根据某个目标( 资源耗费最少或最均衡，或者是s l a ) ， 计算业务需求所具体采用的路由和资源( 如s d h 是时隙，如w d m 是波长) ，也 就是通常所说的r w a 问题。根据通路规划的结果来决定具体设备的容量需求。 本文主要涉及物理拓扑结构的设计，在总结前人成果的基础上，提出了两种 新的物理拓扑结构设计的算法，并把其性能与以前的算法做比较，同时对两者进 行比较，得出论文的结论。我们这里提到的规划主要是单层规划。 2 1 支撑网络收缩算法 算法的输入是节点的物理位置，业务矩阵，成本矩阵，输出是节点在满足 业务传输情况下的物理拓扑，使建设的成本达到最小。 2 1 1 支撑网络收缩算法主要思想和基本流程 一般网络规划的基本流程是： 1 、首先，要预测业务量在未来的变化，给出未来的业务量矩阵； 2 、然后构建一个传送网络来承载这些业务。 3 、这时需要一个评估检测模块来评价这个网络以决定是否优化这个网络。 4 、如果对已有网络结构不满意，就调用网络优化模块对该网络进行优化，然后 5 北京邮电大学硕士论文第二章光传送网规划不同方案的提出与比较 再进行评估；如果满意，就直接输出结果，如果不满意，对此优化过程不断重复， 直到得到满意的结果为止。 上述过程的流程如图2 1 所示： 结果 图2 - - 1 支撑网络收缩算法的流程图 而这个过程具体到支撑网络收缩算法的大概流程就如下所述：在用户所给物 理节点信息的基础上首先构架一个支撑网络，这个网络由一些最小的环网组成， 即由一些三角形的环网组成，另外所有环网的周长加起来最短。这时网络中的逻 辑链路数尚未指定( 一条逻辑链路指一条分配了波长的光通道。) 然后我们在这 个支撑网上运行路由波长分配( r w a ) 算法，将用户输入的业务分配到逻辑链路 上去。这时，网络上的逻辑链路数已经被指定了，我们通过网络费用模块计算现 在网络的成本。理论上讲这个时候网络的成本是比较高的，因此我们就减掉一些 链路，简化这个网络。每一步我们都在所有可以去除的冗余链路中遍历一次，选 择一种使成本下降最多的情况，保留下来。这样一步步下来我们就可以得到一个 “最优 的解。由于我们采用的是一种贪婪算法，只能做到在每一步的最优，因 此不能保证最终结果的最优。 6 北京邮电大学硕士论文第二章光传送网规划不同方案的提出与比较 2 1 2 算法的具体模块 算法的流程包括四个模块：业务矩阵生成模块，支撑网络生成模块，路由波 长分配模块和网络费用模块。下面对这四个模块分别进行介绍： 2 1 2 1 业务矩阵生成模块 y 叮= 百万石兰1 可y ， “薹学+ 熹。鲁“ l ：i 局到j 局的发话话务量 d ：i 局到j 局的距离 c 。：i 局的交换机容量 c ：j 局的交换机容量 e ：i 局到本地网内各局的话务量之和 n ：全网端局总数 k ：足瓦离的k 次方 2 1 2 2 支撑网络生成模块 从上面的算法流程中看到，我们首先要生成一个支撑网络。该模块的输入是 用户设定的网络物理节点的信息，主要是各个节点的位置信息。根据这些位置信 息，来建立一个支撑网络，由于是进行w d m 环网规划，因此在这个支撑网络上 所有的节点都被以环的形式连接起来。在后面的网络评估模块中我们主要考虑的 是网络的建设成本，由于网络的建设成本与传输链路的长度成一定正比关系，因 此要求这个网络中的所有的环网的周长的和最小。每个环网都有三个节点组成， 7 北京邮电大学硕士论文第二章光传送网规划不同方案的提出与比较 这样生成的网络冗余度最大。该算法的流程如下：首先在所有的节点中搜索出三 个节点，三个节点组成的环网周长最小；然后在剩余的节点集中选择出一个节点 添加进来，使其组成新的网络，网络的周长还是最小。这样把一个一个节点添加 进来，最后组成的网络中所有的环网的周长也是最小。这样就形成了一个由一些 相交的环网组成的网络。 该算法的流程如图2 2 ： 图2 2 支撑网络生成算法流程图 2 1 2 3 路由波长分配模块 由于路由波长分配算法不是本文主要研究的对象，所以关于它的介绍就不赘 述了。我们来看一下我们这里采用的r 、凇算法。本算法中把m e s h 网看成是由 一些w d m 环网组成的网络，对已知的网络业务分配路由，并选择波长，最后决 定每个环上的波长数。由于我们进行的是环网的仿真，在环上可以只考虑对环上 业务进行优化，而业务则被分为跨环业务和本环业务。对于跨环业务，我们把各 个环网抽象成一个个“节点 ，而跨环业务则被看成这些虚拟结点之间的业务， 然后调用波长路由算法把这些业务分配下去，考虑到链路均衡和网络生存性问 题，我们采用的是链路均衡波长路由算法。然后这些跨环业务就可以分解成环间 业务和环内业务。对于小规模的w d m 环形网络，可以采用i l p 算法，但对于大 北京邮电大学硕士论文第二章光传送网规划不同方案的提出与比较 规模的网络则需要分解法，在这里我们采用单环优化算法。本算法采用的r w a 算法流程如图2 - - 3 所示： 踌环业务和 本环业务 算法路由 所有本环业务 图2 3 路由波长分配算法流程图 最后需要说明的是该算法中的链路均衡路由波长算法和单环优化算法，均可 以替换成其他的波长路由算法，但是得到结果没有该算法的结果好。 2 1 2 4 网络费用模块 网络费用模块主要是用来评估各种网络构建方案，判断哪一种网络更便宜。 在理论上，一个网络的成本分为三个不同的阶段，分别为： 安装阶段 运行阶段 进一步发展阶段 各个阶段之间的费用模块完全不同，根据软件的需求分析，我们只考虑了在 网络安装阶段的费用，称之为网络建设费用。网络建设费用主要是由组成该网络 的各个光电设备成本和网络的施工费用构成。 9 务一 一环 由业一 一跨解 徽磊一 昕一 一将 北京邮电大学硕士论文第二章光传送网规划不同方案的提出与比较 一种费用模型一般是在技术仍在发展的情况下提出的，如w d m 技术。实际 上这样会有直觉的成分，因为一件设备的总费用完全受其组件的费用的影响，比 如它的功能模块。而一旦某件设备可商用化以后，其它的费用成分就变得重要起 来，如包装和别的制造因素。事实上由于经济、政治和技术上的原因，准确地给 出网络建设费用是很复杂的。并且由于在毕设中，我的侧重点是对整个规划算法 的研究，在对实际情况了解很少的情况下过多研究费用情况是没有必要的。出于 这一考虑，我只用了一个理想化的简单费用计算公式，这些还要在下一节做进一 步说明。 2 2 二阶饱和边算法 饱和边算法是一个解决电子信息网络的一个很好的办法。但是当遇到特殊的 问题时，这种方法还有待改进。传统的饱和边算法不适合光网络拓扑的建设，因 为他不能满足光网络的集中约束。在本文中，对原始的算法进行了改进，得到了 二阶饱和边算法。 其主要思想如下： l 、第一阶段，我们不考虑波长连续性的限制，应用饱和边为主要方法来寻 找一个好的初始网络。 2 、第二阶段，我们考虑了波长连续性限制。我们在初始网络上进行路由和 波长的分配来建立指定的光通路。当一些指定的光通路由于波长冲突不能建立 时，我们再应用饱和边的主要思想，在网络中用最佳的方式插入新的链路。 其实我们也可以看作是第一阶段的算法适用于完全波长变换的网络，第二阶 段的算法适用于非波长变换网络。 2 2 1 网络模型 网络有n 个节点，在已知成本矩阵c 和业务矩阵b 的情况下，规划网络拓 扑使最终得到的网络既能负载所有的业务，成本又能达到最小。 成本矩阵c ：c = ( q ，) 肌| ，c ，是节点之间建立链路所用的成本a 当节点对 之间有链路时，成本不为0 ，否则为无穷。q ，= n ；c f 2 。这里的n 受链路的 1 0 北京邮电大学硕士论文第二章光传送网规划不同方案的提出与比较 长短影响，链路越长，n 越大。链路的长短与n 成比例关系。 业务矩阵b ：b = ( 良d ) 。，以d 是节点之间的业务所需要的通道数。 在第一个阶段，我们没有波长连续性的约束，所以没有波长分配，在第二个 阶段，我们加入了波长连续性的约束，所以有了波长分配的介入。在两个阶段分 别都应用了一次饱和边算法的主要思想。 负载：根据最短路径算法，在一条链路上应该建立而由于波长信道不足而没 有实际建立的通道数。 负载= 应该建立的通道数一可以建立的通道数( 链路上的可用波长数) 实际负载： 实际负载= 已建立已使用的波长数+ 负载 最初网络：在第一阶段算法执行期间，所有中间过程的网络。 初始网络：c s i 结束后得到的网络。 2 2 2 一阶饱和边算法 图2 4 一阶饱和边( c s l ) 算法的流程图 1 ) 基于成本矩阵，确立一个最小的生成树( m s t ) 。由于m s t 是在无向图中定 义的，所以我们把网络转换到无向图中，在无向图中节点i 和节点j 之间的边 的成本为c j 。，或q 。我们从任意一点开始使用m s t 算法来生成最小生成树 北京邮电大学硕士论文 第二章光传送网规划彳；同方案的提出与比较 m s t 。我们按以下方式基于这个m s t 构造一个最初网络：在m s t 中，如果 在节点i 和节点j 之间有边的话，我们就在最初网络中加入从i 到j 的链路和 从i 到i 的链路。 2 ) 为最初网络中的所有节点对找到最小权重( 这里指的是跳数最小) 的路径( 路 由的算法) 。根据路径的权重按照升序的方式为这些节点对进行排序。当遇到 路径权重相同的节点对时，根据两点之间的通道数将节点对降序排序。如果 还有相同的情况，将他们任意排序。对于业务请求，如果沿着最小权重路径 所经过的各条链路上均至少有一条波长信道可用，那么在最初网络中建立这 条通道；否则，在各条链路上给他们的b u r d e n 加1 。为所有的业务请求重复 这样的计算。如果由矩阵b 所定义的业务通道都已建立，转向9 1 ) ，如果还 有通道没有建立，g ot 0 3 ) 。 3 ) 如果最初网络是全连接的，但是却不能提供所有需求矩阵所定义的光通道， 就报告说网络不可能满足需求，停止，否则g ot 0 4 ) 。 4 ) 按以下步骤找到饱和边：根据各链路的实际负载按降序删减链路，直到网络 成为不可连接。被删减的链路组成饱和边。( 注意，这些链路不是真的被移去 了，而只是为了计算饱和边被“删减 掉) 。 5 ) 用l 表示饱和边中所有链路的b u r d e n 之和。要加入最初网络中的链路数为： n i n = l w 。从中选择饱和边中最便宜的n i n 条链路加入最初网络中。为了达 到这个目的，我们还需要解决以下特殊的情况： 5 1 ) 如果饱和边中的最大的链路数为n m ，比n i n 要小，就把所有的 n m 链路加入最初网络中。确定没有在饱和边中而能够加入最初网络中 的链路，如果这些链路的数目比n i n - n m 要大，根据他们的成本按照升 序排序，把最便宜的n i n - n m 条链路插入最初网络，否则，把所有的这 些链路插入最初网络中( 此时网络成为全连接的网络) 。 6 ) 为最初网络中的每一对节点找到最小权重的路径。 7 ) 按照以下的方法重新路由已经建立的通道以缩短长度。对于每一条建立的通 道，把它的长度与在最初网络中的节点间的最小权重路径的长度进行比较。 如果后者比较小，计算他们的差异。并根据这个差异对已建立的通道进行降 序排序。当遇到相同的，把他们根据通道的长度降序排序，如果仍旧有相同， 北京邮电大学硕士论文第二章光传送网规划不同方案的提出与比较 任意排序。对于有着正向差异的每条通道，有以下两种不同的情况： 7 1 ) 如果对于最小权重的路径在每条链路上都有至少一条可用的波长，就 把路径路由到此条路径上。 7 2 ) 如果在其上至少有一条链路没有可用的波长，( 也就是说在6 ) 中可用 的波长现在被另外一条先路由的路径占用了) ，那么不改变此条路径。 重复步骤7 1 ) 和7 2 ) 直到所有的有正向差异的已建立路径都被考虑了。 8 ) 按以下方式建立没有建立的路径。对于那些没有已经建立的路径的节点对， 根据他们的最小权重路径的长度按升序进行排序，如果遇到相同的情况，根 据节点对之间没有已建立通道的数量进行降序排序。如果还有相同的情况， 任意排序。对于节点对s 、d ，我们用x s d 表示他们之间没有建立的通道数。 用y s d 表示在最小权重路径上各链路上可用波长信道的最小数量。在最小权 重路径上可建立的通道数等于m i n ( x s d ，y s d ) 。对于那些由于没有足够的可 用波长信道不可建立的通道，可暂时把他们放在一边。重复这个操作直到没 有通道可以建立。 9 ) 如果在步骤8 ) 中没有通道被建立，则g ot o l o ) 。否则，逐条的检查在步骤 9 1 ) 和9 2 ) 中挑选出来的链路来确定他们是否可以从最初网络中删除。当 检查一条链路时，我们把经过这条链路的所有通道重新路由到其他的链路上。 在为了删除链路而进行的检测当中，我们要区分以下两种情况： 9 1 ) 由矩阵b 确立的所有通道都被建立。根据链路的成本对所有的最初网 络中的链路进行降序排序，对于相同的任意排序。检查所有的链路，如 果可能就删除它。当所有的链路都被检查到了，我们就得到了最初网络。 停止。 9 2 ) 至少有一条通道没有建立。对于最初网络中的节点i j 之间的链路，用 n i j 表示已经占用的波长通道数，用q ，表示每条被占用的波长信道的平 均成本( c ，一= q n i j ) 。根据e 对最初网络中的所有链路进行降序 排序，对于t i e 任意打乱。我们检查第一个n i n 链路( 在步骤5 种插入 到最初网络中的链路数) ，然后，g ot o l o 。 为了检查链路，我们采用了以下的方法：将此条链路的权重设为无限大。对 于每条经过此条链路的通道，为两节点找到最小权重的路径，如果这个路径 1 4 北京邮电大学硕士论文第二章光传送网规划不同方案的提出与比较 为有限大，则这条通道可以重新路由，否则，不可重新路由。如果经过此条 链路的所有通道均可重新路由，则把通道都重新路由到最小权重的路径上并 删除此条链路。否则保持此条链路和其上的通道不变。 1 0 ) 按以下步骤计算最初网络上各条链路的b u r d e n 。对于没有建立的通道，为节 点对找到最小跳数的路由，然后，为此条路由的各条链路的b u r d e n 加l 。 g o t 0 3 ) 进行下一个重复。 注释l ： 步骤1 ) 是一个初始化。为了简化这个初始化，我们假设在最初网络的各链 路中有方向相反的两条光纤。如果有一个方向的光纤的利用率很低，它将会在下 一个循环中被除去。 注释2 ： 如果在步骤8 种没有通道被建立，则在步骤9 种我们不会删除任意一条链路， 否则在步骤5 中刚被加入到最初网络中的链路会在同一循环中被删除，在下一个 循环中有被加入，形成无止境的循环。为了防止这种情况的发生，我们要保证在 每一个循环中要么有一些通道被建立要么有一些光纤被加入。因此，当所有的通 道被建立或最初网络为全连接的时候，我们的算法就会停止。用另外一句话说就 是我们的算法会在有限次的循环后结束。 注释3 ： 在步骤3 中，我们把网络为全连接的这种极端的情况视为算法停止的条件。 按照这种方法，即使当输入的s p e c i f i c a t i o n 是错误的或者是没有道理可言的时候， c s l 将会在有限次的循化后停止。 2 2 3 第二阶段饱和边算法 北京邮电大学硕士论文 第二章光传送网规划不同方案的提出与比较 进行波长路由分配 在初始的网络上建立尽可能多的光通路 y 圣：= 州! 兰竺叠竺! 奎! in 置新进行波长路由分配以缩短己建立的光纤 链路的长度 进行渡长路由分配建立尽可能多的未建立的光 通路 n否所有的光 都已建立? 、 当所有高成本的链路上的光通路都可以重新路 由到其他链路上时删除这条链路 兰三 - - _ - _ _ _ - _ _ - _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ ， 图2 5c s 2 算法的流程图 在这里先解释几个名词： 光通道的长度：光通道的长度等于光通道的跳数。 最小权重光通道：我们按以下方式为每条链路上的每条波长信道分配一个权 j j = ； 里。 如果一条波长信道是可用的，它的权重就是l ，否则他的权重是无限大。在 一条特定波长信道上光通道的权重等于这条光通道上的各条链路上的此条波长 信道的权重之和。为了找到任意两节点之间的最小权重光通道，分两个步骤。第 一，为这w 条波长应用最短路径算法找到每条波长的最小权重路由。第二，在 垆听 北京邮电大学硕士论文第二章光传送网规划不同方案的提出与比较 这w 个选择中选一条权重最小的。如果有冲突，选择最小编号的波长。 算法的流程如下： 1 ) 对于由e s l 得到的路径，按照他们的长度进行降序排序，如果有t i e ，任意排 序。对于每条路径，如果在每条链路至少有一条且是同一条波长可用，根据 首次命中策略分配一条波长信道给这条通道，以建立一条光通道。否则暂时 把它放在一边。如果所有的通道都可建立，则停止。 2 ) 按照以下方式建立尽可能多的网络中没有建立的光通道。 2 1 ) 为没有建立的光通道找到最小权重的光通道。 2 2 ) 如果所有的最小权重的光通道的权重为无限，则转入2 4 ) ，否则执行步 骤2 3 ) 。 2 3 ) 根据权重对最小权重光通道按照降序排序，有t i e 任意排序。对于每条 路径，如果在每条链路至少有一条且是同一条波长可用，根据首次命中策略 分配一条波长信道给这条通道，以建立一条光通道。否则( 也就是说，在2 1 ) 中可用的波长现在被早先建立的光通道占据了) 暂时把它放在一边。如果所 有的光通道都可建立，则停止。否则，9 0t o2 1 ) 。 2 4 ) 对于那些权重为无限大的最小权重光通道，对应的没有建立的光通道采 用了由c s l 确定的路由。每当一条链路被采用，它的b u r d e n 加l 。g o t 0 3 ) 。 3 ) 确定网络是否为全连结的。具体跟c s l 中的3 ) 相同。 4 ) 找到饱和边，具体跟c s l 中的3 ) 相同。 5 ) 基于2 ) 确定能加入网络中的链路的数量。用与c s l 中5 ) 步同样的方法在网 络中加入新的链路。 6 ) 按照以下的方法对以建立的光通道重新路由以缩短他们的长度。对于每条已 建立的光通道，找到两节点之间的最小权重光通道。计算现在的最小权重光 通道的长度和以往的长度的差异。根据这个差异对以建立的光通道进行降序 排序，如果有t i e ，根据通道的长度进行降序排序，如果仍有t i e ，任意排序。 按照这个顺序对以建立的通道处理。特别强调的是，对于由正向差异的光通 道，我们要区分开以下两种情况： 6 1 ) 如果最小权重光通道的每条链路都至少有一条可用的波长，将光通道重 新路由到这条最小权重光通道上，并且根据首次命中策略对其分配一条 1 7 北京邮电大学硕士论文 第二章光传送网规划不同方案的提出与比较 波长。 6 2 ) 否则，光通道不变。 7 ) 建立尽可能多的没有建立的光通道。方法同2 ) ，除了当我们计算每条链路的 b u r d e n ( 2 4 ) 时我们不采用c s l 确定的路由。相反，我们找到并采用每条未 建立光通道的最小权重的那条路由，对这条路由的所有相关链路的b u r