ABSTRACT
In this paper, we consider TCP throughput deadlock problems caused by an inter play between the Nagle algorithm, delayed acknowledgment algorithm, and sev eral implementation details. For some combinations of send and receive buffers, a TCP sender cannot send more segments due to the Nagle algorithm and, at the same time, a TCP receiver cannot acknowledge more segments received due to the delayed acknowledgment algorithm. The outcome is a deadlock, which can only be resolved by the receiver’s timer. Although the deadlock can take place in any types of networks, it is generally more difficult to ensure deadlock-free connec tions on high-speed networks. Moreover, the impact is much more significant on high-speed networks, and the deadlock renders the connection practically unus able. Several straightforward solutions, such as turning off the Nagle algorithm and acknowledging every segment, have been proposed; however, they reintro duce the same problems that they were initially designed for. In this paper we pro pose an adaptive acknowledgment algorithm (A3) to eliminate throughput dead locks on the receiver side while preserving the original intent of employing the Nagle algorithm and delayed acknowledgment. An A3-receiver uses the same de layed acknowledgment as before, but with an additional component to adaptively
compute the acknowledgment threshold, which is adjusted according to the maxi mum amount of segments sent by the sender. By adapting to the sender’s state, an A3-receiver can avoid deadlocks when there is no network congestion. To further adapt to possible network congestion, A3-receivers are enhanced by incorporating a slow-start-like algorithm to adjust the acknowledgment threshold when network congestion is suspected. The resulting algorithm is referred to as congestionsensitive A3 (CSA3). Extensive simulation experiments have confirmed the effec tiveness of both A3 and CSA3.
