End-to-End Blocking for Circuit-Switched Networks: Polynomial Algorithms for Some Special Cases

Recursive algorithms for the computation of the end-to-end blocking in circuit-switched networks operating under very general routing schemes have recently been proposed and implemented, but with exponential upper bounds for their running time. For certain important classes of routings, however, we show that algorithms requiring a single pass in all the route trees are sufficient and, thus, have a polynomial bound. Furthermore, we show that the computation of the appropriate link blocking probabilities is best done by a fixed point method, rather than a Newton-type algorithm. Computational experience is also presented, indicating that these algorithms are fast enough to be considered for the evaluation step of a routing optimization procedure.