An effective numerical method for controlled routing in large trunk line networks

The paper discusses a powerful approach to the routing problem in large networks of the trunk line type. The approximations are based on heavy traffic limit theorems. The sequence of suitably normalized available circuits converges to a reflected diffusion process as the size of the network grows, under reasonable conditions. This limit model contains the basic features of the original network. The optimal ergodic cost problem for a three (link) dimensional system is solved numerically via the Markov chain approximation method to get the optimal controls. These can be approximated in such a way that they can be applied to a network of arbitrary size, using only “local” information. The resulting policies are compared in simulations (on systems with hundreds of links) to other current approaches, and found to be quite competitive with other schemes of current interest and have many advantages.