Scalable Internet Routing on Topology-Independent Node Identities
Bryan Ford
Massachusetts Institute of Technology
Technical Report MIT-LCS-TR-926
October 31, 2003
Abstract:
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.