Dynamic TCP acknowledgment with sliding window

AbstractThe dynamic TCP acknowledgement problem which focuses the acknowledgment mechanism in TCP protocol has been intensively studied in the area of competitive analysis. However, its framework does not consider the sliding window in the TCP protocol that restricts the maximum number of packets that the sender can inject into the network without an acknowledgement. This paper proposes a new problem in which the sliding window is realistically integrated. We study how the ability of on-line algorithms changes, depending on whether the receiver is taught the window size. The greater part of this paper assumes that the window size is a constant integer W. We first show that, if W is given, the optimal on-line algorithm for the previous framework can be extended to our new framework and achieves the optimal competitive ratio of 2. Next we prove that, if W is not given, the lower bound of the competitive ratio for an algorithm class which contains the optimal algorithm for the previous framework depends on the peak packet rate T from the sender and W, and is not better than (TW+⌊TW⌋−1)-competitive. Then, we prove that there exists an on-line algorithm that is (⌈TW⌉+2)-competitive, when W is unknown. An optimal off-line algorithm is also presented in this paper.Significantly, our problem models the situation in which an on-line algorithm involuntarily transforms the input and processes the modified input without noticing the transformation