Job Dispatching Policies for Queueing Systems with Unknown Service Rates
Job Dispatching Policies for Queueing Systems with Unknown Service Rates
复制标题
DOI：
10.1145/3466772.3467047
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Tuhinangshu Choudhury;Gauri Joshi;Weina Wang;S. Shakkottai
中科院分区：
文献类型：
--
作者：
Tuhinangshu Choudhury;Gauri Joshi;Weina Wang;S. Shakkottai
在多服务器排队系统中，没有一个中央队列来存放所有的输入作业，作业调度策略用于将输入作业分配到其中一个服务器的队列中。经典的作业调度策略，如加入最短队列和最短期望延迟假设服务器的服务率和队列长度是已知的调度。在这项工作中，我们解决的问题，没有知识的服务率和队列长度的调度，调度员只能通过观察工作离开噪声估计的服务率。这个问题提出了一种新的探索剥削之间的权衡发送作业到所有的服务器，以估计其服务率，并利用目前已知的最快的服务器，以最大限度地减少预期的等待延迟。我们提出了一个基于土匪的勘探政策，学习服务率从观察到的工作离职。不同于标准的多臂强盗问题，只有一个出一个有限的行动是最佳的，这里的最优策略需要确定的最佳比例传入的工作发送到每个服务器。我们提出了一个遗憾的分析和模拟，以证明所提出的基于土匪的勘探政策的有效性。
In multi-server queueing systems where there is no central queue holding all incoming jobs, job dispatching policies are used to assign incoming jobs to the queue at one of the servers. Classic job dispatching policies such as join-the-shortest-queue and shortest expected delay assume that the service rates and queue lengths of the servers are known to the dispatcher. In this work, we tackle the problem of job dispatching without the knowledge of service rates and queue lengths, where the dispatcher can only obtain noisy estimates of the service rates by observing job departures. This problem presents a novel exploration-exploitation trade-off between sending jobs to all the servers to estimate their service rates, and exploiting the currently known fastest servers to minimize the expected queueing delay. We propose a bandit-based exploration policy that learns the service rates from observed job departures. Unlike the standard multi-armed bandit problem where only one out of a finite set of actions is optimal, here the optimal policy requires identifying the optimal fraction of incoming jobs to be sent to each server. We present a regret analysis and simulations to demonstrate the effectiveness of the proposed bandit-based exploration policy.