Re: [tcpm] Detect Lost Retransmit with SACK

["Scheffenegger, Richard" <[e-mail]>]

Thanks Alex,

I will try to give my example in another form: (RWND = 40000; 
the timing might not be perfectly depicted).

      ACK         Transmitted       Received    ACK Sent
      Received    Segment           Segment     (Including SACK Blocks)
	

                      0-  999
                   1000- 1999
						    0-  999	
								 1000
	 1000		                   1000- 1999
			 2000- 2999                    2000
	 2000        3000- 3999
			 4000- 4999		 2000- 2999
	             5000- 5999				 3000
	 3000		 6000- 6999		 3000- 3999
			 7000- 7999				 4000
	 4000		 8000- 8999		 4000- 4999
			 9000- 9999				 5000
	 5000		10000-10999		 5000- 5999
			11000-11999				 6000
	 6000		12000-12999		 6000- 6999
			13000-13999				 7000
	 7000					 7000- 7999
			14000-14999				 8000
	 8000					 8000- 8999
			15000-15999				 9000
	 9000					 9000-10000
			16000-16999				10000
	10000					(dropped)
			17000-17999
						(dropped)
			.			
						(dropped)
			.			
						(dropped)
			.
						(dropped)
			.	
						15000-15999
								10000,
SACK=15k-16k
	10000, SACK=15k-16k		16000-16999
			18000-18999				10000,
SACK=15k-17k
	10000, SACK=15k-17k		17000-17999
			19000-19999				10000,
SACK=15k-18k
	10000, SACK=15k-18k		.
                  10000-10999
						18000-18999
								10000,
SACK=15k-19k
	10000, SACK=15k-19k		19000-19999
			11000-11999				10000,
SACK=15k-20k
	10000, SACK=15k-20k		(dropped)
			12000-12999		
						11000-11999
								10000,
SACK=11k-12k;15k-20k
	10000, SACK=11k-12k;15k-20k	12000-12999
			13000-13999				10000,
SACK=11k-13k;15k-20k
	10000, SACK=11k-13k;15k-20k
			14000-14999		13000-13999
								10000,
SACK=11k-14k;15k-20k
	10000, SACK=11k-14k;15k-20k	14000-14999
!*A			20000-20999				10000,
SACK=11k-20k
!	10000, SACK=11k-20k
!			21000-21999		20000-20999
!			22000-22999				10000,
SACK=11k-21k
!	10000, SACK=11k-21k
!			23000-23999		21000-21999
!			24000-24999				10000,
SACK=11k-22k
!	10000, SACK=11k-22k		22000-22999
!			25000-25999				10000,
SACK=11k-23k
!	10000, SACK=11k-23k		23000-23999
!*B			26000-26999				10000,
SACK=11k-24k
!     ::          ::                ::          ::
!RWND Full:                                     10000, SACK=11k-50k
!     10000, SACK=11k-50k
!     
!     ::          ::                ::          ::
!
!RTO:
!                 10000-10999
!								50000
!Slow-Start                                               


All the Lines marked with ! Indicate current best practise behaviour 
(RFC, no drafts), if I'm not mistaken - left out LimitedTransmit for 
simplicity's sake.

At point *A (or one ACK later), the sender would have the earliest 
possibility to detect a lost retransmission, taking into account the 
usual 3 ACK reordering hold-down... In this example, this happens by 
coincidence at the same time, that the sender has finished fast 
retransmission (and would go into fastrecovery, restoring CWND, etc; 
this is NOT a requirement....; Actually, the cwnd is likely to be in
the order of 100reds of segments, and most of the time, the sender
will have finished the retransmission episode before one RTT is up)

At point *B, the sender could detect with 100% certainty (2*RTT) that 
one retransmitted segment was lost.

However, current practise (excluding Linux with FACK for now, as 
that's not in RFCs) is to continue sending SND.NXT, until RWND is 
full or RTO expires...

Note that the suggested algorithm will never trigger if no 
retransmitted packet is lost - if would behave exactly the same as 
currently.

Only when *A or *B marks are detected, the DUPACK detection logic 
would re-arm (a more complex implementation could re-arm at the first 
sign of retransmission loss, and dis-arm if a ACK within DupAck 
distance ACKs the segment, for which it armed before).

Thus, a lost retransmission would be retried close to the earliest 
possibility, instead of waiting until RTO (a bit like what FACK seems 
to try to do, but with low reliability as it seems).

Multiple Burst loss events, each lossing a different segment in 
one cwnd would be handled by SACK.

If there are extended periods of time, where no communication is 
possible (the same segment doesn't get lost only twice, but multiple 
times), RTO would eventually fire and, using the RTO backoff 
algorithm, retry at ever increasing intervals with very low 
(1-2 segments) rate...


Do you have a test bed, where you can deliberately drop the same
segment twice (or n times) and check the TCP Behaviour for yourself?

Best regards,



Richard Scheffenegger
Field Escalation Engineer
NetApp Global Support 
NetApp
[phone] Office (2143 3146 - internal)
[phone] Mobile
www.netapp.com 
Franz-Klein-Gasse 5
1190 Wien 


-----Original Message-----
From: Alexander Zimmermann
[mailto:[e-mail]] 
Sent: Dienstag, 10. November 2009 13:51
To: Scheffenegger, Richard
Cc: [e-mail]
Subject: Re: Detect Lost Retransmit with SACK

Hi Richard,

I discussed your example with Arnd (he is a line-of-sight colleague).
Your "algorithms"
may workwhen you have only one bust lost per cwnd. If you have multiple
non-burst
loss (e.g. WLAN), IMHO, is doesn't work.

Am 09.11.2009 um 18:27 schrieb Scheffenegger, Richard:

> 
> Hi Alexander,
> 
> Thanks for the welcome :)
> 
> I fork another thread with the LimitedTransport||FastRecovery / ABC
interaction...
> 
> 
> I will try to sketch up an example to demonstrate what problem I'm
trying to address:
> 
> 
> Let's assume the cwnd is already open for at least 7 segments, before
the segment with
> sequence number 10000 is the first one to be dropped by the network.
> 
> Also, let's assume that FastRetransmit runs from the left edge of the
leftmost hole
> (SND.UNA) upwards, and that per ACK only a single segment is sent.
> 
> 
>             Triggering    ACK      Left     Right    Left     Right
>             Segment                Edge 1   Edge 1   Edge 2   Edge 2
> 
>              9000          9000
>             10000  (lost)       *
>             11000  (lost)
>             12000  (lost)
>             13000  (lost)
>             14000  (lost)
>             15000         10000    15000    16000
>             16000         10000    15000    17000
>             17000         10000    15000    18000

Ok, I count 9 segments ;-) Anyway, your example is a little bit strange.
You assume you send 9 segment in a burst. Then your ACK for 9000 will
trigger
the segment 18000. Then the 2 DUPACKs  for 15000 and 16000 will trigger
19000,
20000 respectively (Limited Transmit). The third DUPACK will trigger the
Fast
Retransmit 10000. Since NextSeq() and pipe allow you retransmit 11000,
12000.

At this point you have to wait since the pipe is full (if I calculate
pipe in a rush correctly).
A RTT later you will get 3 Dupacks, even if the 10000 is not lost.

OK, I think you can adjust your example so that it works for the given
case, however in
other scenarios (multiple loss, reordering, packet duplication,...) it
will be much more
complicated.

I suggest writing examples as Ilpo does in
http://tools.ietf.org/html/draft-ietf-tcpm-sack-recovery-entry-00.
It's much more easier to read.

> 
> 3 ACKs trigger fast retransmit
> 
>             10000  (lost again)
>             11000         10000    11000    12000    15000    18000
>             12000         10000    11000    13000    15000    18000
>             13000         10000    11000    14000    15000    18000
> -> here we have again 3 ACKs indicating a another loss of one of the
retransmitted
> packets. The leftmost hole did not change, while the overall number of
SACKed
> octets did decrease for 3 consecutive ACKs (4; 3 and 2 segments marked
by SACK).
> 

Alex

//
// Dipl.-Inform. Alexander Zimmermann
// Department of Computer Science, Informatik 4
// RWTH Aachen University
// Ahornstr. 55, 52056 Aachen, Germany
// phone: [phone], fax: [phone]
// email: [e-mail]
// web: http://www.umic-mesh.net
//