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 ecient way of routing messages in a network. The problem of character- izing 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 nd an IRS which routes all mes- sages 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 specic 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.

 

Audio

 

Bibtex