ICS Theory Group

ICS 269, Winter 2002: Theory Seminar

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 pth power. Finally, we show lower bounds for randomized algorithms on these problems.

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