Subject: [tcpm] rfc2581bis [2]: limiting cwnd inflation

From: Mark Allman <[email-masked]>
Date: Tue, 13 Feb 2007 10:03:47 -0500

Reminder, the draft should pop out of the usual places soon, but until
then you can slurp a copy from:

    http://www.icir.org/mallman/papers/draft-ietf-tcpm-rfc2581bis-02.txt

The second issue ...

We added a note to step 4 of the fast retransmit/recovery procedure:

    4.  For each additional duplicate ACK received (after the third),
        cwnd MUST be incremented by SMSS.  This artificially inflates
        the congestion window in order to reflect the additional segment
        that has left the network.
    
        Note: [SCWA99] discusses a receiver-based attack whereby many
        bogus duplicate ACKs are sent to the data sender in order to
        artificially inflate cwnd and cause a higher than appropriate
        sending rate to be used.  A TCP MAY therefore limit the number
        of times cwnd is artificially inflated during loss recovery
        to the number of outstanding segments (or, an approximation
        thereof). 

That is, we explicitly allow a TCP to limit the number of dupacks that
are acceptable during fast recovery to prevent an attack such as
discussed in [SCWA99].

Note that (1) this is more conservative than the algorithm in 2581 and
so implicitly allowed already (that is, we are just calling attention to
this) and (2) we are not trying to mandate this behavior, just noting
that it might be useful.

Comments would be appreciated.

Thanks,
allman

---

From: "Anantha Ramaiah \(ananth\)" <[email-masked]>
Date: Tue, 13 Feb 2007 21:13:13 -0800

I was having some private email discussions with Mark when the previous
version was released, basically talking about limiting the artifical
cwnd inflation during fast recovery. Now, the following text which is
added in the new version of this draft talks about the mis-behaving
receivers only. What I had in mind was about in general (whether or not
the receiver is mis-behaving, this applies). To illustrate this :-

Assume that flightsize = f during fast recovery. Assume f > 2 SMSS

When the  3rd duplicate Ack arrives, 

ssthresh = max (FlightSize / 2, 2*SMSS)
Ssthresh = max ( f/2, 2*smss) = f/2.

Now cwnd = f/2 + 3*SMSS

For each duplicate ACK which arrives after that (assuming that the first
segment got dropped) *in theory* you could get 6 duplicate ACK's [This
is NOT a mis-behaving receiver] Since every out-of-order segment ought
to be ACKED immediatley and shouldn't be delayed.

So we would have incremented the cwnd by :-

Cwnd  = (f/2 + 3*SMSS) + 6SMSS > f.  This can happen since there seems
to be no explicit rule to cap the cwnd growth which may cause the higher
than appropriate sending rate to be used.  To make the above example
assuming f = 10 before fast recovery entered, we would be in a situation
where cwnd becomes 14!!, which is un-desirable.

So I would think the text needs to be more generic something like :- 

"Note: Since, in theory, the cwnd can get artifically inflated to a
value greater than what it was before the fast recovery procedure was
entered, a TCP MAY limit the number of times cwnd is artificially
inflated during loss recovery to the number of outstanding segments (or,
an approximation thereof). Also this helps in dealing with
receiver-based attack wherby many bogus duplicate ACKS are sent to the
data sender in order to artifically inflate the cwnd and cause higher
than appropriate sending rate to be used."

Mark suggested that I send this to the wider audience to see if there is
some general consensus on this.

-Anantha
> -----Original Message-----
> From: Mark Allman [mailto:[email-masked]] 
> Sent: Tuesday, February 13, 2007 7:04 AM
> To: [email-masked]
> Subject: [tcpm] rfc2581bis [2]: limiting cwnd inflation
> 
>  
> Reminder, the draft should pop out of the usual places soon, 
> but until then you can slurp a copy from:
> 
>     
> That is, we explicitly allow a TCP to limit the number of 
> dupacks that are acceptable during fast recovery to prevent 
> an attack such as discussed in [SCWA99].
> 
> Note that (1) this is more conservative than the algorithm in 
> 2581 and so implicitly allowed already (that is, we are just 
> calling attention to
> this) and (2) we are not trying to mandate this behavior, 
> just noting that it might be useful.
> 

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

---

From: Mark Allman <[email-masked]>
Date: Wed, 14 Feb 2007 00:36:05 -0500

> where cwnd becomes 14!!, which is un-desirable.

It is not.  After out iteration earlier today I went through this in
more detail in my head.  You want cwnd to grow past where it was before
recovery.  That is how you're able to strobe new segments out.  Simple
example:

FlightSize=40
lose 1 segment; expect 39 dupacks (say none are lost)
after the 3rd dupack:
  cwnd = (FlightSize / 2) + 3 = 23
  ssthresh = FlightSize / 2 = 20
  retransmit
receiver 36 more dupacks, on each:
  cwnd += 1
  if FlightSize < cwnd:
    transmit
    FlightSize += 1
receive an ACK for everything
  cwnd = ssthresh

So, basically before the rexmt is ACKed cwnd will be 59 segments---or,
19 more than it was before the loss happened.  But, this increase is
termed *artificial*.  We did not put 59 segments into the network during
the last RTT, we put 19 segments into the network (or, half of the
FlightSize when the loss occured)---so, we did in fact halve our rate
even though the cwnd is larger.  Before continuing the cwnd collapses
back to what it ought to be (20 segments in this case).

What the new text is attempting to do is to allow stacks to protect
against malicious receivers that strobe many more dupacks into the
stream to boost the sending rate.  Regardless of the value of cwnd, I
don't think there is a case whereby you'll be actually putting an
inappropriate number of segments into the network when things are
working properly.

allman

---

From: "Anantha Ramaiah \(ananth\)" <[email-masked]>
Date: Tue, 13 Feb 2007 23:50:34 -0800

> From: [email-masked] [mailto:[email-masked]] 
> Sent: Tuesday, February 13, 2007 9:36 PM
> To: Anantha Ramaiah (ananth)
> Cc: [email-masked]
> Subject: Re: [tcpm] rfc2581bis [2]: limiting cwnd inflation 
> 
> > to be no explicit rule to cap the cwnd growth which may cause the 
> > higher than appropriate sending rate to be used.  To make the above 
> > example assuming f = 10 before fast recovery entered, we 
> would be in a 
> > situation where cwnd becomes 14!!, which is un-desirable.
> 
> It is not.  After out iteration earlier today I went through 
> this in more detail in my head.  You want cwnd to grow past 
> where it was before recovery.  That is how you're able to 
> strobe new segments out.  Simple
> example:
> 
> FlightSize=40
> lose 1 segment; expect 39 dupacks (say none are lost) after 
> the 3rd dupack:
> 19 more than it was before the loss happened.  But, this 
> increase is termed *artificial*.  We did not put 59 segments 
> into the network during the last RTT, we put 19 segments into 
> the network (or, half of the FlightSize when the loss 
> occured)---so, we did in fact halve our rate even though the 
> cwnd is larger.  Before continuing the cwnd collapses back to 
> what it ought to be (20 segments in this case).

Ok, you are right on this, Mark. Basically the cwnd can grow up to a
maximum of (3f-2)/2 during fast recovery [ f denotes the flightsize
before entering FR]. Due to some interrmitent re-ordering in the
network, we could construct scenarios like below :-

Assume 40 segments sent out (f = 40), 1st segment got dropped. [same
example as above]
We get, lets say, 11 acks which fills the hole, which makes cwnd = 31
(20+11), f = 29(40 -11), after we still have remaining 28 acks, which
can slide the window one segment at a time [I am assuming that the
fast-retransmitted segment "overtook" the 28 segments . Of course I am
assuming some genuine networking scenarios like load balancing
scenarios/network conditions which causes some irregular ACK pattern
which can cause more than needed segments to be sent out. [ "needed
segments" = f/2 = 20 when we entered fast recovery]

Anyways, it appears that I may be trying hard to convince you on this,
but bottomline is we can construct scenarios.

> 
> What the new text is attempting to do is to allow stacks to 
> protect against malicious receivers that strobe many more 
> dupacks into the stream to boost the sending rate.  

Sure there is no issue with the existing text, but I was trying to make
it more generic.
Also it is not just mis-behaving receivers, another reason which I can
think of is some intermittent packet duplication can cause this as well.

> Regardless of the value of cwnd, I don't think there is a 
> case whereby you'll be actually putting an inappropriate 
> number of segments into the network when things are working properly.

Hmm.. This is what I am not too sure about, my loose example above tries
to demonstrate this. But in many real life scenarios partial ack's are
common which kicks in New Reno which has protection against window
deflation anyways since the cwnd gets reduced further.. May be it isn't
as worst as I think, I don't know.

-Anantha

---

From: Mark Allman <[email-masked]>
Date: Wed, 14 Feb 2007 09:04:13 -0500

> segments" = f/2 = 20 when we entered fast recovery]

I don't understand this.  As soon as the window slides we are out of
fast recovery, the cwnd collapses back down and we go to congestion
avoidance to govern sending instead of the fast recovery rules.  How
does the above lead us to sending inappropriately.

> think of is some intermittent packet duplication can cause this as

Yep.  And, I willing to add a parenthetical or something about this
point.  But, for this to be a problem you'd have to have a *lot* of
duplication (which runs against all the evidence about that phenomenon
that I have seen).  I.e., I am not worried about a couple extra dupacks
throwing us off a little.  The concern here is that mis-behavior can
cause many times more segments than appropriate to be sent.

> > Regardless of the value of cwnd, I don't think there is a case
> > whereby you'll be actually putting an inappropriate number of
> > segments into the network when things are working properly.
> 
> Hmm.. This is what I am not too sure about, 

Show us how.

(I am not saying there is not a scenario.  I just haven't yet seen a
scenario that would cause a big problem in the absence of a mis-behaving
receiver.  (Or, a very very flawed network element that is duplicating
packets like nobody's business.))

allman