On serial and parallel implementations of the Erlang fixed-point iteration scheme

摘要

The blocking probability of a route in a loss network is the probability that a call arriving at that route is rejected due to there being insufficient resources available on it. The blocking probabilities, also known as loss probabilities, are often used as a measure of network performance. Closed-form expressions for these are easy to write down, however they cannot be evaluated in polynomial time, even for small networks. Consequently, there has always been an enormous interest in developing efficient methods for approximating them. Arguably, the most important of these is the Erlang fixed-point approximation (EFPA), which teletraffic engineers were using long before rigorous results justifying its use in various circumstances were proved. This article demonstrates that care must be exercised when using the standard Jacobi iteration scheme employed in serial implementations of the EFPA, as it may not converge. A number of modifications to the EFPA, which appear to be more stable and able to avoid pathologies such as limit cycles, are presented. Of particular interest is the Jacobi iteration scheme modified so that each new update is a weighted average of the new and old iterates. We show that convergence of this method is always guaranteed by an appropriate choice of the weighting constant. Finally, a comparison between the serial implementation and a number of parallel implementations of the EFPA is presented.