Cake - FQ_codel the next generation
 help / color / mirror / Atom feed
* [Cake] cake dual hash for dualdst, dualsrc
@ 2015-12-21 14:57 Dave Taht
  2015-12-21 15:05 ` Jonathan Morton
                   ` (3 more replies)
  0 siblings, 4 replies; 6+ messages in thread
From: Dave Taht @ 2015-12-21 14:57 UTC (permalink / raw)
  To: cake

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

^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: [Cake] cake dual hash for dualdst, dualsrc
  2015-12-21 14:57 [Cake] cake dual hash for dualdst, dualsrc Dave Taht
@ 2015-12-21 15:05 ` Jonathan Morton
       [not found]   ` <877fk7lts4.fsf@toke.dk>
  2015-12-21 15:06 ` Loganaden Velvindron
                   ` (2 subsequent siblings)
  3 siblings, 1 reply; 6+ messages in thread
From: Jonathan Morton @ 2015-12-21 15:05 UTC (permalink / raw)
  To: Dave Taht; +Cc: cake


> 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


^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: [Cake] cake dual hash for dualdst, dualsrc
  2015-12-21 14:57 [Cake] cake dual hash for dualdst, dualsrc Dave Taht
  2015-12-21 15:05 ` Jonathan Morton
@ 2015-12-21 15:06 ` Loganaden Velvindron
  2015-12-21 15:54 ` moeller0
  2015-12-22 12:29 ` Dave Taht
  3 siblings, 0 replies; 6+ messages in thread
From: Loganaden Velvindron @ 2015-12-21 15:06 UTC (permalink / raw)
  To: Dave Taht; +Cc: cake

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 ?

^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: [Cake] cake dual hash for dualdst, dualsrc
  2015-12-21 14:57 [Cake] cake dual hash for dualdst, dualsrc Dave Taht
  2015-12-21 15:05 ` Jonathan Morton
  2015-12-21 15:06 ` Loganaden Velvindron
@ 2015-12-21 15:54 ` moeller0
  2015-12-22 12:29 ` Dave Taht
  3 siblings, 0 replies; 6+ messages in thread
From: moeller0 @ 2015-12-21 15:54 UTC (permalink / raw)
  To: Dave Täht, Toke Høiland-Jørgensen; +Cc: cake

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


^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: [Cake] cake dual hash for dualdst, dualsrc
       [not found]   ` <877fk7lts4.fsf@toke.dk>
@ 2015-12-21 16:06     ` Jonathan Morton
  0 siblings, 0 replies; 6+ messages in thread
From: Jonathan Morton @ 2015-12-21 16:06 UTC (permalink / raw)
  To: Toke Høiland-Jørgensen; +Cc: Dave Taht, cake


> 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


^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: [Cake] cake dual hash for dualdst, dualsrc
  2015-12-21 14:57 [Cake] cake dual hash for dualdst, dualsrc Dave Taht
                   ` (2 preceding siblings ...)
  2015-12-21 15:54 ` moeller0
@ 2015-12-22 12:29 ` Dave Taht
  3 siblings, 0 replies; 6+ messages in thread
From: Dave Taht @ 2015-12-22 12:29 UTC (permalink / raw)
  To: cake, Kevin Darbyshire-Bryant

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.

^ permalink raw reply	[flat|nested] 6+ messages in thread

end of thread, other threads:[~2015-12-22 12:29 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-12-21 14:57 [Cake] cake dual hash for dualdst, dualsrc Dave Taht
2015-12-21 15:05 ` Jonathan Morton
     [not found]   ` <877fk7lts4.fsf@toke.dk>
2015-12-21 16:06     ` Jonathan Morton
2015-12-21 15:06 ` Loganaden Velvindron
2015-12-21 15:54 ` moeller0
2015-12-22 12:29 ` Dave Taht

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox