Local Fault Tolerance Analysis in Strictly Nonblocking Clos and Multi-Log<sub><italic>q</italic></sub><italic>N</italic> 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 accommodat...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10965653/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849311227997585408 |
|---|---|
| author | Bey-Chi Lin |
| author_facet | Bey-Chi Lin |
| author_sort | Bey-Chi Lin |
| collection | DOAJ |
| description | 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<inline-formula> <tex-math notation="LaTeX">${}_{q} N$ </tex-math></inline-formula> 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<inline-formula> <tex-math notation="LaTeX">${}_{q} N$ </tex-math></inline-formula> 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<inline-formula> <tex-math notation="LaTeX">${}_{q} N$ </tex-math></inline-formula> 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<inline-formula> <tex-math notation="LaTeX">${}_{q} N$ </tex-math></inline-formula> 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<inline-formula> <tex-math notation="LaTeX">${}_{q} N$ </tex-math></inline-formula> 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. |
| format | Article |
| id | doaj-art-0f8b45de88d44d539f30a9625d9f0206 |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-0f8b45de88d44d539f30a9625d9f02062025-08-20T03:53:28ZengIEEEIEEE Access2169-35362025-01-0113706987070410.1109/ACCESS.2025.356067510965653Local Fault Tolerance Analysis in Strictly Nonblocking Clos and Multi-Log<sub><italic>q</italic></sub><italic>N</italic> NetworksBey-Chi Lin0https://orcid.org/0000-0001-7854-0187Department of Applied Mathematics, National University of Tainan, Tainan, TaiwanFault 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<inline-formula> <tex-math notation="LaTeX">${}_{q} N$ </tex-math></inline-formula> 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<inline-formula> <tex-math notation="LaTeX">${}_{q} N$ </tex-math></inline-formula> 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<inline-formula> <tex-math notation="LaTeX">${}_{q} N$ </tex-math></inline-formula> 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<inline-formula> <tex-math notation="LaTeX">${}_{q} N$ </tex-math></inline-formula> 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<inline-formula> <tex-math notation="LaTeX">${}_{q} N$ </tex-math></inline-formula> 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.https://ieeexplore.ieee.org/document/10965653/Fault tolerancenon-contact faultClos networksmulti-LogqN networksstrictly nonblocking networksmultistage interconnection networks |
| spellingShingle | Bey-Chi Lin Local Fault Tolerance Analysis in Strictly Nonblocking Clos and Multi-Log<sub><italic>q</italic></sub><italic>N</italic> Networks IEEE Access Fault tolerance non-contact fault Clos networks multi-LogqN networks strictly nonblocking networks multistage interconnection networks |
| title | Local Fault Tolerance Analysis in Strictly Nonblocking Clos and Multi-Log<sub><italic>q</italic></sub><italic>N</italic> Networks |
| title_full | Local Fault Tolerance Analysis in Strictly Nonblocking Clos and Multi-Log<sub><italic>q</italic></sub><italic>N</italic> Networks |
| title_fullStr | Local Fault Tolerance Analysis in Strictly Nonblocking Clos and Multi-Log<sub><italic>q</italic></sub><italic>N</italic> Networks |
| title_full_unstemmed | Local Fault Tolerance Analysis in Strictly Nonblocking Clos and Multi-Log<sub><italic>q</italic></sub><italic>N</italic> Networks |
| title_short | Local Fault Tolerance Analysis in Strictly Nonblocking Clos and Multi-Log<sub><italic>q</italic></sub><italic>N</italic> Networks |
| title_sort | local fault tolerance analysis in strictly nonblocking clos and multi log sub italic q italic sub italic n italic networks |
| topic | Fault tolerance non-contact fault Clos networks multi-LogqN networks strictly nonblocking networks multistage interconnection networks |
| url | https://ieeexplore.ieee.org/document/10965653/ |
| work_keys_str_mv | AT beychilin localfaulttoleranceanalysisinstrictlynonblockingclosandmultilogsubitalicqitalicsubitalicnitalicnetworks |