Eliminating RTT ambiguity using relative delays

Round-trip time measurements alone are not sufficient for determining whether data is proceeding along a congested path. Figure 1 shows an example of the ambiguity involved when only RTT measurements are considered. The example shows the transmission of two packets and the returning acknowledgments from the receiver. If only round-trip time (RTT) measurements were used, then measurements RTT₁=4 and RTT₂=5, could lead to an incorrect conclusion of developing congestion in the forward path for the second packet. The true cause of increased RTT for the second packet is congestion in the reverse path, not the data path. Our protocol solves this ambiguity by introducing the notion of the relative forward delay. Using this mechanism we will show that in the forward path congestion has actually improved for the second packet.

  

Figure 1: Determination of forward and reverse path queuing

The congestion control algorithm in TCP-Santa Cruz is based upon changes in the relative delay (increases and decreases in delay that packets experience with respect to each other) as packets are transmitted through the network. The relative delay is calculated from a timestamp returned by the receiver in every acknowledgment packet and specifies the arrival time of the packet at the destination. With relative delay measurements the sender can infer changes that are impossible to determine with a RTT measurements, i.e. the sender can determine whether congestion is increasing or decreasing in either the forward or reverse path of the connection. This determination can be made for every acknowledgment received (including retransmissions).

Figure 2 shows the transfer of two sequential packets, labeled #1 and #2, transmitted from a source to a receiver. The sender maintains a table with the following times for each packet transmitted: the transmission time of the data packet, the arrival time of an acknowledgment packet for the packet, and the arrival time of the data packet at the destination as reported by the receiver in its acknowledgment. From this information the sender is able to calculate for any two data packets the following time intervals: S, the time interval between the transmission the packets; A, the time between arrival of their acknowledgments at the sender; and R, the inter-arrival time of the data packets at the receiver. From these values, the relative forward delay can be obtained:

$$D^{F}_{j,i} = R_{j,i} - S_{j,i} \eqno{1}$$

where D^F_j,i represents the additional forward delay experienced by packet j with respect to packet i.

  

Figure 2: Transmission of 2 packets and corresponding relative delay measurements

Figure 3 illustrates how congestion is determined in the forward path. As illustrated in Figure 3(a), when D^F_j,i = 0 the two packets experience the same amount of queuing in the forward path. Figure 3(b) shows that the first packet was delayed more than the second packet whenever D^F_j,i < 0. Figure 3(c) shows that the second packet has been delayed with respect to the first one when D^F_j,i > 0. Finally, Figure 3(d) illustrates out-of-order arrival at the receiver. In this case the sender is able to determine the presence of multiple paths to the destination by the timestamps returned from the receiver. Note that in the example we have shown measurements for two consecutive packets; however, it is not necessary that the calculations are performed on two sequential packets. If the receiver employs delayed acknowledgments the scheme still works; however, the granularity of measurement is every other packet (or whatever ACK policy is used) instead of on a per packet basis.

  

Figure 3: FORWARD PATH: (a)Equal delay (b)1st packet delayed (c)2nd packet delayed (d)non-FIFO arrival of packets

When computing the relative delay by comparing the transmission of any two packets, four distinct cases are possible regarding the forward data path: no detected increase in forward path, 1st packet experiences congestion in the forward path, 2nd packet experiences congestion in the forward path, or the packets take alternate routes to the destination (non-FIFO arrival at the receiver).

At any time during the connection, the queues (and specifically the bottleneck queue) is in one of three states: increasing in size, decreasing or maintaining its current state. Figure 4 shows via a state diagram how the computation of the relative forward delay, D^F_j,i, provides information about the bottleneck queue and allows an easy determination of change in queue state based upon calculations of D^F_j,i over time. The goal in TCP-Santa Cruz is to allow the network queues (specifically the bottleneck queue) to grow to a desired size; the specific algorithm to achieve this goal is described next.

  

Figure 4: Based upon the value of D^F_j,i, we can determine if the Queue is currently filling, draining or maintaining.