Nonblocking operation of 3-stage clos networks
Fotios K. Liotopoulos, Suresh Chalasani · 1996
Three-stage Clos networks were first introduced by Charles Clos in 1953. Since then they have been used for multiprocessor interconnection and data switching. Asymmetrical Clos networks may consist of switches and links of varying sizes and capacities. Symmetrical networks may become asymmetrical because of faults, irregular expansions, and heterogeneous resources. This thesis presents a comprehensive study of the nonblocking switching operation of asymmetrical three-stage Clos networks primarily under the multirate environment. The multirate environment can support services with a wide range of bandwidth requirements. The Classic Circuit Switching (CCS) case, which assumes that connections are established over physical or virtual links, is a special case of the multirate environment. We consider four modes of nonblocking operation, and for each mode, we derive conditions on the number of middle-stage switches required for nonblocking operation. The Strictly Nonblocking (SNB) mode is the most general and does not assume any particular control algorithm. For this mode, we derive generalized nonblocking conditions for asymmetrical Clos networks. For the Wide-Sense Nonblocking (WSN) mode we propose two routing algorithms based on bandwidth partitioning and study their optimality. In the Semi-Rearrangeably Nonblocking (SRN) mode we propose control algorithms that perform at most one rearrangement of an existing connection after a disconnection occurs. These algorithms are based on balancing the residual link capacity in the network. For the Rearrangeably Nonblocking (RNB) mode we solve the problem of rearrangeability of Clos networks in the multirate environment. We use a maximum flow network model and matrix decomposition techniques in order to assign connections to middle-stage switches. In order to study the feasibility of our semi-centralized control algorithms, we develop a queuing model and solve it algorithmically using exact mean value analysis techniques. Finally, we present and evaluate multicasting algorithms for Clos networks. The results presented in this thesis can be applied in the development and analysis of switch architectures and control algorithms to support connection-oriented services. Specifically, they can be used for establishing virtual paths in the Asynchronous Transfer Mode (ATM) environment.