American Institute of Mathematical Sciences

Advanced
2011, 1(4): 657-673. doi: 10.3934/naco.2011.1.657

Controlling delay differentiation with priority jumps: Analytical study

Tom Maertens 1, , Joris Walraevens 2, and  Herwig Bruneel 2,

1. 

SMACS Research Group, Department of Telecommunications and Information Processing (TELIN), Ghent University (UGent), Sint-Pietersnieuwstraat 41, B-9000 Gent, Belgium
2. 

Department of Telecommunications and Information Processing, Ghent University, St-Pietersnieuwstraat 41, 9000 Gent, Belgium

Received  June 2011 Revised  August 2011 Published  November 2011

Supporting different services with different Quality of Service (QoS) requirements is not an easy task in modern telecommunication systems: an efficient priority scheduling discipline is of great importance.~Fixed or static priority achieves maximal delay differentiation between different types of traffic, but may have a too severe impact on the performance of lower-priority traffic.~In this paper, we propose a priority scheduling discipline with priority jumps to control the delay differentiation.~In this scheduling discipline, packets can be promoted to a higher priority level in the course of time.~We use probability generating functions to study the queueing system analytically.~Some interesting mathematical challenges thereby arise.~With some numerical examples, we finally show the impact of the priority jumps and of the system parameters.
Keywords: Queueing theory, priority scheduling., performance evaluation.
Mathematics Subject Classification: Primary: 68M20, 60K25; Secondary: 90B22, 97I8.
Citation: Tom Maertens, Joris Walraevens, Herwig Bruneel. Controlling delay differentiation with priority jumps: Analytical study. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 657-673. doi: 10.3934/naco.2011.1.657
References:
[1]

J. Abate and W. Whitt, Solving probability transform functional equations for numerical inversion,, Operations Research Letters, 12 (1992), 275.  doi: 10.1016/0167-6377(92)90085-H.  Google Scholar

[2]

N. Bansal and M. Harchol-Balter, Analysis of SRPT scheduling: investigating unfairness,, in, (2001), 279.  doi: 10.1145/378420.378792.  Google Scholar

[3]

H. Bruneel and B. G. Kim, "Discrete-time Models for Communication Systems including ATM,", Kluwer Academic Publishers, (1993).  doi: 10.1007/978-1-4615-3130-2.  Google Scholar

[4]

M. Kargahi and A. Movaghar, A method for performance analysis of Earliest-Deadline-First scheduling policy,, The Journal of Supercomputing, 37 (2006), 197.  doi: 10.1007/s11227-006-5944-2.  Google Scholar

[5]

M. Katevenis, S. Sidiropoulos and C. Courcoubetis, Weighted round-robin cell multiplexing in a general-purpose ATMswitch chip,, IEEE Journal on Selected Areas in Communications, 9 (1991), 1265.  doi: 10.1109/49.105173.  Google Scholar

[6]

L. M. Le Ny and B. Tuffin, Modeling and analysis of multi-class threshold-based queues with hysteresis using Stochastic Petri Nets,, in, (2002), 254.   Google Scholar

[7]

T. Maertens, J. Walraevens and H. Bruneel, On priority queues with priority jumps,, Performance Evaluation, 63 (2006), 1235.  doi: 10.1016/j.peva.2005.12.003.  Google Scholar

[8]

T. Maertens, J. Walraevens and H. Bruneel, A modified HOL priority scheduling discipline: performance analysis,, European Journal of Operational Research, 180 (2007), 1168.  doi: 10.1016/j.ejor.2006.05.004.  Google Scholar

[9]

T. Maertens, J. Walraevens and H. Bruneel, Performance comparison of several priority schemes with prioriy jumps,, Annals of Operations Research, 162 (2008), 109.  doi: 10.1007/s10479-008-0314-5.  Google Scholar

[10]

V. Ramaswami and D. M. Lucantoni, Algorithmic analysis of a dynamic priority queue,, in, (1982), 157.   Google Scholar

[11]

M. Shreedhar and G. Varghese, Efficient fair queuing using deficit round-robin,, IEEE/ACM Transactions on Networking, 4 (1996), 375.  doi: 10.1109/90.502236.  Google Scholar

[12]

A. Sugahara, T. Takine, Y. Takahashi and T. Hasegawa, Analysis of a non-preemptive priority queue with SPP arrivals of high class,, Performance Evaluation, 21 (1995), 215.  doi: 10.1016/0166-5316(93)E0044-6.  Google Scholar

[13]

J. Walraevens, "Discrete-time Queueing Models with Priorities,", Ph.D thesis, (2004).   Google Scholar

[14]

J. Walraevens, B. Steyaert and H. Bruneel, Performance analysis of a single-server ATM queue with a priority scheduling,, Computers and Operations Research, 30 (2003), 1807.  doi: 10.1016/S0305-0548(02)00108-9.  Google Scholar

[15]

J. Walraevens, J. S. H. van Leeuwaarden and O. J. Boxma, Power series approximations for two-class generalized processor sharing systems,, Queueing Systems, 66 (2010), 107.  doi: 10.1007/s11134-010-9188-8.  Google Scholar

[16]

L. Zhang, Virtual clock: a new traffic control algorithm for packet switching networks,, ACM Transactions on Computer Systems, 9 (1990), 101.  doi: 10.1145/103720.103721.  Google Scholar

show all references

References:
[1]

J. Abate and W. Whitt, Solving probability transform functional equations for numerical inversion,, Operations Research Letters, 12 (1992), 275.  doi: 10.1016/0167-6377(92)90085-H.  Google Scholar

[2]

N. Bansal and M. Harchol-Balter, Analysis of SRPT scheduling: investigating unfairness,, in, (2001), 279.  doi: 10.1145/378420.378792.  Google Scholar

[3]

H. Bruneel and B. G. Kim, "Discrete-time Models for Communication Systems including ATM,", Kluwer Academic Publishers, (1993).  doi: 10.1007/978-1-4615-3130-2.  Google Scholar

[4]

M. Kargahi and A. Movaghar, A method for performance analysis of Earliest-Deadline-First scheduling policy,, The Journal of Supercomputing, 37 (2006), 197.  doi: 10.1007/s11227-006-5944-2.  Google Scholar

[5]

M. Katevenis, S. Sidiropoulos and C. Courcoubetis, Weighted round-robin cell multiplexing in a general-purpose ATMswitch chip,, IEEE Journal on Selected Areas in Communications, 9 (1991), 1265.  doi: 10.1109/49.105173.  Google Scholar

[6]

L. M. Le Ny and B. Tuffin, Modeling and analysis of multi-class threshold-based queues with hysteresis using Stochastic Petri Nets,, in, (2002), 254.   Google Scholar

[7]

T. Maertens, J. Walraevens and H. Bruneel, On priority queues with priority jumps,, Performance Evaluation, 63 (2006), 1235.  doi: 10.1016/j.peva.2005.12.003.  Google Scholar

[8]

T. Maertens, J. Walraevens and H. Bruneel, A modified HOL priority scheduling discipline: performance analysis,, European Journal of Operational Research, 180 (2007), 1168.  doi: 10.1016/j.ejor.2006.05.004.  Google Scholar

[9]

T. Maertens, J. Walraevens and H. Bruneel, Performance comparison of several priority schemes with prioriy jumps,, Annals of Operations Research, 162 (2008), 109.  doi: 10.1007/s10479-008-0314-5.  Google Scholar

[10]

V. Ramaswami and D. M. Lucantoni, Algorithmic analysis of a dynamic priority queue,, in, (1982), 157.   Google Scholar

[11]

M. Shreedhar and G. Varghese, Efficient fair queuing using deficit round-robin,, IEEE/ACM Transactions on Networking, 4 (1996), 375.  doi: 10.1109/90.502236.  Google Scholar

[12]

A. Sugahara, T. Takine, Y. Takahashi and T. Hasegawa, Analysis of a non-preemptive priority queue with SPP arrivals of high class,, Performance Evaluation, 21 (1995), 215.  doi: 10.1016/0166-5316(93)E0044-6.  Google Scholar

[13]

J. Walraevens, "Discrete-time Queueing Models with Priorities,", Ph.D thesis, (2004).   Google Scholar

[14]

J. Walraevens, B. Steyaert and H. Bruneel, Performance analysis of a single-server ATM queue with a priority scheduling,, Computers and Operations Research, 30 (2003), 1807.  doi: 10.1016/S0305-0548(02)00108-9.  Google Scholar

[15]

J. Walraevens, J. S. H. van Leeuwaarden and O. J. Boxma, Power series approximations for two-class generalized processor sharing systems,, Queueing Systems, 66 (2010), 107.  doi: 10.1007/s11134-010-9188-8.  Google Scholar

[16]

L. Zhang, Virtual clock: a new traffic control algorithm for packet switching networks,, ACM Transactions on Computer Systems, 9 (1990), 101.  doi: 10.1145/103720.103721.  Google Scholar

[1]

Shuyang Dai, Fengru Wang, Jerry Zhijian Yang, Cheng Yuan. A comparative study of atomistic-based stress evaluation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020322
[2]

Jian Zhang, Tony T. Lee, Tong Ye, Liang Huang. An approximate mean queue length formula for queueing systems with varying service rate. Journal of Industrial & Management Optimization, 2021, 17 (1) : 185-204. doi: 10.3934/jimo.2019106
[3]

Min Ji, Xinna Ye, Fangyao Qian, T.C.E. Cheng, Yiwei Jiang. Parallel-machine scheduling in shared manufacturing. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020174
[4]

Onur Şimşek, O. Erhun Kundakcioglu. Cost of fairness in agent scheduling for contact centers. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021001
[5]

Tomáš Bodnár, Philippe Fraunié, Petr Knobloch, Hynek Řezníček. Numerical evaluation of artificial boundary condition for wall-bounded stably stratified flows. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 785-801. doi: 10.3934/dcdss.2020333
[6]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451
[7]

Kung-Ching Chang, Xuefeng Wang, Xie Wu. On the spectral theory of positive operators and PDE applications. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3171-3200. doi: 10.3934/dcds.2020054
[8]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122
[9]

Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458
[10]

Sergey Rashkovskiy. Hamilton-Jacobi theory for Hamiltonian and non-Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 563-583. doi: 10.3934/jgm.2020024
[11]

Tuoc Phan, Grozdena Todorova, Borislav Yordanov. Existence uniqueness and regularity theory for elliptic equations with complex-valued potentials. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1071-1099. doi: 10.3934/dcds.2020310
[12]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, 2021, 14 (1) : 115-148. doi: 10.3934/krm.2020051
[13]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, 2021, 20 (1) : 449-465. doi: 10.3934/cpaa.2020276
[14]

Jann-Long Chern, Sze-Guang Yang, Zhi-You Chen, Chih-Her Chen. On the family of non-topological solutions for the elliptic system arising from a product Abelian gauge field theory. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3291-3304. doi: 10.3934/dcds.2020127
[15]

Van Duong Dinh. Random data theory for the cubic fourth-order nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020284
[16]

Editorial Office. Retraction: Xiao-Qian Jiang and Lun-Chuan Zhang, A pricing option approach based on backward stochastic differential equation theory. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 969-969. doi: 10.3934/dcdss.2019065

 Impact Factor: 

Tools

Metrics

  • PDF downloads (36)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences