Accession Number:

ADA461973

Title:

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

Descriptive Note:

Corporate Author:

DREXEL UNIV PHILADELPHIA PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

2003-07-01

Pagination or Media Count:

44.0

Abstract:

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 O1 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.

Subject Categories:

  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE