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 that 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. First, we present Quick Fair Queueing (QFQ), a new O(1) scheduler that provides near-optimal guarantees 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 that contribute to its speed of operation. Second, we have developed production-quality implementations 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 fulfills our expectations, outperforming the other algorithms in 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).

QFQ: Efficient Packet Scheduling With Tight Guarantees / F., Checconi; L., Rizzo; Valente, Paolo. - In: IEEE-ACM TRANSACTIONS ON NETWORKING. - ISSN 1063-6692. - STAMPA. - 21:3(2013), pp. 802-816. [10.1109/TNET.2012.2215881]

QFQ: Efficient Packet Scheduling With Tight Guarantees

VALENTE, Paolo
2013

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 that 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. First, we present Quick Fair Queueing (QFQ), a new O(1) scheduler that provides near-optimal guarantees 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 that contribute to its speed of operation. Second, we have developed production-quality implementations 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 fulfills our expectations, outperforming the other algorithms in 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).
2013
21
3
802
816
QFQ: Efficient Packet Scheduling With Tight Guarantees / F., Checconi; L., Rizzo; Valente, Paolo. - In: IEEE-ACM TRANSACTIONS ON NETWORKING. - ISSN 1063-6692. - STAMPA. - 21:3(2013), pp. 802-816. [10.1109/TNET.2012.2215881]
F., Checconi; L., Rizzo; Valente, Paolo
File in questo prodotto:
File Dimensione Formato  
qfq.pdf

Accesso riservato

Descrizione: Articolo principale
Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 742.89 kB
Formato Adobe PDF
742.89 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/812716
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 37
  • ???jsp.display-item.citation.isi??? 22
social impact