© 2000 by British Computer Society
Masked Interval Routing: A New Routing Scheme
1 Dipartimento di Informatica, Università di Pisa, Italy, Italy Email: luccio@di.unipi.it 2 Department of Computer Science, Mu'tah University, Jordan 3 Department of Computer Science, Mu'tah University, Jordan 4 Dipartimento di Informatica, Università di Pisa, Italy
We introduce the new masked interval routing scheme (MIRS), where a mask is added to each interval to indicate particular subsets of `consecutive' labels. We show that the interval information stored in the network is drastically reduced in some hard cases, proving first that in globe graphs of O$(N)$ vertices the number of intervals per edge goes down from $\Omega(\sqrt{N})$, as required in the classical interval routing scheme (IRS), to O$(\log N)$ in MIRS. The technique is also extended to globe graphs of arbitrary dimensions. The advantage of using MIRS is then demonstrated for butterfly graphs, where we prove that the number of intervals per edge goes down from $\Omega(\sqrt{{N}/{\log N}})$ to O$(\log N)$. This paper is aimed at introducing a new technique. The examples provided show that MIRS is powerful to some extent in the reduction of the number of labels, and may be useful in practice. This work represents a possible new direction for further research.
Received 8 December, 1997. Revised 3 February, 2000.