Network Recovery from Massive Failures under Uncertain Knowledge of Damages

We address progressive network recovery under uncertain knowledge of damages. We formulate the problem as a mixed-integer linear programming (MILP), and show that it is NP-Hard. We propose an iterative stochastic recovery algorithm (ISR) to recover the network in a progressive manner to satisfy the critical services. At each optimization step, we make a decision to repair a part of the network and gather more information iteratively, until critical services are completely restored. Three different algorithms are used to find a feasible set and determine which node to repair, namely, 1) an iterative shortest path algorithm (ISR-SRT), 2) an approximate branch and bound (ISR-BB) and 3) an iterative multi-commodity LP relaxation (ISR-MULT). Further, we have modified the state-of-the-art iterative split and prune (ISP) algorithm to incorporate the uncertain failures. Our results show that ISR-BB and ISR-MULT outperform the state-of-the-art ”progressive ISP” algorithm while we can configure our choice of the trade-off between the execution time, a number of repairs (cost), and the demand loss. We show that our recovery algorithm, on average, can reduce the total number of repairs by a factor of about 3 with respect to ISP, while satisfying all critical demands.

Check our paper in IFIP Networking 2017:

Network Recovery from Massive Failures under Uncertain Knowledge of Damages

Download our paper here

Presentation Slides

This entry was posted in Network Recovery by Diman Zad Tootaghaj. Bookmark the permalink.

About Diman Zad Tootaghaj

I'm Diman Zad-Tootaghaj, PhD candidate in Pennsylvania State University. I’m working with a group of bright and motivated folks in the Institute for Networking and Security Research (INSR) under supervision of Prof. Thomas La Porta, and Dr. Novella Bartolini. My research area is computer networks, stochastic analysis, operating system, and parallel computing. I graduated from Sharif University of technology, with MSc. in Electrical Engineering.

Leave a Reply