HLS: A Packet Scheduler for Hierarchical Fairness

Hierarchical link sharing addresses the demand for fine-grain traffic control at multiple levels of aggregation. At present, packet schedulers that can support hierarchical link sharing are not suitable for an implementation at line rates, whereas deployed schedulers perform poorly at distributing excess capacity to classes that need additional bandwidth. We present HLS, a packet scheduler that ensures a hierarchical max-min fair allocation of the link bandwidth. HLS supports minimum rate guarantees and isolation between classes. Since it is realized as a non-hierarchical round-robin scheduler, it is suitable to operate at high rates. We implement HLS in the Linux kernel and evaluate it with respect to achieved rate allocations and overhead. We compare the results with those obtained for CBQ and HTB, the existing scheduling algorithms in Linux for hierarchical link sharing. We show that the overhead of HLS is comparable to that of other classful packet schedulers.