[Cake] cake dual hash for dualdst, dualsrc

[Cake] cake dual hash for dualdst, dualsrc

[Dave Taht]

you begged for it...
you thought it would rock the universe...
you thought it would be a killer feature...
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!

well, here it is, dual mode in the new, improved, "kitchen sink"
version of cake! Forked from the main cake! yet again! Now available
from

https://github.com/dtaht/ks

with support for the dualdst, dualsrc modes in

https://github.com/dtaht/tc-adv

but wait, that's not all!

We've got benchmarks showing dualsrc or dualdst being totally
comparable to rrul and rrul_be (which only use 8 flows) at 30mbits!

http://snapon.cs.kau.se/~d/dual/

Along WITH benchmarks showing lurid misbehavior (250+ms delay) at 50
flows[1], which certainly is an disincentive to have a lot of flows
per host, to be sure!

http://snapon.cs.kau.se/~d/dual/dualnevergetsqueuecontrolled.png
Why did we take time out from fixing the mail server to do this?

FOR SCIENCE!


[1] (it could just be a bug, and this IS a short RTT. but I've always
said that flipping codel state around queues randomly was a bad
idea[2]. A queue will empty, and then get reused by something else....
eyeballs wanted. figuring out the hashy bits made my head hurt)

[2] flowblind still stayed stuck at 40ms delay under this workload at
this bandwidth on this version of codel in cake.

http://snapon.cs.kau.se/~d/dual/flowblind40ms_50flows.png




Dave Täht
Let's go make home routers and wifi faster! With better software!
https://www.gofundme.com/savewifi

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

[Jonathan Morton]

> On 21 Dec, 2015, at 16:57, Dave Taht <dave.taht@gmail.com> wrote:
> 
> you begged for it...
> you thought it would rock the universe...
> you thought it would be a killer feature…

Yes...

> 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.

 - Jonathan Morton

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

[Jonathan Morton]

> 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

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

[Loganaden Velvindron]

On Mon, Dec 21, 2015 at 2:57 PM, Dave Taht <dave.taht@gmail.com> wrote:
> you begged for it...
> you thought it would rock the universe...
> you thought it would be a killer feature...
> 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!
>
> well, here it is, dual mode in the new, improved, "kitchen sink"
> version of cake! Forked from the main cake! yet again! Now available
> from
>
> https://github.com/dtaht/ks
>
> with support for the dualdst, dualsrc modes in
>
> https://github.com/dtaht/tc-adv
>
> but wait, that's not all!
>

A new mailing list as well :p ?

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

[moeller0]

Hi Dave,

> On Dec 21, 2015, at 15:57 , Dave Taht <dave.taht@gmail.com> wrote:
> 
> you begged for it...
> you thought it would rock the universe...
> you thought it would be a killer feature...
> 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!
> 
> well, here it is, dual mode in the new, improved, "kitchen sink"
> version of cake! Forked from the main cake! yet again! Now available
> from
> 
> https://github.com/dtaht/ks
> 
> with support for the dualdst, dualsrc modes in
> 
> https://github.com/dtaht/tc-adv
> 
> but wait, that's not all!
> 
> We've got benchmarks showing dualsrc or dualdst being totally
> comparable to rrul and rrul_be (which only use 8 flows) at 30mbits!



> 
> http://snapon.cs.kau.se/~d/dual/

	Trying to load these into flent lead to python folding down, with plenty of the following:

KeyError: 'rrul_50_down'
Traceback (most recent call last):
  File "/Users/Shared/samba/privat/MOEWE/techno_kram/CODE/flent/flent/gui.py", line 999, in flags
    self.active_widget.results.meta("NAME") != self.open_files[idx.row()].meta("NAME"))\
  File "/Users/Shared/samba/privat/MOEWE/techno_kram/CODE/flent/flent/gui.py", line 847, in __getitem__
    v = self._store[k]
KeyError: 'rrul_50_down'
Traceback (most recent call last):
  File "/Users/Shared/samba/privat/MOEWE/techno_kram/CODE/flent/flent/gui.py", line 1046, in data
    if self.is_primary(idx.row()) and font is not None:
  File "/Users/Shared/samba/privat/MOEWE/techno_kram/CODE/flent/flent/gui.py", line 964, in is_primary
    return self.active_widget.results == self.open_files[idx]
  File "/Users/Shared/samba/privat/MOEWE/techno_kram/CODE/flent/flent/gui.py", line 847, in __getitem__
    v = self._store[k]
KeyError: 'rrul_50_down'
Python(28548,0x7fff791ca300) malloc: *** error for object 0x7fc42c8cee28: incorrect checksum for freed object - object was probably modified after being freed.
*** set a breakpoint in malloc_error_break to debug
Abort trap: 6


This is with most recent flent on machos 10.10.5 with python 3.5, so I can not really see the 50 to 1 “fun"… Question, what should I see? The PNG only shows two lines for upload and download, where are the other 49 flows hiding? Or does the test show the results of a 50 flows test between a different set of machines on a simple one up one down test in a different pair of IPs that all share the cake shaper? I just want to understand how the perfect graph would look like…

For all my whining Dave , no that I see your constant diffserv arrays I actually believe, while tedious to fill these are quite elegant, and precomputing them probably is fine. (Looking at the in decimal is a fun after having tried hard to convince myself that DSCPs are bit patterns, I like the freedom the decimal view entails; since none of the existing DSCP schemes fit too well for a home net, we might as well come up with something fresh and easier to understand)

Best Regards
	Sebastian


> 
> Along WITH benchmarks showing lurid misbehavior (250+ms delay) at 50
> flows[1], which certainly is an disincentive to have a lot of flows
> per host, to be sure!
> 
> http://snapon.cs.kau.se/~d/dual/dualnevergetsqueuecontrolled.png
> Why did we take time out from fixing the mail server to do this?
> 
> FOR SCIENCE!
> 
> 
> [1] (it could just be a bug, and this IS a short RTT. but I've always
> said that flipping codel state around queues randomly was a bad
> idea[2]. A queue will empty, and then get reused by something else....
> eyeballs wanted. figuring out the hashy bits made my head hurt)
> 
> [2] flowblind still stayed stuck at 40ms delay under this workload at
> this bandwidth on this version of codel in cake.
> 
> http://snapon.cs.kau.se/~d/dual/flowblind40ms_50flows.png
> 
> 
> 
> 
> Dave Täht
> Let's go make home routers and wifi faster! With better software!
> https://www.gofundme.com/savewifi
> _______________________________________________
> Cake mailing list
> Cake@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/cake

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

[Dave Taht]

It turns out that I actually proved something slightly different -
cake's current codel implementation doesn't work worth a damn.

Which I already "knew" from other test runs against other data sets.

Toke's 2mbit/384k dataset arrived this morning, more or less making
that obvious.