Cluster-Fault Tolerant Routing in a Torus

Area of Science:

• Computer Science
• Network Engineering
• Distributed Systems

Background:

• The rapid growth of Internet-connected devices and sensors leads to large-scale networks.
• Modern supercomputers utilize torus interconnection networks due to their advantageous topological properties.
• Fault tolerance, particularly for clustered node failures, is critical in large networks.

Purpose of the Study:

• To propose a novel node-to-node routing algorithm for n-dimensional k-ary torus networks.
• To ensure the algorithm is tolerant to both individual node faults and clustered node faults.
• To analyze the performance and complexity of the proposed fault-tolerant routing algorithm.

Main Methods:

• Development of a new routing algorithm for torus networks.
• Analysis of fault tolerance capabilities, specifically for cluster faults.
• Worst-case time complexity analysis of the algorithm.

Main Results:

• The algorithm guarantees a fault-free path with a maximum length of n(2k + ⌊k/2⌋ - 2).
• The worst-case time complexity is determined to be O(n^2 k^2 |F|), where F is the set of faulty nodes.
• The proposed algorithm demonstrates tolerance to both single node and cluster faults.

Conclusions:

• The developed routing algorithm is effective for fault-tolerant communication in large-scale torus networks.
• This research addresses critical challenges in maintaining network reliability amidst increasing device connectivity and supercomputing demands.
• The algorithm offers a viable solution for ensuring robust network performance in the presence of complex fault scenarios.