Subdiffusive Load Balancing in Time-Varying Queueing Systems

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.