Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1998-01-01

Filename

WUCS-98-29.PDF

Technical Report Number

WUCS-98-29

Abstract

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 we describe an on-line algorithm that greedily acknowledges exactly when the cost for an acknowledgment is less than the latency cost incurred by not acknowledging. We show that for this algorithm there is a sequence of n packet arrivals for which it is Omega (squareroot(n))-competitive for the first objective function, 2-competitive for the second function for L = 0, and 1-competitive for the second function for L = 1. Next we present a second on-line algorithm which is a slight modification of the first that we prove is 2-competitive for both objective funcitons. Then for each objective function we give lower bounds on the competitive ration for any deterministic on-line algorithm. These results show that for each objective function, at least one of our algorithms is optimal. 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 perforance with L = 0 and L = 1.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7DB801W

Download

Share

COinS