Subject: [multipathtcp] We don't need to detect shared bottlenecks

From: Costin Raiciu <[email-masked]>
Date: Wed, 13 May 2009 11:33:28 +0100

Hi,

As this is my first message on this list, I'd like to introduce  
myself: I am a PhD student at UCL working with Mark Handley and Damon  
Wischik on multipath TCP.

Theory tells us (e.g. Frank Kelly's paper "joint routing and rate  
control") that we don't  need to detect shared bottlenecks  
explicitly. The rough idea is
to make an the ensemble of multipath subflows act as a single one,  
always assuming they share a bottleneck.

Let me give you an example; say we have two sublfows on exactly the  
same path, with windows w1 and w2, and our strategy is to increase w1  
with 1 whenever
w1+w2 packets are acknowledged on subflow 1,  and with 1 whenever w1 
+w2 packets are acknowledged on subflow 2. When we get a drop on  
subflow 1,
we reduce w1 with (w1+w2)/2; if w1 is less than one after the  
decrease, set it to one. The same goes for subflow 2.

This simple strategy makes the aggregate behave like a single tcp  
flow, with exactly the same aggressiveness.
It is true that traffic will move from one flow to the other  
depending on the , but why should we care? Assuming we can manage  
reordering of packets, this should be the same as
a single flow.

As for traffic oscillations at the bottleneck: this will not  
oscillate worse than TCP already does.

So far we have assumed there is a shared bottleneck, and were fair to  
TCP there. What is we have two completely disjoint paths? The net  
effect will be that traffic will
be pushed towards the paths with the lower drop probability,  
therefore achieving resource pooling (see "the resource pooling  
principle" ccr paper for more).
As a net effect, if everybody runs multipath tcp, there will be large  
swades of the network where the drop probability is the same.
The discussion in this latter case is more involved (we are currently  
running experiments to fill the picture).

Cheers.
Costin

---

From: Bryan Ford <[email-masked]>
Date: Wed, 13 May 2009 16:54:18 +0200

On May 13, 2009, at 12:33 PM, Costin Raiciu wrote:
> myself: I am a PhD student at UCL working with Mark Handley and  
> Damon Wischik on multipath TCP.
>
> same path, with windows w1 and w2, and our strategy is to increase  
> w1 with 1 whenever
> w1+w2 packets are acknowledged on subflow 1,  and with 1 whenever  
> w1+w2 packets are acknowledged on subflow 2. When we get a drop on  
> subflow 1,
> So far we have assumed there is a shared bottleneck, and were fair  
> to TCP there. What is we have two completely disjoint paths? The net  
> As a net effect, if everybody runs multipath tcp, there will be  
> large swades of the network where the drop probability is the same.
> The discussion in this latter case is more involved (we are  
> currently running experiments to fill the picture).

I'm somewhat familiar with this joint congestion control work, and it  
sounds very promising to me - I only wish someone would write a  
version of that paper that's a bit more readable by non-theory folks   
(hint, hint ;) ).  This absolutely needs to be followed up with more  
practical experimentation, regardless of whether this BOF/WG proves to  
be the right place for that to happen.

One outstanding question I have is whether this joint rate control  
approach extends easily to non-Reno congestion control schemes (e.g.,  
TFRC, Microsoft's CTCP, and other "TCP-friendly" alternatives), or  
explicit schemes like XCP/RCP.

Another question is whether this or a similar approach to tying  
multiple congestion control loops together could apply naturally not  
just to multipath transports but to multipath _applications_, as in  
HTTP or BitTorrent for example.  It seems to me that this should be  
relatively easy to accomplish if the multiple flows are to be tied  
together at a given sender, regardless of whether the flows are to the  
same receiver (e.g., multipath transport, or multi-connection HTTP) or  
to different receivers (e.g., BitTorrent).  For example, if an OS's  
TCP stack provided a simple API extension by which applications could  
indicate that a certain set of TCP connections should be treated  
jointly for congestion control purposes, then applications like web  
browsers and BitTorrent clients could use the same mechanism  
independent of whether TCP or any transport supports multipath  
natively between a given pair of hosts.  How to tie flows together at  
the receiver side is not so obvious, nor is how receiver-side flow  
joining would interact with sender-side flow joining when the two  
sides don't necessarily agree on a common set of send and receive  
endpoints to be tied together (again, BitTorrent).  But regardless of  
whether or how these problems might be solved, if this BOF/WG is going  
to spend a lot of time trying to solve the multipath fairness/ 
agressiveness problem like Frank Kelly's work tries to do, it needs to  
consider this problem not just in the context of multipath transports  
(which are still completely nascent and thus really have no economic/ 
industry impetus at the moment) but in the context of multipath  
applications (which are already widespread and for which a solution  
could therefore could provide a much bigger immediate impact).

Bryan

>
> Cheers.
> Costin
>
>
> _______________________________________________
> multipathtcp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/multipathtcp

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 13 May 2009 17:24:08 +0200

On 13 mei 2009, at 12:33, Costin Raiciu wrote:

> say we have two sublfows on exactly the same path, with windows w1  
> and w2, and our strategy is to increase w1 with 1 whenever
> w1+w2 packets are acknowledged on subflow 2.

Are you sure?

The way I understood this approach is that the different congestion  
windows for the different subflows grow with the standard 1 MSS per  
RTT independently, but then when there is congestion:

> When we get a drop on subflow 1,

This is the opposite approach of what I talked about the other day  
where we may limit the cwnd increase but the decrease after a drop is  
the normal cwnd/2.

There are three problems with the approach you outline:

1. Suppose w1 is 1000 and w2 is 2000. After a drop on subflow 1 you  
would have to decrease w1 by 1500, making it -500. That doesn't work.

2. cwnd in isolation is meaningless. I can have 10000 bytes/s with a  
cwnd of only 10 bytes (RTT 1 ms) or with a cwnd of 2500 (250 ms).  
Adding up cwnds that have different RTTs creates meaningless results.  
I believe in your tests you saw this reflected in the fact that higher  
RTT paths are preferred in this scheme.

3. Growing fast and backing off hard makes the sawtooth cycles faster  
so the network becomes burstier.

Iljitsch

---

From: Costin Raiciu <[email-masked]>
Date: Wed, 13 May 2009 18:14:20 +0100

Hi,

> RTT independently, but then when there is congestion:

To get resource pooling you must couple the increases too. There are  
other ways that you could achieve fairness, e.g. increase with 1/2  
per RTT, but those don't get you resource pooling.

> where we may limit the cwnd increase but the decrease after a drop  
> is the normal cwnd/2.
>
I agree there will be "clipping effects" because you can't set cwnd  
less than 1. To mitigate this, you can tweak the increase/decrease  
parameters so that you are still tcp fair, but avoid clipping most of  
the time. E.g. increase with
1/2 packet per RTT (for the whole connection) and drop with 1/4 of  
the total cwnd.

>
> 2. cwnd in isolation is meaningless. I can have 10000 bytes/s with  
> a cwnd of only 10 bytes (RTT 1 ms) or with a cwnd of 2500 (250 ms).  
> Adding up cwnds that have different RTTs creates meaningless  
> results. I believe in your tests you saw this reflected in the fact  
> that higher RTT paths are preferred in this scheme.

This is true. Because of the RTT bias, it looks like we will have to  
introduces rates in this computation, instead of cwnds.

>
> 3. Growing fast and backing off hard makes the sawtooth cycles  
> faster so the network becomes burstier.
Not if you choose milder parameters. Anyways, bursty is not always  
bad; for one thing, it breaks synchronization between flows.

Costin

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 13 May 2009 23:19:33 +0200

On 13 mei 2009, at 19:14, Costin Raiciu wrote:

> To get resource pooling you must couple the increases too.

No, I don't think so... coupling one should be enough.

> There are other ways that you could achieve fairness, e.g. increase  
> with 1/2 per RTT, but those don't get you resource pooling.

(For those who haven't read the resource pooling paper: the idea is if  
you have a bunch of links (paths) where each user can use a subset of  
the links, we make the users react to congestion on each link by  
shifting traffic to less congested ones such that the set of links  
behaves like a single big one.)

Even if you don't couple at all so an MPTCP takes the same amount of  
capacity on a given link, you get weak resource pooling because the  
additional path makes the transfer complete faster so the link we're  
interested in sees less traffic than in the single path case.

> less than 1.

An unfortunate side effect of this is that it makes the behavior of  
the algorithm hard to model.

> introduces rates in this computation, instead of cwnds.

Right.

However, I think with all these changes you're now so far from Reno  
that you've basically created a completely new cc scheme, and we'd  
have to carefully model it or run experiments to see how it behaves  
compared to Reno.

Not having done that, I expect that your scheme (TCP London?) can't  
match the performance of (New)Reno on the fastest path in all cases,  
so there could be situations where enabling MPTCP reduces performance.  
That would be a problem.

> bad; for one thing, it breaks synchronization between flows.

Burstier means more losses for the same utilization and buffering,  
which means reduced performance in a loss based cc.

---

From: Costin Raiciu <[email-masked]>
Date: Thu, 14 May 2009 09:39:27 +0100

Hi,

> approach extends easily to non-Reno congestion control schemes  
> (e.g., TFRC, Microsoft's CTCP, and other "TCP-friendly"  
> alternatives), or explicit schemes like XCP/RCP.
We are finding it difficult to retrofit it to Reno :), so I don't  
know about the others. As I hinted in the previous email, the RTT  
dependence of throughput makes it difficult to use cwnd to get  
resource pooling. If all RTTs are the same it works, otherwise not  
necessarily. I would guess its easier for protocols where RTTs do not  
determine achieved throughput, but I don't know for sure.
> multiple congestion control loops together could apply naturally  
> not just to multipath transports but to multipath _applications_,  
> as in HTTP or BitTorrent for example.  It seems to me that this  
> should be relatively easy to accomplish if the multiple flows are  
> to be tied together at a given sender, regardless of whether the  
> flows are to the same receiver (e.g., multipath transport, or multi- 
> connection HTTP) or to different receivers (e.g., BitTorrent).  For  
> example, if an OS's TCP stack provided a simple API extension by  
> which applications could indicate that a certain set of TCP  
> connections should be treated jointly for congestion control  
> purposes, then applications like web browsers and BitTorrent  
> clients could use the same mechanism independent of whether TCP or  
> any transport supports multipath natively between a given pair of  
> hosts.  How to tie flows together at the receiver side is not so  
> obvious, nor is how receiver-side flow joining would interact with  
> sender-side flow joining when the two sides don't necessarily agree  
> on a common set of send and receive endpoints to be tied together  
> (again, BitTorrent).  But regardless of whether or how these  
> problems might be solved, if this BOF/WG is going to spend a lot of  
> time trying to solve the multipath fairness/agressiveness problem  
> like Frank Kelly's work tries to do, it needs to consider this  
> problem not just in the context of multipath transports (which are  
> still completely nascent and thus really have no economic/industry  
> impetus at the moment) but in the context of multipath applications  
> (which are already widespread and for which a solution could  
> therefore could provide a much bigger immediate impact).

These are interesting observations. Mark has a student working on  
multi-server http, which is the opposite of what you propose: the  
receiver will fetch different data from different replicated servers,  
downloading more from servers that are closer. Here there is no  
explicit coupling of CC, but still we get job level resource pooling  
- users with fast paths will tend to push the download of web objects  
on those paths. Since web objects are small/moderately sized, the  
busy links will be utilized less for users with fast alternatives.  
If, however, web pages were infinite in size (or requests will follow  
immediately after each downloaded page, in an infinite loop) we don't  
get resource pooling anymore: the users with fast links will still  
utilize the busy links all the time,getting an overall unfair share  
of the network.

It is an interesting idea to couple the flows at the sender with  
different receivers like you propose in BitTorrent. It seems like the  
effect would be to get resource pooling in that case too: if there  
are multiple replicas of all files, traffic will flow mostly on  
uncongested links. This could have perverse outcomes too, for users  
that only have congested links to the data sources: they will get  
very little throughput. Also, at first glance, this seems to break  
the tit-for-tat incentive scheme.

Taking a step further, one could couple CC all flows coming out of a  
given machine, which would get you resource pooling, but likely with  
disastrous effects :).

Cheers
Costin

---

From: Michio HONDA <[email-masked]>
Date: Thu, 14 May 2009 18:24:34 +0900

Hi,

> No, I don't think so... coupling one should be enough.
I agree with Iljitsch.
with 1 > whenever

I don't think this approach works, because it looks that behavior on one 
subflow affects the other subflows, reducing overall performance of the 
bundle of subflows.

>> with 1/2 per RTT, but those don't get you resource pooling.
This approach is appropriate (more exactly, increase with (1/2)^2 per 
RTT based on the TCP response function).
Costin, could you please why this approach doesn't get resource pooling?

In addition, now, the discussion mixes up the resource pooling and the 
shared bottleneck.
In fact, resource-pooling congestion control and shared bottleneck aware 
congestion control work similarly, however, we would need separate 
consideration between them, because fairness in the multipath case is 
not clear now.
Do we actually need to share resources equally between different 
bottlenecks?
We might not need to share equally resources across different bottleneck.

-- 
Michio Honda
E-mail: [email-masked], [email-masked]
Website: http://www.micchie.net/

---

From: David Ros <[email-masked]>
Date: Thu, 14 May 2009 16:43:11 +0200

Hi,

Could you please elaborate a little on this?

(I'm surely missing something obvious, but what you say regarding  
burstiness seems to somewhat contradict what some people [including  
us] have found, at least in the context of high-speed TCPs)

Regards,

David.

---

From: Costin Raiciu <[email-masked]>
Date: Fri, 15 May 2009 00:14:22 +0100

Hi,

> > Let me give you an example; say we have two sublfows on exactly  
> the same path, with windows w1 and w2, and our strategy is to  
> increase w1 with 1 > whenever
> I don't think this approach works, because it looks that behavior  
> on one subflow affects the other subflows, reducing overall  
> performance of the bundle of subflows.
That is the whole idea with resource pooling; people will tend to use  
better paths always, therefore increasing the efficiency of the  
network. Nobody guarantees that if you do multipath
at any given user you will get double the throughput.
>
>>
>>> There are other ways that you could achieve fairness, e.g.  
>>> increase with 1/2 per RTT, but those don't get you resource pooling.
> This approach is appropriate (more exactly, increase with (1/2)^2  
> per RTT based on the TCP response function).

Below is an example of why not coupling the increases doesn't achieve  
resource pooling.

I attach are three plots obtained by running different multipath cc  
algorithms in a simple cwnd simulator (that I tested against a real  
implementation, so I have a bit of confidence it does not produce  
garbage :) ). The algos tested are coupling both increase and  
decrease, coupling only decrease, and not coupling anything. The  
first two algorithms are both fair at the bottleneck (they increase  
and decrease like a single flow); the last one is not fair, and is  
just given as reference.

In all runs there are two paths, one that drops 1 packet in 1000, and  
one that drops 1 packet in 500 (the drops are periodic to get  
prettier graphs; we get the same qualitative output for random drops).

To get rate-level resource pooling, the CC algorithm must push all  
its traffic on the path with fewer drops. If everybody does this, the  
net effect is that large parts of the network will have the same drop  
probability!
As the graphs show, the coupled algorithm comes closest to this goal,  
though it's not perfect: it still probes the lossier path, albeit at  
a slow rate.

The version with coupled decreases only is much more aggressive on  
the increase for the bad path than the coupled version, that is why  
it gets more window on that in the end. Thus it is worse at resource  
pooling.

Finally, the uncoupled version is even worse.

---

From: Costin Raiciu <[email-masked]>
Date: Fri, 15 May 2009 13:58:06 +0100

Hi,

My remark comes from Damon Wischik's  paper called "Buffer sizing  
theory for bursty TCP flows" where he shows that bursty TCP traffic  
is less prone to synchronization for different buffer sizes.

Cheers,
Costin