Bounds on the Performance of Dynamic Routing Schemes for Highly Connected Networks

We describe a procedure for bounding the performance of dynamic routing schemes for loss or queueing networks. The bound is developed from a network flow synthesis of a collection of Markov decision processes, one for each resource of the network. The bound emerges as a solution to a dual pair of convex programming problems, where the primal problem describes mean flows through the network and the dual problem describes implied costs and surplus values at resources of the network. The bound is particularly appropriate for large highly connected networks, where it may be approached by simple trunk reservation or threshold routing schemes.