A numerical method for controlled routing in large trunk line networks via stochastic control theory

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 scaled available circuits converges to a reflected diffusion process as the network size grows, under reasonable conditions. This limit model contains the basic features of the original network, and provides a very useful basis for a good control strategy for the physical system. 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 ‘three link’ results can be approximated in such a way that they can be applied to a physical network of arbitrary size, using only ‘local’ informaton. Indeed, the numerical approximations have the interpretation of a type of simplified or ‘aggregated’ network, which allows the use of physical intuition in its application. The resulting policies are compared in simulations (on systems with hundreds of links) to other current approaches, and found to be quite competitive and have many advantages.