Simultaneous Competitive and Regret Guarantees for TCP Acknowledgment

We study simultaneous competitive and regret guarantees for TCP acknowledgment. Each acknowledgment serves all pending packets, and the objective is to minimize the total acknowledgment and waiting costs. It is well known that no deterministic online algorithm achieves a competitive ratio better than 2. Given k randomized online experts and 0<varepsilon<1, we construct a randomized online algorithm whose realized total cost is always at most (2+varepsilon) times the offline optimal cost OPT and whose expected regret against the expert with the smallest realized cost is O(√OPTlog(k+1)+log(1/varepsilon)). The algorithm requires no advance knowledge of the number of packets or OPT. Our algorithm controls switching costs between experts and uses the gap between the permitted competitive bound and its current cost to determine when to learn. We also prove lower bounds showing that, for k≥ 2, this regret bound is asymptotically optimal in OPT, k, and varepsilon, and that varepsilon>0 is necessary for sublinear regret.