Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-17T12:20:40.756Z Has data issue: false hasContentIssue false
  • English
  • Français

Randomized longest-queue-first scheduling for large-scale buffered systems

Part of: Operations research and management science

Published online by Cambridge University Press:  21 March 2016

A. B. Dieker  and
T. Suk
A. B. Dieker*
Affiliation:
Georgia Institute of Technology
T. Suk*
Affiliation:
Georgia Institute of Technology
*
∗ Postal address: H. Milton Stewart School of Industrial and System Engineering, Georgia Institute of Technology, 755 Ferst Drive, NW, Atlanta, GA 30332-0205, USA.
∗ Postal address: H. Milton Stewart School of Industrial and System Engineering, Georgia Institute of Technology, 755 Ferst Drive, NW, Atlanta, GA 30332-0205, 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 develop diffusion approximations for parallel-queueing systems with the randomized longest-queue-first scheduling (LQF) algorithm by establishing new mean-field limit theorems as the number of buffers n → ∞. We achieve this by allowing the number of sampled buffers d = d(n) to depend on the number of buffers n, which yields an asymptotic 'decoupling' of the queue length processes. We show through simulation experiments that the resulting approximation is accurate even for moderate values of n and d(n). To the best of the authors' knowledge, this is the first derivation of diffusion approximations for a queueing system in the large-buffer mean-field regime. Another noteworthy feature of our scaling idea is that the randomized LQF algorithm emulates the LQF algorithm, yet is computationally more attractive. The analysis of the system performance as a function of d(n) is facilitated by the multi-scale nature in our limit theorems: the various processes we study have different space scalings. This allows us to show the trade-off between performance and complexity of the randomized LQF scheduling algorithm.

Keywords

Queueingmean-fieldfluid limitdiffusion limit

MSC classification

Primary: 90B22: Queues and service
Secondary: 90B36: Scheduling theory, stochastic
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 47 , Issue 4 , December 2015 , pp. 1015 - 1038
Copyright
Copyright © Applied Probability Trust 2015 

References

Alanyali, M. and Dashouk, M. (2011). Occupancy distributions of homogeneous queueing systems under opportunistic scheduling. IEEE Trans. Inf. Theory 57, 256–266.Google Scholar
Bakhshi, R., Cloth, L., Fokkink, W. and Haverkort, B. (2011). Mean-field analysis for the evaluation of gossip protocols. In Quantitative Evaluation of Systems, IEEE, New York, pp. 247–256.Google Scholar
Benaïm, M. and Boudec, J.-Y. Le (2008). A class of mean field interaction models for computer and communication systems. Performance Evaluation 65, 823–838.Google Scholar
Bramson, M., Lu, Y. and Prabhakar, B. (2010). Randomized load balancing with general service time distributions. ACM SIGMETRICS Performance Eval. Rev. 38, 275–286.Google Scholar
Bramson, M., Lu, Y. and Prabhakar, B. (2012). Asymptotic independence of queues under randomized load balancing. Queueing Systems 71, 247–292.Google Scholar
Bramson, M., Lu, Y. and Prabhakar, B. (2013). Decay of tails at equilibrium for FIFO join the shortest queue networks. Ann. Appl. Prob. 23, 1841–1878.Google Scholar
Braun, M. (1993). Differential Equations and Their Applications. An Introduction to Applied Mathematics, 4th edn. Springer, New York.CrossRefGoogle Scholar
Chen, H. and Yao, D. D. (2001). Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization. Springer, New York.Google Scholar
Dai, J. G. (1995). On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models. Ann. Appl. Prob. 5, 49–77.Google Scholar
Gast, N. and Gaujal, B. (2010). A mean field model of work stealing in large-scale systems. ACM SIGMETRICS Performance Eval. Rev. 38, 13–24.Google Scholar
Kurtz, T. G. (1977/78). Strong approximation theorems for density dependent Markov chains. Stoch. Process. Appl. 6, 223–240.Google Scholar
Boudec, J.-Y. Le, McDonald, D. and Mundinger, J. (2007). A generic mean field convergence result for systems of interacting objects. In Proc. Fourth International Conference on the Quantitative Evaluation of Systems, pp. 3–18.Google Scholar
Mitzenmacher, M. D. (1996). The power of two choices in randomized load balancing. Doctoral thesis. University of California, Berkeley.Google Scholar
Tsitsiklis, J. N. and Xu, K. (2012). On the power of (even a little) resource pooling. Stoch. Systems 2, 1–66.Google Scholar
Van Houdt, B. (2013). Performance of garbage collection algorithms for flash-based solid state drives with hot/cold data. Performance Evaluation 70, 692–703.Google Scholar
Vvedenskaya, N. D., Dobrushin, R. L. and Karpelevich, F. I. (1996). A queueing system with a choice of the shorter of two queues—an asymptotic approach. Problems Inf. Transmission 32, 15–27.Google Scholar