On Critical Service Recovery after Massive Network Failures

Novella Bartolini, Stefano Ciavarella, Thomas F. La Porta, Simone Silvestri

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


This paper addresses the problem of efficiently restoring sufficient resources in a communications network to support the demand of mission critical services after a large-scale disruption. We give a formulation of the problem as a mixed integer linear programming and show that it is NP-hard. We propose a polynomial time heuristic, called iterative split and prune (ISP) that decomposes the original problem recursively into smaller problems, until it determines the set of network components to be restored. ISP's decisions are guided by the use of a new notion of demand-based centrality of nodes. We performed extensive simulations by varying the topologies, the demand intensity, the number of critical services, and the disruption model. Compared with several greedy approaches, ISP performs better in terms of total cost of repaired components, and does not result in any demand loss. It performs very close to the optimal when the demand is low with respect to the supply network capacities, thanks to the ability of the algorithm to maximize sharing of repaired resources.

Original languageEnglish
Article number7896641
Pages (from-to)2235-2249
Number of pages15
JournalIEEE/ACM Transactions on Networking
Issue number4
StatePublished - Aug 2017

Bibliographical note

Publisher Copyright:
© 1993-2012 IEEE.


  • Network recovery
  • flow restoration
  • massive network disruption

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'On Critical Service Recovery after Massive Network Failures'. Together they form a unique fingerprint.

Cite this