TITLE:On the Dilation of Interval Routing
AUTHORS:Cyril Gavoille
ABSTRACT:
In this paper we deal with interval routing on n-node networks
of diameter D. We show that for every fixed D>=2, there
exists a network on which every interval routing scheme with
O(n/logn) intervals per link has a routing path length
at least \floor{3D/2}-1. It improves the lower bound on the
routing path lengths for the range of very large number of
intervals. No result was known about the path lengths whenever more
than \Theta(\sqrt{n}) intervals per link was used. Best-known
lower bounds for a small number of intervals are 2D-O(1) for 1
interval [TL97b], and 3D/2-O(1) up to \Theta(\sqrt{n})
intervals [KRS97]. For D=2, we show a network on which any
interval routing scheme using less than n/4 - o(n)
intervals has a routing path of length at least 3. Moreover, we build
a network of bounded degree on which every interval routing scheme
with routing path lengths bounded by 3D/2 - o(D)
requires \Omega(n/log^{2+e}{n}) intervals per
link, where e is an arbitrary non-negative constant.