• Previous Article
    The inexact log-exponential regularization method for mathematical programs with vertical complementarity constraints
  • JIMO Home
  • This Issue
  • Next Article
    Multiserver retrial queue with setup time and its application to data centers
January  2019, 15(1): 37-58. doi: 10.3934/jimo.2018031

Delay characteristics in place-reservation queues with class-dependent service times

1. 

SMACS Research Group, Department TELIN, Ghent University, Sint-Pietersnieuwstraat 41, 9000 Gent, Belgium

2. 

Department of Industrial Systems Engineering and Product Design, Ghent University, Technologiepark 903, 9052 Zwijnaarde, Belgium

* Corresponding author: Sabine Wittevrongel

The reviewing process of this paper was handled by Yutaka Takahashi and Wuyi Yue

Received  March 2017 Revised  July 2017 Published  February 2018

This paper considers a discrete-time single-server infinite-capacity queue with two classes of packet arrivals, either delay-sensitive (class 1) or delay-tolerant (class 2), and a reservation-based priority scheduling mechanism. The objective is to provide a better quality of service to delay-sensitive packets at the cost of allowing higher delays for the best-effort packets. To this end, the scheduling mechanism makes use of an in-queue reserved place intended for future class-1 packet arrivals. A class-1 arrival takes the place of the reservation in the queue, after which a new reservation is created at the tail of the queue. Class-2 arrivals always take place at the tail of the queue. We study the delay characteristics for both packet classes under the assumption of a general independent packet arrival process. The service times of the packets are independent and have a general distribution that depends on the class of the packet. Closed-form expressions are obtained for the probability generating functions of the per-class delays. From this, moments and tail probabilities of the packet delays of both classes are derived. The results are illustrated by some numerical examples.

Citation: Sabine Wittevrongel, Bart Feyaerts, Herwig Bruneel, Stijn De Vuyst. Delay characteristics in place-reservation queues with class-dependent service times. Journal of Industrial & Management Optimization, 2019, 15 (1) : 37-58. doi: 10.3934/jimo.2018031
References:
[1]

J. Abate and W. Whitt, Numerical inversion of probability generating functions, Operations Research Letters, 12 (1992), 245-251.  doi: 10.1016/0167-6377(92)90050-D.  Google Scholar

[2]

H. Bruneel, Performance of discrete-time queueing systems, Computers & Operations Research, 20 (1993), 303-320.  doi: 10.1016/0305-0548(93)90006-5.  Google Scholar

[3]

H. Bruneel and B. G. Kim, Discrete-Time Models for Communication Systems Including ATM, Kluwer Academic Publishers, Boston, 1993. doi: 10.1007/978-1-4615-3130-2.  Google Scholar

[4]

S. De ClercqB. Steyaert and H. Bruneel, Delay analysis of a discrete-time multiclass slot-bound priority system, 4OR -A Quarterly Journal of Operations Research, 10 (2012), 67-79.  doi: 10.1007/s10288-011-0183-7.  Google Scholar

[5]

S. De ClercqB. SteyaertS. Wittevrongel and H. Bruneel, Analysis of a discrete-time queue with time-limited overtake priority, Annals of Operations Research, 238 (2016), 69-97.  doi: 10.1007/s10479-015-2000-8.  Google Scholar

[6]

S. De VuystS. Wittevrongel and H. Bruneel, Place reservation: Delay analysis of a novel scheduling mechanism, Computers & Operations Research, 35 (2008), 2447-2462.   Google Scholar

[7]

B. FeyaertsS. De VuystH. Bruneel and S. Wittevrongel, Delay analysis of a discrete-time GI-GI-1 queue with reservation-based priority scheduling, Stochastic Models, 32 (2016), 179-205.  doi: 10.1080/15326349.2015.1091739.  Google Scholar

[8]

B. Feyaerts, S. De Vuyst, S. Wittevrongel and H. Bruneel, Analysis of a discrete-time priority queue with place reservations and geometric service times, in Proceedings of the Summer Computer Simulation Conference, SCSC 2008/DASD (Edinburgh, June 16-18,2008), SCS, (2008), 140-147. Google Scholar

[9]

T. MaertensJ. Walraevens and H. Bruneel, Performance comparison of several priority schemes with priority jumps, Annals of Operations Research, 162 (2008), 109-125.  doi: 10.1007/s10479-008-0314-5.  Google Scholar

[10]

A. MelikovL. Ponomarenko and C. Kim, Approximate method for analysis of queuing models with jump priorities, Automation and Remote Control, 74 (2013), 62-75.  doi: 10.1134/S0005117913010062.  Google Scholar

[11]

S. Ndreca and B. Scoppola, Discrete time GI/Geom/1 queueing system with priority, European Journal of Operational Research, 189 (2008), 1403-1408.  doi: 10.1016/j.ejor.2007.02.056.  Google Scholar

[12]

H. Takagi, Queueing Analysis: A Foundation of Performance Evaluation, Volume 3: Discrete-Time Systems, North-Holland, Amsterdam, 1993.  Google Scholar

[13]

C.-K. ThamQ. Yao and Y. Jiang, A multi-class probabilistic priority scheduling discipline for differentiated services networks, Computer Communications, 25 (2002), 1487-1496.  doi: 10.1016/S0140-3664(02)00035-X.  Google Scholar

[14]

J. WalraevensB. Steyaert and H. Bruneel, Delay characteristics in discrete-time GI-G-1 queues with non-preemptive priority queueing discipline, Performance Evaluation, 50 (2002), 53-75.  doi: 10.1016/S0166-5316(02)00082-2.  Google Scholar

[15]

S. WittevrongelB. FeyaertsH. Bruneel and S. De Vuyst, Delay analysis of a queue with reservation-based scheduling and class-dependent service times, Stoch. Models, 32 (2016), 179-205.  doi: 10.1080/15326349.2015.1091739.  Google Scholar

show all references

References:
[1]

J. Abate and W. Whitt, Numerical inversion of probability generating functions, Operations Research Letters, 12 (1992), 245-251.  doi: 10.1016/0167-6377(92)90050-D.  Google Scholar

[2]

H. Bruneel, Performance of discrete-time queueing systems, Computers & Operations Research, 20 (1993), 303-320.  doi: 10.1016/0305-0548(93)90006-5.  Google Scholar

[3]

H. Bruneel and B. G. Kim, Discrete-Time Models for Communication Systems Including ATM, Kluwer Academic Publishers, Boston, 1993. doi: 10.1007/978-1-4615-3130-2.  Google Scholar

[4]

S. De ClercqB. Steyaert and H. Bruneel, Delay analysis of a discrete-time multiclass slot-bound priority system, 4OR -A Quarterly Journal of Operations Research, 10 (2012), 67-79.  doi: 10.1007/s10288-011-0183-7.  Google Scholar

[5]

S. De ClercqB. SteyaertS. Wittevrongel and H. Bruneel, Analysis of a discrete-time queue with time-limited overtake priority, Annals of Operations Research, 238 (2016), 69-97.  doi: 10.1007/s10479-015-2000-8.  Google Scholar

[6]

S. De VuystS. Wittevrongel and H. Bruneel, Place reservation: Delay analysis of a novel scheduling mechanism, Computers & Operations Research, 35 (2008), 2447-2462.   Google Scholar

[7]

B. FeyaertsS. De VuystH. Bruneel and S. Wittevrongel, Delay analysis of a discrete-time GI-GI-1 queue with reservation-based priority scheduling, Stochastic Models, 32 (2016), 179-205.  doi: 10.1080/15326349.2015.1091739.  Google Scholar

[8]

B. Feyaerts, S. De Vuyst, S. Wittevrongel and H. Bruneel, Analysis of a discrete-time priority queue with place reservations and geometric service times, in Proceedings of the Summer Computer Simulation Conference, SCSC 2008/DASD (Edinburgh, June 16-18,2008), SCS, (2008), 140-147. Google Scholar

[9]

T. MaertensJ. Walraevens and H. Bruneel, Performance comparison of several priority schemes with priority jumps, Annals of Operations Research, 162 (2008), 109-125.  doi: 10.1007/s10479-008-0314-5.  Google Scholar

[10]

A. MelikovL. Ponomarenko and C. Kim, Approximate method for analysis of queuing models with jump priorities, Automation and Remote Control, 74 (2013), 62-75.  doi: 10.1134/S0005117913010062.  Google Scholar

[11]

S. Ndreca and B. Scoppola, Discrete time GI/Geom/1 queueing system with priority, European Journal of Operational Research, 189 (2008), 1403-1408.  doi: 10.1016/j.ejor.2007.02.056.  Google Scholar

[12]

H. Takagi, Queueing Analysis: A Foundation of Performance Evaluation, Volume 3: Discrete-Time Systems, North-Holland, Amsterdam, 1993.  Google Scholar

[13]

C.-K. ThamQ. Yao and Y. Jiang, A multi-class probabilistic priority scheduling discipline for differentiated services networks, Computer Communications, 25 (2002), 1487-1496.  doi: 10.1016/S0140-3664(02)00035-X.  Google Scholar

[14]

J. WalraevensB. Steyaert and H. Bruneel, Delay characteristics in discrete-time GI-G-1 queues with non-preemptive priority queueing discipline, Performance Evaluation, 50 (2002), 53-75.  doi: 10.1016/S0166-5316(02)00082-2.  Google Scholar

[15]

S. WittevrongelB. FeyaertsH. Bruneel and S. De Vuyst, Delay analysis of a queue with reservation-based scheduling and class-dependent service times, Stoch. Models, 32 (2016), 179-205.  doi: 10.1080/15326349.2015.1091739.  Google Scholar

Figure 1.  Insertion of 4 packets arriving during the same slot under reservation-based scheduling
Figure 2.  Sample path of the queueing model
Figure 3.  An $M\times M$ switch with output buffers
Figure 4.  Mean packet delays versus load $\rho$, for $M = 16$, $\mu_1 = \mu_2 = 3$ and various values of $\alpha$
Figure 5.  Mean packet delays versus load $\rho$, for $M = 16$, $\mu_1 = 3$, $\mu_2 = 20$ and various values of $\alpha$
Figure 6.  Standard deviations of packet delays versus load $\rho$, for $M = 16$, $\mu_1 = 3$, $\mu_2 = 20$ and various values of $\alpha$
Figure 7.  Tail probabilities of the packet delays, for $M = 16$, $\rho = 0.8$, $\mu_1 = 3$, $\mu_2 = 20$ and various values of $\alpha$
Figure 8.  Tail probabilities of the packet delays, for $M = 16$, $\rho = 0.8$, $\alpha = 0.15$, $\mu_2 = 4$ and various values of $\mu_1$
Figure 9.  Tail probabilities of the packet delays, for $M = 16$, $\rho = 0.8$, $\alpha = 0.15$, $\mu_2 = 4$ and various values of $\mu_2$
Figure 10.  Mean packet delays versus the standard deviation of the class-1 service times $\sigma_1$, for $M = 16$, $\rho = 0.8$, $\mu_1 = \mu_2 = 3$ and various values of $\alpha$
Figure 11.  Mean packet delays versus the standard deviation of the class-2 service times $\sigma_2$, for $M = 16$, $\rho = 0.8$, $\mu_1 = \mu_2 = 3$ and various values of $\alpha$
Figure 12.  Mean values and standard deviations of packet delays versus traffic mix $\alpha$, for $M = 16$, $\rho = 0.8$, and $\mu_1 = \mu_2 = 3$
[1]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

Jianquan Li, Xin Xie, Dian Zhang, Jia Li, Xiaolin Lin. Qualitative analysis of a simple tumor-immune system with time delay of tumor action. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020341

[11]

Sujit Kumar Samanta, Rakesh Nandi. Analysis of $GI^{[X]}/D$-$MSP/1/\infty$ queue using $RG$-factorization. Journal of Industrial & Management Optimization, 2021, 17 (2) : 549-573. doi: 10.3934/jimo.2019123

[12]

Simone Göttlich, Elisa Iacomini, Thomas Jung. Properties of the LWR model with time delay. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020032

[13]

Nahed Naceur, Nour Eddine Alaa, Moez Khenissi, Jean R. Roche. Theoretical and numerical analysis of a class of quasilinear elliptic equations. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 723-743. doi: 10.3934/dcdss.2020354

[14]

Jean-Paul Chehab. Damping, stabilization, and numerical filtering for the modeling and the simulation of time dependent PDEs. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021002

[15]

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

[16]

Guihong Fan, Gail S. K. Wolkowicz. Chaotic dynamics in a simple predator-prey model with discrete delay. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 191-216. doi: 10.3934/dcdsb.2020263

[17]

Wenbin Lv, Qingyuan Wang. Global existence for a class of Keller-Segel models with signal-dependent motility and general logistic term. Evolution Equations & Control Theory, 2021, 10 (1) : 25-36. doi: 10.3934/eect.2020040

[18]

Matúš Tibenský, Angela Handlovičová. Convergence analysis of the discrete duality finite volume scheme for the regularised Heston model. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1181-1195. doi: 10.3934/dcdss.2020226

[19]

Soniya Singh, Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of second order impulsive systems with state-dependent delay in Banach spaces. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020103

[20]

Feifei Cheng, Ji Li. Geometric singular perturbation analysis of Degasperis-Procesi equation with distributed delay. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 967-985. doi: 10.3934/dcds.2020305

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (211)
  • HTML views (1395)
  • Cited by (0)

[Back to Top]