Subject: Re: [rmcat] rmcat Digest, Vol 10, Issue 6

From: Mirja Kuehlewind <[email-masked]>
Date: Tue, 2 Jul 2013 17:29:20 +0200

Hi Kevin,

thanks a lot. I believe for now the mobile scenarios is not the first thing we 
want to look at. Maybe that useful at a later stage.

Just to double check: Your algorithm is basically a delay-based approach (from 
a very high level point of view based on the same idea than Vegas - comparing 
the actual rate to an expected rate)? And you evaluated your algorithm in a 
moblie scenario, where every user/flow has an own queue, thus no (loss-based) 
cross traffic in the same queue, right? Btw. did you every compare you 
approach with e.g. Vegas?

Mirja

On Saturday 08 June 2013 21:42:15 Keith Winstein wrote:
> Hello,
>
> I am on this list and we're happy to discuss Sprout with anybody. An
> early version of this work was presented at the IAB real-time
> congestion control summit back in Vancouver so it may sound familiar.
>
> One thing RMCAT might be interested in is the evaluation strategy. We
> collected a bunch of network traces that we got from saturating
> various cellular links in both directions simultaneously. (To do this
> well, we think it requires TWO cell phones connected to a single
> laptop -- one phone is the "device under test," and gets its uplink
> and downlink saturated so there is >750 ms of standing queue in each
> direction. The second phone is left uncongested and is used to control
> the feedback loop so we don't accumulate TOO much standing queue in
> either direction so that the network will shut us down.)
>
> Then we take those traces back into the lab (or a virtual machine) and
> set up a device with two network interfaces, that accepts packets and
> puts them at the tail of a queue to leave the other network interface.
> Packets are dequeued and sent whenever they were in the
> earlier-recorded trace. (Plus some minRTT in each direction, 20 ms in
> our case.)
>
> We think this is a good way to *repeatably* test how rate-control
> algorithms perform over an "almost-infinite-buffer" cellular-type link
> with variable link speed. Otherwise it's very hard to get reproducible
> conditions!
>
> We're happy to share our traces, code, etc. with the RMCAT community
> if anybody is interested. Actually we put this whole testing setup in
> an EC2 virtual machine and made it a homework assignment last semester
> in a networking class, asking students to make a better
> congestion-control scheme and then run them over this emulated
> cellular network: http://6829.keithw.org/ps2/
>
> ==
>
> Re: Sprout itself, I think there's probably a few major ideas that
> explain why it gets the performance it does on these links:
>
> (1) Sprout has an explicit goal -- maximize throughput while bounding
> delay at < 100 ms with 95% probability.
>
> (2) The algorithm is designed from the start for two behaviors of the
> network path that are common on cellular links but weren't common 20
> years ago -- namely, the network never drops a packet, and the link
> speed varies quickly. Essentially Sprout assumes bufferbloat.
>
> (3) And, of course, Sprout benefits from some simplifying assumptions
> -- in particular that it is the only flow on the link! If you want to
> run multiple competing flows, we have results on running them *inside*
> Sprout, but not alongside. We have some forthcoming work that deals
> with fairness in a more rigorous fashion, and my colleagues are
> working on some extensions to Sprout to deal with multiple flows at
> once. But this paper hasn't yet grappled with those issues.
>
> Grateful for your interest!
>
> Cheers,
> Keith
>
> On Sat, Jun 8, 2013 at 9:02 PM,  <[email-masked]> wrote:
> > ---------- Forwarded message ----------
> > From: Fu Jiantao <[email-masked]>
> > To: rmcat WG <[email-masked]>
> > Cc:
> > Date: Sat, 8 Jun 2013 17:29:16 +0800
> > Subject: [rmcat] Does any one give sprout a try
> > Sprout seems very impressive according to the test report.
> >
> > http://alfalfa.mit.edu/#paper
> >
> > More details below
> > -----------------------------------
> >
> > Sprout is an end-to-end transport protocol for interactive
> > applications that desire high throughput and low delay. Sprout works
> > well over cellular wireless networks, where link speeds change
> > dramatically with time, and current protocols build up multi-second
> > queues in network gateways. Sprout does not use TCP-style reactive
> > congestion control; instead the receiver observes the packet arrival
> > times to infer the uncertain dynamics of the network path. This
> > inference is used to forecast how many bytes may be sent by the
> > sender, while bounding the risk that packets will be delayed inside
> > the network for too long.
> >
> > In evaluations on traces from four commercial LTE and 3G networks,
> > Sprout, compared with Skype, reduced self-inﬂicted end-to-end delay by
> > a factor of 7.9 and achieved 2.2 the transmitted bit rate on average.
> > Compared with Google’s Hangout, Sprout reduced delay by a factor of
> > 7.2 while achieving 4.4 the bit rate, and compared with Apple’s
> > Facetime, Sprout reduced delay by a factor of 8.7 with 1.9 the bit
> > rate.
> >
> > Although it is end-to-end, Sprout matched or outperformed TCP Cubic
> > running over the CoDel active queue management algorithm, which
> > requires changes to cellular carrier equipment to deploy. We also
> > tested Sprout as a tunnel to carry competing interactive and bulk
> > trafﬁc (Skype and TCP Cubic), and found that Sprout was able to
> > isolate client application ﬂows from one another.

-- 
-------------------------------------------------------------------
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: Keith Winstein <[email-masked]>
Date: Mon, 8 Jul 2013 02:55:46 -0400

Hello Mirja,

Thanks for your interest.

I guess I wouldn't say that Sprout is a delay-based approach. More like a
rate-based or control-based approach that assumes the network will insist
on delivering almost every packet that gets sent, even if that means
delaying all the rest of its packets for a long time (like many networks
today).

The Sprout sender marks each packet with the expected time until the next
packet will be sent. (0 for packets inside a flight.) The receiver uses
this to infer the *rate* of packet arrivals from the network (with
uncertainty, by keeping a full probability distribution). The receiver then
makes a cautious forecast of the future evolution of that rate and
transmits it to the sender along with its ACKs.

The sender keeps an accounting of the number of packets it thinks are still
in the in-network queues (informed by the receiver's ACK) and the rate that
packets are going to be drained in the future (informed by the receiver's
forecast). It uses this to control its own rate of transmissions to be able
to send as many packets as possible, with 95% confidence that no packets
will get queued in the network for more than 100 ms, or whatever is
considered to be acceptable queueing delay.

Unlike Vegas, Sprout doesn't worry about the RTT directly and doesn't try
to measure it. We do try to measure the rate that packets are getting
drained from the network, and the sender tries to add new packets to the
network at a rate that keeps the queueing delay at around 100 milliseconds.

We did compare with Vegas; you can see the results at
http://alfalfa.mit.eduin the talk and paper. On average over our 8
cellular links, Sprout
achieved a 10% speedup over Vegas and a 2.1x reduction in 95th-percentile
queueing delay.

Cheers,
Keith

---

From: John Leslie <[email-masked]>
Date: Mon, 8 Jul 2013 07:32:19 -0400

> network at a rate that keeps the queueing delay at around 100 milliseconds.

   100 milliseconds _is_ rather long...

   (You are talking _queueing delay, right, not transit time?)

--
John Leslie <[email-masked]>

---

From: Dan Weber <[email-masked]>
Date: Mon, 8 Jul 2013 22:35:48 -0600

Hi Keith,

As you probably already know, I've been a fan of Sprout, and there are
others on this list that are too.  Two thoughts come to mind after reading
you summary here:

1) How well does Sprout perform on skinny buffer networks as compared to
those that are fat or bloated?
2) What changes would be required to Sprout to support targeting flow rate
stability rather than maximum throughput?

Your time and feedback are greatly appreciated.

Thanks,
Dan

On Mon, Jul 8, 2013 at 12:55 AM, Keith Winstein <[email-masked]> wrote:

> The sender keeps an accounting of the number of packets it thinks are
> still in the in-network queues (informed by the receiver's ACK) and the
> rate that packets are going to be drained in the future (informed by the
> receiver's forecast). It uses this to control its own rate of transmissions
> to be able to send as many packets as possible, with 95% confidence that no
> packets will get queued in the network for more than 100 ms, or whatever is
> http://alfalfa.mit.edu in the talk and paper. On average over our 8
> cellular links, Sprout achieved a 10% speedup over Vegas and a 2.1x
> reduction in 95th-percentile queueing delay.
>
> Cheers,
> Keith
>

---

From: Keith Winstein <[email-masked]>
Date: Tue, 9 Jul 2013 01:04:32 -0400

>    (You are talking _queueing delay, right, not transit time?)

Yes, queueing delay. I agree that 100 ms is perceptible, but:

(a) when the future link speed is uncertain, there is a tradeoff between
the queueing delay and the throughput of the protocol. The sender can
always achieve the maximum throughput possible if it just keeps the
in-network queues from ever underflowing, i.e. by building up a huge
queueing delay. And it can get lower queuing delay, at the cost of less
throughput.

We talk about this more explicitly in the conference talk (included on
http://alfalfa.mit.edu) and show what we think is the curve of possible
tradeoffs.

A 100 ms target may not be the right answer for a particular application,
but every application has to grapple with this tradeoff between delay and
throughput if it runs over today's cellular networks.

(b) this is still 7-9 *times* shorter queueing delay (at the 95th
percentile) than what is built up by Google Hangout, Skype, and Facetime.

Cheers,
Keith

---

From: Keith Winstein <[email-masked]>
Date: Tue, 9 Jul 2013 01:24:06 -0400

Hi Dan,

> those that are fat or bloated?

I'm not sure, to be honest, without doing the experiment. But I don't
expect Sprout's ideas are that helpful here -- Sprout's main accomplishment
is to compromise between the desire for throughput (on a link whose speed
is varying and uncertain) and low queueing delay, on a typical contemporary
network that holds on to packets for >1000 ms.

I think the game is fundamentally different on a network where queueing
delays can't build up to unacceptable levels. If the network isn't going to
hold on to a packet for longer than 50 ms in a queue, you don't have to
worry about building up an unacceptable in-network queue no matter what you
do.

But really I'm just not sure.

> stability rather than maximum throughput?

Hmm, probably not that much. When the link is doing well, instead of trying
to max it out, we could make Sprout ramp up slowly or cap the sending rate
at some maximum. The one thing we think is misguided is to attempt to get
"stability" in the downward direction. If we were sending at 2000 kbps and
then the link deteriorates to 100 kbps, trying to "slowly vary" the sending
rate is just a recipe for building up a gigantic standing queue of multiple
seconds. Much better to cut immediately to 90 kbps (actually less -- cut to
whatever rate is going to drain the existing queue back to the target of
100 milliseconds) so you can at least get some audio through.

> Your time and feedback are greatly appreciated.

No problem, of course we are flattered by your interest and happy to help
or participate.

Not sure if I mentioned earlier but we do have a whole Amazon VM setup if
you want to play with our evaluation testbed. Directions at
http://6829.keithw.org/ps2/

Best regards,
Keith