WDM光网络中基于软管模型的鲁棒选路及抗毁研究

摘要

在对WDM（Wavelength Division.Multiplexing）光网络进行规划设计时，传统的选路和抗毁方案都需要给出一个明确的业务量矩阵。然而近年来，随着Internet数据业务量的爆炸式增长以及新兴宽带业务的不断涌现，运行于光层之上的分组数据会出现大幅度变化的情况，所以在实际运用中很难预测或估计出点到点之间具体的业务流量大小。因此，十分有必要研究带宽需求信息不确知情况下的鲁棒选路和抗毁问题，以适应其高速增长和动态变化。软管（Hose）不确定业务量模型最早出现在虚拟专用网（VPN，Virtual PrivateNetwork）的研究中。该模型并未指定一个完整的业务量矩阵，仅对流入和流出各节点的合成业务量（即业务量矩阵的“行和”以及“列和”）的上限进行约束。由于不需要具体描述网络中的业务分布情况，因此软管模型大大降低了业务量估计的难度，同时也提高了设计的灵活性。本文研究Hose模型在WDM光网络中的优化问题，主要围绕以下两个方面展开：①基于Hose模型的鲁棒选路问题；②基于Hose模型的鲁棒抗毁研究。
　　 本文的创新点主要包括五点。第一，研究了Hose不确定业务量模型下的静态鲁棒选路问题。与以往解决方案的区别在于，本论文并不仅仅考虑如何减少链路开销，而是更为全面地对影响网络代价的主要因素（包括链路开销和节点交换开销）进行考查，提出了比现有解决方案更节约网络资源的启发式算法。第二，在Hose模型的框架下，作者研究了如何利用部分确知的点到点的业务需求信息来实现鲁棒优化选路的问题，提出了一种新的选路策略，并给出了相应的启发式算法。该算法有效解决了现有鲁棒选路方案时延和抖动较大的问题。第三，探讨了Hose模型下的动态Qos（Quality of Serive，服务质量）选路问题，并提出了相应的启发式算法。该算法根据当前连接请求的服务等级、当前网络中业务的传输情况以及各条链路上空闲波长的数目动态地调整路由。与现有的动态鲁棒选路算法相比，本文所提算法具有更加优越的性能。第四，研究了WDM网状网中的鲁棒单链路抗毁设计问题，并提出了两种共享保护启发式算法。仿真结果表明，两种算法在各自的应用范围内均具有比较明显的性能优势：相对于以前的鲁棒抗毁算法，它们在开销和恢复时间方面都有较为明显的改善。第五，探讨了基于动态Hose模型的多失效生存性问题。最主要的思路有两点：⑴采用分级保护；⑵引入“危险程度”的概念，在为连接请求建立工作和保护路时避开危险程度高的网络部件。按照这两条思路，作者提出了相应的启发式算法，并通过仿真验证了其有效性。
　　 本文第二章从三个方面讨论WDM网状网在Hose业务量模型下的鲁棒选路问题：⑴Hose模型下的静态鲁棒选路问题；⑵业务量矩阵部分确知（指部分网络节点对之间的业务需求大小已知）情况下的鲁棒选路问题；（3）Hose模型下的动态鲁棒选路问题。对于问题⑴，作者以全网代价最小为目标，建立了两种分别基于单路径选路（Single Path Routing，SPR）路由结构以及Valiant负载平衡（ValiantLoad-balancing，VLB）路由结构的数学规划（MP，Mathematical Programming）模型。通过对数学模型的求解，可以获知波长、光收发器以及波长转换器等资源的最佳配备。由于WDM网络中的鲁棒优化选路问题是NP-完全（NP-complete，NPC）问题，因此作者又提出了两种基于SPR和VLB的启发式算法--IBFS（IterativeBreadth-first Search）算法和MNC（Maximizing Network Capability）算法。计算机仿真表明，两种算法都具有良好的性能，而MNC算法则具有更好的可扩展性，在大规模网络中性能明显优于以往的方案。对于问题⑵，根据对业务量变化的观察，作者在VLB的基础上提出了适应性负载平衡（Adaptive Load-balancing，ALB）机制，并给出了相应的启发式算--ADT（Adding Direct Traffic）算法。适应性负载平衡机制的核心思想就是利用已知的点到点业务量信息，尽可能少地调整VLB所建立起来的两跳虚拓扑，使更多业务通过一跳路由的方式进行传输，从而达到降低时延和抖动的目的。仿真结果表明，ALB在具有高吞吐量的同时能提供比VLB更好的服务质量。对于问题⑶，作者考虑全连接逻辑拓扑的情况，提出了DDALB（Differentiated Dynamic Adaptive Load-balancing）启发式算法。
　　 本文第三章到第五章研究WDM网状网在Hose不确定模型下的鲁棒抗毁问题。其中第三章和第四章分别研究单链路失效（Single-link Failure）和相关链路失效（Correlated-link Failure）情况下的抗毁设计问题，而第五章则对多网络部件失效（Multiple Failures）时的抗毁问题进行探讨。为解决单链路失效，作者提出了两种分别基于VPN树路由和Valiant负载平衡机制的共享分段保护（Shared SegmentProtection，SSP）启发式算法叫-TSSP（Tree-based Shared-segment Protection）算法和VLB-SSP（VLB-based Shared-segment Protection）算法。在资源配置方面，TSSP算法通过降低工作树的叶子节点（即树型拓扑中度为1的节点）数来减小工作路径（Work Path，WP）和保护路径（Backup Path，BP）的数目，从而有效地利用资源；而VLB-SSP则通过最小化全网代价配置工作和保护波长，以达到减小开销的目的。在故障恢复方面，两种算法均采用了分段保护机制，因此恢复速度也较快。
　　 对于相关链路抗毁，本文的研究分为以下两个方面。⑴针对双链路失效的抗毁设计问题，作者提出了启发式保护算法-DVLBSP（Differentiated VLB SharedProtection）算法。该算法遵循分级保护（Differentiated Protection）的思想计算保护路径，只为不满足给定可靠性要求的工作路径寻找保护路径；同时还考虑到了业务模型与网络拓扑对全网代价的影响，并结合共享保护的思想配置保护波长。仿真结果表明，DVLBSP算法实现了开销与可靠性之间的较好折衷。⑵针对共享风险链路组（Shared Risk Link Group，SRLG）的抗毁问题，作者提出了PSPPKT（PartialSRLG-disjoint Protection with Partially Known Traffic）启发式算法，并通过计算机仿真论证了其有效性。对于多网络部件失效的情况，将保护和恢复（Restoration）两种抗毁方案结合起来，提出了基于适应性负载平衡机制的CAL（Criticality AvoidanceLoad-balancing）启发式算法。通过仿真结果可以看出，CAL算法是一种较为实用的基于动态Hose业务量模型的多网络部件抗毁方案。为验证、评估本文所提各种算法的性能，作者开发了相关仿真平台。第六章对这一仿真平台做了介绍，并给出了重要伪码。第七章是全文总结。