Sharp waiting-time bounds for multiserver jobs
Sharp waiting-time bounds for multiserver jobs
复制标题
DOI：
10.1145/3492866.3549717
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
Yige Hong;Weina Wang
中科院分区：
文献类型：
--
作者：
Yige Hong;Weina Wang
多服务器作业是指在服务期间同时占用多个服务器的作业，在当今的计算集群中非常普遍。但人们对具有多服务器作业的系统的延迟性能知之甚少。我们考虑了多服务器作业的排队模型，其中系统负载变得很重，同时系统中的服务器总数和作业所需的服务器数变得很大。前人的工作已经得到了在这种伸缩机制下排队概率的上界。然而，如果没有适当的下限，现有的结果就不能用来区分政策。本文通过对多服务器作业的平均等待时间建立严格的界来研究延迟性能，其中作业的等待时间是指排队时间而不是服务时间。我们首先考虑了常用的先到先服务(FCFS)策略，并刻画了它的平均等待时间的确切顺序。然后，我们证明了所有保单的平均等待时间的一个下界，并证明了这个下界与FCFS下的平均等待时间之间存在阶差。最后，我们用可达性结果来补充下界：我们证明了在我们称为P-优先级的优先策略下，平均等待时间达到了下界的顺序。这一可达性结果暗示了FCFS的下界的紧性、P-优先级的渐近最优性和严格次最优性。
Multiserver jobs, which are jobs that occupy multiple servers simultaneously during service, are prevalent in today's computing clusters. But little is known about the delay performance of systems with multiserver jobs. We consider queueing models for multiserver jobs in a scaling regime where the system load becomes heavy and meanwhile the total number of servers in the system and the number of servers that a job needs become large. Prior work has derived upper bounds on the queueing probability in this scaling regime. However, without proper lower bounds, the existing results cannot be used to differentiate between policies. In this paper, we study the delay performance by establishing sharp bounds on the mean waiting time of multiserver jobs, where the waiting time of a job is the time spent in queueing rather than in service. We first consider the commonly used First-Come-First-Serve (FCFS) policy and characterize the exact order of its mean waiting time. We then prove a lower bound on the mean waiting time of all policies, and demonstrate that there is an order gap between this lower bound and the mean waiting time under FCFS. We finally complement the lower bound with an achievability result: we show that under a priority policy that we call P-Priority, the mean waiting time achieves the order of the lower bound. This achievability result implies the tightness of the lower bound, the asymptotic optimality of P-Priority, and the strict suboptimality of FCFS.