* Re: [Cake] Query Regarding CAKE
2018-10-24 12:06 [Cake] Query Regarding CAKE Shefali Gupta
@ 2018-10-24 15:04 ` Dave Taht
2018-10-24 18:43 ` Jonathan Morton
1 sibling, 0 replies; 7+ messages in thread
From: Dave Taht @ 2018-10-24 15:04 UTC (permalink / raw)
To: shefaligups11; +Cc: Cake List
[-- 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 --]
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [Cake] Query Regarding CAKE
2018-10-24 12:06 [Cake] Query Regarding CAKE Shefali Gupta
2018-10-24 15:04 ` Dave Taht
@ 2018-10-24 18:43 ` Jonathan Morton
1 sibling, 0 replies; 7+ messages in thread
From: Jonathan Morton @ 2018-10-24 18:43 UTC (permalink / raw)
To: Shefali Gupta; +Cc: cake
> 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
^ permalink raw reply [flat|nested] 7+ messages in thread