Subject: [iccrg] Some notes on MPTCP Lisa

From: Costin Raiciu <[email-masked]>
Date: Thu, 15 Dec 2016 10:16:36 +0200

Hi all,

I’ve had a chance to read through the LISA draft following Michael Welzl’s request. 

First, I’d like to say that the draft identifies on a problem that matters when the number of subflows is large (datacenters), and matters very little in Internet-style setups (two subflows, one over cellular and one over wifi). The root of the problem is IW10 - IW3 was the standard was MPTCP was standardized. 

I believe the problem needs to be addressed, but I have some concerns about the proposed solution. I believe a simpler fix may be enough (see below).

The LISA draft proposes that a starting subflow borrows its IW from the CWND of an existing sub flow: this goes against the design of all multipath congestion controllers I know about: events on one path should never reduce the rate of subflows on other paths: the theoretical controllers by Kelly/Voice and Srikant/Towsley , as well as for all practical controllers including LIA, OLIA, BALIA only decrease the window when there is congestion notification on that path. LISA decrease the CWND when another subflow starts, tieing the performance of the initial subflow with the number and timing of additional subflow creation. The side effects of LISA are clear: when there are no shared bottlenecks, starting multiple subflows will repeatedly reduce the window of the first subflow, and thus its rate. This type of coupling is obviously suboptimal. 

I have also read the related Lisa paper: it is clear that the mechanism helps when there are shared bottlenecks, but the experiments for the case when there are no shared bottlenecks are not conclusive (sometimes Lisa helps, sometimes it hurts). My guess is that a broader exploration of the simulation parameters (e.g. buffer size, BW, RTT) will highlight it hurts more than it helps in this case.

How about a simpler solution: subsequent subflows should simply use IW=3; IW=10 should only be used for the first subflow. This should reduce MPTCP’s aggressiveness during slow start on shared bottlenecks, while breaking the unwanted coupling between subflows.

Cheers,
Costin

---

From: Michael Welzl <[email-masked]>
Date: Thu, 15 Dec 2016 10:04:17 +0100

Hi Costin,

Thanks a lot for this review!

Please see my answers below:

> On Dec 15, 2016, at 9:16 AM, Costin Raiciu <[email-masked]> wrote:
> 
> Hi all,
> 

I wouldn’t say it necessarily matters very little, and I also disagree that IW10 is the root of the problem - but the size of the IW does magnify it. LISA is about reducing a particular burst during a particular round-trip. If (as in your proposed solution below) you just use IW3 and then add, e.g., 3 more subflows (not a completely unlikely number, even in Internet-style setups, e.g. when using v4 and v6, or talking to a multi-homed server), this gives you a burst of 9 packets **on top of** the IW*4 packets that are being sent in the 3rd round trip. So if all flows would use IW3, this would mean a burst of 9 on top of 3*4 = 12 packets, i.e. the aggregate cwnd jumps from 6 to 21 instead of 12 packets. Whether this is a problem or not depends on your BDP and your queue length, but it does produce some extra delay whenever you share a bottleneck and I wouldn’t say that it generally matters very little.

> I believe the problem needs to be addressed, but I have some concerns about the proposed solution. I believe a simpler fix may be enough (see below).

As from above, your fix would mean: IW10 plus, in round 3, 3 subflows with IW3 each: IW10*4 = 40 packets + 9 on top.  The aggregate slow start behavior is, then: 10, 20, 49, 98, …    Again, this may not always be a huge problem but it doesn’t erase the burst in the 3rd round.

> The LISA draft proposes that a starting subflow borrows its IW from the CWND of an existing sub flow: this goes against the design of all multipath congestion controllers I know about: events on one path should never reduce the rate of subflows on other paths: the theoretical controllers by Kelly/Voice and Srikant/Towsley , as well as for all practical controllers including LIA, OLIA, BALIA only decrease the window when there is congestion notification on that path. LISA decrease the CWND when another subflow starts, tieing the performance of the initial subflow with the number and timing of additional subflow creation.

All of these other controllers are in CA, which is less bursty; the theory is based on a fluid flow model, making it irrelevant to what we’re trying to address here.

> The side effects of LISA are clear: when there are no shared bottlenecks, starting multiple subflows will repeatedly reduce the window of the first subflow, and thus its rate. This type of coupling is obviously suboptimal. 

No it’s not. If reducing cwnd (or, rather, limiting the increase of the aggregate cwnd in slow start) was “obviously suboptimal”, then e.g. Cubic’s Hystart would also be “obviously suboptimal”. In fact, limiting the burstiness of slow start tends to generally be a good thing (because it’s very bursty already).

> I have also read the related Lisa paper: it is clear that the mechanism helps when there are shared bottlenecks, but the experiments for the case when there are no shared bottlenecks are not conclu…

It’s obviously not conclusive when there are no shared bottlenecks, and showing that “sometimes it helps, sometimes it hurts” is what we wanted to show in these experiments. The issue is, it’s a matter of luck whether limiting your slow start increase hurts or helps - it depends on how much you will overshoot and how much the effect of that burst hurts you.

> How about a simpler solution: subsequent subflows should simply use IW=3; IW=10 should only be used for the first subflow. This should reduce MPTCP’s aggressiveness during slow start on shared bott…

So I hope I made it clear why this wouldn’t really solve the problem. Else, please take a look at this recent longer message where I explained things in more detail:
https://www.ietf.org/mail-archive/web/iccrg/current/msg01367.html <https://www.ietf.org/mail-archive/web/iccrg/current/msg01367.html>

Here’s a simpler way of looking at it:

Goal 2 of RFC 6356 reads: "Goal 2 (Do no harm) A multipath flow should not take up more capacity from any of the resources shared by its different paths than if it were a single flow using only one of these paths."

During the third round trip, this goal is not met by today’s uncoupled slow start, and it’s not met by your proposal. It is really only met by LISA (within the bounds given by the constants that it uses).

Cheers,
Michael

---

From: Costin Raiciu <[email-masked]>
Date: Fri, 16 Dec 2016 10:33:48 +0200

> I wouldn’t say it necessarily matters very little, and I also disagree that IW10 is the root of the problem - but the size of the IW does magnify it. LISA is about reducing a particular burst durin…

You can always construct a scenario where this matters; but I don’t think in practice it matters as much as you think.
The assumption of a shared bottleneck. In practice, this is a rather pessimistic assumption; more often than not the bottleneck will not be on the shared segment (e.g. close to the server) but on the client access links (wifi/3g). In the datacenter, people already deploy ECN with small marking thresholds (e.g. 30 according to DCTCP), so I am not sure it matters that much either.

> As from above, your fix would mean: IW10 plus, in round 3, 3 subflows with IW3 each: IW10*4 = 40 packets + 9 on top.  The aggregate slow start behavior is, then: 10, 20, 49, 98, …    Again, this ma…

Slow start is a transitory phase; the first subflow will deliver ~30 pkts before the second one gets a chance to send; this means most flows will finish before even the second subflow starts…

Nobody has mandated how the additional subflows should be opened; currently the model is open them all imediately after the first one is established. We could look at optimisations to reduce the  handshake overhead for small flows: why setup 8 subflows for a flow that is only 100KB? In this context, opening them sequentiially makes more sense, and the impact of slow start on multiple subflows is negligible.  Finally, in datacenters (where you could have many subflows) the BDP is rather small, and so are the buffers: if one staggers the creation of additional subflows it is likely than only one or very few will be in slow start simultaneously.

> All of these other controllers are in CA, which is less bursty; the theory is based on a fluid flow model, making it irrelevant to what we’re trying to address here.

The principle that the behaviour of one subflow should not decrease the rate of another good subflow still stands.

> No it’s not. If reducing cwnd (or, rather, limiting the increase of the aggregate cwnd in slow start) was “obviously suboptimal”, then e.g. Cubic’s Hystart would also be “obviously suboptimal”. In…

I don’t follow this implication. Hystart only applies to the connection in question, not to another connection potentially on a different path.

> https://www.ietf.org/mail-archive/web/iccrg/current/msg01367.html

How about starting new subflows with IW=1? It’s fine if they take longer to reach capacity.

> During the third round trip, this goal is not met by today’s uncoupled slow start, and it’s not met by your proposal. It is really only met by LISA (within the bounds given by the constants that it…

By enabling LISA you are not meeting another goal of MPTCP, which is to do no worse than TCP. LISA will penalize the first sub flow.

Cheers.
Costin

---

From: Michael Welzl <[email-masked]>
Date: Fri, 16 Dec 2016 13:44:48 +0100

> On 16 Dec 2016, at 09:33, Costin Raiciu <[email-masked]> wrote:
> 

So this is an argument for why any form of coupling doesn't matter much in practice, right?  I don't see what turns this into an argument pro/con LISA as part of the MPTCP coupled congestion control.

> Nobody has mandated how the additional subflows should be opened; currently the model is open them all imediately after the first one is established. We could look at optimisations to reduce the  h…

This is all correct; staggering the flows would certainly make the behaviour better - e.g. if you wait until each flow is in CA, then LISA won't even kick in, as LISA operates only on multiple flows in SS. That's good! Fix it this or that way - but as long as multiple subflows ARE in SS, LISA will help.

> I don’t follow this implication. Hystart only applies to the connection in question, not to another connection potentially on a different path.

... the relationship is that generally, by making SS **less** aggressive, Hystart achieves **better** throughput. Similarly, LISA does not consistently make things worse, and sometimes even makes them better, by making SS less aggressive. "decrease the rate" doesn't really capture it.

> How about starting new subflows with IW=1? It’s fine if they take longer to reach capacity.

That would make things even better than giving them IW=3  :)    and LISA would make things even better than that. It's just an extra burst of (num_subflows-1)*IW that you either have or don't, and if you make IW smaller than this burst becomes smaller. LISA eliminates it altogether.

> By enabling LISA you are not meeting another goal of MPTCP, which is to do no worse than TCP. LISA will penalize the first sub flow.

Only sometimes, and equally often it's making it work even better than it was before. TCP in slow start just isn't a fluid flow model - increasing slower can be very good for you (this is the point of my Hystart example).

Cheers,
Michael

---

From: Mark Handley <[email-masked]>
Date: Fri, 16 Dec 2016 16:02:45 +0000

On Fri, Dec 16, 2016, at 08:33 AM, Costin Raiciu wrote:
> By enabling LISA you are not meeting another goal of MPTCP, which is to
> do no worse than TCP. LISA will penalize the first sub flow.

It seems like this could be a particular problem when the RTTs on two
paths are very dissimilar.  Suppose you've a 1ms RTT with a 20 packet
cwnd on the first subflow and 100ms RTT on the new second subflow.    To
keep the same *rate* you should borrow 10 packets from subflow 1's cwnd,
multiply them by the ratio of RTTs, and use that as subflow 2's cwnd. 
In this case that means you'd need a cwnd of 1000 packets on subflow 2
to keep the same transmit rate.  Obviously this isn't sane.

The upshot of this, I think, is you shouldn't borrow cwnd from a lower
RTT subflow, as it will only hurt you.

Now, consider the reverse case.  Subflow 1 has a 100ms RTT and already
has a cwnd of 100 packets, and subflow 2 has a 1ms RTT.  Borrowing ten
packets from subflow 1 to send on subflow 2 will have a negligible
impact on subflow 1, but a large impact on subflow 2.  The effect is the
net rate increases by 10x, from 100 packets per 100ms to 10 packets per
1ms (in practice the linkspeed itself spaces those packets out further,
so the effect may not be quite so large).    In any event, borrowing ten
packets from a large RTT subflow to use on a small RTT path is going to
have almost exactly the same effect as just slowstarting subflow 2 from
ten packets without borrowing.  In this case there's no real benefit
from borrowing.

If I understand this right, then the only time when it seems LISA is
both safe and useful is when the RTTs are more or less equal.

Mark

---

From: Michael Welzl <[email-masked]>
Date: Sat, 17 Dec 2016 15:55:19 +0100

Hi,

Please don’t misunderstand me as being unnecessarily dismissive - I really do appreciate your interest.
Yet, I can’t help but say that absolutely everything in this email is wrong. So much so that I even found it hard to understand the mechanism that you describe at first (which  obviously isn’t LISA, by far). It is indeed an odd mechanism and not the right thing to do. I’m presenting an apple and you’re discussing an orange.

I’ll try to answer this a bit better in line:

> On Dec 16, 2016, at 5:02 PM, Mark Handley <[email-masked]> wrote:
> 
> 
> 

To start with, this statement that you’re quoting is wrong. There is, so far, no indication that LISA would consistently penalize the first sub flow.
Sometimes it does, yes - and about equally often it makes the first subflow alone work better too.

I believe that Costin’s answer, and yours, embeds the logic “smaller cwnd = penalize”. That may be true in fluid flow modeling, and it may hold in congestion avoidance. 
As I was trying to illustrate by pointing at Hystart (as one out of many proposals to make slow start less aggressive - Limited Slow Start (RFC 3742) is an older example), making slow start less aggressive is often a good thing - at least it’s not consistently a bad thing. There is no theory that I know of that undermines that slow start’s doubling is exactly the right thing to do - it's very aggressive and sometimes turns out well, and sometimes it doesn’t.

A few key facts about LISA:
- LISA does *not* let a subflow increase its cwnd faster than it would do without LISA
- thus, “borrowing” packets from another subflow isn’t an allowance to go faster, it’s just stopping the other subflow from increasing for a bit
- LISA also does not really reduce the rate of a subflow, it just stops it from increasing for a few packets, that’s all

All it does is reduce a burst that occurs as a new subflow joins, by stopping the first subflow from increasing for a few packets, yielding an aggregate cwnd behavior that’s closer to one flow in slow start than without it.

> to keep the same transmit rate.  Obviously this isn't sane.

Yes, it isn’t sane, and it isn't even remotely what LISA does.

> RTT subflow, as it will only hurt you.

FWIW, LISA (which doesn’t do what you propose) worked quite ok with different RTTs in our tests: see fig. 7b in
http://heim.ifi.uio.no/michawe/research/publications/icc16-lisa.pdf <http://heim.ifi.uio.no/michawe/research/publications/icc16-lisa.pdf>
as well as the 3G vs. WLAN test in the same paper, surely the RTT wasn’t 100% equal there either.

> ten packets without borrowing.  In this case there's no real benefit

This all makes sense for your mechanism that isn’t LISA.

> both safe and useful is when the RTTs are more or less equal.

Sorry, but you didn’t understand it right.

Cheers,
Michael

---

From: Michael Welzl <[email-masked]>
Date: Sat, 17 Dec 2016 16:28:42 +0100

Hi,

An add-on, as clarification - as I was trying to understand what it is about the draft that causes this misunderstanding - maybe this could help. We can include such an example in the draft:

maybe this thought of penalizing comes from the assumption that reducing cwnd really does decrease the rate.
However, in slow start, a moderate cwnd decrease just limits the increase because of the packets that are already in flight.

Just as an example, consider a flow with a cwnd of 10, which all are in transit. Say, we reduce cwnd of this flow by 5, to 5. Then, as the ACKs arrive, cwnd will grow up to 5 + 10 = 15 in the next round, instead of growing to 20. So the rate is 10 cwnd/RTT, then 15 cwnd/RTT - it doesn’t decrease (unless we decrease cwnd by more than the number of packets in flight, which LISA doesn’t do).

Cheers,
Michael

> On Dec 17, 2016, at 3:55 PM, Michael Welzl <[email-masked]> wrote:
> 
> Hi,
> 
>> On Dec 16, 2016, at 5:02 PM, Mark Handley <[email-masked] <mailto:[email-masked]>> wrote:
>> 
>> 
>> 
> _______________________________________________
> iccrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/iccrg

---

From: Michael Welzl <[email-masked]>
Date: Sat, 17 Dec 2016 22:10:44 +0100

Very sorry for the extra email - but to avoid confusion, I’ll add one more clarification: “which LISA doesn’t do” wasn’t completely correct. Under most normal circumstances, it won’t. If the number of subflows joining is very large, it might.

For the first subflow, LISA reduces cwnd and ignores just the right number of ACKs to give the subflow its right share after the round. So, e.g.:  subflow 1 has cwnd=40, and 40 packets in flight. We try to make sure that the next aggregate cwnd is 80. E.g., 1 extra subflow would take 10 packets, and get 20 in the round after, so LISA tries to make the first subflow get 60 after the round, which we can achieve by e.g. reducing cwnd to 30 and ignoring 10 acks (I’m ignoring delayed acks / ABC in this discussion for simplicity). The first subflow had 40 packets in transit; next round, it’ll have 60 packets in transit. We didn’t really reduce its rate.

However, if e.g. 3 more subflows would join at the same time, the reduction would indeed reduce the first subflow’s rate.
 
That’s because the primary goal of LISA is to make the aggregate cwnd behave as close as possible to the cwnd of one flow in slow start.

If we’d change this to always avoid reducing the rate of the first subflow, it would work just the same in the case of the two subflows above (though then this could be purely implemented by ignoring the right number of incoming ACKs without even touching cwnd), and in the case of more subflows joining, it would be more aggressive / more bursty than a single TCP flow, yet less aggressive/bursty than current MPTCP.

Cheers,
Michael

> On Dec 17, 2016, at 4:28 PM, Michael Welzl <[email-masked]> wrote:
> 
> Hi,
> 
>> On Dec 17, 2016, at 3:55 PM, Michael Welzl <[email-masked] <mailto:[email-masked]>> wrote:
>> 
>> Hi,
>> 
>> [email-masked] <mailto:[email-masked]>