论文部分内容阅读
WDM(Wavelength-Division Multiplexing)技术的出现使得一根光纤可以提供巨大的带宽。在基于WDM技术的光网络中,一根光纤的失效会导致大量数据的丢失。对WDM光网络的生存性进行深入研究具有重要的价值。网络生存性技术主要分为保护和恢复两大类。保护是指事先为业务分配好保护资源,当故障发生时,业务可以利用这些分配好的保护资源来承载业务。恢复是指事先并不为业务分配保护资源,而是当故障发生之后再动态的寻找网络资源来承载受故障影响的业务。由于保护设计时已经为业务分配好了保护资源,因而保护设计具有较快的故障恢复时间。正是由于这一优势,本文研究抗毁WDM网状网中的保护设计问题,主要集中在以下几个方面:抗毁WDM网状网中的分段保护设计问题、SRLG(Shared Risk Link Group)约束下的保护设计问题、支持区分可靠度的保护设计问题、多播的保护设计等问题。分段保护是一种新的保护方式。它不但具有较高的资源利用率,而且具有较短的恢复时间。本文第二章研究抗毁WDM网状网中的分段保护设计问题。主要贡献在于:1)在分段保护当中,工作路被分成了多个工作路段,而每条工作路段都被一个保护路段保护起来。通常情况下,两个工作路段会有一部分相互重叠。这样,工作路上的一些链路就会同时被两个保护路段保护起来。在为每个保护路段预留资源的时候,传统上只考虑这个保护路段对应的工作路段的情况而不关心这条工作路段与其它工作路段的关系。这样就会出现两个保护路段同时为某条链路预留资源的情况,从而出现不必要的资源浪费。针对这一问题,本文提出了一种有效的减少保护资源的保护算法并分析对比了其性能。2)另一方面,虽然分段保护方式下计算出的保护路段大都比较短,但是有的情况下利用分段保护计算出的保护路段依然比较长,从而不能真正达到缩短恢复时间的目的。因此,有必要对保护路段的跳数进行限制,使得每一条保护路段的跳数都限制在某个给定的门限之内。本文研究了保护路段跳数有限制的分段保护问题并提出了一种基于分段的保护算法,同时分析了其性能。在抗毁WDM网状网中引入SRLG概念之后,为一个源宿节点对计算一对SRLG分离的路径对是NP-C的。因此,通常的做法是首先为源宿节点对计算一条工作路,将工作路上的所有链路以及那些跟工作路有相同SRLG的链路全部从网络中删除后,再计算一条源宿节点对之间的保护路。在工作路确定的情况下,有时可能找不到跟工作路SRLG分离的保护路。这就是所谓的“陷阱(Trap)”问题。陷阱既有可能是由实际的物理拓扑决定的,也有可能是资源匮乏或者资源分配不合理而引起的。本文第三章研究抗毁WDM网状网中SRLG约束下的保护设计问题。主要贡献在于:1)一种有效解决“陷阱”问题的方式是分段保护。然而,对于究竟需要多少个段才能够有效的解决“陷阱”的问题,还没有见到相应的研究。本文研究发现在绝大多数情况下(99%)只需利用2个保护段就可以有效的解决“陷阱”问题。据此,本文进一步提出了一种只利用两个保护段来保护工作路的算法并分析对比了其性能。2)由于“陷阱”有可能是因为资源分配不合理而导致的。因此,为连接请求合理的分配资源就变得十分重要。为此,本文将业务量工程的思想引入了SRLG约束下的保护设计当中并提出了一种基于业务量工程的保护设计算法来达到这一目的。为连接请求提供不同可靠等级的服务是光网络发展的趋势。为了实现上述目标,必须要根据连接请求的可靠度来为其计算合适的路由。第四章研究了抗毁WDM网状网中支持区分可靠度的保护设计问题。主要贡献在于:1)提出了两种在单链路失效模型下不允许资源共享的近似算法。第一种近似算法通过构造一个辅助图,可以一次性找到路由连接请求需要的所有资源,避免了传统算法需要分步计算的缺点;而第二种近似算法首先为连接请求计算一条工作路,然后构造一个辅助图并在辅助图中为连接请求计算满足可靠度要求的路由。两种近似算法相比较,第一种算法的近似程度要好,但是需要较高的计算复杂度。2)提出了一种在单链路失效模型下允许资源共享的启发式保护设计算法。3)提出了一种在独立失效模型下不允许资源共享的启发式保护设计算法。该算法允许利用多个保护路段来提高路由的可靠度,从而有效的克服了传统算法只允许利用一个保护路段来提高路由可靠度的缺点。由于WDM网络能够提供巨大的带宽,这使得一些带宽需求较高的多播业务应运而生。在基于光树的多播路由当中,一条链路失效意味着同时会有多个目的节点不能正常接收数据。因此,多播的生存性路由问题在近年来成为了一个研究热点。第五章研究了抗毁WDM网状网中多播的保护设计问题。主要贡献在于:1)研究了多播之间在不可以共享保护资源的情况下,多播树给定时如何为多播树计算保护资源的问题并提出了相应的算法。计算机仿真结果表明,本文提出的算法具有比文献中已有算法更好的性能(如较低的阻塞概率、较小的保护代价等)。2)由于为多播请求计算路由的问题是NP-C的,因而文献中大都是提出一些启发式算法。这就意味着计算出的路由会有冗余资源。本文第一次提出这一问题并提出了一种有效减少冗余资源的算法。计算机仿真结果表明,本文提出的算法具有较好的性能。3)当前,文献中针对多播生存性路由问题的研究大都不考虑多播之间共享保护资源的情况。然而,从对单播的研究中我们知道,保护资源共享可以大大提高网络的资源利用率。为此,本文提出了一种允许保护资源共享的多播保护算法并比较分析了其性能。