On Blocking Probabilities for a Class of Linear Graphs

We consider a t -stage linear graph with a source (the vertex of the first stage) and a sink (the vertex of the last stage). All vertices are lined up in a sequence of stages such that any edge goes from a vertex in stage i to a vertex in stage i + 1 for some i, while each edge can be in either of the two states, busy or idle. The linear graph is said to be blocked if every path joining the source and the sink contains a busy edge. Lee1 first proposed the concept of linear graphs in his study of the blocking performance of switching networks. We use Lee's model and follow his independence assumptions, namely, that the probabilities of occupancy for edges being busy in successive stages are independent. Thus, we may assume that any edge connecting a vertex in stage i with a vertex in stage i + 1 has some probability p, of being busy for 1 i t -- 1. The sequence (p i,p2i'"iPt--i) will be called link occupancies of the t -stage linear graph. A linear graph is said to be superior to another if, for any given 2915