pith. machine review for the scientific record. sign in

arxiv: 2605.08944 · v1 · submitted 2026-05-09 · 💻 cs.NI

Recognition: 2 theorem links

· Lean Theorem

LUDB++: Enabling LUDB for the Analysis of Shaped Feedforward FIFO Networks using Network Calculus

Alexander Scheffler
Authors on Pith no claims yet

Pith reviewed 2026-05-12 01:45 UTC · model grok-4.3

classification 💻 cs.NI
keywords network calculusFIFO networksshaperslatency boundsLUDBfeedforward networksdelay analysistime-sensitive networking
0
0 comments X

The pith

LUDB++ extends the least upper delay bound method to include shaper constraints and compute tighter latency bounds for feedforward FIFO networks.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops LUDB++ to extend the existing least upper delay bound approach in network calculus so that it accounts for shapers that limit traffic rates and bursts. This extension produces less pessimistic delay estimates for flows in non-cyclic FIFO networks where shapers may sit inside the network or at endpoints. A sympathetic reader would care because such bounds directly support latency guarantees required in time-sensitive systems. Evaluation across 130 configurations on line and tree topologies shows LUDB++ improves accuracy over the original LUDB and beats the exponential linear program method in most cases by up to 9.13 percent.

Core claim

The paper establishes that modifying the least upper delay bound analysis to incorporate the rate and burst limits imposed by shapers at each location yields more accurate upper bounds on end-to-end latency for flows in feedforward FIFO networks. The original LUDB method ignored these shaping effects and therefore produced looser bounds. Numerical tests confirm that the new LUDB++ bounds are tighter than those from standard LUDB and, in the majority of tested setups, tighter than those obtained from the exponential linear program approach.

What carries the argument

LUDB++ is the extended least-upper-delay-bound computation that folds shaping parameters (rate and burst) into the arrival and service curve constraints used for each flow and each server.

If this is right

  • Tighter bounds allow network designers to allocate smaller buffers and schedules while still meeting latency targets.
  • The method applies to both simple line topologies and branched tree topologies common in time-sensitive networking.
  • In most of the 130 tested cases LUDB++ produces better results than the exponential linear program method.
  • Resource utilization improves because overestimation of required capacity is reduced.
  • The technique supports direct analysis of networks that already contain rate limiters.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar shaping adjustments could be applied to other network-calculus bound techniques that currently ignore shapers.
  • If shaper parameters contain uncertainty the bounds would need additional margins not computed here.
  • The accuracy gains suggest that earlier designs without shaping awareness were unnecessarily conservative.
  • The approach could be tested on larger networks or mixed traffic patterns to check scalability.

Load-bearing premise

The analysis assumes that shaping parameters are known exactly at every shaper and that the network topology contains no feedback loops.

What would settle it

A concrete falsifier would be a simulation or hardware measurement on one of the evaluated topologies where the observed worst-case latency exceeds the bound produced by LUDB++.

Figures

Figures reproduced from arXiv: 2605.08944 by Alexander Scheffler.

Figure 1
Figure 1. Figure 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 resul… view at source ↗
Figure 2
Figure 2. Figure 2: MSLC with n = 1. Definition 8 (MSLC). The service curve β ∈ MSLC is defined as β = δD ⊗ Vn i=1 ((δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0). 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 ∈ MSLC, i.e., β1 = δD1 ⊗ ( nV1 i=1 (δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0) and β2 = δD2 ⊗ ( nV2 i=1 (δτ˜i ⊗ Iσ˜i ⊗ γ0,ρ˜i ) ∧ δ0). Th… view at source ↗
Figure 3
Figure 3. Figure 3: LUDB++ example for two servers with one crossflow. [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 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% an… view at source ↗
Figure 5
Figure 5. Figure 5: Relative delays to ELP for different shaper configurations, different utilizations and different [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Relative delays to ELP for different shaper configurations, different utilizations and different [PITH_FULL_IMAGE:figures/full_fig_p008_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Tree with N = 3. The (maximal) utilization for this topology is u = N·r R . LUDB++ beats ELP for all of the 36 settings. The min￾imal, 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 E… view at source ↗
Figure 8
Figure 8. Figure 8: Relative delays to ELP for different shaper configurations, different utilizations and different [PITH_FULL_IMAGE:figures/full_fig_p009_8.png] view at source ↗
Figure 9
Figure 9. Figure 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… view at source ↗
Figure 10
Figure 10. Figure 10: Convolution of f and g. 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. Proof of Theorem 4. β1 ⊗ β2 = [δD1 ⊗ ( nV1 i=1 (δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0)]⊗ [δD2 ⊗ ( nV2 i=1 (δτ˜i ⊗ Iσ˜i ⊗ γ0,ρ˜i ) ∧ δ0)] (∗) = δD1+D2 ⊗ ( nV1 i=1 (δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0)⊗ ( nV2 i=1 (δτ˜i ⊗ Iσ˜i ⊗ γ0,ρ˜i ) ∧ δ0) (∗∗) = δD… view at source ↗
Figure 11
Figure 11. Figure 11: Case 1 of the delay bound proof. Case 2 (σ1 > b−L R′−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 − σ1−b r ] +. It is then easily verifiable, that both cases can be summarized as [τ1 · 1{σ1≥ b−L R′−r r+b} −… view at source ↗
Figure 12
Figure 12. Figure 12: Vertical deviation between α and β. Lemma 7 (Vertical Deviation of Arrival Curve and MSLC Ser￾vice Curve equals Maximum of Vertical Deviations of Arrival Curve and MSLC with n = 1). Let α = γb,r and β ∈ MSLC of the form β = δD ⊗ ( Vn i=1 (δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0) with 0 ≤ r ≤ min i=1,...,n ρi . Then, vdev(α, β) = Wn i=1 vdev(α, βi) with βi = δD ⊗ ((δτi ⊗ Iσi ⊗ γ0,ρi ) ∧ δ0). Proof. vdev(α, β) = sup u≥0 {… view at source ↗
Figure 13
Figure 13. Figure 13: Example for θ belonging to Case 1 of the leftover service curve proof. Case 2 (θ > D + τi − b−L R′−r ): First assume θ ≥ D. Let y = (θ+ b−L R′−r −(D+τi))·ρi+σi . If y ≥ b−L R′−r ·r+b, then the leftover for step i is lower bounded by δD ⊗ (((δθ−D+ b−L R′−r ⊗ Iy−( b−L R′−r r+b) ⊗ γ0,ρi−r) ∧ δ0) ∧ ((δθ−D ⊗ I0 ⊗ γ0,+∞) ∧ δ0)). If y < b−L R′−r · r + b, then the intersection of α(t − θ) and δD ⊗ ((δτi ⊗ Iσi ⊗ γ… view at source ↗
Figure 14
Figure 14. Figure 14: Example for θ belonging to Case 2 of the leftover service curve proof [PITH_FULL_IMAGE:figures/full_fig_p013_14.png] view at source ↗
read the original 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%.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript extends the Least Upper Delay Bound (LUDB) method from Network Calculus to incorporate traffic shapers (rate and burst constraints) in feedforward FIFO networks, producing LUDB++. It evaluates the approach on 130 configurations of line and tree topologies and reports that LUDB++ yields tighter latency bounds than plain LUDB and, in most cases, improves upon the Exponential Linear Program (ELP) method by up to 9.13%.

Significance. If the derivation correctly preserves valid upper bounds while tightening them, LUDB++ would supply a lighter-weight alternative to ELP for analyzing shaped TSN networks under the feedforward assumption. The scale of the evaluation (130 configurations) is a positive feature that allows direct numerical comparison across methods.

major comments (2)
  1. [Evaluation section (130 configurations)] The central claim that LUDB++ produces 'more accurate' bounds rests on numerical tightness versus LUDB and ELP, yet the evaluation provides no cross-validation against simulated worst-case latencies or exact analysis on the same topologies. Without this check, it is impossible to confirm that the incorporation of shaping parameters does not introduce an unsound relaxation that invalidates the upper-bound guarantee.
  2. [Abstract and Evaluation] The abstract and evaluation description supply no derivation steps showing how shaping (rate and burst) is folded into the LUDB equations, nor any error bars or sensitivity analysis on the reported 9.13% margin. This omission makes it impossible to assess whether the improvement is load-bearing or an artifact of the specific topologies chosen.
minor comments (1)
  1. [Methodology] Notation for shaped arrival curves and service curves should be introduced with explicit equations early in the methodology section to aid readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript extending LUDB to shaped feedforward FIFO networks. We address the major comments point by point below, providing clarifications on the theoretical soundness and outlining revisions to improve presentation and analysis.

read point-by-point responses

  1. Referee: [Evaluation section (130 configurations)] The central claim that LUDB++ produces 'more accurate' bounds rests on numerical tightness versus LUDB and ELP, yet the evaluation provides no cross-validation against simulated worst-case latencies or exact analysis on the same topologies. Without this check, it is impossible to confirm that the incorporation of shaping parameters does not introduce an unsound relaxation that invalidates the upper-bound guarantee.

    Authors: The incorporation of shaping preserves the upper-bound property because LUDB++ extends the original LUDB linear program by adding standard network calculus arrival-curve constraints that model the shaper's rate and burst limits at each hop. These constraints tighten the feasible set of arrival processes without relaxing any worst-case assumptions, so the optimized solution remains a valid least upper delay bound. The full derivation appears in Section 3. We agree that simulation cross-validation would be valuable; however, exact worst-case simulation for the evaluated topologies is computationally intractable. We will add a dedicated paragraph in the revised evaluation section explaining the theoretical soundness and the practical barriers to simulation. revision: partial

  2. Referee: [Abstract and Evaluation] The abstract and evaluation description supply no derivation steps showing how shaping (rate and burst) is folded into the LUDB equations, nor any error bars or sensitivity analysis on the reported 9.13% margin. This omission makes it impossible to assess whether the improvement is load-bearing or an artifact of the specific topologies chosen.

    Authors: The derivation of shaping integration is given in full in Section 3, where the LUDB equations are updated to include shaper-induced arrival curves. We will revise the abstract to include a concise statement of this extension. The 9.13% figure is the maximum observed improvement over ELP across the 130 deterministic configurations; because each result is exact for its parameter set, error bars are not applicable. We will add a sensitivity analysis subsection to the evaluation that varies utilization, burst sizes, and topology depth to demonstrate that the gains are consistent rather than topology-specific artifacts. revision: yes

Circularity Check

0 steps flagged

LUDB++ extends standard NC FIFO analysis with shaper constraints; no derivation reduces to fitted inputs or self-citation by construction

full rationale

The paper defines LUDB++ by incorporating known shaper rate/burst parameters into the existing LUDB methodology for feedforward FIFO networks using standard network calculus operations (arrival curves, service curves, and delay bound computations). The 130-configuration evaluation compares the resulting numerical upper bounds against LUDB and ELP but does not fit parameters to the target result or rename a known pattern; the comparison is external. No load-bearing step equates the claimed tighter bounds to the inputs by definition, and the feedforward/shaper assumptions are stated explicitly rather than smuggled via self-citation. The derivation chain remains self-contained against external NC benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no equations or modeling details, so free parameters, axioms, and invented entities cannot be enumerated.

pith-pipeline@v0.9.0 · 5508 in / 1089 out tokens · 29992 ms · 2026-05-12T01:45:58.541894+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    802.1q–ieee standard for local and metropolitan area networks– bridges and bridged networks,

    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

    work page 2018

  2. [2]

    A calculus for network delay. i. network elements in isolation,

    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

    work page 2002

  3. [3]

    A calculus for network delay. ii. network analysis,

    ——, “A calculus for network delay. ii. network analysis,”IEEE Transactions on information theory, vol. 37, no. 1, pp. 132–141, 2002

    work page 2002

  4. [4]

    Trade-off between accuracy and tractability of network calculus in fifo networks,

    A. Bouillard, “Trade-off between accuracy and tractability of network calculus in fifo networks,”Performance Evaluation, vol. 153, p. 102250, 2022

    work page 2022

  5. [5]

    Exact worst-case delay in fifo-multiplexing feed-forward networks,

    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

    work page 2014

  6. [6]

    A methodology for computing end-to-end delay bounds in fifo-multiplexing tandems,

    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

    work page 2008

  7. [7]

    Network calculus for bounding delays in feedforward networks of FIFO queueing systems,

    A. Scheffler and S. Bondorf, “Network calculus for bounding delays in feedforward networks of FIFO queueing systems,” inProc. of the International Conference on Quantitative Evaluation of Systems (QEST), August 2021

    work page 2021

  8. [8]

    Bouillard, M

    A. Bouillard, M. Boyer, and E. Le Corronc,Deterministic network calculus: From theory to practical implementation. John Wiley & Sons, 2018

    work page 2018

  9. [9]

    Le Boudec and P

    J.-Y . Le Boudec and P. Thiran,Network calculus: a theory of deter- ministic queuing systems for the internet. Springer LNCS, 2001, vol. 2050

    work page 2001

  10. [10]

    On cyclic dependencies and regulators in time-sensitive networks,

    L. Thomas, J.-Y . Le Boudec, and A. Mifdaoui, “On cyclic dependencies and regulators in time-sensitive networks,” in2019 IEEE Real-Time Systems Symposium (RTSS). IEEE, 2019, pp. 299–311

    work page 2019

  11. [11]

    Analyse et ´evaluation de techniques de commutation ethernet pour l’interconnexion des syst `emes avioniques,

    J. Grieu, “Analyse et ´evaluation de techniques de commutation ethernet pour l’interconnexion des syst `emes avioniques,”PhD Thesis, 2004

    work page 2004

  12. [12]

    Beyond the accuracy-complexity trade- offs of compositional analyses using network calculus for complex networks,

    A. Mifdaoui and T. Leydier, “Beyond the accuracy-complexity trade- offs of compositional analyses using network calculus for complex networks,” in10th International Workshop on Compositional Theory and Technology for Real-Time Embedded Systems (co-located with RTSS 2017), 2017, pp. pp–1

    work page 2017

  13. [13]

    Efficient and accurate handling of periodic flows in time-sensitive networks,

    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

    work page 2023

  14. [14]

    Admission shaping with network calculus,

    A. Bouillard, “Admission shaping with network calculus,”IEEE Net- working Letters, 2024

    work page 2024

  15. [15]

    Tight end-to- end per-flow delay bounds in fifo multiplexing sink-tree networks,

    L. Lenzini, L. Martorini, E. Mingozzi, and G. Stea, “Tight end-to- end per-flow delay bounds in fifo multiplexing sink-tree networks,” Performance Evaluation, vol. 63, no. 9-10, pp. 956–987, 2006

    work page 2006

  16. [16]

    Numerical analysis of worst-case end-to-end delay bounds in fifo tandem networks,

    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

    work page 2012

  17. [17]

    Half-modeling of shaping in fifo net with network calculus,

    M. Boyer, “Half-modeling of shaping in fifo net with network calculus,” in18th International Conference on Real-Time and Network Systems, 2010, pp. 59–68

    work page 2010

  18. [18]

    Chang,Performance guarantees in communication networks

    C.-S. Chang,Performance guarantees in communication networks. Springer Science & Business Media, 2012

    work page 2012

  19. [19]

    Network calculus with flow prolongation – a feedforward fifo analysis enabled by ml,

    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

    work page 2023

  20. [20]

    Searching for upper delay bounds in FIFO multiplexing feedforward networks,

    A. Scheffler, J. B. Schmitt, and S. Bondorf, “Searching for upper delay bounds in FIFO multiplexing feedforward networks,” inthe 30th International Conference on Real-Time Networks and Systems (RTNS 2022), June 2022

    work page 2022

  21. [21]

    Short paper: Analyzing fifo- multiplexing tandems with network calculus and a tailored grid search,

    A. Scheffler, S. Bondorf, and J. B. Schmitt, “Short paper: Analyzing fifo- multiplexing tandems with network calculus and a tailored grid search,” inthe 34th International Teletraffic Congress (ITC 2022), September 2022

    work page 2022

  22. [22]

    The deterministic network calculus analysis: Reliability insights and performance improvements,

    A. Scheffler, M. F ¨ogen, and S. Bondorf, “The deterministic network calculus analysis: Reliability insights and performance improvements,” inProc. of the IEEE International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD), 2018. Alexander Schefflerreceived the MSc degree in computer science from TU (now RPTU) Kai...

    work page 2018