02-04

Distributed Compact Routing

Common wisdom is that the way to scale networks to large size is hierarchy: routing is performed on higher level aggregates across domains, separately from routing within domains. We live with the consequences: inflated path lengths, and the use of location-dependent addresses (IP addresses in the Internet) which complicate management, mobility, and multihoming.

I will present Distributed Compact Routing, a protocol which (1) guarantees scalability, in the form of roughly \\\\sqrt{n} state for a network of n nodes; (2) guarantees approximately-shortest paths, in the form of constant stretch; and (3) routes directly on flat, location-independent identifiers. Our work builds on recent theoretical advances in the area of compact routing. Past attempts to translate these centralized algorithms to practical distributed protocols have had limited success, compromising state or stretch guarantees or assuming special topologies. Our results thus represent a significant step forward in routing technology, which we believe has direct applicability to many kinds of networks including peer-to-peer networks, Internet routing, and content-centric networks.

Joint work with Ankit Singla, Kevin Fall, Gianluca Iannaccone, and Sylvia Ratnasamy.