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-281. doi: 10.1016/0167-6377(92)90085-H.  Google Scholar

[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.  Google Scholar

[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.  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-222. 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-1279. 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 "Proceedings of the 23rd International Conference on Applications and Theory of Petri Nets; Lecture Notes In Computer Science, Vol. 2360," (2002), 254-272. Google Scholar

[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.  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-1185. 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-125. doi: 10.1007/s10479-008-0314-5.  Google Scholar

[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. Google Scholar

[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.  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-238. doi: 10.1016/0166-5316(93)E0044-6.  Google Scholar

[13]

J. Walraevens, "Discrete-time Queueing Models with Priorities," Ph.D thesis, Ghent University, 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-1829. 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-130. 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-124. 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-281. doi: 10.1016/0167-6377(92)90085-H.  Google Scholar

[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.  Google Scholar

[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.  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-222. 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-1279. 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 "Proceedings of the 23rd International Conference on Applications and Theory of Petri Nets; Lecture Notes In Computer Science, Vol. 2360," (2002), 254-272. Google Scholar

[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.  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-1185. 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-125. doi: 10.1007/s10479-008-0314-5.  Google Scholar

[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. Google Scholar

[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.  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-238. doi: 10.1016/0166-5316(93)E0044-6.  Google Scholar

[13]

J. Walraevens, "Discrete-time Queueing Models with Priorities," Ph.D thesis, Ghent University, 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-1829. 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-130. 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-124. doi: 10.1145/103720.103721.  Google Scholar

[1]

Sofian De Clercq, Koen De Turck, Bart Steyaert, Herwig Bruneel. Frame-bound priority scheduling in discrete-time queueing systems. Journal of Industrial & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Management Optimization, 2020, 16 (3) : 1149-1169. doi: 10.3934/jimo.2018197
[20]

Zhanyou Ma, Pengcheng Wang, Wuyi Yue. Performance analysis and optimization of a pseudo-fault Geo/Geo/1 repairable queueing system with N-policy, setup time and multiple working vacations. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1467-1481. doi: 10.3934/jimo.2017002

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences