Dynamic TCP acknowledgment with sliding window
Dynamic TCP acknowledgment with sliding window
复制标题
DOI：
10.1016/j.tcs.2008.12.017
复制
发表时间：
2007-01
期刊：
影响因子：
--
通讯作者：
H. Koga
中科院分区：
文献类型：
--
作者：
H. Koga
动态TCP确认问题是TCP协议中确认机制的研究热点，也是竞争分析领域的研究热点。然而，它的框架没有考虑TCP协议中的滑动窗口，该滑动窗口限制了发送方可以在没有确认的情况下注入网络的最大数据包数量。本文提出了一个新的问题，其中的滑动窗口是现实的整合。我们研究如何在线算法的能力的变化，这取决于接收器是否被教导的窗口大小。本文的大部分假设窗口大小是一个常数W。我们首先表明，如果W是给定的，以前的框架的最佳在线算法可以扩展到我们的新框架，并实现最佳的竞争比2。接下来，我们证明，如果W不给定，则包含前一框架的最优算法的算法类的竞争比的下界取决于来自发送方和W的峰值分组速率T，并且不优于（TW+<$TW <$−1）-竞争。然后，我们证明了存在一个在线算法是（<$TW <$+2）-竞争的，当W是未知的。本文还提出了一种优化的离线算法。值得注意的是，我们的问题模型的情况下，在线算法不自觉地转换的输入和处理修改后的输入没有注意到的转换。
The 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.