A deadlock-free routing scheme for interconnection networks with irregular topologies
Hsin-Chou Chi, Chih-Tsung Tang · 2002
Interconnection networks with irregular topologies (or irregular networks) are ideal communication subsystems for workstation clusters owing to their incremental scalability. While many deadlock-free routing schemes have been proposed for regular networks such as mesh, torus, and hypercube, they cannot be applied in irregular networks. This paper presents a cost-effective routing architecture, called TRAIN, to solve the routing problem with irregular networks. We show that TRAIN is a deadlock-free scheme. Furthermore, unlike many other routing schemes proposed previously for irregular networks, TRAIN does not require a routing table in the switch. Due to this feature, a TRAIN switch is small and the routing decision can be made rapidly. In order to evaluate the effectiveness of our routing scheme, analysis and event-driven simulation have been performed for various irregular networks. Our results show that TRAIN outperforms other schemes with a higher maximum throughput and lower average latency consistently.