Controlling delay differentiation with priority jumps: Analytical study

Tom Maertens; Joris Walraevens; Herwig Bruneel

doi:10.3934/naco.2011.1.657

Article Contents

2011, Volume 1, Issue 4: 657-673. Doi: 10.3934/naco.2011.1.657

This issue Previous Article Multiserver retrial queues with after-call work Next Article Analysis of the statistical time-access fairness index of one-bit feedback fair scheduler

Controlling delay differentiation with priority jumps: Analytical study

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

Received: June 2011

Revised: August 2011

Published: October 2011

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 68M20, 60K25; Secondary: 90B22, 97I80.

Citation:

Related Papers

Cited by

References

[1]	J. Abate and W. Whitt, Solving probability transform functional equations for numerical inversion, Operations Research Letters, 12 (1992), 275-281.doi: 10.1016/0167-6377(92)90085-H.
[2]	N. Bansal and M. Harchol-Balter, Analysis of SRPT scheduling: investigating unfairness, in "Proceedings of the 2001 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems," (2001), 279-290.doi: 10.1145/378420.378792.
[3]	H. Bruneel and B. G. Kim, "Discrete-time Models for Communication Systems including ATM," Kluwer Academic Publishers, Boston, 1993.doi: 10.1007/978-1-4615-3130-2.
[4]	M. Kargahi and A. Movaghar, A method for performance analysis of Earliest-Deadline-First scheduling policy, The Journal of Supercomputing, 37 (2006), 197-222.doi: 10.1007/s11227-006-5944-2.
[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-1279.doi: 10.1109/49.105173.
[6]	L. M. Le Ny and B. Tuffin, Modeling and analysis of multi-class threshold-based queues with hysteresis using Stochastic Petri Nets, in "Proceedings of the 23rd International Conference on Applications and Theory of Petri Nets; Lecture Notes In Computer Science, Vol. 2360," (2002), 254-272.
[7]	T. Maertens, J. Walraevens and H. Bruneel, On priority queues with priority jumps, Performance Evaluation, 63 (2006), 1235-1252.doi: 10.1016/j.peva.2005.12.003.
[8]	T. Maertens, J. Walraevens and H. Bruneel, A modified HOL priority scheduling discipline: performance analysis, European Journal of Operational Research, 180 (2007), 1168-1185.doi: 10.1016/j.ejor.2006.05.004.
[9]	T. Maertens, J. Walraevens and H. Bruneel, Performance comparison of several priority schemes with prioriy jumps, Annals of Operations Research, 162 (2008), 109-125.doi: 10.1007/s10479-008-0314-5.
[10]	V. Ramaswami and D. M. Lucantoni, Algorithmic analysis of a dynamic priority queue, in "Applied Probability - Computer Science: The Interface, Vol. II" (eds. R. L. Disney and T. J. Ott), (1982), 157-206.
[11]	M. Shreedhar and G. Varghese, Efficient fair queuing using deficit round-robin, IEEE/ACM Transactions on Networking, 4 (1996), 375-385.doi: 10.1109/90.502236.
[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-238.doi: 10.1016/0166-5316(93)E0044-6.
[13]	J. Walraevens, "Discrete-time Queueing Models with Priorities," Ph.D thesis, Ghent University, 2004.
[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-1829.doi: 10.1016/S0305-0548(02)00108-9.
[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-130.doi: 10.1007/s11134-010-9188-8.
[16]	L. Zhang, Virtual clock: a new traffic control algorithm for packet switching networks, ACM Transactions on Computer Systems, 9 (1990), 101-124.doi: 10.1145/103720.103721.