News

Colloquia

A Stochastic Network Calculus for Computer Networks

Jorg Liebeherr
University of Toronto

April 20, 2006
JEC 3117 - 4:00 p.m. to 5:00 p.m.
Refreshments at 3:30 p.m.

Abstract:

The stochastic network calculus is an evolving new methodology for backlog and delay analysis of networks that can account for statistical multiplexing gain. The long-term goal of this research is to develop a new theory and new algorithms for determining the delay and throughput performance in packet networks. This talk presents the motivation, background, and our results in this area. For example, it can be shown that, at high data rates, statistical multiplexing gain dominates the effects of scheduling in a network. This is an indication that a relatively simple network design may be sufficient to provide strong service guarantees. We provide statistical lower bounds for the service experienced by a single flow when resources are managed for aggregates of flows and when the scheduling algorithms used in the network are not known. This result can be applied for verifying service level agreements with network service providers: if a network customer can measure its aggregate input to the network and the throughput of only a single flow, the customer can determine with high certainty if the network service provider has provisioned the resources specified in the agreement. We also show how to express the concept of effective bandwidth in terms of effective envelopes. This allows us to evaluate the delay distribution for a diverse set of traffic models (e.g., on-off traffic, fractional Brownian motion) and a variety of scheduling algorithms (GPS, EDF, Static Priority).

Bio:

Jorg Liebeherr received the Ph.D. degree in Computer Science from the Georgia Institute of Technology. After a Postdoc at the University of California, Berkeley, he joined the Department of Computer Science at the University of Virginia. In 1997/1998 he was an Associate Professor in the Department of Electrical Engineering at Polytechnic. In Fall 2005, he joined the Department of Electrical and Computer Engineering of the University of Toronto as the Nortel Chair of Network Architecture and Services. Jorg Liebeherr served as Editor-in-Chief of IEEE Network Magazine, and served as associate editor of IEEE/ACM Transactions on Networking, ACM/Springer Multimedia Systems Journal, Computer Communications, Real-Time Systems Journal and Cluster Computing. He served on the IEEE Communications Society Board of Governors in 2003-2005, and was chair of the IEEE Communications Society Technical Committee on Computer Communications for 2004-2005. He is co-author of the book Mastering Networks: An Internet Lab Manual, published by Addison-Wesley in 2004. His research interests are network protocols, traffic theory, and self-organizing peer networks. He received an NSF Career award in 1996, a University of Virginia Teaching and Technology fellowship in 1995, a Virginia Engineering Foundation fellowship in 2002, and was co-author of the best student paper award at ACM Sigmetrics 2005.

Hosted by: Bulent Yener (x6907)