Cake - FQ_codel the next generation
 help / color / mirror / Atom feed
* [Cake] cake, codel5.h, ecn marking & dropping. Confused
@ 2016-05-04  9:57 Kevin Darbyshire-Bryant
  2016-05-04 11:41 ` Jonathan Morton
  0 siblings, 1 reply; 3+ messages in thread
From: Kevin Darbyshire-Bryant @ 2016-05-04  9:57 UTC (permalink / raw)
  To: cake

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

Hi All,

As a result of Eric's recent change to fq_codel which, to use an
analogy, when being subject to loads of sh*t, it's better to use a
shovel to get rid of it rather than a teaspoon, I started having a nose
deeper into cake than I've ever gone before.  I was also interested to
note that one of Dave's recent tests where cake was using lots of CPU
but apparently cake wasn't getting into its own 'buffer full, discard at
enqueue' mode.  That sort of suggests the dequeue process was the thing
using all the CPU, possibly starving the process generating packets so
the buffer never filled.

So, in the context of I'm an ignorant buffoon, I'm wondering what I'm
misunderstanding from the following extract of code: codel5.h, line 358

        if (!skb) {
                vars->dropping = false;
                return skb;
        }
        drop = codel_should_drop(skb, sch, vars, p, now, overloaded);
        if (vars->dropping) {
                if (!drop) {
                        /* sojourn time below target - leave dropping
state */
                        vars->dropping = false;
                } else if (now >= vars->drop_next) {
                        /* It's time for the next drop. Drop the current
                         * packet and dequeue the next. The dequeue might
                         * take us out of dropping state.
                         * If not, schedule the next drop.
                         * A large backlog might result in drop rates so
high
                         * that the next drop should happen now,
                         * hence the while loop.
                         */

                        /* saturating increment */
                        vars->count++;
                        if (!vars->count)
                                vars->count--;

                        codel_Newton_step(vars);
                        vars->drop_next = codel_control_law(vars->drop_next,
                                                            p->interval,
                                                           
vars->rec_inv_sqrt);
                        do {
                                if (INET_ECN_set_ce(skb)) {
                                        vars->ecn_mark++;
                                        /* and schedule the next drop */
                                        vars->drop_next = codel_control_law(
                                                vars->drop_next,
p->interval,
                                                vars->rec_inv_sqrt);
                                        goto end;
                                }
                                qdisc_drop(skb, sch);
                                vars->drop_count++;
                                skb = custom_dequeue(vars, sch);
                                if (skb && !codel_should_drop(skb, sch,
vars,
                                                              p, now,
overloaded)) {
                                        /* leave dropping state */
                                        vars->dropping = false;
                                } else {
                                        /* schedule the next drop */
                                        vars->drop_next = codel_control_law(
                                                vars->drop_next,
p->interval,
                                                vars->rec_inv_sqrt);
                                }
                        } while (skb && vars->dropping && now >=
                                 vars->drop_next);

                        /* Mark the packet regardless */
                        if (skb && INET_ECN_set_ce(skb))
                                vars->ecn_mark++;
                }

In essence my (mis)understanding of this code is something like: We've
got here because we've been dropping and codel is telling is to continue
to drop.  With that decided we enter a do..while, the first thing to
happen is to ECN mark and let that marked packet escape to send the
signal.  Otherwise we appear to iterate around the loop.  So here's the
nub of my question: the INET_ECN_set_ce is done on every iteration of
that loop...with its potential early escape..do we escape on every
iteration?  Do we need to twiddle the ECN bits on every packet that
we're about to drop?  And we seem to mark the packet on exit of the loop
anyway.

I'm confused but almost certainly because I'm an idiot.

Kevin



[-- Attachment #2: S/MIME Cryptographic Signature --]
[-- Type: application/pkcs7-signature, Size: 4816 bytes --]

^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: [Cake] cake, codel5.h, ecn marking & dropping. Confused
  2016-05-04  9:57 [Cake] cake, codel5.h, ecn marking & dropping. Confused Kevin Darbyshire-Bryant
@ 2016-05-04 11:41 ` Jonathan Morton
  2016-05-04 12:07   ` Kevin Darbyshire-Bryant
  0 siblings, 1 reply; 3+ messages in thread
From: Jonathan Morton @ 2016-05-04 11:41 UTC (permalink / raw)
  To: Kevin Darbyshire-Bryant; +Cc: cake


> On 4 May, 2016, at 12:57, Kevin Darbyshire-Bryant <kevin@darbyshire-bryant.me.uk> wrote:
> 
> In essence my (mis)understanding of this code is something like: We've
> got here because we've been dropping and codel is telling is to continue
> to drop.  With that decided we enter a do..while, the first thing to
> happen is to ECN mark and let that marked packet escape to send the
> signal.  Otherwise we appear to iterate around the loop.  So here's the
> nub of my question: the INET_ECN_set_ce is done on every iteration of
> that loop...with its potential early escape..do we escape on every
> iteration?  Do we need to twiddle the ECN bits on every packet that
> we're about to drop?  And we seem to mark the packet on exit of the loop
> anyway.

It’s rather oddly structured code, to be sure.

The vital clue for you may be that you can only set CE on an IPv{4,6} packet which already has something *other* than Not-ECT set; it’s impossible for non-IP packets, and not ECN compliant for Not-ECT IP packets.  So INET_ECN_set_ce() returns true only when it succeeds.

On a UDP flood stream, typically Not-ECT is set, so the early-out never triggers.  Instead Codel drops a packet, schedules the next drop, and checks whether the next drop schedule has already been reached (which can happen for high drop rates and/or slow transmission rates).

It then attempts to set CE on the first packet transmitted after a drop sequence, just in case it was a mixed ECT/Not-ECT stream; strenuous efforts to get the congestion signal heard as early as possible.  This is more likely when flow isolation isn’t in use, or when it is per-host instead of per-flow.  That’s also why the first attempt to set CE is within the drop loop.

 - Jonathan Morton


^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: [Cake] cake, codel5.h, ecn marking & dropping. Confused
  2016-05-04 11:41 ` Jonathan Morton
@ 2016-05-04 12:07   ` Kevin Darbyshire-Bryant
  0 siblings, 0 replies; 3+ messages in thread
From: Kevin Darbyshire-Bryant @ 2016-05-04 12:07 UTC (permalink / raw)
  To: Jonathan Morton; +Cc: cake

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



On 04/05/16 12:41, Jonathan Morton wrote:
>> On 4 May, 2016, at 12:57, Kevin Darbyshire-Bryant <kevin@darbyshire-bryant.me.uk> wrote:
>>
>> In essence my (mis)understanding of this code is something like: We've
>> got here because we've been dropping and codel is telling is to continue
>> to drop.  With that decided we enter a do..while, the first thing to
>> happen is to ECN mark and let that marked packet escape to send the
>> signal.  Otherwise we appear to iterate around the loop.  So here's the
>> nub of my question: the INET_ECN_set_ce is done on every iteration of
>> that loop...with its potential early escape..do we escape on every
>> iteration?  Do we need to twiddle the ECN bits on every packet that
>> we're about to drop?  And we seem to mark the packet on exit of the loop
>> anyway.
> It’s rather oddly structured code, to be sure.
>
> The vital clue for you may be that you can only set CE on an IPv{4,6} packet which already has something *other* than Not-ECT set; it’s impossible for non-IP packets, and not ECN compliant for Not-ECT IP packets.  So INET_ECN_set_ce() returns true only when it succeeds.
>
> On a UDP flood stream, typically Not-ECT is set, so the early-out never triggers.  Instead Codel drops a packet, schedules the next drop, and checks whether the next drop schedule has already been reached (which can happen for high drop rates and/or slow transmission rates).
>
> It then attempts to set CE on the first packet transmitted after a drop sequence, just in case it was a mixed ECT/Not-ECT stream; strenuous efforts to get the congestion signal heard as early as possible.  This is more likely when flow isolation isn’t in use, or when it is per-host instead of per-flow.  That’s also why the first attempt to set CE is within the drop loop.
>
>  - Jonathan Morton
>
Thanks Jonathan.  Appreciate the time taken for the explanation.  Much
happier :-)

Kevin


[-- Attachment #2: S/MIME Cryptographic Signature --]
[-- Type: application/pkcs7-signature, Size: 4816 bytes --]

^ permalink raw reply	[flat|nested] 3+ messages in thread

end of thread, other threads:[~2016-05-04 12:07 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-05-04  9:57 [Cake] cake, codel5.h, ecn marking & dropping. Confused Kevin Darbyshire-Bryant
2016-05-04 11:41 ` Jonathan Morton
2016-05-04 12:07   ` Kevin Darbyshire-Bryant

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox