Characterization of Networks Supporting Multi-dimensional Linear Interval Routing Schemes.
Yashar Ganjali · 2001
An Interval routing scheme (IRS) is a well-known, space efficient 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 l at a node v indicates the set of destination addresses which should be forwarded through l from 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 a modified version of MLIRS.