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

DOI10.1239/AAP/1449859798MaRDI QIDQ2786425zbMATH OpenOpenAlexFDO

Authors A. B. Dieker, T. Suk

Publication date 12 February 2016

Published in Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.5347, https://projecteuclid.org/euclid.aap/1449859798

zbMATH Keywords

diffusion limitfluid limitmean fieldqueueing

Mathematics Subject Classification ID

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

Abstract: 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 $noinfty$. 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 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.

Recommendations

• Randomized scheduling algorithm for queueing networks
• scientific article; zbMATH DE number 1191591
• The hydrodynamic limit of a randomized load balancing network
• Buffer size requirements under longest queue first
• Sensitivity of mean-field fluctuations in Erlang loss models with randomized routing

Cites work

• Asymptotic independence of queues under randomized load balancing
• Decay of tails at equilibrium for FIFO join the shortest queue networks
• scientific article; zbMATH DE number 1631026 (Why is no real title available?)
• scientific article; zbMATH DE number 273338 (Why is no real title available?)
• Occupancy Distributions of Homogeneous Queueing Systems Under Opportunistic Scheduling
• On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models
• On the power of (even a little) resource pooling
• Performance evaluation of a production/inventory system with periodic review and endogenous lead times
• Queueing system with selection of the shortest of two queues: An asymptotic approach
• Strong approximation theorems for density dependent Markov chains

Cited in

(3)

• Power-of-d-Choices with Memory: Fluid Limit and Optimality
• Join the shortest queue with many servers. The heavy-traffic asymptotics
• Mean field approximations to a queueing system with threshold-based workload control scheme

This page was built for publication: Randomized longest-queue-first scheduling for large-scale buffered systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2786425)