Buffer Management
Algorithms for Streaming Data
with Packet
Dependencies
Gabriel Scalosub
University of Toronto
Date: Friday, September 18, 2pm
Location: BA 1210
Abstract:
In many applications the
traffic traversing the network has inter-packet dependencies due to
application-level encoding schemes. For some applications, e.g., multimedia
streaming, dropping a single packet may render useless the delivery of a whole
sequence. In such environments, the algorithm used to decide which packet to
drop in case of buffer overflows must be carefully designed, to avoid goodput
degradation. We present a model that captures such inter-packet dependencies,
and enables to quantify the effectiveness of buffer management algorithms for
such traffic.
We identify several guidelines for performing buffer management in such
environments, and design several algorithms that follow these guidelines. We
evaluate the performance of our solutions using competitive analysis. We
further present the results of a simulation study showing that the performance
of our algorithm is within a small fraction of the performance of the best
offline algorithm.
Based on joint works with Alex Kesselman, Boaz Patt-Shamir, Peter Marbach, and
Jorg Liebeherr.
Bio:
Received
the B.Sc. in Mathematics and Philosophy from the Hebrew University of Jerusalem,
Israel, in 1999, and the M.Sc. and Ph.D. degrees in Computer Science from the
Technion, Haifa, Israel, in 2002 and 2007, respectively. In 2007-8 he was a
postdoctoral fellow at the School of Electrical Engineering, Tel Aviv
University, Israel, and he is currently a postdoctoral fellow at the Department
of computer Science, University of Toronto, Canada. He will be joining the
Communication Systems Engineering department in Ben Gurion University, Israel,
come October 2009. His research interests include scheduling and buffer
management in computer networks, online and approximation algorithms,
algorithmic game theory, and wireless networks.
Host of the talk
Jörg Liebeherr (jorg@comm.toronto.edu)