TITLE: Optimal Interval Routing AUTHORS: Pierre Fraigniaud and Cyril Gavoille ABSTRACT: Interval routing was introduced to reduce the size of the routing tables. This way of implementing routing functions is quite attractive but very few is known on the topological properties that should satisfy a network to admit an interval routing function satisfying particular constraints (shortest paths, limited number of intervals associated to each direction, etc). In this paper, we investigate the study of {\em optimal} interval routing functions, that is routing functions that construct shortest paths. In particular we derive practical tools that allow to determine if a network supports or not an optimal interval routing function. We describe large classes of networks that admit optimal interval routing functions. We also study the case of the usual networks that interconnect the processors of a distributed memory parallel computer.