TCP Dynamic Acknowledgment Delay: Theory and Practice
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 A = and a look-ahead coefficient L. The goal is to partition A into k subsequences sigma1, sigma2, ...,sigmak (where a subsequence 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 additional latency introduced by delaying acknowledgments. At each arrival, an oracle provides the algorithm with the times of the next L arrivals. For all the results of our paper, we describe how to incorporate other contraints to better match the true acknowledgment delay problem. We first define two different objective functions for measuring the cost of a solution, each with its own measure of latency cost. For each objective function we first given an O (nsquared)-time dynamic programming algorithm for optimally solbing the off-line problem. Then... Read complete abstract on page 2.