权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Practical Analysis of Parallel and Networked Queueing Systems

并行和网络排队系统的实用分析

基本信息

批准号：
EP/T031115/1
负责人：
Florin Ciucu
金额：
$ 62.59万
依托单位：
University of Warwick
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2021
资助国家：
英国
起止时间：
2021 至无数据
项目状态：
未结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FT031115%2F1
关键词：
Practical Analysis Parallel Networked Queueing

项目摘要

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.

计算机或通信系统的基本特征是存在一些资源（例如，CPU、内存、带宽），必须由其进程共享。因为每个资源具有有限的容量，所以系统在过载条件下可能表现得不可预测，即，当请求超过容量时，通过经历延迟效应并因此延迟和/或重传。因此，系统（再）工程的一个关键阶段包括其性能分析，例如，对一般条件下系统行为的基本理解。所获得的洞察力可以为系统工程师提供帮助，例如，从系统性能分析的角度来看，系统性能分析主要有三种理论：系统性能理论（QT）、有效带宽理论（EB）和随机网络演算（SNC）。这些都受到不同的权衡有关的范围内的顺从的系统和数学的准确性，特别是在复杂的多服务器系统。QT提供了精确的结果，但主要受到泊松假设的限制。EB显着扩大抵达的范围，但受渐近制度的精确结果的推导，而使用这些结果作为近似在有限的制度可能会产生误导。SNC进一步扩展了EB的范围，特别是通过管理来处理广泛类别的网络结构和调度算法，但是所产生的随机边界通常非常松散;这可能意味着，例如，对网络进行尺寸确定以满足一些预定义的性能保证将导致网络在很大程度上未被充分利用（即，不必要的大运营成本）。该提案的动机是SNC和QT之间的交叉点最近的一些主要个人成果。特别是，我们通过QT启发的新分析模型和工具，成功地将SNC边界的准确性损失降低了几个数量级;值得注意的是，所获得的结果在交通繁忙的情况下也很明显。同样令人兴奋的是，这种基于鞅变换的新方法可以以初等的方式从QT恢复经典的精确结果（例如，我们计划通过解决一些关键的理论挑战，例如，在具有相关到达的并行和网络队列中推导出尖锐的随机界，这是现代计算机和通信系统的核心。免除泊松/更新假设，典型的突发性理论的特点，是特别及时的广泛承认的证据表明，在现代系统中的负载受到不同程度的突发性。我们未来的工作预计将有助于建立一个强大的理论来分析越来越复杂的系统，例如，电信、制造业或运输业。这是特别需要考虑到当前的努力在IETF开发和部署网络基础设施（固定和5G），能够支持差异化服务与性能保证。从概念的角度来看，这个项目遵循了一个相对较新的挑战，由金曼质疑经典（封装）模型，在他的演讲“100年的封装-Erlang百年”2009年会议。事实上，我们的初步模型的基础上，适当的鞅表示的投机系统实际上已经建议由金曼，并已显示出显着的鲁棒性的基本开放问题的背景下。因此，我们的工作符合金曼的隐含信念，即现代系统在复杂性中发展的速度要求探索全新的嵌入模型，这些模型有可能克服经典模型的局限性，这在100多年的研究中得到了证明。