Bounds on the performance of dynamic schemes for highly connected networks

The paper describes a procedure for bounding the performance of dynamic routing schemes for loss of 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 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.