Zero Queueing for Multi-Server Jobs
Zero Queueing for Multi-Server Jobs
复制标题
DOI：
10.1145/3447385
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Weina Wang;Qiaomin Xie;Mor Harchol-Balter
中科院分区：
文献类型：
--
作者：
Weina Wang;Qiaomin Xie;Mor Harchol-Balter
如今的云计算以多服务器作业为主。这些作业同时请求多个服务器并在作业期间保留所有这些服务器。多服务器作业给传统的每作业一台服务器模型增加了很多复杂性：到达的任务可能无法“适合”可用的服务器，并且可能必须排队，阻塞后来的到达并使服务器空闲。从排队的角度来看，我们对多服务器作业排队系统几乎一无所知；甚至理解确切的稳定区域也是一个非常困难的问题。在本文中，我们研究了系统中服务器数量增长的扩展机制下的多服务器作业排队模型。具体来说，我们考虑具有多个作业类别的系统，其中不同类别的作业可以请求不同数量的服务器并具有不同的服务时间分布，并且作业以先来先服务的顺序提供。多服务器作业模型开辟了新的扩展机制，其中作业所需的服务器数量和系统负载随着服务器总数的变化而变化，在这些扩展机制中，我们得出了关于稳定性、排队概率和每个类别的系统中作业数量的瞬态分析的第一个结果。我们的分析引入了一种从李亚普诺夫漂移中提取信息的新方法，该方法可适用于排队系统中更广泛的问题。
Cloud computing today is dominated by multi-server jobs. These are jobs that request multiple servers simultaneously and hold onto all of these servers for the duration of the job. Multi-server jobs add a lot of complexity to the traditional one-server-per-job model: an arrival might not "fit'' into the available servers and might have to queue, blocking later arrivals and leaving servers idle. From a queueing perspective, almost nothing is understood about multi-server job queueing systems; even understanding the exact stability region is a very hard problem. In this paper, we investigate a multi-server job queueing model under scaling regimes where the number of servers in the system grows. Specifically, we consider a system with multiple classes of jobs, where jobs from different classes can request different numbers of servers and have different service time distributions, and jobs are served in first-come-first-served order. The multi-server job model opens up new scaling regimes where both the number of servers that a job needs and the system load scale with the total number of servers. Within these scaling regimes, we derive the first results on stability, queueing probability, and the transient analysis of the number of jobs in the system for each class. In particular we derive sufficient conditions for zero queueing. Our analysis introduces a novel way of extracting information from the Lyapunov drift, which can be applicable to a broader scope of problems in queueing systems.