A LOWER BOUND ON THE QUEUEING DELAY IN RESOURCE CONSTRAINED LOAD BALANCING

摘要

We consider the following distributed service model: jobs with unit mean, general distribution, and independent processing times arrive as a renewal process of rate lambda n, with 0 < lambda < 1, and are immediately dispatched to one of several queues associated with n identical servers with unit processing rate. We assume that the dispatching decisions are made by a central dispatcher endowed with a finite memory, and with the ability to exchange messages with the servers.