Deficit Round-Robin: A Second Network Calculus Analysis

Deficit Round-Robin (DRR) is a widespread scheduling algorithm that provides fair queueing with variable-length packets. Bounds on worst-case delays obtained with DRR were found by Boyer et al. They used a rigorous network calculus approach and characterized the service obtained by one flow of interest by means of a strict service curve. These bounds do not make any assumptions on the interfering traffic flows hence are pessimistic when the interfering traffic is constrained by some arrival curves. For such cases, Soni et al. improved the worst-case delay bounds by a correction term that accounts for arrival curve constraints of interfering traffic, using a semi-rigorous approach. Unfortunately, these latter bounds are incorrect, as we show by exhibiting a counter-example. Then we derive new service curves for DRR, which are rigorously proven, and we account for arrival curve constraints of interfering traffic. Hence, the resulting delay bounds are guaranteed to be correct. Furthermore, we find numerically that they are smaller than the incorrect ones obtained with the method of Soni et al. These bounds also improve on the results by Boyer et al. when there is no constraint on interfering traffic. Therefore, as of today, they are the best known delay bounds for DRR. Our results are obtained by applying the method of the pseudo-inverse.