[Cake] cake status & forks

[Dave Taht]

On Sat, Jan 28, 2017 at 3:06 AM, Adrian Popescu
<adriannnpopescu at 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