Stochastic Network Calculus: From Theory to Applications
Jorg Liebeherr (University of Toronto, Canada)
Summary:
Current applications in the design of smart grid systems, as well as in the certification of aircraft data networks have broadened interest in network calculus methodologies. Network calculus was conceived in the 1990s, as an analytical tool for the provisioning of network services with deterministic performance guarantees. The main advantage over other analytical approaches is that end-to-end performance metrics, e.g., the delay experienced on a network path of multiple nodes, are easily obtained. However, the worst-case analysis associated with deterministic guarantees has created the misconception that network calculus largely overestimates resource requirements. More recently, probabilistic extensions of network calculus, referred to as stochastic network calculus, have been able to capture statistical multiplexing gain. This makes network calculus an attractive tool for economies of scale, such as data centers or smart grids.
The objective of this tutorial is to give an overview of the techniques of the deterministic and stochastic network calculus, without assuming prior knowledge or familiarity with its methods. The approach is to present network calculus as a systems theory for communication and electrical power distribution networks. An emphasis will be placed on the state-of-the-art of the stochastic network calculus, its potential and limitations, as well as application scenarios.
Outline:
1. A Network Calculus Primer
- Buffered links
- Envelopes and service curves
- Min-plus algebra primer
- Performance bounds for multi-node networks
- Case study: Bandwidth estimation
2. Stochastic Network Calculus
- Statistical multiplexing gain
- Statistical envelopes and sample path envelopes
- Statistical end-to-end analysis
- Assessment of the state-of-the-art (beyond hype and myths)
3. Application areas
- Wireless networks
- Data centers
- Smart grids
Biography of the presenter:
Jorg Liebeherr received the Ph.D. degree in Computer Science from the Georgia Institute of Technology in 1991. After a Postdoc at the University of California, Berkeley, he joined the Department of Computer Science at the University of Virginia in 1992. Since Fall 2005, he is with the Department of Electrical and Computer Engineering of the University of Toronto. He was Editor-in-Chief of IEEE Network in 1999-2000, and served on the editorial board of IEEE/ACM Transactions on Networking, as well as the boards of other journals. He was co-recipient of a best paper award at ACM Sigmetrics 2005. He is a Fellow of the IEEE. He has a long standing research interest in network performance analysis, especially, approaches of the stochastic network calculus. Since 2004, he has been teaching courses on network calculus at the undergraduate and graduate level.