Document Type

Article

Department

Mathematics (HMC)

Publication Date

2006

Abstract

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 < q < q_c$ (where $q_c=1/b^{(c-1)/c}$ is the critical vacancy probability) and tends to $(1-\xi)^2$ (where $\xi$ is the unique solution of the equation $\bigl(1-q(1-x)\bigr)^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