Congestion is currently a major problem. If the Internet is to fulfil its promise of changing the way we communicate, it must evolve new ways of coping with congestion. In this thesis we study the phenomenon of congestion, and examine mechanisms for ensuring the network operates within its capacity. Our main tool is the mathematical theory of Large Deviations.
Large Deviations theory is a modern branch of probability, concerned with estimating the probabilities of rare events. It provides limit theorems, and it is our choice of limiting regime that distinguishes this from earlier work. We study the many sources limiting regime, in which the number of traffic flows in the network increases.
We first establish a Large Deviations Principle for random processes under the many sources limiting regime, to model random traffic flows coming into a network. We use this to estimate the probability of congestion, and to calculate the manner in which congestion occurs. We then extend our traffic model: we prove the important result that the statistical characteristics of a flow remain essentially unchanged as it travels through a network. This dramatically simplifies the analysis of congestion.
In the last part of the thesis, we study mechanisms for controlling congestion. The Internet engineering community has recently proposed a scheme called Explicit Congestion Notification, which allows the network to signal congestion to users. Drawing on economic theory, we define what it means to signal fairly and efficiently, taking into account the random nature of traffic. We then use large deviations theory to analyse the performance of various signalling algorithms. Proper signalling will be fundamental to the future of congestion control.