Algorithms to Determine Exact Blocking Probabilities for Multirate Tree Networks

We consider a circuit-switched network consisting of multiple-access links connected to a common link. Each call requires circuits on one access link and on the common link. The network supports multiple classes of calls where each class specifies a bandwidth requirement, an arrival rate, and a holding-time distribution. Based on a product-form solution for these networks, four algorithms are developed to determine the exact blocking probability for each of the classes. The first two algorithms are based on convolution, the third on the fast Fourier transform, and the fourth on a recursion due to Kaufman [8] and to Roberts [16]. Complexity bounds and numerical results demonstrate that these algorithms can determine blocking probabilities in reasonable CPU time for networks with thousands of circuits.