Dilation Analysis of Interval Routing for General Graphs

Savio Tse
Department of Computing, The Hong Kong Polytechnic University

Interval routing is a space-efficient routing scheme. It is
attractive because of its simplicity. The nodes are labeled by
numbers from {0,...n-1}, where n is the number of nodes in a graph.
The routing information is based on labeling of the edges of a
network with intervals of node numbers, called interval labels.
We study the problem on unit-cost, undirected, simple graph.
Since interval labels are routing information and one may hope to
have shorter routing paths if we use more labels. Performance of
interval routing can be measured by maximum number of labels over
all edges in the network that are needed for shortest-path routing.
For shortest-path routing, it has been proven that Omega(n) labels
are needed for an edge in some graphs.
In practice, we need not insist on shortest-path routing all the
time. We can analyze interval routing by considering the longest
path it may induce. The length of the longest path is called
``dilation'' in the literature. A trivial upper bound based on
BFS spanning tree is 2D, where D is the diameter of the graph.
A Trivial lower bound is D.
In the first part of the talk, I will give the existing results of
dilation analysis. Second, I will give the outline of the proof
of the lower bound 2D-3 for one-label interval routing. We will
make use of the ``multi-globe'' graph in the proof. This lower
bound is just three hops less than the upper bound.
The final part will focus on planar graphs. For optimal dilation
(ie., every path is no longer than D), we need Omega(D) labels.
I will give the outline of an upper bound result which uses O(D^4)
labels for optimal dilation.

DATE:
January 15, 2003, Wednesday @ 13:40
PLACE: EA-409