Subject: [tcpm] Review of PRR

From: Mirja Kühlewind <[email-masked]>
Date: Wed, 1 Feb 2012 18:18:17 +0100

Hi Matt,

I reviewed the PRR algorithm. Actually I read your IMC paper and not the draft 
but I hope its the same algorithm ;-)

Let me summarize the main points from my understanding and then I have some 
questions/comments:

I think there are 3 changes compared to the current Linux implementation:

1) You removed the limitation that the cwnd can't be larger that fight_size+1 
in recovery
   -> Agreed, this limitation does not make sense and really causes problems

2) Make reduction dependent on congestion control
   -> This is an implementational thing. Currently Linux will reduce 
(hard-coded) on every second ACK which will (eventually) lead to a havling of 
the cwnd. I agree that this decision should be made by the CC algo but its 
mainly Linux not providing an easy interface to do so. 

3) SS like increase in recovery
   -> This follows directly from point 2. There is a way to reset the cwnd 
after recovery to any value but Linux will still limit the cwnd to 
flight_size+max_burst_size. max_burst_size is (hard-coded) 3 in Linux and 
this limitation make sense to avoid large bursts. Here comes your SS idea 
into the game. You try to maintain the min cwnd close to ssthresh in recovery 
to avoid any bursts right after recovery when you set your cwnd to the value 
determined by the congestion control algorithm.

Here my comments:

1) Bursts:
As said above the limitation to flight_size+1 is wrong and causes a too 
conservation behavior of the Linux kernel. But actually the problem is mainly 
because of the +1. I believe there should still be a limitation of the 
max burst size (e.g. 3 as used by Linux). In your algorithm it possible to 
have very arge burst in under certain circumstances, right?
At least there should be:
	At the end of recovery:
	cwnd = min(ssthresh, flight_size + max_burst_size)

2) SS:
The SS thing is a smart idea but I'm not sure if its really needed. You run 
into the SS part if you have large burst losses or you are 
application-limited. I would say both cases are worth to be conservative. As 
soon as you leave recovery and your cwnd is below ssthresh you will be in 
slow start anyway. You paper is saying in your measurement you were in 32% in 
the slow start phase at the beginning of recovery. This seems to be a really 
high value. Do you know what's happening there? Is this due to application 
limitations or burst losses? I would guess its loss. But if you have a lot of 
small transmission which hardly leave slow start, it might also explain this 
number. Maybe both cases even need to be handled differently...? 

3) DeliveredData:
You are using the number of ack'ed bytes. That means you need to have the cwnd 
and ssthresh also in bytes (not sure if this is said explicitly anyway). The 
Linux kernel mostly used number of packets and also assumes that there will 
be an ACK for every new packet in recovery. These assumptions might be not 
correct anymore. But I'm not sure if this should be changed implicit in this 
proposal. This might be an important topic on its own which might have more 
implications (if implemented every correctly). 

And I have two more questions:
2) In the paper you say this algorithm will be in the mainline of the Linux 
kernel. I checked and I dont think it is there yet...? Do you have a patch 
available? 
3) And one completely different question: In the paper you say ECN is disabled 
on Google servers. Why is this?

Regards,
Mirja

---

From: Matt Mathis <[email-masked]>
Date: Wed, 1 Feb 2012 11:01:49 -0800

First the quick answers: PRR is in Linux 3.2-rc1.

The implementation in Linux uses packet counts, not bytes.  Yes this causes
a number of artifacts.

The transactional nature of the web and video (codic) pacing both cause
frequent "application stalls" which cause much of our intuition about how
TCP typically operates to be somewhat inaccurate.

I believe that all of your suggestions were evaluated empirically and
didn't pan out.  Several alternative algorithms were tested but not
described in the paper.   I can speak to the one that surprised me, where
my intuition initially matched yours, but the numbers just didn't agree.

The issue is SS during recovery.    Consider the situation were the
cwnd=FlightSize=10, and you lose 8 packets.  Without slowstart during the
recovery it would be completed with a window of 2, taking 5 RTTs.
 Furthermore any additional losses are very likely to cause a timeout.
 Compare this to RFC3517, which allows a 3 packet burst, to complete the
recovery in 2 RTTs.

Although this seems like a corner case, it happens frequently enough to be
statistically significant in the measurement data.   For PRR, in this case
each of the two ACKs will cause 2 segments to be sent (4 total), as does
the first ACK of the next RTT (thus pipe=5).   Note that both RFC3517 and
PRR send 3 extra packets during recovery, either in a burst or
in response to  three different ACKs.

It turns out that due to the risk of additional losses, PRR's
average performance is  slightly better than RFC3517, even though under
identical conditions PRR transmits exactly the same amount of data but
slightly later.

If the existing standard had not specify something so aggressive, we may
have chosen to to do it as as you suggest, but proposing a
new standard that performs worse than the existing standard was a
non-starter.

I am working on an ID that proposes to re-factor TCP congestion control,
which will bring the many of your observations into focus.

Re: ECN.  Last time we checked it caused a measurable increase in the
number of failed user requests, probably due to return paths that
unconditionally discard packets with ECN marks.  Note that the forward path
must be delivering them, which seems rather odd.    But yes, we are
tinkering with ECN, and would like to help foster its deployment.

Thanks,
--MM--
The best way to predict the future is to create it.  - Alan Kay

---

From: Yuchung Cheng <[email-masked]>
Date: Wed, 1 Feb 2012 16:19:59 -0500

> First the quick answers: PRR is in Linux 3.2-rc1.
FYI: http://patchwork.ozlabs.org/patch/110857/

---

From: Mirja Kuehlewind <[email-masked]>
Date: Fri, 3 Feb 2012 18:03:59 +0100

Hi Matt,

I agree with a lot of things you said. But regarding your example of cwnd 10 
and 8 losses I'm not sure. You say its not a corner case. I understand that 
you have many small flows not leaving slow start. But in this case you have 
lost 80% of your packet. I would have expected a max loss of 50% of my 
packets in SS. For me that means 80% is a really high load situation and I 
should be even more careful...!?!

Mirja

Btw. if this is not a corner case maybe IW of 10 is not a good idea...

On Wednesday 01 February 2012 20:01:49 Matt Mathis wrote:
> > Let me summarize the main points from my understanding and then I have
> > some questions/comments:
> >
> > the cwnd. I agree that this decision should be made by the CC algo but
> > its mainly Linux not providing an easy interface to do so.
> >
> > max burst size (e.g. 3 as used by Linux). In your algorithm it possible
> > to have very arge burst in under certain circumstances, right?
> > The SS thing is a smart idea but I'm not sure if its really needed. You
> > run into the SS part if you have large burst losses or you are
> > high value. Do you know what's happening there? Is this due to
> > application limitations or burst losses? I would guess its loss. But if
> > you have a lot of
> > Linux kernel mostly used number of packets and also assumes that there
> > will be an ACK for every new packet in recovery. These assumptions might
> > be not correct anymore. But I'm not sure if this should be changed
> > implicit in this
> > proposal. This might be an important topic on its own which might have
> > more implications (if implemented every correctly).
> >
> > 2) In the paper you say this algorithm will be in the mainline of the
> > Linux kernel. I checked and I dont think it is there yet...? Do you have
> > a patch available?

-- 
-------------------------------------------------------------------
Dipl.-Ing. Mirja Kühlewind
Institute of Communication Networks and Computer Engineering (IKR)
University of Stuttgart, Germany
Pfaffenwaldring 47, D-70569 Stuttgart

tel: +49(0)711/685-67973
email: [email-masked]
web: www.ikr.uni-stuttgart.de
-------------------------------------------------------------------

---

From: Mirja Kühlewind <[email-masked]>
Date: Fri, 3 Feb 2012 18:04:13 +0100

thx.

---

From: Matt Mathis <[email-masked]>
Date: Fri, 3 Feb 2012 12:44:33 -0800

I should have been clearer.   The "not a corner case" I was referring to
was losses exceeding the chosen window reduction, which is the situation
that causes 3517 to send bursts and PRR to invoke slowstarts during
recovery.   We observe that this happens in 32% of the recovery events.

You are correct that a single connection into a single bottleneck should
not cause more than %50 losses.   The most likely cause are bursts on other
connections.  Note that depending on how the packets from two
concurrent slowstarts are interleaved, you expect the losses from to be
slightly asymmetric.    If the receiver is doing "fast ACKs" to speed
slowstart, then you would expect more than 50% losses to
be reasonably common.

However, the primary cause for our data was probably QUBIC itself, which
only invokes a 30% reduction.  This plus fast ACK plus drop tail is likely
cause losses to frequently exceed the target reduction.

We do not have data on how frequently connections experience 80% losses

And you are correct, IW10 could be contributing.  We tried to quantify
that, but couldn't.  What is really needed is  a TCP header study
from within an ISP, just upstream of the primary bottleneck, for all sorts
of types of bottleneck gear, clients and content sources.

Thanks,
--MM--

On Fri, Feb 3, 2012 at 9:03 AM, Mirja Kuehlewind <
[email-masked]> wrote:

> > > I reviewed the PRR algorithm. Actually I read your IMC paper and not
> the
> > > draft
> > > application-limited. I would say both cases are worth to be
> conservative.
> > > As
> > > You are using the number of ack'ed bytes. That means you need to have
> the
> > > cwnd
> > > and ssthresh also in bytes (not sure if this is said explicitly
> anyway).
> > > The