Subject: [ippm] RD and number of TCP retransmissions

From: Anura Jayasumana <[email-masked]>
Date: Fri, 27 Aug 2004 15:58:36 -0600

Stanislav:
Here is our response to the question you posed at the IETF meeting in 
San Diego.

Q: "Suppose you have RD for a TCP stream. No packets were lost. How many 
packets were retransmitted? Assume standard TCP - for example free BSD 
4.X TCP or the RFC TCP with fast retransmissions."

Short answer is    "Sum of RD[k] for k> C," where C is a constant that 
can be found for a given  implementation.
We consider the case in which there are no duplications or  packet 
losses introduced by the network.. 

Now a detailed example with fast retransmit and delayed ACK  implemented 
as follows:
Fast retransmit ( RFC 2581):
   The TCP sender SHOULD use the "fast retransmit" algorithm to detect
   and repair loss, based on incoming duplicate ACKs. The fast
   retransmit algorithm uses the arrival of 3 duplicate ACKs (4
   identical ACKs without the arrival of any other intervening packets)
   as an indication that a segment has been lost. After receiving 3
   duplicate ACKs, TCP performs a retransmission of what appears to be
   the missing segment, without waiting for the retransmission timer to
   expire.

Delayed ACK (RFC1122):
   TCP SHOULD implement a delayed ACK, but an ACK should not
   be excessively delayed; in particular, the delay MUST be
   less than 0.5 seconds, and in a stream of full-sized
   segments there SHOULD be an ACK for at least every second
   segment.

(These criteria used, for example, in Solaris 2.6 implementation.)

It means that a packet is retransmitted after it is not found in next 8 
arrivals : [**, **, **, **,] . (Here a * indicates the arrival of a 
packet at the receiver, and a "," indicates the transmission of an ACK 
by the receiver.
Thus, the displacement (according to RD definitions) is greater than 6 
for retransmitted packets.

Therefore, "Sum of (all RD[k] for k > 6) corresponds to the fraction of 
packets that is retransmitted."

Example:
Arrivals:       1   3   4   5   6   7   8   9   2   10
ACKs:                 2      2        2      2         11

Receive_index:  1   2   3   4   5   6   7   8   9   10
Displacement:   0  -1  -1   -1  -1  -1  -1  -1  7   0

However, there would be a discrepancy, if 500msec is less than one-way 
delay or even instead of 500msec, an implementation uses lower maximum 
that which is less than one-way delay. In such cases, receiver may send 
ACK for every packet [*, *, *, *,]. We can modify the above statement to

"Sum of (all RD[k] for k > 2) corresponds to the fraction of packets 
that is retransmitted."

Example:
Arrivals:      1   3   4   5   2   6
ACKs            2   2   2   2   6   7
Receive_index: 1   2   3   4   5   6
Displacement:   0  -1  -1   -1  3   0

An exception would occur to the above statements, if there is internal 
reordering, e.g., consider

Arrivals:       1   4   5   6   7   8   9   10   2   3
ACKs:                 2      2        2       2        11

Receive_index:  1   2   3   4   5   6   7   8   9   10
Displacement:   0  -2  -2   -2  -2  -2  -2  -2  7   7

Here packet 3 contributes to RD[7] component, but it is not 
retransmitted. Such occurrences are rare in networks (based on our 
measurements). We have not worked through the details of such a case 
yet. However, we believe that an expression for the appropriate 
correction due to internal reordering can be found (on going work).

Comments and suggestions are always welcome...
Regards!

Anura P. Jayasumana <http://www.engr.colostate.edu/%7Eanura>
Professor, Electrical & Computer Engineering
                           and Computer Science
Department of Electrical and Computer Engineering
Colorado State University
Fort Collins, CO 80523
Phone: (970) 491-7855
Fax: (970) 491-2249
Email: <[email-masked]>
_______________________________________________
ippm mailing list
[email-masked] 
https://www1.ietf.org/mailman/listinfo/ippm