A problem on blocking probabilities in connecting networks

✍ Scribed by F. R. K. Chung; F. K. Hwang

• Publisher: John Wiley and Sons
• Year: 1977
• Tongue: English
• Weight: 286 KB
• Volume: 7
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230070205

✦ Synopsis

Abstract

We begin with a three‐stage linear graph in which the first stage has a single node u and the third stage a single node v. The second stage has k independent nodes, each of which is connected by one link to u and to v. In general, we can form a (2n+1)‐stage linear graph recursively by letting each node in the second stage of a three‐stage linear graph be replaced by a copy of a (2n‐1)‐stage linear graph.

A link can either be in the busy state or the idle state. We assume that the states of each link are mutually independent and that any link between stage i and stage i + 1 has the probability I.z of being idle. The nodes u and v are said to be connectable if there exists at least one path from u to v with no busy link. Let P(u, v) denote the probability of such a path existing. Further, let N(2n+1, k) denote the set of (2n+1)‐stage linear graphs whose center stages have k nodes.

In this paper, we determine the size of N(2n+1, k). We also give the linear graph in N(2n+1, k) which has the largest P(u, v) and the one which has the smallest. We then show how our results apply to a recent problem in connecting networks.