Worst-Case Fair Bin Sort Queuing (WBSQ): An O(1) Worst-Case Fair Scheduler

The design of packet schedulers involves a tradeoff between implementation complexity, on one hand, and delay and fairness guarantees, on the other. In this paper, we present worst-case fair bin sort queuing (WBSQ), a new scheduler that has good worst-case fairness and delay properties, yet has low complexity and is amenable to simple hardware implementation. WBSQ achieves this performance by combining features of BSFQ and WF²Q+. We establish the worst-case fairness and delay properties of WBSQ through both analysis and simulation.