TDS Seminar: Competitive Overflow Management With Packet Dependencies, or Online Set Packing
Speaker: Boaz Patt-Shamir , Tel Aviv University
Date: October 8 2010
Time: 1:00PM to 2:30PM
Location: 32-G631
Host: Nancy Lynch, MIT
Contact: Alex Cornejo, 617 253 19-22, acornejo@csail.mit.edu
Relevant URL: http://groups.csail.mit.edu/tds/tds-seminars.html
Title: Competitive Overflow Management With Packet Dependencies,
or Online Set Packing
Abstract:
We study a scenario in which large data frames are broken into small packets and transmitted over a network of limited-capacity links, where overflows may occur. We assume that losing a single packet from a data frame may result in losing the complete frame. The job of the scheduling algorithm is to decide which packets to drop, so as to maximize the number (or weight) of completed frames (aka "goodput"). We abstract this problem as a new type of on-line set packing. We provide a distributed on-line scheduling algorithm to the problem, analyze its competitive ratio, and prove a nearly-matching lower bound. We show how to extend the algorithm to work in various models that allow for redundancy and buffering.
See other events that are part of Theory of Distributed Systems 2010/2011
See other events happening in October 2010
