Computable Bounds in Fork-Join Queueing Systems
Computable Bounds in Fork-Join Queueing Systems
复制标题
DOI：
10.1145/2796314.2745859
复制
发表时间：
2015-06
期刊：
影响因子：
--
通讯作者：
Amr Rizk;Felix Poloczek;F. Ciucu
中科院分区：
文献类型：
--
作者：
Amr Rizk;Felix Poloczek;F. Ciucu
在叉-Join（FJ）排队系统中，上游叉子站将传入的作业分成n个任务，并由n个并行服务器进一步处理，每个服务器都有自己的队列；通过相应任务的响应时间的最大值，在下游联接站确定了一个作业的响应时间。该排队系统对受同步约束的多服务系统的建模有用，例如MapReduce簇或多路径路由。尽管它们显然很简单，但很难分析FJ系统。本文在FJ系统中的等待时间和响应时间分布上提供了第一个可计算的随机界限。我们通过结合1A）续订和1B）非续订到达以及2A）非阻止和2B）阻止服务器来考虑四个实用方案。在非阻止服务器的情况下，我们证明将规模延迟为O（logN），该法律仅在续签输入下是在第一瞬间闻名的。在阻止服务器的情况下，我们证明了log n的相同因素决定了系统的稳定性区域。仿真结果表明，在所有四种情况下，我们的边界都很紧，尤其是在高利用率下。从我们的结果中获得的一个显着洞察力是，在中等到高利用率下，从排队的角度，多路径路由“有意义”，仅对两个路径的排队角度，即，响应时间在n = 2时会下降最大；技术解释是，重新方程（延迟）价格开始迅速主导着由于多路径传输而引起的诱人增益。
In a Fork-Join (FJ) queueing system an upstream fork station splits incoming jobs into N tasks to be further processed by N parallel servers, each with its own queue; the response time of one job is determined, at a downstream join station, by the maximum of the corresponding tasks' response times. This queueing system is useful to the modelling of multi-service systems subject to synchronization constraints, such as MapReduce clusters or multipath routing. Despite their apparent simplicity, FJ systems are hard to analyze. This paper provides the first computable stochastic bounds on the waiting and response time distributions in FJ systems. We consider four practical scenarios by combining 1a) renewal and 1b) non-renewal arrivals, and 2a) non-blocking and 2b) blocking servers. In the case of non blocking servers we prove that delays scale as O(logN), a law which is known for first moments under renewal input only. In the case of blocking servers, we prove that the same factor of log N dictates the stability region of the system. Simulation results indicate that our bounds are tight, especially at high utilizations, in all four scenarios. A remarkable insight gained from our results is that, at moderate to high utilizations, multipath routing 'makes sense' from a queueing perspective for two paths only, i.e., response times drop the most when N = 2; the technical explanation is that the resequencing (delay) price starts to quickly dominate the tempting gain due to multipath transmissions.