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

Liśkiewicz, Maciej and Manthey, Bodo (2004) New lower and upper bounds for the competitive ratio of transmission protocols. Information Processing Letters, 89 (6). pp. 297-301. ISSN 0020-0190

PDF
Restricted to UT campus only: Request a copy
157Kb

Abstract:	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.
Item Type:	Article
Copyright:	© 2004 Elsevier
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/79420
Official URL:	http://dx.doi.org/10.1016/j.ipl.2003.12.003
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page