Randomized longest-queue-first scheduling for large-scale buffered systems. (English) Zbl 1335.90015

Dieker, A. B.; Suk, T.

Adv. Appl. Probab. 47, No. 4, 1015-1038 (2015).

Summary: 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 \to \infty\). 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.

MSC:

90B22	Queues and service in operations research
90B36	Stochastic scheduling theory in operations research

Keywords:

queueing; mean field; fluid limit; diffusion limit

References:

[1]	Alanyali, M. and Dashouk, M. (2011). Occupancy distributions of homogeneous queueing systems under opportunistic scheduling. IEEE Trans. Inf. Theory 57 , 256-266. · Zbl 1366.94008
[2]	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.
[3]	Benaïm, M. and Le Boudec, J.-Y. (2008). A class of mean field interaction models for computer and communication systems. Performance Evaluation 65 , 823-838.
[4]	Bramson, M., Lu, Y. and Prabhakar, B. (2010). Randomized load balancing with general service time distributions. ACM SIGMETRICS Performance Eval. Rev. 38 , 275-286.
[5]	Bramson, M., Lu, Y. and Prabhakar, B. (2012). Asymptotic independence of queues under randomized load balancing. Queueing Systems 71 , 247-292. · Zbl 1275.60071
[6]	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. · Zbl 1287.60110
[7]	Braun, M. (1993). Differential Equations and Their Applications. An Introduction to Applied Mathematics , 4th edn. Springer, New York. · Zbl 0771.34001
[8]	Chen, H. and Yao, D. D. (2001). Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization . Springer, New York. · Zbl 0992.60003
[9]	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. · Zbl 0822.60083
[10]	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.
[11]	Kurtz, T. G. (1977/78). Strong approximation theorems for density dependent Markov chains. Stoch. Process. Appl. 6 , 223-240. · Zbl 0373.60085
[12]	Le Boudec, J.-Y., 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.
[13]	Mitzenmacher, M. D. (1996). The power of two choices in randomized load balancing. Doctoral thesis. University of California, Berkeley.
[14]	Tsitsiklis, J. N. and Xu, K. (2012). On the power of (even a little) resource pooling. Stoch. Systems 2 , 1-66. · Zbl 1296.60253
[15]	Van Houdt, B. (2013). Performance of garbage collection algorithms for flash-based solid state drives with hot/cold data. Performance Evaluation 70 , 692-703. · Zbl 1278.90129
[16]	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. · Zbl 0898.60095