Re: [aqm] I-D Action: draft-ietf-aqm-codel-03.txt

[Jonathan Morton <[e-mail]>]

> On 7 Jul, 2016, at 15:34, Michael Menth <[e-mail]> wrote:
> 
>> Based on our evaluations, with pure CoDel (without FQ-CoDel),
>> "reentering" is actually a common case. I think Dave and Toke should
>> have more experimental results to answer this question. (I included Dave
>> in CC)
> 
> We also studied this issue about one or two years ago. The algorithm
> controlling the reentering of the dropping mode may have a significant
> impact on control variables, drop rates, drop pattern depending on the
> traffic. It can also impact utilization. Most interesting is probably
> Fig. 6 on page 7 in
> https://atlas.informatik.uni-tuebingen.de/~menth/papers/Menth16e.pdf

That’s a very interesting paper for Codel enthusiasts.  IMHO, Codel-ACT performs much better on the important metrics than plain Codel, especially when faced with multiplexed flows.

I had also noticed the potential for Codel’s count to increase unboundedly while working on Cake; in fact when implemented as a 16-bit counter, it would wrap around on certain workloads, causing apparently chaotic behaviour.  I therefore modified the variant of Codel that Cake used to *halve* the count on re-entry, a much more aggressive reduction than Codel-ACT uses, as well as using a saturating increment to prevent wraparound.  However, I kept the basic behaviour of waiting a full interval before re-entry.

More recently, I have changed Cake over to use COBALT, which is a combination of Codel and BLUE; Codel is intended to handle responsive flows which behave in a TCP-like manner, and BLUE to take over if the flow proves to be unresponsive (by running into the queue length limit).

COBALT uses a re-implemented version of Codel with a much simplified main loop.  It also has a novel re-entry behaviour: the count is reduced while the queue length is below target by running the algorithm in reverse, without marking or dropping.  This means that very short non-dropping periods result in a slight reduction in count, and longer periods result in a larger reduction; the reduction also occurs faster when count is high.

With your paper in mind, I may also change it to use the shorter re-entry delay of Codel-ACT, as you explain very clearly how it may be beneficial, and this shows in the graphs as a lower peak delay and a reduction in loss synchronisation between flows.  I also think it will allow Codel to adapt more cleanly to RTTs significantly shorter than it is configured for - this is important where the defaults are set for internet-scale traffic, and people unthinkingly rely on those defaults in a LAN environment.

Here is the relevant part of COBALT’s Codel implementation, showing the re-entry count reduction strategy:

if(next_due && vars->dropping) {
	/* Use ECN mark if possible, otherwise drop */
	drop = !(vars->ecn_marked = INET_ECN_set_ce(skb));

	vars->count++;
	if(!vars->count)
		vars->count--;
	cobalt_invsqrt(vars);
	vars->drop_next = cobalt_control_law(vars->drop_next, p->interval, vars->rec_inv_sqrt);
} else {
	while(next_due) {
		vars->count--;
		cobalt_invsqrt(vars);
		vars->drop_next = cobalt_control_law(vars->drop_next, p->interval, vars->rec_inv_sqrt);
		schedule = now - vars->drop_next;
		next_due = vars->count && schedule >= 0;
	}
}

The full code can be found here:
	https://github.com/dtaht/sch_cake/blob/master/cobalt.c

 - Jonathan Morton