[Cake] Query Regarding CAKE

[Jonathan Morton]

> On 24 Oct, 2018, at 3:06 pm, Shefali Gupta <shefaligups11 at 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