Practical Analysis of Parallel and Networked Queueing Systems

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.

This project aims to underpin the foundations of a robust theory to analyze a plethora of increasingly complex queueing systems. The traditional domain is the telecommunications sector, which has initially motivated the development of the classical queueing theory. By providing a robust set of analytical models and tools for performance analysis, this project has the potential to facilitate network operators to intelligently dimension the underlying transport networks rather than perpetuating the costly approach of bandwidth overprovisioning. Providing a viable alternative to such a conservative approach is particularly timely, especially given the current efforts within IETF to develop and deploy network infrastructures (both fixed and 5G) able to support differentiated services with Quality-of-Service (QoS) performance guarantees.

Besides dimensioning bandwidth, a generic QoS architecture can be applied/deployed in any field subject to (finite) resources, e.g., routers, sensor networks, or data centers. Typically, such resources are overprovisioned by orders of magnitude due to a very conservative attitude of system engineers and the very lack of a robust theory to guide system dimensioning. Unfortunately, the users' perception that systems work seamlessly comes however at unnecessary high economical costs for system operators. In fact, the PI has successfully argued while working for Deutsche Telekom that memories in core routers are much overprovisioned; subsequent internal studies revealed that the proper dimensioning of such apparently insignificant components for a major network provider could in fact bring very large cost reductions.

On a larger scale, our theory has the potential to be instrumental to the development of the so-called Tactile Internet, or Internet at the speed of light, which is foreseen to confine network delays to their mere physical limits. This major paradigm shift is rapidly catching ground from both the academia and the industry, as evidenced by a major European Commission related project (https://riteproject.eu/), involving British Telecom as one the key partners, and which involved the PI as an external annual reviewer. Inspired by the need for real-time connectivity of the Internet-of-Things and 5G communications, the Tactile Internet is expected to have a market share of about USD 20 trillion and foster major innovations in diverse societal areas such as entertaining, education, or medicine (e.g., tele-surgery).

Besides the telecommunication sector, there are several other major industries where a robust tool for queueing analysis, based on a blend between network calculus and queueing theory concepts and methods, can have a significant impact. While co-organizing a thematic Dagstuhl seminar in March 2015, the PI has invited applied researchers from diverse industries such as chip manufacturing, transportation (trains), automotive, or aeronautical. The general consensus which emerged during the seminar is that network calculus has a proven potential to assist the systems' design and optimization. For example, network calculus has been used for the certification of avionic networks in modern Airbus aircrafts, such as the A380, or to assisting the development of automotive networks for safety critical applications.