Practical Routing-Layer Support for Scalable Multihoming

The recent trend of rapid increase in routing table sizes at routers comprising the Internet's core is posing a serious challenge to the current Internet's scalability, availability, and stability. Multihoming is a prime contributor to this table size explosion. This paper argues that it is possible to a) scale the Internet's routing table sub-linearly with degree of multihoming, and b) improve routing convergence times even under pervasive multihoming using simple and incrementally deployable extensions to today's routing protocols. We present an addressing and routing protocol called SIMPLER (Scalable IP Multihoming Protocol LEveraging Routing), which is designed to minimize and contain the propagation in space and time of non-aggregatable routes. SIMPLER's prefix containment property results in lower lookup and route processing costs (promotes scalability), and faster convergence time (helps network availability and stability). SIMPLER vastly diminishes the number of non-aggregatable prefixes appearing in the Internet core due to multihoming (to zero in the absence of network faults, and O(number of faults) otherwise), and always leaks fewer non-aggregatable prefixes than today's dominant multihoming strategy of "hole punching". Additionally, SIMPLER provides Transport-Layer Survivability (TLS) and better routing policy management, while offering the same routing robustness as today's multihoming. The main cost of SIMPLER is the increased use of address space (O(log(network size)) in the average case). SIMPLER is carefully designed to be useful to both multihomed transit providers and multihomed leaf sites