Explicit solution for a network control problem in the large deviation regime. (English) Zbl 1044.60018

Atar, Rami; Shwartz, Adam; Dupuis, Paul

Queueing Syst. 46, No. 1-2, 159-176 (2004).

Summary: We consider optimal control of a stochastic network, where service is controlled to prevent buffer overflow. We use a risk-sensitive escape time criterion, which in comparison to the ordinary escape time criteria heavily penalizes exits which occur on short time intervals. A limit as the buffer sizes tend to infinity is considered. We showed [Math. Oper. Res. 28, No. 4, 801–835 (2003)] that, for a large class of networks, the limit of the normalized cost agrees with the value function of a differential game. In this game, one player controls the service discipline (who to serve and whether to serve), and the other player chooses arrival and service rates in the network. The game’s value is characterized in the paper quoted above as the unique solution to a Hamilton-Jacobi-Bellman partial differential equation (PDE).
In the current paper we apply this general theory to the important case of a network of queues in tandem. Our main results are: (i) the construction of an explicit solution to the corresponding PDE, and (ii) drawing out the implications for optimal risk-sensitive and robust regulation of the network. In particular, the following general principle can be extracted. To avoid buffer overflow there is a natural competition between two tendencies. One may choose to serve a particular queue, since that will help prevent its own buffer from overflowing, or one may prefer to stop service, with the goal of preventing overflow of buffers further down the line. The solution to the PDE indicates the optimal choice between these two, specifying the parts of the state space where each queue must be served (so as not to lose optimality), and where it can idle. Referring to those queues which must be served as bottlenecks, one can use the solution to the PDE to explicitly calculate the bottleneck queues as a function of the system’s state, in terms of a simple set of equations.

MSC:

60F10	Large deviations
60K25	Queueing theory (aspects of probability theory)
49N70	Differential games and control
93E20	Optimal stochastic control

Keywords:

large deviations; stochastic risk-sensitive control; differential game; HJB equation; tandem queue