A deadlock-free routing scheme for interconnection networks with irregular topologies

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