Segment-Based Routing: A New Approach to Efficient Topology-Agnostic Routing
José Flich, José F. Duato · 2005
During the last years, Clusters of PCs are being used as a cost-effective alternative for building high-performance compu-ting and server systems. In these systems, high-speed interconnects like Myrinet, Quadrics and InfiniBandTM are currently used as they offer reliable performance at affordable cost. In these networks routing is deterministic and virtual channels are not used for routing as they simply do not exist (Myrinet), or they are reserved for other purposes like QoS (InfiniBand). In this paper we propose a novel approach in order to get a topology-agnostic routing able to adapt to the topology. The algorithm, referred to as Segment-Based Routing (SR), partitions the topology in such a way that allows to place a bidirectional routing restriction on each partition, being its position independent of the relative positions of the remaining restrictions. This allows much greater flexibility than offered by previous proposals. We intend to use this flexibility as a way to achieve an effective (simple and efficient) routing algorithm that obtains good performance regardless of the topology. Evaluation results show that SR is able to adapt to the topology, and therefore, it achieves better results than up*/down* and FX (in some cases, FX throughput is increased by a factor of 1.8). This promising result suggests that much greater benefits can be obtained by the proposed method. 1