Prioritized Elastic Round Robin An Efficient And Low Latency Packet Scheduler With Improved Fairness

Prioritized Elastic Round Robin: An Efficient and Low-Latency Packet Scheduler with Improved Fairness

In emerging high-speed integrated-services packet-switched networks, fair packet scheduling algorithms in switches and routers will play a critical role in providing the Quality-of- Service (QoS) guarantees required by real-time applications. Elastic Round Robin (ERR), a recently proposed scheduling discipline, is very efficient with an O(1) work complexity. In addition, it has superior fairness and delay characteristics in comparison to other algorithms of equivalent efficiency. However, since ERR is inherently a round robin scheduling algorithm, it suffers from the limitations of all round robin schedulers such as (i) bursty transmission and (ii) the inability of the flows lagging in service to receive precedence over the flows that have received excess service. Recently, Tsao and Lin have proposed a new scheme, Pre-order Deficit Round Robin, which tries to eliminate the problems associated with the round robin service order of Deficit Round Robin (DRR). In this report, we present a new scheduling discipline called Prioritized Elastic Round Robin (PERR), based on a similar principle as Pre-order DRR but in a modified and improved form, which overcomes the limitations of ERR. We derive an upper bound on the latency achieved by PERR using a novel technique based on interpreting the scheduling algorithm as an instance of a nested version of ERR. Our analytical results show that PERR has better fairness characteristics and a significantly lower latency bound in comparison to other scheduling disciplines of equivalent work complexity such as DRR, ERR and Pre-order DRR. We further present simulation results, using both synthetic and real traffic traces, which illustrate the improved performance characteristics of PERR.

IEEE Workshop on High Performance Switching and Routing

Advanced Distributed Systems

This book constitutes the thoroughly refereed post-proceedings of the Fifth International School and Symposium on Advanced Distributed Systems, ISSADS 2005, held in Guadalajara, Mexico in January 2005. The 50 revised full papers presented were carefully reviewed and selected from over 100 submissions. The papers are organized in topical sections on database systems, distributed and parallel algorithms, real-time distributed systems, cooperative information systems, fault tolerance, information retrieval, modeling and simulation, wireless networks and mobile computing, artificial life and multi agent systems.