Semi-Centralized Routing Algorithms for 3-Stage Clos Networks
Fotios K. Liotopoulos, S. Chalasani · 1995
In this paper we study the switching performance of three-stage Clos networks. First, we consider an existing control algorithm for operating the asymmetrical Clos networks in the nonblocking mode, and we derive sufficient conditions under which these networks are nonblocking for this control algorithm. We next design a new routing algorithm for nonblocking operation of asymmetrical Clos networks. Using simulation results, the new control algorithm is shown to perform better than the previous one in terms of network utilization, blocking probability and fault-tolerance. In order to further study the performance of the new semi-centralized routing algorithm, we introduce a queuing model and solve it using an exact mean value analysis algorithm. Simulation results are used to verify the predictions of our analysis regarding the router’s throughput, latency, and the network’s capacity utilization. Since semi-centralized routers are performance-limited by their centralized bottlenecks, we introduce a routing scheme, which consists of multiple interdependent routers which operate in parallel. Simulation results indicate that this routing scheme substantially improves the performance of the single router, thus alleviating the congestion effects due to the centralized bottlenecks.