The Linking Probability of Deep Spider-Web Networks

DOI10.1137/050624376MaRDI QIDQ5470823zbMATH OpenOpenAlexFDO

Authors Nicholas Pippenger

Publication date 1 June 2006

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0502294

zbMATH Keywords

blocking probabilitycommunication networkscrossbar switching networks

Mathematics Subject Classification ID

Applications of graph theory (05C90) Combinatorial probability (60C05) Applications of graph theory to circuits and networks (94C15)

Abstract: We consider crossbar switching networks with base $b$ (that is, constructed from $bimesb$ 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 $bge2$ 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 it was shown that if $cle2$, 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 $(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.

Recommendations

• The asymptotic optimality of spider-web networks
• Loss probabilities in a simple circuit-switched network
• The blocking probability of spider-web networks
• Blocking probabilities in large circuit-switched networks
• scientific article; zbMATH DE number 1334210

Cited in

(3)

• The asymptotic optimality of spider-web networks
• The blocking probability of spider-web networks
• Spider evaluation and representations of web groups

This page was built for publication: The Linking Probability of Deep Spider-Web Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5470823)