# American Institute of Mathematical Sciences

• 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  January 2019 Early access  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 and 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. [2] H. Bruneel, Performance of discrete-time queueing systems, Computers & Operations Research, 20 (1993), 303-320.  doi: 10.1016/0305-0548(93)90006-5. [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. [4] S. De Clercq, B. 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. [5] S. De Clercq, B. Steyaert, S. 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. [6] S. De Vuyst, S. Wittevrongel and H. Bruneel, Place reservation: Delay analysis of a novel scheduling mechanism, Computers & Operations Research, 35 (2008), 2447-2462. [7] B. Feyaerts, S. De Vuyst, H. 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. [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. [9] T. Maertens, J. 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. [10] A. Melikov, L. 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. [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. [12] H. Takagi, Queueing Analysis: A Foundation of Performance Evaluation, Volume 3: Discrete-Time Systems, North-Holland, Amsterdam, 1993. [13] C.-K. Tham, Q. 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. [14] J. Walraevens, B. 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. [15] S. Wittevrongel, B. Feyaerts, H. 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.

show all references

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

##### 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. [2] H. Bruneel, Performance of discrete-time queueing systems, Computers & Operations Research, 20 (1993), 303-320.  doi: 10.1016/0305-0548(93)90006-5. [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. [4] S. De Clercq, B. 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. [5] S. De Clercq, B. Steyaert, S. 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. [6] S. De Vuyst, S. Wittevrongel and H. Bruneel, Place reservation: Delay analysis of a novel scheduling mechanism, Computers & Operations Research, 35 (2008), 2447-2462. [7] B. Feyaerts, S. De Vuyst, H. 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. [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. [9] T. Maertens, J. 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. [10] A. Melikov, L. 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. [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. [12] H. Takagi, Queueing Analysis: A Foundation of Performance Evaluation, Volume 3: Discrete-Time Systems, North-Holland, Amsterdam, 1993. [13] C.-K. Tham, Q. 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. [14] J. Walraevens, B. 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. [15] S. Wittevrongel, B. Feyaerts, H. 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.
Insertion of 4 packets arriving during the same slot under reservation-based scheduling
Sample path of the queueing model
An $M\times M$ switch with output buffers
Mean packet delays versus load $\rho$, for $M = 16$, $\mu_1 = \mu_2 = 3$ and various values of $\alpha$
Mean packet delays versus load $\rho$, for $M = 16$, $\mu_1 = 3$, $\mu_2 = 20$ and various values of $\alpha$
Standard deviations of packet delays versus load $\rho$, for $M = 16$, $\mu_1 = 3$, $\mu_2 = 20$ and various values of $\alpha$
Tail probabilities of the packet delays, for $M = 16$, $\rho = 0.8$, $\mu_1 = 3$, $\mu_2 = 20$ and various values of $\alpha$
Tail probabilities of the packet delays, for $M = 16$, $\rho = 0.8$, $\alpha = 0.15$, $\mu_2 = 4$ and various values of $\mu_1$
Tail probabilities of the packet delays, for $M = 16$, $\rho = 0.8$, $\alpha = 0.15$, $\mu_2 = 4$ and various values of $\mu_2$
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$
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$
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] Yung Chung Wang, Jenn Shing Wang, Fu Hsiang Tsai. Analysis of discrete-time space priority queue with fuzzy threshold. Journal of Industrial and Management Optimization, 2009, 5 (3) : 467-479. doi: 10.3934/jimo.2009.5.467 [2] Bart Feyaerts, Stijn De Vuyst, Herwig Bruneel, Sabine Wittevrongel. The impact of the $NT$-policy on the behaviour of a discrete-time queue with general service times. Journal of Industrial and Management Optimization, 2014, 10 (1) : 131-149. doi: 10.3934/jimo.2014.10.131 [3] Michiel De Muynck, Herwig Bruneel, Sabine Wittevrongel. Analysis of a discrete-time queue with general service demands and phase-type service capacities. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1901-1926. doi: 10.3934/jimo.2017024 [4] Sofian De Clercq, Koen De Turck, Bart Steyaert, Herwig Bruneel. Frame-bound priority scheduling in discrete-time queueing systems. Journal of Industrial and Management Optimization, 2011, 7 (3) : 767-788. doi: 10.3934/jimo.2011.7.767 [5] 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 and Management Optimization, 2019, 15 (3) : 1421-1446. doi: 10.3934/jimo.2018102 [6] Gopinath Panda, Veena Goswami. Effect of information on the strategic behavior of customers in a discrete-time bulk service queue. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1369-1388. doi: 10.3934/jimo.2019007 [7] Gábor Horváth, Zsolt Saffer, Miklós Telek. Queue length analysis of a Markov-modulated vacation queue with dependent arrival and service processes and exhaustive service policy. Journal of Industrial and Management Optimization, 2017, 13 (3) : 1365-1381. doi: 10.3934/jimo.2016077 [8] Bara Kim, Jeongsim Kim. Explicit solution for the stationary distribution of a discrete-time finite buffer queue. Journal of Industrial and Management Optimization, 2016, 12 (3) : 1121-1133. doi: 10.3934/jimo.2016.12.1121 [9] Chuandong Li, Fali Ma, Tingwen Huang. 2-D analysis based iterative learning control for linear discrete-time systems with time delay. Journal of Industrial and Management Optimization, 2011, 7 (1) : 175-181. doi: 10.3934/jimo.2011.7.175 [10] 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 and Management Optimization, 2020, 16 (3) : 1135-1148. doi: 10.3934/jimo.2018196 [11] 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 and Management Optimization, 2017, 13 (4) : 1945-1973. doi: 10.3934/jimo.2017026 [12] Arnaud Devos, Joris Walraevens, Tuan Phung-Duc, Herwig Bruneel. Analysis of the queue lengths in a priority retrial queue with constant retrial policy. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2813-2842. doi: 10.3934/jimo.2019082 [13] A. Azhagappan, T. Deepa. Transient analysis of N-policy queue with system disaster repair preventive maintenance re-service balking closedown and setup times. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2843-2856. doi: 10.3934/jimo.2019083 [14] Xiang Xie, Honglei Xu, Xinming Cheng, Yilun Yu. Improved results on exponential stability of discrete-time switched delay systems. Discrete and Continuous Dynamical Systems - B, 2017, 22 (1) : 199-208. doi: 10.3934/dcdsb.2017010 [15] Jianquan Li, Zhien Ma, Fred Brauer. Global analysis of discrete-time SI and SIS epidemic models. Mathematical Biosciences & Engineering, 2007, 4 (4) : 699-710. doi: 10.3934/mbe.2007.4.699 [16] Ping Yan, Ji-Bo Wang, Li-Qiang Zhao. Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088 [17] Shan Gao, Jinting Wang. On a discrete-time GI$^X$/Geo/1/N-G queue with randomized working vacations and at most $J$ vacations. Journal of Industrial and Management Optimization, 2015, 11 (3) : 779-806. doi: 10.3934/jimo.2015.11.779 [18] Ji-Bo Wang, Bo Zhang, Hongyu He. A unified analysis for scheduling problems with variable processing times. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1063-1077. doi: 10.3934/jimo.2021008 [19] Zsolt Saffer, Wuyi Yue. A dual tandem queueing system with GI service time at the first queue. Journal of Industrial and Management Optimization, 2014, 10 (1) : 167-192. doi: 10.3934/jimo.2014.10.167 [20] Pikkala Vijaya Laxmi, Singuluri Indira, Kanithi Jyothsna. Ant colony optimization for optimum service times in a Bernoulli schedule vacation interruption queue with balking and reneging. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1199-1214. doi: 10.3934/jimo.2016.12.1199

2021 Impact Factor: 1.411