A Class of Shaped Deficit Round-Robin (SDRR) schedulers

Open Access
Author:
Jiwasurat, Soranun
Graduate Program:
Computer Science and Engineering
Degree:
Doctor of Philosophy
Document Type:
Dissertation
Date of Defense:
July 01, 2005
Committee Members:
  • George Kesidis, Committee Chair
  • Raj Acharya, Committee Member
  • Guohong Cao, Committee Member
  • Peng Liu, Committee Member
  • Natarajan Gautam, Committee Member
Keywords:
  • scheduling algorithms
  • high-speed Internet router
  • time complexity
Abstract:
Scheduling mechanisms are deployed in the egress linecards of modern Internet routers to control dequeue from packet memory. Scheduling is required because the egress link fed by packet memory may be channelized (partitioned) and individual flows within each channel may have different priorities or have explicit bandwidth allotments. At extremely high data-rates, schedulers must possess extremely low computation complexity and be able to handle flows of variable-length packets. Existing examples of such schedulers include deficit round robin (DRR). In addition, it may be desirable to limit the variation about the peak-rate (jitter or burstiness) of certain egress flows (e.g., those under expedited forwarding (EF) service) so that their packets are not deemed out-of-profile down stream and possibly dropped as a result. In this research, a scheduler called {em Shaped} Deficit Round-Robin (SDRR)is proposed based on a multiple time-scale decomposition using Shaped Weighted Round-Robin (SWRR) and Deficit Round-Robin (DRR) ideas wherein the deficit counter itself is used for shaping instead of a separate leaky bucket, resulting in O(1) per packet computational complexity. SDRR is proved to have a strict and precisely defined per-flow shaping property making it unique among existing DRR schedulers. As such, the SDRR scheduler is suitable for very high speed multiplexing of flows of variable-length packets. Although SDRR is implementable at high-speeds and has a strict and precisely defined per-flow shaping property, flows, especially those with larger bandwidth allocations, tend to receive less bandwidth than allocated. To improve the under-allocated bandwidth problem while maintaining the ability to limit per-flow shaping property, a Hierarchical Shaped Deficit Round-Robin (HSDRR) is defined. HSDRR is a hybrid round-robin/time-stamp scheduler that employs SDRR scheduling in the first stage and {em Shaped} Virtual Clock (SVC) in the second and final stage. Moreover, several feasible varieties of SDRR are described in order to achieve better packet latency performance or be partially work-conserving.