Ingemar/Keith,

This is an interesting thread and I am glad that RMCAT has exposure to the Sprout work.

From my reading of the Sprout work, I think there is much to be gained by estimating the statistical properties of past attainable bandwidths (as Sprout does) and the statistical properties of the recent past of the Packet Delay Variation (PDV) distributions (as I hope RMCAT does).

From my reading of SPROUT, they continuously update the bandwidth histogram (the 256 discrete values of lambda), but do not attempt to model the variance (of the assumed Poisson distribution). Of course, the 95% confidence point is dependent on the value of the variance!

[Aside, thanks to the Sprout team for NOT assuming a Normal distribution … yeah the math is easier … but a lot of networking stuff has one-sided distributions and often one-sided distributions with heavy tails.]

That being said, the Sprout work (again as I understand it) has much different assumptions than RMCAT does. They assume that their packets are “rarely subject to standing queues accumulated by other users packets”. This leads them to spurt packets onto the wire (at the source) and effectively only include in their estimates (inter-arrival data) measurements from those “burst packets”.

We, in RMCAT, are assuming that the traffic in our delay-inducing queues can be (and usually are) mixed with packet from other streams. And we also assume that our sources do not burst – but rather pace according to the current bandwidth estimate. Perhaps we could allow an occasional back-to-back packet to attain an occasional bandwidth estimate, but I digress.

That being said (and repeating the above), there is much to learn from the Sprout work. More comments below (see MAR:).

Michael Ramalho

From: rmcat-bounces@ietf.org [mailto:rmcat-bounces@ietf.org] On Behalf Of Ingemar Johansson S
Sent: Wednesday, July 10, 2013 2:39 AM
To: Keith Winstein
Cc: rmcat@ietf.org; fuji246@gmail.com; Mirja Kuehlewind; Dan Weber
Subject: Re: [rmcat] Sprout (Was RE: rmcat Digest, Vol 10, Issue 6)

Hi

and thanks for the reply, comments inline marked with [IJ]

Regards
Ingemar

From: winstein@gmail.com [mailto:winstein@gmail.com] On Behalf Of Keith Winstein
Sent: den 10 juli 2013 07:14
To: Ingemar Johansson S
Cc: rmcat@ietf.org; fuji246@gmail.com; Mirja Kuehlewind; Dan Weber
Subject: Re: Sprout (Was RE: [rmcat] rmcat Digest, Vol 10, Issue 6)

Hello Ingemar,

1) I'm not sure about the packet conservation principle. We do have a loose version of it, based on time instead of counting bytes. Instead of saying that the sender is only allowed to introduce a packet to the network when a packet is delivered (the traditional version), in Sprout the sender is only allowed to introduce new packets to the network when it thinks those packets have a 95% probability of getting dequeued within 100 milliseconds. And the forecast about the rate packets are being dequeued comes from the receiver who is inferring it based on the network's current behavior, and some model for its future evolution.
[IJ] OK, understand, sort of like a softer conservation

MAR: In general, I like Sprout’s approach of being proactive and not trying to cause congestion in order to measure it. Rather, it uses the approach of purposely NOT attempting to cause congestion by working “to the edge” of where it believes congestion may lie (with 95%/5% probability). Unfortunately, when you take away the assumptions that only your flow causes your own congestion – you can’t really predict when congestion may occur because of the other sessions packets in the congested queue. You simply can’t know until you see the artifact of the other packets (being increased delay).

MAR: I disagree with Ingemar’s blanket statement that “pure delay based algorithms which do not follow the packet conservation principle”. Who says? Perhaps the implementations that you consider are only based on rate estimates, but there are other algorithms that use window-based (or byte-based as Sprout does) gating of packets/bytes based on delay measurements. I think RMCAT has to be open to solutions that have (as the control) parameters other than (or in addition to) rate.

2) That's a good question. Right now Sprout piggybacks its feedback in the header of whatever packets are going the other way (if any) and wants to send feedback every 20 milliseconds. I don't know if that's feasible with RTCP. Of course (like TCP) it is better if the conversation is bidirectional because then the feedback can just piggyback and go along for the ride instead of causing entirely whole packets to be sent just for feedback.
[IJ] I recall that there has been discussions around the use of RTP header extensions, another option is an extra layer between the UDP and RTP headers. This and the implications are probably something that needs to be addresses by he WG

MAR: Colin, at the last IETF, showed the bounds of what is possible with RTCP. If RMCAT needs more frequent feedback, we will need another mechanism for it. At the microphone, I confirmed that potential use of RTP header extensions for this purpose is on the table.

3) You're right of course that we make modeling assumptions about the network, but my sense is that the issues you point out are not a confounder.
[IJ] OK, may may be right, I have the burden to prove that system simulations are necessary, can’t promise any data in the near future however.
I have not tried it out myself but I recall that NS-3 has some kine of LTE simulation capability (LENA ?) than can behaps be used.

We've done some characterization measurements by taking 6 or 12 cell phones on Verizon or AT&T's LTE networks, and what we infer is that the schedulers seem to give equal resource block allocations (essentially equal time) to each user element that has pending data on the same eNodeB. This ends up being proportionately fair throughput because different UEs have different channel quality and can send or receive more or fewer bits in a timeslice/RB. Our trace represents the maximum number of bits that can get through if the link *always* has pending data in each direction, i.e. using all of the user's timeslices to the fullest.

We measured the maximum number of packets that can get through if the senders keep the link busy; in our evaluation we then let the programs (Skype, etc.) send whatever packets they feel like sending. The emulated "network" enqueues those packets, and dequeues them in FIFO order at the same times that the trace did. If the trace records an event where a packet got through but the network queue is empty, that opportunity is wasted.

Our assumption is that there's nothing better that an application can do than claim all the LTE resource blocks available to it, and then claim all the space inside those resource blocks (whatever their bitrate), without sending excess packets that will just be queued up. I doubt that there is any benefit to forfeiting some of the available resource blocks just because it will allow other customers to get more resource blocks -- I don't think you will get more throughput, or more stable throughput, or less delay, or more fairness among different cellular customers by doing this.

If every UE ran Sprout and claimed their equal share of the eNodeB's RBs, the throughput would be proportionately fair (proportionate to each UE's channel quality) and almost all the RBs would be full. At least in our model, that's basically the end of the story and the best outcome. But I think we are eager to hear how these assumptions break down and would value input from those who understand how the LTE scheduler "really" works. It may be that there are more complex interactions between different UEs that we are not accounting for.

Best regards,
Keith

On Tue, Jul 9, 2013 at 7:26 AM, Ingemar Johansson S <ingemar.s.johansson@ericsson.com<mailto:ingemar.s.johansson@ericsson.com>> wrote:
Hi Keith

Believe that Sprout has some interesting properties. Comments / questions.


1)      Have you thought about the relation to the packet conservation principle?. If I understand the description of the algorithm it at least loosely follows the packet conservation principle as the receiver can only ask for new bytes when it has received a sufficient number of bytes. This differs from pure delay based algorithms which do not follow the packet conservation principle. I would argue that the possible gains with Sprout is a combo of the stochastic approach and the packet conservation principle. Do you agree or is it too far-fetched ?


2)      Implementability with RTCP: As I understand things Sprout, requires quite a high feedback rate, in the same order as TCP does, this may make it difficult to implement Sprout using RTCP due to the large packet overhead, do you envision a more lightweight (inband?) feedback format?



3)      Simulation methodology. I understand that you use trace files from large file downloads in LTE networks in your studies, what I believe is missing then is the dynamic interaction between various kinds of traffic. Not saying that it is completely wrong, just that LTE has some built in features such as for instance proportional fair schedulers that gives some dynamic effects based on the characteristics of the traffic that one push into the network. These dynamic effects are missing with a trace file based approach.

Again , an interesting contribution and it seems to me that it is in the right direction.
/Ingemar


From: Keith Winstein [mailto:keithw@mit.edu<mailto:keithw@mit.edu>]
Sent: den 9 juli 2013 07:24
To: Dan Weber
Cc: rmcat@ietf.org<mailto:rmcat@ietf.org>; fuji246@gmail.com<mailto:fuji246@gmail.com>; Mirja Kuehlewind
Subject: Re: [rmcat] rmcat Digest, Vol 10, Issue 6

Hi Dan,

On Tue, Jul 9, 2013 at 12:35 AM, Dan Weber <dan@marketsoup.com<mailto:dan@marketsoup.com>> wrote:
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?

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.

2) What changes would be required to Sprout to support targeting flow rate 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


On Mon, Jul 8, 2013 at 12:55 AM, Keith Winstein <keithw@mit.edu<mailto:keithw@mit.edu>> wrote:
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.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

On Tue, Jul 2, 2013 at 11:29 AM, Mirja Kuehlewind <mirja.kuehlewind@ikr.uni-stuttgart.de<mailto:mirja.kuehlewind@ikr.uni-stuttgart.de>> wrote:
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,  <rmcat-request@ietf.org<mailto:rmcat-request@ietf.org>> wrote:
> > ---------- Forwarded message ----------
> > From: Fu Jiantao <fuji246@gmail.com<mailto:fuji246@gmail.com>>
> > To: rmcat WG <rmcat@ietf.org<mailto:rmcat@ietf.org>>
> > 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-inflicted 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
> > traffic (Skype and TCP Cubic), and found that Sprout was able to
> > isolate client application flows 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<tel:%2B49%280%29711%2F685-67973>
email: mirja.kuehlewind@ikr.uni-stuttgart.de<mailto:mirja.kuehlewind@ikr.uni-stuttgart.de>
web: www.ikr.uni-stuttgart.de<http://www.ikr.uni-stuttgart.de>
-------------------------------------------------------------------