Skip to Main content Skip to Navigation
New interface
Journal articles

Design of Robust Programmable Networks with Bandwidth-optimal Failure Recovery Scheme

Andrea Tomassilli 1 Giuseppe Di Lena 2, 3, 1 Frédéric Giroire 1 Issam Tahiri 4 Damien Saucez 3 Stéphane Pérennes 1 Thierry Turletti 3 Ruslan Sadykov 4, 5 François Vanderbeck 4 Chidung Lac 2 
1 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
3 DIANA - Design, Implementation and Analysis of Networking Architectures
CRISAM - Inria Sophia Antipolis - Méditerranée
5 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 : More than ever, data networks have demonstrated their central role in the world economy, but also in the well-being of humanity that needs fast and reliable networks. In parallel, with the emergence of Network Function Virtualization (NFV) and Software Defined Networking (SDN), efficient network algorithms considered too hard to be put in practice in the past now have a second chance to be considered again. In this context, as new networks will be deployed and current ones get significant upgrades, it is thus time to rethink the network dimensioning problem with protection against failures. In this paper, we consider a path-based protection scheme with the global rerouting strategy in which, for each failure situation, there may be 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 randomly generated instances, we show the effectiveness of our methods: they lead to savings of 40 to 48% of the bandwidth to be installed in a network to protect against failures compared to traditional schemes. Finally, our implementation in OpenDaylight demonstrates the feasibility of the approach. Its evaluation with Mininet shows that our solution provides sub-second recovery times, but the way it is implemented may greatly impact the amount of signaling traffic exchanged. In our evaluations, the recovery phase requires only a few tens of milliseconds for the fastest implementation, compared to a few hundreds of milliseconds for the slowest one.
Document type :
Journal articles
Complete list of metadata
Contributor : Frédéric Giroire Connect in order to contact the contributor
Submitted on : Monday, November 22, 2021 - 5:27:44 PM
Last modification on : Thursday, August 4, 2022 - 4:58:29 PM
Long-term archiving on: : Wednesday, February 23, 2022 - 8:29:41 PM


Files produced by the author(s)



Andrea Tomassilli, Giuseppe Di Lena, Frédéric Giroire, Issam Tahiri, Damien Saucez, et al.. Design of Robust Programmable Networks with Bandwidth-optimal Failure Recovery Scheme. Computer Networks, 2021, 192 (108043), ⟨10.1016/j.comnet.2021.108043⟩. ⟨hal-03441630⟩



Record views


Files downloads