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 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.

Rights Information

© 2006 Society for Industrial and Applied Mathematics

Download

Share

COinS