Partially shared buffers with full or mixed priority

Previous Article
Stability of a retrial queueing network with different classes of customers and restricted resource pooling
JIMO Home
This Issue
Next Article
Performance evaluation of a power saving mechanism in IEEE 802.16 wireless MANs with bi-directional traffic

July 2011, 7(3): 735-751. doi: 10.3934/jimo.2011.7.735

Partially shared buffers with full or mixed priority

Thomas Demoor ^1, , Dieter Fiems ^1, , Joris Walraevens ^1, and Herwig Bruneel ^1,

1.	Department of Telecommunications and Information Processing, Ghent University, St-Pietersnieuwstraat 41, 9000 Gent

Received September 2010 Revised January 2011 Published June 2011

Abstract
Related Papers
Under a Creative Commons license

This paper studies a finite-sized discrete-time two-class priority queue. Packets of both classes arrive according to a two-class discrete batch Markovian arrival process (2-DBMAP), taking into account the correlated nature of arrivals in heterogeneous telecommunication networks. The model incorporates time and space priority to provide different types of service to each class. One of both classes receives absolute time priority in order to minimize its delay. Space priority is implemented by the partial buffer sharing acceptance policy and can be provided to the class receiving time priority or to the other class. This choice gives rise to two different queueing models and this paper analyses both these models in a unified manner. Furthermore, the buffer finiteness and the use of space priority raise some issues on the order of arrivals in a slot. This paper does not assume that all arrivals from one class enter the queue before those of the other class. Instead, a string representation for sequences of arriving packets and a probability measure on the set of such strings are introduced. This naturally gives rise to the notion of intra-slot space priority. Performance of these queueing systems is then determined using matrix-analytic techniques. The numerical examples explore the range of service differentiation covered by both models.

Keywords: Queueing theory, space priority, partial buffer sharing, time priority, matrix analytic method..

Mathematics Subject Classification: Primary: 60J10, 60K25; Secondary: 68M1.

Citation: Thomas Demoor, Dieter Fiems, Joris Walraevens, Herwig Bruneel. Partially shared buffers with full or mixed priority. Journal of Industrial and Management Optimization, 2011, 7 (3) : 735-751. doi: 10.3934/jimo.2011.7.735

References:

[1]	C. Blondia and O. Casals, Statistical multiplexing of VBR sources: A matrix-analytic approach, Performance Evaluation, 16 (1992), 5-20. doi: 10.1016/0166-5316(92)90064-N.
[2]	T. Demoor, J. Walraevens, D. Fiems, S. De Vuyst and H. Bruneel, Influence of real-time queue capacity on system contents in DiffServ's expedited forwarding per-hop-behavior, Journal of Industrial and Management Optimization, 6 (2010), 587-602. doi: 10.3934/jimo.2010.6.587.
[3]	T. Demoor, D. Fiems, J. Walraevens and H. Bruneel, Time and space priority in a partially shared priority queue, in "Proceedings of the 5th International Conference on Queueing Theory and Network Applications," ACM, (2010), pp. 120.
[4]	D. Fiems and H. Bruneel, A note on the discretization of Little's result, Operations Research Letters, 30 (2002), 17-18. doi: 10.1016/S0167-6377(01)00112-2.
[5]	D. Fiems, J. Walraevens and H. Bruneel, Performance of a partially shared priority buffer with correlated arrivals, Lecture Notes in Computer Science, 4516 (2007), 582-593. doi: 10.1007/978-3-540-72990-7_52.
[6]	G. Hwang and B. Choi, Performance analysis of the $DAR(1)$/$D$/$c$ priority queue under partial buffer sharing policy, Computers & Operations Research, 31 (2004), 2231-2247. doi: 10.1016/S0305-0548(03)00175-8.
[7]	H. Kröner, G. Hébuterne, P. Boyer and A. Gravey, Priority management in ATM switching nodes, IEEE Journal on Selected Areas in Communications, 9 (1991), 418-427. doi: 10.1109/49.76641.
[8]	K. Laevens and H. Bruneel, Discrete-time multiserver queues with priorities, Performance Evaluation, 33 (1998), 249-275. doi: 10.1016/S0166-5316(98)00024-8.
[9]	G. Latouche and V. Ramaswami, "Introduction to Matrix Analytic Methods in Stochastic Modeling," Series on Statistics and Applied Probability. ASA-SIAM, Philadelphia, PA, American Statistical Association, Alexandria, VA, 1999.
[10]	M. Mehmet Ali and X. Song, A performance analysis of a discrete-time priority queueing system with correlated arrivals, Performance Evaluation, 57 (2004), 307-339. doi: 10.1016/j.peva.2004.01.001.
[11]	H. Radha, Y.Chen, K. Parthasarathy and R. Cohen, Scalable internet video using MPEG-4, Signal Processing: Image Communication, 15 (1999), 95-126. doi: 10.1016/S0923-5965(99)00026-0.
[12]	K. Spaey, "Superposition of Markovian Traffic Sources and Frame Aware Buffer Acceptance," Ph.D. thesis, Universitaire Instelling Antwerpen, 2002.
[13]	T. Takine, B. Sengupta and T. Hasegawa, An analysis of a discrete-time queue for broadband ISDN with priorities among traffic classes, IEEE Transactions on Communications, 42 (1994), 1837-1845. doi: 10.1109/TCOMM.1994.582893.
[14]	J. Van Velthoven, B. Van Houdt and C. Blondia, The impact of buffer finiteness on the loss rate in a priority queueing system, Lecture Notes in Computer Science, 4054 (2006), 211-225. doi: 10.1007/11777830_15.
[15]	J. Walraevens, B. Steyaert and H. Bruneel, Performance analysis of a single-server ATM queue with a priority scheduling, Computers & Operations Research, 30 (2003), 1807-1829. doi: 10.1016/S0305-0548(02)00108-9.
[16]	J. Walraevens, S. Wittevrongel and H. Bruneel, A discrete-time priority queue with train arrivals, Stochastic Models, 23 (2007), 489-512. doi: 10.1080/15326340701471158.
[17]	Y. Wang, C. Liu and C. Lu, Loss behavior in space priority queue with batch Markovian arrival process - discrete-time case, Performance Evaluation, 41 (2000), 269-293. doi: 10.1016/S0166-5316(99)00079-6.
[18]	Y. C. Wang, J. S. Wang and F. H. Tsai, Analysis of Discrete-Time Space Priority Queue with Fuzzy Threshold, Journal of Industrial and Management Optimization, 5 (2009), 467-479. doi: 10.3934/jimo.2009.5.467.
[19]	J. Zhao, B. Li, X. Cao and I. Ahmad, A matrix-analytic solution for the $DBMAP$/$PH$/$1$ priority queue, Queueing Systems, 53 (2006), 127-145. doi: 10.1007/s11134-006-8306-0.

show all references

References:

[1]	C. Blondia and O. Casals, Statistical multiplexing of VBR sources: A matrix-analytic approach, Performance Evaluation, 16 (1992), 5-20. doi: 10.1016/0166-5316(92)90064-N.
[2]	T. Demoor, J. Walraevens, D. Fiems, S. De Vuyst and H. Bruneel, Influence of real-time queue capacity on system contents in DiffServ's expedited forwarding per-hop-behavior, Journal of Industrial and Management Optimization, 6 (2010), 587-602. doi: 10.3934/jimo.2010.6.587.
[3]	T. Demoor, D. Fiems, J. Walraevens and H. Bruneel, Time and space priority in a partially shared priority queue, in "Proceedings of the 5th International Conference on Queueing Theory and Network Applications," ACM, (2010), pp. 120.
[4]	D. Fiems and H. Bruneel, A note on the discretization of Little's result, Operations Research Letters, 30 (2002), 17-18. doi: 10.1016/S0167-6377(01)00112-2.
[5]	D. Fiems, J. Walraevens and H. Bruneel, Performance of a partially shared priority buffer with correlated arrivals, Lecture Notes in Computer Science, 4516 (2007), 582-593. doi: 10.1007/978-3-540-72990-7_52.
[6]	G. Hwang and B. Choi, Performance analysis of the $DAR(1)$/$D$/$c$ priority queue under partial buffer sharing policy, Computers & Operations Research, 31 (2004), 2231-2247. doi: 10.1016/S0305-0548(03)00175-8.
[7]	H. Kröner, G. Hébuterne, P. Boyer and A. Gravey, Priority management in ATM switching nodes, IEEE Journal on Selected Areas in Communications, 9 (1991), 418-427. doi: 10.1109/49.76641.
[8]	K. Laevens and H. Bruneel, Discrete-time multiserver queues with priorities, Performance Evaluation, 33 (1998), 249-275. doi: 10.1016/S0166-5316(98)00024-8.
[9]	G. Latouche and V. Ramaswami, "Introduction to Matrix Analytic Methods in Stochastic Modeling," Series on Statistics and Applied Probability. ASA-SIAM, Philadelphia, PA, American Statistical Association, Alexandria, VA, 1999.
[10]	M. Mehmet Ali and X. Song, A performance analysis of a discrete-time priority queueing system with correlated arrivals, Performance Evaluation, 57 (2004), 307-339. doi: 10.1016/j.peva.2004.01.001.
[11]	H. Radha, Y.Chen, K. Parthasarathy and R. Cohen, Scalable internet video using MPEG-4, Signal Processing: Image Communication, 15 (1999), 95-126. doi: 10.1016/S0923-5965(99)00026-0.
[12]	K. Spaey, "Superposition of Markovian Traffic Sources and Frame Aware Buffer Acceptance," Ph.D. thesis, Universitaire Instelling Antwerpen, 2002.
[13]	T. Takine, B. Sengupta and T. Hasegawa, An analysis of a discrete-time queue for broadband ISDN with priorities among traffic classes, IEEE Transactions on Communications, 42 (1994), 1837-1845. doi: 10.1109/TCOMM.1994.582893.
[14]	J. Van Velthoven, B. Van Houdt and C. Blondia, The impact of buffer finiteness on the loss rate in a priority queueing system, Lecture Notes in Computer Science, 4054 (2006), 211-225. doi: 10.1007/11777830_15.
[15]	J. Walraevens, B. Steyaert and H. Bruneel, Performance analysis of a single-server ATM queue with a priority scheduling, Computers & Operations Research, 30 (2003), 1807-1829. doi: 10.1016/S0305-0548(02)00108-9.
[16]	J. Walraevens, S. Wittevrongel and H. Bruneel, A discrete-time priority queue with train arrivals, Stochastic Models, 23 (2007), 489-512. doi: 10.1080/15326340701471158.
[17]	Y. Wang, C. Liu and C. Lu, Loss behavior in space priority queue with batch Markovian arrival process - discrete-time case, Performance Evaluation, 41 (2000), 269-293. doi: 10.1016/S0166-5316(99)00079-6.
[18]	Y. C. Wang, J. S. Wang and F. H. Tsai, Analysis of Discrete-Time Space Priority Queue with Fuzzy Threshold, Journal of Industrial and Management Optimization, 5 (2009), 467-479. doi: 10.3934/jimo.2009.5.467.
[19]	J. Zhao, B. Li, X. Cao and I. Ahmad, A matrix-analytic solution for the $DBMAP$/$PH$/$1$ priority queue, Queueing Systems, 53 (2006), 127-145. doi: 10.1007/s11134-006-8306-0.

[1]	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
[2]	Yoshiaki Kawase, Shoji Kasahara. Priority queueing analysis of transaction-confirmation time for Bitcoin. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1077-1098. doi: 10.3934/jimo.2018193
[3]	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
[4]	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
[5]	Raina Raj, Vidyottama Jain. Optimization of traffic control in $ MMAP\mathit{[2]}/PH\mathit{[2]}/S$ priority queueing model with $ PH $ retrial times and the preemptive repeat policy. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022044
[6]	Alessia Marigo. Optimal traffic distribution and priority coefficients for telecommunication networks. Networks and Heterogeneous Media, 2006, 1 (2) : 315-336. doi: 10.3934/nhm.2006.1.315
[7]	Tom Maertens, Joris Walraevens, Herwig Bruneel. Controlling delay differentiation with priority jumps: Analytical study. Numerical Algebra, Control and Optimization, 2011, 1 (4) : 657-673. doi: 10.3934/naco.2011.1.657
[8]	David Blázquez-Sanz, Juan J. Morales-Ruiz. Lie's reduction method and differential Galois theory in the complex analytic context. Discrete and Continuous Dynamical Systems, 2012, 32 (2) : 353-379. doi: 10.3934/dcds.2012.32.353
[9]	Gang Chen, Zaiming Liu, Jinbiao Wu. Optimal threshold control of a retrial queueing system with finite buffer. Journal of Industrial and Management Optimization, 2017, 13 (3) : 1537-1552. doi: 10.3934/jimo.2017006
[10]	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
[11]	Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391
[12]	Dhanya Shajin, A. N. Dudin, Olga Dudina, A. Krishnamoorthy. A two-priority single server retrial queue with additional items. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2891-2912. doi: 10.3934/jimo.2019085
[13]	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
[14]	Biao Xu, Xiuli Xu, Zhong Yao. Equilibrium and optimal balking strategies for low-priority customers in the M/G/1 queue with two classes of customers and preemptive priority. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1599-1615. doi: 10.3934/jimo.2018113
[15]	Giovanni Russo, Fabian Wirth. Matrix measures, stability and contraction theory for dynamical systems on time scales. Discrete and Continuous Dynamical Systems - B, 2022, 27 (6) : 3345-3374. doi: 10.3934/dcdsb.2021188
[16]	Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control and Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115
[17]	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
[18]	Yuan Zhao, Wuyi Yue. Cognitive radio networks with multiple secondary users under two kinds of priority schemes: Performance comparison and optimization. Journal of Industrial and Management Optimization, 2017, 13 (3) : 1449-1466. doi: 10.3934/jimo.2017001
[19]	David Grant, Mahesh K. Varanasi. Duality theory for space-time codes over finite fields. Advances in Mathematics of Communications, 2008, 2 (1) : 35-54. doi: 10.3934/amc.2008.2.35
[20]	Kyeong-Hun Kim, Kijung Lee. A weighted $L_p$-theory for second-order parabolic and elliptic partial differential systems on a half space. Communications on Pure and Applied Analysis, 2016, 15 (3) : 761-794. doi: 10.3934/cpaa.2016.15.761

2021 Impact Factor: 1.411

Tools

Metrics

Other articles
by authors

on AIMS
Thomas Demoor Dieter Fiems Joris Walraevens Herwig Bruneel
on Google Scholar
Thomas Demoor Dieter Fiems Joris Walraevens Herwig Bruneel

[Back to Top]