Toronto Networking Seminar 2006

Probabilistic Network Calculus:
A System Theory for the Internet

Markus Fidler
University of Toronto

Date:  January  20,  3pm
Location: 1210 Bahen Center

Abstract

The exact performance evaluation of communication systems enables network operators to dimension capacities and buffers to implement cost-efficient services with defined loss rates and end-to-end delays. Respective quality of service parameters are crucial for real-time applications, such as Internet telephony or video broadcasting. Classical queuing theory has been widely used to derive such performance measures for telecommunication systems. The applied Poisson processes are, however, not well suited to model Internet traffic. This shortcoming has motivated the development of new approaches, such as the theory of effective bandwidths and network calculus.
Network calculus is a min-plus system-theory for worst-case analysis of backlogs and delays. It features intuitive and powerful convolution formulas for analysis of single servers and for concatenation of tandem servers. This concatenation property is of highest importance since it establishes a general framework for efficient analysis of multiple node scenarios. Recent research loosens the worst-case assumptions of network calculus to evolve a probabilistic equivalent that benefits from statistical multiplexing of independent flows. Significant achievements have already been made, owing for example to the theory of effective bandwidths, however, the outstanding end-to-end scalability set up by deterministic network calculus has not been attained.
This presentation introduces a concise probabilistic network calculus which effectively builds on moment generating functions. The developed theory features end-to-end probabilistic performance bounds which scale remarkably good, both in the number of traversed nodes as well as in the number of aggregated flows.

Bio:

Markus Fidler is currently an Emmy Noether fellow of the German Research Foundation (DFG) and a postdoctoral fellow of the University of Toronto. He received his Dipl.-Ing. in electrical engineering from RWTH Aachen University in 1997, Dipl.-Kfm. in business economics from Hagen University in 2001, and Dr.-Ing. from RWTH Aachen University in 2003. Before he joined the department of computer science at Aachen University in 2001 he was employed in 1997 by Hagenuk Telecom and later by Alcatel R&D, where he worked on GSM Phase 2 and GPRS. In the fall 2004 he was a postdoctoral fellow of the Mittag-Leffler institute, Sweden, and during the year 2005 at the Centre for Quantifiable Quality of Service at NTNU Trondheim, Norway. His current research interests are in the field of probabilistic network calculus.