We consider crossbar switching networks with base b (that is, constructed from b x b crossbar switches), scale k (that is, with bk inputs, bk outputs, and bk links between each consecutive pair of stages), and depth l (that is, with l stages). We assume that the crossbars are interconnected according to the spider-web pattern, whereby two diverging paths reconverge only after at least k stages. We assume that each vertex is independently idle with probability q, the vacancy probability. We assume that b ≥ 2 and the vacancy probability q are fixed, and that k and l = ck tend to infinity with ratio a fixed constant c > 1.
We consider the linking probability Q (the probability that there exists at least one idle path between a given idle input and a given idle output). In a previous paper [Discrete Appl. Math., 37/38 (1992), pp. 437-450] it was shown that if c ≤ 2, then the linking probability Q tends to 0 if 0 < q < qc (where qc = 1/b(c-1)/c is the critical vacancy probability) and tends to (1-ξ)2 (where ξ is the unique solution of the equation (1-q(1-x))b = x in the range 0 < x < 1) if qc < q < 1. In this paper we extend this result to all rational c > 1. This is done by using generating functions and complex-variable techniques to estimate the second moments of various random variables involved in the analysis of the networks.
© 2006 Society for Industrial and Applied Mathematics
Pippenger, Nicholas. “The Linking Probability of Deep Spider-Web Networks.” SIAM Journal on Discrete Mathematics 20, no. 1 (January 2006): 143-159.