Interacting queues in heavy traffic

摘要

We consider a system of parallel queues with Poisson arrivals and exponentially distributed service requirements. The various queues are coupled through their service rates, causing a complex dynamic interaction. Specifically, the system consists of one primary queue and several secondary queues whose service rates depend on whether the primary queue is empty or not. Conversely, the service rate of the primary queue depends on which of the secondary queues are empty.rnAn important special case arises when the service rates satisfy a specific relationship so that the various queues form a work-conserving system. This case is, in fact, equivalent to a so-called Generalized Processor Sharing (GPS) system. GPS-based scheduling algorithms have emerged as popular mechanisms for achieving service differentiation while providing statistical multiplexing gains.rnWe consider a heavy-traffic scenario, and assume that each of the secondary queues is underloaded when the primary queue is busy. Using a perturbation procedure, we derive the lowest-order asymptotic approximation to the joint stationary distribution of the queue lengths, in terms of a small positive parameter measuring the closeness of the system to instability. Heuristic derivations of these results are presented.rnWe also pursue two extensions: (ⅰ) the more general work-conserving case where the service rate of a secondary queue may depend on its own length, and is a slowly varying function of the length of the primary queue; and (ⅱ) the non-work-conserving case where the service rate of a secondary queue may depend on its own length, but not on the length of the primary queue.