Toronto Networking Seminar

Organized by Department of Computer Science and Department of Electrical and Computer Engineering, University of Toronto

Buffer Management Algorithms for Streaming Data
with Packet Dependencies

Gabriel Scalosub
University of Toronto

Date: Friday, September 18, 2pm
Location: BA 1210 


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.


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 (