[Codel] drop state short-circuit...

[Codel] drop state short-circuit...

[Jeff Weeks]

Hello,

I originally posted this in the aqm list; re-posted to this, more appropriate, list:

There exists a short-circuit into a "deeper" drop state if we were previously and recently in a drop state.  I understand the need for this, but I'm curious where the '16' came from?  How was this decided upon?

For example, here's the ns3 implementation:

          /*
           * if min went above target close to when we last went below it
           * assume that the drop rate that controlled the queue on the
           * last cycle is a good starting point to control it now.
           */
          int delta = m_count - m_lastCount;
          if (delta > 1 && CoDelTimeBefore (now - m_dropNext, 16 * Time2CoDel (m_interval)))
          {
            m_count = delta;
            NewtonStep ();
          }

If I read this correctly, it says;

If we have previously dropped for more than one interval, and have re-entered the drop state in less then 16 intervals from the previous drop state, then short circuit count to the delta... but why 16 intervals?

--Jeff

Re: [Codel] drop state short-circuit...

[Jonathan Morton]

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

The logic is that if the stored count was effectively controlling the
queue, we want to keep using that value if the network is still under
load.  If 16 intervals (1.6 seconds) pass without re-entering drop state,
we can assume the link is no longer saturated (by this flow) and reset
count.

I think the value 16 itself is mostly arbitrary.

I'm a bit skeptical of the way count is saved and restored in the reference
versions - it's hard to follow.  Cake's version explicitly keeps the old
value, but halves it, allowing it to grow back to its original value if
required.  It would also be reasonable to scale the backoff with time,
rather than thresholding it.

- Jonathan Morton

[-- Attachment #2: Type: text/html, Size: 774 bytes --]

Re: [Codel] drop state short-circuit...

[Jeff Weeks]

Thanks!

I'm a bit skeptical of 'count' usage in general, yes.

Say the codel algorithm is managing a large queue, using the default parameters.

That queue could fill, and codel would enter the drop state, and we'd then start dropping packets at 100ms, 70ms, 57ms, 50ms, etc... (i.e., 100/sqrt(count)).

If the queue size is reasonable, this converges quickly on the correct drop rate.

However, if the queue is larger, it takes considerably longer to reach the correct drop rate.

I has previously (perhaps incorrectly) thought that the queue size becomes somewhat irrelevant when using codel, as the queue is effectively managed by inspecting packet latencies, rather than blindly queuing and dequeuing, but that's not entirely true, it seems, as there's no limit placed on the enqueue operation.

In other words, given a high enough input rate, and a large enough queue, codel will still output packets considerably beyond the target ms, no?

Put another way -- if the codel algorithm starts in a heavily congested pipe, it will take many seconds before it can adjust to a 1ms interval (count would have to rise to 10,000).  While adjusting, it's very likely to output many packets with high latencies.

Is this a concern for the algorithm?

--Jeff


________________________________
From: Jonathan Morton [chromatix99@gmail.com]
Sent: Tuesday, August 11, 2015 1:35 PM
To: Jeff Weeks
Cc: codel@lists.bufferbloat.net
Subject: Re: [Codel] drop state short-circuit...


The logic is that if the stored count was effectively controlling the queue, we want to keep using that value if the network is still under load.  If 16 intervals (1.6 seconds) pass without re-entering drop state, we can assume the link is no longer saturated (by this flow) and reset count.

I think the value 16 itself is mostly arbitrary.

I'm a bit skeptical of the way count is saved and restored in the reference versions - it's hard to follow.  Cake's version explicitly keeps the old value, but halves it, allowing it to grow back to its original value if required.  It would also be reasonable to scale the backoff with time, rather than thresholding it.

- Jonathan Morton

Re: [Codel] drop state short-circuit...

[Jonathan Morton]

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

That would imply an unresponsive flow (or a large aggregation of flows in
one queue, which would require a high drop rate to respond).

Indeed, the Codel algorithm in itself doesn't guarantee any latency bound.
Only a hard limit on queue length can do that (or forcibly dropping packets
with sojourn times above the limit).  Practical qdisc implementations do
have such mechanisms.

Flow isolation helps in such circumstances, especially if the qdisc drops
from the longest queue on enqueue overflow.

- Jonathan Morton

[-- Attachment #2: Type: text/html, Size: 603 bytes --]