Performance Analysis of Two Priority Queuing Systems in Tandem

Author(s)
Faouzi Kamoun

ABSTRACT

In this paper, we consider a tandem of two head-of-line (HOL) non-preemptive priority queuing systems, each with a single server and a deterministic service-time. Two classes of traffic are considered, namely high priority and low priority traffic. By means of a generating function approach, we present a technique to derive closed-form expressions for the mean buffer occupancy at each node and mean delay. Finally, we illustrate our solution technique with some numerical examples, whereby we illustrate the starvation impact of the HOL priority scheduling discipline on the performance of the low-priority traffic stream. Our research highlights the important fact that the unfairness of the HOL priority scheduling becomes even more noticeable at the network level. Thus this priority mechanism should be used with caution.

In this paper, we consider a tandem of two head-of-line (HOL) non-preemptive priority queuing systems, each with a single server and a deterministic service-time. Two classes of traffic are considered, namely high priority and low priority traffic. By means of a generating function approach, we present a technique to derive closed-form expressions for the mean buffer occupancy at each node and mean delay. Finally, we illustrate our solution technique with some numerical examples, whereby we illustrate the starvation impact of the HOL priority scheduling discipline on the performance of the low-priority traffic stream. Our research highlights the important fact that the unfairness of the HOL priority scheduling becomes even more noticeable at the network level. Thus this priority mechanism should be used with caution.

Cite this paper

F. Kamoun, "Performance Analysis of Two Priority Queuing Systems in Tandem,"*American Journal of Operations Research*, Vol. 2 No. 4, 2012, pp. 509-518. doi: 10.4236/ajor.2012.24060.

F. Kamoun, "Performance Analysis of Two Priority Queuing Systems in Tandem,"

References

[1] A. Khamisy and M. Sidi, “Discrete-Time Priority Queues with Two-State Markov Modulated Arrivals,” Stochastic Models, Vol. 8, No.2, 1992, pp. 337-357. doi:10.1080/15326349208807228

[2] M. Sidiand and A. Segall, “Structured Priority Queuing Systems with Applications to Packet-Radio Networks,” Performance Evaluation, Vol. 3, No. 4, 1983, pp. 265- 275. doi:10.1016/0166-5316(83)90036-6

[3] T. Takine, B. Sengupta and T. Hasegawa, “An Analysis of a Discrete-Time Queue for Broadband ISDNwith Priorities among Traffic Classes,” IEEE Transactions on Communications, Vol. 42, No. 2-4, 1994, pp. 1837-1845. doi:10.1109/TCOMM.1994.582893

[4] T. Takine, “A NonpreemptivePriority MAP/G/1 Queue with Two Classes of Customers,” Journal of Operations Research Society of Japan, Vol. 39, No. 2, 1996, pp. 266- 290.

[5] J. Walraevens, B. Steyaertand H. Bruneel,” Performance Analysis of a Single-Server ATM Queue with a Priority Scheduling,” Computers and Operations Research, Vol. 30, No. 12, 2003, pp. 1807-1829. doi:10.1016/S0305-0548(02)00108-9

[6] J. Walraevens, D. Fiems and H. Bruneel, “Transient Analysis of a Discrete-Time Priority Queue,” Proceedings of the 12th International Conference on Analytical and Stochastic Modelling Techniques and Applications (ASMTA 2005), Riga, June 2005, pp. 17-24.

[7] K. Laevens and H. Bruneel, “Discrete-Time Multiserver Queues with Priorities,” Performance Evaluation, Vol. 33, No. 4, 1998, pp. 249-275. doi:10.1016/S0166-5316(98)00024-8

[8] J. Walraevens, D. Fiems, S. Wittevrongel and H. Bruneel, “Calculation of Output Characteristics of a Priority Queue through a Busy Period Analysis,” European Journal of Operational Research, Vol. 198, No.3, 2009, pp. 891-898. doi:10.1016/j.ejor.2008.11.018

[9] F. Kamoun, “Performance Analysis of a Non-Preemptive Priority Queuing System Subjected to a Correlated Markovian Interruption Process,” Computers and Operations Research, Vol. 35, No. 12, 2008, pp. 3969-3988. doi:10.1016/j.cor.2007.06.001

[10] J. Walraevens, D. Fiems and H. Bruneel, “The DiscreteTime Preemptive Repeat Identical Priority Queue,” Queuing Systems, Vol. 53, No. 4, 2006, pp. 231-243. doi:10.1007/s11134-006-7770-x

[11] R. Chipalkatti, J. F. Kurose and D. Towsley, “Scheduling Policies for Real-Time and Nonreal-Time Traffic Packet Switching Node,” Proceedings of the IEEE INFOCOM ’89, Ottawa, April 1998, pp. 774-783.

[12] B. I. Choi and Y. Lee, “Performance Analysis of a Dynamic Priority Queue for Traffic Control of Bursty Traffics in ATM Networks,” IEEE Proceedings of Communications, Vol. 148, No. 3, 2001, pp. 181-187. doi:10.1049/ip-com:20010115

[13] D. I. Choi, B. D. Choi and D. Sung, “Performance Analysis of Priority Leaky Bucket Scheme with QueueLength-Threshold Scheduling Policy,” IEE Proceedings of Communications, Vol. 145, No. 6, 1998, pp. 395-401. doi:10.1049/ip-com:19982287

[14] C. Knessl, D. I. Choi and C. Trier, “A Dynamic Priority Queue Model for Simultaneous Service of Voice and Data Traffic,” SIAM Journal on Applied Mathematics, Vol. 63, No. 2, 2002, pp. 398-422. doi:10.1137/S0036139901390842

[15] J. T. Lee and Y. H. Kim, “Performance Analysis of a Hybrid Priority Control Scheme for Input and Output Queuing ATM Switches,” Proceedings of INFOCOM ’98, San Francisco, 29 March-2 April 1998, pp.1470-1477. doi:10.1109/INFCOM.1998.662965

[16] T. Maertens, J. Walraevens and H. Bruneel, “Performance Analysis of a Single-Server Queue with HOL-PJ Priority Scheduling Discipline,” Proceedings of the Second International Working Conference on Performance Modelling and Evaluation of Heterogeneous Networks (HET- NETs ’04), Ilkley, 26-28 July 2004, pp. 1-10.

[17] T. Maertens, J. Walraevens and H. Bruneel, “On Priority Queues with Priority Jumps,” Performance Evaluation, Vol. 63, No. 12, 2006, pp. 1235-1252. doi:10.1016/j.peva.2005.12.003

[18] T. Maertens, J. Walraevens and H. Bruneel, “A Modified HOL Priority Scheduling Discipline: Performance Analysis,” European Journal of Operational Research, Vol. 180, No. 3, 2007, pp. 1168-1185. doi:10.1016/j.ejor.2006.05.004

[19] T. Maertens, J. Walraevens, M. Moeneclaey and H. Bruneel,” Performance Analysis of a Discrete-Time Queuing System with Priority Jumps,” International Journal of Electronics and Communications, Vol. 63, No. 10, 2009, pp. 853-858. doi:10.1016/j.aeue.2008.07.004

[20] S. De Vuyst, S. Wittevrongel, D. Fiems and H. Bruneel, “Controlling the Delay Trade-off Between Packet Flows UsingMultiple Reserved Places,” Performance Evaluation, Vol. 65, No. 6-7, 2008, pp. 484-511. doi:10.1016/j.peva.2007.12.008

[21] S. De Vuyst, D. Wittevrongel and H. Bruneel, “Place Reservation: Delay Analysis of a Novel Scheduling Mechanism,” Computers and Operations Research, Vol. 35, No. 8, 2008, pp. 2447-2462. doi:10.1016/j.cor.2006.12.003

[1] A. Khamisy and M. Sidi, “Discrete-Time Priority Queues with Two-State Markov Modulated Arrivals,” Stochastic Models, Vol. 8, No.2, 1992, pp. 337-357. doi:10.1080/15326349208807228

[2] M. Sidiand and A. Segall, “Structured Priority Queuing Systems with Applications to Packet-Radio Networks,” Performance Evaluation, Vol. 3, No. 4, 1983, pp. 265- 275. doi:10.1016/0166-5316(83)90036-6

[3] T. Takine, B. Sengupta and T. Hasegawa, “An Analysis of a Discrete-Time Queue for Broadband ISDNwith Priorities among Traffic Classes,” IEEE Transactions on Communications, Vol. 42, No. 2-4, 1994, pp. 1837-1845. doi:10.1109/TCOMM.1994.582893

[4] T. Takine, “A NonpreemptivePriority MAP/G/1 Queue with Two Classes of Customers,” Journal of Operations Research Society of Japan, Vol. 39, No. 2, 1996, pp. 266- 290.

[5] J. Walraevens, B. Steyaertand H. Bruneel,” Performance Analysis of a Single-Server ATM Queue with a Priority Scheduling,” Computers and Operations Research, Vol. 30, No. 12, 2003, pp. 1807-1829. doi:10.1016/S0305-0548(02)00108-9

[6] J. Walraevens, D. Fiems and H. Bruneel, “Transient Analysis of a Discrete-Time Priority Queue,” Proceedings of the 12th International Conference on Analytical and Stochastic Modelling Techniques and Applications (ASMTA 2005), Riga, June 2005, pp. 17-24.

[7] K. Laevens and H. Bruneel, “Discrete-Time Multiserver Queues with Priorities,” Performance Evaluation, Vol. 33, No. 4, 1998, pp. 249-275. doi:10.1016/S0166-5316(98)00024-8

[8] J. Walraevens, D. Fiems, S. Wittevrongel and H. Bruneel, “Calculation of Output Characteristics of a Priority Queue through a Busy Period Analysis,” European Journal of Operational Research, Vol. 198, No.3, 2009, pp. 891-898. doi:10.1016/j.ejor.2008.11.018

[9] F. Kamoun, “Performance Analysis of a Non-Preemptive Priority Queuing System Subjected to a Correlated Markovian Interruption Process,” Computers and Operations Research, Vol. 35, No. 12, 2008, pp. 3969-3988. doi:10.1016/j.cor.2007.06.001

[10] J. Walraevens, D. Fiems and H. Bruneel, “The DiscreteTime Preemptive Repeat Identical Priority Queue,” Queuing Systems, Vol. 53, No. 4, 2006, pp. 231-243. doi:10.1007/s11134-006-7770-x

[11] R. Chipalkatti, J. F. Kurose and D. Towsley, “Scheduling Policies for Real-Time and Nonreal-Time Traffic Packet Switching Node,” Proceedings of the IEEE INFOCOM ’89, Ottawa, April 1998, pp. 774-783.

[12] B. I. Choi and Y. Lee, “Performance Analysis of a Dynamic Priority Queue for Traffic Control of Bursty Traffics in ATM Networks,” IEEE Proceedings of Communications, Vol. 148, No. 3, 2001, pp. 181-187. doi:10.1049/ip-com:20010115

[13] D. I. Choi, B. D. Choi and D. Sung, “Performance Analysis of Priority Leaky Bucket Scheme with QueueLength-Threshold Scheduling Policy,” IEE Proceedings of Communications, Vol. 145, No. 6, 1998, pp. 395-401. doi:10.1049/ip-com:19982287

[14] C. Knessl, D. I. Choi and C. Trier, “A Dynamic Priority Queue Model for Simultaneous Service of Voice and Data Traffic,” SIAM Journal on Applied Mathematics, Vol. 63, No. 2, 2002, pp. 398-422. doi:10.1137/S0036139901390842

[15] J. T. Lee and Y. H. Kim, “Performance Analysis of a Hybrid Priority Control Scheme for Input and Output Queuing ATM Switches,” Proceedings of INFOCOM ’98, San Francisco, 29 March-2 April 1998, pp.1470-1477. doi:10.1109/INFCOM.1998.662965

[16] T. Maertens, J. Walraevens and H. Bruneel, “Performance Analysis of a Single-Server Queue with HOL-PJ Priority Scheduling Discipline,” Proceedings of the Second International Working Conference on Performance Modelling and Evaluation of Heterogeneous Networks (HET- NETs ’04), Ilkley, 26-28 July 2004, pp. 1-10.

[17] T. Maertens, J. Walraevens and H. Bruneel, “On Priority Queues with Priority Jumps,” Performance Evaluation, Vol. 63, No. 12, 2006, pp. 1235-1252. doi:10.1016/j.peva.2005.12.003

[18] T. Maertens, J. Walraevens and H. Bruneel, “A Modified HOL Priority Scheduling Discipline: Performance Analysis,” European Journal of Operational Research, Vol. 180, No. 3, 2007, pp. 1168-1185. doi:10.1016/j.ejor.2006.05.004

[19] T. Maertens, J. Walraevens, M. Moeneclaey and H. Bruneel,” Performance Analysis of a Discrete-Time Queuing System with Priority Jumps,” International Journal of Electronics and Communications, Vol. 63, No. 10, 2009, pp. 853-858. doi:10.1016/j.aeue.2008.07.004

[20] S. De Vuyst, S. Wittevrongel, D. Fiems and H. Bruneel, “Controlling the Delay Trade-off Between Packet Flows UsingMultiple Reserved Places,” Performance Evaluation, Vol. 65, No. 6-7, 2008, pp. 484-511. doi:10.1016/j.peva.2007.12.008

[21] S. De Vuyst, D. Wittevrongel and H. Bruneel, “Place Reservation: Delay Analysis of a Novel Scheduling Mechanism,” Computers and Operations Research, Vol. 35, No. 8, 2008, pp. 2447-2462. doi:10.1016/j.cor.2006.12.003