Multi-dimensional interval routing schemes

Abstract. One of the fundamental tasks in any distributed computing system is routing messages between pairs of nodes. An Interval Routing Scheme (IRS) is a space efficient way of routing messages in a network. The problem of characterizing graphs that support an IRS is a well-known problem and has been studied for some variants of IRS. It is natural to assume that the costs of links may vary over time (dynamic cost links) and to try to find an IRS which routes all messages on shortest paths (optimum IRS). In this paper, we study this problem for a variant of IRS in which the labels assigned to the vertices are d-ary integer tuples (d-dimensional IRS). The only known results in this case are for specific graphs like hypercubes, n-dimensional grids, or for the 1-dimensional case. We give a complete characterization for the class of networks supporting multi-dimensional strict and linear (no cyclic intervals) interval routing schemes with dynamic cost links