Premium
The blocking probability of spider‐web networks
Author(s) -
Pippenger Nicholas
Publication year - 1991
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240020202
Subject(s) - blocking (statistics) , probabilistic logic , limiting , computer science , disjoint sets , occupancy , spider , class (philosophy) , computer network , mathematics , discrete mathematics , artificial intelligence , physics , engineering , mechanical engineering , architectural engineering , astronomy
Abstract We determine the limiting behavior of the blocking probability for spider‐web networks, a class of crossbar switching networks proposed by Ikeno. We use a probabilistic model proposed by the author, in which the busy links always form disjoint routes through the network. We show that if the occupancy probability is below the threshold 2 ‐ √2 = 0.5857…, then the blocking probability tends to zero, whereas above this threshold it tends to one. This provides a theoretical explanation for results observed empirically in simulations by Bassalygo, Neiman, and Vvedenskaya.