A randomized online algorithm for bandwidth utilization

Sanjeev Arora, Bo Brinkmann

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
PublisherAssociation for Computing Machinery
Pages535-539
Number of pages5
ISBN (Electronic)089871513X
StatePublished - Jan 1 2002
Event13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 - San Francisco, United States
Duration: Jan 6 2002Jan 8 2002

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume06-08-January-2002

Other

Other13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
CountryUnited States
CitySan Francisco
Period1/6/021/8/02

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'A randomized online algorithm for bandwidth utilization'. Together they form a unique fingerprint.

  • Cite this

    Arora, S., & Brinkmann, B. (2002). A randomized online algorithm for bandwidth utilization. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 (pp. 535-539). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 06-08-January-2002). Association for Computing Machinery.