Eli Upfal, Brown University

The standard framework of algorithm theory does not provide adequate tools for analyzing network performance. Theory of algorithms has focused mainly on static computation problems, whereby the input is known at the start of the computation and the goal is to minimize the number of steps till the process terminates with a correct output. Network processes, such as routing, load balancing and contention resolution protocols are dynamic in nature. Input is continuously injected to the system, and the algorithm (which is not supposed to terminate at all) is measured by its long term (steady state) performance.

In this tutorial we will cover various approaches for modeling and analyzing dynamic processes in networks. Modeling the dynamic performance as a stochastic process, we apply tools from queueing theory, discrete and continues time Markov processes theory, and renewal theory to analyze the long term, steady state, performance of the processes. We will also discuss non-stochastic approaches such as adversarial queueing theory, and game theoretical approach.