Design and Optimization of High-Availabilty Neworks

尽管在为电缆提供物理保护方面做出了相当大的努力，但北美网络仍然经常遇到电缆切断和中断的情况。对于用于基本语音或数据的更传统的网络来说，中断可能会导致严重的经济损失。考虑到新兴网络打算承载的许多应用程序（医疗级应用程序、第一响应者应用程序等）的关键性质，故障的后果可能会更加极端。然而，许多网络的底层基础设施非常稀疏，这使得它们本质上无法生存。对于现代公共网络基础设施来说，应对大范围灾难性相关故障的弹性几乎是遥不可及的。******现代网络采用生存性机制，在面对电缆切断或其他故障时提供恢复。这需要备用容量，允许失败的流量重新路由。以最优方式做到这一点可能是一个难题。目前利用线性规划方法的解决方案在文献中广泛使用，其中大多数模型旨在确保网络在一次故障中存活下来。然而，多个故障可能在时间上重叠；分析表明，多故障场景是导致网络不可用的主要原因。为了提供更高的网络可靠性和连接可用性，生存性方案必须适应处理多种故障。虽然已经开展了增强关键应用程序生存能力的工作，但仍有许多机会可以开发更先进的技术来进一步增强生存能力和可用性。与目前的最佳努力方法相比，现代网络上日益流行的关键应用程序将显著改变它们的发展方式。确定如何设计网络以满足指定的可用性水平仍然是一个悬而未决的问题。******本提案概述的计划包括三个关键目标。***(1)改进的网络可用性模型：为了在网络设计方法中纳入可用性，需要更好的网络可用性模型，主要是那些在大多数现代网络中部署的可生存性机制。***(2)高可用性网络设计的优化模型：接下来我们将重点研究可生存网络设计的线性规划模型，以保证特定的连接可用性。多周期规划和拓扑优化将纳入这些方法。***(3)大规模高可用性网络优化问题的启发式方法：尽管上述类型的优化设计模型难以解决，但将启发式方法应用于基本网络设计方法已显示出获得接近最优设计的希望。我们还将寻求将这些方法应用于抗灾网络设计。

Despite considerable efforts taken to provide physical protection of cables, North American networks still experience frequent cable cuts and outages. For more traditional networks of the type used for basic voice or data, outages can result in severe financial losses. Given the critical nature of many of the applications that emerging networks are intended to carry (medical-grade applications, first responder applications, etc.), the consequences of failure could be much more extreme. And yet the very sparse nature of many networks' underlying infrastructure makes them inherently un-survivable. Resilience against widespread catastrophic correlated failures is virtually out of reach for modern public network infrastructures.******Modern networks employ survivability mechanisms to provide restoration in the face of cable cuts or other failures. This requires having spare capacity on standby, permitting failed traffic to be rerouted. Doing so in an optimal fashion can be a difficult problem. Current solutions utilizing linear programming approaches are widespread in the literature, where most models aim to ensure a network will survive a single failure. However, multiple failures can overlap in time; it has been shown analytically that multi-failure scenarios are the main cause of network unavailability. In order to provide higher network reliability and connection availability, survivability schemes must adapt to handle multiple failures. While work has been done to provide enhanced survivability of critical applications, there are many opportunities to develop more advanced techniques to further enhance survivability and availability. The growing prevalence of critical applications on modern networks will significantly alter the way they will evolve when compared to best effort approaches of today. Determining how to design networks to meet specified levels of availability is still very much an open question.******The program outlined by this proposal includes three key objectives.***(1) Improved Network Availability Models: In order to incorporate availability within the network design approach, better network availability models are needed, primarily those that account for survivability mechanisms deployed in most modern networks.***(2) Optimization Models for High Availability Network Design: Next we will focus on linear programming models for design of survivable networks to guarantee specific connection availability. Multi-period planning and topology optimization will be incorporated into these approaches.***(3) Heuristic Approaches for Large Scale High Availability Network Optimization Problems: Although optimal design models of the type described above are difficult to solve, heuristics applied to basic network design approaches have shown promise in obtaining near optimal designs. We will also seek to apply these approaches to disaster-resilient network design.