Practical Analysis of Parallel and Networked Queueing Systems

计算机或通信系统的一个基本特征是存在一些必须由其进程共享的资源（例如，CPU、内存、带宽）。由于每个资源的容量都是有限的，因此系统在过载条件下（即，当请求超过容量时）的行为可能无法预测，可能会出现排队效应，从而导致延迟和/或重传。因此，系统（再）工程的一个关键阶段是其性能分析，例如，在一般条件下对系统行为的基本理解。获得的洞察力可以帮助系统工程师，例如，调整无缝功能和操作成本之间的权衡。从排队的角度分析系统性能主要有三种理论：排队理论（QT）、有效带宽（EB）和随机网络演算（SNC）。这些都受制于不同的权衡，涉及可适应系统的范围和数学精度，特别是在复杂的多服务器系统上下文中。QT提供了精确的结果，但主要受泊松假设的限制。EB显著地扩展了到达的范围，但受制于在渐近状态下精确结果的推导，而将这些结果用作有限状态下的近似可能会产生误导。SNC进一步扩展了EB的范围，特别是通过管理处理广泛类别的网络结构和调度算法，但产生的随机边界通常非常松散；例如，这可能意味着，根据某些预定义的性能保证对网络进行量纲化将导致网络在很大程度上未得到充分利用（即不必要的大操作成本）。这个提议的动机是最近在SNC和QT之间交叉的一些主要的个人结果。特别是，我们设法通过受QT启发的新颖分析模型和工具，以数量级大幅度减少SNC边界的精度损失；值得注意的是，所获得的结果在交通繁忙的地区也很明显。同样令人兴奋的是，这种基于鞅变换的新方法可以以一种基本的方式（例如，G/M/1队列）从QT中恢复经典的精确结果。我们计划通过解决一些关键的理论挑战来显著推进我们最近的工作，例如，在具有相关到达的并行和网络队列中推导尖锐的随机边界，这是现代计算机和通信系统的核心。考虑到现代系统中的负荷具有不同程度的突发性这一广为公认的证据，抛弃经典排队理论所特有的泊松/更新假设尤其及时。我们未来的工作有望成为一种强大的理论，用于分析大量日益复杂的系统，例如电信、制造或运输。鉴于IETF目前正在努力开发和部署能够在性能保证的情况下支持差异化服务的网络基础设施（包括固定和5G），这一点尤其需要。从概念的角度来看，这个项目遵循了Kingman在2009年“100年排队- Erlang百年纪念”会议上的演讲中对经典（排队）模型的质疑。事实上，我们基于排队系统的合适鞅表示的初步模型实际上是由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.