Technical Report 2000-010

Efficient Approximation of Values in Gain scheduled Routing

Jakob Carlström

April 2000

This paper shows how the cost of computation and memory of a previously proposed routing algorithm can be reduced. The routing algorithm, intended for communications networks carrying multiple call classes, is based on gain scheduling of precomputed relative value functions. Each relative value function is computed by solving a reinforcement learning problem, and defines a link admission control policy. We propose a method for automatically selecting points in a grid of per-class arrival intensities, for which relative value functions are computed. After construction of the grid, relative values are computed by interpolation. The numerical studies of routing in a network with two call classes show that less than 30 relative value functions are needed to avoid performance degradation.

Available as compressed Postscript (493 kB, no cover)

Download BibTeX entry.