pith. sign in

arxiv: 2604.18370 · v1 · submitted 2026-04-20 · 💻 cs.NI

Sub-additive service curves in the Network Calculus analysis

Anne Bouillard This is my paper

Pith reviewed 2026-05-10 03:34 UTC · model grok-4.3

classification 💻 cs.NI
keywords network calculusservice curvessub-additive functionsfeedback systemsperformance boundsnon-negative functionsstability
0
0 comments X

The pith

Sub-additive functions allow non-negative service curves to model all feedback control cases in network calculus without instability.

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

This paper demonstrates that detailed examination of sub-additive service curves makes it possible to perform network calculus analysis using only non-negative functions, even in complex feedback scenarios. A prior approach permitting negative values is shown to produce unsound results with stability problems. Sympathetic readers would care because reliable worst-case performance bounds depend on sound mathematical assumptions in the function space. The work provides a corrected analysis under standard non-negative constraints.

Core claim

The author establishes that in all cases where negative values were proposed for tractability, a conventional analysis using non-negative sub-additive service curves is feasible. Furthermore, the analysis of complex feedback control systems using functions with negative values is unsound and exhibits stability issues, for which a corrected version is supplied when possible.

What carries the argument

Sub-additive service curves, which satisfy f(x + y) ≤ f(x) + f(y) and remain non-negative, carrying the argument by enabling composition of network elements while preserving performance bounds.

If this is right

  • Feedback control systems can be analyzed safely with non-negative functions.
  • The use of negative values leads to invalid stability in feedback models.
  • Conventional hypotheses suffice for all mentioned network cases.
  • A corrected analysis replaces the unsound one in prior work.

Where Pith is reading between the lines

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

  • If the sub-additive property is central, similar restrictions might apply to other function classes in performance modeling.
  • Tools implementing network calculus could be simplified by enforcing non-negativity from the start.
  • Stability verification becomes a key step when extending function spaces in control analyses.

Load-bearing premise

That the sub-additive property of service curves can be maintained under the non-negative constraint without losing the ability to model the feedback systems described in the prior work.

What would settle it

Finding a concrete feedback network example where non-negative sub-additive curves fail to give valid delay bounds while negative-value curves succeed stably.

Figures

Figures reproduced from arXiv: 2604.18370 by Anne Bouillard.

Figure 1
Figure 1. Figure 1: Example of a tandem network with some arrival and departure processes of flow [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Example of arrival process A and one arrival curve α for A. When α is drawn from any point x of A, A must remain below s + α. We now model a server. (min,plus) service curve: consider a generic server (no exponent), crossed by the set of flows I. For each flow i ∈ I, we denote by Ai and Di , its cumulative arrival and departure processes. Let us define A = P i∈I Ai and D = P i∈I Di , respectively the aggre… view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of a service curve: (a) a (min, plus) service curve: since there is a non-zero latency, [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Processes and worst-case performance. The delay of data arriving at time t is d(t) = inf{d | D(t + d) ≥ A(t)}, and the maximum delay is dmax = supt≥0 inf{d | D(t + d) ≥ A(t)} ≤ supt≥0 inf{d | β(t + d) ≥ α(t)}: dmax is bounded by the maximum horizontal distance between α and β. This is illustrated in [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: When the residual service curve can have negative values, there is no guarantee for the departure [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Example of a departure process with a sub-additive service curve. First, [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Sub-additive (min, plus) service curves are not weakly strict service curve: With [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Pure delay (min, plus) do now guarantee the service of flow 2, the lower priority flow. [PITH_FULL_IMAGE:figures/full_fig_p012_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Tandem analysis: delay non-conventional analysis vs. improved PMOO analysis. [PITH_FULL_IMAGE:figures/full_fig_p016_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: An elementary feedback loop. 16 [PITH_FULL_IMAGE:figures/full_fig_p016_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: 0 time data 2W W β ∗ φW (β ∗ φW ) 2 (β ∗ φW ) ∗ 0 time data W 2W β ∗ φW (β ∗ φW ) 2 (β ∗ φW ) ∗ βth ≤ (β ∗ φW ) ∗ [PITH_FULL_IMAGE:figures/full_fig_p017_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Interpretation of the system of Fig. 10 as an open-system. [PITH_FULL_IMAGE:figures/full_fig_p017_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Tandem network with a complex feedback structure. [PITH_FULL_IMAGE:figures/full_fig_p019_13.png] view at source ↗
Figure 15
Figure 15. Figure 15: Counter-example for the analysis of a feedback control network. [PITH_FULL_IMAGE:figures/full_fig_p021_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Tandem network with a complex feedback structure, where each window controls one flow. [PITH_FULL_IMAGE:figures/full_fig_p023_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: Open-loop version of the network of Figure 13. [PITH_FULL_IMAGE:figures/full_fig_p023_17.png] view at source ↗
Figure 18
Figure 18. Figure 18: Nested tandem network with a nested feedback structure. [PITH_FULL_IMAGE:figures/full_fig_p024_18.png] view at source ↗
Figure 20
Figure 20. Figure 20: Interleaved network, with two feedback loops. The first loop controls flow 1 and 2, while the [PITH_FULL_IMAGE:figures/full_fig_p025_20.png] view at source ↗
Figure 21
Figure 21. Figure 21: Maximal set of windows for a possible analysis with blind multiplexing, and, below the [PITH_FULL_IMAGE:figures/full_fig_p026_21.png] view at source ↗
read the original abstract

Network Calculus is a theoretical model that aims at providing upper bounds of worst-case performance (such as delay or buffer occupancy). This is a mathematical framework that handles both network modeling and network analysis. As such it has requirements regarding the space of functions needed for a safe analysis. Namely, the functions need to be non-negative, as they model a quantity of data. This results in some pitfall for the analysis, where hypothesis matter. A recent paper by Hamscher et al. states that allowing functions with negative values can also lead to a valid analysis, in cases that would be untractable with the non-negative assumption results, especially when feedback control is present in the system. In this paper, we show that, on the contrary, a more conventional analysis is possible in all the mentioned cases. The key is a detailed analysis of sub-additive functions. Second, we show that the analysis of complex feedback control systems, presented by Hamscher et al. in a second paper that uses functions with negative values, is unsound and has stability issues. We give a corrected analysis, when possible, with conventional hypotheses.

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 / 2 minor

Summary. The paper claims that Network Calculus service curves can be analyzed using sub-additive functions under the standard non-negative constraint in all cases cited from Hamscher et al., including feedback control systems. It argues that a detailed examination of sub-additive properties enables conventional analysis without negative values, and that the negative-value approach in Hamscher et al.'s second paper is unsound due to stability issues, for which it provides a corrected non-negative model.

Significance. If the derivations and corrections hold, the result would be significant for Network Calculus by confirming that the non-negative function space remains sufficient for complex systems, avoiding physically invalid negative data quantities, and clarifying the role of sub-additivity in preserving valid performance bounds.

major comments (2)
  1. [Critique of negative-value analysis] The argument that the negative-value analysis has stability issues (mentioned in the abstract and presumably developed in the critique section) requires a concrete counter-example or explicit derivation showing divergence or invalid bounds; without it, the claim that the analysis is unsound rests on general properties rather than a load-bearing demonstration.
  2. [Corrected analysis section] In the corrected non-negative model for the complex feedback system, it is unclear whether the sub-additive property is preserved without altering the modeled behavior; a direct comparison of the original (negative) service curve to the corrected one, including verification that the same delay/buffer bounds are recovered, is needed to support the claim that conventional analysis suffices.
minor comments (2)
  1. [Abstract] The abstract refers to 'a second paper' by Hamscher et al. without a full citation; adding the reference here would aid readers.
  2. [Introduction] Notation for service curves and sub-additivity could be introduced with a brief reminder in the introduction for accessibility.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. The comments highlight areas where additional explicit demonstrations would strengthen the presentation of our results on non-negative sub-additive service curves and the issues with negative-value analyses in Network Calculus. We will revise the manuscript accordingly to provide the requested clarifications and examples while preserving the core contributions.

read point-by-point responses

  1. Referee: [Critique of negative-value analysis] The argument that the negative-value analysis has stability issues (mentioned in the abstract and presumably developed in the critique section) requires a concrete counter-example or explicit derivation showing divergence or invalid bounds; without it, the claim that the analysis is unsound rests on general properties rather than a load-bearing demonstration.

    Authors: We agree that an explicit counter-example would make the stability issues more concrete and load-bearing. In the revised manuscript, we will add a dedicated subsection with a simple feedback system example. We will derive the negative service curve, show how it leads to diverging delay bounds under iteration (violating stability), and contrast it with the bounded non-negative case. This will directly demonstrate the unsoundness beyond general properties. revision: yes

  2. Referee: [Corrected analysis section] In the corrected non-negative model for the complex feedback system, it is unclear whether the sub-additive property is preserved without altering the modeled behavior; a direct comparison of the original (negative) service curve to the corrected one, including verification that the same delay/buffer bounds are recovered, is needed to support the claim that conventional analysis suffices.

    Authors: We will expand the corrected analysis section to include a direct side-by-side comparison. This will present the original negative service curve, the derived non-negative sub-additive equivalent, explicit verification that sub-additivity holds, and numerical computation of the resulting delay and buffer bounds to confirm equivalence (or improvement) without changing the underlying system dynamics or performance guarantees. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's derivation proceeds by re-deriving performance bounds from the algebraic properties of sub-additive functions under the standard non-negative constraint and by exhibiting a corrected non-negative model for the feedback example. These steps rely on direct mathematical manipulation of function properties rather than any self-definition, parameter fitting presented as prediction, or load-bearing self-citation. The critique of the external Hamscher et al. work is independent and does not reduce the paper's own claims to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The central claim rests on the assumption that service curves remain sub-additive and non-negative while still modeling the same systems; no free parameters, invented entities, or additional axioms are visible in the abstract.

pith-pipeline@v0.9.0 · 5488 in / 1097 out tokens · 18884 ms · 2026-05-10T03:34:50.651834+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  1. [1]

    Cruz, Clayton Okino, and Rajendran Rajan

    Rajeev Agrawal, Rene L. Cruz, Clayton Okino, and Rajendran Rajan. Performance bonds for flow control protocols.IEEE/ACM Trans. Netw., 7(3):310–323, 1999

    work page 1999

  2. [2]

    Composition of service curves in network calculus

    Anne Bouillard. Composition of service curves in network calculus. pages 35–42, 2011

    work page 2011

  3. [3]

    Individual service curves for bandwidth-sharing policies using network calculus

    Anne Bouillard. Individual service curves for bandwidth-sharing policies using network calculus. IEEE Networking Letters, 3(2):80–83, 2021

    work page 2021

  4. [4]

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

    Anne Bouillard. Trade-off between accuracy and tractability of network calculus in FIFO networks. Perform. Evaluation, 153:102250, 2022

    work page 2022

  5. [5]

    Imperfect bandwidth-sharing policies using network calculus

    Anne Bouillard. Imperfect bandwidth-sharing policies using network calculus. InIFIP Networking Conference, IFIP Networking 2023, Barcelona, Spain, June 12-15, 2023, pages 1–9. IEEE, 2023. 26

    work page 2023

  6. [6]

    ISTE, 2018

    Anne Bouillard, Marc Boyer, and Euriell Le Corronc.Deterministic Network Calculus: From Theory to Practical Implementation. ISTE, 2018

    work page 2018

  7. [7]

    Optimal routing for end-to- end guarantees: theprice ofmultiplexing

    Anne Bouillard, Bruno Gaujal, Sebastien Lagrange, and Éric Thierry. Optimal routing for end-to- end guarantees: theprice ofmultiplexing. In Peter W.Glynn, editor,Proceedings of VALUETOOLS, ACM International Conference Proceeding Series, page 62. ICST/ACM, 2007

    work page 2007

  8. [8]

    Computation of a (min, +) multi-dimensional convolution for end-to-end performance analysis

    Anne Bouillard, Laurent Jouhet, and Eric Thierry. Computation of a (min, +) multi-dimensional convolution for end-to-end performance analysis. In John S. Baras and Costas Courcoubetis, editors, Proceedings of VALUETOOLS, page 68. ICST/ACM, 2008

    work page 2008

  9. [9]

    Service curves in Network Calculus: dos and don’ts

    Anne Bouillard, Laurent Jouhet, and Eric Thierry. Service curves in Network Calculus: dos and don’ts. Research Report RR-7094, INRIA, 2009

    work page 2009

  10. [10]

    Comparison of different classes of service curves in network calculus

    Anne Bouillard, Laurent Jouhet, and Éric Thierry. Comparison of different classes of service curves in network calculus. In Jörg Raisch, Alessandro Giua, Stéphane Lafortune, and Thomas Moor, editors, WODES, pages 306–311. IFAC, 2010

    work page 2010

  11. [11]

    Tight Performance Bounds in the Worst-Case Analysis of Feed-Forward Networks

    Anne Bouillard, Laurent Jouhet, and Éric Thierry. Tight Performance Bounds in the Worst-Case Analysis of Feed-Forward Networks. InIEEE INFOCOM, pages 1316–1324. IEEE, 2010

    work page 2010

  12. [12]

    Anne Bouillard, Paul Nikolaus, and Jens B. Schmitt. Unleashing the power of paying multiplexing only once in stochastic network calculus. In D. Manjunath, Jayakrishnan Nair, Niklas Carlsson, Edith Cohen, and Philippe Robert, editors,SIGMETRICS/PERFORMANCE ’22, pages 117–118. ACM, 2022

    work page 2022

  13. [13]

    Anne Bouillard, Linh T. X. Phan, and Samarjit Chakraborty. Lightweight modeling of complex state dependencies in stream processing systems. In15th IEEE RTAS, pages 195–204. IEEE Computer Society, 2009

    work page 2009

  14. [14]

    Exact worst-case delay for FIFO-multiplexing tandems

    Anne Bouillard and Giovanni Stea. Exact worst-case delay for FIFO-multiplexing tandems. In Bruno Gaujal, Alain Jean-Marie, Eduard A. Jorswieck, and Alexandre Seuret, editors,ICST/IEEE Valuetools, pages 158–167. 2012

    work page 2012

  15. [15]

    Boyer, N

    M. Boyer, N. Navet, X. Olive, and É. Thierry. The PEGASE project: precise and scalable temporal analysis for aerospace communication systems with Network Calculus. InISOLA’10, pages 122–136, 2010

    work page 2010

  16. [16]

    Impact on credit freeze before gate closing in cbs and gcl inte- gration into tsn

    Marc Boyer and Hugo Daigmorte. Impact on credit freeze before gate closing in cbs and gcl inte- gration into tsn. In RTNS ’19, page 80–89. Association for Computing Machinery, 2019

    work page 2019

  17. [17]

    Bounding the delays of themppanetwork-on-chipwithnetworkcalculus: Modelsandbenchmarks.Performance Evaluation, 143:102124, 2020

    Marc Boyer, Amaury Graillat, Benoît Dupont de Dinechin, and Jörn Migge. Bounding the delays of themppanetwork-on-chipwithnetworkcalculus: Modelsandbenchmarks.Performance Evaluation, 143:102124, 2020

    work page 2020

  18. [18]

    Deficit round robin with network cal- culus

    Marc Boyer, Giovanni Stea, and William Mangoua Sofack. Deficit round robin with network cal- culus. In Bruno Gaujal, Alain Jean-Marie, Eduard A. Jorswieck, and Alexandre Seuret, editors, ICST/IEEE Valuetools, pages 138–147. ICST/IEEE, 2012

    work page 2012

  19. [19]

    A general per-flow service curve for GPS

    Almut Burchard and Jörg Liebeherr. A general per-flow service curve for GPS. In30th International Teletraffic Congress, ITC 2018, Vienna, Austria, September 3-7, 2018 - Volume 2, pages 31–36. IEEE, 2018

    work page 2018

  20. [20]

    TNCS, Springer- Verlag, 2000

    Cheng-Shang Chang.Performance Guarantees in Communication Networks. TNCS, Springer- Verlag, 2000

    work page 2000

  21. [21]

    Rene L. Cruz. A calculus for network delay, part I: network elements in isolation.IEEE Trans. Inf. Theory, 37(1):114–131, 1991

    work page 1991

  22. [22]

    Rene L. Cruz. A calculus for network delay, part II: network analysis.IEEE Trans. Inf. Theory, 37(1):132–141, 1991. 27

    work page 1991

  23. [23]

    Rene L. Cruz. Quality of Service Guarantees in Virtual Circuit Switched Networks.IEEE Journal on selected areas in communication, 13:1048–1056, 1995

    work page 1995

  24. [24]

    Anja Hamscher, Vlad-Cristian Constantin, and Jens B. Schmitt. Extending network calculus to deal with min-plus service curves in multiple flow scenarios. In IEEE RTAS 2024, pages 95–107, 2024

    work page 2024

  25. [25]

    Anja Hamscher, Lukas Wildberger, and Jens B. Schmitt. Per-flow performance guarantees in net- worked systems with complex feedback structures. In Renato Mancuso, editor, ECRTS 2025, volume 335 ofLIPIcs, pages 18:1–18:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025

    work page 2025

  26. [26]

    Window flow control in computer communication networks.Computers & In- dustrial Engineering, 12(4):291–298, 1987

    Mohammad Ilyas. Window flow control in computer communication networks.Computers & In- dustrial Engineering, 12(4):291–298, 1987

    work page 1987

  27. [27]

    Evaluating performance in on-chip networks with network calculus

    Md Amirul Islam and Giovanni Stea. Evaluating performance in on-chip networks with network calculus. In2025 ICEET, pages 1–6, 2025

    work page 2025

  28. [28]

    Springer-Verlag, 2001

    Jean-Yves Le Boudec and Patrick Thiran.Network Calculus: A Theory of Deterministic Queuing Systems for the Internet, volume LNCS 2050. Springer-Verlag, 2001. revised version 4, May 10, 2004

    work page 2050

  29. [29]

    Lenzini, L

    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, 63(9-10):956–987, 2006

    work page 2006

  30. [30]

    J. M. McManus and K. W. Ross. Video-on-demand over ATM: Constant-rate Transmission and Transport.IEEE J.Sel. A. Commun., 14(6):1087–1098, September 1996

    work page 1996

  31. [31]

    Schmitt, Frank A

    Jens B. Schmitt, Frank A. Zdarsky, and Markus Fidler. Delay Bounds under Arbitrary Multiplexing: When Network Calculus Leaves You in the Lurch... InIEEE INFOCOM, pages 1669–1677. IEEE, 2008

    work page 2008

  32. [32]

    Schmitt, Frank A

    Jens B. Schmitt, Frank A. Zdarsky, and Ivan Martinovic. Improving Performance Bounds in Feed- Forward Networks by Paying Multiplexing Only Once. In Falko Bause and Peter Buchholz, editors, (MMB 2008), Dortmund, Germany, pages 13–28. VDE Verlag, 2008

    work page 2008

  33. [33]

    Interleaved weighted round-robin: A network calculus analysis

    Seyed Mohammadhossein Tabatabaee, Jean-Yves Le Boudec, and Marc Boyer. Interleaved weighted round-robin: A network calculus analysis. ITC 2020: 64-72, 2020

    work page 2020

  34. [34]

    Nancy: An efficient parallel network calculus library.SoftwareX, 19:101178, 2022

    Raffaele Zippo and Giovanni Stea. Nancy: An efficient parallel network calculus library.SoftwareX, 19:101178, 2022. 28

    work page 2022