A framework for designing a low-loss, low-delay Internet

In this thesis, we present a framework for designing a low-loss, low-delay heterogeneous network like the Internet. We start by presenting a framework for designing end-to-end congestion control schemes in a network where each user may have a different utility function. We first show that there exists an additive increase-multiplicative decrease scheme using only end-to-end measurable losses such that a socially optimal solution can be reached. We incorporate non-congestion-related random losses and round-trip delay in this model, and show that one can generalize observations regarding TCP-type congestion avoidance to more general window flow control schemes. We then consider explicit congestion notification (ECN) as an alternate mechanism (instead of losses) for signaling congestion and show that ECN marking levels can be designed to nearly eliminate losses in the network by choosing the marking level independently for each node in the network. While the ECN marking level at each node may depend on the number of flows through the node, the appropriate marking level can be estimated using only aggregate flow measurements, i.e., per-flow measurements are not required.; In the second part we examine the question of providing feedback from the network such that the congestion controllers derived from the penalty function formulation lead to the solution of the original unconstrained problem. This can be viewed as the decentralized adaptive design of ECN marking rates at each node in the Internet to ensure global loss-free operation of a fluid model of the network. We then look at the stability of such a scheme using a time-scale decomposition of the system. This results in two separate systems that are stable individually and we show that under certain assumptions the entire system is semi-globally stable and converges to the equilibrium point exponentially fast.; Finally, we present a simple Active Queue Management scheme that we call the Adaptive Virtual Queue (AVQ) algorithm and provide design rules for selecting its parameters. We also provide a simple implementation of the AVQ scheme using a token-bucket formulation, which can be implemented with a few lines of code. We then compare its performance to other well-known AQM schemes.