Beyond mean-field limits for the analysis of large-scale networks

Excerpt

Mean-field approximations are ubiquitously used in the study of large-scale networks, including in the analysis of randomized load balancing algorithms. For concreteness, consider a network of n homogeneous servers, fed by independent streams of jobs with independent and identically distributed service times, subject to the well known join-the-shortest-of-two-queues or JSQ(2) algorithm in which each job arriving at a queue polls one other queue uniformly at random and joins the shorter of the two queues. Mean-field analyses of this system were first carried out in [14, 17] for exponential service distributions. Specifically, the dynamics of the empirical queue distribution (equivalently, the random fractions of queues with \(\ell \) or more jobs) were shown to converge, as \(n \rightarrow \infty \), to a deterministic limit characterized as the unique solution to a coupled system of ordinary differential equations (ODE), referred to as the hydrodynamic limit. Moreover, the long-time behavior of this ODE system was analyzed in [17] to show that JSQ(2) leads to a significant performance gain, with the equilibrium queue length exhibiting a doubly exponential tail decay in contrast to the exponential decay exhibited when just random routing is used, a phenomeon dubbed the “power of two choices”. …