Harvard Theory of Computation Seminar
Compact Routing from Theory to Practice
Lenore J. Cowen, Tufts University
Place and Time: Monday, May 7, Maxwell Dworkin 221
Refreshments at 2:30pm, talk at 2:45pm
ABSTRACT
The compact routing problem is a classical problem in the theory of
distributed algorithms. Compact routing achieves routing tables whose
size grows sublinearly with the number of network nodes in exchange
for near optimal, rather than optimal shortest path routes.In
addition, some recent schemes achieve a "name independence" property
where node are arbitrarily assigned persistent identifiers in a way that is
decoupled from the underlying network topology. `Name independence''
(also called ``flat addressing'' or a ``flat address space'' in the
Networking community) has recently gained traction as one approach to
clean slate Internet redesign that may be required to handle
increasing number of mobile nodes (i.e. laptops; wireless devices) and
dynamic changes in network connectivity. In fact, several recent
proposals for a complete redesign of the Internet architecture have
called for separating the naming layer from the packet forwarding
layer.
We show that compact routing schemes perform even better on power-law
networks that may more realistically model the Internet's inter-AS
graph, and give both theoretical and experimental results. We also
discuss remaining questions about dynamic networks, congestion
control, traffic engineering, and policy that must also be addressed
for any compact routing scheme to be extended into a realistic
candidate for a next-generation routing protocol.