Subdiffusive Load Balancing in Time-Varying Queueing Systems

Rami Atar (), Isaac Keslassy () and Gal Mendelson ()
Additional contact information
Rami Atar: The Viterbi Faculty of Electrical Engineering, Technion-Israel Institute of Technology, Haifa 32000, Israel
Isaac Keslassy: The Viterbi Faculty of Electrical Engineering, Technion-Israel Institute of Technology, Haifa 32000, Israel
Gal Mendelson: The Viterbi Faculty of Electrical Engineering, Technion-Israel Institute of Technology, Haifa 32000, Israel

Operations Research, 2019, vol. 67, issue 6, 1678-1698

Abstract: Load-balancing algorithms for systems that operate in heavy traffic are known to lead, under suitable conditions, to state space collapse (SSC). This term refers to the phenomenon whereby imbalance is negligible compared with queue lengths. Specifically, whereas queue lengths behave diffusively, the size of imbalance is at a subdiffusive scale: denoting by n the usual scaling parameter, the former and the latter are of order O ( n 1/2 ) and o ( n 1/2 ) , respectively. In this paper we consider load balancing for time-varying systems. SSC results and the standard techniques on which they are based do not apply to these systems, which (a) are not in heavy traffic, thus queue lengths may reach levels as high as O ( n ) , and (b) have time-varying traffic intensities that cause transitions between underloaded, critically loaded and overloaded regimes. Our results extend SSC far beyond the heavy traffic setting, by establishing subdiffusive [i.e., o ( n 1/2 ) ] balance for time-varying systems. To exhibit the breadth of the described phenomenon, the results address three load-balancing models. The first is the power of d choices [SQ( d )], where arrivals from a single stream are routed to the shortest among d randomly chosen queues, where 1 < d ≤ N and N denotes the fixed number of queues in the system. The second is redundancy-d [R( d )], where jobs are replicated d times and simultaneously routed to d randomly chosen queues. All, but the first, replica to be admitted into service are canceled. The third model is the longest queue first (LQF), where a single resource is shared by N job classes, and the job that receives service is always selected from the queue that is longest. As an application of these results, asymptotic optimality of SQ( d ) and R( d ) is shown, with an optimality guarantee of order o ( n 1/2 ) in the aforementioned framework, where, in particular, queue sizes may reach O ( n ) . Moreover, in the special case of the standard heavy traffic setting, the results are shown to yield new, explicit sufficient conditions for SSC.

Keywords: randomized load balancing; time-varying queues; join the shortest queue; longest queue first; power of choice; task redundancy; redundancy routing; job cancellations; diffusion limits; heavy traffic; state space collapse (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/opre.2019.1851 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:67:y:2019:i:6:p:1678-1698

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().