Home - Topics - Papers - Theses - Blog - CV - Photos - Funny

Scalable Internet Routing on Topology-Independent Node Identities

Bryan Ford
Massachusetts Institute of Technology

Technical Report MIT-LCS-TR-926
October 31, 2003


Unmanaged Internet Protocol (UIP) is a fully self-organizing network-layer protocol that implements scalable identity-based routing. In contrast with address-based routing protocols, which depend for scalability on centralized hierarchical address management, UIP nodes use a flat namespace of cryptographic node identifiers. Node identities can be created locally on demand and remain stable across network changes. Unlike location-independent name services, the UIP routing protocol can stitch together many conventional address-based networks with disjoint or discontinuous address domains, providing connectivity between any pair of participating nodes even when no underlying network provides direct connectivity. The UIP routing protocol works on networks with arbitrary topologies and global traffic patterns, and requires only O(log N) storage per node for routing state, enabling even small, ubiquitous edge devices to act as ad-hoc self-configuring routers. The protocol rapidly recovers from network partitions, bringing every node up-to-date in a multicast-based chain reaction of O(log N) depth. Simulation results indicate that UIP finds routes that are on average within 2× the length of the best possible route.

Paper: PDF PostScript

Topics: Networks Identity Scalability Routing Bryan Ford