Deficit round-robin is a packet scheduling algorithm devised to provide fair queueing in the presence of variable length packets (see Shreedhar, M. and Varghese, G., IEEE Trans. on Networking, vol.4, p.375-85, 1996). DRR can be implemented at O(1) complexity provided that each flow is allowed to transmit at least one maximum size packet on each round; however, under this constraint, DRR may exhibit high latency and poor fairness. We first generalize previous results known for DRR, related to its latency and fairness. We then introduce a novel DRR implementation technique, called active lists queue method (Aliquem), which allows the above constraint to be relaxed while preserving O(1) complexity, thus achieving better latency and fairness that are comparable to those of more complex algorithms, such as self-clocked fair queueing.

Aliquem: a Novel DRR Implementation to Achieve Better Latency and Fairness at O(1) Complexity

LENZINI, LUCIANO;MINGOZZI, ENZO;STEA, GIOVANNI
2002-01-01

Abstract

Deficit round-robin is a packet scheduling algorithm devised to provide fair queueing in the presence of variable length packets (see Shreedhar, M. and Varghese, G., IEEE Trans. on Networking, vol.4, p.375-85, 1996). DRR can be implemented at O(1) complexity provided that each flow is allowed to transmit at least one maximum size packet on each round; however, under this constraint, DRR may exhibit high latency and poor fairness. We first generalize previous results known for DRR, related to its latency and fairness. We then introduce a novel DRR implementation technique, called active lists queue method (Aliquem), which allows the above constraint to be relaxed while preserving O(1) complexity, thus achieving better latency and fairness that are comparable to those of more complex algorithms, such as self-clocked fair queueing.
2002
0780374266
File in questo prodotto:
File Dimensione Formato  
08/04218672086417404973911592541069253690

solo utenti autorizzati

Tipologia: Versione finale editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 673.79 kB
Formato Unknown
673.79 kB Unknown   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

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