Subject: [Tsvwg] (no subject)

From: Lili Wang <[email-masked]>
Date: Thu, 1 Aug 2002 14:19:52 -0400 (EDT)

This message is about the internet draft " A Conservative SACK-based
Loss Recovery Algorithm for TCP".
   We guess that one reason to forbid the recovery algorithm before the
cumuulatively ACK past RecoveryPoint is  to avoid false fast
retransmission. To avoid the problem, we think that it  need to forbid
invoking the algorithm to a further point  beyond what is specified in
the draft(RecoveryPoint).
    In recovery peroid, the sender may send
new data (according to rule(2) in NextSeg()). In this case, 
HighData is above RecoveryPoint. Thus, the data between RecoveryPoint
and HighData have been transmitted in the recovery peroid. If a tomeout
occurs later in the recovery period, the sender begin slow start. Since
the data between RecoveryPoint and Highdata may be already in the
receiver queue, retransmission of those data  may generate duplicate ACKs,
 which may cause false fast retransmission. For example. suppose recovery
point is the right edge of segment n and segment n is lost.
During loss recovery phase, segment n+1, n+2, n+3 have been transmitted
and successfully  received by the receiver. 
A timeout occurs later in the recovery perid and the sender begin slow
start. Segment n, n+1, n+2, n+3, n+4 are (re)transmitted. Receipts
of segment n, n+1, n+2 and n+3 all generate an ACK that tells the sender
to expect segment n+4 (suppose segment n+4 is not in the receiver
queue at that time). Since the  cumulatively acknowledgment has been
beyond the last value of RecoveryPoint, the loss recovery is invoked upon
receipt of enough duplicate ACKs. However, in this case, there is 
no segment loss , it should not invoke the recovery algorithm.

Cheers,

Lili and Ken

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

---

From: Lili Wang <[email-masked]>
Date: Tue, 6 Aug 2002 11:05:01 -0400 (EDT)

On Mon, 5 Aug 2002, Mark Allman wrote:
 
> > To avoid the problem, we think that it need to forbid invoking the
> > algorithm to a further point beyond what is specified in the
> > draft(RecoveryPoint).
> 
> Yep.  Ethan and I just chatted about it and we are inclined to
> agree.  Is the following what you're suggesting?
> 
>   * When we RTO we reset RecoveryPoint to HighData
>   * We surpress fast retransmit until we receive a cumulative ACK
>     for RecoveryPoint (as now)

    The false fast retransmission problem may still exist even   
after taking the above policy.  Of course, the possiblity of occurence of
the problem is lower than before. To solve the problem,  it need to forbid
invoking loss recovery algorithm to a further point beyond
HighData. But I am not sure whether it is a good way, because it
may cause timeout in the face of segment loss without invoking
 the recovery algorithm at some point. It may be
better to find a way to distinguish the duplicate ACK caused by receipt of
data that is already in the receiver's queue from one that is caused by
reordered new segment or segment loss.
    
   However, there is another advantage of not allowing to invoke the
recovery algorithm before the cumulative ACK is beyond
HighData. If the loss recovery algorithm is
invoked before the HighData, there may exist some
segments that could not be (re)transmitted when they need to,
because those segments could not returned by NextSeg(). For example,
some segments are transmitted before RTO but are lost. After RTO, if the
recovery algorithm is invoked before those segment are transmitted, those
segments could not returned by NextSeg() if they are not less than the
highest ocet covered by any received SACK, because those segments are
below HighData.

Lili

---

From: Mark Allman <[email-masked]>
Date: Mon, 05 Aug 2002 15:23:25 -0400

Lili-

Thanks for the comments.

> retransmission. 

Yes.

??

Thanks!

allman

--
Mark Allman -- NASA GRC/BBN -- http://roland.grc.nasa.gov/~mallman/

---

From: Ken Calvert <[email-masked]>
Date: Sat, 17 Aug 2002 09:03:28 -0400 (EDT)

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