Logo image
Back
On the latency and fairness characteristics of pre-order deficit round Robin
Journal article   Peer reviewed

On the latency and fairness characteristics of pre-order deficit round Robin

Salil S Kanhere and Harish Sethu
Computer communications, v 27(7), pp 664-678
2004
DOI: https://doi.org/10.1016/j.comcom.2003.12.006
Featured in Collection :   UN Sustainable Development Goals @ Drexel

Abstract

Deficit round Robin Fairness Latency Packet scheduling Quality of service
In the emerging high-speed packet-switched networks, fair packet scheduling algorithms in switches and routers will form an important component of the mechanisms that seek to satisfy the Quality of Service (QoS) requirements of various applications. The latency bound of a scheduling discipline is an important QoS parameter, especially for real-time playback applications. Frame-based schedulers such as Deficit Round Robin (DRR), though extremely efficient with an O(1) dequeuing complexity, lead to high latencies due to bursty transmissions of each flow's traffic. In recent work by Tsao and Lin [Computer Networks 35 (2001) 287], the authors propose a novel scheme, called Pre-order DRR, which overcomes this limitation of DRR while still preserving a low work complexity. In Pre-order DRR, a priority queue module, appended to the original DRR scheduler, re-orders the packet transmission sequence and thus distributes the output more evenly among flows, reducing burstiness and improving the latency. In this paper, we use a novel technique to analytically derive the latency bound of Pre-order DRR and we prove that our bound is a tight one. Our latency bound is significantly lower than the bound derived by Tsao and Lin, demonstrating that Pre-order DRR has even better performance characteristics than previously argued by its own authors. We further study the fairness properties of Pre-order DRR using a recently proposed measure of instantaneous fairness that seeks to more accurately capture the fairness of a scheduler. Using real router traffic traces, we present simulation results that demonstrate that Pre-order DRR achieves better fairness characteristics than other scheduling disciplines of equivalent complexity.

Metrics

6 Record Views
2 citations in Web of Science
2 citations in Scopus

Details

UN Sustainable Development Goals (SDGs)

This publication has contributed to the advancement of the following goals:

#11 Sustainable Cities and Communities

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Web of Science research areas
Computer Science, Information Systems
Engineering, Electrical & Electronic
Telecommunications
Logo image