Subject: [tcpm] FlightSizePrev in TCP-NCR

From: Lennart Schulte <[email-masked]>
Date: Wed, 13 Apr 2011 12:44:13 +0200

Hi folks,

we are currently implementing TCP-NCR in Linux.

Consider the following scenario:
The connection experiences a lot of reordering and all segments carry
SACK information, even those which advance the cumulative ACK point.
However loss recovery is never entered (reordering extent < dupthresh).

RFC5681 allows an increase of CWND for every ACK that advances the
cumulative ACK point, even if this ACK carries SACK information, so CWND
will grow during the connection's lifetime.

In contrast TCP-NCR calculates the number of segments to sent during
Extended Limited Transmit with FlightSizePrev (E.2). Also, if an ACK
arrives that advances the cumulative ACK point and also carries SACK
information, it sets the CWND to no more than FlightSizePrev (T.1).
Since FlightSizePrev is held constant for such an ACK and is not set
again (T.4), the CWND is not allowed to increase during the whole
connection when there is no ACK that does not carry any SACK
information. With this behavior the throughput will stay very low.

My questions are:
1) Why FlightSizePrev is used in E.2?
2) Why FlightSizePrev is not recalculated in T.4?

Thanks,
Lennart

---

From: Alexander Zimmermann <[email-masked]>
Date: Thu, 14 Apr 2011 18:30:56 +0200

Hi Mark, Hi Ethan,

here is one easy example:

Receiver:  2     4      1      6      3     ...
Sender:    S2    S2,4   A3,S4  S4,6   A5,S6

3517:      LT    LT     Inc    LT     Inc

with S=SACK, A=ACK, LT=Limited Transmit, Inc=CWND increase

> will grow during the connection's lifetime.

See example above...

> Extended Limited Transmit with FlightSizePrev (E.2).

(pipe + Skipped) <= (FlightSizePrev - SMSS)

... and not with CWND (like 3517). Why? => Main question (1)

> Also, if an ACK
> again (T.4),

Copy&Paste

(T.4) When an incoming ACK extends the cumulative ACK point and also
      contains SACK information, the initializations in steps (I.2) and
      (I.3) from Section 3.1 MUST be taken (but step (I.1) MUST NOT be
      executed) to re-start Extended Limited Transmit...

why "(I.1) MUST NOT be executed"? => Main question (2)

> the CWND is not allowed to increase during the whole

In example above, RFC3517 can still increase the CWND according
Slow Start or Congestion Avoidance, NCR get stucked.

> 2) Why FlightSizePrev is not recalculated in T.4?

//
// Dipl.-Inform. Alexander Zimmermann
// Department of Computer Science, Informatik 4
// RWTH Aachen University
// Ahornstr. 55, 52056 Aachen, Germany
// phone: (49-241) 80-21422, fax: (49-241) 80-22222
// email: [email-masked]
// web: http://www.umic-mesh.net
//

---

From: Alexander Zimmermann <[email-masked]>
Date: Tue, 19 Apr 2011 14:40:04 +0200

BTW, if anyone other than the two co-author has some time and is willing to help us,
especially the SACK specialists (Ilpo, Richard, Yuchung,...), be our guest... :-)

Alex

Am 14.04.2011 um 18:30 schrieb Alexander Zimmermann:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Hi Mark, Hi Ethan,
> 

//

---

From: Yuchung Cheng <[email-masked]>
Date: Thu, 21 Apr 2011 11:56:24 -0700

Sorry, I read the RFC have the exactly the same questions and plus a few
more ...

1) E.2 does not make sense that limited-transmit is only allowed if pipe
drops under FlightSizePrev == FlightSize when receiving some dubious ACK.
The RFC needs some clarification for this step.

2) T.4 skipping T.1 does not make sense either

3) Burst suppression in T.1 and T.2 are both MUST. I don't get it. Why
suppress burst upon detecting reordering, not loss? are reorderings highly
correlated to cwnd size. FWIW, Linux has similar logic which I find bizarre.

4) E.6. DupThresh will keep getting larger as limited-transmits increase
FlightSize.

Are there any studies on the effectiveness of TCP-NCR? AFAIK, Linux uses the
scoreboard to derive the reordering degree to compute dynamic dupthresh. The
mechanism seems simpler and more effective.

---

From: Mark Allman <[email-masked]>
Date: Thu, 21 Apr 2011 17:06:49 -0400

> Consider the following scenario: The connection experiences a lot of
> reordering and all segments carry SACK information, even those which
> advance the cumulative ACK point.  However loss recovery is never
> entered (reordering extent < dupthresh).

I think the real bottom line is that NCR doesn't well cover that case.
The cwnd is basically held constant during the event because (1) if it
is really loss then you're going to chop the cwnd in half and so who
cares and (2) if it is reordering then it should be worked out in an RTT
and so you lose an SMSS of cwnd growth and so who cares.  And, (2) is
true if it is only occasionally you see windows of packets that get
jumbled up.  But, if you see constant reordering RTT after RTT then I
can see where that might not hold and "who cares" might be too glib.
However, I guess I'd have to see some evidence that wasn't a totally
pathological case before I'd buy that there was something that needed
done about it.

allman

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Fri, 22 Apr 2011 08:38:12 +0100

Hi Mark,

when I read the RFC, the authors claim that NCR is supposed to allow TCP
to run unimpeded across future equipment that will introduce "heavy"
(from our current understanding) reordering more or less constantly....

If this was one of the design goals, there would be a (3) where constant
reordering is the norm (and not the exception), which was viewed at the
time of the RFC as a design goal (section 1, 3rd point in the
motivations list).

Based on that, it seems that Alex and Lennart have identified a bug
where the algorithm appears to contradict the design goal...

Richard Scheffenegger

> -----Original Message-----
> From: Mark Allman [mailto:[email-masked]]
> Sent: Donnerstag, 21. April 2011 23:07
> To: Lennart Schulte
> Cc: [email-masked]; [email-masked]
> Subject: Re: [tcpm] FlightSizePrev in TCP-NCR
> 
> 
> cares and (2) if it is reordering then it should be worked out in an
> RTT and so you lose an SMSS of cwnd growth and so who cares.  And, (2)
> is true if it is only occasionally you see windows of packets that get