[Cake] Cake implementations

[Cake] Cake implementations

[Adam Moffett]

[-- Attachment #1: Type: text/plain, Size: 407 bytes --]

A colleague just turned me onto Cake.

My impression is that this is a research project, and that the hope is 
for commercial products to implement cake algorithms in their equipment. 
  Is that about right?

Are there any commercial products already using Cake?


-- Adam Moffett, Network Engineer
Plexicomm - Internet Solutions | www.plexicomm.net
Office: 1.866.759.4678 | Fax: 1.866.852.4688

[-- Attachment #2: Type: text/html, Size: 1775 bytes --]

Re: [Cake] Cake implementations

[Dave Taht]

On Thu, Nov 21, 2019 at 1:05 PM Adam Moffett <adam@plexicomm.net> wrote:
>
> A colleague just turned me onto Cake.
>
> My impression is that this is a research project, and that the hope is for commercial products to implement cake algorithms in their equipment.  Is that about right?

It essentially went production with the release of openwrt 18.6, and
incorporation into linux mainline as of version 4.19 in august of last
year.

Certainly by publishing the algorithms and analyses (as well as the
code under dual gpl/bsd) we hoped to see some uptake outside of linux.
https://arxiv.org/pdf/1804.07617.pdf is one fo the two main papers on
it.

Cake is the wrap up of 8 years of development of the SQM (qos) system
(which was htb+fq_codel). Derivatives of SQM are very widely deployed
with many lookalikes (both in linux and bsd) under various trade names
like "adaptive qos" or "anti-bufferbloat". We tired of some of those
derivatives's issues and went for the best of the best ideas from the
sqm deployment. Some are written up here:

https://arxiv.org/pdf/1804.07617.pdf - of note are a revised codel
algorithm, per host/per flow fq (probably the most requested feature),
and ack-filtering, wrapped up in a shaper designed to defeat htb based
ones.

Still the main (outside of linux) cake repo is being used for
additional advanced research, notably nowadays into the SCE - "some
congestion experienced" concept - circulating within the ietf.
https://tools.ietf.org/html/draft-morton-tsvwg-sce-01 - and

Honestly my hope has been that more gear would adopt the BQL (or AQL
for wireless) subsystems which would eliminate the need for shaping in
many cases, rather than go whole howg on shaping everything via cake.
>
> Are there any commercial products already using Cake?

Evenroute, eero, ubnt top that list. Evenroute's implementation is
superb, the first one that used active line measurements to handle
"sag". Anything derived from openwrt (somewhere between 10-30% of the
home router market). I'm not sure if preseem is using it or not.
dd-wrt. Most other things doing "SQM" are doing it via htb + fq_codel.


>
>
> -- Adam Moffett, Network Engineer
> Plexicomm - Internet Solutions | www.plexicomm.net
> Office: 1.866.759.4678 | Fax: 1.866.852.4688
>
> _______________________________________________
> Cake mailing list
> Cake@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/cake



-- 

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

Re: [Cake] Cake implementations

[Adam Moffett]

>>
>>  Are there any commercial products already using Cake?
>
>Evenroute, eero, ubnt top that list. Evenroute's implementation is
>superb, the first one that used active line measurements to handle
>"sag". Anything derived from openwrt (somewhere between 10-30% of the
>home router market). I'm not sure if preseem is using it or not.
>dd-wrt. Most other things doing "SQM" are doing it via htb + fq_codel.
>
>
An idea which was floated was to experiment with routing ISP customer 
traffic through a Linux server using cake to improve customer 
experience.  Basically like Preseem.  My colleague has toyed with it a 
bit in small test cases and was impressed with the outcomes.

He's looked closer than I have, but I'm trying to picture how his idea 
would scale.  I believe I'm seeing a CLI tool for configuring policies.  
It seems like we'd have to create a middle layer to create/update 
policies for customer's IP address based on information obtained from 
our AAA and CRM systems.  I can picture some shapes that might take, but 
I think it would ultimately have to revolve around scripting the tc 
command.  There would be thousands of policies and a policy would be 
created/updated whenever a subscriber reconnects (e.g. when a DHCP lease 
renews or a RADIUS auth event happens or similar).

Should we even pursue this idea?

Although most staff who would touch this will have studied programming 
in college, I would not qualify any of us as "programmers" per se.  My 
biggest concern would be hitting a service affecting problem that we 
can't solve.

Second concern is that many of our equipment vendors already use Linux.  
Even Cisco now in some products.  Maybe we'll waste our time trying to 
roll our own solution and then find that a software update from a vendor 
next year gives us everything we needed anyway.

-Adam

Re: [Cake] Cake implementations

[Toke Høiland-Jørgensen]

"Adam Moffett" <adam@plexicomm.net> writes:

>>>
>>>  Are there any commercial products already using Cake?
>>
>>Evenroute, eero, ubnt top that list. Evenroute's implementation is
>>superb, the first one that used active line measurements to handle
>>"sag". Anything derived from openwrt (somewhere between 10-30% of the
>>home router market). I'm not sure if preseem is using it or not.
>>dd-wrt. Most other things doing "SQM" are doing it via htb + fq_codel.
>>
>>
> An idea which was floated was to experiment with routing ISP customer 
> traffic through a Linux server using cake to improve customer 
> experience.  Basically like Preseem.  My colleague has toyed with it a 
> bit in small test cases and was impressed with the outcomes.
>
> He's looked closer than I have, but I'm trying to picture how his idea 
> would scale.  I believe I'm seeing a CLI tool for configuring policies.  
> It seems like we'd have to create a middle layer to create/update 
> policies for customer's IP address based on information obtained from 
> our AAA and CRM systems.  I can picture some shapes that might take, but 
> I think it would ultimately have to revolve around scripting the tc 
> command.  There would be thousands of policies and a policy would be 
> created/updated whenever a subscriber reconnects (e.g. when a DHCP lease 
> renews or a RADIUS auth event happens or similar).

I know several ISPs that do this (route traffic through a Linux box and
shape there). This deployment mode has not been the primary focus of
CAKE, though; the "standard" way to do it is with HTB+FQ-CoDel, which
allows you to set up arbitrarily complex configurations on a single
interface. This can also be made to scale, but there's a central qdisc
lock in Linux that you have to get around to scale to multiple cores.
Fortunately, Jesper has already solved this particular issue:

https://github.com/netoptimizer/xdp-cpumap-tc

> Should we even pursue this idea?

In my own totally non-biased opinion: Yes! :)

> Although most staff who would touch this will have studied programming 
> in college, I would not qualify any of us as "programmers" per se.  My 
> biggest concern would be hitting a service affecting problem that we 
> can't solve.

One way to go about this would be to open source the entire solution.
There are already bits and pieces available as open source (such as
Jesper's repository above, and sqm-scripts[0]) that you can build on,
and this way you could enlist community help to solve any issues with
the Linux side. You'd still need to get the data from your internal
systems, of course, but you could define a simple configuration format
that was part of the open source code; then you'll just need to write a
script that grabs customer info from your CRM and outputs the config
format...

> Second concern is that many of our equipment vendors already use
> Linux. Even Cisco now in some products. Maybe we'll waste our time
> trying to roll our own solution and then find that a software update
> from a vendor next year gives us everything we needed anyway.

This would be great, of course, and do go and bug your vendors to solve
this problem! Note, however, that just because a system is running
Linux on the control plane, it may be using a hardware-offloaded data
plane that does not have any of the bufferbloat mitigation features
(unless the vendor specifically implemented them). I'm hoping that
*eventually* these things will be ubiquitous across the industry, but
thus far this has seemed to be an "any decade now" kind of proposition :/

-Toke

Re: [Cake] Cake implementations

[Justin Kilpatrick]

>  An idea which was floated was to experiment with routing ISP customer 
> >traffic through a Linux server using cake to improve customer 
>  experience.  Basically like Preseem.  My colleague has toyed with it a 
> >bit in small test cases and was impressed with the outcomes.

Althea.net runs Cake at every hop. Since we use Babel to dynamically generate the network topology we rely on it's neighbor RTT extension and bandwidth counters to reduce the bandwidth over a link when an intermediate device has decided to become bloaty. 

It's been a very effective system that results in happier customers even when we have weak leaks or crazy failover situations. Usually wireless links have to be over provisioned by a factor of 2ish to keep latency under control in the face of dynamic interference and other external factors. Instead Althea networks have more smaller links then back links between each pop.

Traffic is then load balanced based on latency and when an antenna starts to really go crazy due to overloading the auto tuner clamps down Cake until the experience is good again. 

-- 
  Justin Kilpatrick
  justin@althea.net

On Fri, Nov 22, 2019, at 6:46 AM, Toke Høiland-Jørgensen wrote:
> "Adam Moffett" <adam@plexicomm.net> writes:
> 
> >>>
> >>>  Are there any commercial products already using Cake?
> >>
> >>Evenroute, eero, ubnt top that list. Evenroute's implementation is
> >>superb, the first one that used active line measurements to handle
> >>"sag". Anything derived from openwrt (somewhere between 10-30% of the
> >>home router market). I'm not sure if preseem is using it or not.
> >>dd-wrt. Most other things doing "SQM" are doing it via htb + fq_codel.
> >>
> >>
> > An idea which was floated was to experiment with routing ISP customer 
> > traffic through a Linux server using cake to improve customer 
> > experience.  Basically like Preseem.  My colleague has toyed with it a 
> > bit in small test cases and was impressed with the outcomes.
> >
> > He's looked closer than I have, but I'm trying to picture how his idea 
> > would scale.  I believe I'm seeing a CLI tool for configuring policies.  
> > It seems like we'd have to create a middle layer to create/update 
> > policies for customer's IP address based on information obtained from 
> > our AAA and CRM systems.  I can picture some shapes that might take, but 
> > I think it would ultimately have to revolve around scripting the tc 
> > command.  There would be thousands of policies and a policy would be 
> > created/updated whenever a subscriber reconnects (e.g. when a DHCP lease 
> > renews or a RADIUS auth event happens or similar).
> 
> I know several ISPs that do this (route traffic through a Linux box and
> shape there). This deployment mode has not been the primary focus of
> CAKE, though; the "standard" way to do it is with HTB+FQ-CoDel, which
> allows you to set up arbitrarily complex configurations on a single
> interface. This can also be made to scale, but there's a central qdisc
> lock in Linux that you have to get around to scale to multiple cores.
> Fortunately, Jesper has already solved this particular issue:
> 
> https://github.com/netoptimizer/xdp-cpumap-tc
> 
> > Should we even pursue this idea?
> 
> In my own totally non-biased opinion: Yes! :)
> 
> > Although most staff who would touch this will have studied programming 
> > in college, I would not qualify any of us as "programmers" per se.  My 
> > biggest concern would be hitting a service affecting problem that we 
> > can't solve.
> 
> One way to go about this would be to open source the entire solution.
> There are already bits and pieces available as open source (such as
> Jesper's repository above, and sqm-scripts[0]) that you can build on,
> and this way you could enlist community help to solve any issues with
> the Linux side. You'd still need to get the data from your internal
> systems, of course, but you could define a simple configuration format
> that was part of the open source code; then you'll just need to write a
> script that grabs customer info from your CRM and outputs the config
> format...
> 
> > Second concern is that many of our equipment vendors already use
> > Linux. Even Cisco now in some products. Maybe we'll waste our time
> > trying to roll our own solution and then find that a software update
> > from a vendor next year gives us everything we needed anyway.
> 
> This would be great, of course, and do go and bug your vendors to solve
> this problem! Note, however, that just because a system is running
> Linux on the control plane, it may be using a hardware-offloaded data
> plane that does not have any of the bufferbloat mitigation features
> (unless the vendor specifically implemented them). I'm hoping that
> *eventually* these things will be ubiquitous across the industry, but
> thus far this has seemed to be an "any decade now" kind of proposition :/
> 
> -Toke
> 
> _______________________________________________
> Cake mailing list
> Cake@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/cake
>

Re: [Cake] Cake implementations

[Toke Høiland-Jørgensen]

"Justin Kilpatrick" <justin@althea.net> writes:

>>  An idea which was floated was to experiment with routing ISP customer 
>> >traffic through a Linux server using cake to improve customer 
>>  experience.  Basically like Preseem.  My colleague has toyed with it a 
>> >bit in small test cases and was impressed with the outcomes.
>
> Althea.net runs Cake at every hop. Since we use Babel to dynamically
> generate the network topology we rely on it's neighbor RTT extension
> and bandwidth counters to reduce the bandwidth over a link when an
> intermediate device has decided to become bloaty.
>
> It's been a very effective system that results in happier customers
> even when we have weak leaks or crazy failover situations. Usually
> wireless links have to be over provisioned by a factor of 2ish to keep
> latency under control in the face of dynamic interference and other
> external factors. Instead Althea networks have more smaller links then
> back links between each pop.

That's interesting. So you're running CAKE as a (dynamically
configured?) shaper on top of the wireless link? What radio chipsets are
you using and have you benchmarked this against just relying on the
mac80211 FQ implementation (if that is available with your chipset)?

-Toke

Re: [Cake] Cake implementations

[Adam Moffett]

[-- Attachment #1: Type: text/plain, Size: 1006 bytes --]


>
>>  Second concern is that many of our equipment vendors already use
>>  Linux. Even Cisco now in some products. Maybe we'll waste our time
>>  trying to roll our own solution and then find that a software update
>>  from a vendor next year gives us everything we needed anyway.
>
>This would be great, of course, and do go and bug your vendors to solve
>this problem! Note, however, that just because a system is running
>Linux on the control plane, it may be using a hardware-offloaded data
>plane that does not have any of the bufferbloat mitigation features
>(unless the vendor specifically implemented them). I'm hoping that
>*eventually* these things will be ubiquitous across the industry, but
>thus far this has seemed to be an "any decade now" kind of proposition :/
>
>-Toke
That's a great point.

Is the software more or less CPU independent? Would we run into any 
known problems with a 72-core Tilera platform?

Thanks for all your help and input by the way.

-Adam

[-- Attachment #2: Type: text/html, Size: 2481 bytes --]

Re: [Cake] Cake implementations

[Jonathan Morton]

> On 22 Nov, 2019, at 9:33 pm, Adam Moffett <adam@plexicomm.net> wrote:
> 
> Is the software more or less CPU independent?  Would we run into any known problems with a 72-core Tilera platform? 

I don't know how well it scales to many cores (though that patch Toke mentioned will certainly help), but it should compile for just about any Linux-supported CPU.  We know it works on ARM, MIPS, PowerPC, AMD64…

 - Jonathan Morton

Re: [Cake] Cake implementations

[Toke Høiland-Jørgensen]

"Adam Moffett" <adam@plexicomm.net> writes:

>>
>>>  Second concern is that many of our equipment vendors already use
>>>  Linux. Even Cisco now in some products. Maybe we'll waste our time
>>>  trying to roll our own solution and then find that a software update
>>>  from a vendor next year gives us everything we needed anyway.
>>
>>This would be great, of course, and do go and bug your vendors to solve
>>this problem! Note, however, that just because a system is running
>>Linux on the control plane, it may be using a hardware-offloaded data
>>plane that does not have any of the bufferbloat mitigation features
>>(unless the vendor specifically implemented them). I'm hoping that
>>*eventually* these things will be ubiquitous across the industry, but
>>thus far this has seemed to be an "any decade now" kind of proposition :/
>>
>>-Toke
> That's a great point.
>
> Is the software more or less CPU independent? Would we run into any 
> known problems with a 72-core Tilera platform?

Hmm, well, maybe? Depends on the networking hardware; you can run a
separate qdisc on each hardware queue on your network adapter. So if you
can configure that for enough queues you can scale to all 72 cores.
Otherwise, you'll get lock contention between cores trying to transmit
on the same hardware queue, in which case the best solution may be to
configure packet steering so you're just not using all cores.

Jesper's script that I linked previously is basically a way to program
this steering. So it should be doable, but some care is needed in
designing the system.

> Thanks for all your help and input by the way.

You're very welcome! It's always great to hear from someone who is aware
of (and wants to fix!) bufferbloat in their network :)

-Toke

Re: [Cake] Cake implementations

[Jesper Dangaard Brouer]

On Fri, 22 Nov 2019 12:46:18 +0100
Toke Høiland-Jørgensen <toke@redhat.com> wrote:

> "Adam Moffett" <adam@plexicomm.net> writes:
> 
> >>>
> >>>  Are there any commercial products already using Cake?  
> >>
> >>Evenroute, eero, ubnt top that list. Evenroute's implementation is
> >>superb, the first one that used active line measurements to handle
> >>"sag". Anything derived from openwrt (somewhere between 10-30% of the
> >>home router market). I'm not sure if preseem is using it or not.
> >>dd-wrt. Most other things doing "SQM" are doing it via htb + fq_codel.
> >>
> >>  
> > An idea which was floated was to experiment with routing ISP
> > customer traffic through a Linux server using cake to improve
> > customer experience.  Basically like Preseem.  My colleague has
> > toyed with it a bit in small test cases and was impressed with the
> > outcomes.
> >
> > He's looked closer than I have, but I'm trying to picture how his
> > idea would scale.  I believe I'm seeing a CLI tool for configuring
> > policies. It seems like we'd have to create a middle layer to
> > create/update policies for customer's IP address based on
> > information obtained from our AAA and CRM systems.  I can picture
> > some shapes that might take, but I think it would ultimately have
> > to revolve around scripting the tc command.  There would be
> > thousands of policies and a policy would be created/updated
> > whenever a subscriber reconnects (e.g. when a DHCP lease renews or
> > a RADIUS auth event happens or similar).  
> 
> I know several ISPs that do this (route traffic through a Linux box and
> shape there). This deployment mode has not been the primary focus of
> CAKE, though; the "standard" way to do it is with HTB+FQ-CoDel, which
> allows you to set up arbitrarily complex configurations on a single
> interface. 

Yes, I worked for an ISP back in 2005, that route traffic through a
Linux box and does shaping.  There were a number of scalabilities
issues, that we fixed (upstream) and also Open Sources components for
others to reuse.

I did a public talk in 2008 about how we made it scale:
 http://people.netfilter.org/hawk/presentations/osd2008/osd2008_iptables_rules_JesperDangaardBrouer.pdf

This was before Codel and even-before Bufferbloat was coined/defined.
Our setup was HTB+SFQ, with a shaper per customer.  This actually
solved the bufferbloat problem in-practice for people, as SFQ gave each
end-user 128 queues.

Today I would not use iptables for this.  Instead I would use BPF or
nftables 'set' infrastructure.


> This can also be made to scale, but there's a central qdisc
> lock in Linux that you have to get around to scale to multiple cores.
> Fortunately, Jesper has already solved this particular issue:
> 
> https://github.com/netoptimizer/xdp-cpumap-tc

The central qdisc TX lock is a major scalability issue.  But I've
solved in above link, via XDP and TC.  This actually runs in production
at an ISP.

 
> > Should we even pursue this idea?  
> 
> In my own totally non-biased opinion: Yes! :)

It would be great.


> > Although most staff who would touch this will have studied programming 
> > in college, I would not qualify any of us as "programmers" per se.  My 
> > biggest concern would be hitting a service affecting problem that we 
> > can't solve.  
> 
> One way to go about this would be to open source the entire solution.
> There are already bits and pieces available as open source (such as
> Jesper's repository above, and sqm-scripts[0]) that you can build on,
> and this way you could enlist community help to solve any issues with
> the Linux side. You'd still need to get the data from your internal
> systems, of course, but you could define a simple configuration format
> that was part of the open source code; then you'll just need to write a
> script that grabs customer info from your CRM and outputs the config
> format...

Yes, this is the advantage of Open Source! :-)

If you create this as Open Source, then feel free to reach out to me
directly.  And I know of several other people (working at ISPs) that
would likely be interested in collaborating.

As Toke wrote, you can still keep your CRM system proprietary and
closed-source, we don't care anyhow ;-)

 
> > Second concern is that many of our equipment vendors already use
> > Linux. Even Cisco now in some products. Maybe we'll waste our time
> > trying to roll our own solution and then find that a software update
> > from a vendor next year gives us everything we needed anyway.  

I would not hold my breath... and if it does come as a software
upgrade, you can expect to pay plenty for it...

Maybe I'm the wrong guy to ask, but I really think it is straight
forward to implement an ISP Linux router with per customer handling.
All the components seems avail as Open Source.  (There do seem to be a
lack around a DHCP server that can handle this well).

 
> This would be great, of course, and do go and bug your vendors to
> solve this problem! Note, however, that just because a system is
> running Linux on the control plane, it may be using a
> hardware-offloaded data plane that does not have any of the
> bufferbloat mitigation features (unless the vendor specifically
> implemented them). I'm hoping that *eventually* these things will be
> ubiquitous across the industry, but thus far this has seemed to be an
> "any decade now" kind of proposition :/

I would prefer, not to waste time on creating bugs for your vendor, but
instead actually have the ability to fix the issue myself, or hire some
Linux consultant that can...

-- 
Best regards,
  Jesper Dangaard Brouer
  MSc.CS, Principal Kernel Engineer at Red Hat
  LinkedIn: http://www.linkedin.com/in/brouer