Statistical analysis of TCP's retransmission timeout algorithm

The retransmission timeout (RTO) algorithm of Transmission Control Protocol (TCP), which sets a dynamic upper bound on the next round-trip time (RTT) based on past RTTs, plays an important role in reliable data transfer and congestion control of the Internet. A rigorous theoretical analysis of the RTO algorithm is important in that it provides insight into the algorithm and prompts optimal design strategies. Nevertheless, such an analysis has not been conducted to date. This paper presents such an analysis from a statistical approach. We construct an auto-regressive (AR) model for the RTT processes based on experimental results that indicate: 1) RTTs along a certain path in the Internet can be modeled by a shifted Gamma distribution and 2) the temporal correlation of RTTs decreases quickly with lag. This model is used to determine the average reaction time and premature timeout probability for the RTO algorithm. We derive a closed-form expression for the first measure and a formula for numerically calculating the second. Both measures are validated through tests on simulated and real RTT data. The theoretical analysis strengthens a number of observations reported in past experiment-oriented studies.

I. Introduction

The Transmission Control Protocol (TCP) is the underlying transport protocol for many popular Internet applications, such as HTTP (i.e., the Web) and SMTP (e-mail) [1, p. 179]. Among the characteristics of TCP are reliable delivery and congestion control. TCP uses explicit acknowledgment (ACK) to inform the sender of successful transmissions. A retransmission timeout (RTO) is associated with an outgoing packet. Due to network congestion and signal corruption, data and ACK packets can get lost, and hence some transmitted packets are not acknowledged as received. If the TCP sender does not receive the ACK within the RTO of a packet, TCP assumes that the packet is lost and the sender timeouts, reducing the throughput and retransmitting the packet [1]. Clearly, an accurate RTO is important to the performance of TCP. If the RTO is too small, unnecessary retransmissions and reduction in the throughput will occur. Conversely, if the RTO is too large, TCP will not recover lost data in a timely fashion, nor will it quickly react to network congestion.