A Memory-Effective Routing Strategy for Regular Interconnection Networks

Massively parallel computing systems have been or are being built with thousands of nodes. In such systems, high-performance interconnection networks are crucial to achieve the maximum performance. Routing is one of the most important design issues of interconnection networks. Routing strategies can be mainly classified as source and distributed routing. Source routing has been used in some networks because routers are very simple. On the other hand, distributed routing allows more flexibility, but the routers are more complex. Distributed routing can be implemented by a fixed hardware specific to a routing function on a given topology, or by using forwarding tables that are very flexible but suffer from a lack of scalability. In this paper, we propose a distributed routing strategy for commercial switches, Flexible Interval Routing, that is scalable for the most widely used regular topologies (tori and meshes) because it is not based on tables. At the same time, the strategy is easy to reconfigure to deal with changes in the topology or in the routing algorithm for a given topology, being able to implement the most commonly-used routing algorithms in regular topologies.