A faster off-line algorithm for the TCP acknowledgement problem

John Noga; Steve Seiden; Gerhard Woeginger

doi:10.1016/S0020-0190(01)00199-5

A faster off-line algorithm for the TCP acknowledgement problem

John Noga
, Steve Seiden
, Gerhard Woeginger

Research output: Contribution to journal › Article › Academic › peer-review

8 Citations (Scopus)

Abstract

In a recent paper [Proceedings of STOC’98, 1998, pp. 389–398], Dooly, Goldman and Scott study a problem that is motivated by the networking problem of dynamically adjusting delays of acknowledgements in the Transmission Control Protocol (TCP). Among other results, they give an O(n2) off-line algorithm for computing the optimal way of acknowledging n packet arrivals and departures.
In this brief note, we observe that there is a faster off-line algorithm for this problem with time complexity O(n).

Original language	English
Pages (from-to)	71-73
Journal	Information processing letters
Volume	81
Issue number	2
DOIs	https://doi.org/10.1016/S0020-0190(01)00199-5
Publication status	Published - 2002
Externally published	Yes

Keywords

METIS-208607
Transmission Control Protocol
TCP acknowledgement
Netwerks
Dynamic Programming

Access to Document

10.1016/S0020-0190(01)00199-5

Cite this

@article{827e00ef6974434c80d4c16c3c85f668,

title = "A faster off-line algorithm for the TCP acknowledgement problem",

abstract = "In a recent paper [Proceedings of STOC{\textquoteright}98, 1998, pp. 389{\textendash}398], Dooly, Goldman and Scott study a problem that is motivated by the networking problem of dynamically adjusting delays of acknowledgements in the Transmission Control Protocol (TCP). Among other results, they give an O(n2) off-line algorithm for computing the optimal way of acknowledging n packet arrivals and departures. In this brief note, we observe that there is a faster off-line algorithm for this problem with time complexity O(n).",

keywords = "METIS-208607, Transmission Control Protocol, TCP acknowledgement, Netwerks, Dynamic Programming",

author = "John Noga and Steve Seiden and Gerhard Woeginger",

year = "2002",

doi = "10.1016/S0020-0190(01)00199-5",

language = "English",

volume = "81",

pages = "71--73",

journal = "Information processing letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - A faster off-line algorithm for the TCP acknowledgement problem

AU - Noga, John

AU - Seiden, Steve

AU - Woeginger, Gerhard

PY - 2002

Y1 - 2002

N2 - In a recent paper [Proceedings of STOC’98, 1998, pp. 389–398], Dooly, Goldman and Scott study a problem that is motivated by the networking problem of dynamically adjusting delays of acknowledgements in the Transmission Control Protocol (TCP). Among other results, they give an O(n2) off-line algorithm for computing the optimal way of acknowledging n packet arrivals and departures. In this brief note, we observe that there is a faster off-line algorithm for this problem with time complexity O(n).

AB - In a recent paper [Proceedings of STOC’98, 1998, pp. 389–398], Dooly, Goldman and Scott study a problem that is motivated by the networking problem of dynamically adjusting delays of acknowledgements in the Transmission Control Protocol (TCP). Among other results, they give an O(n2) off-line algorithm for computing the optimal way of acknowledging n packet arrivals and departures. In this brief note, we observe that there is a faster off-line algorithm for this problem with time complexity O(n).

KW - METIS-208607

KW - Transmission Control Protocol

KW - TCP acknowledgement

KW - Netwerks

KW - Dynamic Programming

U2 - 10.1016/S0020-0190(01)00199-5

DO - 10.1016/S0020-0190(01)00199-5

M3 - Article

SN - 0020-0190

VL - 81

SP - 71

EP - 73

JO - Information processing letters

JF - Information processing letters

IS - 2

ER -

A faster off-line algorithm for the TCP acknowledgement problem

Abstract

Keywords

Access to Document

Fingerprint

Cite this