Governing routing in the evolving internet

The Internet plays a crucial role in today's information society, making huge amounts of data available to millions of worldwide users. Started as an academic experiment, in less than a decade, the Internet has indeed become a driving force for economy, pushing the information revolution and changing everybody's life. From a technical perspective, the Internet is a global network of networks, which interconnects di erent Autonomous Systems (ASes). Each AS typically corresponds to a di erent administrative entity. In turn, the network of each AS can contain hundreds of heterogeneous and geographically-distributed network devices. Several network protocols are used to regulate the communication between devices, in order to deliver data packets and to o er higher-level services to the Internet end users. Moreover, to achieve better performance and optimize resources, protocol-speci c parameters are typically ne-tuned, via obscure and ambiguous device con guration languages. As the size of the network, the number of deployed protocols and the com- plexity of device con gurations grow, the behavior of each AS network becomes hard to predict, transforming network management into a nightmare. Even worse, management issues are ampli ed by the frequent need for con gura- tion changes dictated by evolving requirements, new opportunities for resource optimization, and availability of new technologies. Due to the complexity of to- day's networks, many fundamental management activities, like careful network design, con guration generation and deployment, and network monitoring, be- come challenging tasks, each posing its own set of problems. Lots of research and industrial e orts have been devoted to support network administrators in network and con guration management tasks. Unfortunately, recent studies re- port human errors to still be the main cause for network downtime, which are, in turn, responsible for signi cant economical losses. In this thesis, we study how to improve routing management in today's In- ternet. The routing problem consists in nding a path (optimal according to some criteria) on which to forward data packets sent by a given source and targeted to a given destination. Network devices, i.e., routers, exchange infor- mation to reach common routing decisions through routing protocols. However, con guring routing is a much harder problem than it seems at a rst glance. Indeed, routing is a distributed problem by nature, mandating router con g- urations to be always consistent network-wide. However, network administra- tors must specify router con guration through vendor-dependent low-level lan- guages, which makes all the con guration generation process hard to automate and error-prone. Even worse, routing decisions can depend on contingent fac- tors, like message timing. Such a feature makes simulations not always suitable for veri cation purposes. Also, static analysis are not always viable. Moreover, several routing protocols are typically deployed in the same network for di er- ent purposes. In particular, in a classic AS network, Interior Gateway Protocols (IGPs) and the Border Gateway Protocol (BGP) provide reachability to intra and inter-domain destinations respectively. However, di erent routing proto- cols can subtly interact, giving rise to unexpected side e ects. Finally, some protocol-speci c features, like BGP information-hiding and support for routing policies, can be responsible for inconsistent routing and forwarding decisions. Hence, it is not surprising that router con guration errors are pervasive, threat- ening user tra c delivery and Internet connectivity disruption. We propose novel research contributions on routing problems that a ect dif- ferent management tasks. First, we tackle the problem of statically checking a given network con guration for correctness. Such a static check is meant to allow router con gurations to be validated before their deployment in a produc- tion network. In particular, we delve into static testing of BGP con gurations for dynamic stability, that is, guaranteed convergence to a stable routing deci- sion. After formally presenting di erent kinds of stability problems, we prove that statically assessing BGP stability is computationally hard . We then adopt a more practical perspective, by describing a heuristic for solving the BGP sta- bility checking problem, and a convergence checker tool based on that heuristic. Second, we propose advanced techniques to improve network monitoring. We describe a new approach for routing protocols monitoring, based on the highly- optimized packet cloning feature available on many commercial routers. Also, we explore possibilities opened by router programmability, especially focusing on data-plane monitoring and real-time tra c matrix computation. Finally, we study how to evolve network-wide routing con guration with no impact on tra c. Our vision is that network-wide recon gurations should be- come a network primitive in the Future Internet, enabling lossless replacement or con guration ne-tuning of any network protocol without a ecting o ered services. We analyze IGP recon gurations, focusing on the commonly deployed link-state IGPs. We formalize the problem of nding an operational ordering which guarantee no packet loss, we prove its complexity, and we propose al- gorithms and heuristics for solving it. Based on those algorithms, we build a general methodology and a prototype system able to automatically perform lossless recon gurations. After, we turn to BGP recon gurations. We discuss how to improve BGP con gurations, by analyzing design proposals targeted to add exibility. Regarding those proposals, we point out their risks of raising unexpected detrimental side e ects, and we propose design guidelines. After, we tackle the problem of how to recon gure BGP with no impact on both routing and forwarding. After formalizing the problem, we show that an algorithmic ap- proach to nd an operational ordering is not viable in the general case. Hence, we discuss a solution based on minimalistic additions to currently supported router features