Dynamics of Random Early Detection Gateway Under A Large Number of TCP Flows

Thumbnail Image


PhD_2004-2.pdf (1.09 MB)
No. of downloads: 1414

Publication or External Link






While active queue management (AQM) mechanisms such as Random Early Detection (RED) are widely deployed in the Internet, they are rarely utilized or otherwise poorly configured. The problem stems from a lack of a tractable analytical framework which captures the interaction between the TCP congestion-control and AQM mechanisms. Traditional TCP traffic modeling has focused on "micro-scale" modeling of TCP, i.e., detailed modeling of a single TCP flow. While micro-scale models of TCP are suitable for understanding the precise behavior of an individual flow, they are not well suited to the situation where a large number of TCP flows interact with each other as is the case in realistic networks.

In this dissertation, an innovative approach to TCP traffic modeling is proposed by considering the regime where the number of TCP flows competing for the bandwidth in the bottleneck RED gateway is large. In the limit, the queue size and the aggregate TCP traffic can be approximated by simple recursions, which can be calculated independently of the number of flows. The limiting model is therefore scalable as it does not suffer from the state space explosion. The steady-state queue length and window distribution can be evaluated from well-known TCP models.

We also extend the analysis to a more realistic model which incorporates session-level dynamics and heterogeneous round-trip delays. Typically, ad-hoc assumptions are required to make the analysis for models with session-level dynamics tractable under a certain regime. In contrast, our limiting model derived here is compatible with other previously proposed models in their respective regime without having to rely on ad-hoc assumptions. The contributions from these additional layers of dynamics to the asymptotic queue are now crisply revealed through the limit theorems. Under mild assumptions, we show that the steady-state queue size depends on the file size and round-trip delay only through their mean values.

For a more accurate description of the queue dynamics, a Central Limit analysis is established which identifies an interesting relationship between the queue fluctuations and the random packet marking mechanism in AQM. Moreover, it also reveals the dependency of the magnitude of the queue fluctuations on the variability of the file size and round-trip delay. Simulation results supporting conclusions drawn from the limit theorems are also presented.