Formulation and benefit analysis of optimization models for network recovery design

Network recovery is critical capability that service providers must provide. It can be accomplished in four ways. Span protection is the most common recovery method. It is fast but expensive. An alternative is path restoration. Although it is typically considered less expensive than span protection, it is too slow for most real-time applications. Some service providers try to achieve the speed and cost advantages of these two methods by selectively applying both span protection and path restoration in different parts of their networks in a "hybrid" recovery configuration. Another alternative is a feature in Multiprotocol Label Switching (MPLS) called "Fast Reroute" which offers the benefits of span protection, path restoration, and hybrid recovery. Since little conclusive research has been accomplished that addresses the effects of network implementation options on recovery methods (particularly newer MPLS Fast Reroute), service providers often rely on rules-of-thumb and industry folklore to guide them in their decision on which recovery methods to use in their network.;This praxis addresses several fundamental problems related to network recovery of large service provider networks. First, the effects of the numbers of links, demand unit sizes, and link size modularity have on the four recovery methods, individually and collectively, are examined. Next, the selection of the minimum cost recovery method given the presence and levels of the other options is determined. Finally, the cost differences of the recovery methods given any combination of the other options and their levels are presented.;Span protection and Fast Reroute are formulated as mixed integer problems while Path restoration is an edge-path multi-commodity linear programming model. Hybrid recovery is accomplished by calculation. The models focus on minimizing the network capacity cost of implementing each of the four recovery methods considering the other options.;To evaluate the effectiveness of these models in providing relevant solutions to network service providers, a series of computational experiments are performed. A suite of network instances, with varying topologies and origin-destination demand sets that mirror realistic service provider networks, are developed and tested using the recovery method, numbers of links, demand units sizes, and link modularity as factors. The results are evaluated to test a series of research hypotheses and develop insight into effectively designing recovery solutions for large service provider networks.;The models have several practical applications to service providers that provide measureable benefits. First, they provide definitive guidance to network design engineers in the selection and placement of recovery methods in their networks. It also allows them to quickly and accurately analyze the effects of implementing or migrating different recovery options based on network characteristics. Finally, and perhaps the most beneficial result of the models, is they provide definitive financial guidance as to which recovery method is the most cost-efficient. The models results are applicable to both planning for new networks and to migration of existing networks.