A fault-tolerant rearrangeable permutation network

As optical communication becomes a promising networking choice, the well-known Clos network has regained much attention recently from optical switch designers/manufacturers and cluster computing community. There has been much work on the Clos network in the literature due to its uses as optical crossconnects (OXCs) in optical networks and high-speed interconnects in parallel/distributed computing systems. However, little attention has been paid to its fault tolerance capability, an indispensable requirement for any practical high-performance networks. In this paper, we analyze the fault tolerance capability of the three-stage rearrangeable Clos network. We first establish a fault model on losing-contact faults in the switches of the network. Then, under this model, we analyze the fault tolerance capability of the Clos network when multiple such faults present in switches in the input stage, middle stage, and/or output stage of the network. Our results show that the rearrangeable condition on the number of middle stage switches for a fault-free rearrangeable Clos network still holds in the presence of a substantial amount of faults, while a more expensive crossbar network cannot tolerate any single such fault. In particular, we obtain that, for an N × N Clos network C(m, n, r), where N = nr and m ≥ n, it can tolerate any m - 1 losing-contact faults arbitrarily located in input/output stage switches, or any m - n losing-contact faults arbitrarily located in middle stage switches, when realizing any permutations. We also demonstrate that, for a given permutation, the network usually can tolerate much such faults. We then present a necessary and sufficient condition on the losing-contact faults a Clos network can tolerate for any given permutation. We also develop an efficient fault-tolerant routing algorithm for a rearrangeable Clos network based on these results.