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