Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-12T21:27:31.134Z Has data issue: false hasContentIssue false
  • English
  • Français

The distribution of wasted spaces in the M/M/∞ queue with ranked servers

Part of:Markov processesAsymptotic theorySpecial processes

Published online by Cambridge University Press:  01 July 2016

Eunju Sohn and
Charles Knessl
Eunju Sohn*
Affiliation:
University of Illinois at Chicago
Charles Knessl*
Affiliation:
University of Illinois at Chicago
*
∗ Postal address: Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, 851 South Morgan (M/C 249), Chicago, IL 60607-7045, USA.
∗ Postal address: Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, 851 South Morgan (M/C 249), Chicago, IL 60607-7045, USA.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We consider the M/M/∞ queue with m primary servers and infinitely many secondary servers. All the servers are numbered and ordered. An arriving customer takes the lowest available server. We define the wasted spaces as the difference between the highest numbered occupied server and the total number of occupied servers. Letting ρ = λ0/μ be the ratio of arrival to service rates, we study the probability distribution of the wasted spaces asymptotically for ρ → ∞. We also give some numerical results and the tail behavior for ρ = O(1).

Keywords

Ranked serverasymptoticswasted spaces

MSC classification

Primary:60K25: Queueing theory
Secondary:34E10: Perturbations, asymptotics60J27: Continuous-time Markov processes on discrete state spaces

Information

Type
General Applied Probability
Information
Advances in Applied Probability , Volume 40 , Issue 3 , September 2008, pp. 835 - 855
Copyright
Copyright © Applied Probability Trust 2008 

Footnotes

∗∗∗∗

This work was partly supported by NSF grant DMS 05-03745.

References

Aldous, D. (1986). Some interesting processes arising as heavy traffic limits in an M/M/∞ storage process. Stoch. Process. Applic. 22, 291–313.CrossRefGoogle Scholar
Coffman, E. G. Jr. and Leighton, F. T. (1989). A provably efficient algorithm for dynamic storage allocation. J. Comput. Syst. Sci. 8, 2–35.CrossRefGoogle Scholar
Coffman, E. G. Jr. and Mitrani, I. (1988). Storage of single server queues. In Queueing Theory and Its Applications (CWI Monogr. 7), eds Boxma, O. J. and Syski, R., North-Holland, Amsterdam, pp. 193–205.Google Scholar
Coffman, E. G. Jr., Flatto, L. and Leighton, F. T. (1990). First fit allocation of queues: tight probabilistic bounds on wasted space. Stoch. Process. Applic. 36, 311–330.CrossRefGoogle Scholar
Coffman, E. G. Jr., Kadota, T. T. and Shepp, L. A. (1985). A stochastic model of fragmentation in dynamic storage allocation. SIAM J. Comput. 14, 416–425.CrossRefGoogle Scholar
Knessl, C. (2000). Asymptotic expansions for a stochastic model of queue storage. Ann. Appl. Prob. 10, 592–615.CrossRefGoogle Scholar
Knessl, C. (2004). Some asymptotic results for the M/M/∞ queue with ranked servers. Queueing Systems 47, 201–250.CrossRefGoogle Scholar
Kosten, L. (1937). Uber Sperrungswahrscheinlichkeiten bei Staffelschaltungen. Electra Nachrichten-Technik 14, 5–12.Google Scholar
Newell, G. F. (1984). The M/M/∞ Service System with Ranked Servers in Heavy Traffic. Springer, New York.CrossRefGoogle Scholar
Preater, J. (1997). A perpetuity and the M/M/∞ ranked server system. J. Appl. Prob. 34, 508–513.CrossRefGoogle Scholar
Sohn, E. and Knessl, C. (2008). A simple direct solution to a storage allocation model. Appl. Math. Lett. 21, 172–175.CrossRefGoogle Scholar