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]

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

Angelica Pachon, Federico Polito, Costantino Ricciuti. On discrete-time semi-Markov processes. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1499-1529. doi: 10.3934/dcdsb.2020170
[3]

Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046
[4]

Cuicui Li, Lin Zhou, Zhidong Teng, Buyu Wen. The threshold dynamics of a discrete-time echinococcosis transmission model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020339
[5]

Veena Goswami, Gopinath Panda. Optimal customer behavior in observable and unobservable discrete-time queues. Journal of Industrial & Management Optimization, 2021, 17 (1) : 299-316. doi: 10.3934/jimo.2019112
[6]

Ming Chen, Hao Wang. Dynamics of a discrete-time stoichiometric optimal foraging model. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 107-120. doi: 10.3934/dcdsb.2020264
[7]

Peter Giesl, Zachary Langhorne, Carlos Argáez, Sigurdur Hafstein. Computing complete Lyapunov functions for discrete-time dynamical systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 299-336. doi: 10.3934/dcdsb.2020331
[8]

Stefan Siegmund, Petr Stehlík. Time scale-induced asynchronous discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1011-1029. doi: 10.3934/dcdsb.2020151
[9]

Ting Liu, Guo-Bao Zhang. Global stability of traveling waves for a spatially discrete diffusion system with time delay. Electronic Research Archive, , () : -. doi: 10.3934/era.2021003
[10]

Haixiang Yao, Ping Chen, Miao Zhang, Xun Li. Dynamic discrete-time portfolio selection for defined contribution pension funds with inflation risk. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020166
[11]

Guangjun Shen, Xueying Wu, Xiuwei Yin. Stabilization of stochastic differential equations driven by G-Lévy process with discrete-time feedback control. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 755-774. doi: 10.3934/dcdsb.2020133
[12]

Jian Zhang, Tony T. Lee, Tong Ye, Liang Huang. An approximate mean queue length formula for queueing systems with varying service rate. Journal of Industrial & Management Optimization, 2021, 17 (1) : 185-204. doi: 10.3934/jimo.2019106
[13]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451
[14]

Kung-Ching Chang, Xuefeng Wang, Xie Wu. On the spectral theory of positive operators and PDE applications. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3171-3200. doi: 10.3934/dcds.2020054
[15]

Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458
[16]

Sergey Rashkovskiy. Hamilton-Jacobi theory for Hamiltonian and non-Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 563-583. doi: 10.3934/jgm.2020024
[17]

Tuoc Phan, Grozdena Todorova, Borislav Yordanov. Existence uniqueness and regularity theory for elliptic equations with complex-valued potentials. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1071-1099. doi: 10.3934/dcds.2020310
[18]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, 2021, 14 (1) : 115-148. doi: 10.3934/krm.2020051
[19]

Javier Fernández, Cora Tori, Marcela Zuccalli. Lagrangian reduction of nonholonomic discrete mechanical systems by stages. Journal of Geometric Mechanics, 2020, 12 (4) : 607-639. doi: 10.3934/jgm.2020029
[20]

Sören Bartels, Jakob Keck. Adaptive time stepping in elastoplasticity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 71-88. doi: 10.3934/dcdss.2020323

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences