Abstract
Motivated by a certain situation in communication networks, we will investigate the M/M/1/∞ queuing system, where one can change the input stream. Performance criteria coincide with the long-run average throughput of the system and the queue length. We will present a rigorous mathematical study of the constrained version of the multicriteria optimization problem for jump Markov processes. Subsequently, it will be shown that the stationary control strategies of the threshold type form a sufficient class in the initial bicriteria problem considered.
Similar content being viewed by others
References
E. Altman, Constrained Markov Decision Processes(Chapman and Hall/CRC Press, London, 1999).
E. Altman, G. Koole and T. Jimenez, On optimal call admission control in a resource-sharing system, IEEE Trans. Commun. 49 (2001) 1659-1668.
E. Altman and A. Shwartz, Markov decision problems and state-action frequences, SIAM J. Control Optim. 29 (1991) 786-809.
P.S. Ansell, K.D. Glazebrook, I. Mitrani and J. Nino-Mora, A semidefinite programming approach to the optimal control of a single server queueing system with imposed second moment constraints, J. Oper. Res. Soc. 50 (1999) 765-773.
V. Borkar, Topics in Controlled Markov Chains(Longman Scientific and Technical, Harlow, Essex, England, 1991).
E.A. Feinberg, Constrained semi-Markov decision processes with average rewards, Z. Oper. Res. 39 (1994) 257-288.
E.A. Feinberg, Optimal control of average reward constrained continuous-time finite Markov decision processes, in: Proc. of IEEE Conf. on Decision and Control, Vol. 4 (2002) pp. 3805-3810.
S. Floyd, TCP and explicit congestion notification, ACM Comput. Commun. Rev. 24 (1994) 10-23.
X. Guo and O. Hernandez-Lerma, Constrained continuous-time Markov control processes with discounted criteria, Stochastic. Anal. Appl. 21 (2003) 379-400.
X. Guo and O. Hernandez-Lerma, Drift and monotonicity conditions for continuous-time controlled Markov chains with an average criterion, IEEE Trans. Automat. Control 48 (2003) 236-245.
N. Hemachandra and Y. Narahari, A mathematical programming approach to optimal Markovian switching of Poisson arrival streams to queueing systems, Queueing Systems 36 (2001) 443-461.
O. Hernandez-Lerma and R. Romera, Pareto optimality in multiobjective Markov control processes, Preprint (2001).
C.V. Hollot, V. Misra, D. Towsley and W. Gong, A control theoretic analysis of RED, in: Proc. of IEEE Conf. INFOCOM(2001) pp. 1510-1519.
A. Hordijk and F. Spieksma, Constrained admission control to a queueing system, Adv. in Appl. Probab. 21 (1989) 409-431.
M. Kitaev, Semi-Markov and jump Markov controllable models. Average cost criterion, Teor. Veroyatnost. i Primenen. 30 (1985) 252-268 (in Russian).
M.Y. Kitaev and V.V. Rykov, Controlled Queueing Systems(CRC Press, New York, 1995).
M.E. Lewis, Average optimal policies in a controlled queueing system with dual admission control, J. Appl. Probab. 38 (2001) 369-385.
R.Sh. Liptzer and A.N. Shiryaev, Theory of Martingales(Kluwer, Dordrecht, 1989).
M. Mandjes, D. Mitra and W. Scheinhardt, Models of network access using feedback fluid queues, Queueing Systems (in press).
V. Misra, W.B. Gong and D. Towsley, A fluid-based analysis of a network of AQM routers supporting TCP flows with an application to RED, in: Proc. of ACM Conf. SIGCOMM’2000.
A.B. Piunovskiy, Homogeneous controllable Markov models with continuous time, Cybernetics 25 (1989) 55-61.
A.B. Piunovskiy, Optimal Control of Random Sequences in Problems with Constraints(Kluwer Academic, Dordrecht, 1997).
A.B. Piunovskiy, A controlled jump discounted model with constraints, Theory Probab. Appl. 42 (1998) 51-72.
A.B. Piunovskiy and V.M. Khametov, New effective solutions of optimality’s equation for the controlled Markov chains with continuous parameter (the unbounded price-function), Probl. Control Inform. Theory 14 (1985) 303-318.
M.L. Puterman, Markov Decision Processes(Wiley, New York, 1994).
M.I. Reiman and A. Shwartz, Call admission: A new approach to quality of service, Queueing Systems 38 (2001) 125-148.
R.T. Rockafellar, Conjugate Duality and Optimization(SIAM, Philadelphia, PA, 1989).
V.V. Rykov, Monotone control of queueing systems with heterogeneous servers, Queueing Systems 37 (2001) 391-403.
S. Sanghavi, K. Avrachenkov and E. Altman, Optimal policies for admitting calls with silence suppression, Preprint (2002).
L. Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems(Wiley, New York, 1999).
H.M. Taylor and S. Karlin, An Introduction to Stochastic Modeling(Academic Press, San Diego, CA, 1998).
A.A. Yushkevich and E.A. Feinberg, On homogeneous Markov models with continuous time and finite or countable state space, Teor. Veroyatnost. i Primenen. 24 (1979) 155-160 (in Russian).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Piunovskiy, A. Bicriteria Optimization of a Queue with a Controlled Input Stream. Queueing Systems 48, 159–184 (2004). https://doi.org/10.1023/B:QUES.0000039892.03630.24
Issue Date:
DOI: https://doi.org/10.1023/B:QUES.0000039892.03630.24