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.