Computer Science Colloquium, 2009-2010

Classical Queuing Theory (as well as modern Adversarial Queuing Theory) study the conditions under which a queuing system is stable, i.e., the queue sizes remain bounded. Ideally, a stable system can be designed so that buffer overflows virtually never occur, and hence the issue of buffer overflows was largely overlooked by these disciplines. However, in modern networks like the Internet, buffer overflows occur quite often (being intentionally caused by TCP). The talk will focus on settings where buffer resources are limited, while traffic is arbitrary and requires some Quality-of-Service (QoS) guarantees. In these settings buffer overflows are the common case, rather than the exception. We will consider several such problems including buffer management for traffic consisting of both committed and excess traffic, buffer management for traffic with inter-packet dependencies, and time permitting also discuss buffer management for jitter-sensitive traffic aggregates. We will discuss these problems from a competitive point of view, and present algorithms for admission control and scheduling. Our results consist of both analytic guarantees in terms of the competitive ratio of algorithms for these problems, as well as simulation studies. Our models and solutions are especially applicable to audio and video streaming, which are gaining ever-increasing popularity recently. Based on joint works with David Hay, Alex Kesselman, Boaz Patt-Shamir, and Yuval Shavitt.