Sequencial Routing Optimization for Circuit Switched Networks

Nonhierarchical alternate routing is the simplest extension to the hierarchical routing currently used in telephone networks. In order to evaluate the merits of such a technique, it is necessary to be able to optimize some performance measure over the routing variables. In a first step, a short discussion is presented of the evaluation algorithms used for computing the end-to-end blocking probabilities in networks operating under nonhierarchicai alternate routings. Then the results of a statistical sampling of the routing space for a small network are presented, to illustrate important characteristics of the routing problem. Next, two heuristic optimization techniques are discussed, one based on classical steepest descent and the other inspired from classical routing optimization of traffic flows in transportation and communication networks. Acceleration techniques are discussed in both cases, and the convergences rates of the alorgithms are presented for a number of networks. A brief discussion is finally given of the usefulness of nonhierarchical alternate routing in reducing the blocking probability in already existing networks, and in decreasing the number of trunks required to maintain a prespecified grade of service, both in real and artificially generated networks.