Asymptotic Optimality of Balanced Routing
Asymptotic Optimality of Balanced Routing
复制标题
DOI：
10.1287/opre.1110.0998
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Hong Chen;H. Ye
中科院分区：
文献类型：
--
作者：
Hong Chen;H. Ye
考虑一个有K台并行服务器的系统，每台服务器都有自己的等待室。在到达时，作业被路由到其中一个服务器的队列。寻找一个路由策略，最大限度地减少系统中的总工作量是一个已知的困难的问题。即使确定了最优策略，该策略也需要每个作业到达时的完整队列长度信息;例如，加入最短队列策略（已知对于具有指数分布服务时间的相同服务器是最优的）将需要比较所有服务器的队列长度。在本文中，我们考虑了一个平衡路由策略，只检查一个子集的c个服务器，1 ≤ c ≤ K：具体地说，在一个任务到达时，选择一个子集的c个服务器的概率成比例的服务率，然后路由到一个最短的队列中的c个选择的服务器。在这种平衡策略下，我们得到了队长过程和工作量过程的扩散极限。我们注意到，无论c的选择如何，只要c ≥ 2，这些过程的扩散极限都是相同的。我们进一步表明，建议的平衡路由策略为任何固定的c ≥ 2是渐近最优的意义上，它最大限度地减少工作量在所有时间的扩散限制。此外，该策略有助于在所有服务器之间均匀地分配工作。
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.