* Re: [Starlink] SIGCOMM MIT paper: Starvation in e2e congestion control
2022-08-11 19:34 ` David P. Reed
@ 2022-08-11 20:22 ` Ulrich Speidel
2022-08-11 20:24 ` Ulrich Speidel
2022-08-12 14:21 ` Livingood, Jason
2022-08-25 20:26 ` Dave Taht
2 siblings, 1 reply; 13+ messages in thread
From: Ulrich Speidel @ 2022-08-11 20:22 UTC (permalink / raw)
To: starlink
[-- Attachment #1: Type: text/plain, Size: 3070 bytes --]
On 12/08/2022 7:34 am, David P. Reed via Starlink wrote:
>
> I'll give you another example of a serious misuse of a theorem outside
> its range of applicability:
>
> Shannon proved a channel capacity theorem: C = W log(S / N). The proof
> is mathematical, and correct.
>
Indeed.
>
> But hiding in the assumptions are some very strong and rarely
> applicable conditions. It was a very useful result in founding
> information theory.
>
> But... it is now called "Shannon's Law" and asserted to be true and
> applicable to ALL communications systems.
>
...and it is. But it needs to be applied correctly.
>
> This turns out not to be correct. And it is hardly ever correct in
> practice.
>
Ahem ... if it's proven, it's correct, even in practice ;-)
>
> An example of non-correct application turns out to be when multiple
> transmissions of electromagnetic waves occur at the same time. EE
> practice is to treat "all other signals" as Gaussian Noise. They are
> not - they never are
>
Therein lies the problem. Correct theorem, incorrectly applied.
>
> .
>
> So, later information theorists discovered that where there are
> multiple signals received by a single receiving antenna, and only a
> little noise (usually from the RF Front End of the receiver, not the
> environment) the Slepian-Wolf capacity theorem applies C = W
> log(\sum(S[i]. i=1,N) /W).
>
Note: N here isn't the noise power (just the number of signals).
>
> That's a LOT more capacity than Shannon's Law predicts, especially in
> narrowband signalling.
>
Only if you lump in correlated signals with noise, which is an incorrect
(or rather, over-simplified) application of the Shannon-Hartley theorem.
>
> And noise itself is actually "measurement error" at the receiver,
> which is rarely Gaussian, in fact it really is quite predictable
> and/or removable.
>
Noise in the Shannon sense is random and therefore not predictable or
correlated. Interference can be both predictable and correlated, and
therefore can sometimes be removed / to an extent. Modelling
interference as noise means not exploiting its inherent properties, and
yes that means ending lower capacity. But that doesn't mean that either
theorem is inapplicable - Shannon's fundamental limit still holds, even
in the multi-user case, as long as the noise you plug in is the "little
noise" from the RF front end and leave the interference out.
The point I guess is that models are just models, and the more you know
about what it is that you are dealing with, the better you can model.
Which, I suppose, applies to managing queues also. The more you know
what's in them and how it'll respond when you manage it, the better.
--
****************************************************************
Dr. Ulrich Speidel
School of Computer Science
Room 303S.594 (City Campus)
The University of Auckland
u.speidel@auckland.ac.nz
http://www.cs.auckland.ac.nz/~ulrich/
****************************************************************
[-- Attachment #2: Type: text/html, Size: 7370 bytes --]
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Starlink] SIGCOMM MIT paper: Starvation in e2e congestion control
2022-08-11 19:34 ` David P. Reed
2022-08-11 20:22 ` Ulrich Speidel
@ 2022-08-12 14:21 ` Livingood, Jason
2022-08-12 14:23 ` Hesham ElBakoury
2022-08-25 20:26 ` Dave Taht
2 siblings, 1 reply; 13+ messages in thread
From: Livingood, Jason @ 2022-08-12 14:21 UTC (permalink / raw)
To: David P. Reed, starlink
[-- Attachment #1: Type: text/plain, Size: 6225 bytes --]
IMO this is all good feedback for the authors to have. I don’t know them but will send them a note that this list may have feedback on the paper as well as for future research*.
JL
* I will also note that this research is the kind of thing a grant program I lead at work might be interested in for 2023.
From: Starlink <starlink-bounces@lists.bufferbloat.net> on behalf of "David P. Reed via Starlink" <starlink@lists.bufferbloat.net>
Reply-To: "David P. Reed" <dpreed@deepplum.com>
Date: Thursday, August 11, 2022 at 15:34
To: "starlink@lists.bufferbloat.net" <starlink@lists.bufferbloat.net>
Subject: Re: [Starlink] SIGCOMM MIT paper: Starvation in e2e congestion control
On Thursday, August 11, 2022 10:29am, starlink-request@lists.bufferbloat.net said:
> From: Hesham ElBakoury <helbakoury@gmail.com>
> To: "David P. Reed" <dpreed@deepplum.com>,
> starlink@lists.bufferbloat.net
> Subject: Re: [Starlink] SIGCOMM MIT paper: Starvation in e2e
> congestion control
>
> Hi David,
>
> I think someone such as Professor Hari who got many awards including the
> sigcomm 2021 life-achievement award or his student Venkat need to be
> educated on Fair Queuing. There are many publications and text books
> which describe FQ. The results of this paper is for network paths that
> do not use FQ or ECN. Venkat/Hari can provide more details.
I would think that he knows about FQ in AQM, too. He should.
My point is that this paper, which talks about *starvation*, doesn't mention FQ at all, even though it is well known to mitigate "starvation effects" - it was invented to solve exactly that problem!
I'd suggest at minimum that the paper should point out that it *excludes* FQ from consideration. And if possible, explain why it was excluded...
I can think of reasons for excluding FQ in the specific paper, but shouldn't the title and abstract say it applies only narrowly: Proposed revised title: "Starvation in e2e congestion control if FQ is excluded within the network"
Particularly since the paper makes *broad* generalizations - the only 2-out-of-3 argument is stated as if it applies to ALL congestion control.
>
> For the CAP theorem, do you think I can get C,A,P, if this is what I
> need ? if this is the case, then this theorem is wrong or has limited
> applicability, correct ?
It has limited applicability for sure. Yet, it has become fashionable to act as if it is a completely general truth.
The CAP theorem, in the limited space of its assumptions, appears to be correct. But because it is so easily trivialized, as encouraged by the "you can have any two of C A an P, but not 3" without any qualification, problems with the definitions of the words C A and P - serious problems indeed that matter to a first order in real distributed systems - it is often used to derive "impossibility".
I'll give you another example of a serious misuse of a theorem outside its range of applicability:
Shannon proved a channel capacity theorem: C = W log(S / N). The proof is mathematical, and correct.
But hiding in the assumptions are some very strong and rarely applicable conditions. It was a very useful result in founding information theory.
But... it is now called "Shannon's Law" and asserted to be true and applicable to ALL communications systems.
This turns out not to be correct. And it is hardly ever correct in practice. An example of non-correct application turns out to be when multiple transmissions of electromagnetic waves occur at the same time. EE practice is to treat "all other signals" as Gaussian Noise. They are not - they never are.
So, later information theorists discovered that where there are multiple signals received by a single receiving antenna, and only a little noise (usually from the RF Front End of the receiver, not the environment) the Slepian-Wolf capacity theorem applies C = W log(\sum(S[i]. i=1,N) /W). That's a LOT more capacity than Shannon's Law predicts, especially in narrowband signalling.
And noise itself is actually "measurement error" at the receiver, which is rarely Gaussian, in fact it really is quite predictable and/or removable.
So a theorem can be correct (based on its assumptions) and inapplicable in most cases, because of its narrowness.
And this is why a limited (not very general) theorem of the 2-out-of-3 form is dangerous.
As for the CAP theorem, my Ph.D. thesis was in this very area - multi-copy consistency in distributed data systems. That was in 1978, 45 years ago. I've followed that work since the time - both the pragmatics and the theory. I think I fully understand both the context and how the axioms chosen by Brewer simplify reality in radical ways.
C A and P are not booleans or binary quantities. So in a real sense the CAP theorem is always inapplicable. But worse, the proof structure falls apart as a mathematical proof if you assume any metric for C A or P that isn't homomorphic to boolean algebraic quantities.
And worse, there is no standard measure of C A and P that captures what matters on any dimension.
So, aside from an intuition that maybe C, A, and P trade off in some way in some model of reality, the theorem is meaningless, and not very useful.
I hope this helps understand what's behind my comments.
At core, a referee ought to have asked - how is this conclusion justified as a general conclusion about ALL e2e congestion control in all networks, when it is only shown in a narrow, unrealistic case?
In my nearly 50 years of publishing in the computing and communications world, I've done a LOT of refereeing, and served on program committees as well. The obligation of a referee is to look at the conclusions of the paper, in the context of the state of the science, and figure out if the conclusion is supported by the paper's contents.
I'm not sure why this didn't happen here.
David
PS: compared to the post-publication comments to my first CS publication, in a letter to my mentor from Edsgar Dijkstra, I think I'm being gentle. It's motivated by getting the science right.
>
> Thanks
>
> Hesham
[-- Attachment #2: Type: text/html, Size: 16292 bytes --]
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Starlink] SIGCOMM MIT paper: Starvation in e2e congestion control
2022-08-12 14:21 ` Livingood, Jason
@ 2022-08-12 14:23 ` Hesham ElBakoury
0 siblings, 0 replies; 13+ messages in thread
From: Hesham ElBakoury @ 2022-08-12 14:23 UTC (permalink / raw)
To: starlink
[-- Attachment #1: Type: text/plain, Size: 6634 bytes --]
I already notified the authors.
Hesham
On 8/12/2022 7:21 AM, Livingood, Jason via Starlink wrote:
>
> IMO this is all good feedback for the authors to have. I don’t know
> them but will send them a note that this list may have feedback on the
> paper as well as for future research*.
>
> JL
>
> * I will also note that this research is the kind of thing a grant
> program I lead at work might be interested in for 2023.
>
> *From: *Starlink <starlink-bounces@lists.bufferbloat.net> on behalf of
> "David P. Reed via Starlink" <starlink@lists.bufferbloat.net>
> *Reply-To: *"David P. Reed" <dpreed@deepplum.com>
> *Date: *Thursday, August 11, 2022 at 15:34
> *To: *"starlink@lists.bufferbloat.net" <starlink@lists.bufferbloat.net>
> *Subject: *Re: [Starlink] SIGCOMM MIT paper: Starvation in e2e
> congestion control
>
> On Thursday, August 11, 2022 10:29am,
> starlink-request@lists.bufferbloat.net said:
>
> > From: Hesham ElBakoury <helbakoury@gmail.com>
> > To: "David P. Reed" <dpreed@deepplum.com>,
> > starlink@lists.bufferbloat.net
> > Subject: Re: [Starlink] SIGCOMM MIT paper: Starvation in e2e
> > congestion control
> >
> > Hi David,
> >
> > I think someone such as Professor Hari who got many awards including the
> > sigcomm 2021 life-achievement award or his student Venkat need to be
> > educated on Fair Queuing. There are many publications and text books
> > which describe FQ. The results of this paper is for network paths that
> > do not use FQ or ECN. Venkat/Hari can provide more details.
>
> I would think that he knows about FQ in AQM, too. He should.
>
> My point is that this paper, which talks about *starvation*, doesn't
> mention FQ at all, even though it is well known to mitigate
> "starvation effects" - it was invented to solve exactly that problem!
>
> I'd suggest at minimum that the paper should point out that it
> *excludes* FQ from consideration. And if possible, explain why it was
> excluded...
>
> I can think of reasons for excluding FQ in the specific paper, but
> shouldn't the title and abstract say it applies only narrowly:
> Proposed revised title: "Starvation in e2e congestion control if FQ is
> excluded within the network"
>
> Particularly since the paper makes *broad* generalizations - the only
> 2-out-of-3 argument is stated as if it applies to ALL congestion control.
>
> >
> > For the CAP theorem, do you think I can get C,A,P, if this is what I
> > need ? if this is the case, then this theorem is wrong or has limited
> > applicability, correct ?
>
> It has limited applicability for sure. Yet, it has become fashionable
> to act as if it is a completely general truth.
>
> The CAP theorem, in the limited space of its assumptions, appears to
> be correct. But because it is so easily trivialized, as encouraged by
> the "you can have any two of C A an P, but not 3" without any
> qualification, problems with the definitions of the words C A and P -
> serious problems indeed that matter to a first order in real
> distributed systems - it is often used to derive "impossibility".
>
> I'll give you another example of a serious misuse of a theorem outside
> its range of applicability:
>
> Shannon proved a channel capacity theorem: C = W log(S / N). The proof
> is mathematical, and correct.
>
> But hiding in the assumptions are some very strong and rarely
> applicable conditions. It was a very useful result in founding
> information theory.
>
> But... it is now called "Shannon's Law" and asserted to be true and
> applicable to ALL communications systems.
>
> This turns out not to be correct. And it is hardly ever correct in
> practice. An example of non-correct application turns out to be when
> multiple transmissions of electromagnetic waves occur at the same
> time. EE practice is to treat "all other signals" as Gaussian Noise.
> They are not - they never are.
>
> So, later information theorists discovered that where there are
> multiple signals received by a single receiving antenna, and only a
> little noise (usually from the RF Front End of the receiver, not the
> environment) the Slepian-Wolf capacity theorem applies C = W
> log(\sum(S[i]. i=1,N) /W). That's a LOT more capacity than Shannon's
> Law predicts, especially in narrowband signalling.
>
> And noise itself is actually "measurement error" at the receiver,
> which is rarely Gaussian, in fact it really is quite predictable
> and/or removable.
>
> So a theorem can be correct (based on its assumptions) and
> inapplicable in most cases, because of its narrowness.
>
> And this is why a limited (not very general) theorem of the 2-out-of-3
> form is dangerous.
>
> As for the CAP theorem, my Ph.D. thesis was in this very area -
> multi-copy consistency in distributed data systems. That was in 1978,
> 45 years ago. I've followed that work since the time - both the
> pragmatics and the theory. I think I fully understand both the context
> and how the axioms chosen by Brewer simplify reality in radical ways.
>
> C A and P are not booleans or binary quantities. So in a real sense
> the CAP theorem is always inapplicable. But worse, the proof structure
> falls apart as a mathematical proof if you assume any metric for C A
> or P that isn't homomorphic to boolean algebraic quantities.
>
> And worse, there is no standard measure of C A and P that captures
> what matters on any dimension.
>
> So, aside from an intuition that maybe C, A, and P trade off in some
> way in some model of reality, the theorem is meaningless, and not very
> useful.
>
> I hope this helps understand what's behind my comments.
>
> At core, a referee ought to have asked - how is this conclusion
> justified as a general conclusion about ALL e2e congestion control in
> all networks, when it is only shown in a narrow, unrealistic case?
>
> In my nearly 50 years of publishing in the computing and
> communications world, I've done a LOT of refereeing, and served on
> program committees as well. The obligation of a referee is to look at
> the conclusions of the paper, in the context of the state of the
> science, and figure out if the conclusion is supported by the paper's
> contents.
>
> I'm not sure why this didn't happen here.
>
> David
>
> PS: compared to the post-publication comments to my first CS
> publication, in a letter to my mentor from Edsgar Dijkstra, I think
> I'm being gentle. It's motivated by getting the science right.
>
> >
> > Thanks
> >
> > Hesham
>
>
> _______________________________________________
> Starlink mailing list
> Starlink@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/starlink
[-- Attachment #2: Type: text/html, Size: 20401 bytes --]
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Starlink] SIGCOMM MIT paper: Starvation in e2e congestion control
2022-08-11 19:34 ` David P. Reed
2022-08-11 20:22 ` Ulrich Speidel
2022-08-12 14:21 ` Livingood, Jason
@ 2022-08-25 20:26 ` Dave Taht
2 siblings, 0 replies; 13+ messages in thread
From: Dave Taht @ 2022-08-25 20:26 UTC (permalink / raw)
To: David P. Reed; +Cc: Dave Taht via Starlink
btw, it won best student paper at sigcomm. twitter thread here:
https://twitter.com/VenkatArun95/status/1555200399652814850
On Thu, Aug 11, 2022 at 12:34 PM David P. Reed via Starlink
<starlink@lists.bufferbloat.net> wrote:
>
>
>
> On Thursday, August 11, 2022 10:29am, starlink-request@lists.bufferbloat.net said:
>
> > From: Hesham ElBakoury <helbakoury@gmail.com>
> > To: "David P. Reed" <dpreed@deepplum.com>,
> > starlink@lists.bufferbloat.net
> > Subject: Re: [Starlink] SIGCOMM MIT paper: Starvation in e2e
> > congestion control
> >
> > Hi David,
> >
> > I think someone such as Professor Hari who got many awards including the
> > sigcomm 2021 life-achievement award or his student Venkat need to be
> > educated on Fair Queuing. There are many publications and text books
> > which describe FQ. The results of this paper is for network paths that
> > do not use FQ or ECN. Venkat/Hari can provide more details.
>
>
>
> I would think that he knows about FQ in AQM, too. He should.
>
> My point is that this paper, which talks about *starvation*, doesn't mention FQ at all, even though it is well known to mitigate "starvation effects" - it was invented to solve exactly that problem!
>
> I'd suggest at minimum that the paper should point out that it *excludes* FQ from consideration. And if possible, explain why it was excluded...
>
>
>
> I can think of reasons for excluding FQ in the specific paper, but shouldn't the title and abstract say it applies only narrowly: Proposed revised title: "Starvation in e2e congestion control if FQ is excluded within the network"
>
>
>
> Particularly since the paper makes *broad* generalizations - the only 2-out-of-3 argument is stated as if it applies to ALL congestion control.
>
> >
> > For the CAP theorem, do you think I can get C,A,P, if this is what I
> > need ? if this is the case, then this theorem is wrong or has limited
> > applicability, correct ?
>
>
>
> It has limited applicability for sure. Yet, it has become fashionable to act as if it is a completely general truth.
>
>
>
> The CAP theorem, in the limited space of its assumptions, appears to be correct. But because it is so easily trivialized, as encouraged by the "you can have any two of C A an P, but not 3" without any qualification, problems with the definitions of the words C A and P - serious problems indeed that matter to a first order in real distributed systems - it is often used to derive "impossibility".
>
>
>
> I'll give you another example of a serious misuse of a theorem outside its range of applicability:
>
>
>
> Shannon proved a channel capacity theorem: C = W log(S / N). The proof is mathematical, and correct.
>
> But hiding in the assumptions are some very strong and rarely applicable conditions. It was a very useful result in founding information theory.
>
>
>
> But... it is now called "Shannon's Law" and asserted to be true and applicable to ALL communications systems.
>
>
>
> This turns out not to be correct. And it is hardly ever correct in practice. An example of non-correct application turns out to be when multiple transmissions of electromagnetic waves occur at the same time. EE practice is to treat "all other signals" as Gaussian Noise. They are not - they never are.
>
> So, later information theorists discovered that where there are multiple signals received by a single receiving antenna, and only a little noise (usually from the RF Front End of the receiver, not the environment) the Slepian-Wolf capacity theorem applies C = W log(\sum(S[i]. i=1,N) /W). That's a LOT more capacity than Shannon's Law predicts, especially in narrowband signalling.
>
> And noise itself is actually "measurement error" at the receiver, which is rarely Gaussian, in fact it really is quite predictable and/or removable.
>
>
>
> So a theorem can be correct (based on its assumptions) and inapplicable in most cases, because of its narrowness.
>
>
>
> And this is why a limited (not very general) theorem of the 2-out-of-3 form is dangerous.
>
>
>
> As for the CAP theorem, my Ph.D. thesis was in this very area - multi-copy consistency in distributed data systems. That was in 1978, 45 years ago. I've followed that work since the time - both the pragmatics and the theory. I think I fully understand both the context and how the axioms chosen by Brewer simplify reality in radical ways.
>
>
>
> C A and P are not booleans or binary quantities. So in a real sense the CAP theorem is always inapplicable. But worse, the proof structure falls apart as a mathematical proof if you assume any metric for C A or P that isn't homomorphic to boolean algebraic quantities.
>
>
>
> And worse, there is no standard measure of C A and P that captures what matters on any dimension.
>
>
>
> So, aside from an intuition that maybe C, A, and P trade off in some way in some model of reality, the theorem is meaningless, and not very useful.
>
>
>
> I hope this helps understand what's behind my comments.
>
>
>
> At core, a referee ought to have asked - how is this conclusion justified as a general conclusion about ALL e2e congestion control in all networks, when it is only shown in a narrow, unrealistic case?
>
>
>
> In my nearly 50 years of publishing in the computing and communications world, I've done a LOT of refereeing, and served on program committees as well. The obligation of a referee is to look at the conclusions of the paper, in the context of the state of the science, and figure out if the conclusion is supported by the paper's contents.
>
>
>
> I'm not sure why this didn't happen here.
>
>
>
> David
>
>
>
> PS: compared to the post-publication comments to my first CS publication, in a letter to my mentor from Edsgar Dijkstra, I think I'm being gentle. It's motivated by getting the science right.
>
>
>
> >
> > Thanks
> >
> > Hesham
>
> _______________________________________________
> Starlink mailing list
> Starlink@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/starlink
--
FQ World Domination pending: https://blog.cerowrt.org/post/state_of_fq_codel/
Dave Täht CEO, TekLibre, LLC
^ permalink raw reply [flat|nested] 13+ messages in thread