Perspectives on network calculus
- 13 August 2012
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGCOMM Computer Communication Review
- Vol. 42 (4), 311-322
- https://doi.org/10.1145/2377677.2377747
Abstract
ACM Sigcomm 2006 published a paper [26] which was perceived to unify the deterministic and stochastic branches of the network calculus (abbreviated throughout as DNC and SNC) [39]. Unfortunately, this seemingly fundamental unification---which has raised the hope of a straightforward transfer of all results from DNC to SNC---is invalid. To substantiate this claim, we demonstrate that for the class of stationary and ergodic processes, which is prevalent in traffic modelling, the probabilistic arrival model from [26] is quasi-deterministic, i.e., the underlying probabilities are either zero or one. Thus, the probabilistic framework from [26] is unable to account for statistical multiplexing gain, which is in fact the raison d'être of packet-switched networks. Other previous formulations of SNC can capture statistical multiplexing gain, yet require additional assumptions [12], [22] or are more involved [14], [9] [28], and do not allow for a straightforward transfer of results from DNC. So, in essence, there is no free lunch in this endeavor. Our intention in this paper is to go beyond presenting a negative result by providing a comprehensive perspective on network calculus. To that end, we attempt to illustrate the fundamental concepts and features of network calculus in a systematic way, and also to rigorously clarify some key facts as well as misconceptions. We touch in particular on the relationship between linear systems, classical queueing theory, and network calculus, and on the lingering issue of tightness of network calculus bounds. We give a rigorous result illustrating that the statistical multiplexing gain scales as Ω(√ N ), as long as some small violations of system performance constraints are tolerable. This demonstrates that the network calculus can capture actual system behavior tightly when applied carefully. Thus, we positively conclude that it still holds promise as a valuable systematic methodology for the performance analysis of computer and communication systems, though the unification of DNC and SNC remains an open, yet quite elusive task.Keywords
This publication has 34 references indexed in Scilit:
- Stochastically bounded burstiness for communication networksIEEE Transactions on Information Theory, 2000
- Performance bounds for flow control protocolsIEEE/ACM Transactions on Networking, 1999
- Majorizing measures: the generic chainingThe Annals of Probability, 1996
- Wide area traffic: the failure of Poisson modelingIEEE/ACM Transactions on Networking, 1995
- Effective Bandwidths for Stationary SourcesProbability in the Engineering and Informational Sciences, 1995
- On the self-similar nature of Ethernet traffic (extended version)IEEE/ACM Transactions on Networking, 1994
- A calculus for network delay. I. Network elements in isolationIEEE Transactions on Information Theory, 1991
- Networks of queues with customers of different typesJournal of Applied Probability, 1975
- Open, Closed, and Mixed Networks of Queues with Different Classes of CustomersJournal of the ACM, 1975
- Values of Mills' Ratio of Area to Bounding Ordinate and of the Normal Probability Integral for Large Values of the ArgumentThe Annals of Mathematical Statistics, 1941