TITLE:Interval Routing Schemes
AUTHORS:Pierre Fraigniaud and Cyril Gavoille
ABSTRACT:
Interval routing was introduced to reduce the size of the routing
tables: a router finds the direction where to forward a message by
determining which interval contains the destination address of the
message, each interval being associated to one particular
direction. This way of implementing routing function is quite
attractive but very few is known about the topological properties that
must satisfy a network to support an interval routing function with
particular constraints (shortest paths, limited number of intervals
associated to each direction, etc). In this paper, we deeply
investigate the study of the interval routing functions. In
particular, we characterize the set of networks which support a
linear or a linear strict interval routing function with
only one interval per direction. We also derive practical tools to
measure the efficiency of an interval routing function (number of
intervals, length of the paths, etc), and we describe large classes of
networks which support optimal (linear) interval routing
functions. Finally, we derive the main properties satisfied by the
popular networks used to interconnect processors in a distributed
memory parallel computer.