On the optimal and distributed control of stochastic network systems.

摘要

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.;When it exists, the continuously differentiable value function is a solution to the associated hybrid HJB equations. In general, the smoothness of the value functions and uniqueness of the solutions to the hybrid HJB equations may not hold. In this thesis, viscosity solutions to a general class of hybrid HJB equations are developed and under mild conditions it is shown that the value function is continuous and, further, any continuous value function is the unique viscosity solution to the hybrid HJB equations.;The computational intractability of the dynamic programming (DP) equations associated with optimal admission and routing in stochastic loss networks of any non-trivial size (Ma et al., 2006, 2008) leads one to consider suboptimal distributed game theoretic formulations of the problem.;The special class of radial networks with a central core of infinite capacity is considered, and it is shown (under adequate assumptions) that an associated distributed admission control problem becomes tractable asymptotically, as the size of radial network grows to infinity. This is achieved by following a methodology first explored by M. Huang et al. (2003, 2006-2008) in the context of large scale dynamic games for sets of weakly coupled linear stochastic control systems. At the established Nash equilibrium, each agent reacts optimally with respect to the average trajectory of the mass of all other agents; this trajectory is approximated by a deterministic infinite population limit (associated with the mean field or ensemble statistics of the random agents) which is the solution of a particular fixed point problem. This framework has connections with the mean field models studied by Lasry and Lions (2006, 2007) and close connections with the notion of oblivious equilibrium proposed by Weintraub, Benkard, and Van Roy (2005, 2008) via a mean field approximation.;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)).