Re: [Codel] [Cake] openwrt build available with latest cake and fq_pie

Re: [Codel] [Cake] openwrt build available with latest cake and fq_pie

[Dave Taht]

adding in codel list. I do think we need a better understanding from
observing flow behavior in the fq case than we have.

certainly we had a case in the early days where count increased without bound.

On Sun, Jun 14, 2015 at 10:19 AM, Jonathan Morton <chromatix99@gmail.com> wrote:
>
>> On 14 Jun, 2015, at 19:09, Dave Taht <dave.taht@gmail.com> wrote:
>>
>> I do pretty strongly think count - 1 is the rightest thing still.
>
> I really don’t.  Here’s why:
>
> Every time Codel triggers the dropping state, it will mark or drop at least one packet, and increment count by that number.  With count decremented only by 1 on recovery, it will effectively remain constant *if*, by some miracle, the queue empties before the second signal was sent; it cannot decrease between episodes unless it resets or wraps.

It aint a miracle, it is hopefully within an rtt.

> With count decremented by 2 on recovery, it is possible for count to decrease slowly in that ideal case, but it’ll remain constant if two signals were sent before the queue cleared, and - this is important - it will always continue to increase if three or more signals are sent before the queue empties.

quibble: queue's latency falls below the target delay.

>
> If one signal did suffice to clear the queue, then logically the value of count was irrelevant to that congestion episode and shouldn’t be preserved.  This is true regardless of the actual reason the queue emptied.
>
> The problem arises when more than one signal is sent before the queue is observed to clear.  This could be a sign of several distinct network conditions:
>
> - The RTT is longer than interval / sqrt(count), in which case one signal would still have been sufficient, and the ideal value of count is less than its current value.  On non-ECN TCP flows, this results in more retransmissions than necessary.
>
> - The RTT is much shorter than interval / sqrt(count), so the congestion window is recovering faster than the signalling rate, and count needs to increase to compensate for that.
>
> - There is more than one flow sharing the queue, and it was necessary to signal to all of them, in which case count should reflect the flow count and be capable of adjusting both up and down.
>
> - The flow is unresponsive, so count should adjust to provide the correct dropping rate, and RTT is irrelevant.  With default parameters, the maximum drop rate is presently 25600 pps (which would cause count to wrap after a few seconds, until I put in the saturating arithmetic).

There was some good discussion of things on another list recently
(can't remember which) at 100Gig rates.

>
> How does Codel distinguish between those cases?  It can’t - at least, not reliably.  So it must allow count to increase until the queue is observed to be controlled, and then decrease count by some other means to cover the case where it was overestimated.  For this latter phase, count-2 is obviously insufficient to cope with the case where count is actually correct, but more than one signal per episode is required.
>
> *That* is why I put in count/2.

When resuming the drop phase of codel, it is almost *already* too late
to catch that burst incurring the latency.

Sometimes I think we need to do away with the count idea and measure
slopes of curves instead, and "harmonics".

>A multiplicative decrease allows count to stabilise at some value which adequately controls the queue, rather than continuously increasing past it.  For the typical cake case where there is one flow per Codel instance and the RTT is of Internet scale, this should work at least as well as an additive decrease; in particular, the behaviour is identical where count ended at 2, 3 or 4 (it can’t end at 1).

> Of course, hard data would help to evaluate it, but I do think it’s theoretically sound.

adding in codel list.

The brief bits of data I got so far show it failing to control queue,
building over time.

>  - Jonathan Morton
>



-- 
Dave Täht
What will it take to vastly improve wifi for everyone?
https://plus.google.com/u/0/explore/makewififast

Re: [Codel] [Cake] openwrt build available with latest cake and fq_pie

[Jonathan Morton]

> On 14 Jun, 2015, at 20:38, Dave Taht <dave.taht@gmail.com> wrote:
> 
>> Every time Codel triggers the dropping state, it will mark or drop at least one packet, and increment count by that number.  With count decremented only by 1 on recovery, it will effectively remain constant *if*, by some miracle, the queue empties before the second signal was sent; it cannot decrease between episodes unless it resets or wraps.
> 
> It aint a miracle, it is hopefully within an rtt.

No, it is *at minimum* one RTT.  It takes that long for the congestion signal to reach the receiver, be reflected back to the sender, the sender’s reaction to *begin to* appear at the queue.  Then the queue *starts* to empty, if the signal is what’s required to make it do so.

> When resuming the drop phase of codel, it is almost *already* too late
> to catch that burst incurring the latency.

Yes, but that’s what FQ is for.  And ELR, if we ever get that properly started.

> Sometimes I think we need to do away with the count idea and measure
> slopes of curves instead, and "harmonics”.


> Is there any reason why the decrease couldn't be some sort of decay?
> I.e. a function of how long ago the drop state was exited?

Such things are theoretically possible, but require further thought to determine how best to do them.

 - Jonathan Morton

Re: [Codel] [Cake] openwrt build available with latest cake and fq_pie

[Dave Taht]

On Sun, Jun 14, 2015 at 11:07 AM, Jonathan Morton <chromatix99@gmail.com> wrote:
>
>> On 14 Jun, 2015, at 20:38, Dave Taht <dave.taht@gmail.com> wrote:
>>
>>> Every time Codel triggers the dropping state, it will mark or drop at least one packet, and increment count by that number.  With count decremented only by 1 on recovery, it will effectively remain constant *if*, by some miracle, the queue empties before the second signal was sent; it cannot decrease between episodes unless it resets or wraps.
>>
>> It aint a miracle, it is hopefully within an rtt.
>
> No, it is *at minimum* one RTT.  It takes that long for the congestion signal to reach the receiver, be reflected back to the sender, the sender’s reaction to *begin to* appear at the queue.  Then the queue *starts* to empty, if the signal is what’s required to make it do so.

Flows, btw, do end quite rapidly in the real world. What was it, 95%
of all web flows ended inside of IW10? Dropping a packet at the tail
end of an ending flow forces a retransmit. Far too much of our testing
and thinking is oriented to full rate flows.

That is what I meant by "hopefully". I would like to build a test that
consisted primarily of short flows, one that hopefully looked more
like normal traffic.

>> When resuming the drop phase of codel, it is almost *already* too late
>> to catch that burst incurring the latency.
>
> Yes, but that’s what FQ is for.  And ELR, if we ever get that properly started.
>
>> Sometimes I think we need to do away with the count idea and measure
>> slopes of curves instead, and "harmonics”.
>
>
>> Is there any reason why the decrease couldn't be some sort of decay?
>> I.e. a function of how long ago the drop state was exited?
>
> Such things are theoretically possible, but require further thought to determine how best to do them.
>
>  - Jonathan Morton
>



-- 
Dave Täht
What will it take to vastly improve wifi for everyone?
https://plus.google.com/u/0/explore/makewififast

Re: [Codel] [Cake] openwrt build available with latest cake and fq_pie

[Jonathan Morton]

> On 14 Jun, 2015, at 21:24, Dave Taht <dave.taht@gmail.com> wrote:
> 
> Flows, btw, do end quite rapidly in the real world. What was it, 95%
> of all web flows ended inside of IW10?

It might be worth thinking about how heavily loaded a network needs to be for Codel to trigger on such a flow.  However, with perfect flow isolation, count will start at 1, making it less relevant to the present thread.

Cake will start triggering on a instantly-arrived burst (call it a packet salvo) after 35ms.  Thus, a ten-packet burst will not trigger provided at least 4.5 Mbps is available to that flow.  However, on many links that is still a tall order, since if the flows really are that short, there are probably lots of them in parallel.

A paced burst is much more friendly.  At a 100ms RTT, IW10 could be delivered at 100pps (1.5 Mbps), extending the range of link speeds on which congestion signalling will not occur by at least 3x (and generally more).  Since this greatly reduces the risk of packet loss, it might actually reduce the average time that the sender needs to maintain the connection’s buffers, despite the deliberate 1-RTT delay introduced.

 - Jonathan Morton

Re: [Codel] [Cake] openwrt build available with latest cake and fq_pie

[Dave Taht]

On Sun, Jun 14, 2015 at 12:35 PM, Jonathan Morton <chromatix99@gmail.com> wrote:
>
>> On 14 Jun, 2015, at 21:24, Dave Taht <dave.taht@gmail.com> wrote:
>>
>> Flows, btw, do end quite rapidly in the real world. What was it, 95%
>> of all web flows ended inside of IW10?
>
> It might be worth thinking about how heavily loaded a network needs to be for Codel to trigger on such a flow.  However, with perfect flow isolation, count will start at 1, making it less relevant to the present thread.
>
> Cake will start triggering on a instantly-arrived burst (call it a packet salvo) after 35ms.  Thus, a ten-packet burst will not trigger provided at least 4.5 Mbps is available to that flow.  However, on many links that is still a tall order, since if the flows really are that short, there are probably lots of them in parallel.
>
> A paced burst is much more friendly.  At a 100ms RTT, IW10 could be delivered at 100pps (1.5 Mbps), extending the range of link speeds on which congestion signalling will not occur by at least 3x (and generally more).  Since this greatly reduces the risk of packet loss, it might actually reduce the average time that the sender needs to maintain the connection’s buffers, despite the deliberate 1-RTT delay introduced.

Data point: Quic is presently 10 packet burst, 22 packets paced. Not
that I like it.

>  - Jonathan Morton
>



-- 
Dave Täht
What will it take to vastly improve wifi for everyone?
https://plus.google.com/u/0/explore/makewififast