Subdiffusive Load Balancing in Time-Varying Queueing Systems

• 成果类型: Article
• 署名作者: Atar, Rami; Keslassy, Isaac; Mendelson, Gal
• 署名单位: Technion Israel Institute of Technology
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2019.1851
• 发表日期: 2019
• 页码: 1678-1698
• 关键词: 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

摘要

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 ofd 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.