Speaker: Muneeb Ali, Princeton
Title: Routing with Constant State 

Abstract:

Scalability is one of the fundamental problems in computer
networks. Most deployed routing protocols in today's networks use
shortest-path routing. Path-vector routing in BGP (inter-domain),
link-state routing in OSPF/ISIS (intra-domain), and distance-vector
routing in AODV (ad-hoc networks) are all variations of shortest-path
routing. The growth rate of routing tables in shortest-path routing
protocols is linear, polynomial, or worse. Nodes need to know about
all other nodes in the network to calculate the shortest-path to any
given node. For a network to be scalable, logarithmic or better
scaling is desired.

There is a fundamental tradeoff between state (entries in routing
tables) and stretch (ratio of worst-case and shortest path). We
propose Ley Line Routing (L2R), a network layer protocol that occupies
a unique point in the design space of routing; its routing state is
independent of the network size. L2R allows users to specify the
amount of state per node and then optimizes stretch within that
limit. L2R works by serializing nodes onto a logical line of
connectivity. In its simplest form, each node maintains only two
routing entries, the prior and next nodes on the line, and the routing
stretch can be O(N). Nodes can maintain additional routing entries
that allow it to skip further along the line. With respect to network
size, these skip entries provide a tunable tradeoff between routing
state and routing stretch.

We discuss the feasibility of L2R in three types of networks a)
embedded networks of tiny devices, b) the Internet, and c) networks in
developing regions.