Virtualized Queueing Theory

Florin Ciucu
Assistant Professor of Computer Science
University of Warwick
SERC 306
Monday, August 24, 2015 - 11:00
Queueing is a fundamental problem characteristic to resource-sharing systems: whenever there is more load than available resources, some jobs/requests are queued and implicitly delayed. The classical queueing theory was conceived by Erlang more than a century ago, and has since evolved as one the most important branches of applied probability. Due to some key technical limitations in its scope, the applicability of queueing theory has been increasingly questioned in the context of complex modern systems, e.g., the Internet. This talk introduces Virtualized Queueing Theory (VQT), a modern approach whose central idea is to increase tractability by sacrificing the exact analysis. At the apparent expense of computing queueing performance metrics in terms of bounds, VQT can address, for the first time, two fundamental problems: per-flow scheduling and multi-queue networks, for a broader class of arrival processes (e.g., Markov modulated). Moreover, by relying on martingale representations of certain transforms of the queueing systems, the obtained bounds are tight and improve existing results by orders of magnitude.