A Robust Optimization Approach to Backup Network Design With Random Failures

作者：Johnston Matthew; Lee Hyang Won^*; Modiano Eytan

来源：IEEE/ACM Transactions on Networking, 2015, 23(4): 1216-1228.

DOI：10.1109/TNET.2014.2320829

• Backup network design
• random failures
• robust optimization

This paper presents a scheme in which a dedicated backup network is designed to provide protection from random link failures. Upon a link failure in the primary network, traffic is rerouted through a preplanned path in the backup network. We introduce a novel approach for dealing with random link failures, in which probabilistic survivability guarantees are provided to limit capacity overprovisioning. We show that the optimal backup routing strategy in this respect depends on the reliability of the primary network. Specifically, as primary links become less likely to fail, the optimal backup networks employ more resource sharing among backup paths. We apply results from the field of robust optimization to formulate an ILP for the design and capacity provisioning of these backup networks. We then propose a simulated annealing heuristic to solve this problem for large-scale networks and present simulation results that verify our analysis and approach.

• 出版日期2015-8
• 单位MIT