In packet-switched networks, the scheduling algorithm implemented by the routers must possess three important properties: fairness, to provide isolation among competing flows and ensure that each flow receives its fair share of the link bandwidth; bounded delay, so as to guarantee a bounded end-to-end delay to interactive applications; and low complexity, so as to be possible to operate at wire speeds even for large number of flows. Although many fair queuing disciplines have been proposed, the best among them have worst-case time complexity of O(log n) for a link with n flows.
Tiered Service Fair Queuing (TSFQ), a new queuing discipline, has been proposed to achieve packet sorting and virtual time computation in time that is independent of the number of flows. TSFQ 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. Consequently, TSFQ maps the competing n flows to p service levels where p is a small constant, and uses a special queuing structure that eliminates the need to sort most packets.
As part of this thesis work, we implement the WF2Q+ discipline and various TSFQ variants in the Linux kernel as separate loadable modules, and we investigate their relative performance over a small testbed. Our experimental results indicate that TSFQ closely emulates previously proposed fair queuing disciplines.
The main conclusion of our work is that TSFQ is a viable packet scheduler that
can be used in networks with heavy traffic loads to achieve fairness in constant time.
