TY - GEN

T1 - A randomized online algorithm for bandwidth utilization

AU - Arora, Sanjeev

AU - Brinkmann, Bo

PY - 2002/1/1

Y1 - 2002/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=42549124706&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=42549124706&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:42549124706

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 535

EP - 539

BT - Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

PB - Association for Computing Machinery

T2 - 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

Y2 - 6 January 2002 through 8 January 2002

ER -