Huffman Fair Queueing: A Scheduling Algorithm Providing Smooth Output Traffic
Man-Ting Choy, Tony Lee · 2006 IEEE International Conference on Communications · 2006
A scheduling algorithm based on Huffman algorithm and Weighted Fair Queueing (WFQ) is proposed. The aim of this scheduler is to provide good fairness and smooth output traffic, while remaining simple in operation. Since WFQ can only guarantee good relative fairness between two flows, we apply WFQ on adjacent nodes of the Huffman binary tree. Therefore, it secures a good worst case fairness result. The Huffman algorithm also suggests that the number of comparisons needed is optimal among all possible tree structures. Our algorithm is able to achieve delay, relative fairness and worst case fairness bounds in the order of O(1) while the complexity is O(logN), where N is the number of flows.