Static and Dynamic Low-Congested Interval Routing Schemes

Interval Routing Schemes (IRS for short) have been extensively investigated in the past years with special regard to shortest paths. Besides their theoretical interest, IRS have practical applications, as they have been implemented with wormhole routing in the last generation of INMOS Transputer Router Chips. In this paper we consider IRS that are optimal with respect to the congestion of the induced path system. In fact, wormhole routing is strongly influenced by the maximum number of paths that share a physical link and from low to moderate congestion it outperforms the previous packet switching technique. We provide a general framework able to deal with the various congestion issues in IRS. In fact, it is possible to distinguish between static cases, in which the source-destination configurations are fixed, and dynamic cases, where they vary over time. All these situations can be handled in a unified setting, thanks to the notion of competitiveness introduced in this paper. Regarding the one-to-all communication pattern, we show that constructing competitive IRS for a given network is an intractable problem, both for the static and the dynamic case, that is respectively when the root node is fixed and when it can change along the time. Then, we provide nicely competitive $1$-IRS for relevant topologies, both for one-to-all and all-to-all communication patterns. Networks considered are chains, trees, rings, chordal rings and multi-dimensional grids and tori. We consider both the directed congestion case, in which there are pairwise opposite unidirectional links connecting two neighbor processors, and the undirected congestion case, in which two neighbors are connected by a single bi-directional link.