1
Beyond Virtual Delay: Improving Packet Delay Bound in Network Calculus
arXiv:2606.13631v1 [cs.PF] 11 Jun 2026
Yuming Jiang Norwegian University of Science and Technology, Trondheim, Norway
Abstract—In network calculus, a fundamental result is the classical delay bound given by the horizontal deviation between the arrival and service curves. While widely used, the classical bound is derived from the notion of virtual delay. In this work, we first show that the maximum packet delay is always upper-bounded by the maximum virtual delay, revealing inherent conservatism when applying the virtual-delay-based bound to packet delay. Motivated by this insight, we revisit packet delay analysis and derive a new packet delay bound that requires no assumptions beyond the arrival and service curves. Specializing the new bound to a system with leaky-bucket arrival curve and rate-latency service curve shows strict improvement over the classical bound, which is further demonstrated through a case study in time-sensitive networking (TSN). Index Terms—Network Calculus, arrival curve, service curve, virtual delay, packet delay, delay bound.
I. I NTRODUCTION Network calculus provides a powerful framework for analyzing worst-case performance guarantees in communication networks [1] [2] [3]. By modeling traffic arrivals through arrival curves and system capabilities through service curves, network calculus enables the derivation of bounds on key performance metrics such as backlog and delay. A fundamental result is the classical delay bound given by the horizontal deviation between the arrival and service curves [1] [2] [3]. The classical delay bound is derived from the notion of virtual delay, which represents the time required to serve all traffic that has arrived up to a given time. If the only available information is the arrival and service curve characterizations, the bound is tight for virtual delay (Theorem 1.4.4, [2]). If the system is FIFO, the delay of a packet can be connected to the virtual delay at the time of its arrival. This not only justifies the use of virtual delay as a proxy for packet delay but also using the classical bound on virtual delay as a bound on packet delay e.g. in [4] and references therein. In this work, however, we prove that the maximum packet delay is inherently upper-bounded by the maximum virtual delay. This implies that the classical bound can be conservative when applied to packet delay. In addition, it suggests that tighter bounds may be obtained by directly working on packet delay without the intermediate use of virtual delay. This idea is consistent with the max-plus version of network calculus [1] and has been exploited in the literature to find improved bounds for packet delay. Specifically, the work [5] shows that for a service curve network element, if its transmission rate is known, an improved delay bound can be derived. In [6], it is shown that if the input traffic is also known to have a packet-level arrival curve, the bound can be further improved.
In this work, we also conduct analysis directly on packet delay without relying on virtual delay. However, unlike [5] [6], we investigate whether an improved packet delay bound can be obtained without introducing additional assumptions. Specifically, we ask whether a tighter packet delay bound can be derived using only the arrival and service curves so as to preserve the generality and abstraction, as the classical virtual-delay-based bound. We answer this question in the affirmative. The new packet delay bound is exemplified as being strictly tighter than the classical bound in practical systems, which is also illustrated through a case study in timesensitive networking (TSN). In the next section, the system model and the necessary background on network calculus are introduced, including the classical delay bound. Then we prove the relationship between the maximum virtual delay and the maximum packet delay. The new bound is derived and exemplified for a system with leaky-bucket arrival curve and rate-latency service curve in Section IV. In Section V, a TSN case study is conducted to quantitatively compare the bounds. Finally, the conclusion is made in Section VI. II. S YSTEM M ODEL AND THE C LASSICAL D ELAY B OUND A. The System We consider a FIFO system in a packet-switched network. The system may be a single network element or a network of elements. Its input process is a sequence of packets. The input process may consist of multiple flows. Packets may be queued within the system but are not dropped. By convention, a packet is considered to have arrived to (respectively departed from) the system if and only if its last bit has arrived (respectively departed). For each packet n = 1, 2, 3, . . . , let a(n), d(n) and l(n) denote its arrival time, departure time and length (in bits), respectively. In addition, let A(t) represent the cumulative input (in bits) entering the system and A∗ (t) the cumulative output (in bits) from the system, up to time t (excluded). The input has arrival curve α and the system provides to the input service curve β. By arrival curve and service curve definitions [2], the input satisfies, ∀0 ≤ s ≤ t, A(s, t) ≡ A(t) − A(s) ≤ α(t − s),
∀0 ≤ s ≤ t
and the service provided by the system ensures A∗ (t) ≥ A ⊗ β(t) ≡ inf {A(s) + β(t − s)}, 0≤s≤t
∀t ≥ 0
where α and β are non-negative wide-sense increasing functions with β(0) = 0, and ⊗ is the min-plus convolution operation.
2
B. Packet Delay, Virtual Delay, and the Classical Bound The delay D(n) of packet n(≥ 1) in the system is D(n) = d(n) − a(n).
(1)
The virtual delay D̃(t) at time t(≥ 0) is defined as [2] D̃(t) = inf{τ ≥ 0 : A(t) ≤ A∗ (t + τ )}.
(2)
Pn In addition, we mustPhave (A∗ )↓ ( k=1 l(k)) > d(n) n because A∗ (t) reaches k=1 l(k) only after packet n has finished its service. Consequently, we have a(n)+ + D̃max > d(n) or by letting ϵ → 0, we have D̃max ≥ d(n)−a(n). Since this relation holds for all n ≥ 1, Theorem 1 is proved. With Theorem 1, Corollary 1 is immediate.
A fundamental result in network calculus is that the virtual delay D̃(t) at any time t is upper-bounded by the horizontal deviation between the arrival curve α and the service curve β [2], which is denoted as h(α, β) and referred to as the classical delay bound in this work, i.e., ∀t ≥ 0,
Corollary 1. An upper bound on the maximum virtual delay is also an upper bound on the maximum packet delay.
D̃(t) ≤ h(α, β) ≡ sup inf{τ : α(t) ≤ β(t + τ )}.
Corollary 2. The delay D(n) of any packet n(≥ 1) and the maximum packet delay Dmax are both upper-bounded by the classical delay bound, i.e. the horizontal deviation h(α, β).
(3)
t≥0
If the arrival curve α and the service curve β are the only available information and α is sub-additive with α(0) = 0, the bound on virtual delay is tight (Theorem 1.4.4, [2]), i.e. a system with arrival curve α and service curve β can be constructed where the bound can be reached by virtual delay. III. R ELATIONSHIP BETWEEN M AXIMUM PACKET D ELAY AND M AXIMUM V IRTUAL D ELAY Consider the maximum packet delay Dmax and the maximum virtual delay D̃max , which are, respectively, D
max
D̃max
=
max D(n)
(4)
=
sup D̃(t)
(5)
n≥1
Since the horizontal deviation is time-independent, we have D̃max ≤ h(α, β), which, together with Corollary 1 and Dmax ≥ D(n), ∀n ≥ 1 from (4), leads to Corollary 2.
IV. I MPROVING PACKET D ELAY B OUND Theorem 1 implies that the classical virtual-delay bound may overestimate when applied to packet delay. This gap motivates direct analysis at the packet-level to reduce conservatism. A. A New Packet Delay Bound Theorem 2 is from direct analysis at the packet-level, where a new bound is introduced without additional assumptions other than the arrival and service curves. Its potential improvement over the classical bound is demonstrated in Sec. IV-B.
t≥0
Theorem 1 reveals a relationship between the two quantities. In its proof as well as in the rest of the paper, the lower and upper pseudo-inverse functions, f ↓ and f ↑ , of a wide-sense increasing function f , are respectively defined as [1] [7]: ↓
f (y)
≡
inf{x ≥ 0 : f (x) ≥ y}
↑
≡
inf{x ≥ 0 : f (x) > y}
f (y)
Theorem 1. For a FIFO system, if the delay is bounded, i.e. D(n) < ∞ for ∀n ≥ 1, the maximum packet delay is upperbounded by the maximum virtual delay, i.e., Dmax ≤ D̃max . Proof. Consider any packet n ≥ 1. Note that at a(n), there may be multiple concurrent arrivals. Without loss of generality, suppose n is the last among them and focus on studying its delay, since by FIFO, this packet experiences at least the same or generally higher delay than the other packets. Define a(n)+ as the right limit Pnof a(n), i.e. a(n)+ = a(n)+ϵ, ϵ → 0. Clearly, A(a(n)+ ) ≥ k=1 l(k). By the definition of D̃max , we have ∗
l(k) ≤ A(a(n)+ ) ≤ A (a(n)+ + D̃
k=1
Taking the lower pseudo-inverse gives a(n)+ + D̃max ≥ (A∗ )↓ (
n X
k=1
l(k))
max
D(n) ≤ sup{β ↑ (v) − α↓ (v + l(n))}.
(6)
v≥0
In [7], a collection of their properties can be found, including, if f (x) ≥ y, f ↓ (y) ≤ x and if f (x) > y, f ↑ (y) ≤ x.
n X
Theorem 2. For a FIFO system, if the input has arrival curve α and the system provides to the input service curve β, then, for any packet n ≥ 1, its delay D(n) satisfies
)
Pn−1 Proof. 1 Consider any packet n ≥ 1. Let L(n) ≡ m=0 l(m) and L(m, n) ≡ L(n) − L(m). Note that l(n) is not included in L(n) and L(0) = 0 by convention. In addition, packet 0 is a virtual packet with a(0) = d(0) = l(0) = 0. First, focus on a(n). Since multiple packets may arrive at Pna(n) and n is one of them, we have A(a(m), a(n)+ ) ≥ k=m l(k) = L(m, n) + l(n), for any 0 ≤ m ≤ n. In addition, the arrival curve tells that for any 0 ≤ m ≤ n, A(a(m), a(n)+ ) ≤ α(a(n)+ − a(m)). Combining them gives L(m, n) + l(n) ≤ A(a(m), a(n)+ ) ≤ α(a(n)+ − a(m)). Taking the lower pseudo-inverse yields α↓ (L(m, n) + l(n)) ≤ a(n)+ − a(m) and hence for any (0 ≤)m(≤ n) a(n)+ ≥ a(m) + α↓ (L(m, n) + l(n)).
(7)
Next, focus on d(n). The service curve definition indicates that there exists some time s, (0 ≤ s ≤ d(n)), such that A∗ (d(n)) ≥ A(s)+β(d(n)−s) [2]. In addition, by definition, 1 The proof can also be obtained by extending the results in [1]. In particular, step (7) extends Lemma 6.2.8 (ii) in [1], by following the same proof but letting t = τ (n)+ there to obtain (7) with l(n) included. Step (8) follows from Lemma 6.3.2 and Step (9) from Theorem 6.3.4 (i) in [1].
3
A∗ (t) represents the amount of departure up to t (excluded), so A∗ (d(n)) does not include the packet(s) finishing at d(n), among which is packet n, and A∗ (d(n)) < L(n). Hence, L(n)
>
∗
A (d(n)) ≥ A(s) + β(d(n) − s).
Let m = min{k : a(k − 1) < s}, which implies a(m − 1) < s ≤ a(m). The first part a(m − 1) < s suggests that by s (excluded), at least packets 1, . . . , m − 1 have arrived, so A(s) ≥ L(m). The second part s ≤ a(m) together with that β is non-decreasing gives β(d(n) − s) ≥ β(d(n) − a(m)). Together, we now have L(n) > L(m) + β(d(n) − a(m)), or L(m, n) > β(d(n) − a(m)). Taking the upper inverse yields d(n) − a(m) ≤ β ↑ (L(m, n)). and hence, d(n)
≤
a(m) + β ↑ (L(m, n)).
(8)
Finally, focus on D(n) = d(n) − a(n). Since a(n)+ = a(n) + ϵ, letting ϵ → 0 and combining (7) and (8), we get D(n)
≤
β ↑ (L(m, n)) − α↓ (L(m, n) + l(n))
≤
sup{β ↑ (v) − α↓ (v + l(n))}
(9)
v≥0
From Proposition 1, since α↓ is non-decreasing [7], Corollary 4 can be verified. Corollary 4. For the system considered in Proposition 1, the delay D(n) of any packet n(≥ 1) and the maximum packet delay Dmax are both upper-bounded by lmin σ +T − ≡ ∆N ew . (12) R R As a comparison, for the system considered in Proposition 1, the classical delay bound from virtual delay analysis becomes σ +T ≡∆ (13) R with which, we can rewrite ∆N ew as lmin . R Clearly the new bound ∆N ew is tighter, since in real networks, the length of a packet is always lower-bounded e.g. by the header size. This leads to the following remark. ∆N ew = ∆ −
Remark 1: The improvement of ∆N ew over ∆ is strictly positive in practical systems.
which completes the proof. Since α↓ is non-decreasing (Lemma 10.1, [7]), Corollary 3 follows immediately from Theorem 2. Corollary 3. The delay D(n) of any packet n(≥ 1) and the maximum packet delay Dmax are both upper-bounded by sup{β ↑ (v) − α↓ (v + lmin )}
It can be shown that the supremum of β ↑ (v) − α↓ (v + l(n)) is σ−l(n) + T , which completes the proof. R
(10)
V. C ASE S TUDY In this section, we conduct a case study to compare the delay bounds quantitatively. It is based on an example configuration for a time-aware Talker in time-sensitive networking (TSN), as described in Annex U: TSN Configuration Examples, [8].
v≥0
A. The Case The transmission rate of the Talker is c = 100 Mb/s. The Talker has two queues, a TSN queue and a non-TSN B. Exemplification queue, where the TSN queue has non-preemptive strict priority To demonstrate the potential improvement of the new bound over the non-TSN queue. When the TSN queue is enabled, a over the classical bound, we consider in the following that the non-TSN frame can interfere and this interference is up to arrival curves are of the leaky-bucket type [2] and the service τinterf erence = 123.36 µs, assuming maximum frame size curves are of the rate-latency type [2]. 1522 bytes for the non-TSN queue. Proposition 1. For a FIFO system, suppose the input has The Talker supports two TSN streams, Stream J and Stream leaky-bucket arrival curve α(t) = ρt + σ, and the service has K. Both generate frames periodically. For Stream J, the frame rate-latency service curve β(t) = R(t − T )+ , where (x)+ ≡ size is lJ = 1500 bytes and the interval is 500 µs. For Stream max{x, 0}. If ρ ≤ R, the delay D(n) of any packet n(≥ 1) K, the frame size is lK = 1000 bytes, and the interval is also satisfies: 500 µs. The two streams form the input to the TSN queue, and l(n) σ lmax = 1500 bytes and lmin = 1000 D(n) ≤ +T − (11) hence for the TSN queue, max max R R bytes. In addition, lJ = lJmin = 1500 bytes and lK = min Proof. Consider any packet n(≥ 1) and apply α(t) = ρt + lK = 1000 bytes. σ and β(t) = R(t − T )+ to Theorem 2. The lower inverse For this case, it can be verified that Stream J has leakyfunction α↓ (v + l(n)) of α(t) = ρt + σ is: bucket arrival curve αJ (t) = ρJ t + σJ with ρJ = 24 Mb/s and σJ = lJ = 1500 bytes, and Stream K has arrival curve α↓ (v + l(n)) = inf{t ≥ 0 : ρt + σ ≥ v + l(n)} αK (t) = ρK t+σK with ρK = 16 Mb/s and σK = lK = 1000 + v + l(n) − σ bytes. The aggregate input to the TSN queue has arrival curve = ρ α(t) = ρt + σ with ρ = ρJ + ρK = 40 Mb/s and σ = and the upper inverse function β ↑ of β(t) = R(t − T )+ is lJ + lK = 2500 bytes. In addition, the system provides+to the v TSN-queue latency-rate servicemax curve β(t) = R(t − T ) with β ↑ (v) = inf{t(≥ 0) : R(t − T )+ > v} = R + T . Hence l R = c = 100 Mb/s and T = T cSN + τinterf erence = 243.36 ( v + T − v+l(n)−σ , if v + l(n) ≥ σ µs (e.g. see Sec. 2.4.2, [1]). With these, the classical bound ρ β ↑ (v)−α↓ (v+l(n)) = R v + T, if v + l(n) < σ ∆ and the new bound ∆N ew are readily calculated. R where lmin denotes the minimum packet length.
4
B. Related Delay Bounds Note that the case description contains more specific information than α and β. This information can be exploited in delay bound analysis. For instance, Proposition 1 from Theorem 2 can be generalized to Corollary 5 by exploiting the information of each individual flow, whose proof follows from focusing only on packets of the considered flow in (11). Corollary 5. If the input consists of multiple P flows, each flow i has arrival curve αi = ρi t + σi and i ρi ≤ R, the delay D(ni ) of any packet ni in flow i satisfies: P l(ni ) i σi D(ni ) ≤ +T − R R and the maximum packet delay of flow i is upper-bounded by lmin EW ≡ ∆N ∆− i . i R
(14)
where limin denotes the minimum packet length of flow i. In addition, the description contains information that enables the application of delay bounds from [5] [6]. Specifically it is proved in [5] that, for a FIFO element with rate-latency service curve R(t − T )+ , if the transmission rate c(≥ R) is known, the maximum packet delay of any flow i is upper-bounded by: 1 1 ∆ − limin ( − ) ≡ ∆i[5] .
(15) R c If the TSN traffic specification of each flow is also known, it is further proved in [6] that the maximum packet delay of any flow i is upper-bounded by: 1 1 − ) ≡ ∆i[6] (16) R c where limax denotes the maximum packet length of flow i. EW Comparing (14) with (15) and (16), it is clear that ∆N = i min min l l [5] [6] 1 N EW max 1 i i ∆i − c and ∆i = ∆i − R + li ( R − c ). They EW imply that ∆N is always tighter than ∆i[5] but its tightness i in comparison with ∆i[6] is influenced by limin , limax , R and EW c. In addition, comparing (14) with (12), it is clear ∆N = i limin −lmin min min min N ew . Since l = min {l } ≤ l , ∀i, we ∆ − i i i R EW always have ∆N ≤ ∆N ew . It is worth highlighting that i EW ∆N does not rely on the additional information, e.g. c, i required for ∆i[5] and ∆i[6] . In addition, ∆N ew does not rely EW on the information of individual flows required for ∆N . i To give a more direct impression, the bounds are compared quantitatively for the considered case below. ∆ − limax (
C. Quantitative Comparison Table I summarizes and compares the delay bounds for the considered case, which are arranged in two categories. One contains the new bound ∆N ew and the classical bound ∆ that do not require or make use of traffic information of the constituent flows. The other category contains the new bound EW ∆N and the bound ∆i[5] from [5] and the bound ∆i[6] from i [6], which make use of information of the constituent flows. As shown in Table I, the two new delay bounds ∆N ew EW and ∆N are more than 25% tighter in their categories. i In particular, Table I demonstrates that the classical bound ∆
TABLE I C OMPARISON OF DELAY BOUNDS ( IN µs) FOR S TREAMS J AND K Stream J K
∆N ew 363.36 363.36
∆ 443.36 443.36
EW ∆N i 323.36 363.36
∆i[5] 443.36 443.36
∆i[6] 443.36 443.36
can be significantly conservative, which confirms the finding in Theorem 1. In addition, it shows that with information about EW individual flows, ∆N can improve ∆N ew particularly i EW for Stream J. Furthermore, ∆N also exhibits significant i [5] [6] improvement over ∆i and ∆i for the considered case. Note that both streams have the frame generation interval 500 µs. This implies that within each such interval, only two frames are generated, one from each stream. In addition, all bounds less than 500 µs imply that the two frames finish before the next such frames are generated. With these, the worst case is that both frames arrive at the same time just before the transmission of a non-TSN frame, and the worstcase delay becomes lcJ + lK c + Tinterf erence = 323.36 µs. Comparing with Table I, while all bounds are valid, most are not tight. Recall that ∆, ∆ [5] and ∆ [6] have been shown to be tight under their conditions. We hence remark the following. Remark 2: A delay bound that is tight under certain conditions may not be tight if additional information is available. VI. C ONCLUSION We revisited delay bound analysis in network calculus and showed that the maximum packet delay is upper-bounded by the maximum virtual delay. Building on this insight, we developed an analysis that directly targets packet delay without relying on virtual delay and derived a new packet delay bound that requires no additional assumption beyond arrival and service curves. We further specialized the new bound for a system with leaky-bucket arrival curve and rate-latency service curve, showing that the new bound is strictly tighter. A TSN case study demonstrated that the new bound can produce a reduction of more than 25% compared to the classical virtual-delay-based bound. In addition, the case study indicates that the tightness of a delay bound depends on the available information and cannot be universally generalized. R EFERENCES [1] C.-S. Chang, Performance Guarantees in Communication Networks. Springer-Verlag, 2000. [2] J.-Y. Le Boudec and P. Thiran, Network Calculus: A Theory of Deterministic Queueing Systems for the Internet. Springer-Verlag, 2001. [3] A. Bouillard, M. Boyer, and E. Le Corronc, Deterministic Network Calculus: From Theory to Practical Implementation. Wiley-ISTE, 2018. [4] L. Zhao, P. Pop, and S. Steinhorst, “Quantitative performance comparison of various traffic shapers in time-sensitive networking,” IEEE Trans. Network and Service Management, vol. 19, no. 3, pp. 2899–2928, 2022. [5] E. Mohammadpour, E. Stai, and J.-Y. Le Boudec, “Improved delay bound for a service curve element with known transmission rate,” IEEE Networking Letters, vol. 1, no. 4, pp. 156–159, 2019. [6] ——, “Improved network-calculus nodal delay-bounds in time-sensitive networks,” IEEE/ACM Trans. Networking, vol. 31, pp. 2902–2917, 2023. [7] J. Liebeherr, “Duality of the max-plus and min-plus network calculus,” Foundations and Trends in Networking, vol. 11, pp. 139–282, 2017. [8] “IEEE standard for local and metropolitan area networks–bridges and bridged networks,” IEEE Std 802.1Q-2022 (Revision of IEEE Std 802.1Q2018), pp. 1–2163, 2022.