On Blocking Probabilities for a Class of Linear Graphs

In a t-stage linear graph, all vertices are arranged in a sequence of stages such that any edge goes between a vertex in stage i and a vertex in stage i + 1 for some i. Lee first proposed the use of t-stage linear graphs for studying the blocking performance of t-stage switching networks. In his model, each edge is in either of two states, busy or idle, and the states of the edges are independent. Furthermore, an edge connecting a vertex in stage i to a vertex in stage i + 1 has the constant probability pi of being busy. In the current paper, we use Lee's model to compare the blocking probabilities of different linear graphs. In particular, a t-stage linear graph is said to be superior to another t-stage linear graph if the blocking probability of the former never exceeds that of the latter for any choice of the pi. For a class of linear graphs known as SP-canopies, we give simple necessary and sufficient conditions that one t-stage linear graph is superior to another.