• 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 & 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

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.  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]

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]

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

[16]

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

[17]

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

[18]

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

[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

2020 Impact Factor: 1.801

Metrics

  • PDF downloads (272)
  • HTML views (1398)
  • Cited by (0)

[Back to Top]