[Codel] [Cake] Proposing COBALT

[Jonathan Morton]

> On 24 May, 2016, at 16:47, Jeff Weeks <jweeks at sandvine.com> wrote:
> 
>> In COBALT, I keep the drop-scheduler running in this phase, but without actually dropping packets, and *decrementing* count instead of incrementing it; the backoff phase then 
>> naturally ends when count returns to zero, instead of after an arbitrary hard timeout.  The loop simply ensures that count will reduce by the correct amount, even if traffic 
>> temporarily ceases on the queue.  Ideally, this should cause Codel’s count value to stabilise where 50% of the time is spent above target sojourn time, and 50% below.  (Actual 
>> behaviour won’t quite be ideal, but it should be closer than before.)
> 
> I tried this as well, at one point, but can't remember, off-hand, why I didn't stick with it; will have to see if I can find mention of it in my notes.
> What trigger are you using to decrement count?  I initially did a crude decrement of count every interval, but then you end up with a ramp-down time which is considerably slower then the ramp-up (and the ramp up is slow to begin with).
> I assume you're actually re-calculating the next drop, using the 1/sqrt(count) but instead of dropping and increasing count, you're simply decreasing count, so the time to get from 1->N is the same as the time to get to N->1?

That’s basically right.  In retrospect, it seems like a very obvious approach to the backoff problem.  :-)

Of course, due to the “priming” delay and the possibility of the signalling frequency exceeding the packet rate, it’s likely to take *less* time to ramp down than to ramp up; this is why the ramping down is guarded by a while loop.

>> As another simplification, I eliminated the “primed” state (waiting for interval to expire) as an explicit entity, by simply scheduling the first drop event to be at now+interval when 
>> entering the dropping state.  This also eliminates the first_above_time variable.  Any packets with sojourn times below target will bump Codel out of the dropping state anyway.
> 
> How do you handle the case where you're scheduled a drop event 100ms in the future, and we immediately see low latency; is the event descheduled?
> If not, what if we then see high latency again; can the still-scheduled-event cause us to start dropping packets earlier than 100ms?

The first drop event is scheduled by setting the “dropping” flag, ensuring that “count” is nonzero, and setting the “drop_next” timestamp to now+interval.  Any packet below the target sojourn time clears the “dropping” flag, which prevents marking or dropping from occurring - which is why the explicit “primed” state is eliminated.

Since the timestamp is set in this way whenever the “dropping” flag transitions from cleared to set, there are no spurious drop events.

The code is in the sch_cake repo if you want to examine the details.  I promise it’s a lot easier to read than the original Codel code.

 - Jonathan Morton