The Linking Probability of Deep Spider-Web Networks
Nicholas J. Pippenger · SIAM Journal on Discrete Mathematics · 2006
We consider crossbar switching networks with base b (that is, constructed from $b\times b$ crossbar switches), scale k (that is, with $b^k$ inputs, $b^k$ outputs, and $b^k$ 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\ge2$ 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\le2$, then the linking probability Q tends to 0 if $0 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.