New lower and upper bounds for the competitive ratio of transmission protocols

Maciej Liśkiewicz, Bodo Manthey

Research output: Contribution to journalArticleAcademicpeer-review


Transmission protocols like TCP are usually divided into a time scheduling and a data selection policy. We consider on-line algorithms of data selection policies for any time scheduling policy and any routing behavior in a network. For the model introduced by Adler et al. [Proc. 5th Israel Symp. on Theory of Computing Systems, 1997, pp. 64–72], we improve both the lower and the upper bound on the competitive ratio making them asymptotically tight. Furthermore, we present a lower bound that depends on the size of the buffers that are available both to the sender and to the receiver. We obtain a constant lower bound for the competitive ratio for constant buffer size.
Original languageUndefined
Pages (from-to)297-301
Number of pages5
JournalInformation processing letters
Issue number6
Publication statusPublished - 2004


  • On-line algorithms
  • EWI-21254
  • IR-79420
  • Transmission protocols
  • Interconnection networks

Cite this