1
LUDB++: Enabling LUDB for the Analysis of Shaped Feedforward FIFO Networks using Network Calculus
arXiv:2605.08944v1 [cs.NI] 9 May 2026
Alexander Scheffler, Faculty of Mathematics and Computer Science, University of Hagen, Germany
Abstract—This paper discusses how latency guarantees for non-cyclic (feedforward) First-In-First-Out (FIFO) networks with shapers can be computed within the Network Calculus (NC) framework. Shapers are methods implemented in software or hardware and may reside inside the network and at the endpoint which constrain the rate and maximum packet sizes for the transmission of specific data streams (flows) or groups thereof. Shaping can improve latencies and is an important aspect of Time-Sensitive Networking (TSN). Several methods in NC exist to analyze FIFO networks. Among them is the Least Upper Delay Bound (LUDB) methodology. So far, LUDB does not incorporate shaping assumptions into its analysis. This paper addresses this gap resulting in the new methodology called LUDB++. The evaluation on a set of different line topologies and a tree topology with a total of 130 configurations shows that LUDB++ delivers more accurate latency bounds compared to LUDB. Moreover, the Exponential Linear Program (ELP) method, which considers FIFO and shaping inside the network, yields the most accurate bounds to this date. ELP is superseded by LUDB++ for most of cases by a margin of up to 9.13%. Index Terms—Network Calculus, Delay Bounds, Mathematical Optimization.
I. I NTRODUCTION
R
EAL-TIME systems inclusive of the automotive industry, avionics and industrial automation require deterministic guarantees on timing behavior. Missing a response within a certain timeframe can often be critical in such systems, e.g., a delayed triggering of a brake after pressing the respective pedal. Ethernet as communication backbone for such systems has become increasingly popular in the last years. It is lowcost and an enhancement of the standard called TSN [1] offers reliable network communication with deterministic delays. TSN also comes with traffic shaping which limits the rate and maximum packet sizes certain data flows can transmit in the network. This method can reduce maximum delays inside the network, especially for high-priority flows. NC [2] [3] has been proven useful for the formal derivation of delays. This paper assumes that FIFO scheduling – which is widespread and easy to implement – alongside shaping inside the network and at the endpoint is at place. Limited work in NC exist that studies both aspects in conjunction. One approach is ELP [4] which constructs one global Linear Program (LP) as upper bound of the Mixed Integer Linear Program (MILP) discussed in [5] by removing the integer variables of the latter. Different to the MILP of [5], ELP also includes line shaping constraints and
thus can be seen as the most accurate analysis to this date for our studied network model. Another stream of research in NC for FIFO is LUDB [6] [7]. It is a modular analysis where tandems (servers in a row) are analyzed separately and where the global solution consists of stitching the individual solutions together. Its complexity mainly stems from (i) dividing up the network into tandems and (ii) solving each tandem that occurred during the analysis by means of solving a set of LPs. So far, LUDB is restricted to simple, so-called token bucket, arrival curves and pseudo-affine service curves [6] where a rate-latency curve is a special form of it. LUDB does not take shaping into account – neither at the endpoint nor inside the network. In this paper, we propose LUDB++, an extension of LUDB that considers shaping assumptions. For this, step (ii) had to be completely revised as the curves during the analysis got significantly more complex. Our evaluation on different tandems and a tree topology reveals that LUDB++ delivers more accurate bounds than ELP for almost all cases. As the modeling complexity increased compared to LUDB, so did its runtime. Nonetheless, we were able to carry out our evaluation with topologies where the tandems during the analysis were each spanning up to 8 servers. Additionally, we provide an open-source C++ implementation of LUDB++. The rest of this paper is organized as follows: Section II gives background on NC and states the system model for this study. In Section III, we report the related work. Section IV presents the LUDB++ methodology including a comprehensive example after which it is evaluated on different network configurations in Section V. The paper ends with concluding remarks in Section VI. II. N ETWORK C ALCULUS BACKGROUND AND S YSTEM M ODEL An overview on NC performance analysis can be found in [8] [9]. Definition 1 (Cumulative Data Functions). Let function A describe the cumulative input data arrival of a flow crossing a server S. Then A′ describes its cumulative output after S. These functions are in the set F0 := {f : R∞ → R+ ∞ |f (0) = 0 ∀s ≤ t : f (t) ≥ f (s)} with R∞ = R ∪ {∞} and + R+ ∞ = R ∪ {∞}, respectively.
2
Definition 2 (Arrival Curve). Let A be the cumulative input function of a flow f at server S. Then we call α ∈ F0 an arrival curve of f at S if ∀ 0 ≤ d ≤ t : A(t) − A(t − d) ≤ α(d). Definition 3 (Service Curve). Let A be an input to a server S and A′ be the respective output function. Then we say that β ∈ F0 is a service curve for S if ∀t ≥ 0 : A′ (t) ≥ inf {A(t − s) + β(s)} =: A ⊗ β(t). 0≤s≤t
Definition 4 (NC Operations). The (min,plus)-algebraic aggregation, convolution and deconvolution of the functions g, h ∈ F0 are defined as aggregation: (g + h) (d) = g (d) + h (d),
(1)
convolution: (g ⊗ h) (d) = inf {g(d − u) + h(u)}, (2) 0≤u≤d
deconvolution: (g ⊘ h) (d) = sup {g(d + u) − h(u)}.
(3)
u≥0
Theorem 1 (Performance Bounds). Consider a server S that offers a service curve β. Assume flow f has arrival curve α. Then we obtain the following bounds:
maximum transmission capacity of the outgoing link and L for the maximum packet size. A shaper may also be assumed to hold at the entry of the network, i.e., the endpoint itself shapes some of its outgoing flows. Mathematically, the output process is constrained by (α ⊘ β) ∧ γL,R′ after server S and by α ∧ γL,R′ after the endpoint with a ∧ b := min{a, b}. Our network model consists of data flows originating from endpoints. Each flow is constrained by a token bucket arrival curve with token bucket endpoint-shaping. The flows traverse a network of FIFO-multiplexing servers. Each server offers a rate latency curve1 and a token bucket output shaper per outgoing link. For stability, we assume per traversed server S that the sum of the of the respective flows’ non-shaped arrival curve rates is less than the rate of S. Moreover, we assume that each shaper rate R′ is at least as high as the service rate of the corresponding server S. Additionally, we assume that R′ of S is also at least as high as the following service rates of servers on any path of a flow that traverses S on the respective link. The assumption also applies to the endpoint-shaping rate. A similar assumption on the shaper rate can be found in [10]. Lastly, we limit our study to feedforward networks, so the paths among the flows do not exhibit cyclic dependencies.
Output Bound: α′ (t) = α ⊘ β(t) := sup{α(t + u) − β(u)} u≥0
III. R ELATED W ORK
Delay Bound: hDev(α, β) = inf{d ≥ 0 : (α ⊘ β)(−d) ≤ 0}
Backlog Bound: vDev(α, β) = sup{α(u) − β(u)} = α ⊘ β(0) A. TFA, TFA++, FP-TFA, GFP-TFA, AdmTFA u≥0 Total Flow Analysis (TFA) [8] is a method to compute a ′ ′ delay bound for the flow of interest (foi) by iteratively applying where α is a bound on A , the output from server S (see delay and output bound of Theorem 1 to the aggregation of Definition 3), and the horizontal (vertical) deviation hDev flows (Definition 4) along foi’s path. TFA has low compu(vDev) between arrival curve and service curve bounds the tational cost, however, the bounds become increasingly loose delay (backlog) experienced by f at S. with increasing network size. TFA++ [11] [12] is an extension Theorem 2 (Convolution of Service Curves). Consider two of TFA that incorporates shaping constraints of the links. For servers in tandem S1 and S2 with service curves β1 and β2 this, the respective shaper curve is used to get a tighter input respectively for flow f . Then, β1 ⊗ β2 is a service curve for arrival curve when computing the node’s delay bound, i.e., f for the system (S1 , S2 ). hDev(α ∧ γL,R′ , β) instead of hDev(α, β). Similarly, the Theorem 3 (FIFO Leftover Service). Let server S offer shaper curve is used go get a tighter output bound. Other service curve β. Assume flows f1 and f2 with arrival curves extensions of TFA include Fixed-Point TFA (FP-TFA) [10] for α1 and α2 cross S. Assuming FIFO multiplexing, the leftover cyclic networks, Generic FP-TFA (GFP-TFA) [13] for more general curves than TFA-FP and Admission Shaping with service for f1 is TFA (AdmTFA) [14]. AdmTFA solves TFA as an LP that βfl.o. (t) = [β(t) − α2 (t − θ)]+ · 1{t>θ} incorporates shaping constraints at the entry of the network 1 + with [x] := max{0, x}, the indicator function 1{condition} that and within the network. It is also applicable to cyclic networks is 0 if the condition is not met and 1 otherwise, and θ ∈ R+ for which a fixed point equation is computed. is the free FIFO parameter. As abbreviation for the expression we use β ⊖θ α2 . Example 1 (Common Curve Shapes). Common curve shapes in NC include the so-called burst-delay function δT (t) that is 0 for t ≤ T and ∞ otherwise. δ0 (t) is the neutral element w.r.t. operator ⊗. A typical service curve is the so-called rate latency curve defined as βR,T (t) = R · [t − T ]+ . A common arrival curve is the so-called token bucket curve defined as γb,r (t) = r · t + b. Definition 5 (Shapers). The cumulative output A′ after server S can further be constrained by a so-called shaper. It can be described by a curve γL,R′ where R′ typically stands for the
B. SFA-FIFO Separated Flow Analysis with FIFO (SFA-FIFO) [7] computes the residual service curve at each server along the path of the foi according to Theorem 3. The θ value is fixed as T + Rb for service curve βR,T and arrival curve γb,r . Afterwards, Theorem 2 is applied iteratively on the residual service curves. From this, the final delay bound is computed with Theorem 1. It does not take shaping into account, has low computational cost and often results in better bounds than TFA. 1 more general curve is allowed as long as it fits into the curve class described in Section IV.
3
C. LUDB, LUDB-FF LUDB [6] was initially developed for nested tandems which are defined as follows. Definition 6 (Nested Tandem). Tandem T consisting of a set of subsequent servers S1 , S2 , ..., Sn is called a nested tandem iff for all pairs of flows fi , fj its respective paths on T either have a subset relation or are fully disjoint. Note that the previous definition assumes that a flow does not rejoin T . If the flow indeed rejoins T , the flow is split into several flows for each rejoining segment on T . A nested tandem allows the analysis to proceed from the inside out applying Theorem 3 and Theorem 2 along the way. For example, for the following nested tandem T ,
curve. The study is limited to one hop persistent cross-traffic at each server, so a special nested topology. The crossflows’ arrival curves are all limited to token bucket arrival curves. The approach is quite similar to LUDB with the difference that it finds the optimal θi values w.r.t. delay bound of a CPL arrival curve (new) and left-over service curve for this topology (old). It derives a close form solution for the delay bound which is then at least as good as LUDB. This is because LUDB ignores shaping and more generally, reduces CPL arrival curves to token bucket curves. The authors of [17] admit that ”the general case, with shaping on considered and interfering flow ... seems really harder”, exactly where this paper contributes to. E. ELP, PLP and PLPP
Fig. 1: Sinktree tandem with N = 3. the analysis would proceed as follows. β3 ⊖θ1 α3 is what is left at S3 for the aggregate f2 and f3 . This result is then convolved with the service curve of S2 , i.e., β2 ⊗ (β3 ⊖θ1 α3 ) which is how much service is left for the aggregate f2 and f3 on the subtandem T2,3 that spans S2 and S3 only. That result in turn is used to remove flow f2 ’s interference on T2,3 given by the result of (β2 ⊗ (β3 ⊖θ1 α3 )) ⊖θ2 α2 . This can be convolved with the service curve of S1 which results in β1 ⊗((β2 ⊗(β3 ⊖θ1 α3 ))⊖θ2 α2 ) that is the leftover service curve . Finally, for f1 for the complete tandem T denoted by βfl.o. 1 the delay bound can be computed with Theorem 1, namely hDev(α, βfl.o. ). 1 LUDB automates this procedure by first building up a socalled nesting tree that encodes the steps of the analysis in a tree which is then traversed bottom-up. Moreover, LUDB does not set the FIFO parameters θi to a fixed value during the traversal of the nesting tree. Instead, it formulates all steps of the analysis symbolically to then be able to optimize the θi ’s to achieve the lowest upper delay bound w.r.t. the involved NC operation in this order. LUDB is tight2 for sink tree networks [15], but the computed bound can be larger than the actual worst case delay for other topologies. Another limitation of LUDB is that it is restricted to token bucket arrival curves and pseudoaffine service curves for which the rate latency curve is a special form of it. Later on, LUDB has been extended to non-nested tandems [16] by virtual flow splitting to transform non-nested tandems into nested ones. LUDB has also been extended to feedforward networks denoted by LUDB-FF [7]. D. LUDB with Shaped Foi [17] presents an extension of LUDB where the foi experiences a so-called concave piecewise linear (CPL) arrival 2 i.e., there exist a sample path that coincides with the upper bound
As LUDB does not guarantee tight delay bounds, [5] presents an approach based on mathematical optimization that provably delivers tight delay bounds in FIFO feedforward networks without shapers. For this purpose, it encodes the complete network with its flow paths, arrival curves constraints, service curve constraints, FIFO property, timing relations, monotonicity constraints and indicator variables into a single exponentially-sized MILP. The MILP has not been researched with shaping constraints to this date. Recent works discussed in [4] relax the tightness guarantee as follows. ELP is the MILP of [5] without the indicator variables, thus effectively turning the MILP into a LP of exponential size. Polynomial Linear Program (PLP) is a polynomial-sized LP that takes the main ideas of the MILP. It has fewer time variables than the MILP which are naturally ordered and thus do not require indicator variables that enforce such an ordering. Moreover, PLP includes TFA++ and SFA constraints to make the delay bound result less pessimistic. Additionally, PLP incorporates shaping constraints within the network, i.e., line shaping constraints3 . PLPP (PLP’ in [4]) is the same as PLP just without the TFA++ and SFA constraints and thus an upper bound of PLP’s delay results. IV. LUDB++ This Section constitutes our main contribution, LUDB++, an extension of LUDB that incorporates shaping assumptions into its analysis. While the order of operations of the analysis is the same as in LUDB (discussed in Section III), the statements of intermediary results need to be completely revised. We first start by defining a useful function, the so-called window function Iw [18]. Definition 7 (Window ( Function). The window function is w if t = 0 defined as Iw (t) = +∞ if t > 0 Next, we model an essential curve for our study within the NC framework that begins at some offset, followed by a step 3 Note that our evaluation in Section V shows that the implementation of ELP which is available at https://github.com/anne-bou/panco seems to also incorporate shaping assumptions, although this is not officially stated in [4].
4
after which it continues linearly. This can be modeled with the curve ((δτ ⊗ Iσ1 ⊗ γ0,ρ1 ) ∧ δ0 ) ⊗ δD (4)
Next, we will consider backlog and output bounds which are important to analyze non-nested tandems and general feedforward networks.
since inf s,u≥0 {(δτ ⊗ Iσ1 ⊗ γ0,ρ1 ) ∧ δ0 (s) + δD (u)} ( s+u=t 0 if t ≤ D = ((δτ ⊗ Iσ1 ⊗ γ0,ρ1 ) ∧ δ0 )(t − D) if t > D Note, that (δτ ⊗ Iσ1 ⊗ γ0,ρ1 ) ∧ δ0 is a function that starts at the origin, has a plateau of height σ1 with width τ and is then followed by a linear rate of ρ1 . We call the curve class that can be described as minimum of such functions that all begin after a common offset M SLC as abbreviation for ’Minimum of Steps Linear Curve’. Figure 2 illustrates this class for n = 1.
Theorem 6 (Backlog Bound and Output Arrival Curve of Arrival Curve and Service Curve in MSLC). Let α = γb,r and n V β ∈ MSLC of the form β = δD ⊗ ( (δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0 ) i=1
with 0 ≤ r ≤ min ρi . Then vdev(α, β) = [b+Dr]∨[ i=1,...,n
n W
(b−
i=1
σi + (D + τi )r)] and an output arrival curve for the flow is n W α ⊘ β(t) = rt + vdev(α, β) = rt + [b + Dr] ∨ [ (b − σi + i=1
(D + τi )r)] for t ≥ 0.
We also need to discuss how to compute the leftover service curves with LUDB++. Theorem 7 (Non-Decreasing Lower Bound of Leftover Service in MSLC). Let α = γb,r ∧ γL,R′ and β ∈ MSLC of the n V form β = δD ⊗ ( (δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0 ) with L ≤ b i=1
and r < R′ , R′ ≥
max {ρi |ρi < +∞}, r ≤
i=1,...,n
↑
min ρi .
i=1,...,n ↑
Then, (β ⊖θ α) ∈ MSLC for every θ ≥ 0 where f for f ∈ F is the non-decreasing lower bound of f defined as ↑ f (t) := inf {f (u)}. u≥t
Corollary 1 (Symbolic Non-Decreasing Lower Bound of Leftover Service Curve). Let α = γb,r ∧ γL,R′ and β ∈ MSLC of n V the form β = δD ⊗ ( (δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0 ) with L ≤ b
beta_theta=T^pri.pdf
and r < R′ , R′ ≥
Fig. 2: M SLC with n = 1.
i=1
max {ρi |ρi < +∞}, r ≤
i=1,...,n
min ρi .
i=1,...,n
↑
Definition 8 (MSLC). The service curve β ∈ MSLC is defined n V as β = δD ⊗ ((δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0 ). i=1
Lemma 1 (Rate Latency Service Curve is in MSLC). Let β = βR,T be a rate latency service curve. Then, β ∈ MSLC. Theorem 4 (MSLC Closed under Convolution). Let β1 , β2 ∈ n V1 MSLC, i.e., β1 = δD1 ⊗ ( (δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0 ) and β2 = δD2 ⊗ (
n V2
τi +
[y−σi ]+ ρi −r
⊗I[σi −y]+ ⊗γ0,ρi −r )∧δ0 )∧((δθ−D ⊗
R −r θ−D+ Rb−L ′ −r + ρ −r
R −r
i
γ0,ρi −r ) ∧ δ0 ) ∧ ((δθ−D ⊗ I0 ⊗ γ0,+∞ ) ∧ δ0 )) with θ ≥ D b−L and θ ≥ D + τi − Rb−L ′ −r and y = (θ + R′ −r − (D + τi ))ρi + σi . and for ρi = +∞ with θ ≥ D it can be described as
The delay bound for shaped arrival curves and this new curve class can be computed as follows. Theorem 5 (Delay Bound Shaped Arrival Curve and MSLC Service Curve). Let α = γb,r ∧γL,R′ and β ∈ MSLC of n V the form β = δD ⊗( (δτi ⊗Iσi ⊗γ0,ρi )∧δ0 ) with L ≤ b and i=1
max {ρi |ρi < +∞}, r ≤ min ρi . Then i=1,...,n n W [σi −b]+ , τi · hdev(α, β) = D + [ [τi · 1{σi ≥ b−L r+b} − r ′ i=1,...,n
i=1 ρi <+∞ b−L [ R′ −r r+b−σi ]+ ρi
δD ⊗(((δτi ⊗I0 ⊗γ0,+∞ )∧δ0 )∧((δθ−D ⊗I0 ⊗γ0,+∞ )∧δ0 )) with D ≤ θ ≤ D + τi . • δD ⊗(((δθ−D ⊗I0 ⊗γ0,+∞ )∧δ0 )∧((δθ−D ⊗I0 ⊗γ0,+∞ )∧ δ0 )) with θ > D + τi . •
With the aforementioned results, we are now able to analyze shaped FIFO networks with LUDB++ and provide an example in the following.
R −r
−
b−L + R′ −r ] ,
n W
[τi · i=1 ρi =+∞ [σi −b]+ [σi −L]+ + + 1{σi ≥ b−L , τi · 1{ b−L ] ] r+b} − r+b≥σi } − r R′ R′ −r R′ −r 1{ b−L r+b≥σi } + ′
δD ⊗(((δ
I0 ⊗ γ0,+∞ ) ∧ δ0 )) with D ≤ θ ≤ D + τi − Rb−L ′ −r and y = ((D + τi ) − θ)r + b. • δD ⊗ (((δ r+b−y]+ ⊗ I[y−( b−L [ b−L r+b)]+ ⊗ ′ ′
(δτ˜i ⊗ Iσ˜i ⊗ γ0,ρ˜i ) ∧ δ0 ). Then β1 ⊗ β2 ∈
MSLC as well.
R −r
•
i=1
i=1
r < R′ , R′ ≥
Then, (β ⊖θ α) for ρi < +∞ with θ ≥ D can be described as follows
A. Example In this (sub-)Section, we present the LUDB++ analysis steps for two server topology depicted in Figure 3.
5
b −L
[ R2′ −r2 r2 +b2 −0]+
1{ b2 −L2 r2 +b2 ≥0} +
2
2
ρ1 −r1
′ −r R2 2
−
b2 −L2 + W [(τ2 R2′ −r2 ]
+
+
2] 1 1 τ1 + ρy−σ ) · 1{σ2 ≥ b2 −L2 r2 +b2 } − [σ2 −b , (τ2 + τ1 + ρy−σ )· r2 1 −r1 1 −r1 ′ −r R2 2 b −L [ R2′ −r2 r2 +b2 −σ2 ]+ 2 2
1{ b2 −L2 r2 +b2 ≥σ2 } + Fig. 3: LUDB++ example for two servers with one crossflow. For delay bounding, LUDB++ computes ↑ inf hdev(α2 , β2 ⊗ (β1 ⊖θ α1 ) ) with αi ∈ γbi ,ri ∧ γLi ,Ri′ and
θ≥0
βi ∈ MSLC with n = 1. ↑ By Corollary 1, (β1 ⊖θ α1 ) yields: (I) δD1 ⊗ ([δ [y−σ1 ]+ ⊗ I[σ1 −y]+ ⊗ γ0,ρ1 −r1 ] ∧ [δθ−D1 ⊗ τ1 + ρ −r 1
1
b1 −L1 I0 ⊗ γ0,+∞ ] ∧ δ0 ) with θ ≥ D1 , θ ≤ D1 + τ1 − R and ′ 1 −r1 y = ((D1 + τ1 ) − θ)r1 + b1 . ⊗ (II) δD1 ⊗ ([δ b −L1 [ 1 r1 +b1 −y]+ b −L
θ−D1 + R1′ −r1 + 1
1
′ −r R1 1 ρ1 −r1
I[y−( b1 −L1 r1 +b1 )]+ ⊗ γ0,ρ1 −r1 ] ∧ [δθ−D1 ⊗ I0 ⊗ γ0,+∞ ] ∧ δ0 ) ′ −r R1 1
with θ ≥ D1 , θ ≥ D1 + τ1 − b1 −L1 y = (θ + R − (D + τ ))ρ . ′ −r 1 1 1 1
b1 −L1 R1′ −r1
and
1
For brevity, we only show decomposition (I) in the following. ↑ For β2 ⊗ (β1 ⊖θ α1 ) , we make use of Theorem 4 while already removing duplicate steps in the overall minimum expression as well as some optimization considerations where one of the rates is infinite and obtain the following: (I) δD1 +D2 ([δτ2 ⊗ Iσ2 ⊗ γ0,ρ2 ] ∧ [δ [y−σ1 ]+ ⊗ I[σ1 −y]+ ⊗ τ1 + ρ −r
γ0,ρ1 −r1 ] ∧ [δ [δ
[y−σ1 ]+ τ2 +τ1 + ρ −r 1 1
1
⊗ I[σ1
1
⊗ I[σ1 −y]+ +σ2 ⊗ γ0,ρ2 ] ∧
[y−σ1 ]+ τ2 +τ1 + ρ −r 1 1
−y]+ +σ
2
⊗ γ0,ρ1 −r1 ] ∧ [δθ−D1 ⊗
I0 ⊗ γ0,+∞ ] ∧ [δτ2 +θ−D1 ⊗ Iσ2 ⊗ γ0,ρ2 ] ∧ δ0 ) with b1 −L1 θ ≥ D1 , θ ≤ D1 + τ1 − R and y = ((D1 + τ1 ) − θ)r1 + b1 ′ −r 1 1
ρ1 −r1
[δτ2 +τ1 + y−σ1 ⊗Iσ2 ⊗γ0,ρ2 ]∧[δτ2 +τ1 + y−σ1 ⊗Iσ2 ⊗γ0,ρ1 −r1 ]∧ ρ1 −r1
Again, for brevity, we only show the decomposition (I.I) in the following. Now, we apply Theorem 5 for a delay bound expression of this composition and obtain + 2] , τ2 · (I.I) D1 + D2 + [τ2 · 1{σ2 ≥ b2 −L2 r2 +b2 } − [σ2 −b r2 1{ b2 −L2 r2 +b2 ≥σ2 } + ′ −r R2 2
y−σ1 ρ1 −r1 )
′ −r R2 2 b −L [ R2′ −r2 r2 +b2 −σ2 ]+ 2 2
ρ2
· 1{0≥ b2 −L2 r2 +b2 } − ′ −r R2 2
b2 −L2 + − R ′ −r ] 2 2
[0−b2 ]+ , (τ1 r2
+
W
[(τ1 +
y−σ1 ρ1 −r1 )
·
2
[(τ2 +
+
′ −r R2 2 b −L [ R2′ −r2 r2 +b2 −σ2 ]+ 2 2
1{ b2 −L2 r2 +b2 ≥σ2 } +
b2 −L2 + − R ′ −r ] 2
ρ1 −r1
′ −r R2 2
W
[(θ −
2
+
2] , (θ −D1 )·1{ b2 −L2 r2 +b2 ≥0} − D1 )·1{0≥ b2 −L2 r2 +b2 } − [0−b r2 ′ −r ′ −r R2 R2 2 2 + W [0−L2 ] + [σ2 −b2 ]+ ] [(τ +θ−D )·1 , (τ2 + − b2 −L2 ′ 2 1 R r2 {σ2 ≥ r2 +b2 } ′ −r R2 2 b −L
2
θ − D1 ) · 1{ b2 −L2 r2 +b2 ≥σ2 } +
[ R2′ −r2 r2 +b2 −σ2 ]+ 2
2
ρ2
′ −r R2 2
b2 −L2 + −R ′ −r ] 2 2
with y = ((D1 + τ1 ) − θ)r1 + b1 and constraints b1 −L1 θ ≥ D 1 , θ ≤ D1 + τ 1 − R ′ −r , y − σ1 ≥ 0. 1 1
The decomposition (I.I) with further constraint b2 −L2 b2 −L2 decompositions R r2 + b2 ≥ 0, R r2 + b2 ≥ σ2 ′ ′ 2 −r2 2 −r2 + and where the second element in [] is the maximum element yields the following LP Minimize D1 + D2 + τ2 +
b2 −L2 ′ −r r2 +b2 −σ2 R2 2
ρ2
b2 −L2 −R ′ −r 2 2
such that b2 −L2 R2′ −r2 r2 + b2 ≥ 0 b2 −L2 R′ −r2 r2 + b2 ≥ σ2 2
τ2 + τ2 +
τ2 +
b2 −L2 ′ −r r2 +b2 −σ2 R2 2
τ2 + τ2 +
τ2 +
τ2 + τ2 +
2
b2 −L2 ′ −r r2 +b2 −σ2 R2 2
b2 −L2 −R ≥0 ′ −r 2
ρ2 b2 −L2 ′ −r r2 +b2 −σ2 R2 2
2
b2 −L2 1 −R ≥ τ2 + τ1 + ρy−σ + ′ 1 −r1 2 −r2
b2 −L2 ρ2 R2′ −r2 b2 −L2 ′ −r r2 +b2 −σ2 R2 b2 −L2 2 ρ2 R2′ −r2 b2 −L2 ′ −r r2 +b2 −σ2 R2 b2 −L2 2 ρ2 R2′ −r2
−
ρ2 b2 −L2 r +b2 −σ2 ′ R2 −r2 2 ρ2 b2 −L2 ′ −r r2 +b2 −σ2 R2 2 ρ2 b2 −L2 r2 +b2 −σ2 R′ −r
b2 −L2 R2′ −r2
2
ρ2
−
≥0
−
1 ≥ τ2 + τ1 + ρy−σ + 1 −r1
b2 −L2 −R ′ −r 2
b2 −L2 ′ −r r2 +b2 −σ2 R2 2
2
b −L
2 2 ′ −r r2 +b2 R2 y−σ1 b2 −L2 2 −R ≥ τ + + − ′ −r 1 ρ1 −r1 ρ1 −r1 2 2
ρ2
ρ1 −r1
τ2 +
b2 −L2 −R ≥0 ′ −r 2
ρ2 b2 −L2 ′ −r r2 +b2 −σ2 R2 2
b2 −L2 ′ −r r2 +b2 −σ2 R2 2
τ2 +
2
b2 −L2 −R ≥0 ′ 2 −r2
ρ2 b2 −L2 ′ −r r2 +b2 −σ2 R2 2
ρ2 b2 −L2 r +b −σ 2 2 2 ′ R2 −r2
τ2 +
b2 −L2 −R ≥0 ′ −r 2
ρ2 b2 −L2 ′ −r r2 +b2 −σ2 R2 2
b2 −L2 R2′ −r2
ρ1 −r1
[δθ−D1 ⊗ I0 ⊗ γ0,+∞ ] ∧ [δτ2 +θ−D1 ⊗ Iσ2 ⊗ γ0,ρ2 ] ∧ δ0 ) (I.II) Additional constraint y − σ1 ≤ 0 yields δD1 +D2 ⊗ ([δτ2 ⊗ Iσ2 ⊗ γ0,ρ2 ] ∧ [δτ1 ⊗ Iσ1 −y ⊗ γ0,ρ1 −r1 ] ∧ [δτ2 +τ1 ⊗ Iσ2 +σ1 −y ⊗ γ0,ρ2 ] ∧ [δτ2 +τ1 ⊗ Iσ2 +σ1 −y ⊗ γ0,ρ1 −r1 ] ∧ [δθ−D1 ⊗ I0 ⊗ γ0,+∞ ] ∧ [δτ2 +θ−D1 ⊗ Iσ2 ⊗ γ0,ρ2 ] ∧ δ0 )
W
2] 1 1 τ1 + ρy−σ ) · 1{σ2 ≥ b2 −L2 r2 +b2 } − [σ2 −b , (τ2 + τ1 + ρy−σ )· r2 1 −r1 1 −r1
τ2 +
We proceed bottom up as in the LUDB methodology by splitting up the different cases already at this level of the analysis. (I) Let y = ((D1 + τ1 ) − θ)r1 + b1 and constraints b1 −L1 θ ≥ D 1 , θ ≤ D1 + τ 1 − R ′ 1 −r1 (I.I) Additional constraint y − σ1 ≥ 0 yields δD1 +D2 ⊗ ([δτ2 ⊗ Iσ2 ⊗ γ0,ρ2 ] ∧ [δτ1 + y−σ1 ⊗ I0 ⊗ γ0,ρ1 −r1 ] ∧
b2 −L2 + − R ′ −r ] 2
ρ2
′ −r R2 2
2
b2 −L2 −R ≥0 ′ −r 2 2
b2 −L2 −R ≥ θ − D1 ′ 2 −r2 b2 −L2 −R ≥0 ′ −r 2 2
b −L
2 2 ′ −r r2 +b2 −σ2 R2 b2 −L2 2 −R ≥ τ +θ−D + − ′ −r 2 1 ρ2 2 2
6
θ ≥ D1 b1 −L1 θ ≤ D 1 + τ1 − R ′ 1 −r1 y − σ1 ≥ 0
1) One Hop Persistent Tandems: These nested tandems have a foi that crosses all servers and for each server there is exactly one crossflow which only crosses exactly that one server.
with y = ((D1 + τ1 ) − θ)r1 + b1 . Each LP will be solved individually and the minimum objective value over all these LPs will be then the LUDB++ result. The result is formally equal to inf hdev(α2 , β2 ⊗ θ≥0
↑
(β1 ⊖θ α1 ) ). The procedure for backlog bounds is done in an analogous way. V. E VALUATION We begin the evaluation Section by noting the hard- and software with which we obtained our data4 .
A. Hardware and Software Experiments were performed on a MacBook Pro with macOS Sequoia 15.6.1 (24G90), Apple M1 Chip (2020), 8GB RAM. 5 • LUDB++ data were obtained with the code , version 1.0.0, C++17, cmake 3.30, CLion 2024.3.5, CPLEX V22.1.1.0. Release build with compiler flags -O3 march=armv8.5-a -funroll-loops -flto=thin. 6 • LUDB-FF, SFA-FIFO data were obtained with the code , commit 5bfcdeea705130f719304257b3530dac0b7b36ed, Java 19 SDK, IntelliJ IDEA Ultimate 2024.2.4, CPLEX V22.1.1.0. • ELP, PLP, PLPP, TFA++, AdmTfa data were obtained with the code7 , commit 2c923fc8618d73bbc589d95450ec530b37b58a1e, Python 3.9.6, PyCharm 2024.1.4 (Professional Edition), lp solve version 5.5.2.11
•
B. Networks and Results We evaluate three different kind of network topologies in the following. For all of them the following holds. Each server has service curve βR,T = βR,1 and each flow has arrival curve α = γb,r = γ1,1 . Moreover, we assume that each flow is shaped at the ingress location and each server has an (output) shaper with γL,R′ = γ0.5,R′ . We vary R and R′ to achieve different utilizations and different shaper rate to service rate ratios. We use the following metric to compare delay bounds: delayA,B = delay(A)−delay(B) , say relative delay bound (of delay(B) A) to B. A negative value hence signifies that A’s bound is smaller than B’s. 4 Released after acceptance. 5 Released after acceptance. 6 https://github.com/alexscheffler/DNC 7 https://github.com/anne-bou/panco
Fig. 4: One hop persistent tandem with N = 3. The utilization for this topology is u = 2·r R . From 63 settings, ELP failed for 5 settings where panco terminated with an error. This is the reason why some plots end at 6 or 7 servers instead of 8. LUDB++ beats ELP for the majority of the settings, namely in 38 settings from 58 settings. The minimal, maximal and average deviation of LUDB++ to ELP is −9.13%, 6.66% and −1.42% respectively. ELP shows no influence on R′ (not shown in the figures) for this topology. Hence, the plots precisely depict the influence of R′ on LUDB++’s delay bounds. For a fixed utilization, a decrease of R′ yields a larger absolute deviation of LUDB++ to ELP. This is because a smaller R′ has a larger impact on the shaped input arrival curve which in turn decreases the LUDB++ delay bounds. For the corner case u = 100%, note that R′ no longer influences LUDB++’s delay bounds such that they coincide with the bounds from LUDB-FF and are worse than ELP. In most cases, increasing the number of servers decreases the gap between ELP and LUDB++ because the shaping effect at the entry of the network that LUDB++ considers in contrast to ELP has a smaller weight. As expected, LUDB++ delay bounds are less than or equal to LUDB-FF as the latter does not take shaping into account. Interestingly, SFA-FIFO delivers the same bounds as LUDB-FF. This can be explained as follows. There is no cutting for this topology, so LUDB-FF and SFA-FIFO are very similar with the only difference in the optimization of θ variables – for this topology and settings they apparently coincide. PLP delivers the same bounds as LUDBFF except for 2 servers where it yields a better bound which additionally coincides with ELP. The group which delivers inferior bounds are: AdmTFA, PLPP and TFA++ and the gap to ELP for these methods tends to increase with increasing number of servers. AdmTFA delivers smaller or equal bounds compared to TFA++ and for small number of servers also than PLPP. 2) Sinktree Tandems: These nested tandems have a foi that crosses all N servers and N − 1 crossflows. Each crossflow starts at a unique position in the tandem (earliest at the second server) and ends in the sink of the tandem. For an example with N = 3, refer to Figure 1. The (maximal) utilization for this topology is u = NR·r . LUDB++ beats ELP for all of the 36 settings. The minimal, maximal and average deviation of LUDB++ to ELP is −5.03%, −0.26% and −1.29% respectively. ELP shows no influence on R′ (not shown in the figures) for this topology.
7
103
102
102
0
LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
100 101
2
3
4
5 6 Number of Servers
7
101
101 100 LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
0 100 101
8
2
5 6 Number of Servers
7
0
101
8
103
102
102
101 100 LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF 2
3
4
5 6 Number of Servers
7
101 100 LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
0 100 101
8
2
(d) u = 75%, R′ = R
3
4
5 6 Number of Servers
7
Deviation to ELP Delay [%]
103
101
4
5 6 Number of Servers
7
8
(g) u = 100%, R′ = R
101 LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
0
2
3
4
5 6 Number of Servers
7
8
(h) u = 100%, R′ = 2R
Deviation to ELP Delay [%]
102
Deviation to ELP Delay [%]
102
3
2
3
4 5 Number of Servers
6
7
(f) u = 75%, R′ = 3R
102
2
LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
101
103
0
6
100
8
100
5
0
103
LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
4 Number of Servers
100
(e) u = 75%, R′ = 2R
101
3
101
103
100
2
(c) u = 50%, R′ = 3R
102
0
LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
100
103
100
Deviation to ELP Delay [%]
4
100
(b) u = 50%, R′ = 2R
Deviation to ELP Delay [%]
Deviation to ELP Delay [%]
(a) u = 50%, R′ = R
3
Deviation to ELP Delay [%]
100
Deviation to ELP Delay [%]
101 Deviation to ELP Delay [%]
102
101 LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
100
0
2
3
4 Number of Servers
5
6
(i) u = 100%, R′ = 3R
Fig. 5: Relative delays to ELP for different shaper configurations, different utilizations and different R′ to R ratios for one hop persistent tandems. PLPP also shows no influence on R′ . PLP is R′ -sensitive for number of servers at least 3 where an increase of R′ increases the delay bound. For a reasoning on the influence of R′ for a fixed utilization on the relative LUDB++ delay bounds, refer to the previous (sub-)Section (one hop tandem topology). In all cases for this topology, increasing the number of servers decreases the gap between ELP and LUDB++. For the reasoning behind this, refer again to the previous (sub)Section (one hop tandem topology). Interestingly, LUDB-FF delivers the same bound as ELP. Since ELP does not have an influence on R′ here and LUDB-FF is tight for sinktrees (without shaping assumptions), both methods deliver the same bounds8 . Moreover, PLP delivers the same bound as LUDBFF for this topology for number of servers 2 and worse bounds for larger number of servers. The relative delay gap of PLP to ELP increases with increasing number of servers for this topology. SFA-FIFO delivers worse bounds compared to PLP 8 as formally, for a sinktree topology, LUDB-FF achieves the same bound as the MILP from which the ELP stems from but apparently the latter two coincide for this topology as well.
and in some scenarios is beaten by TFA++ and AdmTFA, especially for a low R′ to R ratio, mid to low utilization and from 3 servers upwards. PLPP delivers the worst bounds in almost all scenarios for this topology. 3) Tree: As an example for the analysis of general feed-forward networks with this method, the last topology of our evaluation has a tree structure. The foi crosses servers on a main branch. Each crossflow comes from a side branch and joins the foi on the main branch until the last server. The interference pattern on the main branch is of type sink tree while the pattern on the side branch is of type one hop persistent. Figure 7 depicts this topology where the foi crosses 3 servers. Note that the side branch objective minimizes for the backlog bound as we are interested in the output arrival curve for the crossflow at the location where it joins the foi. After computing it, we compute the output arrival curve according to Theorem 6 and then shape it with the shaping curve γL,R′ .
102
102
101
101
101
100 0
LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
100 101
2
3
Number of Servers
4
100 0
LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
100 101
5
2
4
0
101
5
101
101
101
100
LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF 2
3
Number of Servers
4
100 0
LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
100 101
5
2
(d) u = 75%, R′ = R
3
Number of Servers
4
Deviation to ELP Delay [%]
102
101
101
5
102
100 101
2
3
Number of Servers
4
5
(g) u = 100%, R′ = R
101 100 LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
100 101
2
3
Number of Servers
4
5
(h) u = 100%, R′ = 2R
Deviation to ELP Delay [%]
102 Deviation to ELP Delay [%]
102
0
5
LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF 2
3
Number of Servers
4
5
(f) u = 75%, R′ = 3R 103
LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
4
100
103
100
Number of Servers
0
(e) u = 75%, R′ = 2R
101
3
100
103
0
2
(c) u = 50%, R′ = 3R
102
0
LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
100
102
100
Deviation to ELP Delay [%]
Number of Servers
100
(b) u = 50%, R′ = 2R
Deviation to ELP Delay [%]
Deviation to ELP Delay [%]
(a) u = 50%, R′ = R
3
Deviation to ELP Delay [%]
102
Deviation to ELP Delay [%]
Deviation to ELP Delay [%]
8
101 100
LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
0 100
2
3
Number of Servers
4
5
(i) u = 100%, R′ = 3R
Fig. 6: Relative delays to ELP for different shaper configurations, different utilizations and different R′ to R ratios for sinktree tandems.
Fig. 7: Tree with N = 3. The (maximal) utilization for this topology is u = NR·r . LUDB++ beats ELP for all of the 36 settings. The minimal, maximal and average deviation of LUDB++ to ELP is −3.74%, −0.67% and −2.13% respectively. Here, ELP
shows an influence on R′ (not shown in the figures) for this topology. For a fixed utilization, a decrease of R′ still tends to increase the absolute deviation of LUDB++ to ELP indicating that LUDB++ is more sensitive to a change of R′ than ELP. Interestingly, LUDB-FF delivers the same bound as ELP in 6 of the 9 settings for this topology. For R′ = R, LUDB-FF delivers worse bounds (except the 2 server scenario in (g)) and the gap gets smaller by increasing the number of servers. PLP delivers worse bounds compared to LUDB-FF except for R′ = R paired with lower than 100% utilization and low number of servers (2 to 3). The gap of PLP to ELP increases with increasing number of servers for this topology. SFA-FIFO delivers worse bounds compared to PLP and in some scenarios is beaten by TFA++ and AdmTFA, especially for R′ = R, mid to low utilization and from 3 servers upwards. For utilization of 50%, SFA-FIFO is beaten by PLPP for larger networks (5 servers) although the latter performs the worst compared to all other methods for the other scenarios. 4) Runtimes: In the following, we discuss the aggregate runtimes which means that for a fixed topology and server
102
102
101
101
101
100 0
LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
100
2
3 4 Number of Servers on Foi's Path
0
LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
100 101
5
2
3 4 Number of Servers on Foi's Path
102
102
101
101
100 0
LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
100 101
2
3 4 Number of Servers on Foi's Path
101
5
100 0
LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
100 101
5
2
3 4 Number of Servers on Foi's Path
100 LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
0 100 101
5
2
3 4 Number of Servers on Foi's Path
(e) u = 75%, R′ = 2R
LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
0 100
101 100 LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
0 100 101
5
2
3 4 Number of Servers on Foi's Path
(g) u = 100%, R′ = R
Deviation to ELP Delay [%]
102
Deviation to ELP Delay [%]
102
100
5
(f) u = 75%, R′ = 3R
102 101
5
101
103
3 4 Number of Servers on Foi's Path
3 4 Number of Servers on Foi's Path
102
103
2
2
(c) u = 50%, R′ = 3R
103
101
LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
103
(d) u = 75%, R′ = R
Deviation to ELP Delay [%]
0
(b) u = 50%, R′ = 2R
Deviation to ELP Delay [%]
Deviation to ELP Delay [%]
(a) u = 50%, R′ = R
100
100
Deviation to ELP Delay [%]
101
100
Deviation to ELP Delay [%]
102
Deviation to ELP Delay [%]
Deviation to ELP Delay [%]
9
101 100 LUDB++ SFA-FIFO PLPP PLP TFA++ AdmTFA LUDB-FF
0 100 101
5
2
3 4 Number of Servers on Foi's Path
(h) u = 100%, R′ = 2R
5
(i) u = 100%, R′ = 3R
Fig. 8: Relative delays to ELP for different shaper configurations, different utilizations and different R′ to R ratios for the specified tree topology.
108 106
1012
LUDB++ SFA-FIFO ELP PLPP PLP TFA++ AdmTFA LUDB-FF
1010 Runtime[us]
1010
Runtime[us]
1012
LUDB++ SFA-FIFO ELP PLPP PLP TFA++ AdmTFA LUDB-FF
108
LUDB++ SFA-FIFO ELP PLPP PLP TFA++ AdmTFA LUDB-FF
1010 Runtime[us]
1012
108
106
106
104
104
104 102
2
3
4
5 6 Number of Servers
7
8
2
(a) One hop persistent tandems (ELP non-nan adjusted)
3
Number of Servers
4
5
(b) Sinktree tandems
2
3 4 Number of Servers on Foi's Path
5
(c) Tree
Fig. 9: Aggregate runtimes per topology.
count up to 9 runs of a specific analysis such as LUDB++ is summed up. For at least 3 servers, LUDB++ takes the longest compared to all other analyses. Its runtime ranges from 0.29 s for 2 servers to 4.26 d for 8 servers regarding the one-hop
persistent topology. Its runtimes for sinktree tandem (tree) topology range from 0.05 s (0.03 s) for 2 servers to 3.91 d (1.41 d) for 5 servers. Next is LUDB-FF with a runtime ranging from 0.5 s for 2 servers to 0.68 s for 8 servers
10
regarding the one-hop persistent topology. The runtimes for sinktree tandem (tree) topology range from 0.32 s (0.32 s) for 2 servers to 5.83 s (6.54 s) for 5 servers. That LUDB++’s runtime is larger than LUDB-FF is due to the considerably more complex network model which incorporates shaping assumptions and thus achieves better delay bounds. ELP has a runtime ranging from 0.04 s for 2 servers to 34.22 min for 8 servers. Thus, for at least 5 servers upwards ELP takes longer than LUDB-FF for the one-hop persistent topology. Runtimes of ELP for sinktree tandem (tree) topology range from 0.03 s (0.07 s) for 2 servers to 0.29 s (0.41 s) for 5 servers. The other methods are all below 1s with PLP being the most expensive one since it internally calls TFA++ and SFA and adds respective delay constraints into the optimization formulation before solving. PLPP’s optimization problem is as PLP just without the TFA++ and SFA constraints and is thus faster but comes with a higher inaccuracy. SFA-FIFO is the fastest method among all for which no optimization is required.
ACKNOWLEDGMENTS The author thanks Anne Bouillard for her help with the derivation of Equation (4). A PPENDIX We now present the proofs of the Theorems of Section IV. Proof of Lemma 1. β = βR,T = δT ⊗((δ0 ⊗I0 ⊗γ0,R )∧δ0 ) ∈ MSLC. Lemma 2 (Convolution of MSLC with n = 1 ). Let β1 , β2 ∈ MSLC with β1 = δD1 ⊗ ((δτ1 ⊗ Iσ1 ⊗ γ0,ρ1 ) ∧ δ0 ) and β2 = δD2 ⊗ ((δτ2 ⊗ Iσ2 ⊗ γ0,ρ2 ) ∧ δ0 ). Then β1 ⊗ β2 ∈ MSLC. Proof. Due to commutativity of ⊗, we can write β1 ⊗ β2 = δD1 +D2 ⊗ ((δτ1 ⊗ Iσ1 ⊗ γ0,ρ1 ) ∧ δ0 ) ⊗ ((δτ2 ⊗ Iσ2 ⊗ γ0,ρ2 ) ∧ δ0 ). Since βD1 +D2 is just shifting the function by D1 + D2 units to the right, we focus on the expression [(δτ1 ⊗ Iσ1 ⊗ γ0,ρ1 ) ∧ δ0 ] ⊗ [(δτ2 ⊗ Iσ2 ⊗ γ0,ρ2 ) ∧ δ0 )] =: f ⊗ g(t) = inf r,s≥0 {f (r) + g(s)}. r+s=t
Case 1 (t = 0): f (0) ∧ g(0) = 0 = f (0) + g(0). VI. C ONCLUSION This paper discusses formal delay bound guarantees in feedforward FIFO networks with shapers that limit the maximum packet size and rate of flows. Our work extends LUDB, which is FIFO-aware but does not take shaping into account, is called LUDB++ and takes both aspects into consideration. Hence, LUDB++ delivers better delay bounds than LUDB except in edge cases where both methods yield the same result. ELP is another existing method that also considers both aspects in its analysis and encodes it into one exponential LP. Our evaluation shows that LUDB++ delivers better delay bounds compared to ELP for the majority of the cases by up to 9.13%. However, these delay bounds come with a computational price. Although LUDB++ splits up the feedforward network into nested (sub)tandems, solving these tandems can quickly get computationally expensive depending on the topology and number of crossflows. This is especially the case for sinktree tandems where our evaluation shows that for 5 servers and a total of 9 configurations the total runtime already grows to 3.91 d. Future work will focus on improving the scalability of the approach by e.g., approximation techniques. One such technique could be to make an educated guess on the decomposition(s) during the analysis – from the 4 possible ones per leftover operation, only consider 1 ≤ k < 4 ones. AI could also be combined with this as it has been successfully combined with NC in the past in other contexts such as flow prolongation [19] for which a choice within the analysis is AI-driven instead of bruteforcing all alternatives. Moreover, LUDB++ computes for a vector of variables that each stem from an application of the FIFO leftover service theorem a setting that strictly minimizes the delay or backlog bound. While preserving non-negativity, the variables can be set arbitrarily, so approximated solutions are valid as well and have been applied in the past to network models without shaping assumptions [20] [21]. It might also be worthwhile to apply parallelization on the decompositions on the nested (sub-)tandem level within LUDB++ which is one analysis-level deeper than parallelization of the splitting the network into tandems process discussed in [22].
Case 2 (0 < t ≤ max{τ1 , τ2 }): inf s=0 {f (t) + g(0)} ∧ inf t=s {f (0) + g(t)} ∧ inf 0<s<t {f (t − s) + g(s)} = f (t) ∧ g(t) ∧ inf 0<s<t {f (t − s) + g(s)}. Now, we evaluate inf {f (t − s) + g(s)}. First 0<s<t≤max{τ1 ,τ2 }
of all, note that g(s) ≥ σ2 and f (t − s) ≥ σ1 . We have to show that f (t − s) + g(s) ≥ f (t) ∧ g(t) for t ≥ max{τ1 , τ2 } and t >0. if 0 < s ≤ τ2 σ 2 g(s) = σ2 + ρ2 (s − τ2 ) if s > τ2 , s < t which implies max{τ1 , τ2 } = τ1 σ1 if 0 < t − s ≤ τ1 σ + ρ (t − s − τ ) if t − s > τ , 1 1 1 1 f (t−s) = t − s < max{τ 1 , τ2 } which implies max{τ1 , τ2 } = τ2 Subcase 2.1 (max{τ1 , τ2 } = τ1 ): f (t − s) = σ1 , g(s) = σ2 and f (t) ∧ g(t) = σ1 ∧ (σ2 + ρ2 (t − τ2 )), f (t − s) + g(s) = σ1 + σ2 ≥ σ1 ∧ (σ2 + ρ2 (t − τ2 )). Subcase 2.2 (max{τ1 , τ2 } = τ2 ): f (t − s) = σ1 , g(s) = σ2 and f (t) ∧ g(t) = (σ1 + ρ1 (t − τ1 )) ∧ σ2 , f (t − s) + g(s) = σ1 + σ2 ≥ (σ1 + ρ1 (t − τ1 )) ∧ σ2 . Hence, for this case f ⊗ g(t) = f (t) ∧ g(t). Case 3 (t > max{τ1 , τ2 } > 0): As before, we have f ⊗ g(t) = f (t) ∧ g(t) ∧ inf 0<s<t {f (t − s) + g(s)}. Since t > max{τ1 , τ2 }, f (t) = σ1 + ρ1 (t − τ1 ) and g(t) = σ2 + ρ2 (t − τ2 ). Moreover, note that f (t − s) ≥ σ1 and g(s) ≥ σ2 for 0 < s < t. Subcase 3.1 (t ≤ τ1 +τ2 ): inf 0<s<t {f (t−s)+g(s)} = σ1 +σ2 Subcase 3.2 (t > τ1 + τ2 ): inf 0<s<t {f (t − s) + g(s)} = (σ1 + (t − τ2 − τ1 )ρ1 + σ2 ) ∧ (σ2 + (t − τ1 − τ2 )ρ2 + σ1 ). Hence, for this case we get f ⊗ g(t) = f (t) ∧ g(t) ∧ (σ1 + σ2 ) if 0 < max{τ1 , τ2 } < t and t ≤ τ1 + τ2 f (t) ∧ g(t) ∧ [f (t − τ2 ) + σ2 ] if 0 < τ1 + τ2 < t ∧[g(t − τ1 ) + σ1 ]
11
= sup[inf {d ≥ 0|α(t − d) ≤ β(t − D)}] Finally, note that we can express f ⊗ g as minimum of 4 curves each of type ((δτk ⊗ Iσk ⊗ γ0,ρk ) ∧ δ0 ) as follows. f ⊗ g(t) = ((δτ1 ⊗ Iσ1 ⊗ γ0,ρ1 ) ∧ δ0 ) ⊗ ((δτ2 ⊗ Iσ2 ⊗ γ0,ρ2 ) ∧ δ0 ) = ((δτ1 ⊗ Iσ1 ⊗ γ0,ρ1 ) ∧ δ0 ) ∧ ((δτ2 ⊗ Iσ2 ⊗ γ0,ρ2 ) ∧ δ0 ) ∧((δτ1 +τ2 ⊗ Iσ1 +σ2 ⊗ γ0,ρ1 ) ∧ δ0 ) ∧((δτ1 +τ2 ⊗ Iσ1 +σ2 ⊗ γ0,ρ2 ) ∧ δ0 ) = f (t) ∧ g(t) ∧ (f (t − τ2 ) + σ2 ) ∧ (g(t − τ1 ) + σ1 ) The following figure illustrates the convolution of f and g.
t≥0 (∗)
= sup [inf {d ≥ 0|α(t − d) ≤ β(t − D)}]
t≥D (∗∗)
= sup [inf {d ≥ 0|α(D + t′ − d) ≤ β(t′ )}] t≥D
= sup[inf {d ≥ 0|α(D + t − d) ≤ β(t)}] t≥0
= sup[inf {d ≥ 0|α(t − (d − D)) ≤ β(t)}] t≥0
= sup[D + inf {d ≥ 0|α(t − d) ≤ β(t)}] t≥0
= D + sup[inf {d ≥ 0|α(t − d) ≤ β(t)}] t≥0
= D + hdev(α, β) (∗) holds since β(t − D) = 0 for t ≤ D, (∗∗) holds with t = D + t′ .
Lemma 4 (Delay Bound of an Arrival Curve and Minima of Several Service Curves). Let α be an arrival curve and β a n n V V service curve of the form β = βi . Then hdev(α, βi ) = i=1
n W
i=1
hdev(α, βi ).
beta_theta=T^pri.pdf
i=1
Fig. 10: Convolution of f and g.
Proof. hdev(α,
Note that the result also holds if ρ1 or ρ2 is infinite. Since β1 ⊗ β2 = δD1 +D2 ⊗ (f ⊗ g), we can now conclude that β1 ⊗ β2 ∈ MSLC and the proof is complete.
[δD2 ⊗ (
i=1 n V2
(δτ˜i ⊗ Iσ˜i ⊗ γ0,ρ˜i ) ∧ δ0 )]
i=1 (∗)
= δD1 +D2 ⊗ (
(
n V2
n V1
βi )
i=1
= sup[inf {d ≥ 0|α(t − d) ≤ t≥0 (∗)
Proof of Theorem 4. β1 ⊗ β 2 n V1 = [δD1 ⊗ ( (δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0 )]⊗
n V
= sup[
n W
=
t≥0 i=1 n W
=
i=1 t≥0 n W
n V
βi (t)}]
i=1
inf {d ≥ 0|α(t − d) ≤ βi (t)}]
sup[inf {d ≥ 0|α(t − d) ≤ βi (t)}] hdev(α, βi )
i=1
(∗) due to α ∈ F , i.e., a wide sense increasing function.
(δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0 )⊗
i=1
(δτ˜i ⊗ Iσ˜i ⊗ γ0,ρ˜i ) ∧ δ0 )
i=1 (∗∗)
= δD1 +D2 ⊗ (
n V1 nV2
((δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0 )⊗
i=1 j=1
((δτ˜j ⊗ Iσ˜j ⊗ γ0,ρ˜j ) ∧ δ0 )) n V1 nV2 (∗∗∗) = δD1 +D2 ⊗ ( (((δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0 )∧ i=1 j=1 ((δτ˜j ⊗ Iσ˜j ⊗ γ0,ρ˜j ) ∧ δ0 ) ∧ ((δτi +τ˜j ⊗ Iσi +σ˜j ⊗ γ0,ρi ) ∧ δ0 ) ∧((δτi +τ˜j ⊗ Iσi +σ˜j ⊗ γ0,ρ˜j ) ∧ δ0 ))). (∗) holds due to commutativity of ⊗, (∗∗) holds due to (f ∧ g) ⊗ h = (f ⊗ h) ∧ (g ⊗ h) (see [9]) and (∗ ∗ ∗) holds due to Lemma 2. Hence, we have shown that β1 ⊗ β2 ∈ MSLC and the proof is complete. Lemma 3 (Delay Bound of an Arrival Curve and Shifted Service Curve). Let α be an arrival curve and β a service curve and D ≥ 0. Then hdev(α, δD ⊗ β) = D + hdev(α, β). Proof. hdev(α, δD ⊗ β) = sup[inf {d ≥ 0|α(t − d) ≤ δD ⊗ β(t)}] t≥0
Lemma 5 (Delay Bound of Shaped Arrival Curve and MSLC Service Curve with n = 1 and D = 0). Let α = γb,r ∧ γL,R′ and β ∈ MSLC with n = 1 and D = 0, i.e., β = (δτ1 ⊗ Iσ1 ⊗ γ0,ρ1 ) ∧ δ0 , with L ≤ b, r < R′ , R′ ≥ ρ1 (if ρ1 < +∞) and r ≤ ρ1 . Then, hdev(α, β) = + − [σ1 −b] , if ρ1 < +∞ [τ1 · 1{σ1 ≥ b−L r+b} r ′ R −r b−L + [ ′ r+b−σ1 ] + R −r ρ1 τ1 · 1{ Rb−L ′ −r r+b≥σ1 } + − Rb−L ′ −r ] [σ1 −b]+ [τ1 · 1{σ1 ≥ b−L , if ρ1 = +∞ r+b} − r R′ −r + [σ −L] 1 + τ1 · 1{ b−L r+b≥σ } − ] R′ 1 ′ R −r
Proof. We first start with the assumption ρ1 < +∞ and note that Rb−L ′ −r r + b is the y-value of the inflection point of α. Case 1 (σ1 ≤ Rb−L ′ −r r + b): hdev can only be between the inflection value of α and the respective value of β since R′ ≥ b−L r+b−σ1 ′
ρ1 . This can be described as τ1 + R −r ρ1
− Rb−L ′ −r .
12
form δD ⊗ ((δτ1 ⊗ Iσ1 ⊗ γ0,ρ1 ) ∧ δ0 ). Then, vdev(α, β) = [b + Dr, b − σ1 + (D + τ1 )r]. Proof. vdev(α, β) can be computed as sup{α(u) − β(u)} u≥0 (∗)
= [α(D) − 0] ∨ [α(D + τ1 ) − β(D + τ1 )] = [α(D)] ∨ [α(D + τ1 ) − σ1 ] = [b + Dr] ∨ [b − σ1 + (D + τ1 )r] = [b + Dr, b − σ1 + (D + τ1 )r] (∗) since u = D or u = D + τ1 .
Fig. 11: Case 1 of the delay bound proof. Case 2 (σ1 > Rb−L ′ −r r + b): hdev can only be between the inflection point of β and the respective value of α as r ≤ ρ1 . Moreover, we have to guard this case also for negativity, as theoretically, α may not have any intersection with β. This can be described as [τ1 − σ1r−b ]+ . It is then easily verifiable, that both cases can be summarized [σ1 −b]+ as [τ1 · 1{σ1 ≥ b−L , τ1 · 1{ b−L r+b} − r+b≥σ1 } + r ′ ′ R −r
Fig. 12: Vertical deviation between α and β.
R −r
+ [ Rb−L ′ −r r+b−σ1 ] + − Rb−L ′ −r ] . ρ1
Finally, we now assume that ρ1 = +∞. Case 1 (σ1 ≤ Rb−L ′ −r r + b): If L > σ1 , then hdev = τ1 since + ′ R < +∞. Otherwise, hdev = [τ1 − σ1R−L ′ ] . b−L Case 2 (σ1 > R′ −r r + b): The delay bound is equal to [τ1 − σ1r−b ]+ . It is then again easily verifiable, that both cases can [σ1 −b]+ be summarized as [τ1 · 1{σ1 ≥ b−L , τ1 · r+b} − r ′ +
beta_theta=T^pri.pdf
R −r
[σ1 −L] + ] . 1{ b−L r+b≥σ1 } − R′ ′ R −r
Proof of Theorem 5. We divide the proof as follows: hdev(α, δD ⊗ β) = D + hdev(α, β) for any arrival curve α and service curve β (Lemma 3) n n V W βi ) = hdev(α, βi ) for any arrival curve • hdev(α,
Lemma 7 (Vertical Deviation of Arrival Curve and MSLC Service Curve equals Maximum of Vertical Deviations of Arrival Curve and MSLC with n = 1). Let α = γb,r and β ∈ n V MSLC of the form β = δD ⊗ ( (δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0 ) i=1 i=1,...,n
with βi = δD ⊗ ((δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0 ).
i=1
α and service curve β (Lemma 4) • hdev(α, βi ) = + − [σi −b] , [τi · 1{σi ≥ b−L r+b} r ′ R −r b−L [ ′ r+b−σi ]+ + R −r ρi τi · 1{ Rb−L ′ −r r+b≥σi } + − Rb−L ′ −r ] [σi −b]+ [τ · 1 − , b−L i {σ ≥ r+b} r i R′ −r + τi · 1{ b−L r+b≥σ } − [σi −L] ]+ R′ i R′ −r (Lemma 5)
u≥0 n V
= sup{α(u) − δD ⊗ ( u≥0 α=γb,r
=
((δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0 )(u))}
i=1
[b + Dr] ∨ sup{α(u + D) − ( u≥0
δ0 )(u))} if ρi < +∞
vdev(α, βi )
i=1
Proof. vdev(α, β) = sup{α(u) − β(u)}
•
i=1
n W
with 0 ≤ r ≤ min ρi . Then, vdev(α, β) =
= [b+Dr]∨sup{
n W
=
((δτi ⊗ Iσi ⊗ γ0,ρi ) ∧
i=1
α(u+D)−(((δτi ⊗Iσi ⊗γ0,ρi )∧δ0 )(u))}
u≥0 i=1 α=γb,r
n V
[b + Dr] ∨ sup{
n W
Dr + α(u) − (((δτi ⊗ Iσi ⊗ γ0,ρi ) ∧
u≥0 i=1
if ρi = +∞
δ0 )(u))} = [b + Dr] ∨ {Dr +
{sup α(u) − (((δτi ⊗ Iσi ⊗ γ0,ρi ) ∧
i=1 u≥0
δ0 )(u))}} Lemma 6
=
Hence, all in all, we obtain the claim. Lemma 6 (Backlog Bound Arrival Curve and MSLC Service Curve with n = 1). Consider an arrival curve with α = γb,r and a service curve β in MSLC with n = 1, i.e., β has the
n W
[b + Dr] ∨ {Dr +
= [b + Dr] ∨ =
n W
n W
n W
[b, b − σi + τi r]}
i=1
[b + Dr, b − σi + (D + τi )r]
i=1
[b + Dr, b − σi + (D + τi )r]
i=1
13
n W
=
vdev(α, βi )
i=1
Lemma 8 (Outputbound via Vertical Deviation for Arrival Curve and MSLC Service Curve). Let α = γb,r and β ∈ n V MSLC of the form β = δD ⊗ ( (δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0 ) with ′
If y ≤ σi , then the leftover for step i is lower bounded by δD ⊗(((δτi ⊗Iσi −y ⊗γ0,ρi −r )∧δ0 )∧((δθ−D ⊗I0 ⊗γ0,+∞ )∧δ0 )) for θ > D and δD ⊗ ((δτi ⊗ Iσi −y ⊗ γ0,ρi −r ) ∧ δ0 ) for θ ≤ D. If y > σi , then we have to compute the intersection of α(t−θ) and δD ⊗ ((δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0 ), so the leftover for step i is lower bounded by δD ⊗ ((δτi + y−σi ⊗ I0 ⊗ γ0,ρi −r ) ∧ δ0 ). ρi −r
i=1
0 ≤ r ≤ min ρi . Then, α (t) = α ⊘ β(t) = rt + vdev(α, β) i=1,...,n
for t ≥ 0. Proof. First of all, note that α ⊘ β(0) = sup{α(u) − β(u)} = u≥0
vdev(α, β). Now, let t > 0. Then, α ⊘ β(t) = sup{α(t + u) − β(u)} u≥0 α=γb,r ,t>0
=
sup{b + r(t + u) − β(u)} u≥0
β(0)=0
=
rt + sup{α(u) − β(u)} ∨ [b − β(0)] u>0
β(0)=0
=
rt + sup{α(u) − β(u)} ∨ [b] u>0
α(0)=β(0)=0
=
beta_theta=T^pri.pdf
rt + vdev(α, β) ∨ [b]
(∗)
= rt + vdev(α, β). (∗) since due to Lemma 6, vdev(α, β) ≥ b holds.
Fig. 13: Example for θ belonging to Case 1 of the leftover service curve proof.
Proof of Theorem 6. We divide the proof into several steps n W • vdev(α, β) = vdev(α, βi ) for α, β as above (see i=1
Lemma 7) vdev(α, βi ) = [b+Dr]∨[b−σi +(D +τi )r] (see Lemma 6) • α ⊘ β(t) = rt + vdev(α, β) for t ≥ 0 and α, β as above (see Lemma 8)
•
Case 2 (θ > D + τi − Rb−L ′ −r ): First assume θ ≥ D. Let b−L y = (θ + Rb−L −(D +τ ))·ρ +σ ′ −r i i i . If y ≥ R′ −r ·r +b, then the leftover for step i is lower bounded by δD ⊗ (((δθ−D+ b−L ⊗ R′ −r Iy−( b−L r+b) ⊗ γ0,ρi −r ) ∧ δ0 ) ∧ ((δθ−D ⊗ I0 ⊗ γ0,+∞ ) ∧ δ0 )). ′ R −r
If y < Rb−L ′ −r · r + b, then the intersection of α(t − θ) and δD ⊗ ((δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0 needs to be found which will b−L r+b−y ′
Lemma 9 (Leftover of Minima of Service Curves). For any n n V V arrival curve α and service curve β, ( βi )⊖θ α = (βi ⊖θ i=1
i=1
α) holds. Proof. First assume t > θ since otherwise the claim is trivial. n V We write βi (t) =: βj (t). i=1
If βj (t) ≤ α(t − θ), then [( α(t−θ)]+ = 0. Also
n V
n V
βi (t)) − α(t − θ)]+ = [βj (t) −
R −r be at time θ + Rb−L ′ −r + ρi −r is lower bounded by δD ⊗ ((δ
, so the leftover for step i b−L r+b−y ⊗ I0 ⊗ ′
R −r θ−D+ Rb−L ′ −r + ρ −r i
γ0,ρi −r ) ∧ δ0 ). Now, we assume θ ≤ D. Let y = (θ+ Rb−L ′ −r −(D+τi ))·ρi +σi . If y ≥ Rb−L r + b, then the leftover for step i is lower bounded ′ −r ⊗ I ⊗ γ0,ρi −r ) ∧ δ0 ). If by δD ⊗ ((δθ+ b−L b−L −D y−( ′ r+b) ′ R −r
R −r
y < Rb−L ′ −r r + b, then this is the same as in the case θ ≥ D.
i=1
[βi (t)−α(t−θ)]+ = 0 since [βj (t)−
i=1
α(t − θ)]+ = 0, [βi − α(t − θ)]+ ≥ 0. n V If βj (t) > α(t − θ), then [( βi (t)) − α(t − θ)]+ = βj (t) − α(t − θ) =
n V
i=1
[βi (t) − α(t − θ)]+ ≥ 0.
i=1
Proof of Theorem 7. The main idea is as follows. First, we consider the leftover per step 1 ≤ i ≤ n denoted by βi ⊖θ α ↑ and model its non-decreasing lower bound (βi ⊖θ α) with at least one MSLC curve. Then, we take the minimum over all these leftover steps according Lemma 9 to obtain the overall leftover curve. The leftover per step i with ρi < +∞ and its non-decreasing lower bound is computed follows: Case 1 (θ ≤ D + τi − Rb−L ′ −r ): Let y = ((D + τi ) − θ)r + b.
beta_theta=T^pri.pdf
Fig. 14: Example for θ belonging to Case 2 of the leftover service curve proof.
14
Lastly, we consider ρi = +∞. If θ ≤ D, the leftover for step i is lower bounded by δD ⊗ ((δτi ⊗ I0 ⊗ γ0,+∞ ) ∧ δ0 ). If D ≤ θ ≤ D + τi , the leftover for step i is lower bounded by δD ⊗ (((δτi ⊗ I0 ⊗ γ0,+∞ ) ∧ δ0 ) ∧ ((δθ−D ⊗ I0 ⊗ γ0,+∞ ) ∧ δ0 )). If θ > D + τi , the leftover for step i is lower bounded by δD ⊗ ((δθ−D ⊗ I0 ⊗ γ0,+∞ ) ∧ δ0 ). Hence, the leftover for step i is lower bounded by δD ⊗ size(i) V
(
j=1
((δτj′ ⊗Iσj′ ⊗γ0,ρ′j )∧δ0 )) with size(i) ∈ {1, 2} depending
on the specific case. Hence, the lower bound non-decreasing n size(i) V V leftover service curve has the form δD ⊗( ((δτj′ ⊗Iσj′ ⊗ i=1 j=1
γ0,ρ′j ) ∧ δ0 )) ∈ MSLC due to (f ⊗ g) ∧ h = (f ∧ g) ⊗ h (see [9]) which holds for any functions f, g, h ∈ F. Proof of Corollary 1. We first start by arguing that only θ ≥ D is relevant as lower values of θ yield a smaller leftover service curve. Indeed, for such values it is clear from the proof of Theorem 7 that θ ↑ yields y ↓ for Case 1 and y ↑ for Case 2, so a larger leftover service for the step i at least until θ = D is reached. Hence, it is sufficient for the analysis to consider θ ≥ D only. Next, we can rewrite the non-decreasing lower bound leftover per step i in the proof of Theorem 7 in a more compact way which completes the proof.
[14] A. Bouillard, “Admission shaping with network calculus,” IEEE Networking Letters, 2024. [15] L. Lenzini, L. Martorini, E. Mingozzi, and G. Stea, “Tight end-toend per-flow delay bounds in fifo multiplexing sink-tree networks,” Performance Evaluation, vol. 63, no. 9-10, pp. 956–987, 2006. [16] L. Bisti, L. Lenzini, E. Mingozzi, and G. Stea, “Numerical analysis of worst-case end-to-end delay bounds in fifo tandem networks,” Real-Time Systems, vol. 48, no. 5, pp. 527–569, 2012. [17] M. Boyer, “Half-modeling of shaping in fifo net with network calculus,” in 18th International Conference on Real-Time and Network Systems, 2010, pp. 59–68. [18] C.-S. Chang, Performance guarantees in communication networks. Springer Science & Business Media, 2012. [19] F. Geyer, A. Scheffler, and S. Bondorf, “Network calculus with flow prolongation – a feedforward fifo analysis enabled by ml,” IEEE Transactions on Computers, vol. 72, no. 1, pp. 97–110, 2023. [20] A. Scheffler, J. B. Schmitt, and S. Bondorf, “Searching for upper delay bounds in FIFO multiplexing feedforward networks,” in the 30th International Conference on Real-Time Networks and Systems (RTNS 2022), June 2022. [21] A. Scheffler, S. Bondorf, and J. B. Schmitt, “Short paper: Analyzing fifomultiplexing tandems with network calculus and a tailored grid search,” in the 34th International Teletraffic Congress (ITC 2022), September 2022. [22] A. Scheffler, M. Fögen, and S. Bondorf, “The deterministic network calculus analysis: Reliability insights and performance improvements,” in Proc. of the IEEE International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD), 2018.
R EFERENCES [1] IEEE, “802.1q–ieee standard for local and metropolitan area networks– bridges and bridged networks,” 2018. [Online]. Available: https: //standards.ieee.org/standard/802-1Q-2018.html [2] R. L. Cruz, “A calculus for network delay. i. network elements in isolation,” IEEE Transactions on information theory, vol. 37, no. 1, pp. 114–131, 2002. [3] ——, “A calculus for network delay. ii. network analysis,” IEEE Transactions on information theory, vol. 37, no. 1, pp. 132–141, 2002. [4] A. Bouillard, “Trade-off between accuracy and tractability of network calculus in fifo networks,” Performance Evaluation, vol. 153, p. 102250, 2022. [5] A. Bouillard and G. Stea, “Exact worst-case delay in fifo-multiplexing feed-forward networks,” IEEE/ACM Transactions on Networking, vol. 23, no. 5, pp. 1387–1400, 2014. [6] L. Lenzini, E. Mingozzi, and G. Stea, “A methodology for computing end-to-end delay bounds in fifo-multiplexing tandems,” Performance Evaluation, vol. 65, no. 11-12, pp. 922–943, 2008. [7] A. Scheffler and S. Bondorf, “Network calculus for bounding delays in feedforward networks of FIFO queueing systems,” in Proc. of the International Conference on Quantitative Evaluation of Systems (QEST), August 2021. [8] A. Bouillard, M. Boyer, and E. Le Corronc, Deterministic network calculus: From theory to practical implementation. John Wiley & Sons, 2018. [9] J.-Y. Le Boudec and P. Thiran, Network calculus: a theory of deterministic queuing systems for the internet. Springer LNCS, 2001, vol. 2050. [10] L. Thomas, J.-Y. Le Boudec, and A. Mifdaoui, “On cyclic dependencies and regulators in time-sensitive networks,” in 2019 IEEE Real-Time Systems Symposium (RTSS). IEEE, 2019, pp. 299–311. [11] J. Grieu, “Analyse et évaluation de techniques de commutation ethernet pour l’interconnexion des systèmes avioniques,” PhD Thesis, 2004. [12] A. Mifdaoui and T. Leydier, “Beyond the accuracy-complexity tradeoffs of compositional analyses using network calculus for complex networks,” in 10th International Workshop on Compositional Theory and Technology for Real-Time Embedded Systems (co-located with RTSS 2017), 2017, pp. pp–1. [13] S. M. Tabatabaee, M. Boyer, J.-Y. Le Boudec, and J. Migge, “Efficient and accurate handling of periodic flows in time-sensitive networks,” in 2023 IEEE 29th Real-Time and Embedded Technology and Applications Symposium (RTAS). IEEE, 2023, pp. 303–315.
Alexander Scheffler received the MSc degree in computer science from TU (now RPTU) Kaiserslautern, Germany, in 2020. From 2020 to 2023, he worked as a research associate at the Faculty of Computer Science, Ruhr University Bochum, Germany. In 2022, he was a visiting researcher at Huawei in France. Since 2024, he has been working as an embedded software engineer in the semiconductor industry. His primary field of research is the Network Calculus methodology.