Frame-bound priority scheduling in discrete-time queueing systems

Previous Article
JIMO Home
This Issue
Next Article
Stability of a retrial queueing network with different classes of customers and restricted resource pooling

July 2011, 7(3): 767-788. doi: 10.3934/jimo.2011.7.767

Frame-bound priority scheduling in discrete-time queueing systems

Sofian De Clercq ^1, , Koen De Turck ^1, , Bart Steyaert ^1, and Herwig Bruneel ^1,

1.	SMACS Research Group, Ghent University, St.-Pietersnieuwstraat 41, 9000 Gent, Belgium, Belgium, Belgium, Belgium

Received September 2010 Revised May 2011 Published June 2011

Abstract
Related Papers
Under a Creative Commons license

A well-known problem with priority policies is starvation of delay-tolerant traffic. Additionally, insufficient control over delay differentiation (which is needed for modern network applications) has incited the development of sophisticated scheduling disciplines. The priority policy we present here has the benefit of being open to rigorous analysis. We study a discrete-time queueing system with a single server and single queue, in which $N$ types of customers enter pertaining to different priorities. A general i.i.d. arrival process is assumed and service times are generally distributed. We divide the time axis into 'frames' of fixed size (counted as a number of time-slots), and reorder the customers that enter the system during the same frame such that the high-priority customers are served first. This paper gives an analytic approach to studying such a system, and in particular focuses on the system content (meaning the customers of each type in the system at random slotmarks) in stationary regime, and the delay distribution of a random customer. Clearly, in such a system the frame's size is the key factor in the delay differentiation between the $N$ priority classes. The numerical results at the end of this paper illustrate this observation.

Keywords: discrete-time., Queueing theory, priority.

Mathematics Subject Classification: Primary: 60K25, 68M20; Secondary: 90B2.

Citation: 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

References:

[1]	D. A. Bini, G. Latouche and B. Meini, "Numerical Methods for Structured Markov Chains," Numerical Mathematics and Scientific Computation, Oxford Science Pulications, Oxford University Press, New York, 2005.
[2]	H. Bruneel, Performance of Discrete-Time Queueing Systems, Computers Operations Research, 20 (1993), 303-320 doi: 10.1016/0305-0548(93)90006-5.
[3]	S. De Clercq, B. Steyaert and H. Bruneel, Analysis of a Multi-Class Discrete-time Queueing System under the Slot-Bound Priority rule, Proceedings of the 6th St. Petersburg Workshop on Simulation, (2009), 827-832.
[4]	S. De Vuyst, S. Wittevrongel and H. Bruneel, A queueing discipline with place reservation, Proceedings of the COST 279 Eleventh Management Committee Meeting (Ghent, 23-24 September 2004), COST279TD(04)36.
[5]	H. R. Gail, S. L. Hantler and B. A. Taylor, Spectral Analysis of $M$/$G$/$1$ and $G$/$M$/$1$ Type Markov chains, Advances in Applied Probability, 28 (1996), 114-165. doi: 10.2307/1427915.
[6]	R. G. Gallager, "Discrete Stochastic Processes," Kluwer Academic Publishers, 1996.
[7]	S. Halfin, Batch Delays Versus Customer Delays, The Bell System Technical Journal, 62 (1983), 2011-2015.
[8]	L. Kleinrock, "Queueing Systems, Volume I: Theory," Wiley, New York, 1975.
[9]	V. Klimenok, On the modification of Rouche's theorem for queueing theory problems, Queueing Systems, 38 (2001), 431-434. doi: 10.1023/A:1010999928701.
[10]	K. Y. Liu, D. W. Petr, V. S. Frost, H. B. Zhu, C. Braun and W. L. Edwards, Design and analysis of a bandwidth management framework for ATM-based broadband ISDN, IEEE Communications Magazine, 35 (1997), 138-145. doi: 10.1109/35.592108.
[11]	M. F. Neuts, "Structured Stochastic Matrices of $M$/$G$/$1$ Type and Their Applications," Probability: Pure and Applied, 5, Marcel Dekker, Inc., New York, 1989.
[12]	I. Stavrakakis, Delay bounds on a queueing system with consistent priorities, IEEE Transactions on Communications, 42 (1994), 615-624. doi: 10.1109/TCOMM.1994.577089.
[13]	H. Takada and K. Kobayashi, Loss Systems with Multi-Thresholds on Network Calculus, Proc. of Queueing Symposium, (2007), 241-250.
[14]	J. Walraevens, B. Steyaert and H. Bruneel, 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 (2000), 91-103
[15]	H. S. Wilf, "Generatingfunctionology," 2nd edition, Academic Press, Inc., Boston, 1994.

show all references

References:

[1]	D. A. Bini, G. Latouche and B. Meini, "Numerical Methods for Structured Markov Chains," Numerical Mathematics and Scientific Computation, Oxford Science Pulications, Oxford University Press, New York, 2005.
[2]	H. Bruneel, Performance of Discrete-Time Queueing Systems, Computers Operations Research, 20 (1993), 303-320 doi: 10.1016/0305-0548(93)90006-5.
[3]	S. De Clercq, B. Steyaert and H. Bruneel, Analysis of a Multi-Class Discrete-time Queueing System under the Slot-Bound Priority rule, Proceedings of the 6th St. Petersburg Workshop on Simulation, (2009), 827-832.
[4]	S. De Vuyst, S. Wittevrongel and H. Bruneel, A queueing discipline with place reservation, Proceedings of the COST 279 Eleventh Management Committee Meeting (Ghent, 23-24 September 2004), COST279TD(04)36.
[5]	H. R. Gail, S. L. Hantler and B. A. Taylor, Spectral Analysis of $M$/$G$/$1$ and $G$/$M$/$1$ Type Markov chains, Advances in Applied Probability, 28 (1996), 114-165. doi: 10.2307/1427915.
[6]	R. G. Gallager, "Discrete Stochastic Processes," Kluwer Academic Publishers, 1996.
[7]	S. Halfin, Batch Delays Versus Customer Delays, The Bell System Technical Journal, 62 (1983), 2011-2015.
[8]	L. Kleinrock, "Queueing Systems, Volume I: Theory," Wiley, New York, 1975.
[9]	V. Klimenok, On the modification of Rouche's theorem for queueing theory problems, Queueing Systems, 38 (2001), 431-434. doi: 10.1023/A:1010999928701.
[10]	K. Y. Liu, D. W. Petr, V. S. Frost, H. B. Zhu, C. Braun and W. L. Edwards, Design and analysis of a bandwidth management framework for ATM-based broadband ISDN, IEEE Communications Magazine, 35 (1997), 138-145. doi: 10.1109/35.592108.
[11]	M. F. Neuts, "Structured Stochastic Matrices of $M$/$G$/$1$ Type and Their Applications," Probability: Pure and Applied, 5, Marcel Dekker, Inc., New York, 1989.
[12]	I. Stavrakakis, Delay bounds on a queueing system with consistent priorities, IEEE Transactions on Communications, 42 (1994), 615-624. doi: 10.1109/TCOMM.1994.577089.
[13]	H. Takada and K. Kobayashi, Loss Systems with Multi-Thresholds on Network Calculus, Proc. of Queueing Symposium, (2007), 241-250.
[14]	J. Walraevens, B. Steyaert and H. Bruneel, 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 (2000), 91-103
[15]	H. S. Wilf, "Generatingfunctionology," 2nd edition, Academic Press, Inc., Boston, 1994.

[1]	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
[2]	Yung Chung Wang, Jenn Shing Wang, Fu Hsiang Tsai. Analysis of discrete-time space priority queue with fuzzy threshold. Journal of Industrial and Management Optimization, 2009, 5 (3) : 467-479. doi: 10.3934/jimo.2009.5.467
[3]	Zaidong Zhan, Shuping Chen, Wei Wei. A unified theory of maximum principle for continuous and discrete time optimal control problems. Mathematical Control and Related Fields, 2012, 2 (2) : 195-215. doi: 10.3934/mcrf.2012.2.195
[4]	Shaojun Lan, Yinghui Tang. Performance analysis of a discrete-time $ Geo/G/1$ retrial queue with non-preemptive priority, working vacations and vacation interruption. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1421-1446. doi: 10.3934/jimo.2018102
[5]	Raina Raj, Vidyottama Jain. Optimization of traffic control in $ MMAP\mathit{[2]}/PH\mathit{[2]}/S$ priority queueing model with $ PH $ retrial times and the preemptive repeat policy. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022044
[6]	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
[7]	Zsolt Saffer, Wuyi Yue. A dual tandem queueing system with GI service time at the first queue. Journal of Industrial and Management Optimization, 2014, 10 (1) : 167-192. doi: 10.3934/jimo.2014.10.167
[8]	Hideaki Takagi. Unified and refined analysis of the response time and waiting time in the M/M/m FCFS preemptive-resume priority queue. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1945-1973. doi: 10.3934/jimo.2017026
[9]	Wai-Ki Ching, Sin-Man Choi, Min Huang. Optimal service capacity in a multiple-server queueing system: A game theory approach. Journal of Industrial and Management Optimization, 2010, 6 (1) : 73-102. doi: 10.3934/jimo.2010.6.73
[10]	Willem Mélange, Herwig Bruneel, Bart Steyaert, Dieter Claeys, Joris Walraevens. A continuous-time queueing model with class clustering and global FCFS service discipline. Journal of Industrial and Management Optimization, 2014, 10 (1) : 193-206. doi: 10.3934/jimo.2014.10.193
[11]	Ketty A. De Rezende, Mariana G. Villapouca. Discrete conley index theory for zero dimensional basic sets. Discrete and Continuous Dynamical Systems, 2017, 37 (3) : 1359-1387. doi: 10.3934/dcds.2017056
[12]	Fabio Giannoni, Paolo Piccione, Daniel V. Tausk. Morse theory for the travel time brachistochrones in stationary spacetimes. Discrete and Continuous Dynamical Systems, 2002, 8 (3) : 697-724. doi: 10.3934/dcds.2002.8.697
[13]	Ernst Eberlein, Dilip B. Madan. Portfolio theory for squared returns correlated across time. Probability, Uncertainty and Quantitative Risk, 2016, 1 (0) : 1-. doi: 10.1186/s41546-016-0001-4
[14]	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 and Management Optimization, 2017, 13 (3) : 1467-1481. doi: 10.3934/jimo.2017002
[15]	Sin-Man Choi, Ximin Huang, Wai-Ki Ching. Minimizing equilibrium expected sojourn time via performance-based mixed threshold demand allocation in a multiple-server queueing environment. Journal of Industrial and Management Optimization, 2012, 8 (2) : 299-323. doi: 10.3934/jimo.2012.8.299
[16]	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
[17]	Omer Gursoy, Kamal Adli Mehr, Nail Akar. Steady-state and first passage time distributions for waiting times in the MAP/M/s+G queueing model with generally distributed patience times. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2505-2532. doi: 10.3934/jimo.2021078
[18]	Chrystie Burr, Laura Gardini, Ferenc Szidarovszky. Discrete time dynamic oligopolies with adjustment constraints. Journal of Dynamics and Games, 2015, 2 (1) : 65-87. doi: 10.3934/jdg.2015.2.65
[19]	Karl P. Hadeler. Quiescent phases and stability in discrete time dynamical systems. Discrete and Continuous Dynamical Systems - B, 2015, 20 (1) : 129-152. doi: 10.3934/dcdsb.2015.20.129
[20]	Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial and Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Sofian De Clercq Koen De Turck Bart Steyaert Herwig Bruneel
on Google Scholar
Sofian De Clercq Koen De Turck Bart Steyaert Herwig Bruneel

[Back to Top]