Local Fault Tolerance Analysis in Strictly Nonblocking Clos and Multi-Log_<i>q</i> <i>N</i> Networks

Fault tolerance is a fundamental consideration in the design of multistage interconnection networks (MINs). While extensive research has been conducted on the fault tolerance of blocking networks, nonblocking networks have received less attention. Nonblocking networks, which guarantee the accommodation of all possible permutations without blocking, present greater analytical challenges but are essential for high-reliability applications. Among MINs, the nonblocking properties of Clos and multi-Log<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">_qN</i> networks, commonly used in parallel and high-performance computing systems, have been widely studied. However, fault tolerance has been explored only for rearrangeably nonblocking (RNB) MINs, which include Clos networks and specific cases of multi-Log<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">_qN</i> networks, leaving strictly nonblocking (SNB) MINs underexplored. SNB MINs are highly attractive for applications demanding robust and uninterrupted operation. Though they have higher hardware requirements than RNB MINs, they ensure new connections can be established without requiring rearrangements, thereby eliminating potential connection interruptions. This paper addresses the gap in the research of SNB MINs by analyzing the fault tolerance capabilities of SNB Clos and multi-Log<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">_qN</i> networks. The analysis is particularly challenging due to the complexity introduced by the extensive routing scenarios inherent to SNB networks. To address these challenges, we propose a deterministic method for evaluating the local fault tolerance of SNB Clos and multi-Log<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">_qN</i> networks. Specifically, we derive the maximum number of tolerable non-contact faults within each shell s, which includes both the sth node stage and its symmetric counterpart, while ensuring the feasibility of all possible permutations. Our findings demonstrate that the SNB property is preserved in multi-Log<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">_qN</i> networks with at least one additional node stage, even under numerous non-contact faults. In contrast, Clos networks lose their SNB capability with even a single non-contact fault. These results offer valuable insights into the fault tolerance characteristics of SNB networks and provide a robust foundation for designing resilient interconnection architectures in high-performance computing systems.