Dynamic TCP acknowledgement: Penalizing long delays

Susanne Albers, Helge Bals

Research output: Contribution to conferencePaperpeer-review

12 Scopus citations


We study the problem of acknowledging a sequence of data packets that are sent across a TCP connection. Previous work on the problem has focused mostly on the objective function that minimizes the sum of the number of acknowledgements sent and the delays incurred for all of the packets. Dooly, Goldman and Scott presented a deterministic 2-competitive online algorithm and showed that this is the best competitiveness of a deterministic strategy. Recently Karlin, Kenyon and Randall developed a randomized online algorithm that achieves an optimal competitive ratio of e/(e - 1) ≈ 1.58. In this paper 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. This function is especially interesting if a TCP connection is used for interactive data transfer between network nodes. The TCP acknowledgement problem with this new objective function is different in structure than the problem with the function considered previously. We develop a deterministic online algorithm that achieves a competitive ratio of π2/6 ≈ 1.644 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, for some positive integer p. Again we give tight upper and lower bounds on the best possible competitive ratio of deterministic online algorithms. The competitiveness is 1 plus an alternating sum of Riemann's zeta function and tends to 1.5 as p → ∞. Finally we consider randomized online algorithms and show that, for our first objective function, no randomized strategy can achieve a competitive ratio smaller than 3/(3 - 2/e) ≈ 1.324. For the generalized objective function we show a lower bound of 2/(2 - 1/e) ≈ 1.225.

Original languageEnglish
Number of pages9
StatePublished - 2003
Externally publishedYes
EventConfiguralble Computing: Technology and Applications - Boston, MA, United States
Duration: 2 Nov 19983 Nov 1998


ConferenceConfiguralble Computing: Technology and Applications
Country/TerritoryUnited States
CityBoston, MA


Dive into the research topics of 'Dynamic TCP acknowledgement: Penalizing long delays'. Together they form a unique fingerprint.

Cite this