Average Packet Latency and Link Fault Tolerant Routing Algorithms in Tree-Like Interconnection Networks

In the first part of this research, we propose two hybrid topologies named k-Cube k-Ary n-Tree (CAT) and Mirrored k-Cube k-Ary n-Tree (MiCAT), based on fat-trees and hypercubes. We evaluate the path diversity, cost, performance, and average packet latency of CAT and MiCAT. The results show that CAT and MiCAT can save up to 87% switches and 80% links in a large-scale parallel system, for example, if k = n = 8, compared to fat-trees, and meanwhile, both CAT and MiCAT have higher path diversities than fat-trees. The second part gives four link fault tolerant routing algorithms in Mirrored k-ary n-tree (MiKANT) interconnection networks and evaluates their performance through simulations. In addition, the performance of the combined algorithms is also evaluated.