[Starlink] SIGCOMM MIT paper: Starvation in e2e congestion control

[David P. Reed]

On Thursday, August 11, 2022 10:29am, starlink-request at lists.bufferbloat.net said:



> From: Hesham ElBakoury <helbakoury at gmail.com>
> To: "David P. Reed" <dpreed at deepplum.com>,
> starlink at 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.bufferbloat.net/private/starlink/attachments/20220811/191c9264/attachment.html>