Controlling delay differentiation with priority jumps: Analytical study

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

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

Abstract
Related Papers

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

show all references

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.

[1]	Sofian De Clercq, Koen De Turck, Bart Steyaert, Herwig Bruneel. Frame-bound priority scheduling in discrete-time queueing systems. Journal of Industrial and Management Optimization, 2011, 7 (3) : 767-788. doi: 10.3934/jimo.2011.7.767
[2]	Zhanyou Ma, Wenbo Wang, Linmin Hu. Performance evaluation and analysis of a discrete queue system with multiple working vacations and non-preemptive priority. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1135-1148. doi: 10.3934/jimo.2018196
[3]	Omer Faruk Yilmaz, Mehmet Bulent Durmusoglu. A performance comparison and evaluation of metaheuristics for a batch scheduling problem in a multi-hybrid cell manufacturing system with skilled workforce assignment. Journal of Industrial and Management Optimization, 2018, 14 (3) : 1219-1249. doi: 10.3934/jimo.2018007
[4]	Zhanqiang Huo, Wuyi Yue, Naishuo Tian, Shunfu Jin. Performance evaluation for the sleep mode in the IEEE 802.16e based on a queueing model with close-down time and multiple vacations. Journal of Industrial and Management Optimization, 2009, 5 (3) : 511-524. doi: 10.3934/jimo.2009.5.511
[5]	Yoshiaki Kawase, Shoji Kasahara. Priority queueing analysis of transaction-confirmation time for Bitcoin. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1077-1098. doi: 10.3934/jimo.2018193
[6]	Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391
[7]	Zhanyou Ma, Wuyi Yue, Xiaoli Su. Performance analysis of a Geom/Geom/1 queueing system with variable input probability. Journal of Industrial and Management Optimization, 2011, 7 (3) : 641-653. doi: 10.3934/jimo.2011.7.641
[8]	Shunfu Jin, Wuyi Yue, Zhanqiang Huo. Performance evaluation for connection oriented service in the next generation Internet. Numerical Algebra, Control and Optimization, 2011, 1 (4) : 749-761. doi: 10.3934/naco.2011.1.749
[9]	Shunfu Jin, Wuyi Yue, Chao Meng, Zsolt Saffer. A novel active DRX mechanism in LTE technology and its performance evaluation. Journal of Industrial and Management Optimization, 2015, 11 (3) : 849-866. doi: 10.3934/jimo.2015.11.849
[10]	Shunfu Jin, Haixing Wu, Wuyi Yue, Yutaka Takahashi. Performance evaluation and Nash equilibrium of a cloud architecture with a sleeping mechanism and an enrollment service. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2407-2424. doi: 10.3934/jimo.2019060
[11]	Keiji Tatsumi, Masashi Akao, Ryo Kawachi, Tetsuzo Tanino. Performance evaluation of multiobjective multiclass support vector machines maximizing geometric margins. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 151-169. doi: 10.3934/naco.2011.1.151
[12]	Tuan Phung-Duc, Wouter Rogiest, Sabine Wittevrongel. Single server retrial queues with speed scaling: Analysis and performance evaluation. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1927-1943. doi: 10.3934/jimo.2017025
[13]	Yuan Zhao, Wuyi Yue. Cognitive radio networks with multiple secondary users under two kinds of priority schemes: Performance comparison and optimization. Journal of Industrial and Management Optimization, 2017, 13 (3) : 1449-1466. doi: 10.3934/jimo.2017001
[14]	Kyosuke Hashimoto, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance analysis of backup-task scheduling with deadline time in cloud computing. Journal of Industrial and Management Optimization, 2015, 11 (3) : 867-886. doi: 10.3934/jimo.2015.11.867
[15]	Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control and Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115
[16]	Shunfu Jin, Wuyi Yue. Performance analysis and evaluation for power saving class type III in IEEE 802.16e network. Journal of Industrial and Management Optimization, 2010, 6 (3) : 691-708. doi: 10.3934/jimo.2010.6.691
[17]	Yuan Zhao, Wuyi Yue. Performance evaluation and optimization of cognitive radio networks with adjustable access control for multiple secondary users. Journal of Industrial and Management Optimization, 2019, 15 (1) : 1-14. doi: 10.3934/jimo.2018029
[18]	Shunfu Jin, Wuyi Yue, Xuena Yan. Performance evaluation of a power saving mechanism in IEEE 802.16 wireless MANs with bi-directional traffic. Journal of Industrial and Management Optimization, 2011, 7 (3) : 717-733. doi: 10.3934/jimo.2011.7.717
[19]	Jianping Liu, Shunfu Jin. An imperfect sensing-based channel reservation strategy in CRNs and its performance evaluation. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1149-1169. doi: 10.3934/jimo.2018197
[20]	Chia-Huang Wu, Dong-Yuh Yang, Chia-Ru Yong. Performance evaluation and bi-objective optimization for $ F $-policy queue with alternating service rates. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022111

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Tom Maertens Joris Walraevens Herwig Bruneel
on Google Scholar
Tom Maertens Joris Walraevens Herwig Bruneel

[Back to Top]