论文部分内容阅读
当今社会生活的各个方面越来越依赖于通信网络,尤其是骨干通信网络的可靠运行。波分复用(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网状网中预置圈仿真平台软件,并利用仿真平台对各种算法进行计算机仿真。论文最后是全文总结。