Bandwidth and latency analysis of modified deficit round robin scheduling algorithms

Luciano  Lenzini; Enzo  Mingozzi; Giovanni  Stea

1st International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

Bandwidth and latency analysis of modified deficit round robin scheduling algorithms

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1145/1190095.1190147,
    author={Luciano  Lenzini and Enzo  Mingozzi and Giovanni  Stea},
    title={Bandwidth and latency analysis of modified deficit round robin scheduling algorithms},
    proceedings={1st International ICST Conference on Performance Evaluation Methodologies and Tools},
    publisher={ACM},
    proceedings_a={VALUETOOLS},
    year={2012},
    month={4},
    keywords={Deficit Round Robin Latency Performance Evaluation.},
    doi={10.1145/1190095.1190147}
}

Luciano Lenzini
Enzo Mingozzi
Giovanni Stea
Year: 2012
Bandwidth and latency analysis of modified deficit round robin scheduling algorithms
VALUETOOLS
ACM
DOI: 10.1145/1190095.1190147

Luciano Lenzini¹^,*, Enzo Mingozzi¹^,*, Giovanni Stea¹^,*

1: Dipartimento di Ingegneria dell’Informazione, University of Pisa, Italy, Via Diotisalvi 2, 56122 Pisa, Italy – Ph. +39 050 2217599

*Contact email: l.lenzini@iet.unipi.it, e.mingozzi@iet.unipi.it, g.stea@iet.unipi.it

Abstract

Deficit Round Robin (DRR) is a scheduling algorithm which provides fair queuing at O(1) complexity. However, due to its round robin structure, its latency properties are not adequate for latency-critical applications, such as voice. For this reason, router manufacturers implement variants of the DRR algorithm which guarantee lower latencies to one (or a subset of) queue(s). In this paper we evaluate the performance of two such variants, both of which are known as Modified Deficit Round Robin, currently implemented in commercial routers. The comparison is carried out analytically, by deriving the latency and bandwidth sharing properties of both algorithms, and by simulation.

Keywords: Deficit Round Robin Latency Performance Evaluation.

Published: 2012-04-12
Publisher: ACM

: http://dx.doi.org/10.1145/1190095.1190147