[Tsvwg] TCP: SetPipe() in SACK draft

[Ken Calvert <[e-mail]>]

Folks,

We believe there is a problem with the SetPipe()
routine as defined in draft-allman-tcp-sack-12.txt.
It counts data that is considered lost, but has not
yet been retransmitted, as being in the pipe.  This
prevents retransmissions that should (we think) be
allowed.

Here is an example illustrating the problem: Assume that
there are 8 segments outstanding and cwnd=8.  The sixth,
seventh and eighth segments are SACKed, causing the recovery
phase to be entered.  cwnd is set to 4, and the first
segment is retransmitted.  At this point HighAck is just
before the first segment, HighData is the end of the eighth
segment, and HighRxt is the end of the first segment.

SetPipe() returns 5, and no other segments are retransmitted.
The problem is that if segment 1 is considered lost,
segments 2 through 5 should be also. Segments 2-4 should
be retransmitted, but they will not be under the current
algorithm. (End of example.)

We propose a different method of computing SetPipe(),
but along the same lines.  Consider two predicates
on sequence numbers:

- Lost(i) is true when the byte with sequence number
  i is considered lost.
- Rxd(i) is true if the sequence number i has been
  retransmitted during the current recovery phase.

These can be defined exactly as in the current draft
(i.e. IsLost and i <= HighRxt), but for the moment
we don't care how they are defined.

What's important is that each of these predicates
has a "monotonicity" property, in that there are
sequence numbers k_Lost and k_Rxt, such that each
predicate is true for all sequence numbers smaller
than its k (between HighAck and HighData), and
false for all others. The currently-used definitions
have this  property.

These predicates partition the unSACKed portion
of the outstanding sequence space into four parts
(some of which may be empty):

|-----------|-------------|------------|-------------|
|Lost && Rxd|Lost && !Rxd |!Lost && Rxd|!Lost && !Rxd|
      1           2             3            4

Part 1 contains #s that were returned per
clause (1) in earlier invocations of NextSeg()
(and the initially-retransmitted segment).
They should be counted once in computing pipe.

Part 2 contains those sequence #s that will be returned
by future invocations of NextSeg(), per clause (1) of
its definition. These bytes are considered to have
left the network but haven't been retransmitted and
should not be included in the pipe calculation.

Part 3 contains sequence #s that were returned per
clause (3) in earlier invocations of NextSeg().
They should be counted twice in computing pipe.

Part 4 contains sequence #s whose fate is
unknown, and which might or might not ever be
retransmitted (per clause (3) of NextSeg). They
should be counted once in computing pipe.

At any time, at least one of Part 2 or Part 3 is
empty. (This follows from the monotonicity property.)
Intially Part 3 is empty.  As HighRxt increases,
the boundary between 1 and 2 moves right
until Part 2 is empty; then seq #s (may) begin
to move from 4 to 3.

This leads to the following suggested
definition for SetPipe():

Between HighAck and HighData:

add 1 for each unSACKed sequence number i such that !Lost(i),
and 
add 1 for each unSACKed sequence number i such that Rxt(i).


Ken and Lili


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