INTERVAL ROUTING SCHEMES

Interval routing was introduced to reduce the size of 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 imp lementing a routing function is quite attractive but very little is kn own about the topological properties that must satisfy a network to su pport an interval routing function with particular constraints (shorte st paths, limited number of intervals associated to each direction, et c.). In this paper we investigate the study of the interval routing fu nctions. In particular, we characterize the set of networks which supp ort a linear or a linear strict interval routing function with only on e interval per direction. We also derive practical tools to measure th e efficiency of an interval routing function (number of intervals, len gth of the paths, etc.), and we describe large classes of networks whi ch support optimal (linear) interval routing functions. Finally, we de rive the main properties satisfied by the popular networks used to int erconnect processors in a distributed memory parallel computer.