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.