Stratified Round Robin: A Low Complexity Packet Scheduler with Bandwidth
Fairness and Bounded Delay
Sriram Ramabhadran and Joseph Pasquale
Department of Computer Science and Engineering
University of California, San Diego
Fair queuing is a well-studied problem in modern computer networks. However,
there remains a gap between scheduling algorithms that have provably good
performance, and those that are feasible and practical to implement in
high-speed routers. In this paper, we propose a novel packet scheduler
called Stratified Round Robin, which has low complexity, and is amenable to
a simple hardware implementation. Stratified Robin Robin exhibits good
fairness and delay properties that are demonstrated through both analytical
results and simulations. In particular, it provides a single packet delay
bound that is independent of the number of flows. This property is unique to
Stratified Round Robin among all other schedulers of comparable complexity.