Date Added: Dec 2010
Routing scalability is highly desirable for very large, dynamic, and resource-constrained networks, including many peer-to-peer systems and the Internet. Shortest path routing algorithms (link state, distance vector, path vector, etc.) all require (n) memory at each router for a network with n destinations, and at least as much communication and computation to build the routing tables. One way to scale routing is to use a structured network topology that makes routing easy. Examples range from torus networks in supercomputers to planar networks which permit greedy geographic routing to hypercubes, small world networks, and other topologies in distributed hash tables. But requiring a particular highly structured topology is not feasible for general-purpose networks.