Fault-Tolerant General Beneš Networks
Bey‐Chi Lin · IEEE Transactions on Communications · 2023
Beneš networks are well-known rearrangeable nonblocking (RNB) multistage networks. The so-called conventional Beneš networks are based on$2\times 2$switches. In this paper, Beneš network is a general term used to refer to an$N\times {N}~n$-nary Beneš network. Such networks, denoted by B($n$,$t)$, where$N = n^{t}$and$t \ge2$, are based on regular$n\times n$switches, and are RNB as well. A Beneš network is constructed recursively from a 3-stage Clos network. For an$N\times N$RNB Clos network C($n$,$m$,$r)$, where$N = nr$and$m \ge n$, the maximum allowable number of non-contact faults in each single shell for realizing any permutation has been investigated in an earlier study, where shell$k$in a network consists of both the$k$th and the$k$th-to-last node stages. That study showed that, for a given integer$N$, an RNB C($n$,$n$,$r)$network with larger$n\times n$switches leads to tolerance of more non-contact faults in shell 1. In this paper, for an$N\times N$B($n$,$t)$network, we study the maximum allowable number, say$f_{k}$, of non-contact faults for any permutation not only in each single shell$k$, but also in all shells simultaneously under the fault condition that at most$f_{k}$non-contact faults are arbitrarily located in the switches in each shell$k$. We call the former the fault tolerance capability in a single shell, and the latter the fault tolerance capability of the network. We show that a larger switch size, i.e.,$n\times n$, in an${N} \times N$B($n$,$t)$network leads to a higher fault tolerance capability of the network and a higher fault tolerance capability in each non-middle shell. An$N\times N$Beneš network B($n$,$t)$considers only the value of$N$which is a power of$n$. To consider a flexible$N$with$N = n^{s}\cdot \textit {q}$, where$s\ge2$,$1 < {q} < n$and${q}\vert n$, which means that$n$is divisible by${q}$, we propose in this paper an$N\times N$RNB Beneš-type network using regular$n\times n$switches, which is called an extended Beneš and denoted by B($n$,$s$,${q})$. Both Beneš and extended Beneš networks are based on regular switches, and they have better scalabilities than a Clos network. We define a network’s fault tolerance rate as the ratio of the fault tolerance capability to the total crosspoints in the network. For given integers$N$and$n$, we derive that the fault tolerance capability and fault tolerance rate of an${N} \times N$Beneš (or extended Beneš) network are higher than or equal to those of an$N\times N$RNB C($n$,$n$,$r)$network, and the former outperforms the latter in most cases.