Beyond Virtual Delay: Improving Packet Delay Bound in Network Calculus

A tighter packet delay bound without extra assumptions

Yuming Jiang· 2026· DOI 10.48550/arXiv.2606.13631

The core problem

Network calculus provides a foundational framework for deterministic performance guarantees in communication networks. A central result is the classical delay bound, computed as the horizontal deviation between the arrival curve α (t) and the service curve β (t) : D_{classical} = t \geq 0 sup in f {τ \geq 0 : α (t) \leq β (t + τ)} This bound is derived from the notion of *virtual delay*, which assumes a fluid model where bits are served instantaneously. However, in real packet-switched networks, packets are discrete units, and the virtual delay may not accurately reflect the actual packet delay. The author identifies a fundamental conservatism: for FIFO systems, the maximum packet delay is always upper-bounded by the maximum virtual delay. This gap motivates the need for a more precise packet delay bound that does not rely on virtual delay assumptions.

For the leaky-bucket and rate-latency case, the classical bound is: D_{classical} = T + \frac{σ}{R} The new bound is shown to be strictly smaller: D_{new} = T + \frac{σ - L _{max}}{R} + \frac{L _{max}}{R} \cdot 1_{{σ > 0}} or more precisely, the improvement is at least the maximum packet length L_{max} divided by the service rate R, under certain conditions. A case study in Time-Sensitive Networking (TSN) demonstrates the practical impact: for typical TSN parameters, the new bound reduces the delay bound by up to 15%, allowing tighter network design and resource allocation. The results are validated through simulations and numerical examples.

Network calculus provides a foundational framework for deterministic performance guarantees in communication networks. A central result is the classical delay bound, computed as the horizontal deviation between the arrival curve α (t) and the service curve β (t) :

D_{classical} = t \geq 0 sup in f {τ \geq 0 : α (t) \leq β (t + τ)}

The new bound reveals that the classical virtual-delay-based bound is inherently conservative for packetized traffic. The improvement stems from accounting for the fact that a packet is served only when its last bit arrives, and the service curve may provide additional capacity that is not captured by the virtual delay of the last bit. The author discusses the implications for network calculus theory and practice. The new bound requires no additional assumptions, making it widely applicable. However, it is specific to FIFO systems; extending it to non-FIFO or multi-class systems remains an open challenge. The paper also notes that the bound can be further tightened if more information about packet arrival patterns is available. The TSN case study highlights the potential for better quality-of-service guarantees in industrial and automotive networks.

CS practitioners and researchers

Opening member content…