Optimal QoS control of interacting service stations

Abdelkrim Haqiq; I. Lambadaris; N. Mikou; L. Orozco-Barbosa

RAIRO - Operations Research - Recherche Opérationnelle (2002)

  • Volume: 36, Issue: 3, page 191-208
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Haqiq, Abdelkrim, et al. "Optimal QoS control of interacting service stations." RAIRO - Operations Research - Recherche Opérationnelle 36.3 (2002): 191-208. <http://eudml.org/doc/245294>.

@article{Haqiq2002,
abstract = {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.},
author = {Haqiq, Abdelkrim, Lambadaris, I., Mikou, N., Orozco-Barbosa, L.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {queues; flow control; dynamic programming; policies; IP network},
language = {eng},
number = {3},
pages = {191-208},
publisher = {EDP-Sciences},
title = {Optimal QoS control of interacting service stations},
url = {http://eudml.org/doc/245294},
volume = {36},
year = {2002},
}

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
PB - EDP-Sciences
VL - 36
IS - 3
SP - 191
EP - 208
AB - 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.
LA - eng
KW - queues; flow control; dynamic programming; policies; IP network
UR - http://eudml.org/doc/245294
ER -

References

top
  1. [1] R. Braden, Requirements for Internet Hosts Communication Layers. STD 3, RFC 1122 (1989). 
  2. [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. [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. [4] A. Ephremides, P. Varaiya and J. Walrand, A Simple Dynamic Routing Problem. IEEE Trans. Automat. Control 25 (1980) 690-693. Zbl0451.90060MR583444
  5. [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. [6] S. Floyd and V. Jacobson, Random Early Detection Gateways for Congestion Avoidance. IEEE/ACM Trans. Networking (1993). 
  7. [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. [8] H. Ghoneim and S. Stidham, Optimal Control of Arrivals to Two Queues in Series. Eur. J. Oper. Res. 21 (1985) 399-409. Zbl0569.60091MR811095
  9. [9] B. Hajek, Optimal Control of Two Interacting Service Stations. IEEE Trans. Automat. Control 29 (1984) 491-499. Zbl0555.90047MR745188
  10. [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. Zbl1024.90022
  11. [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. [12] V. Jacobson, Congestion Avoidance and Control. ACM SIGCOMM (1988). 
  13. [13] P.R. Kumar and P. Varaiya, Stochastic Systems: Estimation, Identification and Adaptive Control. Prentice Hall (1986). Zbl0706.93057
  14. [14] I. Lambadaris and P. Narayan, Jointly Optimal Admission and Routing Controls at a Network Node. Commun. Statist. Stochastic Models 10 (1994) 223-252. Zbl0791.60080MR1259860
  15. [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. [16] A. Lazar, Optimal Flow Control of a Class of Queueing Networks in Equilibrium. IEEE Trans. Automat. Control 28 (1983) 1001-1007. Zbl0526.90041MR722351
  17. [17] S. Lippman, Applying a New Device in the Optimization of Exponential Queueing Systems. Oper. Res. 23 (1975) 687-710. Zbl0312.60048MR443125
  18. [18] S. Lippman, On Dynamic Programming with Unbounded Rewards. Management Sci. 21 (1975) 1225-1233. Zbl0309.90017MR398535
  19. [19] J. Nagle, Congestion Control in IP/TCP. RFC 896 (1984). 
  20. [20] Z. Rosberg, P. Varaiya and J. Walrand, Optimal Control of Service in Tandem Queues. IEEE Trans. Automat. Control AC-27 (1982) 600-610. Zbl0497.90024MR680318
  21. [21] W. Stevens, TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms. RFC 2001 (1997). 
  22. [22] S. Stidham, Optimal Control of Admission to a Queueing System. IEEE Trans. Automat. Control AC-30 (1985) 705-713. Zbl0563.90044MR794203
  23. [23] S. Stidham and R. Weber, Control of Service Rates in Cycles and Series of Queues. Stat. Lab., Univ. Cambridge, Cambridge (1983). 
  24. [24] P. Varaiya, Note on Optimization. Van Nostrand Reinhold, New York (1972). Zbl0251.90034
  25. [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. [26] J. Walrand, An Introduction to Queueing Networks. Prentice Hall International Editions, Englwood Cliffs, New Jersey (1988). Zbl0854.60090
  27. [27] R. Weber, On the Optimal Assignment of Customers to Parallel Servers. J. Appl. Probab. 15 (1978) 406-413. Zbl0378.60095MR518586
  28. [28] W. Winston, Optimalily of the Shortest-Processing-Time Discipline. J. Appl. Probab. 14 (1977) 181-189. Zbl0357.60023MR428516

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.