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

We develop diffusion approximations for parallel-queueing systems with the randomized longest-queue-first scheduling 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 extremely accurate even for moderate values of n and d(n). To our knowledge, we are the first to derive diffusion approximations for a queueing system in the large-buffer mean-field regime. Another noteworthy feature of our scaling idea is that the randomized longest-queue-first algorithm emulates the longest-queue-first 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 longest-queue-first scheduling algorithm.