Re: [Cake] Modification of DRR with deficit saving

[Luca Muscariello]

That is a big mountain to climb

On Thu, Jan 4, 2018 at 5:20 PM, Dave Taht  wrote:

>
> Done fixing the home. It's time to fix the rest of the internet. And
> that's not just queue theory but address assignment and routing.
> Here's
> a traceroute from where I sit in Nicaragua at the moment, post cake.
> How to figure out exactly how much NAT is on the path?
>
>
___
Cake mailing list
Cake@lists.bufferbloat.net
https://lists.bufferbloat.net/listinfo/cake

Re: [Cake] Modification of DRR with deficit saving

[Dave Taht]

On Thu, Jan 4, 2018 at 7:53 AM, Luca Muscariello
 wrote:
> Sanity check: the active flow list in Jim's work is very compact
> as it counts only the flows with a packet in the queue.
> So you need to read that paragraph with this in mind. Then you'll agree :)
>
> I have a reasonable proof that what cake is doing is truly sane.
> You just need to compare cake to Jim's monumental work and see that it fits
> in that class.

I agree it does.

> Then you sleep well as I do.

I'd sleep better if I knew at least some of this stuff was actually
making it out into a few vendors head-ends.

> don't pay too much attention to admission control.
> Even if it makes sense to me. In case of overload, i.e. too many flows in
> the system for too long,
> nobody is happy.
> Accepting more flows is making no one happier. The new one included.
> So instead of dropping one random packet, dropping new SYN packets seems
> like the bouncer telling
> you "guys: there is no room left". And it works well in the home.

Yes, SYN rate limiting is the default (and set very low) in nearly
everything. That might be measurable. QUIC is now 7% of internet
traffic.

Done fixing the home. It's time to fix the rest of the internet. And
that's not just queue theory but address assignment and routing.
Here's
a traceroute from where I sit in Nicaragua at the moment, post cake.
How to figure out exactly how much NAT is on the path?


daves-MacBook-Air:Downloads d$ traceroute -n 8.8.8.8

traceroute to 8.8.8.8 (8.8.8.8), 64 hops max, 52 byte packets

 1  192.168.1.1  72.710 ms  2.548 ms  1.639 ms

 2  10.0.0.1  2.384 ms  2.086 ms  2.070 ms

 3  192.168.66.1  18.438 ms  11.606 ms  8.063 ms

 4  165.98.53.209  23.945 ms  13.506 ms  16.446 ms

 5  172.20.1.77  15.788 ms  21.602 ms  7.710 ms

 6  172.20.28.21  10.496 ms  13.440 ms  15.514 ms

 7  172.20.26.77  11.745 ms  9.659 ms  7.834 ms

 8  172.20.0.81  17.636 ms  12.180 ms  20.880 ms

 9  172.20.25.30  52.408 ms  32.566 ms  21.970 ms

10  165.98.53.41  17.654 ms  10.712 ms  15.352 ms

11  84.16.9.155  51.730 ms  64.468 ms  52.894 ms

12  176.52.255.218  50.340 ms  52.045 ms  65.218 ms

13  216.184.112.169


>
>
>
>
>
>
> On Thu, Jan 4, 2018 at 4:42 PM, Dave Taht  wrote:
>>
>> On Thu, Jan 4, 2018 at 7:23 AM, Luca Muscariello
>>  wrote:
>> > I think the closest scheduler to Cake is this one, if I have to compare:
>> >
>> > https://team.inria.fr/rap/files/2013/12/KOR05.pdf
>>
>> Try as I might, at workloads that I've been able to create (I did just
>> add 10GigE capability to my testbed), it's seemingly nearly impossible
>> to have more than a few hundred flows in memory (compared to
>> potentially thousands actually active), and it's unclear how to go
>> about thinking about it sanely.This tends to point to cake's 8 way set
>> associativity as being overkill, but haven't got around to trying
>> higher bandwidths, lower target RTTs, or, as I said, higher
>> bandwidths.
>>
>> 'course, while I disagree with this statement in the paper, and do
>> care a lot about handling overload sanely,
>>
>> "In overload, it is necessary to apply per-flow admission control in
>> order to preserve good performance for admitted flows. Note that no
>> scheduler can avoid drastic performance degradation when offered
>> traffic exceeds capacity. PDRR has the advantage of allowing"
>>
>> I wish I had reasonable proof that what we do in cake is truly sane,
>> or had some curve to apply to flows per the available bandwidth.
>>
>> >
>> > J. Roberts et al. Implicit Service Differentiation using Deficit Round
>> > Robin, In Proc of ITC 2005.
>> >
>> > Luca
>> >
>> >
>> > On Thu, Jan 4, 2018 at 4:01 PM, Jonathan Morton 
>> > wrote:
>> >>
>> >> > On 4 Jan, 2018, at 4:29 pm, Toke Høiland-Jørgensen 
>> >> > wrote:
>> >> >
>> >> > This popped up in my Google Scholar notifications:
>> >> >
>> >> > https://atlas.informatik.uni-tuebingen.de/~menth/papers/Menth18b.pdf
>> >> >
>> >> > Basically, they are proposing to permit a queue to accumulate a
>> >> > larger
>> >> > deficit while empty to allow light users to achieve the same
>> >> > throughput
>> >> > as heavy users (users being an endpoint with potentially multiple
>> >> > flows).
>> >> >
>> >> > Not sure how useful this really is, but it's somewhat related to
>> >> > Cake's
>> >> > src/dst user fairness feature, so may be of interest.
>> >>
>> >> They're trying to solve the same problem as DRR++ does, not the same
>> >> one
>> >> as Triple Isolation does.
>> >>
>> >> As a result, they've basically proposed a bugfix to the original DRR
>> >> (ie.
>> >> you should keep replenishing the deficit until it saturates, even if
>> >> the
>> >> queue is temporarily empty), without gaining the full benefit of DRR++.
>> >>
>> >> Not interesting at all.
>> >>
>> >>  - Jonathan Morton
>> >>
>> >> ___
>> >> Cake mailing list
>> >> 

Re: [Cake] Modification of DRR with deficit saving

[Luca Muscariello]

Sanity check: the active flow list in Jim's work is very compact
as it counts only the flows with a packet in the queue.
So you need to read that paragraph with this in mind. Then you'll agree :)

I have a reasonable proof that what cake is doing is truly sane.
You just need to compare cake to Jim's monumental work and see that it fits
in that class.
Then you sleep well as I do.

don't pay too much attention to admission control.
Even if it makes sense to me. In case of overload, i.e. too many flows in
the system for too long,
nobody is happy.
Accepting more flows is making no one happier. The new one included.
So instead of dropping one random packet, dropping new SYN packets seems
like the bouncer telling
you "guys: there is no room left". And it works well in the home.






On Thu, Jan 4, 2018 at 4:42 PM, Dave Taht  wrote:

> On Thu, Jan 4, 2018 at 7:23 AM, Luca Muscariello
>  wrote:
> > I think the closest scheduler to Cake is this one, if I have to compare:
> >
> > https://team.inria.fr/rap/files/2013/12/KOR05.pdf
>
> Try as I might, at workloads that I've been able to create (I did just
> add 10GigE capability to my testbed), it's seemingly nearly impossible
> to have more than a few hundred flows in memory (compared to
> potentially thousands actually active), and it's unclear how to go
> about thinking about it sanely.This tends to point to cake's 8 way set
> associativity as being overkill, but haven't got around to trying
> higher bandwidths, lower target RTTs, or, as I said, higher
> bandwidths.
>
> 'course, while I disagree with this statement in the paper, and do
> care a lot about handling overload sanely,
>
> "In overload, it is necessary to apply per-flow admission control in
> order to preserve good performance for admitted flows. Note that no
> scheduler can avoid drastic performance degradation when offered
> traffic exceeds capacity. PDRR has the advantage of allowing"
>
> I wish I had reasonable proof that what we do in cake is truly sane,
> or had some curve to apply to flows per the available bandwidth.
>
> >
> > J. Roberts et al. Implicit Service Differentiation using Deficit Round
> > Robin, In Proc of ITC 2005.
> >
> > Luca
> >
> >
> > On Thu, Jan 4, 2018 at 4:01 PM, Jonathan Morton 
> > wrote:
> >>
> >> > On 4 Jan, 2018, at 4:29 pm, Toke Høiland-Jørgensen 
> wrote:
> >> >
> >> > This popped up in my Google Scholar notifications:
> >> >
> >> > https://atlas.informatik.uni-tuebingen.de/~menth/papers/Menth18b.pdf
> >> >
> >> > Basically, they are proposing to permit a queue to accumulate a larger
> >> > deficit while empty to allow light users to achieve the same
> throughput
> >> > as heavy users (users being an endpoint with potentially multiple
> >> > flows).
> >> >
> >> > Not sure how useful this really is, but it's somewhat related to
> Cake's
> >> > src/dst user fairness feature, so may be of interest.
> >>
> >> They're trying to solve the same problem as DRR++ does, not the same one
> >> as Triple Isolation does.
> >>
> >> As a result, they've basically proposed a bugfix to the original DRR
> (ie.
> >> you should keep replenishing the deficit until it saturates, even if the
> >> queue is temporarily empty), without gaining the full benefit of DRR++.
> >>
> >> Not interesting at all.
> >>
> >>  - Jonathan Morton
> >>
> >> ___
> >> Cake mailing list
> >> Cake@lists.bufferbloat.net
> >> https://lists.bufferbloat.net/listinfo/cake
> >
> >
> >
> > ___
> > Cake mailing list
> > Cake@lists.bufferbloat.net
> > https://lists.bufferbloat.net/listinfo/cake
> >
>
>
>
> --
>
> Dave Täht
> CEO, TekLibre, LLC
> http://www.teklibre.com
> Tel: 1-669-226-2619
>
___
Cake mailing list
Cake@lists.bufferbloat.net
https://lists.bufferbloat.net/listinfo/cake

Re: [Cake] Modification of DRR with deficit saving

[Dave Taht]

On Thu, Jan 4, 2018 at 7:23 AM, Luca Muscariello
 wrote:
> I think the closest scheduler to Cake is this one, if I have to compare:
>
> https://team.inria.fr/rap/files/2013/12/KOR05.pdf

Try as I might, at workloads that I've been able to create (I did just
add 10GigE capability to my testbed), it's seemingly nearly impossible
to have more than a few hundred flows in memory (compared to
potentially thousands actually active), and it's unclear how to go
about thinking about it sanely.This tends to point to cake's 8 way set
associativity as being overkill, but haven't got around to trying
higher bandwidths, lower target RTTs, or, as I said, higher
bandwidths.

'course, while I disagree with this statement in the paper, and do
care a lot about handling overload sanely,

"In overload, it is necessary to apply per-flow admission control in
order to preserve good performance for admitted flows. Note that no
scheduler can avoid drastic performance degradation when offered
traffic exceeds capacity. PDRR has the advantage of allowing"

I wish I had reasonable proof that what we do in cake is truly sane,
or had some curve to apply to flows per the available bandwidth.

>
> J. Roberts et al. Implicit Service Differentiation using Deficit Round
> Robin, In Proc of ITC 2005.
>
> Luca
>
>
> On Thu, Jan 4, 2018 at 4:01 PM, Jonathan Morton 
> wrote:
>>
>> > On 4 Jan, 2018, at 4:29 pm, Toke Høiland-Jørgensen  wrote:
>> >
>> > This popped up in my Google Scholar notifications:
>> >
>> > https://atlas.informatik.uni-tuebingen.de/~menth/papers/Menth18b.pdf
>> >
>> > Basically, they are proposing to permit a queue to accumulate a larger
>> > deficit while empty to allow light users to achieve the same throughput
>> > as heavy users (users being an endpoint with potentially multiple
>> > flows).
>> >
>> > Not sure how useful this really is, but it's somewhat related to Cake's
>> > src/dst user fairness feature, so may be of interest.
>>
>> They're trying to solve the same problem as DRR++ does, not the same one
>> as Triple Isolation does.
>>
>> As a result, they've basically proposed a bugfix to the original DRR (ie.
>> you should keep replenishing the deficit until it saturates, even if the
>> queue is temporarily empty), without gaining the full benefit of DRR++.
>>
>> Not interesting at all.
>>
>>  - Jonathan Morton
>>
>> ___
>> Cake mailing list
>> Cake@lists.bufferbloat.net
>> https://lists.bufferbloat.net/listinfo/cake
>
>
>
> ___
> Cake mailing list
> Cake@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/cake
>



-- 

Dave Täht
CEO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-669-226-2619
___
Cake mailing list
Cake@lists.bufferbloat.net
https://lists.bufferbloat.net/listinfo/cake

Re: [Cake] Modification of DRR with deficit saving

[Luca Muscariello]

I think the closest scheduler to Cake is this one, if I have to compare:

https://team.inria.fr/rap/files/2013/12/KOR05.pdf

J. Roberts et al. Implicit Service Differentiation using Deficit Round
Robin, In Proc of ITC 2005.

Luca


On Thu, Jan 4, 2018 at 4:01 PM, Jonathan Morton 
wrote:

> > On 4 Jan, 2018, at 4:29 pm, Toke Høiland-Jørgensen  wrote:
> >
> > This popped up in my Google Scholar notifications:
> >
> > https://atlas.informatik.uni-tuebingen.de/~menth/papers/Menth18b.pdf
> >
> > Basically, they are proposing to permit a queue to accumulate a larger
> > deficit while empty to allow light users to achieve the same throughput
> > as heavy users (users being an endpoint with potentially multiple
> > flows).
> >
> > Not sure how useful this really is, but it's somewhat related to Cake's
> > src/dst user fairness feature, so may be of interest.
>
> They're trying to solve the same problem as DRR++ does, not the same one
> as Triple Isolation does.
>
> As a result, they've basically proposed a bugfix to the original DRR (ie.
> you should keep replenishing the deficit until it saturates, even if the
> queue is temporarily empty), without gaining the full benefit of DRR++.
>
> Not interesting at all.
>
>  - Jonathan Morton
>
> ___
> Cake mailing list
> Cake@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/cake
>
___
Cake mailing list
Cake@lists.bufferbloat.net
https://lists.bufferbloat.net/listinfo/cake

Re: [Cake] Modification of DRR with deficit saving

[Dave Taht]

To this day I regret mis-identifying fq-codel with SFQ in that first talk.

And they ripped the idea of codel out entirely in their evaluation.

"Drop-on-dequeue is inspired by new AQMs like CoDel, but we pursue a
very simple approach. A packet is dropped if it is older than a
con gurable delay thresholdTD. This method limits the packet delay
toTD and removes packets from the queue in case of congestion.
Nevertheless, the bu er can over ow under certain conditions. To avoid
that, we postulated a su ciently large bu er and assumed in nite for
the sake of simplicity"

But, negative proofs of an idea are worthwhile stepping stones to ones
that work.

On Thu, Jan 4, 2018 at 6:29 AM, Toke Høiland-Jørgensen  wrote:
> This popped up in my Google Scholar notifications:
>
> https://atlas.informatik.uni-tuebingen.de/~menth/papers/Menth18b.pdf
>
> Basically, they are proposing to permit a queue to accumulate a larger
> deficit while empty to allow light users to achieve the same throughput
> as heavy users (users being an endpoint with potentially multiple
> flows).
>
> Not sure how useful this really is, but it's somewhat related to Cake's
> src/dst user fairness feature, so may be of interest.
>
> -Toke
> ___
> Cake mailing list
> Cake@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/cake



-- 

Dave Täht
CEO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-669-226-2619
___
Cake mailing list
Cake@lists.bufferbloat.net
https://lists.bufferbloat.net/listinfo/cake

[Cake] Modification of DRR with deficit saving

[Toke Høiland-Jørgensen]

This popped up in my Google Scholar notifications:

https://atlas.informatik.uni-tuebingen.de/~menth/papers/Menth18b.pdf

Basically, they are proposing to permit a queue to accumulate a larger
deficit while empty to allow light users to achieve the same throughput
as heavy users (users being an endpoint with potentially multiple
flows).

Not sure how useful this really is, but it's somewhat related to Cake's
src/dst user fairness feature, so may be of interest.

-Toke
___
Cake mailing list
Cake@lists.bufferbloat.net
https://lists.bufferbloat.net/listinfo/cake