Multidimensional interval routing schemes

• Published in: Theoretical computer science 1998-09, Vol.205 (1), p.115-133
• Main Authors: Flammini, Michele, Gambosi, Giorgio, Nanni, Umberto, Tan, Richard B.
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; Compact routing methods; Computer science; control theory; systems; Computer systems and distributed systems. User interface; Dimensions; Exact sciences and technology; Information retrieval. Graph; Interconnection networks; Interval routing schemes; Product graphs; Software; Theoretical computing
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/S0304-3975(97)00070-4

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 k-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 (as 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.