TCP is competitive against a limited adversary

While the well-known Transport Control Protocol (TCP) is a de facto standard for reliable communication on the Internet, and performs well in practice, the question "how good is the TCP/IP congestion control algorithm?" is not completely resolved. In this paper, we provide some answers to this question using the competitive analysis framework. First, we prove that for networks with a single bottleneck (or point of congestion), TCP is competitive to the optimal global algorithm in minimizing the user-perceived latency or flow time of the sessions. Specifically, we show that with O(1) times as much bandwidth and O(1) extra time per job, TCP is O(1)-competitive against an optimal global algorithm. We motivate the need for allowing TCP to have extra resources by observing that existing lower bounds for non-clairvoyant scheduling algorithms imply that no online, distributed, non-clairvoyant algorithm can be competitive with an optimal offline algorithm if both algorithms were given the same resources. Second, we show that TCP is fair by proving that it converges quickly to allocations where every session gets its fair share of network bandwidth.