Getting a Grip on Network Delays

Start: 12/04/2013 - 1:15pm
End  : 12/04/2013 - 2:15pm

Applied Math Seminar

Almut Burchard (University of Toronto)


Delay analysis in packet networks is notoriously hard. Statistical properties of traffic, link scheduling, and subtle correlations between traffic at different nodes increase the difficulty of characterizing the variable portion of delays. Historically, performance analysis has relied on two fundamentally different tools: Classical queuing theory (to predict delay distributions in a network where nodes operate independently and time correlations can be neglected), and worst-case analysis (to understand complex scheduling algorithms in smaller networks). Beyond that, asymptotic methods have been used to determine stability regions and exponential decay rates.

In this talk, I will discuss recent progress on the end-to-end delay analysis for a traffic flow in a packet network, using a stochastic network calculus approach that has been developed over the last twenty years. I will consider the following questions: What is the relative impact of scheduling and statistical multiplexing on delays at a packet switch? How do end-to-end delays scale as the number of traversed nodes is increased? What do self-similar and heavy-tailed traffic arrival processes contribute to the delay? (Joint work with J. Liebeherr and his group.)

Davidson Lecture Hall