Publications by Seyed Mohammadhossein Tabatabaee

Efficient and Accurate Handling of Periodic Flows in Time-Sensitive Networks

Jean-Yves Le Boudec, Seyed Mohammadhossein Tabatabaee

Total Flow Analysis (TFA) is a method for the worst-case 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 time-sensitive 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.

2023

Deficit Round-Robin: A Second Network Calculus Analysis

Jean-Yves Le Boudec, Seyed Mohammadhossein Tabatabaee

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.

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

Deficit Round-Robin: A Second Network Calculus Analysis

Jean-Yves Le Boudec, Seyed Mohammadhossein Tabatabaee

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.

2021

Interleaved Weighted Round-Robin: A Network Calculus Analysis

Jean-Yves Le Boudec, Seyed Mohammadhossein Tabatabaee

Weighted Round-Robin (WRR) is often used, due to its simplicity, for scheduling packets or tasks. With WRR, a number of packets equal to the weight allocated to a flow can be served consecutively, which leads to a bursty service. Interleaved Weighted Round-Robin (IWRR) is a variant that mitigates this effect. We are interested in finding bounds on worst-case delay obtained with IWRR. To this end, we use a network calculus approach and find a strict service curve for IWRR. The result is obtained using the pseudo-inverse of a function. We show that the strict service curve is the best obtainable one, and that delay bounds derived from it are tight (i.e., worst-case) for flows of packets of constant size. Furthermore, the IWRR strict service curve dominates the strict service curve for WRR that was previously published. We provide some numerical examples to illustrate the reduction in worst-case delays caused by IWRR compared to WRR.

IEICE-INST ELECTRONICS INFORMATION COMMUNICATION ENGINEERS2021

,

Weighted Round-Robin (WRR) is often used, due to its simplicity, for scheduling packets or tasks. With WRR, a number of packets equal to the weight allocated to a flow can be served consecutively, which leads to a bursty service. Interleaved Weighted Round-Robin (IWRR) is a variant that mitigates this effect. We are interested in finding bounds on worst-case delay obtained with IWRR. To this end, we use a network calculus approach and find a strict service curve for IWRR. The result is obtained using the pseudo-inverse of a function. We show that the strict service curve is the best obtainable one, and that delay bounds derived from it are tight (i.e., worst-case) for flows of packets of constant size. Furthermore, the IWRR strict service curve dominates the strict service curve for WRR that was previously published. We provide some numerical examples to illustrate the reduction in worst-case delays caused by IWRR compared to WRR.

2020