A fast numerical algorithm for multi-rate network synthesis

We consider here the problem of the optimal network design either for multi -rate circuit switching or VC switching in an ATM network through the use o f effective bandwidth models. We put the emphasis on the development of a f ast and stable numerical algorithm for computing solutions of networks of u p to 50 nodes. We show that the main difficulty is in the calculation of th e gradient of the objective function in the presence of the Erlang fixed po int system. We then propose an approximation for this calculation based on the power series of the inverse of a matrix. Next, we review explicit repre sentation techniques for the matrices involved in this calculation and show that reductions in CPU time of factors as large as 20 can be obtained with practically no penalty in terms of memory requirement. We also show that t he dimensioning problem is ill-conditioned and that a simple scaling of the dimensioning variables is sufficient to speed up the convergence. As a fin al point, we use the algorithm to examine some features of the problem. We show that the objective function has no definite convexity property, that a lternate routing is used mostly by wideband calls and that the grade of ser vice constraints are generally binding only for these wideband calls.