[Bloat] pacing, applied differently than bbr

[Bloat] pacing, applied differently than bbr

[Dave Taht]

I don't know how I stumbled across this, but it seemed interesting at
this late hour. I wonder if they kept at it or tried ecn also.

"A Model Predictive Control Approach to Flow Pacing for TCP"

"we propose a different approach to latency based congestion control.
In particular, our controller sets the maximum pacing rate by solving
a model-based receding horizon control problem at each time step. Each
new roundtrip time (RTT) measurement is first incorporated into a
linear time-varying (LTV) predictive model. Subsequently, we solve a
one-step look-ahead optimization problem which finds the pacing rate
which optimally trades off RTT, RTT variance, and throughput according
to the most recent model. Our method is computationally inexpensive
making it readily implementable on current systems."

https://people.eecs.berkeley.edu/~dfk/pdfs/network_control_camera_ready.pdf


-- 
Make Music, Not War

Dave Täht
CTO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-831-435-0729

Re: [Bloat] pacing, applied differently than bbr

[Taran Lynn]

Here's a paper and slides on work that has built on this research
[1][2]. They were presented at the 2019 Buffer Workshop. A paper should
also be posted on arXiv soon that has more details of the actual
algorithm, which has been slightly updated since the workshop. Currently
we're trying to improve the algorithm's performance and fairness. So far
we've seen pretty good reductions in RTT (hopefully you'll see more
papers in the future). We're also learning some things from BBR and the
challenges it faced.

P.S. If you're wondering why the math looks significantly different than
in the original paper, it's because a lot of progress has already been
made :).

[1] http://buffer-workshop.stanford.edu/papers/paper14.pdf
[2] http://buffer-workshop.stanford.edu/slides/mpc.pdf

On 2/8/20 11:11 PM, Dave Taht wrote:
> I don't know how I stumbled across this, but it seemed interesting at
> this late hour. I wonder if they kept at it or tried ecn also.
> 
> "A Model Predictive Control Approach to Flow Pacing for TCP"
> 
> "we propose a different approach to latency based congestion control.
> In particular, our controller sets the maximum pacing rate by solving
> a model-based receding horizon control problem at each time step. Each
> new roundtrip time (RTT) measurement is first incorporated into a
> linear time-varying (LTV) predictive model. Subsequently, we solve a
> one-step look-ahead optimization problem which finds the pacing rate
> which optimally trades off RTT, RTT variance, and throughput according
> to the most recent model. Our method is computationally inexpensive
> making it readily implementable on current systems."
> 
> https://people.eecs.berkeley.edu/~dfk/pdfs/network_control_camera_ready.pdf
> 
> 

Re: [Bloat] pacing, applied differently than bbr

[Taran Lynn]

As promised, here's the updated arXiv paper on applying model predictive
control to TCP CC [1]. It contains more in depth information about the
implementation, as well as some data from physical experiments.

[1] https://arxiv.org/abs/2002.09825

On 2/9/20 8:39 AM, Taran Lynn wrote:
> Here's a paper and slides on work that has built on this research
> [1][2]. They were presented at the 2019 Buffer Workshop. A paper should
> also be posted on arXiv soon that has more details of the actual
> algorithm, which has been slightly updated since the workshop. Currently
> we're trying to improve the algorithm's performance and fairness. So far
> we've seen pretty good reductions in RTT (hopefully you'll see more
> papers in the future). We're also learning some things from BBR and the
> challenges it faced.
> 
> P.S. If you're wondering why the math looks significantly different than
> in the original paper, it's because a lot of progress has already been
> made :).
> 
> [1] http://buffer-workshop.stanford.edu/papers/paper14.pdf
> [2] http://buffer-workshop.stanford.edu/slides/mpc.pdf
> 
> On 2/8/20 11:11 PM, Dave Taht wrote:
>> I don't know how I stumbled across this, but it seemed interesting at
>> this late hour. I wonder if they kept at it or tried ecn also.
>>
>> "A Model Predictive Control Approach to Flow Pacing for TCP"
>>
>> "we propose a different approach to latency based congestion control.
>> In particular, our controller sets the maximum pacing rate by solving
>> a model-based receding horizon control problem at each time step. Each
>> new roundtrip time (RTT) measurement is first incorporated into a
>> linear time-varying (LTV) predictive model. Subsequently, we solve a
>> one-step look-ahead optimization problem which finds the pacing rate
>> which optimally trades off RTT, RTT variance, and throughput according
>> to the most recent model. Our method is computationally inexpensive
>> making it readily implementable on current systems."
>>
>> https://people.eecs.berkeley.edu/~dfk/pdfs/network_control_camera_ready.pdf
>>
>>

Re: [Bloat] pacing, applied differently than bbr

[Dave Taht]

A couple thoughts:

"the scheme perform poorly in networks that experience high levels of
random losses.. Such networks include most all networks with WiFi
access points, which make up an increasing number of access points."

While not exactly a myth, most wifi networks today actually do an
extreme level of hardware retry to obscure losses, some retrying 30 or
more times before giving up (on unicast). So you are more likely to
see extremes of RTT variance than actual loss on such networks (until
the introduction of intentional loss or marking from the fq_codel for
wifi stuff). Loss and RTT variance could perhaps be better correlated,
and I've sometimes had hope people would take that RTT variance into
account when dealing with loss (and especially ecn!) response to
"rate" reduction. There really is no such thing as a "rate" when
dealing with wifi, it's just data over an interval, where that
interval varies more than how most humans think of the thing, and
there's lots of different intervals, including fairly large ones where
the rate can be *0*. I try to give some intuition in the latter half
of my old mit talk here:

https://www.youtube.com/watch?v=Wksh2DPHCD

As to how mmwave radios will actually behave in the field, not a clue.

"One notable advantage of FQ over FQ Codel is that provides flow
pacing to applications and higher-level congestion control algorithms.
This is why FQ is suggested to be used with BBR and not FQ Codel." -
this is not quite true. The FQ qdisc is *more efficient* at managing
the pacing itself, but since linux 4.something, the tcp stack will
fall back to keep the timers and pacing within itself for any qdisc.
I'm always at pains to praise the sch_fq qdisc - really, it's awesome
stuff for a tcp-serving-heavy workload on bare metal, but for any
other workload...

And pacing helps cubic and reno a lot as well.

As for the actual content of the paper... umm.. code is where? One of
the things opening up to the bpf and related approaches is perhaps
better means for couple congestion control (e.g. multiple ledbat-like
flows), and I like very much maybe having a knob for other sorts of
flows....

On Tue, Feb 25, 2020 at 10:52 PM Taran Lynn <taranlynn0@gmail.com> wrote:
>
> As promised, here's the updated arXiv paper on applying model predictive
> control to TCP CC [1]. It contains more in depth information about the
> implementation, as well as some data from physical experiments.
>
> [1] https://arxiv.org/abs/2002.09825
>
> On 2/9/20 8:39 AM, Taran Lynn wrote:
> > Here's a paper and slides on work that has built on this research
> > [1][2]. They were presented at the 2019 Buffer Workshop. A paper should
> > also be posted on arXiv soon that has more details of the actual
> > algorithm, which has been slightly updated since the workshop. Currently
> > we're trying to improve the algorithm's performance and fairness. So far
> > we've seen pretty good reductions in RTT (hopefully you'll see more
> > papers in the future). We're also learning some things from BBR and the
> > challenges it faced.
> >
> > P.S. If you're wondering why the math looks significantly different than
> > in the original paper, it's because a lot of progress has already been
> > made :).
> >
> > [1] http://buffer-workshop.stanford.edu/papers/paper14.pdf
> > [2] http://buffer-workshop.stanford.edu/slides/mpc.pdf
> >
> > On 2/8/20 11:11 PM, Dave Taht wrote:
> >> I don't know how I stumbled across this, but it seemed interesting at
> >> this late hour. I wonder if they kept at it or tried ecn also.
> >>
> >> "A Model Predictive Control Approach to Flow Pacing for TCP"
> >>
> >> "we propose a different approach to latency based congestion control.
> >> In particular, our controller sets the maximum pacing rate by solving
> >> a model-based receding horizon control problem at each time step. Each
> >> new roundtrip time (RTT) measurement is first incorporated into a
> >> linear time-varying (LTV) predictive model. Subsequently, we solve a
> >> one-step look-ahead optimization problem which finds the pacing rate
> >> which optimally trades off RTT, RTT variance, and throughput according
> >> to the most recent model. Our method is computationally inexpensive
> >> making it readily implementable on current systems."
> >>
> >> https://people.eecs.berkeley.edu/~dfk/pdfs/network_control_camera_ready.pdf
> >>
> >>
> _______________________________________________
> Bloat mailing list
> Bloat@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/bloat



-- 
Make Music, Not War

Dave Täht
CTO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-831-435-0729

Re: [Bloat] pacing, applied differently than bbr

[Taran Lynn]

On 2/26/20 12:12 PM, Dave Taht wrote:
> As for the actual content of the paper... umm.. code is where?
The code can be found on out site here
https://lambda-11235.github.io/control_theo_network/projects/. Note hat
the code there is the implementation used in the paper. We have since
made significant changes, but will wait to publish the code until we
publish our results.


On 2/26/20 1:00 PM, Jonathan Morton wrote:
> Hmmm.  I see some qualitative similarities to BBR behaviour, but the
> algorithm doesn't seem to be very robust since it seems to improve a
> lot when given approximate a-priori information via cap and collar
> settings.

Current work is focused on improving robustness in this area, and some
of our recent work has already seen some improvements.


On 2/26/20 1:00 PM, Jonathan Morton wrote:
> How does it treat ECN information, or does it set itself Not-ECT?

The algorithm currently only uses delay based feedback. It does not use
loss or ECN information.

Re: [Bloat] pacing, applied differently than bbr

[Jonathan Morton]

> On 26 Feb, 2020, at 8:51 am, Taran Lynn <taranlynn0@gmail.com> wrote:
> 
> As promised, here's the updated arXiv paper on applying model predictive
> control to TCP CC [1]. It contains more in depth information about the
> implementation, as well as some data from physical experiments.
> 
> [1] https://arxiv.org/abs/2002.09825

Hmmm.  I see some qualitative similarities to BBR behaviour, but the algorithm doesn't seem to be very robust since it seems to improve a lot when given approximate a-priori information via cap and collar settings.

How does it treat ECN information, or does it set itself Not-ECT?

 - Jonathan Morton

Re: [Bloat] pacing, applied differently than bbr

[David Fridovich-Keil]

Hi Dave,

To be honest I haven’t personally been involved in follow up work but I think my coauthors may have. Maybe try contacting Nate at nate.hanford@gmail.com?

Best,
David

Sent from my iPhone

> On Feb 9, 2020, at 2:12 AM, Dave Taht <dave.taht@gmail.com> wrote:
> 
> I don't know how I stumbled across this, but it seemed interesting at
> this late hour. I wonder if they kept at it or tried ecn also.
> 
> "A Model Predictive Control Approach to Flow Pacing for TCP"
> 
> "we propose a different approach to latency based congestion control.
> In particular, our controller sets the maximum pacing rate by solving
> a model-based receding horizon control problem at each time step. Each
> new roundtrip time (RTT) measurement is first incorporated into a
> linear time-varying (LTV) predictive model. Subsequently, we solve a
> one-step look-ahead optimization problem which finds the pacing rate
> which optimally trades off RTT, RTT variance, and throughput according
> to the most recent model. Our method is computationally inexpensive
> making it readily implementable on current systems."
> 
> https://people.eecs.berkeley.edu/~dfk/pdfs/network_control_camera_ready.pdf
> 
> 
> -- 
> Make Music, Not War
> 
> Dave Täht
> CTO, TekLibre, LLC
> http://www.teklibre.com
> Tel: 1-831-435-0729