• Previous Article
    Multiserver retrial queue with setup time and its application to data centers
  • JIMO Home
  • This Issue
  • Next Article
    The inexact log-exponential regularization method for mathematical programs with vertical complementarity constraints
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.

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

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

[6]

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

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

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

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

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

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

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

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

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

[6]

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

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

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

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

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

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

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

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, 2018, 13 (5) : 1-26. doi: 10.3934/jimo.2018102

[6]

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

[7]

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

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

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

[10]

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

[11]

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

[12]

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, 2018, 13 (5) : 1-15. doi: 10.3934/jimo.2018088

[13]

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

[14]

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

[15]

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

[16]

Pikkala Vijaya Laxmi, Obsie Mussa Yesuf. Analysis of a finite buffer general input queue with Markovian service process and accessible and non-accessible batch service. Journal of Industrial & Management Optimization, 2010, 6 (4) : 929-944. doi: 10.3934/jimo.2010.6.929

[17]

Huan Su, Pengfei Wang, Xiaohua Ding. Stability analysis for discrete-time coupled systems with multi-diffusion by graph-theoretic approach and its application. Discrete & Continuous Dynamical Systems - B, 2016, 21 (1) : 253-269. doi: 10.3934/dcdsb.2016.21.253

[18]

Shaojun Lan, Yinghui Tang, Miaomiao Yu. System capacity optimization design and optimal threshold $N^{*}$ for a $GEO/G/1$ discrete-time queue with single server vacation and under the control of Min($N, V$)-policy. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1435-1464. doi: 10.3934/jimo.2016.12.1435

[19]

Hideaki Takagi. Times until service completion and abandonment in an M/M/$ m$ preemptive-resume LCFS queue with impatient customers. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1701-1726. doi: 10.3934/jimo.2018028

[20]

Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial & Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (82)
  • HTML views (645)
  • Cited by (0)

[Back to Top]