Abstract

An Interval Routing Scheme (IRS) is a well-known, space ecient routing strategy for routing messages in a distributed network. In this scheme, each node of the network is assigned an integer label and each link at each node is labeled with an interval. The interval assigned to a link e at a node v indicates the set of destination addresses of the messages which should be forwarded through e at v. A Multi-dimensional Interval Routing Scheme (MIRS) is a generalization of IRS in which each node is assigned a multi-dimensional label (which is a list of d integers for the d-dimensional case). The labels assigned to the links of the network are also multi-dimensional (a list of d 1-dimensional intervals). The class of networks supporting linear IRS (in which the intervals are not cyclic) is already known for the 1-dimensional case [FG94]. In this paper, we generalize this result and completely characterize the class of networks supporting linear MIRS (or MLIRS) for a given number of dimensions d. We show that by increasing d, the class of networks supporting MLIRS is strictly expanded. We also give a characterization of the class of networks supporting strict MLIRS (which is an MLIRS in which the intervals assigned to the links incident to a node v, does not contain the label of v).

 

Audio

 

Bibtex