TITLE: Name Independent Compact Routing

Kofi Laing
Tufts University

Wednesday, February 11, 2004
12:00pm
149 Cullinane Hall
Northeastern University

ABSTRACT:
Networks can be modeled as graphs with nodes representing computers
And edge weights which reflect the cost of communication across each edge. 
We consider the problem of routing between a source and destination node
using local routing tables that are *compact*, meaning the maximum routing
table size is a sublinear function of the network size.  This space
constraint affects the quality of the routes that can be encoded, and we
measure this by defining the *stretch* of a path as the ratio of the route
length between two nodes, to the shortest distance.  It is an easier problem
to solve when the nodes of a network are labeled to encode topological
information about the graph (as one might use the row and column number in a
two-dimensional grid, for example).  However we consider the more difficult
and realistic model, called the *name-independent* model, in which the nodes
are adversarially labeled; each node's label has no functional relationship
to its position in the graph (imagine that someone scrambles the names on
the two dimensional mesh arbitrarily).

In this talk we present new results for the name-independent compact routing
problem, which significantly improve the best known algorithms, and obtain
improved tradeoffs between space and stretch for general graphs.
Specifically we show a stretch 5 scheme that uses approximately O(sqrt(n))
space.  We present two general tradeoff schemes -- one with a stretch of
O(2^k) for approximately O(n^{1/k}) space, which outperforms the other
scheme with stretch O(k^2) given the same space, for small values of k.  We
will also present similar results on roundtrip routing in directed networks,
and new improvements for the special case of routing in a tree network, and
observe that similar improvements in general graphs would entail an
NP-Complete problem related to the problem of optimizing the amount of
routing table information.

(Some of these results are joint work with Arias, Cowen, Rajaraman, and
Taka.)

HOST: Rajmohan Rajaraman