Multidimensional interval routing schemes

Interval routing scheme (k-IRS) is a compact routing scheme on general networks. It has been studied extensively and recently been implemented on the latest generation INMOS Transputer Router chip. In this paper we introduce an extension of the Interval Routing Scheme k-IRS to the multidimensional case [k,d]-MIRS, where k is the number of intervals and d is the number of dimensions. Whereas R-IRS only represents compactly a single shortest path between any two nodes, with this new extension we are able to represent all shortest paths compactly. This is useful for fault-tolerance and traffic distribution in a network. We study efficient representations of all shortest paths between any pair of nodes for general network topologies, for product graphs and for specific interconnection networks such as rings, grids, tori, hypercubes and chordal rings. For these interconnection networks we show that for about the same space complexity as K-IRS we can represent all shortest paths in [k,d]-MIRS las compared to only a single shortest path in K-IRS), Moreover, trade-offs are derived between the dimension d and the number of intervals k in multidimensional interval routing schemes on hypercubes, grids and tori. (C) 1998-Elsevier Science B.V. All rights reserved