BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:QFQ: Efficient Packet Scheduling with Tight Service Guarantees - L
 uigi Rizzo\, Associate Professor of Computer Science at the University of 
 Pisa
DTSTART:20090921T090000Z
DTEND:20090921T100000Z
UID:TALK20137@talks.cam.ac.uk
CONTACT:Professor Andrew W. Moore
DESCRIPTION:\n(joint work with Fabio Checconi\, SSSUP S. Anna\, Pisa and P
 aolo Valente\, Universita` di Modena e Reggio Emilia)\n\nAbstract:\n\nPack
 et schedulers with tight bandwidth and delay guarantees must keep up with 
 rapidly increasing link speeds at the core of the Internet and within ente
 rprise switched Ethernets.\n\nThere is a trade-off between an algorithm's 
 complexity and the strength of the service guarantees it provides. State-o
 f-the-art solutions range from fast round-robin schedulers with O(N) guara
 ntees\, to O(log N) timestamp-based schedulers with optimal guarantees. Wh
 ile approximated timestamp-based schedulers exist that achieve near-optima
 l service guarantees in O(1) time\, they do so only with significant const
 ants hidden in the O() notation. For 10 Gbps links and beyond\, even the m
 agnitude of an algorithm's constants limits scalability.\n\nWe present QFQ
 \, a truly practical WFQ scheduler with near-optimal guarantees *and* trul
 y low complexity (250 x86 instructions per packet\, irrespective of number
  of flows and configuration parameters). QFQ combines known techniques to 
 group flows and round timestamps with a novel approach to manipulate multi
 ple groups of flows at once\, thus cutting the constant factors in the alg
 orithm's complexity\, and enhancing scalability.\n\nLink to paper: http://
 info.iet.unipi.it/~luigi/papers/20090731-qfq-full.pdf\n\nSpeaker Bio:\n\nL
 uigi Rizzo\, an Associate Professor of Computer Science at the University 
 of Pisa (and PC co-chair of SIGCOMM 2009) is visiting the SRG/CL Monday.\n
 \nLuigi has made many well-known contributions to the networking community
 : from the IPFW software firewall and dummynet network emulation code in F
 reeBSD (now also available for Linux)\, to high-performance network device
  polling kernel code\, to multicast congestion control\, among many other 
 interesting things.\n\nLuigi has generously offered to give an impromptu t
 alk on his recent work: he's designed and implemented a new O(1) packet sc
 heduling algorithm that features tighter worst-case complexity bounds than
  previous scheduling algorithms. Luigi's new algorithm is well suited to h
 igh-throughput routers and switches\, which must make packet scheduling de
 cisions to keep up with exponentially increasing line rates.\n\n
LOCATION:FW26\, Computer Laboratory\, William Gates Builiding
END:VEVENT
END:VCALENDAR