The Drift Method for Heavy Traffic Limits, with Applications in Data Centers and Networks

摘要

Heavy traffic limits of queueing systems have been studied in the literature using fluid and diffusion limits. Recently, a new method called the 'Drift Method' has been developed to study these limits. In the drift method, a function of the queue lengths is picked and its drift is set to zero in steady-state, to obtain bounds on the steady-state queue lengths that are tight in the heavy-traffic limit. The key is to establish an appropriate notion of state-space collapse in terms of steady-state moments of weighted queue length differences, and use this state-space collapse result when setting the drift equal to zero. These moment bounds involved in state space collapse are also obtained by drift arguments similar to the well-known Foster-Lyapunov theorem. We will apply the methodology to study routing, scheduling, and other resource allocation problems that arise in data centers and cloud computing systems.