Network programming methods for loss networks

In IEEE Journal on Selected Areas in Communications, 13(1995), 1189-1198.

Abstract

This paper descibes how some of the insights available from the stochastic analysis of dynamic routing may be incorporated into the classical mathematical programming approach to the design of networks. In particular, we present the results of a number of numerical investigations into network architectures for circuit-switched communication networks. Our investigations use recent theoretical results integrating network flow optimization and Markov decision processes to provide performance bounds for dynamic routing strategies. Following a tutorial introduction of the above mentioned topics we develop a sequence of network examples. Our first examples are familiar ones, such as symmetric fully connected networks and networks with moderate amounts of asymmetry, and we descibe how network programming methods complement earlier work on dynamic routing. We then consider a variety of example networks which have a more sparse collection of links. These examples indicate the potential applicability of the methods to a variety of areas, including the design, performance and resilience of future communication networks.