抗毁光网络中预置圈算法研究

来源 :电子科技大学 | 被引量 : 10次 | 上传用户:zcsq1987
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
当今社会生活的各个方面越来越依赖于通信网络,尤其是骨干通信网络的可靠运行。波分复用(Wavelength-Division Multiplexing,WDM)技术的发展大大提高了通信网络的传输容量,将成为下一代骨干网络的核心传输方式,同时,由于每个波长承载的传输容量可高达吉比特每秒,网络故障会导致大量业务中断,这也使得网络抗毁性问题显得更加紧迫和突出。由于抗毁策略既要求快速的故障恢复时间又要满足实时业务的需求,很多研究集中在保护恢复策略。网络中起点与终点重合的通路叫做圈。光网络中圈状结构的构造简单,可以灵活适应各种故障恢复算法,基于圈状结构的抗毁性技术具有保护速度快、资源利用率高等特点,因此,非常适用于光网络中业务的故障恢复。基于保护设计思想,本文研究了网状WDM网中的基于圈状结构的故障恢复设计相关问题,集中在这几个方面:链路型预置圈(Pre-configuration Cycles,p-Cycles)构造算法研究、节点环绕型预置圈构造算法研究、抗毁网状光网络中预置圈容量分配、SRLG(Shared Risk Link Group)约束下的分离式路由和预置圈设计。网状网络中抗毁性设计的本质是快速故障恢复和高可靠性,预置圈p-Cycles故障恢复方案就具有上述特性。为此,作者在第二章中研究了抗毁WDM网状网链路型简单预置圈构造算法问题,主要包括三个方面的工作:(1)针对网状网络中链路型p-Cycles的构造设计,就如何快速有效的在网络中构造出性能优良的备选链路型p-Cycles问题,研究了三种基于节点扩张的算法Node-Add、Node-Expand和Node-Grow算法。提出了快速简单圈挖掘算法,能在网络中非常灵活快速地构造性能优良的链路型p-Cycles,产生备选p-Cycles的性能可以由算法的输入参数灵活控制,非常适合网状WDM光网络的圈构造。(2)研究了基于k-最短路由的预置圈启发式算法,针对利用k-最短路由算法构造更多备选圈的问题,提出基于k-最短路改进metaDijkstra的圈构造算法。虽然算法的复杂度比最短路算法要高一点,但基于k-最短路改进metaDijkstra算法在同等条件下能构造出更多的备选圈。(3)根据处于局部范围内的p-Cycles具有保护切换时间短的特性,引入了局域图Local-map的概念,并在此基础上提出了获取更多备选圈的基于Local-map的圈扩张算法。将Local-map概念应用到链路型简单p-Cycles的构造就形成了提出的基于Local-map的预置圈启发式算法,该方法构造的链路型p-Cycles既恢复速度快又容量利用率高,实现网络故障快速故障恢复。节点环绕型p-Cycles不仅可以保护圈上链路和跨接链路,而且可以提供节点失效恢复,其结构特点是必须经过所有与中心节点邻接的所有节点且不包含该中心节点,因此,其构造算法也比较特殊。作者在第三章中进行了节点环绕型预置圈构造算法研究,主要包含三个方面的工作:(1)根据节点环绕型p-Cycles的结构特点,提出了圈收缩算法以获得包含目标节点的最小目标圈,在最小目标圈上运行的三种圈扩张算法Sp-Add、Sp-Expand和Sp-Grow算法获取更多备选圈,提出了一种节点环绕圈挖掘算法。如果在网络中存在节点环绕型p-Cycles,该算法就能为不同的网络节点构造性能优良的备选节点环绕型p-Cycles,产生备选p-Cycles的性能可以由算法的输入参数灵活控制,同时适合覆盖多个目标节点的p-Cycles构造问题。(2)将Local-map概念应用在节点环绕型p-Cycles的构造算法中,提出了基于Local-map的最小目标节点圈构造算法。研究了获取更多备选圈的圈扩张算法,提出基于Local-map的圈挖掘算法。该算法适合网状网络中节点环绕型p-Cycles构造算法的需要,并且在不需要枚举的情况下该算法比深度优先搜索(Depth First Search,DFS)算法可以构造出更多备选圈。(3)针对快速构造备选节点环绕型p-Cycles问题,采用逐级增加Local-map级数的方法,提出了基于Local-map的p-Cycles快速构造算法。该方法在逐级增大的Local-map中寻找目标圈和运行圈扩张算法,可以快速的构造出更多备选节点环绕型p-Cycles,并且构造出的p-Cycles既恢复速度快又保护效率高。只有为一个备选p-Cycles分配了容量,才能真正的将p-Cycles配置到网络中,优化的容量分配是网状网络中p-Cycles设计非常重要的一步。作者在第四章中研究了抗毁网状光网络中预置圈容量分配问题,主要包含三个方面的工作:(1)针对如何在抗毁网状光网络拓扑中优化配置p-Cycles问题,研究了在网络空闲容量中的利用圈扩展算法来获得更多性能优良p-Cycles,提出基于空闲容量的p-Cycles启发式分配算法。该算法充分考虑网络中空闲资源的分布情况,使得网络中的空闲资源能够提供尽量大的保护恢复能力,性能优于枚举算法,适合抗毁网状光网络中的p-Cycles优化配置。(2)针对如何在工作容量约束下优化配置p-Cycles,提出获得更多性能优良圈的Local-map圈扩展算法和工作容量约束下p-Cycles空闲容量分配算法。该算法在考虑网络中每条链路容量限制的前提下,充分考虑网络中分布的工作容量约束,使得整个网络资源分配最优。因此,在考虑工作容量的分布情况下,工作容量约束下p-Cycles空闲容量分配算法既实现快速空闲容量配置又保证所配置p-Cycles的保护效能高。(3)考虑为网络中的工作容量提供100%的单链路失效保护,使网络中配置p-Cycles的预留空闲资源最少,研究了获取高保护性能备选p-Cycles的容量扩展算法,提出了联合优化p-Cycles容量分配算法,该方法优化配置的p-Cycles可以为网络中所有工作容量提供保护。该算法充分考虑网络预留空闲容量分布的均衡性,既保证网络预留空闲资源少,又大大降低网络成本,满足抗毁网状WDM网络中单链路故障恢复的p-Cycles规划设计的需求。在实际网络中,光纤链路由于共享了相同的物理设备而具有故障相关性,这可以用共享风险链路组(Shared Risk Link Groups,SRLG)来表示。考虑SRLG约束,作者在第五章中研究WDM网状网基于SRLG的分离式路由和预置圈设计,主要包括两个方面的工作:(1)基于SRLG约束下的分离式路由,针对找不到完全SRLG分离路由时候如何找SRLG尽量分离路由的问题,研究了利用SRLG失效对网络最大流的消减程度来评价SRLG重要性的方法,提出基于重要性的部分SRLG分离算法MIDR。找分离路的时候考虑每个SRLG的重要性,MIDR算法使工作路经过可靠性高的SRLG,使保护路优先经过空闲容量多的链路。对比基于重要性的部分SRLG分离算法和保护路优先算法,MIDR算法使整个网络能为更多的业务提供服务,降低网络的阻塞率。(2)研究了SRLG约束下的p-Cycles构造问题,引入SRLG完全分离p-Cycles的概念,提出了基于SRLG的简单p-Cycles构造算法和获得更多p-Cycles的SRLG约束下的圈扩展算法;针对如何在光网络拓扑中优化配置SRLG完全分离的p-Cycles,提出了SRLG约束下的p-Cycles配置算法,该算法中的最小容量配置方案可以预留更少的网络资源,而优化容量配置方案可以快速的为p-Cycles配置容量。提出的SRLG约束下p-Cycles配置算法在考虑SRLG的分布情况下,保证所配置SRLG分离p-Cycles的保护效能高,使网络具备单SRLG故障恢复能力。为验证、评估本文所提各种算法的性能,作者自行开发了抗毁WDM网状网中预置圈仿真平台软件,并利用仿真平台对各种算法进行计算机仿真。论文最后是全文总结。
其他文献
西部开发要求教育大发展。美国教育在西部开发中采取了拨地兴学、兴办公立学校、建立农工商学院、发展职业教育、重视科研导航等措施并取得了成功。借鉴历史经验,完善现行教育
从上世纪七十年代开始,协议测试技术就成为了网络界研究的热点课题之一。其间,ISO9646定义了面向路由器等中继系统的两种测试法和面向端系统的四种测试法,以及一种定义测试控
近年来,基于小波变换的图像编码技术取得了长足的进步。优秀的小波图像编码器不仅具有较高的压缩效率,而且产生的码流具有可伸缩性,从而使得渐进传输和动态带宽适应成为可能。但
烟草行业是一个特殊的行业,是国民经济的重要组成部分。烟叶生产为烟草行业发展提供基本保障,坚定不移推进行业供给侧结构性改革,烟叶生产规模从122万公顷、235万吨降至现在的90万公顷、174.4万吨。内蒙古地区种植烟叶规模减少约五分之四。本文利用查阅资料和调查研究的方法,对内蒙古烟叶生产进行了详细论述。内蒙古地区种植烟叶已有40多年的历史,2005年种植面积达3200公顷、12000吨。内蒙古现代烟
<正>0引言静脉血栓是肾病综合征(NS)的常见并发症之一,可出现下肢深静脉血栓形成(DVT)、肾静脉血栓(RVT)、肺栓塞(PE)及其他部位的血栓[1,2]。国外文献报道NS患者发生静脉血栓栓塞的
1临床资料患者,男,75岁。因腹痛、腹胀、纳差、乏力4个多月,加重1个月人院。既往无特殊病史。查体:生命体征正常,贫血面容,浅表淋巴结未扪及肿大;心肺未见明显异常;腹软,无肌紧张,中上
由于摄像载体的运动或拍摄平台的不稳定等因素,导致拍摄的视频序列产生各种不稳定现象,这些不稳定现象严重影响了拍摄视频序列的质量。这些不稳定现象在视频节目制作中,大大影响
本文在波束成形、空时编码和功率控制理论基础上,对CDMA系统的波束成形与功率控制联合优化技术进行了深入研究。针对现有方法在微蜂窝、微微蜂窝环境下,性能受指峰干扰影响而