## 24 Jan 2003:

Dynamic TCP Acknowledgement: Penalizing Long Delays

Josiah Carlson

We study the problem of acknowledging a sequence of data packets that
are sent across a TCP connection. We investigate a new objective
function that minimizes the sum of the number of acknowledgements sent
and the maximum delay incurred for any of the packets.
We develop a deterministic online algorithm that achieves a competitive
ratio of π^{2}/6 and prove that no deterministic algorithm
can have a smaller competitiveness. We also study a generalized
objective function where delays are taken to the *p*th power.
Finally, we show lower bounds for randomized algorithms on these problems.

(From a SODA 2003 paper by Susanne Albers and Helge Bals.)