1QFQ: Efficient Packet Scheduling with Tight Guarantees

Abstract—Packet scheduling, together with classification, is one of the most expensive processing steps in systems providing tight bandwidth and delay guarantees at high packet rates. Schedulers with near-optimal service guarantees and O(1) time complexity have been proposed in the past, using techniques such as timestamp rounding and flow grouping to keep their execution time small. However, even the two best proposals in this family have a per-packet cost component which is linear either in the number of groups, or in the length of the packet being transmitted. Furthermore, no studies are available on the actual execution time of these algorithms. In this paper we make two contributions. Firstly, we present QFQ, a new O(1) scheduler that provides near-optimal guaran-tees, and is the first to achieve that goal with a truly constant cost also with respect to the number of groups and the packet length. The QFQ algorithm has no loops, and uses very simple instructions and data structures which contribute to its speed of operation. Secondly, we have developed production-quality implemen-tations of QFQ and of its closest competitors, which we use to present a detailed comparative performance analysis of the various algorithms. Experiments show that QFQ fulfils our expectations, outperforming the other algorithms of the same class. In absolute terms, even on a low end workstation, QFQ takes about 110 ns for an enqueue()/dequeue() pair (only twice the time of DRR, but with much better service guarantees). I