（电磁场与微波技术专业论文）格状网中基于pcycle的环保护方案.pdf

北京邮电大学硕士学位论文 格状网中基于p - o y c l e 的环保护方案 摘要 现有的传送网络已经不能满足日益增长的数据业务的要求， a s o n 应运而生，它实现了网络的智能化，具有很高的灵活性。而光 传送网络也正在从传统的环状网向灵活性更高的格状网发展。格状 a s o n 网络抵御故障风险的能力是非常重要的，这样可以避免巨大的 社会影响和经济损失。因此，对格状a s o n 网络的生存性进行深入 研究不仅具有重要的实用价值，而且具有深远的理论意义。 本文以北邮一朗讯贝尔实验室联合项目“光网络的生存性”为背 景，首先介绍了预配置环( p 圈) 的概念和工作原理，并提出了一种 针对传送平面节点故障的p 圈算法节点环绕p 圈算法，描述了该 算法的思想、计算步骤、评价标准、优化以及配置资源的方法。 为了在a s o n 中实现基于p 圈的保护技术，本文还提出了两套 利用p 圈进行故障业务恢复的故障处理流程，包括对单链路故障、多 链路故障、单节点故障及多节点故障情况下的p 圈查询、保护倒换， 以及故障排除后将业务倒换回工作路径的整套处理机制与信令流程。 两套处理方案，一简一繁，各有所长，可以根据不同的要求选择其中 一种进行配置，对实际网络中p 圈功能的配置和实现有一定的参考价 值。 为了验证上面提出的p 圈算法和处理机制，在0 p n e t 仿真软件 中对a s o n 进行了网络建模，在仿真网络中实现了p 圈功能，并对 仿真结果进行了分析，得到了节点环绕p 圈和采用p 圈技术的a s o n 网络的一些性能参数，对p 圈在a s o n 中的应用提出了看法和建议。 关键词：格网预配置环生存性自动交换光网络信令机制 北京邮电大学硕士学位论文 p c y c l eb a s e dp r o t e c t i o ns c h e m e i nm e s hn e t w o r k s a b s t r a c t n o w a d a y s ，t h ee x i s t i n gt r a n s p o r tn e t w o r k s c a l l h a r d l yb e a rt h e e v e r - g r o w i n gd a t as e r v i c e s ，s oa s o ne m e r g e sa st h et i m e sr e q u i r e i t a d d si n t e l l i g e n c ea n da g i l i t yi n t ot h et r a n s p o r tn e t w o r k s a n dt h er i n g l i k e n e t w o r ki sa l s oe v o l v i n gt oam o r ef l e x i b l em e s h l i k en e t w o r k t h ea b i l i t yt os u r v i v ef r o mf a i l u r e si sv e r yi m p o r t a n tf o rm e s h a s o nb e c a u s ei tc a nh e l pt h en e t w o r ka v o i db i gl o s so fm o n e ya n d s i d e e f f e c ti nt h e s o c i e t y t h e r e f o r e ，r e s e a r c h o nm e s ha s o n s u r v i v a b i l i t yi so fg r e a tp r a c t i c a lv a l u ea n di sm e a n i n g f u lf o rt h e o r e t i c a l r e s e a r c h t h i s p a p e r i sb a s e do nt h e p r o j e c t s u r v i v a b i l i t y o fo p t i c a l n e t w o r k s ”c o - s p o n s o r e db y b u p ta n db e l ll a b sa n dl u c e n tt e c h n o l o g i e s t h e p a p e r f i r s t l y i n t r o d u c e st h e c o n c e p t a n dm e c h a n i s mo f p r e c o n f i g u r e dc y c l e sp - c y c l e ) ，a n dp r o p o s e sap - c y c l ea l g o r i t h mc a l l e d c y c l e ss u r r o u n d i n gn o d e s ，w h i c hi sd e s i g n e ds p e c i a l l yf o rn o d ef a i l u r e s t h e nt h ep a p e rd e s c r i b e st h ei d e aw h i c hl e a d st ot h ea l g o r i t h m ，t h e p r o c e d u r eo ft h ea l g o r i t h m ，t h ee v a l u a t i o ns y s t e mo ft h ea l g o r i t h m ，t h e o p t i m i z a t i o no ft h ec y c l e sa n dt h ea s s i g n m e n to fn e t w o r kr e s o u r c e so n t o t h ec y c l e s i no r d e rt oe q u i pa s o nw i t hp c y c l e s ，t h i sp a p e ra l s ob r i n g sf o r w a r d t w os e t so ff a i l u r ep r o c e s s i n gp r o c e d u r e sa n ds i g n a l i n gs c h e m e su s i n g p c y c l e s e a c h o ft h e mc o n s i s t so fs c h e m e sf o r s i n g l e l i n kf a i l u r e ， m u l t i p l e l i n kf a i l u r e ，s i n g l e - n o d ef a i l u r ea n dm u l t i p l e n o d ef a i l u r e t h e f a i l u r ep r o c e s s i n gi n c l u d e ss e a r c h i n gf o r p - c y c l e s ，p r o t e c ts w i t c h i n gw h e n t h ef a i l u r e a p p e a r sa n dr e v e r s i o n o ft h et w os e t so fs c h e m e s ，o n ei s s i m p l ea n dt h eo t h e ri sc o m p l i c a t e d ，a n dt l l e ye a c hh a v et h e i ra d v a n t a g e s 北京邮电大学硕士学位论文 w ec a nc h o o s eo n eo ft h e ma c c o r d i n gt ot h er e q u i r e m e n t s a n dt h e s e s c h e m e sc a nb eu s e df o rr e f e r e n c e t h i sp a p e ra l s oi n t r o d u c e st h ea s o ns i m u l a t i o np l a t f o r mb u i l tu s i n g o p n e t t h ef i n a lp a r to ft h ep a p e rg i v e ss o m eo ft h es i m u l a t i o nr e s u l t s f o rn o d ef a i l u r e su s i n gp - c y c l e a n dt h er e s u l t sa r ea n a l y z e da n dt h e p e r f o r m a n c e so ft h ec o m p l i c a t e ds c h e m ea n dt h ec y c l e ss u r r o u n d i n g n o d e sa l g o f i t h ma r e - a c q u i r e d k e yw o r d s ：m e s h ，p - c y c l e ，f a i l u r er e c o v e r y , a s o n ，s i g n a l i n g s c h e m e 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 笪磋援 日期：2 盟至1 2 主 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅：学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 塑座 ，刮! 猁曼 r 期：刍缸= 墨。堕 日期：2 鲤z t 丛 北京邮电大学硕士学位论文 1 1 引言 第一章绪论 自2 0 世纪9 0 年代开始，全世界的通信建设和应用明显地加快了前进步伐，进 入2 1 世纪后，继续向前快速推进。随着因特网的快速发展，i p 业务呈现爆炸式增 长，电信网络从以承载语音业务为主转向以承载数据业务为主，这给传送技术带来 了巨大的挑战，在传输的业务量上和传输的业务特性方面给传统的电信网络提出了 很高的要求。由于数据业务不同于话音业务，其所具有的自相似性、不对称性、动 态性、突发性等特点，对传送网络提出了动态、实时进行业务提供的要求。 现有的传输网络结构难以适应网络业务发展的需求。现今的传送网络结构最初 是为传输话音业务设计的，并不适用于高速数据网络业务。数据业务的迅速增长和 数掘业务需求的不可预见性，要求网络的配置必须具有良好的扩展性和比较低的成 本。但是现有的网络结构没有足够的灵活性去满足数据业务的要求，因为网络的管 理是采用手工配置的方式，带宽分配是静态的，网络的业务能力差，而且容量的扩 展需要网络提供商花费较多的资金和较长的时间。 因此以i p 为核心的数据业务和相应的网络支撑技术的发展是现代电信技术发展 的推动力，在通信的历史上揭开了新的一页。智能光网络( 1 0 n ) 作为一个为了适 应现代电信业发展的新型的网络破土而出，它的提出给现有传送网络带来一场革命。 智能光网络的最主要的变革是提供了一个网络的控制平面，通过控制平面为网络提 供相应的功能，改变了由网络管理系统来配置光交叉连接和光分叉复用设备提供光 路径的情况，从而实现网络的智能化。 智能光网络是下一代传送网的发展方向，自动交换光网络( a s o n ) 是智能光 网络的典型代表，它的提出是在原有概念和技术基础上的延续和发展，并且给现有 传送网络的体系结构带来重大的变革，对智能光网络的研究将有重要和深远的意义。 1 2 a s o n 生存性研究及其意义 网络的生存性( s u r v i v a b i l i t y ) 定义为网络抵制故障所造成的业务中断或干扰的 能力，也就是网络在发生任何故障后能将发生故障的资源中承载的业务倒换到其它 空闲的资源上，以减少因故障而造成的社会影响和经济损失，使网络维持一个可以 接受的业务水平的能力。 a s o n 生存性是指在自动交换光网络中，在网络出现故障的时候通过控制平面 的信息交互和自动资源调配功能，对网络动态的资源重新分配并对故障业务实施重 路由，以实现对网络故障实现动态的恢复，减小网络故障给业务带来的影响。 北京邮电大学硕上学位论文 生存性就是要保障故障恢复率及恢复时间与资源利用率之间的权衡，最大的生 存住就是使恢复时间最小的同时最大化资源利用率。 a s o n 中生存性技术主要包括保护技术和恢复技术。 保护( p r o t e c t i o n ) 就是在网络中预先为业务分配保护路径，发生故障后将受影 响的业务倒换到事先已连接好的保护路径上去。 恢复( r e s t o r a t i o n ) 是指在网络中并不对业务预先分配保护资源，而是在发生故 障后再在可用容量上根据一定的算法和策略选择并建立新的业务路径。 这两种方式各有优缺点： 保护方式下，由于在故障发生之前就对可能发生的故障进行了准备，为业务分 配了已经连接好的保护路径，故障时只需简单地将业务倒换到保护路径上去业务就 可以继续进行，因此业务受到故障影响的时间较短，恢复时间快。但是由于在故障 未发生时就占用了部分网络容量作为保护资源，这种方式下网络资源利用率相当较 低。 恢复方式中，由于在网络中是在故障发生后再采取措施对故障业务重新计算、 建立路由，这一系列操作需要消耗较多的时间，因此业务受故障影响需要中断较长 的时间，恢复时间相对慢。但是这种策略相对灵活，故障发生后结合网络中资源的 使用状况为业务重路由，网络资源的利用率相对较高。 现有的保护技术有1 + l ，1 ：1 ，m ：n ，p - c y c l e 等，恢复技术有快速重路由技术等。 1 3 p c y c l e 的引出 环形结构是当前主导的网络拓扑，它的一个很大的优点就是能够进行5 0 毫秒内 的业务快速保护倒换。但同时它也有两大弊端，一是当网络规模扩大或者业务模式 发生变化时，扩展带宽的难度大、成本高；二是为保证快速的业务保护，网络至少 需要1 0 0 的冗余量( 冗余量为预留的备用容量与工作容量之比) 。 环网保护虽然能够快速地实现业务保护，但它是以牺牲网络5 0 的资源换得的， 因此会给运营商带来竞争上的压力。同时，面对网络上承载的越来越多的不同类型 业务，它们对保护恢复的要求是不同的，比如语音业务要求在5 0 毫秒以内得到恢复， 而电子邮件等非即时业务能够容忍的恢复时间就非常长，这就要求光网络能够提供 更多的保护恢复方式，特别是提供更加灵活的恢复机制，不仅能在较短的时间内恢 复中断的业务连接，而且能够有效地节省网络资源。 与环网比较起来，格状( m e s h ) 光网络以其灵活的选路方式、高度的网络连接 性以及有效的资源利用率更具优势，它的优点包括其选路灵活性高、资源使用效率 高、生存性效率高、扩容简单、组网成本低等。因此，光传送网络由环形网络向格 状网络发展是大势所趋。 北京邮电大学硕士学位论文 表1 1 环形网与格状网络的对比 环形光网络格状光网络 组网方式单环或相连的多个环格状 建设成本 较高较低 相同业务条件下配置所需容量较大较小 扩容升级复杂度较大较小 预留的备份容量5 0 小于3 0 带宽利用率低高 按需提供保护( p r o t e c t i o n o n d e m a n d ) 不支持支持 依具体的生存性策略 m t t r ( 平均故障修复时间)小于s o 毫秒 而定 灵活性 小大 下面简单况明为什么格状网络比环形网络效率高。 在传统s d h 的环形网络中，每个节点的连通度均为2 。而在基于a s o n 的格状 网络中，为实现故障恢复而预留的资源可被网络中的所有业务共享，这与传统光网 络中的保护带宽资源被单条业务独占( 如线性l + l 、s n c p ) ，或只被有限业务共 享( 如复用段环的保护带宽只被环上业务共享) 不同。 a s o n 格状网络的保护恢复技术受益于网络较高的连通度，连通度越高则恢复 的可能性越大，连通度每增加l ，网络的可靠度就会增加至少1 个数量级。并且由 于需要预留的带宽资源和连通度成反比，因此连通度的增加可以显著提高网络资源 利用率。连通度达到6 时，就已经可以得到足够的网络可靠度。更高的连通度对提 高网络可靠度的影响较小。 鉴于以上优点，随着对光网络智能化的要求不断提高和各种设备的逐渐商业化， 格状网将会成为光网络的主流拓扑结构，因此基于格状网的生存性技术将成为 a s o n 网络生存性的主要技术。 在从环网向着格状网发展的前进中，我们希望把原有s d h 自愈环成熟的保护 机制拓展到格状网络中，使格状网络也能拥有快速的故障恢复速度。但是由于环网 中资源利用率低，需要有与工作容量相同的保护容量对业务进行保护。因此，人们 对在格状网络中的环保护方法进行了改进，提出了p - c y c l e ( 预配置圈，p r e - c o n f i g u r e d c y c l e s ) 保护法。 北京邮电大学硕士学位论文 1 4 论文的研究内容及主要工作 论 文 主 要 工 作 图l 一1 本文组织结构图 a s o n 的提出为格状网络结构的应用和发展提供了必要的条件，格状网凭借其 在网络资源的使用效率、组网灵活性等方面的优势成为未来光网络的主流结构。对 格状光网络的生存性研究也是势在必行，并具有深远的意义。本论文的主要工作就 是研究格状a s o n 网络基于p 圈的生存性方案，提出一种对节点故障更为有效的p 圈算法，并根据p 圈的特殊性对a s o n 控制面信令方案迸行研究，提出了两套对各 种故障情况的处理机制。论文的结构安排如图1 - 1 所示。 第一章：绪论。对a s o n 网络及其生存性技术的背景、研究方向做了分析，阐 明了a s o n 生存性研究的重要意义，由网络结构由环状向格状发展引出了p 圈的概 念，为进一步深入论述做了铺垫。 第二章：节点环绕p 圈算法。本章介绍了p 圈的工作原理，并提出了一种简单 的针对节点故障的p 圈算法一节点环绕p 圈算法，介绍了该算法的思想、计算方 法、评价标准，对其特点与性能进行了理论分析。 第三章：基于p 圈的a s o n 生存性机制及其信令扩展。本章提出了一种针对p 圈特殊的工作方式而设计的两套a s o n 控制平面信令机制。 第四章：a s o n 网络p 圈的实现及仿真结果分析。本章首先介绍了仿真环境， 即o p n e t 网络仿真软件，然后介绍了故障发生模拟模块、资源管理模块以及信令 流程的具体实现，最后分析了仿真结果。 1 5 小结 随着数据业务的迅猛增长，对传送网提出了更高的要求，而现有的传送网是主 4 北京邮电大学硕士学位论文绪论 要针对语音业务设计的，已经不能满足如今用户的需要了，a s o n 呼之欲出。a s o n 网络的可靠性也就成为一个重要的研究课题。 p 圈作为一种预先配置的环形结构，结合了环网快速恢复的优点和格状网络灵 活的优点，值得我们深入研究。 这一章概要介绍了a s o n 生存性研究的背景和主要研究方向，阐述了对a s o n 生存性进行研究的意义，然后从光网络结构的演进入手解释了p 圈的产生根源及其 意义，最后对本文的内容组织结构和文章的贡献做了简单描述。 下面的章节将详细介绍本文的主要工作成果，第二章是本文提出的一种节点p 圈算法，第三章是本文提出的两种基于p 圈的故障处理流程，第四章是本文对a s o n 网络和p 圈技术搭建的仿真平台和仿真所得结果及其分析。 北京邮电大学硕士学位论文节点环绕p 圈算法 第二章节点环绕p 圈算法 预配置环( p - c y c l e ) 是w d g r o v e r 教授在1 9 9 8 年提出的概念，它是在格状 网络中预先计算并配置的若干个环状连接，用以对这些环上的链路进行保护，故障 时可以进行坏回保护，同时还能对跨接链路进行保护。本章介绍了p 圈的工作原理， 分析了它与以往保护恢复机制的区别，并提出了一种简单的针对节点故障的p 圈算 法节点环绕p 圈算法，介绍了该算法的思想、计算方法、评价标准，对其特点 与性能进行了理论分析。 2 1p 圈工作原理 p 圈( p c y c l e ：p r e c o n f i g u r e dc y c l e s ) 是一种十分优秀的光网络保护机制。p 圈技术利用格状网络的空闲资源来构造保护环路，这些环路是格状网络中一系列已 经配置连接好的环。 配置了p 圈的格状光网络具有和环形光网络差不多的保护倒换时间，这是因为 在故障发生后只有p 圈上的某两个节点执行倒换动作，并且这些动作在故障发生前 都已经预先规定好了。它既具有环型网络通路倒换快的优点，又具有和空闲容量分 配( s c a ：s p a r e c a p a c i t y a s s i g n m e n t ) 算法或者关节容量分配( j c a ：j o i n t c a p a c i t y a s s i g n m e n t ) 算法格状网络保护设计有一样的容量利用率高的优点。 p c y c l e 动态保护恢复是指，网络中的业务是动态拆建的，网络中各节点之间 的业务何时发起、持续时间不可预测，网络以p - c y c l e 方式为这些动态业务提供保 护。 p 圈比普通的环网保护多了一层保护功能，即它既能够保护环上的链路，还可 以对不在环上的链路( 类似于环上的弦，称为跨接链路) 进行保护。当环上的一条 链路故障时，它可以进行类似于环保护的环回保护倒换。当它的一条跨接链路发生 故障时，则有两条通路可以进行保护倒换。现有的环保护( u p s r 、b l s r 、f d d i ) 对单位容量都只能最多提供一条保护路径，而且只保护环上的故障。相比之下， p - c y c l e 的保护效率就大大提高了。在占用同样容量的情况下，p - c y c l e 的保护链路 相比环形网络能多出1 6 到1 3 。 p 圈的工作原理如图2 1 所示： 6 北京邮电大学硕士学位论文节点环绕p 圈算法 图2 - 2p - c y c l e 保护跨接链路 综上所述，p c y c l e 保护是格状网络中一种保护方式，它结合了环形网保护和格 状网保护恢复两者的优点。p c y c l e 利用空闲资源预先配置的环形通道来实现格状网 络中的快速保护，同时允许业务选择最短的路由而不受网络中p 圈的限制。p - c y e l e 的配置发生在任何网络故障出现之前，并且所需要的实时倒换动作是预先设计好的。 尽管在倒换功能及网络拓扑上使用p c y c l e 和环相似，但p c y c l e 与至今为止任何有 恢复能力的基于环的系统( 包括1 + 1 ，单向通道保护环u p s r ，双向线路倒换环b l s r ， 共享备用通路保护s b p p 等) 并不相同，因为它不仅能对环上( o n c y c l e ) 链路的故 障提供保护，还能为跨接区段( s t r a d d l i n gs p a n ) 的故障提供保护。 2 2 基于资源的保护方式 根据a s o n 的保护倒换发生位置的不同可以将其保护技术分为两类： 基于业务的保护方式。 基于业务的保护方式下，所配置的保护资源都是根据具体的业务而分配的，例 如1 + 1 、1 ：l ，都是典型的针对业务的保护方式。这种方式是在业务的源节点和宿节 7 北京邮电大学硕上学位论文节点环绕p 圈算法 点之间计算出若干不相关的路由，以最优路由作为工作路径，以次优路由为备用路 径，在故障发生前就迸行连接配置，在故障发生后直接倒换到备用路径上去，达到 使业务不中断的目的。 在发生敌障时也是以业务为单位进行保护倒换的，在业务的两个端节点进行倒 换。 这种方式的优点是可以根据网络中的业务量来分配空闲容量作为保护容量。当 网络中业务较少时，使用的保护容量也较少。 缺点有： 计算保护路径的限制条件较多，受网络拓扑条件制约大。例如m ：n 方式下， 保护路径与其保护的若干条业务路径必须是同源同目的的，并且必须是不相关的。 如果网络的连通度不够大，符合这些条件的保护路径也不容易找到。 不够灵活。分配给某个业务或某几个业务的保护容量不能被其它的业务利用。 濠节点 宿节点 热谬、紫一旁 一糟糕 热蔷藩二三煮矬意一馥 咱糍 夥警糟糕 鬟2 瞧麓，、增热某个节点发生故尊时放尊节点的两个相邻节 。 嘲，宿节点 誊 ， 一 ， 酱 热 黧 北京邮电大学硕士学位论文节点环绕p 圈算法 从上面的分析可以看出，p 圈是属于基于资源的保护方式，故障发生时在故障 资源的两端进行保护倒换，而不需其中业务的源宿节点进行动作。 p 圈利用空闲资源预先配置的环形通道，在故障后只有圈上的某两个节点进行 倒换动作，从而实现格状网络中的快速保护。它同时允许工作通道在网络资源图上 选择最短的直达路由，结合了环网的快速保护倒换的优点和格状网络灵活的选路和 较高的资源使用效率的优点。 由于p 圈是一种基于资源的保护方式，同以往的基于业务的保护方式如1 + 1 、 1 ：l 等有很大差别，所以它在配置方式、保护倒换流程上都跟已往的基于业务的保护 方式有所不同，需要重新为它设计一套机制来将它应用在a s o n 中。 p 圈在a s o n 中的难点主要集中在下面两个方面： 它的算法比较复杂，在格状网络中要得出一组符合网络中业务分布、容量配置 的p 圈，从而使网络性能达到最优是没有解析算法的，因而是n p c o m p l e t e 问题。 理论七讲，n p ，c o m p l e t e 问题无法得到最优解，只能得到最接近最优解的次优解。解 决这个问题可以借助于整数线形规划，也可以使用启发式算法。这是一个难点，第 三章将提出一种朴素的基础的针对节点故障的p 圈启发式算法。 p 圈是基于资源的。故障发生时是在故障的边缘进行倒换，与业务源宿节点控 制的保护恢复机制也不相同。因此需要为它重新设计一套配置以及倒换的信令流程， 于是需要对现有的a s o n 控制平面基于g m p l s 的信令流程以及包格式做出必要的 修改和扩展。这也导致p 圈在现实网络中应用起来带来一些问题，这是第二个难点。 本文将在第血章详细介绍本论文提出的基于p 圈保护方式的两套故障处理机制和信 令方案。 2 3p 圈算法概述 按照p 圈的配置方法一般分成两种：静态p 圈和动态p 圈。 静态p 圈是指在网络规划初期，根据网络资源使用情况和对业务分布情况的预 测计算一组p 圈并进行配置，一旦p 圈计算并配置成功以后，就不再改变。 动态p 圈是指在业务进行过程中，根据实时的网络情况在一定策略驱动下，动 态地计算并且修改p 圈的配置情况，旦以前所计算的p 圈不再对当前的网络和业 务进行有效的保护，将重新配置一遍。 按照p 圈的针对性不同，可以分为针对链路故障的链路p 圈和针对节点故障的 节点p 圈。 在给定的网络拓扑下，计算链路p 圈的算法主要有： 基本圈生成算法 网孔圈生成算法 9 北京邮电大学硕士学位论文节点环绕p 圈算法 针对节点故障的基础圈生成算法 基础圈的扩张算法 无论使用何种基础圈生成算法，所得到的基础圈并不能完全满足保护网络中所 有业务的需要，因此，必须通过某些特定的策略，对基础圈里面的元素进行扩张， 以得到更优的一组备选p 圈集合。这些基础圈扩张策略包括： 基于环上链路的扩张策略 基于跨接链路的扩张策略 在很多情况下，如果网络中业务数目比较多，两且网络资源比较有限的时候， 仅仅作一次基础圈的扩张是远远不够的，因此，需要迭代式地对p 圈集合中的元素 进行扩张，用前一次扩张的结果作为下一次扩张策略的输入参数，经过多次扩张以 后，可以得到比较优的p 圈集合，本项目所提出的扩张周期包括： 单次扩张 迭代扩张 对于链路p 圈的研究已经有很多，因此这里不再赘述。本论文针对目前研究较 少的节点p 圈进行了一些探讨。 2 4 节点环绕p 圈算法 当前，针对节点故障的p 圈算法还不是很多，本论文就提出了一种基本的朴素 的节点p 圈算法节点环绕p 圈算法。 本算法的主要思想是：在传送平面光节点发生故障时，为了使经过故障节点的 业务不中断而找到一个比较优化的p 圈，使得该圈可以承载大部分经过该节点的业 务。因为经过故障节点的业务一定是从该节点的一个邻居节点流入该节点，又从该 节点的另一个邻居流出，如果能找到一个圈，这个圈包含这个故障节点的所有邻居 节点，那么当故障发生时，所有穿过故障节点的业务都可以倒换到这个圈上，从而 绕过故障，使业务继续进行。 2 4 1 算法描述 针对网络中的任何一个节点n ，首先寻找与该节点相连的所有链路，并记录这 些链路的另一个端点( 即节点n 的所有邻居节点) 。在拓扑图上删除这几条链路以 及节点n ，并且以这些邻居节点作为输入参数，在新拓扑图计算一个经过这些节点 的环绕p 圈。从描述过程可以看出，由于环绕p 圈是以节点n 为中心生成的，因此 至少可以保护一个节点，即节点n 。那么如果存在其它的节点如节点m ，它的邻居 节点集合跟节点n 的邻居节点集合有交集，也就意味着这个圈也可以保护部分穿过 节点m 的业务，同时圈上的链路和这个圈的跨接链路也可以得到保护。 i o 北京邮电大学顾士学位论文 节点环绕p 朋算法 图2 5 节点环绕p 圈示意 首先，认为当节点n 发生故障时，以它为源或目的的业务都无法保护，能够保 护的只有经过节点n 的所有业务。如图2 5 ，穿过节点n 的业务可以为a ，b ，c ， d ，e 之间任意两节点之间承载的业务，如由节点b 进入，经过n ，从节点e 流出 的业务，或者由节点d 进入，经过n ，从节点a 流出的业务等等。如果节点n 的度 为c ，则所有可能的业务方向数目为：。( o - 1 个。为了更加有效的保护流经节点n 的业务，可以看到，包含节点n 的所有邻居节点的p 圈就可以保护上述所有经过节 点n 的业务。例如，对于节点b 、e 间的业务，可以利用b - a e 或b c d - e 两段弧 来进行保护( 图中虚线表示不一定有直接的连接，可能经过其它节点) 。同时，该环 绕圈还对圈上的节点l 日j 的业务流进行环回的保护。 如果删除了节点n 之后网络变成非连通图，说明有节点度数为1 ，对于这样的 节点及流经它的业务是没有办法进行保护的。可以证明，对于连通度大于2 的节点 一定可以找到包含其所有邻居节点的环绕圈。 对于连通度为2 的节点，不必特地为它计算环绕圈，只要它的两个邻居已经包 含在其它的圈中即可。 这样，对网络中所有的节点都计算了环绕圈之后，所得到的圈集合就是需要的 那组p 圈。 2 4 2 节点环绕基本p 圈计算步骤 ( 1 ) 、将网络中的节点按照连通度由大到小排列。 考虑到连通度越高的节点，如果发生故障，影响越大，而且连通度小的节点的 圈也可能包含在了连通度大的节点中的图中，所以先对连通度大的节点优先配圈。 因此在进行选圈算法的之前，要对节点按照连通度进行排序。 这罩特别要注意的是，这个时候每个节点就有了两个序号，一个是它在拓扑图 北京邮电大学硕士学位论文 节点环绕p 圈算法 中的序号，而另一个是他在按照连通度大小排序后得到的序号。这个在算法中要尤 其注意区分开来。在编程实现算法的时候遇到过很多问题都是由于没有注意到这两 种编号这间的联系与区别，将两者混淆而造成的。虽然将节点按照连通度排序，让 本算法有点复杂，但是与它带来的好处相比，这是值得的。 ( 2 ) 、选择网络中联通度大于二的最高的点n x ，其所有的邻居节点为集合 i q j ) ， 从f n i 中删除第一个点n 。加入集合 n 2 ； 这里要特别提出的是，本算法不计算连通度只有2 的节点，因为这个节点可能 已经包含在别的节点的保护圈中，这个圈也可以用来保护它。 图2 - 6 当节点的连通度只有2 的拓扑举例 节点1 连通度为2 ，假设按照算法给它进行配圈，则应该为0 - ) 2 一) 7 一) 0 。必 须为这个圈配上额外的保护波长，而实际上如果节点1 连通度为2 ，只要设置当节 点1 发生了故障，通过它的业务也就是0 - 1 - 2 ，直接通过0 - ) 2 来保护就行了，圈 0 - ) 2 - ) 7 - ) 0 的作用也到此为止，其他为该圈配上的波长资源都被浪费了。所以在 算法开始前将连通度不大于2 的节点都排除出去。当得到最终的一组圈以后，将通 过了某个连通度不大于2 的节点的两个邻居节点的圈也作为该节点的保护圈，从而 达到既节省计算时间和复杂度，又提高资源利用率的目的。 ( 3 ) 、取 n l 中的第一个点为n b ，利用d 算法找出n 。，n b 间不含有n x 的最短 径。如果最短径不存在，则将n b 移n n l 的尾部；并将n 。对应的有效次数减1 。 这里要提到的是，之所以要在最短径不存在的情况下，将n b 移到 n 1 ) 的尾部， 是因为发现有可能出现这样的情况： 按照算法思想，假设为某个点计算p 圈，从拓扑图中将这个节点去掉，剩下如 下拓扑，1 ，2 ，3 ，4 都为该节点的邻居节点 北京邮电大学硕士学位论文节点环绕p 圈算法 图2 7 非理想情况 理想情况下，假设从节点l 开始算起，通过1 找到2 ，通过2 找到3 ，通过3 找到4 ，通过4 找到1 从而完成了圈的找法。但是事实上，如图2 7 所示，由于每 次出现等长路径时选路的任意性，程序可能选择了1 到2 ，2 到4 ，4 到3 ，3 到不了 1 ，于是得出算不出圈的结果，所以将算法第三步后改为，如果最短径不存在，则 将n b 移到f n 。 的尾部。这样，如果遇到上述的问题，程序会继续往下计算而不是得 出算不出圈的结论。 更外一个需要解释的地方就是，有效次数的概念。实际上它指的是以n 。为起 始节点时，下一跳有几种可能。比如邻居节点链表n e b 4 = 0 ，6 ，8 ，1 0 ，。那么当 n 。= 0 时，以0 为起始点，它的下一跳有3 种可能，分别为0 一) 6 ，0 ) 8 和0 ) 1 0 ， 所以0 的有效次数是3 ，如果已知了以0 为起始点的一种可能走不通，则要将其有 效次数减l 。比如，计算出0 一 6 没有最短路径，那么以0 为起始点，它的下一跳可 能性只有2 种了，即有效次数变成了2 。如果当一个点的有效次数变成了一1 ，那么说 明以它为起始点时行不通的，要返回到前一跳，重新计算。这在判断循环是否结束 中是十分重要的。 ( 4 ) 、重复3 ，直到n 。，n b 问存在不含有n x 的最短径为止，如果找不到，将 n 。从集合 n 2 中删除，n 。的有效次数减l ，用n b 代替n 。，放a n 2 ) ，重复3 ；如果 最短径存在，将同时存在 n 1 ) 和该最短径中的节点从 n l 中删去并：j i a n ：) ，该最 短径记为路径表p a t h l i s t = n a ，地 ，用代替m ； ( 5 ) 、重复3 ，如果 n l 不为空而且无法找到n a 与n b 之间的路径，则将n a 从 n 2 中删除，并放入 n 1 ) 队尾，将 n 2 中最后一个节点取为n a ，重复3 ；如果 n i 为空，则用d 算法计算p a t h l i s t 首尾两节点间的不包含该路径上点的最短径，最终 得到一个包含尽可能多的n x 的邻居节点的圈。 2 4 3 节点环绕p 圈评价标准 对于每个环绕p 圈，如何判断它的优劣从而对它作出取舍呢? 主要从以下几个方面来看： 北京邮电大学硕士学位论文节点环绕p 圈算法 ( 1 ) 节点保护效率：即节点a 的环绕p 圈上包含的节点a 的邻居节点数与 非节点a 邻居节点数之比。这个数值越大，说明该圈越优化，保护效率越高。当分 母为0 时，即该p 圈只包含节点a 的邻居节点，这时，在所有能够保护流过节点a 所有业务的圈中需要的资源最少。 ( 2 ) 覆盖节点数目：即有多少个节点的所有邻居都能包含在这个p 圈中。这 个数值越大越好，说明这个p 圈效率越高。 2 4 4p 圈优化 经过第一步骤得到的一组圈并不是最终想要的最优化的那组圈，需要对它们进 行整合、优化，来得到尽可能大的容量效率同时也保证尽可能高的保护成功率。 如果一个节点a 的所有邻居节点都包含在另一个不相邻节点b 的所有邻居中， 那么节点a 一定能被节点b 的环绕p 圈所保护，这样只需要为节点b 的环绕p 圈 进行配置就可以同时保护节点a 和b 。 2 4 5 资源配置方式 通过网络中的业务矩阵或者业务预测矩阵计算出通过每个节点的业务流的情 况，再为它们配置保护瓷源。有两种资源配置策略： 从计算出的那组基本p 圈中效率最高的开始配置资源利用前面统计出的穿过 一个节点的业务流的情况来在p 圈上每个方向配置足够的资源。 ( 1 ) 按照上面的方式为每个节点的环绕p 圈配置保护资源。 ( 2 ) 迸一步对资源配置进行优化。配好一个p 圈上的资源数后，由于p 圈上的 节点还可以被这个圈保护一部分业务，所以将可以保护的这部分从圈上节点需要保 护的业务中删去。这样为这个圈上的节点的环绕p 圈配置资源时就需要更少的保护 资源，可以大大提高容量效率。 2 5 小结 p 圈可以分为链路p 圈和节点p 圈。对于链路p 圈已经进行了很多研究。 本章提出了一种简单的节点p 圈启发式算法，叫做节点环绕圈算法。它主要思 想是在网络中针对一个节点找出包含它所有相邻节点的圈，于是这个p 圈可以保护 穿过这个节点的所有业务，同时还可以对圈上的链路以及跨接链路以及圈上节点的 部分业务提供保护。 本章首先描述了节点环绕p 圈的算法思想、它的计算步骤，然后讨论了该算法 得到的p 圈的评价体系，从而对这一系列p 圈进行优化。最后介绍了如何为算出的 一组p 圈分配资源，使网络的容量效率有所提高。 1 4 北京邮电大学硕士学位论文 节点环绕p 圈算法 我们可以看到p 圈是一种比较优秀的格状网保护方式，借鉴了环网中保护方式 的特点，成为最具研究价值的一种保护技术。但是将p 圈应用到网络当中不是仅仅 有算法就够的，还需要网络对它的支持。因此，后面一章提出了两套可以将p 圈技 术嵌入a s o n 网络的故障处理机制，分别对网络中可能发生的各种故障情况提出了 相应的处理机制。 北京邮电大学硕士学位论文基于p 圈的a s o n 生存性机制及其信令扩展 第三章基于p 圈的a s o n 生存性机制及其信令扩展 a s o n 通过引入控制平面使光网络变得智能化、自动化，能够进行实时的流量 工程控制，根据数据业务的需求，实时、动态地调整网络的逻辑拓扑结构，以避免 拥塞，实现资源的最佳配置，实现网络资源的动态分配，智能化的连接管理，为快 速高效的网络生存性策略的实现提供了条件。前文介绍了p 圈保护技术，它结合了 环网的快速故障恢复能力和格状网络资源使用效率高的优点。本章为了将p 圈应用 到a s o n 中提出了两套针对p 圈特殊的工作方式而设计的a s o n 控制面信令机制。 3 1a s o n 中基于业务的保护与恢复的流程 3 1 11 + 1 保护方式 1 + 1 保护方式又被称为“并发优收的方式”。这种方式下业务的源节点同时向工 作路径和备用路径传送数据，业务的宿节点根据收到信号的信号质量( 如误码率、 信号强度等) 来决定从哪一条路径接收数据。因此这种方式下当一条路径上有链路 或者节点发生故障时，业务的宿节点会自动倒换到另一条路径上，不需要控制平面 进行信令的交互。 勉墼一鳓 f优救 一一一一一一一一一一一一一一一。一宿节矗 图3 11 + 1 方式原理 这样的虚线均表示该连接不一定是一条链路，有可能经过 1 ：1 的保护方式下业务的源节点只在工作路径上传送数据，备用路径可以是空 闲的或者传送一些服务等级较低的业务。 当故障发生时，定位到故障的故障链路两个端节点分别向业务的源节点和宿节 点发送n o t i f y 消息，通知发生故障。源节点和宿节点在收到n o t i f y 消息之后倒换到 备用路径上。 需要注意的一点是，这时n o t i f y 消息的发送方式与业务建立或拆除时p a t h 或 p a t h t e a r 消息的发送方式不同。p a t h p a t h t e a r 消息根据传送平面业务路径上节点的顺 北京邮电大学硕士学位论文 基于p 圈的a s o n 生存性机制及其信令扩展 序在控制平面的相应节点逐跳发送，而故障时的n o t i f y 消息则是由故障链路的入口 和出口节点直接发送到业务的源节点和宿节点，不需要逐跳发送。 静一鲤数国 迄9 哩= 二乡懒 图3 - 21 ：l 方式恢复流程 3 1 3 恢复方式下的信令流程 恢复方式就是在故障发生后查找替代路径，并且重新建立连接。 以重路由方式为例，故障发生后，源节点收到故障通知，向业务路径下游节点 发送p a t h t e a r 消息拆除整条业务连接，同时计算一条新的路由，并在新的路径上发 送p a t h 消息建立连接。 撑獭点甏萎? 一一一一 j ：作蹄径8 9 、一一一 n 科 h 耀节点；誊一一一一。i ：作路径_ 潭尊点 - o = 作路径t 肖链鼙发牛蘸障 一蝴一一。， n o