The multiserver job queueing model
The multiserver job queueing model
复制标题
多服务器作业排队模型
DOI：
10.1007/s11134-022-09762-x
复制
发表时间：
2022
期刊：
影响因子：
1.2
通讯作者：
Harchol-Balter, Mor
中科院分区：
文献类型：
--
作者：
Harchol-Balter, Mor
大量的排队论致力于研究多服务器模型，如M/G/n模型。这类模型的一个重要特征是每个作业运行在一台服务器上。不幸的是，这种每个作业一台服务器的模型并不能很好地代表当今的数据中心。如今几乎所有的数据中心作业都同时占用多台服务器[12]。我们将在多台服务器上运行的此类作业称为多服务器作业。Google的Borg调度程序[12]最近的一项跟踪显示，单个作业使用的服务器数量在不同作业之间可能会有五个数量级的差异。因此，了解具有多服务器作业的系统的性能至关重要。图1显示了多服务器作业排队模型。作业以平均速率λ进入具有n个同构服务器的系统，在该系统中，它们以FCFs顺序提供服务。工作是概率为pi的第i类工作。I类作业需要(任何)Ni个服务器，并行占用这些服务器达Si个小时，其中Si是一个随机变量。重要的是，I类作业的大小是ni.si，并以服务器小时为单位指定。一些相关模型：虽然对多服务器作业排队模型的性能几乎一无所知，但该模型有一个近亲，我们称之为丢弃模型，它在非常一般的设置下是分析容易处理的。在丢弃模型中，不能立即接收服务的作业被丢弃。如Arthur和Kaufman[1]所示，当作业工期(Si‘s)呈指数分布时，丢弃模型呈现出美丽的乘积形式。Whitt[15]将该模型推广到允许作业需要多种资源类型，而van Dijk[13]则允许工期大致分布。与丢弃模型相关的是通信网络中出现的流模型。这里共享的资源是网络中的带宽。“作业”是需要预留固定带宽才能运行的音频流或视频流(类似于需要固定数量的服务器)。目标是调度流程以最小化与丢弃概率相关的成本[4，10]。
A great deal of queueing theory is devoted to studying multiserver models, such as the M/G/n. A key feature of such models is that each job runs on a single server. Unfortunately this one-server-per-job model is not a good representation of today’s data centers. Almost all of today’s data center jobs occupy multiple servers simultaneously [12]. We refer to such jobs that run on multiple servers as multiserver jobs. A recent trace from Google’s Borg scheduler [12] shows that the number of servers utilized by a single job can vary by five orders of magnitude across jobs. Understanding the performance of systems with multiserver jobs is therefore of paramount importance. Figure 1 shows the multiserver job queueing model. Jobs arrive with average rate λ into a system with n homogeneous servers, where they are served in FCFS order. A job is of class i with probability pi. A job of class i requires (any) ni servers, which it occupies in parallel for Si hours, where Si is a random variable. Importantly, the size of a job of class i is ni· Si and is specified in units of server-hours. Some related models: While almost nothing is known about the performance of multiserver job queueing models, there is a cousin of this model, which we call the dropping model, which is analytically tractable under very general settings. In the dropping model, jobs which cannot immediately receive service are dropped. The dropping model exhibits a beautiful product form when job durations (the Si’s) are exponentially distributed, as shown in Arthurs and Kaufman [1]. Whitt [15] generalized the model to allow jobs to demand multiple resource types, while van Dijk [13] allowed durations to be generally-distributed. Related to dropping models are streaming models, which come up in communication networks. Here the resource being shared is bandwidth in the network. The “jobs” are audio or video flows which require a fixed bandwidth reservation to run (akin to needing a fixed number of servers). The goal is to schedule flows to minimize a cost related to dropping probabilities [4, 10].
登录
查看更多内容
DOI：
--
发表时间：
1987
期刊：
影响因子：
--
作者：
F. Baccelli;C. Courcoubetis;M. Reiman
通讯作者：
M. Reiman
客户从随机数量的服务器接收同时服务的队列：系统点方法
影响因子：
5.4
作者：
P. H. Brill;L. Green
通讯作者：
L. Green
具有同时服务的多服务器模型的稳定性判据
影响因子：
4.8
作者：
A. Rumyantsev;E. Morozov
通讯作者：
E. Morozov
阻止需要具有一般思考和保持时间的同步服务器的有限源输入
影响因子：
1.1
作者：
N. Dijk
通讯作者：
N. Dijk
DOI：
10.1145/3492866.3549717
发表时间：
2021-09
期刊：
Proceedings of the Twenty-Third International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing
影响因子：
--
作者：
Yige Hong;Weina Wang
通讯作者：
Yige Hong;Weina Wang