On the Finite Capacity Shortest Queue Problem

Charles Knessl, Haishen Yao

Abstract


We consider two parallel queues. There is one server tending to each queue and the capacity of each queue is K. The network is fed by a single Poisson arrival stream of rate λ, and the two servers are identical exponential servers working at rate µ. A new arrival is routed to the queue with the smaller number of customers. If both have the same number of customers then the arrival is routed randomly, with the probability of joining either queue being 1/2. If there are more than 2K customers in the system, further arrivals are turned away and lost. We let ρ = λ/µ and take K →∞, and consider the cases ρ< 2, ρ> 2 and ρ − 2 = O(K−1). We shall obtain asymptotic approximations to the joint steady state distribution of finding m customers in the first queue and n in the second. The asymptotic approximations are shown to be quite accurate numerically. We shall identify precisely for what ranges of m and n can the finite capacity model be approximated by the infinite capacity one. We will also show that the marginal distribution of finding n customers in the second queue undergoes a transition when ρ = 4.

Key words: Shortest queue problem; Finite capacity; Poisson arrival stream; Analytical approximations

Keywords


Shortest queue problem; Finite capacity; Poisson arrival stream; Analytical approximations

Full Text:

PDF

References


Foschini, G. (1977). On Heavy Traffic Diffusion Analysis and Dynamic Routing in Packet Switched Networks. In K. Chandy, & J. Reiser (Eds.), Computer Performance, (pp. 499–513). New York: North-Holland.

Foschini, G., & Salz, J. (1978). A Basic Dynamic Routing Problem and Diffusion. IEEE (Trans.) Commun., 26(3), 320–327.

Gertsbakh, I. (1984). The Shorter Queue Problem: A Numerical Study Using the Matrix-geometric Solution. Eur. J. Oper. Res., 15 (3), 374–381.

Flatto, L., & McKean, H. (1977). Two Queues in Parallel. Commun. Pure Appl. Math., 30(2), 255–

Kingman, J. F. C. (1961). Two Similar Queues in Parallel. Annals Math. Statist., 32(4), 1314–1323.

Halfin, S. (1985). The Shortest Queue Problem. J. Appl. Probab., 22(4), 865–878.

Adan, I. J. B. F., Wessels, J., & Zijm, W. H. M. (1990). Analysis of the Symmetric Shortest Queue Problem. Comm. Statist. Stochastic Models, 6(4), 691–713.

Adan, I. J. B. F.,Wessels, J., & Zijm, W. H. M. (1991). Analysis of the Asymmetric Shortest Queue Problem. Queueing Systems Theory Appl., 8(1), 1–58.

Adan, I. J. B. F., J. van Houtum, G., & Van der Wal, J. (1994). Upper and Lower Bounds for the Waiting Time in the Symmetric Shortest Queue Problem. Ann. Oper. Res., 48(2), 197–217.

Wang, P. P. (2000). Workload Distribution of Discrete Time Parallel Queues with Two Servers. Naval Res. Logist., 47(5), 440–454.

Wu, P., & Posner, M. J. M. (1997). A Level-crossing Approach to the Solution of the Shortest Queue Problem. Oper. Res. Lett., 21(4), 181–189.

J. van Houtum, G., Adan, I. J. B. F., Wessels, J., & Zijm, W. H. M. (2001). Performance Analysis of Parallel Identical Machines with a Generalized Shortest Queue Arrival Mechanism. OR Spektrum, 23(3), 411–427.

Zhao, Y. Q., & Grassman, W. K. (1990). The Shortest Queue Model with Jockeying. Naval Res. Logist., 37(5), 773–787.

Adan, I. J. B. F., Wessels, J., & Zijm, W. H. M. (1991). Analysis of the Symmetric Shortest Queue Problem with Threshold Jockeying. Comm. Statist. Stochastic Models, 7(4), 615–627.

Adan, I. J. B. F., Wessels, J., & Zijm, W. H. M. (1993). Matrix-geometric Analysis of the Shortest Queue Problem with Threshold Jockeying. Oper. Res. Lett., 13(2), 107–112.

Conolly, B. W. (1984). The Autostrada Queueing Problems. J. Appl. Prob., 21(2), 394–403.

Tarabia, A. M. K. (2008). Analysis of Two Queues in Parallel with Jockeying and Restricted Capaci­ties. Appl. Math. Model., 32(5), 802–810.

Tarabia, A. M. K. (2009). Transient Analysis of Two Queues in Parallel with Jockeying. Stochastics: An International Journal of Probability and Stochastic Processes, 81(2), 129–145.

Flatto, L. (1989). The Longer Queue Problem. Probab. Eng. Inform. Sci., 3(4), 537–559.

Blanc, J. P. C. (1992). The Power-series Algorithm Applied to the Shortest-queue Model. Oper. Res., 40(1), 157–167.

Grassman, W. K. (1980). Transient and Steady State Results for Two Parallel Queues. Omega Int. J. Manag. Sci., 8(1), 105–112.

Hooghiemstra, G., Keane, M., & Van de Rhee, S. (1988). Power-series for Stationary Distributions of Coupled Processor Models. SIAM J. Appl. Math., 48(5), 1159–1166.

Rieman, M. (1984). Some Diffusion Approximations with State Space Collapse. In A. V. Balakreshnan & M. Thomas (Eds.), Modelling and Performance Evaluation Methodology, (pp. 209–240). Berlin: Springer-Verlag.

Fleming, P. J., & Simon, B. (1999). Heavy Traffic Approximations for a System of Infinite Servers with Load Balancing. Probab. Eng. Inform. Sci., 13(3), 251–273.

Turner, S. R. E. (2000). A Join the Shorter Queue in Heavy Traffic. J. Appl. Probab., 37(1), 212–223.

Sakuma, Y, Miyazawa, M., & Zhao, Y. Q. (2006). Decay Rates for PH/M/2 Queue with Shortest Queue Discipline. Queueing Systems, 53(4), 189–201.

Kurkova, I. A., & Suhov, Y. M. (2003). Malyshev’s Theory and JS-queues: Asymptotics of Stationary Probabilities. Ann. Appl. Probab., 13(4), 1313–1354.

McDonald, D. (1996). Overloading Parallel Servers when Arrivals Join the Shortest Queue. In P. Glasserman, K. Sigman & D. Yao (Eds.), Stochastic Networks: Stability and Rare Events, Lecture Notes in Statistics 117, (pp. 169–196). New York: Springer Verlag.

Alanyali, M., & Hajek, B. (1998). On Large Deviations in Load Sharing Networks. Ann. Appl. Probab., 8(1), 67–97.

Shwartz, A., & Weiss, A. (1995). Large Deviations for Performance Analysis, Queues, Communica­tions, and Computing, Stochastic Modeling Series. London: Chapman and Hall.

Yao, H., & Knessl, C. (2005). On the Infinite Server Shortest Queue Problem: Symmetric Case. Stochastic Models, 21(1), 101–132.

Yao, H., & Knessl, C. (2006). On the Infinite Server Shortest Queue Problem: Non-symmetric Case. Queueing Systems, 52(2), 157–177.

Yao, H., & Knessl, C. (2008). On the Shortest Queue Version of the Erlang Loss Model. Studies in Appl. Math., 120(2), 129–212.




DOI: http://dx.doi.org/10.3968/j.pam.1925252820110201.012

DOI (PDF): http://dx.doi.org/10.3968/g1786

Refbacks

  • There are currently no refbacks.


Copyright (c)



Share us to:   

Reminder

If you have already registered in Journal A and plan to submit article(s) to Journal B, please click the "CATEGORIES", or "JOURNALS A-Z" on the right side of the "HOME".


We only use the follwoing mailboxes to deal with issues about paper acceptance, payment and submission of electronic versions of our journals to databases:
pam@cscanada.org
pam@cscanada.net

 Articles published in Progress in Applied Mathematics are licensed under Creative Commons Attribution 4.0 (CC-BY).

 ROGRESS IN APPLIED MATHEMATICS Editorial Office

Address: 1055 Rue Lucien-L'Allier, Unit #772, Montreal, QC H3G 3C4, Canada.

Telephone: 1-514-558 6138
Http://www.cscanada.net
Http://www.cscanada.org
E-mail:office@cscanada.net office@cscanada.org caooc@hotmail.com

Copyright © 2010 Canadian Research & Development Center of Sciences and Cultures