Dynamic TCP acknowledgment: Penalizing long delays

Susanne Albers, Helge Bals

Research output: Contribution to journalArticlepeer-review

10 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 acknowledgments sent and on 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 acknowledgments 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 acknowledgment 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 pth 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
Pages (from-to)938-951
Number of pages14
JournalSIAM Journal on Discrete Mathematics
Issue number4
StatePublished - 2005
Externally publishedYes


  • Acknowledgment
  • Competitive analysis
  • Data packet
  • Online algorithm
  • TCP


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

Cite this