A randomized online algorithm for bandwidth utilization
Sanjeev Arora, Bo Brinkman · 2002
Princeton University Abstract Protocols for data transmission over a TCP-like computer network should not only lead to efficient network utilization but also be fair to different users. Current networks accomplish these goals by some form of end-to-end congestion control. However, existing protocols assume somewhat altruistic behavior from hosts, and Karp et al. [7] have initiated a study of whether or not the host's optimum strategy is altruistic. We carry this exploration further by developing an efficient randomized algorithm for bandwidth utilization in their model. The competitive ratio of this algorithm is optimal up to a constant factor. Karp et al. had earlier studied the deterministic case and left open the randomized case. What may be of some interest is that our algorithm is essentially the classical MIMD (multiplicative increase, multiplicative decrease) strategy, which is very aggressive and non-altruistic. 1 Introduction In TCP networks, such as the Internet, there is no central authority which allots bandwidth to hosts. Instead, individual hosts are responsible for setting their sending rate appropriately. Each host would like to send data as fast as possible, but if they all do this, router queues throughout the network overflow and start dropping packets, which dramatically reduces network utilization. Such a congestion collapse was a frequent occurrence on the Internet in the 1980s. Thus there is an inherent tension between the interests of the hosts and those of the network designer.