On Rearrangeability of Multirate Clos Networks
Guohui Lin, Ding‐Zhu Du, Xiao-Dong Hu, Guoliang Xue · SIAM Journal on Computing · 1999
Chung and Ross [SIAM J. Comput., 20 (1991), pp. 726--736] conjectured that the multirate three-stage Clos network C(n,2n-1,r) is rearrangeable in the general discrete bandwidth case; i.e., each connection has a weight chosen from a given finite set {p 1 , p 2 ,. . .,p k } where $1 \geq p_1 > p_2 > \cdots > p_k > 0$ and p i is an integer multiple of p i , denoted by $p_k \mid p_i$, for $1 \leq i \leq k-1$. In this paper, we prove that multirate three-stage Clos network C(n,2n-1,r) is rearrangeable when each connection has a weight chosen from a given finite set {p 1 , p 2 ,. . .,p k } where $1 \geq p_1 > p_2 > \cdots > p_{h} > 1/2 \geq p_{h+1} > \cdots > p_k > 0$ and p h+2 | p h+1 ,p h+3 |p h+2 ,. . . ,p k | p h+1 . We also prove that C(n,2n-1,r) is two-rate rearrangeable and $C(n, \lceil \frac{7n}{3} \rceil, r)$ is three-rate rearrangeable.