  Deficit Round-Robin (DRR) is a widespread scheduling algorithm that provides
fair queueing with variable-length packets. Bounds on worst-case delays for DRR
were found by Boyer et al., who used a rigorous network calculus approach and
characterized the service obtained by one flow of interest by means of a convex
strict service curve. These bounds do not make any assumptions on the
interfering traffic hence are pessimistic when the interfering traffic is
constrained by some arrival curves. For such cases, two improvements were
proposed. The former, by Soni et al., uses a correction term derived from a
semi-rigorous heuristic; unfortunately, these bounds are incorrect, as we show
by exhibiting a counter-example. The latter, by Bouillard, rigorously derive
convex strict service curves for DRR that account for the arrival curve
constraints of the interfering traffic. In this paper, we improve on these
results in two ways. First, we derive a non-convex strict service curve for DRR
that improves on Boyer et al. when there is no arrival constraint on the
interfering traffic. Second, we provide an iterative method to improve any
strict service curve (including Bouillard's) when there are arrival constraints
for the interfering traffic. As of today, our results provide the best-known
worst-case delay bounds for DRR. They are obtained by using the method of the
pseudo-inverse.

Performance