American Institute of Mathematical Sciences

Advanced
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

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

[2]

H. Bruneel, Performance of Discrete-Time Queueing Systems,, Computers Operations Research, 20 (1993), 303.  doi: 10.1016/0305-0548(93)90006-5.  Google Scholar

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

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

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

[6]

R. G. Gallager, "Discrete Stochastic Processes,", Kluwer Academic Publishers, (1996).   Google Scholar

[7]

S. Halfin, Batch Delays Versus Customer Delays,, The Bell System Technical Journal, 62 (1983), 2011.   Google Scholar

[8]

L. Kleinrock, "Queueing Systems, Volume I: Theory,", Wiley, (1975).   Google Scholar

[9]

V. Klimenok, On the modification of Rouche's theorem for queueing theory problems,, Queueing Systems, 38 (2001), 431.  doi: 10.1023/A:1010999928701.  Google Scholar

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

[11]

M. F. Neuts, "Structured Stochastic Matrices of $M$/$G$/$1$ Type and Their Applications,", Probability: Pure and Applied, 5 (1989).   Google Scholar

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

[13]

H. Takada and K. Kobayashi, Loss Systems with Multi-Thresholds on Network Calculus,, Proc. of Queueing Symposium, (2007), 241.   Google Scholar

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

[15]

H. S. Wilf, "Generatingfunctionology,", 2nd edition, (1994).   Google Scholar

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

[2]

H. Bruneel, Performance of Discrete-Time Queueing Systems,, Computers Operations Research, 20 (1993), 303.  doi: 10.1016/0305-0548(93)90006-5.  Google Scholar

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

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

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

[6]

R. G. Gallager, "Discrete Stochastic Processes,", Kluwer Academic Publishers, (1996).   Google Scholar

[7]

S. Halfin, Batch Delays Versus Customer Delays,, The Bell System Technical Journal, 62 (1983), 2011.   Google Scholar

[8]

L. Kleinrock, "Queueing Systems, Volume I: Theory,", Wiley, (1975).   Google Scholar

[9]

V. Klimenok, On the modification of Rouche's theorem for queueing theory problems,, Queueing Systems, 38 (2001), 431.  doi: 10.1023/A:1010999928701.  Google Scholar

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

[11]

M. F. Neuts, "Structured Stochastic Matrices of $M$/$G$/$1$ Type and Their Applications,", Probability: Pure and Applied, 5 (1989).   Google Scholar

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

[13]

H. Takada and K. Kobayashi, Loss Systems with Multi-Thresholds on Network Calculus,, Proc. of Queueing Symposium, (2007), 241.   Google Scholar

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

[15]

H. S. Wilf, "Generatingfunctionology,", 2nd edition, (1994).   Google Scholar

[1]

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
[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, 2020, 16 (3) : 1135-1148. 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]

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
[11]

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
[12]

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
[13]

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
[14]

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
[15]

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
[16]

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
[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]

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
[19]

Angelica Pachon, Federico Polito, Costantino Ricciuti. On discrete-time semi-Markov processes. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020170
[20]

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

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (92)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences