Home | Articles | Past volumes | About | Login | Notify | Contact | Search
 Stochastic Systems > Vol. 2 (2012) open journal systems 


On the power of (even a little) resource pooling

John N. Tsitsiklis, Massachusetts Institute of Technology
Kuang Xu, Massachusetts Institute of Technology


Abstract
We propose and analyze a multi-server model that captures a performance trade-off between centralized and distributed processing. In our model, a fraction p of an available resource is deployed in a centralized manner (e.g., to serve a most-loaded station) while the remaining fraction 1 ‒ p is allocated to local servers that can only serve requests addressed specifically to their respective stations.
Using a fluid model approach, we demonstrate a surprising phase transition in the steady-state delay scaling, as p changes: in the limit of a large number of stations, and when any amount of centralization is available (p > 0), the average queue length in steady state scales as $\log_{\frac{1}{1-p}}{\frac{1}{1-\lambda}}$ when the traffic intensity λ goes to 1. This is exponentially smaller than the usual M/M/1-queue delay scaling of $\frac{1}{1-\lambda}$, obtained when all resources are fully allocated to local stations (p = 0). This indicates a strong qualitative impact of even a small degree of resource pooling.
We prove convergence to a fluid limit, and characterize both the transient and steady-state behavior of the actual system, in the limit as the number of stations N goes to infinity. We show that the sequence of queue-length processes converges to a unique fluid trajectory (over any finite time interval, as N → ∞), and that this fluid trajectory converges to a unique invariant state vI, for which a simple closed-form expression is obtained. We also show that the steady-state distribution of the N-server system concentrates on vI as N goes to infinity.

AMS 2000 subject classifications: Primary 60K25; secondary 60K30, 60F17, 90B15, 90B22, 37C10.

Keywords: Queueing, service flexibility, resource pooling, asymptotics, fluid approximation.

Creative Common LOGO

Full Text: PDF
Tsitsiklis, John N., Xu, Kuang, On the power of (even a little) resource pooling, Stochastic Systems, 2, (2012), 1-66 (electronic). DOI: 10.1214/11-SSY033.

References

[1]    M. Bramson, State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Systems: Theory and Applications, 30: pp. 89–148, 1998. MR1663763

[2]    S. N. Ethier and T. G. Kurtz, Markov Processes: Characterization and Convergence (2nd edition). Wiley-Interscience, 2005. MR0838085

[3]    N. D. Vvedenskaya, R. L. Dobrushin, and F. I. Karpelevich, “Queueing system with selection of the shortest of two queues: An asymptotic approach,” Probl. Inf. Transm, 32(1): 20–34, 1996. MR1384927

[4]    M. Mitzenmacher, “The power of two choices in randomized load balancing,” Ph.D. thesis, U.C. Berkeley, 1996. MR2695522

[5]    M. Alanyali and M. Dashouk, “On power-of-choice in downlink transmission scheduling,” Inform. Theory and Applicat. Workshop, U.C. San Diego, 2008.

[6]    N. Gast and B. Gaujal, “Mean field limit of non-smooth systems and differential inclusions,” INRIA Research Report, 2010.

[7]    M. Bramson, Y. Lu, and B. Prabhakar, “Randomized load balancing with general service time distributions,” ACM Sigmetrics, New York, 2010.

[8]    M. Mitzenmacher, A. Richa, and R. Sitaraman, “The power of two random choices: A survey of techniques and results,” Handbook of Randomized Computing: Volume 1, 255–312, 2001. MR1966907

[9]    W. Jordan and S. C. Graves, “Principles on the benefits of manufacturing process flexibility,” Management Science, 41(4):577–594, 1995.

[10]    D. Simchi-Levi and Y. Wei, “Understanding the performance of the long chain and sparse designs in process flexibility,” submitted, 2011.

[11]    S. C. Graves and B. T. Tomlin, “Process flexibility in supply chains,” Management Science, 49:289–328, 2003.

[12]    S. Gurumurthi and S. Benjaafar, “Modeling and analysis of flexible queueing systems,” Management Science, 49:289–328, 2003. MR2071833

[13]    S. M. Iravani, M. P. Van Oyen, and K. T. Sims, “Structural flexibility: A new perspective on the design of manufacturing and service operations,” Management Science, 51(2):151–166, 2005.

[14]    R. Wallace and W. Whitt, “A staffing algorithm for call centers with skill-based routing,” Manufacturing and Service Operations Management, 7:276–294, 2005.

[15]    A. Mandelbaum and M. I. Reiman, “On pooling in queueing networks,” Management Science, 44(7):971-981, 1998.

[16]    J. M. Harrison and M. J. Lopez, “Heavy traffic resource pooling in parallel-server systems,” Queueing Systems, 33:39-368, 1999. MR1742575

[17]    S. L. Bell and R. J. Williams, “Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: asymptotic optimality of a threshold policy,” Ann. Appl. Probab., 11(3): 608-649, 2001. MR1865018

[18]    A. Mandelbaum and A. L. Stolyar, “Scheduling flexible servers with convex delay costs: Heavy-traffic optimality of the generalized cμ-rule,” Operations Research, 52(6):836-855, 2004. MR2104141

[19]    A. Bassamboo, R. S. Randhawa, and J. A. Van Mieghem, “A little flexibility is all you need: on the asymptotic value of flexible capacity in parallel queuing systems,” submitted, 2011.

[20]    G. J. Foschini and J. Salz, “A basic dynamic routing problem and diffusion,” IEEE Trans. on Comm. 26:320–327, 1978.

[21]    Y. T. He and D. G. Down, “On accommodating customer flexibility in service systems,” INFOR, 47(4): 289–295, 2009. MR2759824

[22]    V. Acary and B. Brogliato, Numerical Methods for Nonsmooth Dynamical Systems: Applications in Mechanics and Electronics, Springer Verlag, 2008.

[23]    L. Tassiulas and A. Ephremides, “Dynamic server allocation to parallel queues with randomly varying connectivity,” IEEE Trans. on Inform. Theory, 30: 466–478, 1993. MR1224342

[24]    J. R. Norris, Markov Chains, Cambridge University Press, 1997. MR1600720

[25]    S. Foss and T. Konstantopoulos, “An overview of some stochastic stability methods,” Journal of Operations Research Society of Japan, 47(4), 2004. MR2174067

[26]    D. Gamarnik and D. Goldberg, “Steady-state GI/GI/n queue in the Halfin-Whitt regime,” Submitted to the Annals of Applied Probability, 2011.

[27]    Borel-Cantelli Lemma, Wikipedia, http://en.wikipedia.org/wiki/Borel-Cantelli_lemma.

[28]    Gronwall’s Inequality, Wikipedia, http://en.wikipedia.org/wiki/Gronwall’s\_inequality.

[29]    K. Xu. On the power of centralization in distributed processing. S.M. thesis, MIT, 2011. http://arxiv.org/pdf/1203.5026v1.pdf.
Home | Articles | Past volumes | About | Login | Notify | Contact | Search

Stochastic Systems. ISSN: 1946-5238