Subject: [Tsvwg] A few questions and observations on TCP SACK

From: Gil Jose-josegil1 <[email-masked]>
Date: Wed, 3 Dec 2003 20:53:00 -0000

I have a few questions specific to the operation of loss recovery specified
in RFC 3517 (A conservative Selective Acknowledgment SACK-based Loss
Recovery algorithm for TCP). Perhaps an example will help to understand
better my questions.

Let's assume a window of six segments as an example. Let's numerate segments
in that window from 16 to 21. Assume that segments 20 and 21 are lost. Let's
say that the next immediate round of segments contains four segments (22 to
25) generated by the acks from segments 16 to 19 (no delayed ack assumed).
Let's say that segment 25 is also lost. So in total three segments are lost.

When the third dupack arrives for segment 19 then segment 20 is fast
retransmitted.  Following RFC 3517 pipe=2 after the fast retransmit. Because
cwnd=3 > pipe=2 then segment 21 could be retransmitted also (since it is
determined as lost by the function IsLost()). Therefore two immediate
retransmissions could happen. My question is if there is any limit in the
number of segments sent straight after the first fast retransmit if the
condition cwnd > pipe is met (apart from the receiver's advertised window
limit)? It seems to me that RFC 3517 would allow the fast retransmit of 'n'
consecutive lost segments in one go (after the first three dupacks are
received and provided that cwnd > pipe and receivers's advertised window
limit is not exceeded).

When the ack for segment 20 arrives (first partial ack) the value of pipe is
recalculated to 2. Therefore only one segment can be transmitted. A new
segment 26 could be then transmitted since no more segments have been
determined as lost at this point. However reading Kevin Fall and Sally Floyd
paper "Simulation-based comparisons of Tahoe, Reno and SACK TCP" pipe is
decremented by two for every partial ack received. It seems to me that the
RFC 3517 would not decrement pipe by two in my particular example. Is my
understanding correct and can we say that decrementing pipe by two for every
received partial ack cannot be generalised?

My third question relates to the lost segment 25. When the partial ack for
segment 24 arrives only one new segment (27) can be transmitted since pipe=2
and segment 25 is not determined yet as lost. Reading the definition of the
procedure IsLost() defined in RFC 3517 it is my understanding that segment
25 cannot be retransmitted until three segments above the lost segment are
SACKed since IsLost() determines the lost of a segment when "either
DupThresh discontiguous SACKed sequences have arrived above 'SeqNum' or
(DupThresh*SMSS) bytes with sequence numbers greater than 'SeqNum' have been
SACKed". Essentially, in my example we need to receive three dupacks for
segment 24 before we can retransmit segment 25. Am i wrong? My confusion
comes from reading Fall&Foyd paper where they retransmit a lost segment
immediately after a SACK sequence above the lost segment is received
(essentially after one dupack). Does the RFC 3517 allow for the operation
described in this paper?

Jose

_______________________________________________
tsvwg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tsvwg

---

From: Mark Allman <[email-masked]>
Date: Wed, 03 Dec 2003 23:38:55 -0500

> retransmitted.  Following RFC 3517 pipe=2 after the fast
> retransmit. Because cwnd=3 > pipe=2 then segment 21 could be
> retransmitted also (since it is determined as lost by the function
> IsLost()). Therefore two immediate retransmissions could happen. My
> question is if there is any limit in the number of segments sent
> straight after the first fast retransmit if the condition cwnd > pipe
> is met (apart from the receiver's advertised window limit)? It seems
> to me that RFC 3517 would allow the fast retransmit of 'n' consecutive
> lost segments in one go (after the first three dupacks are received
> and provided that cwnd > pipe and receivers's advertised window limit
> is not exceeded).

You are correct.  If the cwnd is X segments before loss recovery then I
think you can get a burst on the order of (X/2)-3 in the worst case
(i.e., you cut cwnd by half and you need 3 segments (at the end of the
window) to get through to indicate that all the intervening segments
have been lost).

While we increase burstiness a bit we also get to retransmit sooner and
get the loss cleaned up as quickly and painlessly as possible.  E.g., we
have some simulations that show that when a retransmit is lost (and the
connection RTOs) the RFC3517 style recovery ends up sending a lot fewer
spurious retransmits in slow start loss recovery because we cleaned up a
bunch of loss earlier in the process.

> When the ack for segment 20 arrives (first partial ack) the value of
> pipe is recalculated to 2. Therefore only one segment can be
> transmitted. A new segment 26 could be then transmitted since no more
> segments have been determined as lost at this point. However reading
> Kevin Fall and Sally Floyd paper "Simulation-based comparisons of
> Tahoe, Reno and SACK TCP" pipe is decremented by two for every partial
> ack received. It seems to me that the RFC 3517 would not decrement
> pipe by two in my particular example. Is my understanding correct and
> can we say that decrementing pipe by two for every received partial
> ack cannot be generalised?

An important point, I think... The scheme in the Fall/Floyd paper is
what we started with in writing RFC3517.  However, we ended up some
place fairly different.  The spirit might be similar, but the details
are not.  So, reading both the Fall/Floyd paper and RFC3517 at the same
time might be a tad confusing in that the details are going to be
different.  I.e., you cannot generalize them and say "why does this
scheme decrement by 2 and this one only by 1?".  The reason is that they
started with two slightly different notions of "pipe" to begin with.  As
an example, Fall/Floyd start pipe at the number of outstanding segments
when loss recovery is entered.  Meanwhile, RFC3517 starts pipe from zero
and counts the number of things that it believes are still in the
network at various times within loss recovery.  These are similar in
their end result, but different in their approach.  The two documents
are filled with such things.

So, I think you should try to understand how each algorithm works
seperately without trying to intermix them and figure out why each
detail is different.

That said, you are right that RFC3517 does not decrement by 2 on each
partial ACK, while Fall/Floyd does.  But, the reason is that the schemes
use two different approaches.  Because one does and one does not is
fairly meaningless.  They are both reasonable choices in the context of
the particular scheme.

> My third question relates to the lost segment 25. When the partial ack
> for segment 24 arrives only one new segment (27) can be transmitted
> since pipe=2 and segment 25 is not determined yet as lost. Reading the
> definition of the procedure IsLost() defined in RFC 3517 it is my
> understanding that segment 25 cannot be retransmitted until three
> segments above the lost segment are SACKed since IsLost() determines
> the lost of a segment when "either DupThresh discontiguous SACKed
> sequences have arrived above 'SeqNum' or (DupThresh*SMSS) bytes with
> sequence numbers greater than 'SeqNum' have been SACKed". Essentially,
> in my example we need to receive three dupacks for segment 24 before
> we can retransmit segment 25. Am i wrong? My confusion comes from
> reading Fall&Foyd paper where they retransmit a lost segment
> (essentially after one dupack). Does the RFC 3517 allow for the
> operation described in this paper?

No.  In some sense the RFC provides more aggressive retransmission than
Fall/Floyd (by declaring some segments that have been "lost" as to have
left the pipe).  And, in other cases, (as you note above) the
retransmission behavior in the RFC can be viewed as more conservative.
That is, the RFC requires a higher bar before something is declared lost
and so is eligible for retransmission (assuming new data to send).

I hope that helps!

allman

--
Mark Allman -- ICIR -- http://www.icir.org/mallman/