Performance Analysis of Dynamic
Network Processes
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.