On-Line End-to-End Congestion Control
Naveen Garg, Neal E. Young · 2002
Congestion control in the current Internet is accomplished mainly by TCP/IP. To understand the macroscopic network behavior that results from TCP/IP and similar endto-end protocols, one main analytic technique is to show that the the protocol maximizes some global objective function of the network traffic. Here we analyze a particular end-to-end, MIMD (multiplicative-increase, multiplicative-decrease) protocol. We show that if all users of the network use the protocol, and all connections last for at least logarithmically many rounds, then the total weighted throughput (value of all packets received) is near the maximum possible. Our analysis includes round-trip-times, and (in contrast to most previous analyses) gives explicit convergence rates, allows connections to start and stop, and allows capacities to change. 1. Congestion control and optimization Congestion control in the current Internet is accomplished mainly by TCP/IP — 90 % of Internet traffic is TCP-based [41]. Meanwhile the design and analysis of TCP and other end-to-end congestion-control protocols are only partially understood and are becoming the subject of increasing attention [25, 28]. One main analytic technique is to interpret the protocol as solving some underlying combinatorial optimization problem on the network — to show that the protocol causes the traffic distribution, over time, to optimize some global objective function