Re: [Cake] cake dual hash for dualdst, dualsrc

[Jonathan Morton <chromatix99@gmail.com>]

> On 21 Dec, 2015, at 17:12, Toke Høiland-Jørgensen <toke@toke.dk> wrote:
> 
> Jonathan Morton <chromatix99@gmail.com> writes:
> 
>>> you thought that isolating individual machines into roughly 8 queues
>>> each would help defeat bittorrent and other forms of too-many-flow
>>> abuse... and that you'd get some of the benefits of fq for everyone
>>> and that codel could correctly compensate for it!
>> 
>> Um, no.  That isn’t what I had in mind at all.
>> 
>> I’m not at all surprised that your version doesn’t work.
> 
> Do explain; or maybe show us the code, even?

The scheme described above stops working as well as standard flow-isolation just as soon as any single host (or host pair) has more than eight flows.  Note that the ordinary RRUL test employs *thirteen* flows, and the only reason the results still look good is because most of them aren’t bulk, so half the queues do double or triple duty.  The 50:1 test completely destroys it, for obvious reasons, whereas this was something that Cake did comparatively well at.

Additionally, hosts can still get up to an 8x throughput advantage over another using multiple flows.  If both source and destination hosts are considered in the host hash, sharding gains further advantages, evading the dual-isolation measure entirely.

This is not progress.

An early design I had in mind imposed an explicit two-layer structure, with a DRR structure for hosts, and each host bucket having an independent DRR structure for flows.  This would have both avoided the host-to-host competition by flow count (which was the whole point of dual isolation), and avoided restricting the number of flows each host could use without losing the entire benefit of flow isolation.

However, this still forced the user to choose between source-address or destination-address host isolation, in order to avoid the “sharding” cheat.  So I searched further for a way to treat both addresses equally with the same overall benefit.

What I now have in mind restores primary DRR control to the flow level, but adds per-source and per-destination deficit counters which are indexed to from the flows.  All three deficit counters must be non-negative before the queue will be serviced, making it an *implicit* two-level structure with the upper level in two interlocked branches.  This should work well outside of pathological cases, since our set-associative flow isolation doesn’t often suffer collisions.

The challenge is maintaining the new deficit counters accurately, since we can’t rely on the monotonic sweep behaviour as ordinary DRR does.  That’s what I’m currently trying to focus on.

 - Jonathan Morton