[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Performance Analysis of Priority Queueing Systems in Discrete Time

  • Chapter
Network Performance Engineering

Part of the book series: Lecture Notes in Computer Science ((LNCCN,volume 5233))

Abstract

The integration of different types of traffic in packet-based networks spawns the need for traffic differentiation. In this tutorial paper, we present some analytical techniques to tackle discrete-time queueing systems with priority scheduling. We investigate both preemptive (resume and repeat) and non-preemptive priority scheduling disciplines. Two classes of traffic are considered, high-priority and low-priority traffic, which both generate variable-length packets. A probability generating functions approach leads to performance measures such as moments of system contents and packet delays of both classes.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 93.50
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Miller, R.: Priority queues. Annals of Mathematical Statistics 31, 86–103 (1960)

    Article  MathSciNet  MATH  Google Scholar 

  2. Kleinrock, L.: Queueing systems. Computer applications, vol. II. John Wiley & Sons, New York (1976)

    MATH  Google Scholar 

  3. Takagi, H.: Queueing analysis: a foundation of performance evaluation, vacation and priority systems, part 1, vol. 1. North-Holland, Amsterdam (1991)

    MATH  Google Scholar 

  4. Khamisy, A., Sidi, M.: Discrete-time priority queues with two-state Markov Modulated arrivals. Stochastic Models 8(2), 337–357 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  5. Takine, T., Sengupta, B., Hasegawa, T.: An analysis of a discrete-time queue for broadband ISDN with priorities among traffic classes. IEEE Transactions on Communications 42(2-4), 1837–1845 (1994)

    Article  Google Scholar 

  6. Laevens, K., Bruneel, H.: Discrete-time multiserver queues with priorities. Performance Evaluation 33(4), 249–275 (1998)

    Article  Google Scholar 

  7. Choi, B., Choi, D., Lee, Y., Sung, D.: Priority queueing system with fixed-length packet-train arrivals. IEE Proceedings-Communications 145(5), 331–336 (1998)

    Article  Google Scholar 

  8. Walraevens, J., Steyaert, B., Bruneel, H.: Performance analysis of a single-server ATM queue with a priority scheduling. Computers & Operations Research 30(12), 1807–1829 (2003)

    Article  MATH  Google Scholar 

  9. Mehmet Ali, M., Song, X.: A performance analysis of a discrete-time priority queueing system with correlated arrivals. Performance Evaluation 57(3), 307–339 (2004)

    Article  Google Scholar 

  10. Van Velthoven, J., Van Houdt, B., Blondia, C.: The impact of buffer finiteness on the loss rate in a priority queueing system. In: Horváth, A., Telek, M. (eds.) EPEW 2006. LNCS, vol. 4054, pp. 211–225. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  11. Kamoun, F.: Performance analysis of a discrete-time queuing system with a correlated train arrival process. Performance Evaluation 63(4-5), 315–340 (2006)

    Article  Google Scholar 

  12. Walraevens, J., Wittevrongel, S., Bruneel, H.: A discrete-time priority queue with train arrivals. Stochastic Models 23(3), 489–512 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  13. Demoor, T., Walraevens, J., Fiems, D., Bruneel, H.: Mixed finite-/infinite-capacity priority queue with interclass correlation. In: Al-Begain, K., Heindl, A., Telek, M. (eds.) ASMTA 2008. LNCS, vol. 5055, pp. 61–74. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  14. Walraevens, J., Fiems, D., Bruneel, H.: Time-dependent performance analysis of a discrete-time priority queue. Performance Evaluation 65(9), 641–652 (2008)

    Article  Google Scholar 

  15. Walraevens, J., Wittevrongel, S., Bruneel, H.: Performance analysis of a priority queue with session-based arrivals and its application to E-commerce web servers. International Journal On Advances in Internet Technology 2(1), 46–57 (2009)

    Google Scholar 

  16. Walraevens, J., Fiems, D., Wittevrongel, S., Bruneel, H.: Calculation of output characteristics of a priority queue through a busy period analysis. European Journal of Operational Research 198(3), 891–898 (2009)

    Article  MATH  Google Scholar 

  17. Stanford, D.: Interdeparture-time distributions in the non-preemptive priority ΣMi/Gi/1 queue. Performance Evaluation 12(1), 43–60 (1991)

    Article  MathSciNet  Google Scholar 

  18. Sugahara, A., Takine, T., Takahashi, Y., Hasegawa, T.: Analysis of a nonpreemptive priority queue with SPP arrivals of high class. Performance Evaluation 21(3), 215–238 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  19. Abate, J., Whitt, W.: Asymptotics for M/G/1 low-priority waiting-time tail probabilities. Queueing Systems 25(1-4), 173–233 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  20. Takine, T.: The nonpreemptive priority MAP/G/1 queue. Operations Research 47(6), 917–927 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  21. Isotupa, K., Stanford, D.: An infinite-phase quasi-birth-and-death model for the non-preemptive priority M/PH/1 queue. Stochastic Models 18(3), 387–424 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  22. Drekic, S., Stafford, J.: Symbolic computation of moments in priority queues. INFORMS Journal on Computing 14(3), 261–277 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  23. Bouallouche-Medjkoune, L., Aissani, D.: Quantitative estimates in an M 2/G 2/1 priority queue with non-preemptive priority: the method of strong stability. Stochastic Models 24, 626–646 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  24. Iftikhar, M., Singh, T., Landfeldt, B., Caglar, M.: Multiclass G/M/1 queuing system with self-similar input and non-preemptive priority. Computer Communications 31, 1012–1027 (2008)

    Article  Google Scholar 

  25. Al-Begain, K., Dudin, A., Kazimirsky, A., Yerima, S.: Investigation of the M 2/G 2/1/ ∞ ,N queue with restricted admission of priority customers and its application to HSDPA mobile systems. Computer Networks 53, 1186–1201 (2009)

    Article  MATH  Google Scholar 

  26. Chen, Y., Chen, C.: Performance analysis of non-preemptive GE/G/1 priority queueing of LER system with bulk arrivals. Computers and Electrical Engineering 35, 764–789 (2009)

    Article  MATH  Google Scholar 

  27. Rubin, I., Tsai, Z.: Message delay analysis of multiclass priority TDMA, FDMA, and discrete-time queueing systems. IEEE Transactions on Information Theory 35(3), 637–647 (1989)

    Article  MathSciNet  Google Scholar 

  28. Hashida, O., Takahashi, Y.: A discrete-time priority queue with switched batch Bernoulli process inputs and constant service time. In: Proceedings of ITC 13, Copenhagen, pp. 521–526 (1991)

    Google Scholar 

  29. Takine, T., Matsumoto, Y., Suda, T., Hasegawa, T.: Mean waiting times in nonpreemptive priority queues with Markovian arrival and i.i.d. service processes. Performance Evaluation 20, 131–149 (1994)

    Article  Google Scholar 

  30. Takine, T.: A nonpreemptive priority MAP/G/1 queue with two classes of customers. Journal of Operations Research Society of Japan 39(2), 266–290 (1996)

    MathSciNet  MATH  Google Scholar 

  31. Walraevens, J., Steyaert, B., Bruneel, H.: Performance analysis of the system contents in a discrete-time non-preemptive priority queue with general service times. Belgian Journal of Operations Research, Statistics and Computer Science (JORBEL) 40(1-2), 91–103 (2000)

    MathSciNet  MATH  Google Scholar 

  32. Walraevens, J., Steyaert, B., Bruneel, H.: Delay characteristics in discrete-time GI-G-1 queues with non-preemptive priority queueing discipline. Performance Evaluation 50(1), 53–75 (2002)

    Article  Google Scholar 

  33. Walraevens, J., Steyaert, B., Moeneclaey, M., Bruneel, H.: Delay analysis of a HOL priority queue. Telecommunication Systems 30(1-3), 81–98 (2005)

    Article  Google Scholar 

  34. Maertens, T., Walraevens, J., Bruneel, H.: Priority queueing systems: from probability generating functions to tail probabilities. Queueing Systems 55(1), 27–39 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  35. Demoor, T., Walraevens, J., Fiems, D., De Vuyst, S., Bruneel, H.: Analysis of a non-preemptive priority queue with finite high-priority capacity and general service times. In: Proceedings of the 4th International Conference on Queueing Theory and Applications (QTNA 2009), Singapore, ID12 (2009)

    Google Scholar 

  36. Miller, D.: Computation of steady-state probabilities for M/M/1 priority queues. Operations Research 29(5), 945–958 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  37. Sandhu, D., Posner, M.: A priority M/G/1 queue with application to voice/data communication. European Journal of Operational Research 40(1), 99–108 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  38. Takine, T., Hasegawa, T.: The workload in the MAP/G/1 queue with state-dependent services: its application to a queue with preemptive resume priority. Communications in Statistics - Stochastic Models 10(1), 183–204 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  39. Takahashi, Y., Miyazawa, M.: Relationship between queue-length and waiting time distributions in a priority queue with batch arrivals. Journal of the Operations Research Society of Japan 37(1), 48–63 (1994)

    MathSciNet  MATH  Google Scholar 

  40. Boxma, O., Cohen, J., Deng, Q.: Heavy-traffic analysis of the M/G/1 queue with priority classes. In: Proceedings of ITC 16, Edinburgh, pp. 1157–1167 (1999)

    Google Scholar 

  41. Sharma, V., Virtamo, J.: A finite buffer queue with priorities. Performance Evaluation 47(1), 1–22 (2002)

    Article  MATH  Google Scholar 

  42. Takada, H., Miyazawa, M.: A Markov Modulated fluid queue with batch arrivals and preemptions. Stochastic Models 18(4), 529–652 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  43. Liu, Y., Gong, W.: On fluid queueing systems with strict priority. IEEE Transactions on Automatic Control 48(12), 2079–2088 (2003)

    Article  MathSciNet  Google Scholar 

  44. Jin, X., Min, G.: Performance analysis of priority scheduling mechanisms under heterogeneous network traffic. Journal of Computer and System Sciences 73, 1207–1220 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  45. Tarabia, A.: Two-class priority queueing system with restricted number of priority customers. AEÜ-International Journal of Electronics and Communications 61(8), 534–539 (2007)

    Article  Google Scholar 

  46. Tzenova, E., Adan, I., Kulkarni, V.: Output analysis of multiclass fluid models with static priorities. Performance Evaluation 65(1), 71–81 (2008)

    Article  Google Scholar 

  47. Horvath, A., Horvath, G., Telek, M.: A traffic based decomposition of two-class queueing networks with priority service. Computer Networks 53, 1235–1248 (2009)

    Article  MATH  Google Scholar 

  48. Lee, Y.: Discrete-time Geo x/G/1 queue with preemptive resume priority. Mathematical and Computer Modelling 34(3-4), 243–250 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  49. Walraevens, J., Steyaert, B., Bruneel, H.: Performance analysis of a GI-Geo-1 buffer with a preemptive resume priority scheduling discipline. European Journal of Operational Research 157(1), 130–151 (2004)

    Article  MATH  Google Scholar 

  50. Walraevens, J., Steyaert, B., Bruneel, H.: A packet switch with a priority scheduling discipline: Performance analysis. Telecommunication Systems 28(1), 53–77 (2005)

    Article  Google Scholar 

  51. Van Houdt, B., Blondia, C.: Analyzing priority queues with 3 classes using tree-like processes. Queueing Systems 54 (2), 99–109 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  52. Ndreca, S., Scoppola, B.: Discrete-time GI/Geom/1 queueing system with priority. European Journal of Operational Research 189, 1403–1408 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  53. Walraevens, J., Steyaert, B., Bruneel, H.: Analysis of a discrete-time preemptive resume priority buffer. European Journal of Operational Research 186(1), 182–201 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  54. Sumita, U., Sheng, O.: Analysis of query processing in distributed database systems with fully replicated files: a hierarchical approach. Performance Evaluation 8(3), 223–238 (1988)

    Article  MATH  Google Scholar 

  55. Yoon, C., Un, C.: Unslotted 1- and p i -persistent CSMA-CD protocols for fiber optic bus networks. IEEE Transactions on Communications 42(2-4), 158–465 (1994)

    Google Scholar 

  56. Mukherjee, S., Saha, D., Tripathi, S.: A preemptive protocol for voice-data integration in ring-based LAN: performance analysis and comparison. Performance Evaluation 11(3), 339–354 (1995)

    MATH  Google Scholar 

  57. Walraevens, J., Steyaert, B., Bruneel, H.: A preemptive repeat priority queue with resampling: performance analysis. Annals of Operations Research 146(1), 189–202 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  58. Walraevens, J., Fiems, D., Bruneel, H.: The discrete-time preemptive repeat identical queue. Queueing Systems 53(4), 231–243 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  59. Hong, S., Takagi, H.: Analysis of transmission delay for a structured-priority packet-switching system. Computer Networks and ISDN Systems 29(6), 701–715 (1997)

    Article  Google Scholar 

  60. Kim, K., Chae, K.: Discrete-time queues with discretionary priorities. European Journal of Operational Research 200(2), 473–485 (2010)

    Article  MATH  Google Scholar 

  61. Fidler, M., Persaud, R.: M/G/1 priority scheduling with discrete pre-emption points: on the impacts of fragmentation on IP QoS. Computer Communications 27(12), 1183–1196 (2004)

    Article  Google Scholar 

  62. Fiems, D., Maertens, T., Bruneel, H.: Queueing systems with different types of server interruptions. European Journal of Operational Research 188(3), 838–845 (2008)

    Article  MATH  Google Scholar 

  63. Hsu, J.: Buffer behavior with Poisson arrival and geometric output processes. IEEE Transactions on Communications 22, 1940–1941 (1974)

    Article  Google Scholar 

  64. Heines, T.: Buffer behavior in computer communication systems. IEEE Transactions on Communications 28, 573–576 (1979)

    MATH  Google Scholar 

  65. Bruneel, H.: A general treatment of discrete-time buffers with one randomly interrupted output line. European Journal of Operational Research 27(1), 67–81 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  66. Woodside, C., Ho, E.: Engineering calculation of overflow probabilities in buffers with Markov-interrupted service. IEEE Transactions on Communications 35(12), 1272–1277 (1987)

    Article  Google Scholar 

  67. Yang, O., Mark, J.: Performance analysis of integrated services on a single server system. Performance Evaluation 11, 79–92 (1990)

    Article  Google Scholar 

  68. Lee, D.: Analysis of a single server queue with semi-Markovian service interruption. Queueing Systems 27(1–2), 153–178 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  69. Bruneel, H.: Buffers with stochastic output interruptions. Electronics Letters 19(18), 735–737 (1983)

    Article  Google Scholar 

  70. Georganas, N.: Buffer behavior with Poisson arrivals and bulk geometric output processes. IEEE Transactions on Communications 24(8), 938–940 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  71. Bruneel, H.: A general model for the behaviour of infinite buffers with periodic service opportunities. European Journal of Operational Research 16, 98–106 (1984)

    Article  MATH  Google Scholar 

  72. Laevens, K., Bruneel, H.: Delay analysis for discrete-time queueing systems with multiple randomly interrupted servers. European Journal of Operational Research 85, 161–177 (1995)

    Article  MATH  Google Scholar 

  73. Bruneel, H.: A discrete-time queueing system with a stochastic number of servers subjected to random interruptions. Opsearch 22(4), 215–231 (1985)

    MathSciNet  MATH  Google Scholar 

  74. Bruneel, H.: On buffers with stochastic input and output interruptions. International Journal of Electronics and Communications (AEU) 38(4), 265–271 (1984)

    MATH  Google Scholar 

  75. Ali, M., Zhang, X., Hayes, J.: A discrete-time queueing analysis of the wireless ATM multiplexing system. In: Lorenz, P. (ed.) ICN 2001. LNCS, vol. 2093, pp. 429–438. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  76. Kamoun, F.: Performance evaluation of a queuing system with correlated packet-trains and server interruption. Telecommunication Systems 41(4), 267–277 (2009)

    Article  Google Scholar 

  77. Inghelbrecht, V., Laevens, K., Bruneel, H., Steyaert, B.: Queueing of fixed-length messages in the presence of server interruptions. In: Proceedings Symposium on Performance Evaluation of Computer and Telecommunication Systems, SPECTS 2k, Vancouver, Canada (July 2000)

    Google Scholar 

  78. Fiems, D., Steyaert, B., Bruneel, H.: Performance evaluation of CAI and RAI transmission modes in a GI-G-1 queue. Computers and Operations Research 28(13), 1299–1313 (2001)

    Article  MATH  Google Scholar 

  79. Fiems, D., Steyaert, B., Bruneel, H.: Randomly interrupted GI-G-1 queues, service strategies and stability issues. Annals of Operations Research 112, 171–183 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  80. Fiems, D., Steyaert, B., Bruneel, H.: Analysis of a discrete-time GI-G-1 queueing model subjected to bursty interruptions. Computers and Operations Research 30(1), 139–153 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  81. Fiems, D., Steyaert, B., Bruneel, H.: Discrete-time queues with generally distributed service times and renewal-type server interruptions. Performance Evaluation 55(3-4), 277–298 (2004)

    Article  Google Scholar 

  82. Adan, I., Van Leeuwaarden, J., Winands, E.: On the application of Rouché’s theorem in queueing theory. Operations Research Letters 34(3), 355–360 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  83. Bruneel, H., Kim, B.: Discrete-time models for communication systems including ATM. Kluwer Academic Publisher, Boston (1993)

    Book  Google Scholar 

  84. Fiems, D., Bruneel, H.: A note on the discretization of Little’s result. Operations Research Letters 30(1), 17–18 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  85. Drmota, M.: Systems of functional equations. Random Structures & Algorithms 10(1-2), 103–124 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  86. Flajolet, P., Odlyzko, A.: Singularity analysis of generating functions. SIAM Journal on discrete mathematics 3(2), 216–240 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  87. Takagi, H.: Queueing Analysis; A foundation of performance evaluation. Discrete-time systems, vol. 3. Elsevier Science Publishers, Amsterdam (1993)

    Google Scholar 

  88. Hunter, J.J.: Mathematical Techniques of Applied Probability. Operations Research and Industrial Engineering, vol. 2. Academic Press, New York (1983)

    MATH  Google Scholar 

  89. Bruneel, H.: Performance of discrete-time queuing systems. Computers and Operations Research 20, 303–320 (1993)

    Article  MATH  Google Scholar 

  90. Kleinrock, L.: Queueing systems. Theory, vol. I. John Wiley & Sons, New York (1975)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. SMACS Research Group, Department for Telecommunications and Information Processing (IR07), Ghent University - UGent, Sint-Pietersnieuwstraat 41, B-9000, Gent, Belgium

    Joris Walraevens, Dieter Fiems & Herwig Bruneel

Authors
  1. Joris Walraevens
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dieter Fiems
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Herwig Bruneel
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of Computing, Informatics and Media, University of Bradford, Richmond Road, BD7 1DP, Bradford, UK

    Demetres D. Kouvatsos

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Walraevens, J., Fiems, D., Bruneel, H. (2011). Performance Analysis of Priority Queueing Systems in Discrete Time. In: Kouvatsos, D.D. (eds) Network Performance Engineering. Lecture Notes in Computer Science, vol 5233. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02742-0_10

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-02742-0_10

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-02741-3

  • Online ISBN: 978-3-642-02742-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation