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 implement ed on the latest generation INMOS Transputer Router chip. In this pape r we introduce an extension of the Interval Routing Scheme k-IRS to th e multidimensional case [k,d]-MIRS, where k is the number of intervals and d is the number of dimensions. Whereas R-IRS only represents comp actly a single shortest path between any two nodes, with this new exte nsion we are able to represent all shortest paths compactly. This is u seful for fault-tolerance and traffic distribution in a network. We st udy efficient representations of all shortest paths between any pair o f nodes for general network topologies, for product graphs and for spe cific 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 shortes t 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 th e number of intervals k in multidimensional interval routing schemes o n hypercubes, grids and tori. (C) 1998-Elsevier Science B.V. All right s reserved.