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

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 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 Shaped Virtual Clock (SVC) in the second and final stage. Moreover, feasible varieties of SDRR that we have considered to achieve better packet latency performance or be partially work-conserving are described.