Control of admission and routing in loss networks: Hybrid dynamic programming equations

Call admission and routing control decisions in stochastic loss (circuit-switched) networks with semi Markovian, multi-class, call arrival and general connection time processes are formulated as optimal stochastic control problems. The resulting so-called Hybrid Dynamic Programming equation systems take the form of vectors of partial differential equations with each component associated to a distinct distribution of routed calls over the network (i.e. distinct occupation states). This framework reduces to that of a Markov Decision Process when the traffic is Poisson and the associated computational limitations are approximately those of linear programs. Examples are provided of (i) network state space constructions and controlled state transition processes, (ii) a new closed form solution for a simple network, and (iii) the analysis and illustrative numerical results for a three link network. While the optimal control approach is in general computationally intractable, the current results permit estimates of computational requirements as well as the automatic formulation, or specification, of a range of suboptimal control problems obtained by adequately restricting admissible network routes. Furthermore the results presented constitute an essential foundation for a proposed game theoretic strategy of local optimization and global co-ordination for large loss networks (the Point Process Nash Certainty Equivalence (or Mean Field) Principle, (Ma et al. 2007-2009).)