A randomized online algorithm for bandwidth utilization

Sanjeev Arora, Bo Brinkman

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Protocols for data transmission over an IP 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. Existing protocols, however, assume somewhat altruistic behavior from hosts. Karp et al. (2000) have initiated a study of whether or not a single host's optimum strategy (in a system where other hosts are well behaved) 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 multiplicative increase, multiplicative decrease strategy, which is very aggressive and non-altruistic.

Original languageEnglish (US)
Pages (from-to)187-194
Number of pages8
JournalJournal of Scheduling
Issue number3
StatePublished - May 2004

All Science Journal Classification (ASJC) codes

  • Software
  • General Engineering
  • Management Science and Operations Research
  • Artificial Intelligence


  • Congestion control
  • Online algorithms


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

Cite this