（电磁场与微波技术专业论文）基于p圈的格状光网络生存性设计.pdf

独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 球。，厶i 本人签名：艺继l 圣至日期：芝蒸至：2 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定， 即：研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学 校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论 文被查阅和借阅：学校可以公布学位论文的全部或部分内容，可以允许采用 影印、缩印或其它复制手段保存、汇编学位论文。( 保密的学位论文在解密 后遵守此规定) 本学位论文属于保密范围，在年解密后适用本授权书。 本人签名：速丞奎日期：之塑主：l 导师签名：耋基：岂日期：丞丝：兰：f 北京邮电大学硕士学位论文 摘要 基于p 圈的格状光网络生存性设计 摘要 随着社会生活的不断进步，通信在人们的工作、学习和生活中扮 演着越来越重要的角色。人们对通信质量的要求越来越高，网络生存 性逐渐成为通信网络组网技术的核心内容。光网络作为传送网的主要 形式，其生存性倍受关注。随着网络结构的不断演进，格网成为了智 能光网络的典型网络结构，格状网络的生存性研究成为了一大热点。 p 圈同时具有格网的高容量效率与环网的快速业务恢复速度，是未来 光网络生存性方案的理想选择。 本论文主要对采用p 圈法实现格状光网络生存性的方案和算法 进行了研究。第一章简要介绍了格网的概念和光网络的生存性，并引 入了p 圈的概念；第二章对p 圈的评价体系、生成算法，和其在w d m 网络配置方案作出了介绍；第三章主要介绍了双链路故障的概念，分 析了采用p 圈实现双链路故障生存性的配置方案，同时提出了两种双 链路情况下的p 圈启发式算法；第四章描述了节点故障，并对节点故 障的生存性进行了分析，提出了两种节点故障条件下的p 圈启发式算 法；第五章对基于o p n e t 软件开发的a s o m m 网络生存性平台 作了简要的介绍，并说明了论文中涉及到的仿真环境的设置；最后一 章对未来的发展方向作出了一些探索。 总的来说，论文的主要创新工作有： 1 提出了一种基于对偶圈合并法则的p 圈预选算法和一种 w d m 网络中的有向p 圈配置策略，并进行了仿真： 2 对格状光网络中的双链路故障进行了分析，提出了两种双链 路故障时的p 圈配置算法，并进行了仿真； 3 对格状光网络中的节点故障及其生存性实现方案进行了分 析，提出了两种节点故障时的p 圈配置算法，并进行了仿真； 4 参与开发了有特色的a s o 啪m 生存性仿真平台，实现了 p 圈的生存性仿真，并且能支持传统的生存性方案的仿真， 如1 + 1 、重路由等。 关键词：格状光网络生存性p 圈双链路故障节点故障仿真 北京邮电大学硕士学位论文 s u r v i v a b i u t yd e s i g no fm e s ho p t i c a l n e t w o r kb a s e do npc y c l e a b s t r a c t t h er o l eo fc o m m u n i c a t i o ni np e o p l e sd a i l yl i f eb o c o m e sm o 佗a n dm o r e i m p o r t a n t , a n dt h er e q u i r e m e n to ft h eq u a l i t yo fc o m m u n i c a t i o n i sb e c o m i n gh i g h e r s i n c et h ed e m a n df o rh i 曲q u a l i t yc o m m u n i c a t i o nh a si n c r e a s e do b v i o u s l y ，t h e s u r v i v a b i l i t yo ft h en e t w o r k sb e c o m e s ak e yf i e l di nc o m m u n i c a t i o nn e t w o r kp l a n n i n g o p t i c a ln e t w o r ki st h em a i nf o r mo ft h et r a n s m i tn e t w o r k , a n di t ss u r v i v a b i l i t yi st h e f o c u so fn e t w o r kt e c h n o l o g yr e s e a r c h a st h en e t w o r ke v o l v e s ，m e s hn e t w o r kh a s b o c o m eat y p i c a lt o p o l o g yo fi o n ( i n t e l l i g e n c eo p t i c a ln e t w o r k ) p - c y c l e ，w h i c h h a sf a s tr e c o v e r i n gs p e e da st h er i n gn e t w o r kd o e s ，a n dh a sh i g h l ye f f i c i e n c ya st h e m e s hn e t w o r kd o e s ，p l a y sav e r yi m p o r t a n tr o l ei nt h ec u r r e n tn e t w o r ks u r v i v a b i l i t y t h ed i s s e r t a t i o nf o c u s e so nt h er e s e a r c ho fs u r v i v a b i l i t yo fm e s ho p t i c a ln e t w o r k b a s e do np - c y c l e t h ef i r s tc h a p t e ri n t r o d u c e dt h ec o n c e p to fm e s hn e t w o r ka n d o p t i c a ln e t w o r ks u r v i v a b i l i t y , a n da l s ot h ec o n c e p to fp - c y c l e c h a p t e r2 i n t r o d u c e d t h ep r i m a r ye l e c t i o na l g o r i t h m so fp - c y c l e ，a n dt h ec o n f i g u r a t i o no fp - c y c l ei nw d m n e t w o r kw a sd i s c u s s e d c h a p t e r3a n a l y z e dt h ed u a ll i n kf a i l u r ei nm e s ho p t i c a l n e t w o r k , a n dp r o p o s e dt w oh e u r i s t i ca l g o r i t h m so fp - c y c l ed e p l o y m e n t c h a p t e r4 d i s c u s s e dt h es u r v i v a b i l i t yo fn o d ef a i l u r e ，ap - c y c l ec o n f i g u r es c h e m ew a sp r o p o s e d , a n d2h e u r i s t i ca l g o r i t h m sw e r eg i v e n c h a p t e r5i n t r o d u c e dt h es u r v i v a b i l i t y s i m u l a t i o np l a t f o r mb a s e do no p n e t , a n dt h ee n v i r o n m e n tc o n f i g u r a t i o no ft h e s i m u l a t i o ni nt h ed i s s e r t a t i o nw a sd i s c u s s e d a n da no u t l o o ko ff u r t h e rr e s e a r c hw a s m a d ei nt h el a s tc h a p t e r t h em a i nw o r ko ft h i sd i s s e r t a t i o ni sl i s t e da sf o l l o w i n g ： 1 ap r i m a r ye l e c t i o na l g o r i t h mo fp - c y c l eb a s e do nc o u p l e dc y c l ec o m b i n a t i o nw a s p r o p o s e d , t h ep r o t e c t i o nm e c h a n i s m b a s e do nd i r e c t i o n a lp - c y c l ew a sg i v e n 2 t h ed u a lr i n kf a i l u r ei nm e s ho p t i c a ln e t w o r kw a sd i s c u s s e d , t w oh e u r i s t i c a l g o r i t h m sw e r ep r o p o s e d ，a n dw e r es i m u l a t e do na no p n e t s i m u l a t i o np l a t f o r m 2 北京邮电大学硕十学位论文 3 t h en o d ef a i l u r ea n di t ss u r v i v a lm e c h a n i s mi nm e s ho p t i c a ln e t w o r kw e r e d i s c u s s e d ，t w oh e u f i s t i ca l g o r i t h m sw e r eg i v e n ，a n dw e r es i m u l a t e do na no p n e t s i m u l a t i o np l a t f o r m 4 as u r v i v a l b i l i t ys i m u l a t i o np l a t f o r mo fa s o n w d mw a sb u i l t ，a n da l lt h e p r o p o s e da l g o r i t h m sa n dp - c y c l ec o n f i g u r es t r a t e g yw e r es i m u l a t e d o ni t k e yw o r d s ：m e s ho p t i c a ln e t w o r k ；s u r v i v a b i l i t y ；p _ c y c l e ；d u a ll i n kf a i l u r e ； n o d ef a i l u r e 3 北京邮电人学硕上学位论文 第一章绪论 第一章绪论 随着d w d m ( d e n s ew 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 ) 的普遍应用，光纤 成为了通信网络的主要传输媒质。目前的光传送网主要以环状结构为主，难以实 现光路由的最优化，在网络故障时难以实现先进的业务生存性方案。为解决这一 问题，光网络的拓扑结构将逐渐往格状( m e s h ) 拓扑发展。同时，在光传送网 中引入信令和动态交换的能力，以提高网络的智能性和网络的连接管理与故障恢 复能力。 在这一思想的影响下，基于格状网络拓扑的下一代光传送网逐渐成为人们议 论的热点【1 1 。而由于光传送网所承载的业务越来越巨大，且人们对通信质量的要 求越来越高，光网络的生存性成为了人们研究的一个焦点1 2 1 1 3 1 。 本章首先介绍了格网的概念，接着阐述了网络生存性的概念、生存性的研究 历史及光网生存性的重要性，最后概述了本论文的主要工作和创新点。 1 1 格网结构 目前人们对格网的概念尚没有公认的的准确定义，文献中关于格网概念的叙 述大致有以下几类： 格网是指网络中存在一个以上的节点，该节点的度( 与其直接相连的边的数 目) 大于2 ( 环形网络中每个节点的度均为2 ) 【4 l 。 在保持连通的情形下，所有网络节点之间至少存在两条不同的物理连接的非 环形拓扑便为格i 碉 s l 。 格网是一种至少有两个节点之间存在两个或多个连接路径的网络拓扑【6 】。 当涉及通信的许多点直接互联时就形成了格网i _ n 。 如果网络中任意两个节点间均有直接相连的链路，则称之为完全格网或理想 格网；去除完全格网中的一些链路链路( 不能造成拓扑分离或连通度过低) ，即 为部分格网。通常人们所说的格网就是指部分格网。 网络的拓扑结构是描述网络特征的一个重要参数，选择一个合适的拓扑可以 极大地提高通信网络地性能。在w d m 技术刚开始使用时，光网络地拓扑以点对 点结构为主。s d h 技术的成熟与大规模地应用，使得光网络的拓扑逐渐发展成 为环状结构，而智能光网络技术的日渐成熟，将推动光网络拓扑结构向格状方向 发展。 与传统的环形网络相比，格网主要具有以下三个方面的优势【4 l ： ( 1 ) 高效直达、方便扩容； 北京邮电大学硕士学位论文 第一章绪论 ( 2 ) 可以对抗多重失效； ( 3 ) 更有效的备用带宽利用效率。 点到点的w d m 链路 1 2 光网络生存性 环形拓扑网络格状拓扑网络 图1 - 1 网络拓扑结构的演进 网络生存性是指网络在经受各种故障后能够维持可接受业务量的能力，属于 网络完整性的一部分。完整性包括通信质量、可靠性和生存性，涉及通信系统的 多方面技术。网络生存性定义为网络抵制故障业务中断或干扰的能力，即在网络 发生任何故障后能尽快将受影响的业务重新选路到空闲资源，以减少因故障而造 成的社会影响和经济上损失，使网络维护在一个可以接受的业务水平的能力【2 】。 影响网络生存性的因素通常有以下三方面原因【9 j ： ( 1 ) 业务高度集中，使得元件失效的影响成倍放大； ( 2 )软件错误的影响； ( 3 ) 自然灾害和人为破坏等。 1 2 1 生存性概念 由于w d m 技术的飞速发展，单根光纤中承载的业务越来越巨大，基于 d w d m 密集波分复用技术的光网络可以提供庞大的点对点容量每根光纤传 输容量高达驯s 。这使得任何形式的光传送网故障都会带来极其巨大的损失。光 纤作为传输介质其优点包括低损耗、轻便、抗电磁波、高带宽、低成本等等。不 管光纤及系统的技术如何先进，均是基于线缆的技术，是非常脆弱的。而光传送 网的网络结构越来越复杂，使得网络故障的修复也更加困难。据美国f c c 报告， 每两天就有一次影响3 0 ，0 0 0 客户的网络故障发生，而故障修复的平均时间是5 1 0 个小时 9 1 。如果传输容量达t b s 的单根光纤的失效，将影响1 , 2 0 0 万对以上的电 话业务【l o l 。所以在通信日益发展的今天，对网络的生存性进行深入研究不仅具有 理论意义，而且具有重要的实用价值。而以下几个因素导致目前对生存性的研究 日益重视1 9 l ： 北京邮电大学硕士学位论文第一章绪论 ( 1 ) 光纤技术的发展； ( 2 ) 电信市场的开发和竞争加剧； ( 3 ) 通信业务空前的增长，特别是互联网的业务和应用； ( 4 ) 社会对通信的依赖越来越强。 由此，使得寻找一种新的、高效快速的生存性设计方案具有了重要的动机。 1 2 2 光网络生存性技术 网络生存性在实现时主要分为保护和恢复两大类。保护是指在故障发生之前 预先为业务设定保护路径，并预留资源的生存性实现方式；而恢复是在故障发生 之后，再依据网络拓扑和资源占用状况为故障业务寻找代替路由的生存性实现方 式。一般来讲，保护方式具有较快的业务恢复速度，但无论是否发生故障，都需 要为业务预留备用资源，资源冗余度较大。而恢复方式不需要为业务预留备用资 源，网络的资源冗余度较低，但故障发生后，受损业务需要较长的时间才能恢复。 在电信级业务中，要求故障业务能够实现5 0 m s 量级的恢复速度，故在实际 电信网络中，保护方式应用比较广泛；而在互联网应用中，对恢复时间的要求不 是很高，较多采用恢复的方式。 随着传输技术和网络技术的发展，保护恢复方法已经得到广泛而又深入的研 究，目前已经成熟的生存性技术最为典型的就是s d h 网的保护恢复方法，s d h 网络中的生存性技术可分为保护倒换和恢复方案1 6 j 。其中，自动保护倒换( a p s ) 和自愈环( s 陬) 是s d h 网络中最常用的保护方法。 此外，动态恢复方式是指在网络故障时，动态地发现网络的空闲资源来恢复 受影响的业务。恢复方式比保护方式具有更高的资源使用效率，但恢复方式需要 的时间更长，且不能确保1 0 0 的业务恢复率。在s d h 网络中用数字交叉连接系 统( d x c ) 和控制器把多个环网连接起来形成格状网络，可实现动态的资源恢复 功能。控制器可以用集中或分布方式来完成路由和波长分配( r w a ) 算法。 一 a 生存性技术基本分类 尽管生存性技术多种多样，但是它始终都是以最基本的生存性技术为基础。 基本生存性方案除了包括纯保护方案，纯恢复方案外，还包括介于二者之间的中 问型生存性方案。即预置恢复。分类的原则是替换路由的寻找是否在故障前已完 成，和空闲容量的交叉连接是否在故障前已就位，这也是影响每个生存性方案倒 换时间的两个因素。 纯保护：即传统的保护方案，预先知道保护路由，空闲容量预先进行连 接，故障发生时只需在端点进行倒换，如：1 + 1a p s 3 2 ，u p s r ，b l s r ，p c y c l e s 。 北京邮电人学硕上学位论文第一章绪论 纯恢复：即传统的恢复方案，恢复路由在故障发生后进行计算得到，那 么恢复路由的交叉连接和倒换需要实时进行，如：分布式路由算法 d r a ( d i s t r i b u t e dr e s t o r a t i o na l g o r i t h m ) 。 预置恢复方案：即中间型方案，替换路由己提前计算得到且每个节点的 交叉连接映射已就位，恢复路径集合的交叉连接和倒换需实时进行，如：分布式 预置的区段恢复s r - d p p ( s p a nr e s t o r a t i o nu s i n gd i s t r i b u t e dp r e p l a n n i n g ) ，共享备 份路径保护s b p p ( s h a r e db a c k u pp a t hp r o t e c t i o n ) ，区段共享保护s l s p ( s e g m e n t e d o rs h o r t l e a ps h a r e dp r o t e c t i o n ) 。 b 光网络生存性技术分类 光网络中的生存性技术可以从不同的角度进行分类【1 4 1 ，主要包括： 根据备用资源的分配是在故障发生的前后，可分为保护和恢复两种方案； 按照处理层次来分，可分为单层和多层网络生存性问题，而多层网络的 生存性是指在分层网络之间生存性方案的嵌套以及这些方案之间的相互作用； 从保护策略上来分，有基于链路和通道的保护、共享和专用资源保护等； 从恢复的策略上来分，包括基于链路的和基于通道的故障恢复、预先规 划和动态计算的故障恢复等； 从控制方式的角度来说，有基于集中式控制和分布式控制的故障恢复； 依据适用的故障类型，有针对单链路故障、单节点故障和多点故障的生 存性机制。 c 智能光网络生存性技术分类 关于智能光网络( i o n ：i n t e l l i g e n to p t i c a ln e t w o r k ) 生存性技术的研究所出 现的热点问题和新的领域【1 5 l 【1 6 l ，主要可以包括以下方面： 格状拓扑下的网络生存性：智能光网络的拓扑结构是格状的，格状网络 连通度大，网络拓扑的生存性高。在i o n 环境下，研究和提出适用的格状光网 络的保护恢复机制具有重要的意义： 区分生存性业务：智能光网络中可实现多种生存性策略，而用户也有不 同的业务需求，故区分生存性业务成为了智能光网络引人注目的一项服务； g m p l s 控制协议实现生存性：控制平面的引入为在i o n 中实现多样的、 高效的生存性机制提供了强有力的手段，而g m p l s 协议中的信令、路由和资源 管理机制也需要进行不断的改进以实现i o n 中智能化的生存性要求； 控制平面的生存性技术：控制平面是i o n 中的核心层面，它负责了传送 平面中业务的可靠传输，值得注意的是它自身也需要有相应的生存性机制保证其 正常的工作，这也是i o n 中所特有的新问题； 北京邮电大学硕士学位论文第一章绪论 多层网络的生存性：网络层次结构的发展由复杂逐渐趋向简单，i p i o n 的结构将成为未来网络发展的趋势。如何在这样的多层网络结构下保证生存性策 略的协调实现，成为了智能光网络出现以后需要解决的问题之一； 多粒度光网络的生存性：多粒度交换技术是智能光网络中传送平面的一 项重要技术，它在节约网络成本的基础上能够合理地疏导网络中不同粒度的流 量，实现资源的优化利用。原有传统光网络中的生存性技术都是基于单波长粒度 的，因此，多粒度环境下保护恢复机制的研究就成为了i o n 生存性技术中需要 迫切解决的关键问题之一。 光网络从点对点的线形拓扑，演进到环网，再演进到格网；光网络的生存性 方案也从点对点的( 线性复用保护) 拓扑的生存性方案：1 ：1 ，i + i ，i ：n ，演进 到环的保护方法：两纤单向通道保护( u p s r ) ，两纤双向复用段保护( b l s r ) 和四纤双向复用段保护，再演进到格网的生存性方案：d r a ，s r d p p ，s b p p ， s l s p ，p - c y c l e s ( p r e - c o n f i g u r e dp r o t e c t i o nc y c l e s ，p 圈) 1 3p 圈原理 在相当长的一段时间内，网络生存性有两种基本却又截然不同的实现方案： 基于环的生存方案和基于格状网络的生存方案1 1 7 】。基于环的方案包括双向复用段 保护环( b i - d i r e c t i o n a ll i n es w i t c h e dr i n 蓼，b l s r ) 、单向通道保护环( u n d i r e c t i o n a l p a t hs w i t c h e dr i n g s ，u p s r ) 、光共享保护环( o p t i c a ls h a r e dp r o t e c t i o nr i n g s ，o s p r ) 等。由于环保护方案采用了非常简单的保护倒换机制，使得它能够在5 0 m s 内实 现故障业务的恢复。但是，它需要至少1 0 0 的资源冗余备份，而在实际的复杂 环状结构网络中，甚至能够达到2 0 0 3 0 0 ! r n 。格状网络的传输系统嵌入了 数字交叉连接系统( d i g i t a lc r o s s - c o n n e c ts y s t e m s ，d c s ) ，能够实现集中或分布 式的控制，典型的格网恢复机制多以此为基础。由于采用了动态的路由机制，格 网中的空闲容量都能够得到重新利用，具有很高的资源利用率。但分布式重路由 会耗费较长的时间，使得格网的故障业务恢复时间比环网要长。 在p 圈的概念提出以前，组网时都面临着生存性实现方案非此即彼的选择问 题。1 9 9 8 年，加拿大a l b e r t a 大学的g r o v e r 教授领导的生存性研究小组提出了一 种新型生存性方案i 墙l ，该方案以环结构为基础，利用预先设定的环形保护通道来 实现格状网络中的快速保护，即通常所说的p 圈法。它与其他一些基于环的保护 方案，如增强环法、单向环双重覆盖法等，最大的区别在于能够同时为圈上链路 和跨接链路提供保护1 1 9 1 。 图1 2 描述了一个基本的p 圈的配置情况和其工作方式。 北京邮电大学硕十学位论文 第一章绪论 b 上链路故障时p 圈的保 护倒换方式 c 跨接链路故障时p 圈的保 护倒换方式 工作链路保护链路- _ 卜保护倒换= = ：z 故障 图1 - 2p 圈的配置和工作方式 图1 - 2 ( a ) 中的粗线部分即为一个在网络中配置的p 圈，在这些链路上，预 留了一部分保护资源，形成一个预配置的保护环( 即p 圈) 。当该环上的某条链 路发生故障时，该链路所承载的业务将按照预先设定好的方式，倒换到预先配置 的保护环上去，如同s d h 环网所做的一样，如图1 2 ( b ) 。1 2 ( c ) 描述了跨接链路 发生故障时p 圈的工作方式。所谓的跨接链路是指链路的两个端点都在环上，但 其本身不在环上的链路。当这样的链路发生故障时，有两条保护路径可供选择， 也就是说，一个p 圈能够保护其跨接链路上的两份业务，这正是p 圈高容量效率 的体现。像这样的一个p 圈，能够保护7 条圈上链路和4 条跨接链路。若在p 圈的每条链路上配置了一份保护资源，则每条圈上的链路上的一份工作资源、跨 接链路上的两份工作资源能够得到保护，即该p 圈的容量效率= ( 7 4 - 4 宰2 ) 6 = 2 5 ( 其中容量效率定义为工作资源与保护资源的比例) ，而在s d h 环网中，容量 效率仅为1 。同时，由于预先配置了保护资源，当故障发生时，受损业务将按照 预先设定好的路径进行倒换，不必进行费时的重路由工作，使得p 圈具有了环网 般的快速业务恢复能力。 1 4 论文主要工作及贡献 光网络的生存性研究已经成为网络规划和设计的重要组成部分，同时也是光 网络研究精细化的重要一部分。随着网络的演进，格网已成为智能光网络的典型 网络结构。而p 圈由于具有环网的倒换速度和格网的容量效率，基于p 圈的格网 生存性研究已成为目前网络生存性研究的一大亮点。 本论文主要研究基于p 圈的格状光网络的生存性问题。第一章简要介绍了格 网的概念和光网络生存性的重要性、主要生存性技术等，并介绍了p 圈的基本概 念；第二章介绍了p 圈的评价体系、生成算法和光网络中p 圈的配置方案；第三 章分析了双链路故障条件下的生存性实现条件，并提出了采用p 圈实现双链路故 障生存性的设计方案；第四章对节点故障条件下光网络生存性进行了分析，并阐 北京邮电大学硕上学位论文 第一章绪论 述了采用p 圈实现节点故障生存性的设计方案；第五章介绍了用o p n e t 软件搭 建的a s o n 光网络生存性平台，以及采用该平台实现p 圈生存性方案的配置方 式；第六章对论文的工作进行了简要的总结，并对后续的研究方向进行了展望。 总体来讲，论文的主要创新工作有： ( 1 ) 提出了一种基于对偶圈合并法则的启发式p 圈生成算法，在c o s t 2 3 9 和 n s f n e t 网络拓扑上的仿真证明了该算法的可行性和有效性。 ( 2 ) 提出了一种w d m 双向光网络中基于有向圈的保护p 圈配置方案，并在 c o s t 2 3 9 和n s f n e t 网络拓扑上进行了仿真，仿真结果证明了该方案能有效地 降低网络资源冗余度。 ( 3 ) 提出了两种双链路故障条件下采用p 圈实现网络生存性的启发式算法， 在c o s t 2 3 9 网络上的仿真证明了算法能有效地降低网络资源冗余度。 ( 4 ) 提出了采用p 圈实现节点故障生存性的配置方案，和两种启发式算法， 并在c o s t 2 3 9 和n s f n e t 网络拓扑上进行了仿真，仿真结果证明了算法的可行 性和有效性。 ( 5 ) 采用o p n e t 软件搭建了a s o n 生存性仿真平台，实现了上述算法的仿真， 并与一些传统的生存性方案，如1 + 1 、1 ：1 、重路由等，进行了比较，验证了p 圈生存性设计方案的优势。 参考文献： 【1 1 1韦乐平智能光网络的发展与演进结构现代电信科技，2 0 0 2 ( 0 4 ) 【2 1 韦乐平下一代网络生存性的总体考虑世界电信，2 0 0 0 ( 6 ) 【3 】3k a r t a l o p o u l o ssv s u r v i v i n gad i s a s t e r 【j 】c o m m u n i c a t i o n sm a g a z i n e ，i e e e 2 0 0 2 ，4 0 ( 7 ) 【4 】倪斌，”网格状网络的设计探讨，。邮电设计技术，2 0 0 5 ( 9 ) 【5 】顾畹仪，张杰，全光通信网北京：北京邮电大学出版社，2 0 0 1 【6 】八c t i a l ”n e t w o r kt o p o l o g y 。 h t t p ：w w w a t i s o r g t 9 2 k n e t w o r k _ t o p o l o g y h t m l , p u b l i s h e db y a l l i a n c ef o r t e l e c o m m u n i c a t i o n si n d u s t r ys o l u t i o n s 1 7 】韦乐平，光同步数字传送网北京：人民邮电出版社，1 9 9 8 年1 2 月第2 版 【8 】韦乐平，”智能光网络的概念、体系架构和演进路线，”当代通信，2 0 0 3 ( 0 7 ) 【9 】wd g r o v e r , m e s h b a s e ds u r v i v a b l en e t w o r k s ：o p t i o n sf o ro p t i c a l , m p l s ，s o n e t , a n d a t mn e t w o r k i n g u p p e rs a d d l er i v e r , n j ：p r e n t i c eh a l lf i r , a u g 2 0 0 3 【1 0 1 王健全，徐荣，牟春波，顾畹仪，纪越峰，。2 1 世纪光通信技术发展趋势预测，”遥詹趔冕 2 0 0 1 ( 1 0 ) 【1 1 】s r a m a m u r t h y , b m u k h e r j e e ，。s u r v i v a b l ew d m m e s hn e t w o r k s p a r ti - p r o t e c t i o n ，”j o u r n a l o fl i g h t w a v et e c h n o l o g y , v 0 1 2 1 ，p p 8 7 0 - 8 8 31 9 9 9 ( 4 ) 1 2 三匕京邮电人兰堕士学位论文 第一章绪论 【1 2 】s r a m a m u a h y ，ls a h a s r a b u d d h e ，b m u k h e r j e e ，”s u r v i v a b l ew d mm e s hn e t w o r k s i i r e s t o r a t i o n , ”p r e s e n t e da t1 9 9 9i e e ei n t e r n a t i o n a lc o n f e r e n c ec o m m u n i c a t i o n s ，2 0 0 3 【1 3 】八f u m a g a l l i ，i c e r u t t i ，m t a c c a , em a s e t t i ，r j a g a n n a t h a n ，s a l a g a r , 。s u r v i v a b l e n e t w o r k sb a s e do i lo p t i m a lm u t i n ga n dw d m s e l f - h e a l i n gr i n g s ，”p r e s e n t e da ti n f o c o m 9 9 e i g h t e e n t h a n n u a lj o i n tc o n f e r e n c eo ft h ei e e ec o m p u t e ra n dc o m m u n i c a t i o n s s o c i e t i e s p r o c e e d i n g s , 1 9 9 9 【1 4 】ed e m e e s t e r , m g r y s e e l s ，八a u t c n r i e t h ，c b r i a n z a , lc a s t a g n a ，gs i g n o r e l l lr c l e m e n f e ，m r a v e r a ，aj a j s z c z y ld j a n u k o w i c z , kv a nd o o r s e l a e r e ，yh a r a d a , ”r e s i l i e n c ei nm u l t i l a y e rn e t w o r k s ，。c o m m u n i c a t i o n sm a g a z i n e ，i e e e , v 0 1 3 7 ，p p 7 0 - 7 6 ， 1 9 9 9 ( 8 ) 【1 5 】张杰，徐云斌，宋鸿升等自动交换光网络a s o n 北京：人民邮电出版社，2 0 0 4 年2 月 第一版 【1 6 】s d em a e s s c h a l c ld c o l l e ，ag r o e b b e n s , c d e v e l d e r , 八l i e v e n s ，el a g a s s e ，m p i c k a v e t ，ed e m e e s t e r , es a l u t a , m o u a g l i a t t i , ”i n t e l l i g e n to p t i c a ln e t w o r k i n gf o rm u l t i l a y e r s u r v i v a b i l i t y , ”c o m m u n i c a t i o n sm a g a z i n e ，e e e , v 0 1 4 0 ，p p 4 2 - 4 9 ，2 0 0 2 ( 1 ) 【1 7 】wdg r o v e r , ds t a m a t e l a k i s b r i d g i n gt h er i n g - m e s hd i c h o t o m yw i t hp - c y c l e s c p r o c e e d i n g so fd e s i g no fr e l i a b l ec o m m u n i c a t i o nn e t w o r k s ( d r c n2 0 0 0 ) , g e r m a n y , a p r i l 9 - 1 2 ，2 0 0 0 【1 8 】w d g r o v e r , d s t a m a t e l a k i s ，。c y c l e - o r i e n t e dd i s t r i b u t e dp r e c o n f i g u r a t i o n ：r i n g l i k e s p e e dw i t hm e n - l i k ec a p a c i t yf o rs e l f p l a n n i n gn e t w o r kr e s t o r a t i o n , ”p m c i e e ei c c 9 8 ， p p5 3 7 - 5 4 3 【1 9 】wdg r o v e r u n d e r s t a n d i n gp - c y c l e s , e n h a n c e dr i n g s , a n do r i e n t e dc y c l ec o v e r s i n t s c o n f e r e n c eo i lo p t i c a lc o m m u n i c a t i o n sa n dn e t w o r k s 0 c o c n ) ，s i n g a p o r e ，n o v 1 1 1 4 ，2 0 0 2 一1 3 北京邮电人学硕士学位论文第二章p 圈的生成与配置 第二章p 圈的生成与配置 p 圈法是在网络规划阶段就已经为业务预先配置了一系列保护圈的生存性 方案。在p 圈配置过程中，首先是为工作通道在网络拓扑图上选择最短的直达路 由，然后使用空闲的网络资源设置一系列环状的预先连接的封闭通道( 即p 圈) 对这些工作通道进行保护。p 圈可以设置成为网络中固定的圈结构( 就像在s d h 网络中保护资源的配置一样) 或者作为一组虚拟圈进行动态配置。p 圈的设置发 生在任何网络故障之前，并且在故障对所要求的实时倒换动作都是预先设计好 的，因此可以实现快速的故障恢复。p 圈可由集中式的网络管理系统负责完成配 置，或者通过分布式协议进行搜索。集中式配置就是网络管理人员按照某种特定 的策略，静态对根据已经计算出的备选p 圈集合，为每一个业务分配一个或者多 个p 圈。而分布式配置则是使用些协议，通过使用信令对p 圈进行自动的配置。 2 1p 圈设计方案的求解 在网络生存方案的设计中存在两个设计目标，即有两类混合整数规划 ( m i x e di n t e g e rp r o g r a m ，m i p ) 方程解决生存性方案的设计问题，对基于p 圈 的生存性设计方案来讲也是如此【1 】【2 1 。这两种方案都可用于d w d m 和s d h 网络 的生存性设计。 第一类方程为“m a xr pls p a r e ”，即在网络可用资源给定的情况下，如何合 理的设计p 圈，使得业务恢复率最大化。第二类方程“m i ns p a r eir p = l 一，即在 要求1 0 0 的业务恢复率的情况下，如何使p 圈所需要的空闲容量最小化。在格 网中，由于网络的资源状况是给定的，一般采用第一种设计方案。 对m i p 方程的求解可采用整数线性规划( i n t e g e rl i n e a rp r o g r a m s ，i l p ) 和启 发式算法两种方式。m 腰方程是一个全局性最优化问题，对它的精确求解是一个 n p ( n o w p o l y n o m i a l ) 闯题。若采用p 求解，在l 网络规模较大对会非常复杂， 表达式繁琐，计算速度很慢甚至不能求解，而启发式算法能够快速而有效地解决 此类问题，并接近最优解【3 1 。所以，在p 圈网络设计中普遍采用的是启发式算法。 针对格状网络中的p 圈配置问题，研究人员提出了一种名为c i d a ( c a p a c i t a t e di t e r a t i v ed e s i g na l g o r i t h m ) 的启发式算法1 4 1 i s l ，针对网络的不同情况， 选取效率最高的p 圈作为网络配置的选择。主要的效率评价系数有：拓扑分值 o o p o l o g i c a ls o r e s 聊，先验效率( ap r i o r ie f f i c i e n c y - a e ) ，效率比值( e f f i c i e n c y r a t i o - e r ) ，和实际效率( c a p a c i t y - w e i g h t e de f f i d e n c y - c w e ) 等。效率评价系数是 启发式算法的核心，同时，采用预选算法对备用p 圈进行筛选，减少候选p 圈的 北京邮电大学硕上学位论文 第一二章p 罔的生成j j 配置 数量，以降低计算代价。所谓的预选算法即采用一定的优化算法来生成候选p 圈集合，而不用计算出网络中所有的可用圈集合，具体的算法将在2 3 节中介绍。 c i d a 的基本步骤如下： ( 1 ) 计算出一组候选的p 圈； ( 2 ) 计算每个圈的效率评价系数： ( 3 ) 选择效率评价系数最优的圈，并为其配置保护资源； ( 4 ) 更新未受保护工作资源的分布； ( 5 ) 返回步骤( 2 ) ，知道未受保护资源为0 或网络可用资源耗尽。 c i d a 算法可分为两个部分，一个是采用预选算法生成备用p 圈集合，另一 个是启发式的保护资源配置。文献【5 】对c i d a 算法的运行速度进行了分析，算法 的运行环境为1 3 g h za m da t h l o n 处理器和m s