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]

Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183
[2]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311
[3]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349
[4]

Chin-Chin Wu. Existence of traveling wavefront for discrete bistable competition model. Discrete & Continuous Dynamical Systems - B, 2011, 16 (3) : 973-984. doi: 10.3934/dcdsb.2011.16.973
[5]

Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355
[6]

Ronald E. Mickens. Positivity preserving discrete model for the coupled ODE's modeling glycolysis. Conference Publications, 2003, 2003 (Special) : 623-629. doi: 10.3934/proc.2003.2003.623
[7]

Cécile Carrère, Grégoire Nadin. Influence of mutations in phenotypically-structured populations in time periodic environment. Discrete & Continuous Dynamical Systems - B, 2020, 25 (9) : 3609-3630. doi: 10.3934/dcdsb.2020075
[8]

Guillermo Reyes, Juan-Luis Vázquez. Long time behavior for the inhomogeneous PME in a medium with slowly decaying density. Communications on Pure & Applied Analysis, 2009, 8 (2) : 493-508. doi: 10.3934/cpaa.2009.8.493
[9]

Wei-Jian Bo, Guo Lin, Shigui Ruan. Traveling wave solutions for time periodic reaction-diffusion systems. Discrete & Continuous Dynamical Systems - A, 2018, 38 (9) : 4329-4351. doi: 10.3934/dcds.2018189
[10]

Kin Ming Hui, Soojung Kim. Asymptotic large time behavior of singular solutions of the fast diffusion equation. Discrete & Continuous Dynamical Systems - A, 2017, 37 (11) : 5943-5977. doi: 10.3934/dcds.2017258
[11]

Alexey Yulin, Alan Champneys. Snake-to-isola transition and moving solitons via symmetry-breaking in discrete optical cavities. Discrete & Continuous Dynamical Systems - S, 2011, 4 (5) : 1341-1357. doi: 10.3934/dcdss.2011.4.1341
[12]

Emma D'Aniello, Saber Elaydi. The structure of $ \omega $-limit sets of asymptotically non-autonomous discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 903-915. doi: 10.3934/dcdsb.2019195
[13]

Tomáš Roubíček. An energy-conserving time-discretisation scheme for poroelastic media with phase-field fracture emitting waves and heat. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 867-893. doi: 10.3934/dcdss.2017044
[14]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences