Asymptotic Optimality of Balanced Routing
- 1 February 2012
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 60 (1), 163-179
- https://doi.org/10.1287/opre.1110.0998
Abstract
Consider a system with K parallel servers, each with its own waiting room. Upon arrival, a job is routed to the queue of one of the servers. Finding a routing policy that minimizes the total workload in the system is a known difficult problem in general. Even if the optimal policy is identified, the policy would require the full queue length information at the arrival of each job; for example, the join-the-shortest-queue policy (which is known to be optimal for identical servers with exponentially distributed service times) would require comparing the queue lengths of all the servers. In this paper, we consider a balanced routing policy that examines only a subset of c servers, with 1 ≤ c ≤ K: specifically, upon the arrival of a job, choose a subset of c servers with a probability proportional to their service rates, and then route the job to the one with the shortest queue among the c chosen servers. Under such a balanced policy, we derive the diffusion limits of the queue length processes and the workload processes. We note that the diffusion limits are the same for these processes regardless the choice of c, as long as c ≥ 2. We further show that the proposed balanced routing policy for any fixed c ≥ 2 is asymptotically optimal in the sense that it minimizes the workload over all time in the diffusion limit. In addition, the policy helps to distribute work among all the servers evenly.Keywords
This publication has 29 references indexed in Scilit:
- Analysis of join-the-shortest-queue routing for web server farmsPerformance Evaluation, 2007
- Some diffusion approximations with state space collapsePublished by Springer Science and Business Media LLC ,2005
- OPTIMAL ROUTING IN OUTPUT-QUEUED FLEXIBLE SERVER SYSTEMSProbability in the Engineering and Informational Sciences, 2005
- Heavy traffic analysis of open processing networks with complete resource pooling: Asymptotic optimality of discrete review policiesThe Annals of Applied Probability, 2005
- MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy trafficThe Annals of Applied Probability, 2004
- Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: asymptotic optimality of a threshold policyThe Annals of Applied Probability, 2001
- Heavy traffic limit theorems for a sequence of shortest queueing systemsQueueing Systems, 1995
- Dynamic routing in open queueing networks: Brownian models, cut constraints and resource poolingQueueing Systems, 1993
- Optimal control of a queueing system with two heterogeneous serversIEEE Transactions on Automatic Control, 1984
- Optimality of the shortest line disciplineJournal of Applied Probability, 1977