Methods and Techniques for Disruption-Free Network Reconfiguration

Tue, 10/02/2012 - 10:20 by Laurent Vanbever


With the advent of the Internet, many Internet services have become mission critical. Network operators are therefore under tremendous pressure to make their networks highly available. Yet, network operators also need to regularly change the configuration (i.e., reconfigure) of their networks to deploy new services or upgrade network devices. Despite being necessary, such reconfiguration operations are an important source of concerns as they can lead to severe disruptions.

In this thesis, we aim at enabling disruption-free routing reconfiguration which consists in modifying the way a running network forwards traffic without incurring any traffic losses. We consider both intradomain and interdomain routing protocols, the two major routing protocol families used in today's Internet. In both cases, we prove that it is necessary to precisely order the reconfiguration operations. Intuitively, this ordering is such that each intermediate state maintains the network global correctness. Unfortunately, we show that such an ordering does not always exist. Moreover, we prove that deciding if a disruption-free reconfiguration ordering exists is computationally hard (i.e., NP-hard). Despite the inherent complexity, we manage to enable disruption-free reconfiguration in most reconfiguration scenarios and to reduce significantly the number of anomalies in the rest of them. Our techniques include efficient ordering algorithms, configuration guidelines and practical reconfiguration procedures. By combining theory and practice, we also implement and evaluate a reconfiguration framework which completely automates the reconfiguration process including the live provisioning of device configurations.

Laurent Vanbever
PhD thesis
Université catholique de Louvain, October 2012.
network management, reconfiguration, configuration, igp, bgp
Full text
pdf    (1.61 MB)
pdf    (5.92 MB)
Cite it
See here

IEEE Copyright Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

ACM Copyright Notice: Copyright 1999 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page or intial screen of the document. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM Inc., fax +1 (212) 869-0481, or

Springer-Verlag LNCS Copyright Notice: The copyright of these contributions has been transferred to Springer-Verlag Berlin Heidelberg New York. The copyright transfer covers the exclusive right to reproduce and distribute the contribution, including reprints, translations, photographic reproductions, microform, electronic form (offline, online), or any other reproductions of similar nature. Online available from Springer-Verlag LNCS series.