Bandwidth-optimal Failure Recovery Scheme for Robust Programmable Networks

Andrea Tomassilli 1, 2 Giuseppe Di Lena 3, 4, 5 Frédéric Giroire 1, 6, 2 Issam Tahiri 7 Damien Saucez 4, 5 Stéphane Perennes 1, 6 Thierry Turletti 4, 5 Ruslan Sadykov 7 François Vanderbeck 7 Chidung Lac 3
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
4 DIANA - Design, Implementation and Analysis of Networking Architectures
CRISAM - Inria Sophia Antipolis - Méditerranée
7 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : ISP networks are taking a leap forward thanks to emerging technologies such as Software Defined Networking (SDN) and Network Function Virtualization (NFV). Efficient algorithms considered too hard to be put in practice on legacy networks now have a second chance to be considered again. In this context, we rethink the ISP network dimensioning problem with protection against Shared Risk Link Group (SLRG) failures. In this paper, we consider a path-based protection scheme with a global rerouting strategy, in which, for each failure situation, we may have a new routing of all the demands. Our optimization task is to minimize the needed amount of bandwidth. After discussing the hardness of the problem, we develop two scalable mathematical models that we handle using both Column Generation and Benders Decomposition techniques. Through extensive simulations on real-world IP network topologies and on random generated instances, we show the effectiveness of our methods. Finally, our implementation in OpenDaylight demonstrates the feasibility of the approach and its evaluation with Mininet shows that technical implementation choices may have a dramatic impact on the time needed to reestablish the flows after a failure takes place.
Complete list of metadatas
Contributor : Andrea Tomassilli <>
Submitted on : Friday, April 26, 2019 - 3:40:27 PM
Last modification on : Tuesday, April 30, 2019 - 4:49:43 PM


Files produced by the author(s)


  • HAL Id : hal-02112282, version 1


Andrea Tomassilli, Giuseppe Di Lena, Frédéric Giroire, Issam Tahiri, Damien Saucez, et al.. Bandwidth-optimal Failure Recovery Scheme for Robust Programmable Networks. [Research Report] RR-9272, Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France; Orange Labs R&D [Lannion] (France Télécom). 2019. ⟨hal-02112282⟩



Record views


Files downloads