Figure 1.
Insertion of 4 packets arriving during the same slot under reservation-based scheduling
-
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 |
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.
Keywords:
Discrete-time queue,
priority scheduling,
place reservation,
delay analysis,
class-dependent service times.
Mathematics Subject Classification:
Primary: 60K25, 90B22; Secondary: 68M20.
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. |
| [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. Google Scholar |
| [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. Google Scholar |
| [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
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. Google Scholar |
| [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. Google Scholar |
| [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. |
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] |
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 |
| [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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Management Optimization, 2021 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 & 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 & Management Optimization, 2016, 12 (4) : 1199-1214. doi: 10.3934/jimo.2016.12.1199 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]