SCALABILITY AND STABILITY OF IP AND COMPACT ROUTING

Abstract

Inter-domain routing scalability has always been one of the most challenging issues for the Internet. Recently, it has raised strong concerns again. One reason is the growth of the Internet itself. In particular, the practice that customer networks widely use provider independent (PI) addresses and deploy traffic engineering solutions, is identified as the key reason. In addition, the Internet’s original hierarchical inter-domain topology structure, which was designed for routing scalability, has evolved into a small world graph. On the other hand, routing schemes based on routing aggregation cannot scale well on small world graphs, and tunnel-based solutions relying on the reliable and effective Identifier/Locator mapping dissemination are proved to be un-scalable either. This calls for other routing solutions that are scalable for the need. In the literature, compact routing has been developed for a long time with routing scalability as the major objective. Specifically, it has also been shown very promising in terms of routing scalability. However, this promising performance of the literature compact routing schemes is for static networks. For dynamic networks, their performances are not studied. Since most networks are dynamic in nature, due to, e.g., network upgrading, network failure, and network maintenance, it is hence desired to design routing schemes that are robust and scalable for such dynamic scenarios. In this thesis, a totally distributed and scalable compact routing scheme is firstly developed. The study shows that the developed compact routing scheme still keeps the good scalability in the dynamic network environment. Then, the distributed compact routing scheme is enhanced by accounting for the nearby scale from topology at the inter-domain level. The study shows that the enhanced scheme has smaller average routing stretch while keeping the routing scalability. Thirdly, to gain deeper understanding of compact routing, the routing scalability and stability of typical compact routing schemes are studied in the context of dynamic networks. There is an implicit assumption in the Internet routing community: structured address labels are key for routing scalability and the structured address labels must reflect the network topology to make the routing algorithms scale well. The thesis finally investigates the validity of this assumption. Specifically, the thesis formulates the concepts of address label and identifier in a mathematical manner and analyzes their properties and mutual relations. It is observed that a fine address label is a sequence of address labels with different granularities plus the identifier. With the logic predicate, the explicit relation between the address label and the underlying network topology is modeled. It is shown that the total number of routing entries is decided by the set of binary relation, which is defined by the logic predicate describing the relation between the address label and the underlying network topologies. That is, the total number of routing entries is equal to the number of equivalent class of address labels. Based on these, the key components of a routing system are identified and a simple address label management model is developed. With this model, it is shown that no routing scheme based on the flat address labels is scalable, i.e., without the proper construction and allocation of address labels based on the specific network topologies, a routing algorithm with the good routing scalability is unachievable. In all these studies, simulation has been used. However, for studying the inter-domain routing scalability, the simulation of large-scale network routing with the business model taken into account imposes is highly challenging. Currently, the popular BGP simulators are packet level, i.e., they are running on TCP/IP and actual BGP messages are exchanged over BGP peers. In addition, the simulations with the popular BGP simulators are performed on the router level topologies. They demand formidable computing resources for simulating large-scale networks. To overcome this limitation, various simulation tools have been developed in this thesis work for the research objective by making a reasonable tradeoff between model accuracy and the interested features.