A class of shaped deficit round-robin (SDRR) schedulers

In the egress linecards of very high-speed Internet routers, packet 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 of certain egress flows (e.g., those under expedited forwarding (EF) service) so that their packets are not deemed out-of-profile downstream or possibly dropped as a result. Based on Shaped Weighted Round-Robin (SWRR), we propose a scheduler called Shaped Deficit Round-Robin (SDRR) and prove that it strictly limits the variation about the allocated peak-rate of every output flow. As such, our proposed SDRR is suitable for the modern Internet routers of a differentiated-service/MPLS.