Discussion:
Bufferbloat in high resolution + non-stationarity
(too old to reply)
Martin Geddes
2017-11-25 20:23:54 UTC
Permalink
Raw Message
Hi Dave,

The data was being taken from general network traffic from multiple opcos
for a tier 1 global network operator. The task wasn't to fix or improve
anything, but to merely establish the baseline quality of the network as-is.

What is different about these metrics is the ability to extract the
underlying causality, and to be able to (de)compose complete supply chains
in a scientific manner (that would stand up in court). If you can capture
timing data of the same packet passing multiple probing points, then you
can use preexisting measurement capture systems. What matters if getting
multi-point distributions, rather than single-point averages.

The inherent limitation of AQM is its goal: constructing exemplars of
"success modes" for differential flow treatment, without considering what
the "failure mode" risks are (which are significant and serious). That
said, it prolongs the life of the current infrastructure, buying time to
address the underlying science and engineering issues (like work
conservation, emergent performance outcomes, and loss/delay trading that
conflates degrees of freedom).

It doesn't matter what scheduling algorithm you build if it creates
arbitrage or denial-of-service attacks that can arm a systemic collapse
hazard. The good news is we have a new class of scheduling technology (that
works on a different paradigm) that can fully address all of the
requirements. We are currently deploying it to enable the world's first
commercial quality-assured broadband service.

Martin
Sorry for the late reply.
Folks,
I have uploaded a presentation of high-fidelity network performance
measures
which includes an example of bufferbloat in high resolution, as possibly
you
have never seen it before.
Well, flent can generate a similar level of detail under a generated
load. Some of kathie's work can now do it against tcp on pcaps.
Was yours against general traffic?
https://www.slideshare.net/mgeddes/stationarity-is-the-new-speed. The
classic
"bloat" is a sudden formation of the queue, and a very slow (and steady)
draining. Bufferbloat is just one form of statistical variability
("non-stationarity") in packet networks.
Good set of slides. Analysis is picking up...
Where you and I always tend to fall off a cliff is on your conclusions
as to what to do about it, e.g. slide 19. I'd rather love it if you
repeated your tests and graphs against pie, and fq_codel, and/or cake.
For that matter BBR might be interesting against your tool.
And then say what you'd do differently. In some way I can repeat.
For a world record winner, see this one where packets take over a minute
(Huawei
WiFi hotspot roaming in Ireland with UK SIM)! Or for a pretty picture of
buffers
draining, try this one.
Well, at the moment gogo-in-flight holds the interplanetary record
(680sec as I recall), but yea, 60+ seconds is up there. Contact
Guinness!
Happy to answer any questions.
Martin Geddes
_______________________________________________
Bloat mailing list
https://lists.bufferbloat.net/listinfo/bloat
Toke Høiland-Jørgensen
2017-11-26 12:20:26 UTC
Permalink
Raw Message
Post by Martin Geddes
It doesn't matter what scheduling algorithm you build if it creates
arbitrage or denial-of-service attacks that can arm a systemic
collapse hazard. The good news is we have a new class of scheduling
technology (that works on a different paradigm) that can fully address
all of the requirements. We are currently deploying it to enable the
world's first commercial quality-assured broadband service.
Could you point to any research papers describing this technology? Would
be interesting to read up on...

-Toke
Martin Geddes
2017-11-27 23:16:03 UTC
Permalink
Raw Message
Hi Toke,

The two critical references are this paper
<http://www.pnsol.com/public/TP-PNS-2003-09.pdf> and this PhD thesis
<https://www.cs.kent.ac.uk/pubs/2003/1892/>. The former describes
"cherish-urgency" multiplexing. The "cherish" is what is different to
today's scheduling. It is used to create a new class of algorithm whose
goal is global optimisation, not local optimisation (and global
pessimisation).

The latter describes a paradigm change from "build it and then reason about
emergent performance" to "reason about engineered performance and then
build it". It works in practise
<http://www.martingeddes.com/how-wales-got-the-first-internet-fast-lane/>,
so whether it works in theory is left as an exercise to the reader.

The first step is to get the measurement right. I'm running a public workshop
in London on 8th Dec <http://scientificnetwork.management>, and I am happy
to accommodate anyone from this list at our internal cost.

Everyone working on AQM has done the best possible within the paradigm they
are operating. There is a bigger box of possibilities available, but it
needs you to engage with a paradigm change.

Martin

*About me <http://martingedd.es> Free newsletter
<http://eepurl.com/dSkfz>* Company
website <http://www.martingeddes.com/> Twitter
<https://twitter.com/martingeddes> Zoom <https://zoom.us/j/5043587162> My
new start-up <http://justright.network> Not LinkedIn
<https://medium.com/@martingeddes/linkedin-or-lockedin-why-i-deleted-my-account-and-maybe-you-should-too-8cad40a0ea68>
Martin Geddes Consulting Ltd, Incorporated in Scotland, number SC275827
VAT Number: 859 5634 72 Registered office: 17-19 East London Street,
Edinburgh, EH7 4BN
Post by Toke Høiland-Jørgensen
Post by Martin Geddes
It doesn't matter what scheduling algorithm you build if it creates
arbitrage or denial-of-service attacks that can arm a systemic
collapse hazard. The good news is we have a new class of scheduling
technology (that works on a different paradigm) that can fully address
all of the requirements. We are currently deploying it to enable the
world's first commercial quality-assured broadband service.
Could you point to any research papers describing this technology? Would
be interesting to read up on...
-Toke
Dave Taht
2017-11-27 23:55:07 UTC
Permalink
Raw Message
Post by Martin Geddes
Hi Toke,
The two critical references are this paper and this PhD thesis. The former
describes "cherish-urgency" multiplexing. The "cherish" is what is different
to today's scheduling. It is used to create a new class of algorithm whose
goal is global optimisation, not local optimisation (and global
pessimisation).
The latter describes a paradigm change from "build it and then reason about
emergent performance" to "reason about engineered performance and then build
it". It works in practise, so whether it works in theory is left as an
exercise to the reader.
The first step is to get the measurement right. I'm running a public
workshop in London on 8th Dec, and I am happy to accommodate anyone from
this list at our internal cost.
Everyone working on AQM has done the best possible within the paradigm they
are operating. There is a bigger box of possibilities available, but it
needs you to engage with a paradigm change.
We are currently benchmarking the known alternatives vs everything
else via a dozen methods we understand.

fq_codel v "cake":

http://www.drhleny.cz/bufferbloat/cake/round1/eg_csrt_rrulbe_eg_fq_codel_200mbit/index.html

http://www.drhleny.cz/bufferbloat/cake/round1/eg_csrt_rrulbe_eg_cakeeth_200mbit/index.html
Post by Martin Geddes
Martin
About me Free newsletter Company website Twitter Zoom My new start-up Not
LinkedIn Martin Geddes Consulting Ltd, Incorporated in Scotland, number
SC275827 VAT Number: 859 5634 72 Registered office: 17-19 East London
Street, Edinburgh, EH7 4BN
Post by Toke Høiland-Jørgensen
Post by Martin Geddes
It doesn't matter what scheduling algorithm you build if it creates
arbitrage or denial-of-service attacks that can arm a systemic
collapse hazard. The good news is we have a new class of scheduling
technology (that works on a different paradigm) that can fully address
all of the requirements. We are currently deploying it to enable the
world's first commercial quality-assured broadband service.
Could you point to any research papers describing this technology? Would
be interesting to read up on...
-Toke
_______________________________________________
Bloat mailing list
https://lists.bufferbloat.net/listinfo/bloat
--
Dave Täht
CEO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-669-226-2619
Aaron Wood
2017-11-28 02:07:53 UTC
Permalink
Raw Message
For the graphs, it would be great for f they were using a normalize output
that allows for easy comparisons between runs. Especially the y axis for
the “all” graph.
Post by Martin Geddes
Post by Martin Geddes
Hi Toke,
The two critical references are this paper and this PhD thesis. The
former
Post by Martin Geddes
describes "cherish-urgency" multiplexing. The "cherish" is what is
different
Post by Martin Geddes
to today's scheduling. It is used to create a new class of algorithm
whose
Post by Martin Geddes
goal is global optimisation, not local optimisation (and global
pessimisation).
The latter describes a paradigm change from "build it and then reason
about
Post by Martin Geddes
emergent performance" to "reason about engineered performance and then
build
Post by Martin Geddes
it". It works in practise, so whether it works in theory is left as an
exercise to the reader.
The first step is to get the measurement right. I'm running a public
workshop in London on 8th Dec, and I am happy to accommodate anyone from
this list at our internal cost.
Everyone working on AQM has done the best possible within the paradigm
they
Post by Martin Geddes
are operating. There is a bigger box of possibilities available, but it
needs you to engage with a paradigm change.
We are currently benchmarking the known alternatives vs everything
else via a dozen methods we understand.
http://www.drhleny.cz/bufferbloat/cake/round1/eg_csrt_rrulbe_eg_fq_codel_200mbit/index.html
http://www.drhleny.cz/bufferbloat/cake/round1/eg_csrt_rrulbe_eg_cakeeth_200mbit/index.html
Post by Martin Geddes
Martin
About me Free newsletter Company website Twitter Zoom My new start-up Not
LinkedIn Martin Geddes Consulting Ltd, Incorporated in Scotland, number
SC275827 VAT Number: 859 5634 72 Registered office: 17-1
<https://maps.google.com/?q=mber:+859+5634+72+Registered+office:+17-1&entry=gmail&source=g>9
East London
Post by Martin Geddes
Street, Edinburgh, EH7 4BN
Post by Toke Høiland-Jørgensen
Post by Martin Geddes
It doesn't matter what scheduling algorithm you build if it creates
arbitrage or denial-of-service attacks that can arm a systemic
collapse hazard. The good news is we have a new class of scheduling
technology (that works on a different paradigm) that can fully address
all of the requirements. We are currently deploying it to enable the
world's first commercial quality-assured broadband service.
Could you point to any research papers describing this technology? Would
be interesting to read up on...
-Toke
_______________________________________________
Bloat mailing list
https://lists.bufferbloat.net/listinfo/bloat
--
Dave TÀht
CEO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-669-226-2619
_______________________________________________
Bloat mailing list
https://lists.bufferbloat.net/listinfo/bloat
Toke Høiland-Jørgensen
2017-11-28 11:03:36 UTC
Permalink
Raw Message
Post by Martin Geddes
The two critical references are this paper
<http://www.pnsol.com/public/TP-PNS-2003-09.pdf> and this PhD thesis
<https://www.cs.kent.ac.uk/pubs/2003/1892/>. The former describes
"cherish-urgency" multiplexing. The "cherish" is what is different to
today's scheduling. It is used to create a new class of algorithm
whose goal is global optimisation, not local optimisation (and global
pessimisation).
Cool, thanks; I'll add that to my reading list (well, the paper
certainly; not sure I'll get the time to go through the whole 200+ page
thesis anytime soon :/)
Post by Martin Geddes
The latter describes a paradigm change from "build it and then reason
about emergent performance" to "reason about engineered performance
and then build it". It works in practise
<http://www.martingeddes.com/how-wales-got-the-first-internet-fast-lane/>,
so whether it works in theory is left as an exercise to the reader.
I don't suppose there's an open source implementation available to play
with?

-Toke
Jonathan Morton
2017-11-28 16:16:44 UTC
Permalink
Raw Message
I read the paper just now, and skimmed through the thesis to determine that
it was talking about the same thing using an order of magnitude more space.

It boils down to a Diffserv implementation using a classifier (details
handwaved as usual), policers, shapers, and a strict-priority tail-dropping
queue. The only noteworthy feature is that the position of the queue's
tail depends on the "cherish" metric of each traffic class, which is used
to provide differentiation in loss, leaving the strict-priority mechanism
to provide "urgency" (delay) differentiation.

From the above, you might reasonably conclude that I'm not very impressed.

The paper includes a test scenario versus a plain FIFO and a DRR system.
The DRR was weighted with a-priori knowledge of the relative traffic
volumes, which in fact would have degraded its performance in delay
management. A DRR++ implementation *without* such knowledge would have
outperformed it substantially.

Toke, reproducing that test load and running it through an unmodified Cake
instance would perhaps be enlightening.

- Jonathan Morton
Neil Davies
2017-11-30 12:31:04 UTC
Permalink
Raw Message
The key design goal was to create assured bounds on loss and delay for designated classes during extended periods of load saturation.

The mechanisms, to some extent, are not the issue - the ability configure it and know a-prori (to a given error bound) what would happen to the traffic flows was our primary goal.

The key point we found as we did this work is (as you remark below) that current systems don’t mange the two degrees of freedom that is present in every queueing system, whereas this one does. As anyone who has done any control theory will tell you that is the first essential step to being able control.

We note that what queueing mechanisms do (with respect to application’s performance outcomes) is share the delay and loss (which occurs when the queueing system is non-empty) between the flows that are in competition at the moment in time - this is what this mechanism does.

If you want a larger evaluation, including what needs to be done when transmission capacity changes (as in 3G/4G/5G etc) take a look at http://www.pnsol.com/public/TP-PNS-CS-2005-11.pdf <http://www.pnsol.com/public/TP-PNS-CS-2005-11.pdf> - it is a much richer scenario and provides some strong motivation for why just managing to bandwidth (and speed) is probably not the right goal for many emerging use cases.

Cheers

Neil
I read the paper just now, and skimmed through the thesis to determine that it was talking about the same thing using an order of magnitude more space.
It boils down to a Diffserv implementation using a classifier (details handwaved as usual), policers, shapers, and a strict-priority tail-dropping queue. The only noteworthy feature is that the position of the queue's tail depends on the "cherish" metric of each traffic class, which is used to provide differentiation in loss, leaving the strict-priority mechanism to provide "urgency" (delay) differentiation.
From the above, you might reasonably conclude that I'm not very impressed.
The paper includes a test scenario versus a plain FIFO and a DRR system. The DRR was weighted with a-priori knowledge of the relative traffic volumes, which in fact would have degraded its performance in delay management. A DRR++ implementation *without* such knowledge would have outperformed it substantially.
Toke, reproducing that test load and running it through an unmodified Cake instance would perhaps be enlightening.
- Jonathan Morton
Spam <https://portal.roaringpenguin.co.uk/canit/b.php?c=s&i=04UDsgPAO&m=bd67d1bccf1c&rlm=pnsol-com&t=20171128>
Not spam <https://portal.roaringpenguin.co.uk/canit/b.php?c=n&i=04UDsgPAO&m=bd67d1bccf1c&rlm=pnsol-com&t=20171128>
Forget previous vote <https://portal.roaringpenguin.co.uk/canit/b.php?c=f&i=04UDsgPAO&m=bd67d1bccf1c&rlm=pnsol-com&t=20171128>
_______________________________________________
Bloat mailing list
https://lists.bufferbloat.net/listinfo/bloat
Jonathan Morton
2017-11-30 16:51:40 UTC
Permalink
Raw Message
A central assumption in all of your references so far is that the relevant
traffic classes can be distinguished reliably in realtime and sent to
appropriate queues. There is no fallback mechanism given for any cases
where this assumption is false - the queue within each class is a FIFO,
which as each paper notes is utterly incapable of providing the required
quality, or even an approximation to it, by itself.

In practice, we have found traffic classification to be a major problem in
terms of deployment. Although some classes are easy to identify by layer-4
protocol and port, some important traffic (from a quality management point
of view) deliberately obscures its identity to avoid censorship, while
other types are simply difficult to distinguish from best-effort web
traffic because they piggy-back on the HTTP port and protocol. The
TOS/DSCP field, which could theoretically be useful here, is rarely used in
practice by applications, and is frequently mangled by ISPs as part of
their own traffic management.

I submit that to provide *deployable* QoS schemes, you must either solve
the classification problem elegantly (which is a Hard Problem), or else
show that your scheme works adequately in the absence of classification.
I'm taking the latter approach with Cake, even though it *also* supports
Diffserv awareness to enhance its performance where classification is
straightforward.

My earlier point was that the scenario given in your 2003 paper could be
satisfied with *no* a-priori knowledge, classification or configuration,
merely a good flow-isolation algorithm operating on the 5-tuple. In 2003,
you may not have known about DRR++, but it is widely deployed today as part
of fq_codel and meets those criteria by default.

In your 2005 paper, I find you in the curious position of assuming that an
"ad hoc" network can have a sophisticated QoS scheme, dynamically
configured to match the offered load (which for the experiment required
manual trial and error), in a way that supports *safety critical* levels of
service. You then establish the frankly unsurprising results that strictly
prioritising critical traffic over the rest improves its quality of
service, and that it is possible to adequately service all traffic if the
network is not driven into saturation. I stopped reading at that point; I
have little patience for laborious proof of the obvious.

Being able to measure a network well *is* potentially useful. The papers
and articles you've linked so far do *not* disclose anything useful.

- Jonathan Morton
Mikael Abrahamsson
2017-11-30 19:59:03 UTC
Permalink
Raw Message
Post by Jonathan Morton
I submit that to provide *deployable* QoS schemes, you must either solve
the classification problem elegantly (which is a Hard Problem), or else
show that your scheme works adequately in the absence of classification.
I'm taking the latter approach with Cake, even though it *also* supports
Diffserv awareness to enhance its performance where classification is
straightforward.
In IETF INT-AREA, there is now discussion about allocating a new diffserv
codepoint for "less-than-best-effort" traffic. I have been advocate for
this for quite a while, and I actually believe that this is incrementally
deployable and has a chance to actually get ISP buy-in.

The idea is to use TOS 0, but use the last 3 diffserv bits to indicate
that this is less-than-BE. Non-implementing networks will treat this as
BE, implementing networks can use some kind of DRR scheme to give this
traffic less bandwidth in case of congestion, or just drop it earlier when
there is queue buildup.

I think this is the only chance we have to get internet-wide coordination
for a diffserv codepoint that people will do anything with, and the
recommendation should be to only act on this at the customer access line
(the one connecting the ISP to the residential gateway) or perhaps within
the customer network. The hope is that ISPs will not mangle/bleach this
codepoint, because it actually indicates traffic should get lower
priority, not higher.

I am in complete agreement with you that any scheme that relies on
Internet-wide QoS scheme based on diffserv/TOS is a no-go. No ISP will
listen to this and act on it, as it's a DoS vector.
--
Mikael Abrahamsson email: ***@swm.pp.se
Jonathan Morton
2017-11-30 20:09:40 UTC
Permalink
Raw Message
Cake already supports treating CS1 as less-than-besteffort by default.
Adding more codepoints to that list is easy.

The trick is getting applications to actually use them. That's a
chicken-egg problem.

- Jonathan Morton
Michael Welzl
2017-12-01 09:06:57 UTC
Permalink
Raw Message
I thought that some browsers already use various DSCPs when running WebRTC?
Cake already supports treating CS1 as less-than-besteffort by default. Adding more codepoints to that list is easy.
The trick is getting applications to actually use them. That's a chicken-egg problem.
- Jonathan Morton
_______________________________________________
Bloat mailing list
https://lists.bufferbloat.net/listinfo/bloat
Jonathan Morton
2017-12-01 13:48:33 UTC
Permalink
Raw Message
If so, that's a step in the right direction. I know of a few "old guard"
protocols which typically use appropriate DSCPs too.

But YouTube doesn't, and neither do any of the major BitTorrent
implementations (despite us asking nicely), nor typical VoIP clients, nor
multiplayer games. Those are the places I'd hope to see progress
relatively early.

Several prominent game publishers use libtorrent in combination with a CDN
of web-seeds, in which the web-seeds would benefit from having CS1 set and
libtorrent tuned for a smaller number of connections - no dice so far,
though libtorrent's developers seem to nominally agree.

- Jonathan Morton

Martin Geddes
2017-11-28 23:57:45 UTC
Permalink
Raw Message
Hi Toke,

I'd really like to get it to be open source, and that's probably going to
take a collaborative industry funding effort to achieve as a reference
measurement implementation of a universal interoperable quality standard
(i.e. ∆Q-based metrics). There's a mathematical inevitability to the end
game of both metrics and scheduling, and we're very close to it.

In the meantime, I can give you a trial version to play with. How about you
give it a spin and share your feedback here of what you learned?

Martin

*About me <http://martingedd.es> Free newsletter
<http://eepurl.com/dSkfz>* Company
website <http://www.martingeddes.com/> Twitter
<https://twitter.com/martingeddes> Zoom <https://zoom.us/j/5043587162> My
new start-up <http://justright.network> Not LinkedIn
<https://medium.com/@martingeddes/linkedin-or-lockedin-why-i-deleted-my-account-and-maybe-you-should-too-8cad40a0ea68>
Martin Geddes Consulting Ltd, Incorporated in Scotland, number SC275827
VAT Number: 859 5634 72 Registered office: 17-19 East London Street,
Edinburgh, EH7 4BN
Post by Toke Høiland-Jørgensen
Post by Martin Geddes
The two critical references are this paper
<http://www.pnsol.com/public/TP-PNS-2003-09.pdf> and this PhD thesis
<https://www.cs.kent.ac.uk/pubs/2003/1892/>. The former describes
"cherish-urgency" multiplexing. The "cherish" is what is different to
today's scheduling. It is used to create a new class of algorithm
whose goal is global optimisation, not local optimisation (and global
pessimisation).
Cool, thanks; I'll add that to my reading list (well, the paper
certainly; not sure I'll get the time to go through the whole 200+ page
thesis anytime soon :/)
Post by Martin Geddes
The latter describes a paradigm change from "build it and then reason
about emergent performance" to "reason about engineered performance
and then build it". It works in practise
<http://www.martingeddes.com/how-wales-got-the-first-internet-fast-lane/
,
so whether it works in theory is left as an exercise to the reader.
I don't suppose there's an open source implementation available to play
with?
-Toke
Toke Høiland-Jørgensen
2017-11-29 11:57:03 UTC
Permalink
Raw Message
Post by Martin Geddes
In the meantime, I can give you a trial version to play with. How
about you give it a spin and share your feedback here of what you
learned?
You mean the measurement tool, right? I won't promise I have time to do
an extensive evaluation, but I can take it for a spin and report first
impressions at least... :)

-Toke
Loading...