#### Document Type

Article

#### Department

Mathematics (HMC)

#### Publication Date

2006

#### Abstract

We consider crossbar switching networks with base *b* (that is, constructed from *b* x *b* crossbar switches), scale *k* (that is, with *b ^{k}* inputs,

*b*outputs, and

^{k}*b*links between each consecutive pair of stages), and depth

^{k}*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* < *q _{c}* (where

*q*= 1/

_{c}*b*

^{(c-}^{1}

*is the critical vacancy probability) and tends to (1-ξ)*

^{)/c}^{2}(where ξ is the unique solution of the equation (1-

*q*(1-

*x*))

^{b}=

*x*in the range 0 <

*x*< 1) if

*q*<

_{c}*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.

#### Rights Information

© 2006 Society for Industrial and Applied Mathematics

#### Recommended Citation

Pippenger, Nicholas. “The Linking Probability of Deep Spider-Web Networks.” SIAM Journal on Discrete Mathematics 20, no. 1 (January 2006): 143-159.