Abstract

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.