Toronto Networking Seminar


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







Breaking through the Complexity Limits of Rate-based Packet Scheduling





Martin Karsten


School of Computer Science


University of Waterloo




Date:  Friday, March  6,  2pm

Location: BA 1130 



Abstract:




A rate-based packet scheduler with constant execution complexity AND constant
worst-case delay and fairness properties has been elusive in the past. In fact,
recent research has speculated that such a scheduler cannot exist. However,
these speculations turn out to be premature. In this talk, I present a
packet scheduler that uses a novel priority queue called Interleaved
Stratified Timer Wheels (ISTW). The scheduler can be implemented with low
overhead and has constant execution complexity. It provides weighted
rate-based packet service with constant worst-case delay and fairness
properties.




Host of the talk



Yashar Ganjali (yganjali@cs.toronto.edu)