[Cake] cake status & forks

[Cake] cake status & forks

[Adrian Popescu]

Hello,

Cake has been under development for a while. It still doesn't seem to
be ready. I have some questions to ask.

LEDE uses a fork of Cake. Why does such a small project need to use a
fork to be included in another project? What's wrong with the main
repository?

Cake doesn't seem to have comments sprinkled all over the source code.
Is there any kind of documentation which describes the algorithms used
in the code? It's hard to know whether the code does the right thing
or not without comments.

Cake seems to be a lot more complicated than some of the other qdiscs.
It's harder to understand Cake's code. One such thing which isn't
documented is the logic behind the 8 way associative hash. It's hard
to tell exactly what's what because there's no explanation in the
code. Everything is spread across multiple functions without any
comments or documentation.

The lack of documentation and the Linux kernel specific code make it
quite difficult to port Cake to other operating systems. The lack of
comments and documentation makes it harder to prove the code is right.
There are no algorithms and no description of what the code does to
compare with the implementation.

What Linux kernel versions does Cake support currently? Are there any
plans to add comments to the code? Are there any plans to write
documentation on the individual discrete algorithms and constants used
in the code?

How should we compute the overhead options? How are we supposed to use
the new features without documentation?

Are there any plans for more major changes? Is the code still going to
receive major overhauls?

Re: [Cake] cake status & forks

[Dave Taht]

On Sat, Jan 28, 2017 at 3:06 AM, Adrian Popescu
<adriannnpopescu@gmail.com> wrote:
> Hello,
>
> Cake has been under development for a while. It still doesn't seem to
> be ready. I have some questions to ask.
>
> LEDE uses a fork of Cake. Why does such a small project need to use a
> fork to be included in another project? What's wrong with the main
> repository?

There were two new features (mpu and nat) that needed further testing.
The enthusiasm for such was that they went into lede first...

I merged these into cake mainline last night. Making, temporarily, a
greater mess of things than when we started. Hopefully everything can
get back into sync now. I did some testing on the API on x86 and
things appeared to be working correctly again.

There are also structural and personal differences within the project
that haven't helped. The main developer has a tendency to disappear,
the project manager (me), has a tendency to be busy, and there are
both users and core folk pulling things in different ways.

Lastly, there is no funding in the project left, which has been the
case for a very, very long time.

> Cake doesn't seem to have comments sprinkled all over the source code.
> Is there any kind of documentation which describes the algorithms used
> in the code? It's hard to know whether the code does the right thing
> or not without comments.

Several of the algorithms are innovative and new, and at some point or
another someone will get around to finishing the paper on them.
Jonathan is the originator of several of them, and I'll argue we could
use a Dyson to translate and synthesize between code and doc.

The best doc we have on the intent of cake and how it goes about it is here:

https://www.bufferbloat.net/projects/codel/wiki/CakeTechnical/

We could certainly use better tests for whether the API is actually
working or not. I believe this is one of the things that have bit us
on testing of late - but I was not paying attention to the fork, or
cake, being busy on make-wifi-fast stuff.

Note also: "Doing the right thing" is also a matter of measurement.
These are *new* algorithms for queue management, never developed
before. As one example, the codel algorithm endured 9+ months of
extensive simulation before it got written up, and then ported to the
kernel, and tuned more than a bit there.

Cake, well, cake "just grew", in response to the majority of requests
from the field. The core deficits observed there were notably per host
fq, nat, more perfect hashing, and QoS... which is what the sqm
scripts tried to address with several increasingly complicated qdisc
setups and cake has tried to build upon, and simplify.

My intent (had funding ever existed) was to port this stuff to ns3 and
try to take it apart in more extensive simulation there.

>
> Cake seems to be a lot more complicated than some of the other qdiscs.

No kidding! It's also the only thing out there that's ever existed
that can shape to this extent of perfection, cope with nat, do per
host fq while still doing flow fq, and manage queue length with an
aqm.

> It's harder to understand Cake's code. One such thing which isn't
> documented is the logic behind the 8 way associative hash. It's hard
> to tell exactly what's what because there's no explanation in the
> code. Everything is spread across multiple functions without any
> comments or documentation.

I love the 8 way associative hash!

The really hard part for me to understand or describe is the per-host fq,
and as best as I can tell triple-isolate is not working properly - but
perhaps that was an API change that didn't make it to the field.

https://github.com/dtaht/sch_cake/issues/46

was actually the event that triggered me to go and try to sort matters out.

> The lack of documentation and the Linux kernel specific code make it
> quite difficult to port Cake to other operating systems.

We made it dual BSD/gpl licensed so you can at least use the code as a
reference. The *best* way I can think for someone else to get a deep
understanding for how it works would be to port it to another OS (dpdk
was high on my list).

> The lack of
> comments and documentation makes it harder to prove the code is right.

While I agree, proving the code is right is not just a matter of documentation.
The work to prove each algorithm is correct in conjunction with the
others is quite enormous.

> There are no algorithms and no description of what the code does to
> compare with the implementation.
>
> What Linux kernel versions does Cake support currently?

In general we have tried to make it compile on versions going back as
far as 3.12. We don't check very often - the principal users of that
are the folk at ubnt testing it and some folk at comcast.

> Are there any
> plans to add comments to the code? Are there any plans to write
> documentation on the individual discrete algorithms and constants used
> in the code?
>
> How should we compute the overhead options? How are we supposed to use
> the new features without documentation?

Like every under-resourced open source project, if there are things
you would like to do, go right ahead and do them. Since you are big on
documentation, please go for it.

>
> Are there any plans for more major changes? Is the code still going to
> receive major overhauls?

Cake has muddled along for a long time without me paying much attention to it.

At the moment, however, I do regard cake as feature complete with the
nat per-host fq support. Most of the other members of the team would
like to get it upstream. I'd like to clean up the API and stats while
doing that. I'm pretty sure a feature or two will get rejected by
upstream...

One nice new feature landed in net-next for fq_codel last week, which
allows for terminating vpns better. I looked over cake while cleaning
up (the backport defines made my eyes bleed), and I think that feature
can't work in cake.

I appreciate your interest and concern. I think cake contains
important, breakthrough technologies, and they need to be polished and
made more useful. I would love it, if one day, cake inspired the same
level of academic interest that codel did and industry acceptance that
fq_codel has.

-- 
Dave Täht
Let's go make home routers and wifi faster! With better software!
http://blog.cerowrt.org

Re: [Cake] cake status & forks

[Adrian Popescu]

Hello,

I've been reading the code for a while. I'll experiment and send any
useful patches.

The technical docs would have been extremely useful in the process.
The CakeTechnical page is useful, but it lacks descriptions of the
algorithms.

Is cake still being maintained? What's the status of the cobalt branch?

On Sat, Jan 28, 2017 at 6:42 PM, Dave Taht <dave.taht@gmail.com> wrote:
> On Sat, Jan 28, 2017 at 3:06 AM, Adrian Popescu
> <adriannnpopescu@gmail.com> wrote:
>> Hello,
>>
>> Cake has been under development for a while. It still doesn't seem to
>> be ready. I have some questions to ask.
>>
>> LEDE uses a fork of Cake. Why does such a small project need to use a
>> fork to be included in another project? What's wrong with the main
>> repository?
>
> There were two new features (mpu and nat) that needed further testing.
> The enthusiasm for such was that they went into lede first...
>
> I merged these into cake mainline last night. Making, temporarily, a
> greater mess of things than when we started. Hopefully everything can
> get back into sync now. I did some testing on the API on x86 and
> things appeared to be working correctly again.
>
> There are also structural and personal differences within the project
> that haven't helped. The main developer has a tendency to disappear,
> the project manager (me), has a tendency to be busy, and there are
> both users and core folk pulling things in different ways.
>
> Lastly, there is no funding in the project left, which has been the
> case for a very, very long time.
>
>> Cake doesn't seem to have comments sprinkled all over the source code.
>> Is there any kind of documentation which describes the algorithms used
>> in the code? It's hard to know whether the code does the right thing
>> or not without comments.
>
> Several of the algorithms are innovative and new, and at some point or
> another someone will get around to finishing the paper on them.
> Jonathan is the originator of several of them, and I'll argue we could
> use a Dyson to translate and synthesize between code and doc.
>
> The best doc we have on the intent of cake and how it goes about it is here:
>
> https://www.bufferbloat.net/projects/codel/wiki/CakeTechnical/
>
> We could certainly use better tests for whether the API is actually
> working or not. I believe this is one of the things that have bit us
> on testing of late - but I was not paying attention to the fork, or
> cake, being busy on make-wifi-fast stuff.
>
> Note also: "Doing the right thing" is also a matter of measurement.
> These are *new* algorithms for queue management, never developed
> before. As one example, the codel algorithm endured 9+ months of
> extensive simulation before it got written up, and then ported to the
> kernel, and tuned more than a bit there.
>
> Cake, well, cake "just grew", in response to the majority of requests
> from the field. The core deficits observed there were notably per host
> fq, nat, more perfect hashing, and QoS... which is what the sqm
> scripts tried to address with several increasingly complicated qdisc
> setups and cake has tried to build upon, and simplify.
>
> My intent (had funding ever existed) was to port this stuff to ns3 and
> try to take it apart in more extensive simulation there.
>
>>
>> Cake seems to be a lot more complicated than some of the other qdiscs.
>
> No kidding! It's also the only thing out there that's ever existed
> that can shape to this extent of perfection, cope with nat, do per
> host fq while still doing flow fq, and manage queue length with an
> aqm.
>
>> It's harder to understand Cake's code. One such thing which isn't
>> documented is the logic behind the 8 way associative hash. It's hard
>> to tell exactly what's what because there's no explanation in the
>> code. Everything is spread across multiple functions without any
>> comments or documentation.
>
> I love the 8 way associative hash!
>
> The really hard part for me to understand or describe is the per-host fq,
> and as best as I can tell triple-isolate is not working properly - but
> perhaps that was an API change that didn't make it to the field.
>
> https://github.com/dtaht/sch_cake/issues/46
>
> was actually the event that triggered me to go and try to sort matters out.
>
>> The lack of documentation and the Linux kernel specific code make it
>> quite difficult to port Cake to other operating systems.
>
> We made it dual BSD/gpl licensed so you can at least use the code as a
> reference. The *best* way I can think for someone else to get a deep
> understanding for how it works would be to port it to another OS (dpdk
> was high on my list).
>
>> The lack of
>> comments and documentation makes it harder to prove the code is right.
>
> While I agree, proving the code is right is not just a matter of documentation.
> The work to prove each algorithm is correct in conjunction with the
> others is quite enormous.
>
>> There are no algorithms and no description of what the code does to
>> compare with the implementation.
>>
>> What Linux kernel versions does Cake support currently?
>
> In general we have tried to make it compile on versions going back as
> far as 3.12. We don't check very often - the principal users of that
> are the folk at ubnt testing it and some folk at comcast.
>
>> Are there any
>> plans to add comments to the code? Are there any plans to write
>> documentation on the individual discrete algorithms and constants used
>> in the code?
>>
>> How should we compute the overhead options? How are we supposed to use
>> the new features without documentation?
>
> Like every under-resourced open source project, if there are things
> you would like to do, go right ahead and do them. Since you are big on
> documentation, please go for it.
>
>>
>> Are there any plans for more major changes? Is the code still going to
>> receive major overhauls?
>
> Cake has muddled along for a long time without me paying much attention to it.
>
> At the moment, however, I do regard cake as feature complete with the
> nat per-host fq support. Most of the other members of the team would
> like to get it upstream. I'd like to clean up the API and stats while
> doing that. I'm pretty sure a feature or two will get rejected by
> upstream...
>
> One nice new feature landed in net-next for fq_codel last week, which
> allows for terminating vpns better. I looked over cake while cleaning
> up (the backport defines made my eyes bleed), and I think that feature
> can't work in cake.
>
> I appreciate your interest and concern. I think cake contains
> important, breakthrough technologies, and they need to be polished and
> made more useful. I would love it, if one day, cake inspired the same
> level of academic interest that codel did and industry acceptance that
> fq_codel has.
>
> --
> Dave Täht
> Let's go make home routers and wifi faster! With better software!
> http://blog.cerowrt.org

Re: [Cake] cake status & forks

[Kevin Darbyshire-Bryant]

On 27/06/17 19:41, Adrian Popescu wrote:
> Hello,
> 
> I've been reading the code for a while. I'll experiment and send any
> useful patches.
> 
> The technical docs would have been extremely useful in the process.
> The CakeTechnical page is useful, but it lacks descriptions of the
> algorithms.
> 
> Is cake still being maintained? What's the status of the cobalt branch?
Good questions.

The cobalt branch has an attractive feature of 'ingress' mode, which 
from what I can tell, puts the 'bandwidth used' calculation before the 
drop/no drop packet decision rather than after (as used in the normal 
egress mode) - thus we add up the bandwidth that arrived rather than 
bandwidth used post our drop.

I tried putting the relevant commits into master and did some simple 
testing which proved ok.  Shortly afterward I saw a report of increased 
latency in egress mode and saw a similar thing myself - I probably 
panicked a bit and reverted the 3 commits very shortly after.....but 
continued running 'ingress' mode code myself.  I haven't seen the issue 
return and suspect a misconfig with rates on my part to be the cause. 
so I suspect 'ingress' mode could go into master.  For those who've 
used/tested this independently it has proved useful in controlling the 
torrent like behaviour of certain games providers and OS updates.

The 'lower latency priority' changes haven't obviously been a real 
improvement. See the end of https://github.com/dtaht/sch_cake/issues/52

I agreed an overview of the algorithms present in the code would be 
incredibly useful - I started trying to do so by reading the code a year 
or so back...and the little I produced is now very out of date (it was 
pre the original cobalt implementation)

Kevin