Mirrored K‐Ary N‐Tree and its efficiency of fault tolerance. (22nd August 2020)

• Record Type: Journal Article
• Authors: Li, Yamin; Chu, Wanming
• Is Part Of: International journal of communication systems. Volume 33:Number 17(2020)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2020-08-22
• Subjects: deadlock‐free -- fat‐tree -- fault tolerance -- interconnection network -- k‐ary n‐tree -- routing algorithm; Telecommunication systems -- Periodicals; 621.382
• DOI: 10.1002/dac.4594
• Languages: English
• ISSNs: 1074-5351

Abstract

Summary: Fat‐tree is one of the most commonly used topologies in the interconnection networks of modern supercomputers and datacenters. In a traditional fat‐tree, k ‐ary n ‐tree for instance, the degree of root switches is less than that of other switches. Fat‐tree is a folded version of a Clos network. A Clos network uses the same degree switches in all stages. However, fat‐tree or Clos network has a high switch cost and great packet latency. This paper introduces a Mirrored K ‐Ary N ‐Tree (MiKANT) network and presents switch fault‐tolerant routing algorithms for it. Compared with k ‐ary n ‐trees and Clos networks, MiKANT connects more compute nodes with fewer switches and links so that it can be implemented at a lower hardware cost, it uses switches that have the same number of ports to keep the regularity, and it shortens the average distance to reduce the packet latency for achieving higher communication performance. We give three simple deadlock‐free switch fault‐tolerant routing algorithms for MiKANT and evaluate their performance. The simulation results show that the proposed algorithms achieve much higher performance than the shortest path routing algorithm. Although MiKANT uses fewer switches and links than fat‐tree, the simulation result shows that it has an almost the same successful routing ratio as the fat‐tree for the switch fault tolerance. Abstract : This paper introduces a Mirrored K ‐Ary N ‐Tree (MiKANT) network and presents switch fault‐tolerant routing algorithms for it. Compared with k ‐ary n ‐trees and Clos networks, MiKANT connects more compute nodes with less switches and links so that it can be implemented at lower hardware cost, it uses switches that have a same number of ports to keep the regularity, and it shortens the average distance to reduce the packet latency for achieving higher communication performance. We give three simple deadlock‐free switch fault‐tolerant routing algorithms for MiKANT and evaluate their performance.