Multipath QUIC

[Oliver Mattos]

Is there a multipath QUIC in the works?

With increasingly mobile users changing endpoints increasingly frequently, it seems hard to encourage the use of a protocol that doesn't allow a user to use multiple endpoints simultaneously and/or transition between them as networks appear and go away...

[Alyssa (Rzeszutek) Wilk]

QUIC is designed to transition seemlessly as clients migrate across networks; that's one of the benefits for using the CID as the connection identifier rather than IP:port pairs. 

cheers,

Alyssa

On Wed, Aug 6, 2014 at 11:27 AM, Oliver Mattos <oma...@gmail.com> wrote:

Is there a multipath QUIC in the works?

With increasingly mobile users changing endpoints increasingly frequently, it seems hard to encourage the use of a protocol that doesn't allow a user to use multiple endpoints simultaneously and/or transition between them as networks appear and go away...

--
You received this message because you are subscribed to the Google Groups "QUIC Prototype Protocol Discussion group" group.
To unsubscribe from this group and stop receiving emails from it, send an email to proto-quic+...@chromium.org.
To post to this group, send email to proto...@chromium.org.
For more options, visit https://groups.google.com/a/chromium.org/d/optout.

[Sargun Dhillon]

So, I also had this question, but rather than address mobility, which I've seen as part of the QUIC standard, does QUIC have active multipathing a la MP-TCP (RFC 6824). Today, I only see specification to handle changing the IP address of the client. I haven't seen any portion of the specification that talks about active-active connections between multiple paths, and either load balancing at the stream-level, or the frame-level. 

I think that is QUIC is to become a protocol that used on the internet, this would be super valuable for the following reasons.:

1) Simultaneous transmission of packets over multiple media: Data duplication has been pointed out in a number of academic papers as a method to "calm" or flatten latency. When a user has multiple, unpredictable links, duplicating small, important bits of traffic, like chat messages would be very valuable. The specific example is if I'm using QUIC between an origin node, and a CDN node - the CDN will have multiple paths back to the origin. I can then duplicate the traffic over multiple paths in order to ensure more predictable, and reliable delivery of the data. Although this is a bit different than the MP-TCP mechanism, it's still very valuable for some users.

2) Multiple paths: The internet uses some combination of BGP distance-vector, Valiant load balancing (ECMP), and proprietary TE for load balancing traffic over backbones. The most visible method of these is ECMP, which decides which intermediate path to take depending on the hash of the 5-tuple (protocol, src ip, src port, dst ip, dst port) of a specific packet (flow). In a casual survey of flows, a popular CDN has measures great deltas while only changing the dst port of their flows, and their conclusion is that ECMP, and fabric-oblivious load balancing is resulting in some number of the flows taking a bad path. The CDN has noticed that these particular paths incur higher latency (congestion), and other paths incur higher corruption penalties. By utilizing, and probing multiple 5-tuples, it enables QUIC to circumvent these paths. 

3) MTR / QoS: Today, QUIC already supports multiple streams within one connection / association. Occasionally these streams have vastly different characteristics. For example, one stream could contain a large image, whereas another stream could contain a few kb of Javascript. QUIC already avoids HOL by treating these as two separate entities, but the network itself with route them over the same path. In real life networks, and things like CDNs, low-latency paths can be more expensive (per the gbps), and can become quickly congested requiring traffic to fall over to high latency paths. Surfacing these as different 5-tuples would be valuable. 

4) Better traffic matrix: By breaking up connections into individual frames, or streams, and load balancing them across the network in more fine-grained portions, it's easier to build a perfect traffic matrix for the network. For networks that use adaptive load balancing, having smaller, fine-grained units to move around the network makes scheduling easier, as opposed to having to move around entire QUIC connections, as elephants. 

Has there been any thought put into this?

[Ian Swett]

There has been a fair amount of internal discussion around multipath, and I agree it would be extremely valuable for all the reasons you mention above.  QUIC, with it's connection id and encrypted transport data(ie: acks, etc) is well positioned to implement multipath and avoid some of the middlebox issues MP-TCP does.

A lot of the work involved in implementing connection migration would help multipath, so once that's complete, I think we'll have a clearer plan in regards to multipath.

[Dave Taht]

On Wed, Jan 7, 2015 at 9:18 AM, 'Ian Swett' via QUIC Prototype
Protocol Discussion group <proto...@chromium.org> wrote:
> There has been a fair amount of internal discussion around multipath, and I
> agree it would be extremely valuable for all the reasons you mention above.
> QUIC, with it's connection id and encrypted transport data(ie: acks, etc) is
> well positioned to implement multipath and avoid some of the middlebox
> issues MP-TCP does.
>
> A lot of the work involved in implementing connection migration would help
> multipath, so once that's complete, I think we'll have a clearer plan in
> regards to multipath.

There was a great deal of discussion of the new mosh-multipath work here:

http://comments.gmane.org/gmane.network.mosh.devel/756

and continuing here, in trying to come up with an api better than
getaddrinfo in particular.

http://www.ietf.org/mail-archive/web/homenet/current/msg04495.html

One of the implications of doing fq_codel on bottleneck links everywhere is that
short, interactive traffic wins big over longer duration traffic.

However there is the possibility of a hash collision causing
performance to go to hell -
when a big flow shares a (otherwise fair) queue with a tiny,
interactive, one. mosh-multipath,
by seeking the lowest RTT IP 5 tuple across multiple connections,
always, finds a queue for itself no matter the load on the rest of the
network. This "IP agility" in mosh-multipath eliminates one of the
last big objections to FQ everywhere, and it would be of benefit to
quic, also, to always find it's own queue in a FQ'd system.

I have been extending the IP agility idea to work with several VPN
technologies, also, to make encapsulated traffic behave similarly in a
FQ'd world. (and not serially as vpns do today)

https://plus.google.com/u/0/107942175615993706558/posts/QWPWLoGMtrm

Dave Täht

thttp://www.bufferbloat.net/projects/bloat/wiki/Upcoming_Talks

[Jim Roskind]

Very cool idea "to probe for better path" via IP agility (it sounds like port agility would also work?). Although that prevents a (mosh) ant flow from being hashed with an elephant flow, does it also open the door to methods for subverting FQ efforts?  

Historically, the internet has created multiple host names to subvert the "agreed limit" on the number of flows to a single host.  That host-sharding also subverted the concept of the initial congestion window limitation, as well as the backoff multiplier in the face of lost packets.

Is it a good or bad thing that FQ can be manipulated in this manner by the endpoints?  ...or is it assumed that "most (TCP) flows" won't bother (be able?) to similarly game the system?

[Oliver Mattos]

Designing a system which has arbitrary bad paths, but that can then probe to get better paths seems suboptimal...   That probe process is going to take a long time, and how do you know if you have a "good" or "bad" or "quite good" path? It becomes the multi-armed bandit problem!  

Just make sure we don't get bad paths in the first place by using N hashing algorithms in the FQ design, and take the min response, a bit like a counting bloom filter   If you have 2^20 hash buckets, you just reduced your chance of full collision to about 2^(20*N), as long as the count of elephant flows << 2^20. 

[Dave Taht]

On Wed, Jan 7, 2015 at 9:58 AM, Jim Roskind <j...@chromium.org> wrote:
> Very cool idea "to probe for better path" via IP agility (it sounds like
> port agility would also work?).

Port agility works also. As does protocol agility. I recently showed that
udplite actually works across many paths, and through cerowrt, on ipv6,
for example. The patches to netperf are here: https://github.com/dtaht/netperf
and also (sadly) showed udplite doesn't get through my firewall config on ipv4.

(I am coining the usage of "agility" here, I think. If there is a better word
for "nailing up multiple connections and choosing the "best" one, let me
know)

> Although that prevents a (mosh) ant flow
> from being hashed with an elephant flow, does it also open the door to
> methods for subverting FQ efforts?

Well, this conflates several things that need to be conceptually separated.

And I need to think about how to unconflate them before writing more on it.

>
> Historically, the internet has created multiple host names to subvert the
> "agreed limit" on the number of flows to a single host. That host-sharding
> also subverted the concept of the initial congestion window limitation, as
> well as the backoff multiplier in the face of lost packets.
>
> Is it a good or bad thing that FQ can be manipulated in this manner by the
> endpoints? ...or is it assumed that "most (TCP) flows" won't bother (be
> able?) to similarly game the system?

The answer is yes and no. :/ FQ (specifically fq_codel) is just such a huge win
in general that I am willing to live with it :) - it can, at least
theoretically (and
certainly in the case of mosh-multipath), apply more signal above the "noise"
on multiple flows when the end-points are aware they have multiple flows.

bittorrent works just great, today, when competing with web traffic,
on a fq_codel'ed network. The existing web sharding mechanisms work
well when competing against torrent... and mosh-multipath is
absolutely spectacular at competing with all of that. What's left...
webrtc videoconferencing tends to work well but I think the approach
mosh is taking to getting a good connection would be cool for
videoconferencing.

Big long-term flows tend to degrade to competing equally with torrent,
( http://perso.telecom-paristech.fr/~drossi/paper/rossi14comnet-b.pdf
)

but what I see presently is short flows in slow start still knocking
torrent aside for dash/web traffic.

But having a long term conceptual framework for imagining a fq_codeled
world, and a detailed threat analysis,
no have.

And pure FQ is quite different from fq_codel. FQ provides flow
isolation. Codel keeps the overall size of all the queues short (so as
to optimize for filling the pipe, not the buffers).

[Dave Taht]

On Thu, Jan 8, 2015 at 10:39 AM, Oliver Mattos <oma...@gmail.com> wrote:
> Designing a system which has arbitrary bad paths, but that can then probe to
> get better paths seems suboptimal... That probe process is going to take a
> long time,

In the case of mosh it doesn't matter how long it takes. The protocol is very
lightweight and is basically sending a diff from the last known state of the
terminal. If all but one of 99 probes fail, you still won.

In the case of a quic, you have the inevitable keep-alive process you need
to maintain, anyway, after connection establishment.

> and how do you know if you have a "good" or "bad" or "quite good"
> path? It becomes the multi-armed bandit problem!

mosh-multipath measures RTT as it's primary metric.

try it.

Mosh was one of those tools that I went around installing *everywhere*, much
like I did mosaic back in the day. I have nearly completely abandoned ssh for
interactive (terminal) traffic as a result. mosh-multipath is making
an occasionally
annoying problem (fq hash collision) vanish completely.

In the case of a quic with multiple connections I would imagine periodic
measurements of idle RTT, and preserving a mapping between
(observed capacity, connection).

>
> Just make sure we don't get bad paths in the first place by using N hashing
> algorithms in the FQ design, and take the min response, a bit like a
> counting bloom filter

You are possibly conflating two things. In this case the "fq" stuff is on a
bottleneck link somewhere else on the network. There is no way for
the application to infer the number of queues, the kind of stochastic
hash (2 tuple?
5 tuple?), the actual value of the hash (randomly permuted), etc.

An application can, however, observe differences in RTT when nailed up
via different ips and port ranges. The mosh-multipath technique was
originally intended for dealing with source specific routing, where a
given set of source IPs might end up going out vastly different
(ethernet, wifi, LTE) paths, with intermittent connectivity on all of
them.

> If you have 2^20 hash buckets, you just reduced your

Although the fq_codel algorithm, as implemented, supports 2^16 hash buckets, the
default is 2^10. This is partially due to the keeping codel state on a
per queue basis on links in the range 0-1gigbit and monty carlo
testing ( see https://tools.ietf.org/html/draft-hoeiland-joergensen-aqm-fq-codel-01
),
and partially due to trying to keep memory overhead low. The "right"
number has not been derived for faster links or for "all" traffic
loads, 2^10 was merely a good-seeming number given traffic conditions
today.

The full blown sch_fq algorithm (widely deployed now in linux based
datacenters) uses a red-black tree to do completely fair queueing with
no stochastic hash, scaling to millions of flows.

SFQ, as deployed, uses 127 queues, and many deployments permute the
hash every 10 seconds (scrambling long duration flows and acting as a
poor man's aqm)

Other combinations of FQ + aqm technologies do the FQ first, across N
flows, then apply a single aqm algorithm to the resulting flow.

> chance of full collision to about 2^(20*N), as long as the count of elephant
> flows << 2^20.

Well, there is the birthday problem, and the fact that few hosts have
more than a few IP addresses to source or dest to.

[Sargun Dhillon]

People already are doing path selection in CDNs. There's even
literature about the multi-armed bandit in the context of CDNs
(http://www.cs.nyu.edu/~mohri/pub/bandit.pdf). Using external
information (from BGP) to influence path selection. ALTO
http://datatracker.ietf.org/wg/alto/charter/ provides inter-AS methods
for path inspection, which could drastically reduce the amount of time
for path selection, and stabilization. Unfortunately, today, the
internet is largely a black box to end hosts.

In a study of coupled MP-TCP connections, "On the Benefits of Applying
Experimental Design to Improve Multipath TCP" it proves that the
endpoints don't necessarily need physically diverse queues (network
connections). There are cases where intermediate paths have congestion
(due to elephants), and this can be circumvented via congestion
techniques like OLIA (MPTCP is not Pareto-Optimal: Performance Issues
and a
Possible Solution). This is somewhat dependent on long-lived
connections, to circumvent the slow start of every path. In OLIA,
shows that empirically, even with competing paths (queues), fairness
is achieved with little overhead.

From the datacenter perspective, this is also discussed in "Data
Center Networking with Multipath TCP" and how utilizing multiple
subflows in a datacenter network can be beneficial. Datacenters today
use valiant load balancing, but they balance at the TCP flow level,
which results in the elephants vs. mice problem. Even with full
bisection bandwidth, achieving perfect utilization of the fabric isn't
possible. The methods applied in MP-TCP are still valuable here.

P.S.
Another benefit of first-class multipathing is anycast path selection.
TCP anycast has become a provable method of load balancing across
internet sites (https://www.nanog.org/meetings/nanog37/presentations/matt.levine.pdf),
due to the relative stability of BGP prefixes. Unfortunately,
datacenters do not provide the same stability. Given that most modern
datacenter clos topologies utilize ECMP for load balancing flows, and
ECMP implementations typically leverage modulo-hashing, anycast alone
is not good enough for datacenter load balancing (See: Ananta: Cloud
Scale Load Balancing, SIGCOMM'13). It typically requires some
intermediary layer to provide consistent hashing for traffic ingress
to a VIP. This is needed to work around host instability. An
alternative, as scene in SCTP-anycast, and MP-TCP implementations is
to make the initial connection via a TCP anycast address, and then
move the connection to a unicast address. IP agility in QUIC supports
this.

[Dave Taht]

Yes.

(and thank you for the valuable links)

> P.S.
> Another benefit of first-class multipathing is anycast path selection.
> TCP anycast has become a provable method of load balancing across
> internet sites (https://www.nanog.org/meetings/nanog37/presentations/matt.levine.pdf),
> due to the relative stability of BGP prefixes.

I am actually using anycast successfully in a locally routed network
(babel based) for dns
queries.

I would argue in the case of IPv6 however, that the services presented
on an anycast address be held to the subset of those that work well -
dns in particular is good, a web server that does short transactions
only, also, long duration transfers, not so much. We have whole /64s
to use up, might as well use them for something.

>Unfortunately,
> datacenters do not provide the same stability. Given that most modern
> datacenter clos topologies utilize ECMP for load balancing flows, and
> ECMP implementations typically leverage modulo-hashing, anycast alone
> is not good enough for datacenter load balancing (See: Ananta: Cloud
> Scale Load Balancing, SIGCOMM'13).

More recently there was CONGA, which I find disturbing on several levels.

http://simula.stanford.edu/~alizade/papers/conga-sigcomm14.pdf

> It typically requires some
> intermediary layer to provide consistent hashing for traffic ingress
> to a VIP. This is needed to work around host instability. An
> alternative, as scene in SCTP-anycast, and MP-TCP implementations is
> to make the initial connection via a TCP anycast address, and then
> move the connection to a unicast address.

> IP agility in QUIC supports this.

Are you making the assertion that Quic *could* support this or *does*
support this?

(and am I using the phrase "IP agility" in a suitably distinct manner?
"Mobility" is heavily overloaded.... )

[sunil kumar kumar]

  Hi. Is any group working on  Multipath - QUIC ?  May I know the latest update on this topic..

  Thanks,

  Sunil