Wide-sense nonblocking Clos networks under packing strategy

In this paper, we study wide-sense nonblocking conditions under packing strategy for the three-stage Clos network, or v(m, n, r) network. Wide-sense nonblocking networks are generally believed to have lower network cost than strictly nonblocking networks. However, the analysis for the wide-sense nonblocking conditions is usually more difficult. Moore proved that a v(m, n, 2) network is nonblocking under packing strategy if the number of middle stage switches. This result has been widely cited in the literature, and is even considered as the wide-sense nonblocking condition under packing strategy for the general v(m,n,r) networks in some papers, such as [7]. In fact, it is still not known that whether the condition holds for v(m, n, r) networks In this paper, we introduce a systematic approach to the analysis of wide-sense nonblocking conditions for general v(m,n, r) networks with any r value. We first translate the problem of finding the nonblocking condition under packing strategy for a v(m, n, r) network to a set of linear programming problems. We then solve this special type of linear programming problems and obtain a closed form optimum solution. We prove that the necessary condition for a v(m, n, r) network to be nonblocking under packing strategy is m≥[(2-1/F _2r-1)n], where F _2r-1 is the Fibonacci number. In the case of n≤F _2r-1, this condition is also a sufficient nonblocking condition for packing strategy. We believe that the systematic approach developed in this paper can be used for analyzing other wide-sense nonblocking control strategies as well.