Multi-dimensional 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 multi-dimensional 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 and for specific interconnection networks such as rings, grids, tori and hypercubes. 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, tradeoffs are derived between the dimension d and the number of intervals k in multi-dimensional interval routing schemes on hypercubes, grids and tori.