In feed-forward time-sensitive networks with Deficit Round-Robin (DRR), worst-case delay bounds were obtained by combining Total Flow Analysis (TFA) with the strict service curve characterization of DRR by Tabatabaee et al. The latter is the best-known single server analysis of DRR, however the former is dominated by Polynomial-size Linear Programming (PLP), which improves the TFA bounds and stability region, but was never applied to DRR networks. We first perform the necessary adaptation of PLP to DRR by computing burstiness bounds per-class and per-output aggregate and by enabling PLP to support non-convex service curves. Second, we extend the methodology to support networks with cyclic dependencies: This raises further dependency loops, as, on one hand, DRR strict service curves rely on traffic characteristics inside the network, which comes as output of the network analysis, and on the other hand, TFA or PLP requires prior knowledge of the DRR service curves. This can be solved by iterative methods, however PLP itself requires making cuts, which imposes other levels of iteration, and it is not clear how to combine them. We propose a generic method, called PLP-DRR, for combining all the iterations sequentially or in parallel. We show that the obtained bounds are always valid even before convergence; furthermore, at convergence, the bounds are the same regardless of how the iterations are combined. This provides the best-known worst-case bounds for time-sensitive networks, with general topology, with DRR. We apply the method to an industrial network, where we find significant improvements compared to the state-of-the-art.

Total Flow Analysis (TFA) is a method for the worstcase analysis of time-sensitive networks. It uses service curve characterizations of the network nodes and arrival curves of flows at their sources; for tractability, the latter are often taken to be linear functions. For periodic flows, which are common in timesensitive networks, linear arrival curves are known to provide less good bounds than ultimately pseudo-periodic (UPP) arrival curves, which exactly capture the periodic behaviours. However, in existing tools, applying TFA with many flows and UPP curves quickly becomes intractable because when aggregating several UPP curves, the pseudo-period of the aggregate might become extremely large. We propose a solution to this problem, called Finite-Horizon TFA. The method computes finite horizons over which arrival and service curves can be restricted without affecting the end-results of TFA. It can be applied to networks with cyclic dependencies. We numerically show that, while remaining computationally feasible, the method significantly improves the bounds obtained by TFA when using linear curves.

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.

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 worstcase 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.