Network recovery from massive failures under uncertain knowledge of damages

Diman Zad Tootaghaj, Hana Khamfroush, Novella Bartolini, Stefano Ciavarella, Seamus Hayes, Thomas La Porta

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

12 Scopus citations

Abstract

This paper addresses 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 trade-off between the execution time, 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.

Original languageEnglish
Title of host publication2017 IFIP Networking Conference, IFIP Networking 2017 and Workshops
Pages1-9
Number of pages9
ISBN (Electronic)9783901882944
DOIs
StatePublished - Jul 2 2017
Event2017 IFIP Networking Conference and Workshops, IFIP Networking 2017 - Stockholm, Sweden
Duration: Jun 12 2017Jun 16 2017

Publication series

Name2017 IFIP Networking Conference, IFIP Networking 2017 and Workshops
Volume2018-January

Conference

Conference2017 IFIP Networking Conference and Workshops, IFIP Networking 2017
Country/TerritorySweden
CityStockholm
Period6/12/176/16/17

Bibliographical note

Publisher Copyright:
© 2017 IFIP.

ASJC Scopus subject areas

  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Network recovery from massive failures under uncertain knowledge of damages'. Together they form a unique fingerprint.

Cite this