The Stratified Round Robin Scheduler: Design, Analysis and Implementation

Sriram Ramabhadran and Joseph Pasquale
Department of Computer Science and Engineering
University of California, San Diego

Stratified Round Robin is a fair-queuing packet scheduler which has good
fairness and delay properties, and low quasi-O(1) complexity. It is unique
among all other schedulers of comparable complexity in that it provides a
single packet delay bound that is independent of the number of flows.
Importantly, it is also amenable to a simple hardware implementation, and
thus fills a current gap between scheduling algorithms that have provably
good performance and those that are feasible and practical to implement in
high-speed routers. We present both analytical results and simulations to
demonstrate its performance properties.

Full paper in pdf

This is a revision of our work that appeared in SIGCOMM 2003:
Stratified Round Robin: a low complexity packet scheduler with bandwidth fairness and bounded delay.