Frame-bound priority scheduling in discrete-time queueing systems

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

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

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 & 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, (2005).
[2]	H. Bruneel, Performance of Discrete-Time Queueing Systems,, Computers Operations Research, 20 (1993), 303. 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.
[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, (2004), 23.
[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. 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.
[8]	L. Kleinrock, "Queueing Systems, Volume I: Theory,", Wiley, (1975).
[9]	V. Klimenok, On the modification of Rouche's theorem for queueing theory problems,, Queueing Systems, 38 (2001), 431. 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. 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 (1989).
[12]	I. Stavrakakis, Delay bounds on a queueing system with consistent priorities,, IEEE Transactions on Communications, 42 (1994), 615. 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.
[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, 40 (2000), 91.
[15]	H. S. Wilf, "Generatingfunctionology,", 2nd edition, (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, (2005).
[2]	H. Bruneel, Performance of Discrete-Time Queueing Systems,, Computers Operations Research, 20 (1993), 303. 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.
[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, (2004), 23.
[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. 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.
[8]	L. Kleinrock, "Queueing Systems, Volume I: Theory,", Wiley, (1975).
[9]	V. Klimenok, On the modification of Rouche's theorem for queueing theory problems,, Queueing Systems, 38 (2001), 431. 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. 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 (1989).
[12]	I. Stavrakakis, Delay bounds on a queueing system with consistent priorities,, IEEE Transactions on Communications, 42 (1994), 615. 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.
[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, 40 (2000), 91.
[15]	H. S. Wilf, "Generatingfunctionology,", 2nd edition, (1994).

[1]	Yoshiaki Kawase, Shoji Kasahara. Priority queueing analysis of transaction-confirmation time for Bitcoin. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-22. 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 & 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 & 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 & Management Optimization, 2019, 15 (3) : 1421-1446. doi: 10.3934/jimo.2018102
[5]	Zsolt Saffer, Wuyi Yue. A dual tandem queueing system with GI service time at the first queue. Journal of Industrial & Management Optimization, 2014, 10 (1) : 167-192. doi: 10.3934/jimo.2014.10.167
[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 & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2018196
[7]	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 & Management Optimization, 2017, 13 (4) : 1945-1973. doi: 10.3934/jimo.2017026
[8]	Wai-Ki Ching, Sin-Man Choi, Min Huang. Optimal service capacity in a multiple-server queueing system: A game theory approach. Journal of Industrial & Management Optimization, 2010, 6 (1) : 73-102. doi: 10.3934/jimo.2010.6.73
[9]	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 & Management Optimization, 2014, 10 (1) : 193-206. doi: 10.3934/jimo.2014.10.193
[10]	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
[11]	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 & Management Optimization, 2012, 8 (2) : 299-323. doi: 10.3934/jimo.2012.8.299
[12]	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
[13]	Fabio Giannoni, Paolo Piccione, Daniel V. Tausk. Morse theory for the travel time brachistochrones in stationary spacetimes. Discrete & Continuous Dynamical Systems - A, 2002, 8 (3) : 697-724. doi: 10.3934/dcds.2002.8.697
[14]	Ketty A. De Rezende, Mariana G. Villapouca. Discrete conley index theory for zero dimensional basic sets. Discrete & Continuous Dynamical Systems - A, 2017, 37 (3) : 1359-1387. doi: 10.3934/dcds.2017056
[15]	Chrystie Burr, Laura Gardini, Ferenc Szidarovszky. Discrete time dynamic oligopolies with adjustment constraints. Journal of Dynamics & Games, 2015, 2 (1) : 65-87. doi: 10.3934/jdg.2015.2.65
[16]	Karl P. Hadeler. Quiescent phases and stability in discrete time dynamical systems. Discrete & Continuous Dynamical Systems - B, 2015, 20 (1) : 129-152. doi: 10.3934/dcdsb.2015.20.129
[17]	Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial & Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499
[18]	Xu Zhang, Chuang Zheng, Enrique Zuazua. Time discrete wave equations: Boundary observability and control. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 571-604. doi: 10.3934/dcds.2009.23.571
[19]	Senda Ounaies, Jean-Marc Bonnisseau, Souhail Chebbi, Halil Mete Soner. Merton problem in an infinite horizon and a discrete time with frictions. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1323-1331. doi: 10.3934/jimo.2016.12.1323
[20]	Thorsten Hüls. Numerical computation of dichotomy rates and projectors in discrete time. Discrete & Continuous Dynamical Systems - B, 2009, 12 (1) : 109-131. doi: 10.3934/dcdsb.2009.12.109

2017 Impact Factor: 0.994

American Institute of Mathematical Sciences