A Practical and Efficient Implementation of WF2Q+

The WF²Q+ scheduler combines all three properties that are important to a fair queueing algorithm: a tight delay bound, a small worst-case fair index value, and a relatively low worst-case complexity of O(log n) for a link with n flows. We present a new implementation of WF²Q+ in which both the number of packet sorting operations and the computation of the virtual time function are independent of the number n of flows. Our implementation exploits two widely observed characteristics of the Internet, namely that service providers offer some type of tiered service with a small number of service levels, and that a small number of packet sizes dominate. Our scheduler combines provably good performance with amenability to hardware implementation in high-speed routers.