To Stephen D. Scott's home page
Abstract
In this paper we study an on-line problem that is motivated by the networking problem of dynamically adjusting delays of acknowledgments in the Transmission Control Protocol (TCP). The theoretical problem we study is the following. There is a sequence of n packet arrival times Arr = (a1, ..., an) and a look-ahead coefficient L. The goal is to find a partition of Arr into k segments sigma1, sigma2, ..., sigmak (where a segment end is defined by an acknowledgment) that minimizes a linear combination of the cost for the number of acknowledgments sent and the cost for the latency introduced by delaying acknowledgments. At each arrival, an oracle provides the algorithm with the times of the next L arrivals.First we give an O(n2) dynamic programming algorithm for optimally solving the off-line problem. Then we describe an on-line algorithm that greedily acknowledges exactly when the resulting cost is less than that obtained by not acknowledging. We show that for this algorithm there is a sequence of n packet arrivals for which it is Omega(n1/2) competitive. Next we present a second on-line algorithm which is a slight modification of the first that we prove is 2-competitive. Let Copt be the cost for the optimal solution and let CA be the cost of the solution produced by algorithm A. We then show that for any on-line algorithm A with any fixed look-ahead L,
CA >= 2 Copt - c
where c is a factor that can be made arbitrarily small with respect to Copt. Thus, in the worst case, our result for L = 0 is the best possible even for on-line algorithms that can use any fixed look-ahead.
Finally we give some initial empirical results using arrival sequences from real network traffic where we compare the two methods used in TCP for acknowledgment delay with our two on-line algorithms. In all cases we examine performance with L = 0 and L = 1.
To Stephen D. Scott's home page
Last modified 06 June 2000.