New lower and upper bounds for the competitive ratio of transmission protocols
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. (C) 2003 Elsevier B.V. All rights reserved.
transmission protocols on-line algorithms interconnection networks