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 all n and D such
that 2 <= D <= \Theta(n), there exists a network on
which every interval routing scheme with less than
\Omega(n/(Dlog(n/D))) 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. Moreover, we build a network of bounded
degree, for all n and D such that \Theta(logn) <=
D <= \Theta(n), on which every interval routing scheme
with less than \Omega(n/D2) intervals per
link has a routing path length at least 3D/2 - O(logn).