[Cake] Query Regarding CAKE

[Cake] Query Regarding CAKE

[Shefali Gupta]

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

Hello Jonathan and Dave,

Thanks for the quick replies.

We took sometime to understand the whole framework and have come up with
some more queries:

1. Can we use the COBALT code available on the following link as a
reference:
https://github.com/dtaht/sch_cake/blob/old-master/cobalt.c

2. Since ns-3 code is in C++, we're hoping to implement the different
modules (four modules as mentioned in LANMAN paper) of Cake in separate
classes.
Is that approach fine? or you recommend us to implement all modules in a
single file as done in Linux?

Thanks and Regards,
Shefali Gupta
Jendaipou Palmei

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

Re: [Cake] Query Regarding CAKE

[Jonathan Morton]

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

Yes, I think that's close enough to the final version.

Putting all the code in one file was imposed on us by Linux coding
standards, because COBALT isn't used by any other qdisc (yet).  I would
actively encourage more modularity in reimplementations, especially if you
can do so in ways which make reusing the algorithms in different
combinations easier.

- Jonathan Morton

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

Re: [Cake] Query Regarding CAKE

[Shefali Gupta]

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

Hi Jonathan,

Thanks for your feedback.

We're close to completing the implementation of COBALT based on that link
which we shared in our earlier email.

Yes, we will try and implement the Cake modules in ns-3 such that they can
be used in different combinations.

Thanks and Regards,
Shefali Gupta
Jendaipou Palmei

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

Re: [Cake] Query Regarding CAKE

[Dave Taht]

Shefali Gupta <shefaligups11@gmail.com> writes:

> Hello Jonathan and Dave,
>
> Thanks for the quick replies.
>
> We took sometime to understand the whole framework and have come up
> with some more queries:
>
> 1. Can we use the COBALT code available on the following link as a
> reference:
> https://github.com/dtaht/sch_cake/blob/old-master/cobalt.c
>
> 2. Since ns-3 code is in C++, we're hoping to implement the different
> modules (four modules as mentioned in LANMAN paper) of Cake in
> separate classes.
> Is that approach fine? or you recommend us to implement all modules in
> a single file as done in Linux?

I see jon has a later reply to this, this is just a note.

I would in the long run, really like to see a C++ boost library
implementing all the bufferbloat-fighting algorithms generically - I
tend to think that GPS fair and load-shedding and rate-limiting behavior
would be a boon in many applications.

I started work once on doing something generic in userspace in C but,
well, go do a "man queue" and recoil in horror. I should stick that
somewhere and tie myself to the chair long enough to finish it.

hmm... perhaps Go?

>
> Thanks and Regards,
> Shefali Gupta 
> Jendaipou Palmei 
>
> _______________________________________________
> Cake mailing list
> Cake@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/cake

Re: [Cake] Query Regarding CAKE

[Jonathan Morton]

> On 24 Oct, 2018, at 3:06 pm, Shefali Gupta <shefaligups11@gmail.com> wrote:
> 
> We're working on the implementation of CAKE in ns-3, but have been facing an issue about finding resources on COBALT (algorithm / pseudo code). In the LANMAN paper on CAKE, we did not find much detail about COBALT. Can anyone provide us resources on COBALT.

Essentially, COBALT is a variant of Codel, incorporating its key features:

 - Acts on dequeue, ie. signals at the head of the queue rather than at the tail.

 - Time based rather than packet percentage based, thereby interacting efficiently with TCP's RTT cycle.

 - Linear signalling frequency ramp over time, implemented through an inverse-square-root law per drop event, while packet sojourn time remains above target.

As Dave Täht noted, the implementation is different, being a nearly complete rewrite, but the behaviour is the same in simple cases.  The API is also different, being based entirely on calls from the qdisc into COBALT, rather than relying on a callback from Codel into the qdisc to obtain a dequeued packet.

COBALT returns a flag indicating whether the packet should be dropped, rather than doing so itself; this permits Cake to avoid dropping the last packet in a sub-queue, which could lead to "tail loss" and an RTO delay at the application level.  On ECN capable traffic, the Codel portion of COBALT signals using CE marks and does not flag any packets for dropping.

The functional differences between Codel and COBALT arise from limitations we observed in Codel's capabilities.

The behaviour when sojourn time fell below target, then rose again shortly afterwards, was poorly specified in Codel and didn't seem to have any theoretical basis.  I introduced a reversal of the linear-over-time frequency ramp, which proved to be reasonably easy to implement as well as being theoretically reasonable behaviour.  It should allow COBALT to adapt cleanly to lower-than-expected path RTTs, which require faster signalling and shorter reaction times when the target sojourn time is exceeded; I would be interested to see results which could establish whether that's actually true.

Codel also has trouble with unresponsive and anti-reponsive traffic due to its relatively gentle method of signalling, and with ECN blackholes in conjunction with ECN capable traffic.  Cake has a backstop here in the form of head-dropping from the longest queue in case of hitting a global backlog limit, but this typically leads to burst loss in much the same way as tail-drop FIFOs do.  Hence the introduction of the BLUE portion of COBALT.

BLUE, as implemented in COBALT, is exceedingly simple.  When packets are hard-dropped due to a global limit violation, the affected sub-queue's COBALT is notified of the event.  Subject to a timeout, this causes the drop percentage to be incremented by a fixed step.  BLUE never uses ECN, and acts only through packet drops.  When the sub-queue empties, COBALT is notified of this as well, and subject to the same timeout, decrements the drop percentage by a smaller step.  By acting only at these extremes, the action of BLUE avoids interfering with the normal action of Codel (which permits temporary excursions in queue length).

These modifications require the COBALT state to be regularly updated even when the associated sub-queue is empty and idle, as long as the COBALT state has not reached quiescence (zero drop percentage for BLUE, and a complete ramp-down of signalling frequency for Codel).  There are measures within Cake which ensure that occurs.

As always, the source code is authoritative as to actual behaviour - but please do continue to ask for clarification on rationale if required.

 - Jonathan Morton

Re: [Cake] Query Regarding CAKE

[Dave Taht]

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

Glad to hear it!

In the lwn article, cobalt was mis-identified as having something to do
with the per host fq portion of cake (which I wish we had a name for!). The
"blue" component of cake was easily at the time separated out from the
codel component, a patch and some testing were on this thread here:

https://lists.bufferbloat.net/pipermail/cake/2017-December/003167.html

At the time (in the src tree), the codel implementation in cake was
recognisably like the paper, it no longer is.


On Wed, Oct 24, 2018 at 5:06 AM Shefali Gupta <shefaligups11@gmail.com>
wrote:

> Hi all,
>
> We're working on the implementation of CAKE in ns-3, but have been facing
> an issue about finding resources on COBALT (algorithm / pseudo code). In
> the LANMAN paper on CAKE, we did not find much detail about COBALT. Can
> anyone provide us resources on COBALT.
>
> Congratulations on getting CAKE in the Linux mainline!
>
> Thanks,
> Shefali Gupta
> Jendaipou Palmei
> NITK Surathkal, India
> _______________________________________________
> 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

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

[Cake] Query Regarding CAKE

[Shefali Gupta]

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

Hi all,

We're working on the implementation of CAKE in ns-3, but have been facing
an issue about finding resources on COBALT (algorithm / pseudo code). In
the LANMAN paper on CAKE, we did not find much detail about COBALT. Can
anyone provide us resources on COBALT.

Congratulations on getting CAKE in the Linux mainline!

Thanks,
Shefali Gupta
Jendaipou Palmei
NITK Surathkal, India

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