On Mar 30, 2015, at 19:28 , Jonathan Morton <[email protected]> wrote:
> I made a lot of progress over the weekend, and got cake3 running on a
> sacrificial box today. No crashes yet!
>
> The set-associative hashing is in, currently hard-coded to 8-way, which
> should be more than adequate for typical home workloads (especially if
> BitTorrent is marked as background). I’m now adding statistics outputs so
> that we can all see how well it works under real loads, distinguishing
> between direct hits (the fast path, where the hash points directly to a
> correctly allocated queue), indirect hits (where a search through the set
> locates an allocated queue), misses (where an empty queue was allocated) and
> collisions (where all the queues were already occupied by other flows). Note
> that “allocation” in this case simply means updating the tag on the queue to
> match the packet, not allocating memory. These statistics should help with
> tuning the number of flow queues in each class.
>
> The new Diffserv logic is also in and apparently working well. I’m able to
> observe both the priority-balanced and bandwidth-balanced behaviours under
> appropriate circumstances. It is, however, fairly sensitive to the baseline
> quantum value from which the outer DRR weights are derived. Setting it to
> the MTU lets the high-priority classes burst too much, temporarily starving
> the lower classes. It seems to work a lot better using 256 as a baseline,
> but I hope the overhead of going around the DRR loop several times per packet
> isn’t too high. It might be sane to vary the baseline quantum based on the
> bandwidth setting, but we can experiment with that later.
>
>> We keep track of how many bytes of system memory are consumed by a packet in
>> 'skb->truesize'.
>
> The buffer-occupancy queue limit is in, using the field quoted above.
> Previously, it would just count packets. As with previous versions of cake
> (and fq_codel), it checks the limit immediately after enqueuing each packet,
> and drops one packet from the head of the longest queue (by byte count) if
> it’s violated.
Does this mean the largest size the queue actually occupies is limit
plus the last packet’s true size temporarily? What about the case a full MTU
packet comes in while the eligible packet at the head of the longest queue is
say 64 byte?
>
> Calculating the appropriate size to use here was an interesting problem. I
> start by estimating the BDP (from the shaper bandwidth and the Codel
> interval), quadrupling that and enforcing a lower limit of 64KB. If it’s set
> to “unlimited bandwidth”, I set the size to an arbitrary 1MB. Then I look at
> the packet limit, multiply that by the MTU and clamp the resulting size down
> to that - providing a straightforward mechanism to set a limit on memory
> usage.
>
> This all comes with a *fifth* almost-copy of codel.h, which incorporates the
> more efficient dequeue callback from codel4.h, but puts back the separate
> treatment of interval and target. Cake auto-tunes both of them to related
> values, but the relationship isn’t as simple as scaling one from the other,
> and I’m not comfortable with the mental contortions involved in the new
> reasoning.
I thought the main argument was, that interval needs to be roughly in
the right range and target is supposed to be between 5 to 10 percent of
interval.
>
> I also added a lookup table for the first few inverse square roots, because I
> found (using a spreadsheet) that these are very inaccurate if you only do one
> Newton iteration on them - something like 1.0, 0.500, 0.563, 0.488 instead of
> 1.0, 0.707, 0.577, 0.500. Nebulous problems with “insufficiently tight
> control” might possibly be traced to this. With the first fifteen entries
> calculated up-front using four iterations and stored, accuracy is vastly
> improved and, in practice, almost all square-root calculations will now
> reduce to a simple table lookup. The memory cost is trivial, and Newton is
> good enough for exceptionally large drop counts.
>
> Along with the hashing statistics, I’m also adding three measures of latency
> to replace the one from the first version. This no longer relies on data
> provided by Codel (so there’s no space penalty per flow for collecting it,
> and the inner loop in the stats dump is also eliminated), but performs the
> necessary calculation just after dequeuing each packet, storing the
> aggregated values per class instead of per flow. Each measure is an EWMA
> (using optimised weights which reduce to shifts and adds), but two of them
> are biased - one towards high latencies (so it’ll mostly track the fattest
> flows), and one towards low latencies (so it’ll mostly track sparse flows).
>
> Still lots of little things to do…
>
> - Jonathan Morton
Wahoo, this sounds great. I cant’t wait to do a “test-drive” with this ;),
(once you are looking for testers let me know)
Best Regards
Sebastian
_______________________________________________
Codel mailing list
[email protected]
https://lists.bufferbloat.net/listinfo/codel
