Cycle time distribution and control for the deficit round robin packet scheduler

Deficit Round Robin (DRR) is a widely implemented packet scheduling algorithm for providing throughput fairness among competing traffic flows in a router. However, its original form may yield poor response times for short-lived flows when the load is heavy. In this paper, we derive the probability distribution of the DRR cycle time, which is key to response times experienced by short-lived flows, with the aids of Renewal Theory and Central Limit Theorem. To utilize the analytical results on DRR cycle time, we then present a mechanism that adjusts the DRR service quanta offered to active traffic flows such that the DRR cycle time is contained. As a result, the response times for short-lived flows can be protected at a desired statistical level. Simulation results demonstrate the accuracy of the Gaussian DRR cycle time distribution as well as the significant improvements achieved by adjusting the quanta.