Optimal QoS control of interacting service stations
RAIRO - Operations Research - Recherche Opérationnelle, Tome 36 (2002) no. 3, pp. 191-208.

We consider a system of three queues and two types of packets. Each packet arriving at this system finds in front of it a controller who either sends it in the first queue or rejects it according to a QoS criterion. When the packet finishes its service in the first queue, it is probabilistically routed to one of two other parallel queues. The objective is to minimize a QoS discounted cost over an infinite horizon. The cost function is composed of a waiting cost per packet in each queue and a rejection cost in the first queue. Subsequently, we generalize this problem by considering a system of (m+1) queues and n types of packets. We show that an optimal policy is monotonic.

DOI : 10.1051/ro:2003002
Mots-clés : queues, flow control, dynamic programming, policies, IP network 
@article{RO_2002__36_3_191_0,
     author = {Haqiq, Abdelkrim and Lambadaris, I. and Mikou, N. and Orozco-Barbosa, L.},
     title = {Optimal {QoS} control of interacting service stations},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {191--208},
     publisher = {EDP-Sciences},
     volume = {36},
     number = {3},
     year = {2002},
     doi = {10.1051/ro:2003002},
     zbl = {1062.90017},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro:2003002/}
}
TY  - JOUR
AU  - Haqiq, Abdelkrim
AU  - Lambadaris, I.
AU  - Mikou, N.
AU  - Orozco-Barbosa, L.
TI  - Optimal QoS control of interacting service stations
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2002
SP  - 191
EP  - 208
VL  - 36
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro:2003002/
DO  - 10.1051/ro:2003002
LA  - en
ID  - RO_2002__36_3_191_0
ER  - 
%0 Journal Article
%A Haqiq, Abdelkrim
%A Lambadaris, I.
%A Mikou, N.
%A Orozco-Barbosa, L.
%T Optimal QoS control of interacting service stations
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2002
%P 191-208
%V 36
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro:2003002/
%R 10.1051/ro:2003002
%G en
%F RO_2002__36_3_191_0
Haqiq, Abdelkrim; Lambadaris, I.; Mikou, N.; Orozco-Barbosa, L. Optimal QoS control of interacting service stations. RAIRO - Operations Research - Recherche Opérationnelle, Tome 36 (2002) no. 3, pp. 191-208. doi : 10.1051/ro:2003002. http://archive.numdam.org/articles/10.1051/ro:2003002/

[1] R. Braden, Requirements for Internet Hosts Communication Layers. STD 3, RFC 1122 (1989).

[2] I. Christidou, I. Lambadaris and R. Mazumdar, Optimal Control of Arrivals to a Feedback Queueing System, in Proc. of the 27th CDC. Austin, Texas (1988) 663-667.

[3] E. Davis, Optimal Control of Arrivals to a Two-server Queueing System with Separate Queues, Ph.D. Dissertation, Program in Operations Research. N.Y. State University, Raleigh (1977).

[4] A. Ephremides, P. Varaiya and J. Walrand, A Simple Dynamic Routing Problem. IEEE Trans. Automat. Control 25 (1980) 690-693. | MR | Zbl

[5] W. Farrell, Optimal Switching Policies in a Nonhomogeneous Exponential Queueing System, Ph.D. Dissertation. Graduate School of Management, University of California, Los Angeles (1976).

[6] S. Floyd and V. Jacobson, Random Early Detection Gateways for Congestion Avoidance. IEEE/ACM Trans. Networking (1993).

[7] H. Ghoneim, Optimal Control of Arrivals to a Network of Two Queues in Series, Ph.D. Dissertation, Program in Operations Research. North Carolina State University, Raleigh (1980).

[8] H. Ghoneim and S. Stidham, Optimal Control of Arrivals to Two Queues in Series. Eur. J. Oper. Res. 21 (1985) 399-409. | MR | Zbl

[9] B. Hajek, Optimal Control of Two Interacting Service Stations. IEEE Trans. Automat. Control 29 (1984) 491-499. | MR | Zbl

[10] A. Haqiq and N. Mikou, Contrôle Dynamique de Flux dans un Système d'Attente avec Panne. RAIRO: Oper. Res. 33 (1999) 69-86. | Numdam | Zbl

[11] A. Haqiq, Admission and routing dynamic control in a queueing system with breakdown, in Troisième Conférence Internationale en Recheche Opérationnelle. Marrakech, Maroc (2002).

[12] V. Jacobson, Congestion Avoidance and Control. ACM SIGCOMM (1988).

[13] P.R. Kumar and P. Varaiya, Stochastic Systems: Estimation, Identification and Adaptive Control. Prentice Hall (1986). | Zbl

[14] I. Lambadaris and P. Narayan, Jointly Optimal Admission and Routing Controls at a Network Node. Commun. Statist. Stochastic Models 10 (1994) 223-252. | MR | Zbl

[15] I. Lambadaris, P. Narayan and I. Viniotis, Optimal Service Allocation among Two Heterogeneous Traffic Types at a Network Node with no Queueing, in Proc. of the 26th CDC. Los Angeles, Vol. CA (1987) 1496-1498.

[16] A. Lazar, Optimal Flow Control of a Class of Queueing Networks in Equilibrium. IEEE Trans. Automat. Control 28 (1983) 1001-1007. | MR | Zbl

[17] S. Lippman, Applying a New Device in the Optimization of Exponential Queueing Systems. Oper. Res. 23 (1975) 687-710. | MR | Zbl

[18] S. Lippman, On Dynamic Programming with Unbounded Rewards. Management Sci. 21 (1975) 1225-1233. | MR | Zbl

[19] J. Nagle, Congestion Control in IP/TCP. RFC 896 (1984).

[20] Z. Rosberg, P. Varaiya and J. Walrand, Optimal Control of Service in Tandem Queues. IEEE Trans. Automat. Control AC-27 (1982) 600-610. | MR | Zbl

[21] W. Stevens, TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms. RFC 2001 (1997).

[22] S. Stidham, Optimal Control of Admission to a Queueing System. IEEE Trans. Automat. Control AC-30 (1985) 705-713. | MR | Zbl

[23] S. Stidham and R. Weber, Control of Service Rates in Cycles and Series of Queues. Stat. Lab., Univ. Cambridge, Cambridge (1983).

[24] P. Varaiya, Note on Optimization. Van Nostrand Reinhold, New York (1972). | Zbl

[25] I. Viniotis and A. Ephremides, Optimal Switching of Voice and Data at a Network Node, in Proc. of the 26th CDC, Vol. CA. Los Angeles (1987) 1504-1507.

[26] J. Walrand, An Introduction to Queueing Networks. Prentice Hall International Editions, Englwood Cliffs, New Jersey (1988). | Zbl

[27] R. Weber, On the Optimal Assignment of Customers to Parallel Servers. J. Appl. Probab. 15 (1978) 406-413. | MR | Zbl

[28] W. Winston, Optimalily of the Shortest-Processing-Time Discipline. J. Appl. Probab. 14 (1977) 181-189. | MR | Zbl

Cité par Sources :