Practical Analysis of Parallel and Networked Queueing Systems

计算机或通信系统的一个基本特征是存在一些必须由其进程共享的资源(例如，CPU、内存、带宽)。由于每个资源具有有限的容量，因此系统可能在过载情况下，即当请求超过容量时，通过经历排队效应以及随后的延迟和/或重传而不可预测地运行。因此，系统(再)工程的一个关键阶段是系统的性能分析，例如，对系统在一般条件下的行为的基本理解。从排队的角度分析系统性能主要有三种理论：排队论(QT)、有效带宽(EB)和随机网络演算(SNC)。在服从系统的范围和数学精度方面，尤其是在复杂的多服务器系统的上下文中，这些问题受到不同的权衡。Qt提供了准确的结果，但这些结果大多受到到达时的泊松假设的限制。EB极大地扩展了到达的范围，但取决于在渐近区域中的精确结果的推导，而在有限区域中使用这些结果作为近似可能具有误导性。SNC进一步扩展了EB的范围，特别是通过设法处理网络结构和调度算法的广泛类别，但产生的随机边界通常非常宽松；这可能意味着，例如，按照一些预定义的性能保证来确定网络的尺寸将导致网络未得到很大程度的利用(即，不必要的大的运营成本)。特别是，通过受Qt启发的新的分析模型和工具，我们成功地将SNC边界的精度损失降低了数量级；值得注意的是，所获得的结果在繁忙的交通区域也是尖锐的。同样令人兴奋的是，这种基于鞅变换的新方法能够以初等的方式从Qt中恢复经典的精确结果(例如G/M/1队列)。我们计划通过解决一些关键的理论挑战来显著推进我们最近的工作，例如，推导到达相关的并行和网络队列的精确随机界，这是现代计算机和通信系统的核心。考虑到现代系统中的负载受到不同程度的突发性的广泛认可的证据，摆脱泊松/更新假设尤其及时，这是经典排队理论的特征。我们未来的工作有望为分析大量日益复杂的系统(例如电信、制造或运输)提供一个强大的理论。考虑到IETF目前正在努力开发和部署网络基础设施(固定和5G)，能够支持具有性能保证的差异化服务，这一点尤其必要。从概念的角度来看，这个项目遵循了Kingman在2009年会议上的演讲中提出的质疑经典(排队)模型的相对较近的挑战。事实上，我们的初步模型基于排队系统的适当的鞅表示，实际上是由Kingman提出的，并且在基本开放问题的背景下显示了显著的稳健性。因此，我们的工作与Kingman的隐含信念一致，即现代系统在复杂性中发展的速度需要探索全新的排队模型，这种模型有可能克服经典排队模型的局限性，这是经过100多年的研究证明的。

A fundamental characteristic of a computer or communication system is the existence of some resources (e.g., CPU, memory, bandwidth) which must be shared by its processes. Because each resource has a finite capacity, the system can behave unpredictably in overload conditions, i.e., when requests exceed capacity, by experiencing queueing effects and consequently delays and/or retransmissions. Therefore, a crucial stage in the (re-)engineering of system consists of its performance analysis, e.g., the fundamental understanding of the system's behavior under general conditions. The gained insight can be instrumental for system engineers, e.g., to tune the trade-off between seamless functionality and operational costs.There are three main theories for the system performance analysis from a queueing perspective: queueing theory (QT), effective bandwidth (EB), and stochastic network calculus (SNC). These are subject to different tradeoffs concerning the scope of amenable systems and mathematical accuracy, especially in the context of complex multi-server systems. QT provides exact results but which are mostly restricted by the Poisson assumption on arrivals. EB significantly extends the scope of arrivals but subject to the derivation of exact results in asymptotic regimes, whereas using those results as approximations in finite regimes can be misleading. SNC further extends the scope of EB, in particular by managing to deal with broad classes of network structures and scheduling algorithms, but the produced stochastic bounds are typically very loose; this may imply, for instance, that dimensioning a network subject to some predefined performance guarantees would result in a largely underutilized network (i.e., unnecessarily large operational costs).This proposal is motivated by some recent major personal results at the intersection between SNC and QT. In particular, we managed to drastically reduce the accuracy loss of SNC bounds by orders of magnitude through novel analytical models and tools inspired from QT; remarkably, the obtained results are also sharp in heavy-traffic regimes. Equally excitingly, this novel method based on martingale transforms can recover classical exact results from QT in an elementary manner (e.g., the G/M/1 queue).We plan to significantly advance our recent work by addressing some key theoretical challenges, e.g., deriving sharp stochastic bounds in parallel and networked queues with correlated arrivals, which are at the core of modern computer and communication systems. Dispensing with the Poisson/renewal assumption, characteristic to the classical queueing theory, is particularly timely given the widely acknowledge evidence that the load in modern systems is subject to various degrees of burstiness. Our future work is expected to lend itself to a robust theory to analyze a plethora of increasingly complex systems, e.g., telecommunication, manufacturing, or transportation. This is especially needed given the current efforts within IETF to develop and deploy network infrastructures (both fixed and 5G) able to support differentiated services with performance guarantees.From a conceptual point of view, this project follows a relatively recent challenge by Kingman to question classical (queueing) models, during his speech at the "100 Years of Queueing - The Erlang Centennial" 2009 conference. In fact, our preliminary models based on suitable martingale representations of queueing systems have in fact been suggested by Kingman, and have shown significant robustness in the context of fundamental open problems. Our work thus aligns to Kingman's implicit belief that the pace at which modern systems evolve in complexity calls for the exploration of fundamentally new queueing models, which have the potential to overcome the limitations of classic ones, evidenced over more than 100 years of research.