From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp72.iad3a.emailsrvr.com (smtp72.iad3a.emailsrvr.com [173.203.187.72]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id 3E1F03B2A4 for ; Thu, 11 Aug 2022 15:34:50 -0400 (EDT) Received: from app4.wa-webapps.iad3a (relay-webapps.rsapps.net [172.27.255.140]) by smtp34.relay.iad3a.emailsrvr.com (SMTP Server) with ESMTP id B58EB22C11 for ; Thu, 11 Aug 2022 15:34:49 -0400 (EDT) Received: from deepplum.com (localhost.localdomain [127.0.0.1]) by app4.wa-webapps.iad3a (Postfix) with ESMTP id A11B4E0E1D for ; Thu, 11 Aug 2022 15:34:49 -0400 (EDT) Received: by apps.rackspace.com (Authenticated sender: dpreed@deepplum.com, from: dpreed@deepplum.com) with HTTP; Thu, 11 Aug 2022 15:34:49 -0400 (EDT) X-Auth-ID: dpreed@deepplum.com Date: Thu, 11 Aug 2022 15:34:49 -0400 (EDT) From: "David P. Reed" To: starlink@lists.bufferbloat.net MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_20220811153449000000_21922" Importance: Normal X-Priority: 3 (Normal) X-Type: html In-Reply-To: References: X-Client-IP: 209.6.168.128 Message-ID: <1660246489.6578887@apps.rackspace.com> X-Mailer: webmail/19.0.17-RC X-Classification-ID: 30ca8f06-fd1f-4b53-8258-6dc8372fcdd6-1-1 Subject: Re: [Starlink] SIGCOMM MIT paper: Starvation in e2e congestion control X-BeenThere: starlink@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: "Starlink has bufferbloat. Bad." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 11 Aug 2022 19:34:50 -0000 ------=_20220811153449000000_21922 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable =0A =0AOn Thursday, August 11, 2022 10:29am, starlink-request@lists.bufferb= loat.net said:=0A=0A=0A=0A> From: Hesham ElBakoury = =0A> To: "David P. Reed" ,=0A> starlink@lists.bufferbl= oat.net=0A> Subject: Re: [Starlink] SIGCOMM MIT paper: Starvation in e2e=0A= > congestion control=0A> =0A> Hi David,=0A> =0A> I think someone such as Pr= ofessor Hari who got many awards including the=0A> sigcomm 2021 life-achiev= ement award or his student Venkat need to be=0A> educated on Fair Queuing. = There are many publications and text books=0A> which describe FQ. The resul= ts of this paper is for network paths that=0A> do not use FQ or ECN. Venkat= /Hari can provide more details.=0A =0AI would think that he knows about FQ = in AQM, too. He should.=0AMy point is that this paper, which talks about *s= tarvation*, doesn't mention FQ at all, even though it is well known to miti= gate "starvation effects" - it was invented to solve exactly that problem!= =0AI'd suggest at minimum that the paper should point out that it *excludes= * FQ from consideration. And if possible, explain why it was excluded...=0A= =0AI can think of reasons for excluding FQ in the specific paper, but shou= ldn't the title and abstract say it applies only narrowly: Proposed revise= d title: "Starvation in e2e congestion control if FQ is excluded within the= network"=0A =0AParticularly since the paper makes *broad* generalizations = - the only 2-out-of-3 argument is stated as if it applies to ALL congestion= control.=0A> =0A> For the CAP theorem, do you think I can get C,A,P, if th= is is what I=0A> need ? if this is the case, then this theorem is wrong or = has limited=0A> applicability, correct ?=0A =0AIt has limited applicability= for sure. Yet, it has become fashionable to act as if it is a completely g= eneral truth.=0A =0AThe CAP theorem, in the limited space of its assumption= s, appears to be correct. But because it is so easily trivialized, as encou= raged by the "you can have any two of C A an P, but not 3" without any qual= ification, problems with the definitions of the words C A and P - serious p= roblems indeed that matter to a first order in real distributed systems - i= t is often used to derive "impossibility".=0A =0AI'll give you another exam= ple of a serious misuse of a theorem outside its range of applicability:=0A= =0AShannon proved a channel capacity theorem: C =3D W log(S / N). The proo= f is mathematical, and correct.=0ABut hiding in the assumptions are some ve= ry strong and rarely applicable conditions. It was a very useful result in = founding information theory.=0A =0ABut... it is now called "Shannon's Law" = and asserted to be true and applicable to ALL communications systems. =0A = =0AThis turns out not to be correct. And it is hardly ever correct in pract= ice. An example of non-correct application turns out to be when multiple tr= ansmissions 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.=0ASo, later information theorists discovered that where there are mult= iple signals received by a single receiving antenna, and only a little nois= e (usually from the RF Front End of the receiver, not the environment) the = Slepian-Wolf capacity theorem applies C =3D W log(\sum(S[i]. i=3D1,N) /W). = That's a LOT more capacity than Shannon's Law predicts, especially in narro= wband signalling.=0AAnd noise itself is actually "measurement error" at the= receiver, which is rarely Gaussian, in fact it really is quite predictable= and/or removable.=0A =0ASo a theorem can be correct (based on its assumpti= ons) and inapplicable in most cases, because of its narrowness.=0A =0AAnd t= his is why a limited (not very general) theorem of the 2-out-of-3 form is d= angerous.=0A =0AAs for the CAP theorem, my Ph.D. thesis was in this very ar= ea - 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 ax= ioms chosen by Brewer simplify reality in radical ways.=0A =0AC A and P are= not booleans or binary quantities. So in a real sense the CAP theorem is a= lways inapplicable. But worse, the proof structure falls apart as a mathema= tical proof if you assume any metric for C A or P that isn't homomorphic to= boolean algebraic quantities.=0A =0AAnd worse, there is no standard measur= e of C A and P that captures what matters on any dimension.=0A =0ASo, aside= from an intuition that maybe C, A, and P trade off in some way in some mod= el of reality, the theorem is meaningless, and not very useful.=0A =0AI hop= e this helps understand what's behind my comments.=0A =0AAt core, a referee= ought to have asked - how is this conclusion justified as a general conclu= sion about ALL e2e congestion control in all networks, when it is only show= n in a narrow, unrealistic case?=0A =0AIn my nearly 50 years of publishing = in the computing and communications world, I've done a LOT of refereeing, a= nd 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 sc= ience, and figure out if the conclusion is supported by the paper's content= s.=0A =0AI'm not sure why this didn't happen here.=0A =0ADavid=0A =0APS: co= mpared to the post-publication comments to my first CS publication, in a le= tter to my mentor from Edsgar Dijkstra, I think I'm being gentle. It's moti= vated by getting the science right.=0A =0A> =0A> Thanks=0A> =0A> Hesham=0A= =0A ------=_20220811153449000000_21922 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

 

=0A

On Thursday, August 11, 2022 10:29am, starlink-request@lists.b= ufferbloat.net said:

=0A
=0A=

> From: Hesham ElBakoury <helbakoury@gmail.com&g= t;
> To: "David P. Reed" <dpreed@deepplum.com>,
> sta= rlink@lists.bufferbloat.net
> Subject: Re: [Starlink] SIGCOMM MIT p= aper: Starvation in e2e
> congestion control
>
> H= i David,
>
> I think someone such as Professor Hari who go= t many awards including the
> sigcomm 2021 life-achievement award o= r his student Venkat need to be
> educated on Fair Queuing. There a= re many publications and text books
> which describe FQ. The result= s of this paper is for network paths that
> do not use FQ or ECN. V= enkat/Hari can provide more details.

=0A

 

= =0A

I would think that he knows about FQ in AQM, too. H= e should.

=0A

My point is that this paper, which tal= ks about *starvation*, doesn't mention FQ at all, even though it is well kn= own to mitigate "starvation effects" - it was invented to solve exactly tha= t problem!

=0A

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...

=0A

 

=0AI can think of reasons for excluding FQ in the specific = paper, but shouldn't the title and abstract say  it applies only narro= wly: Proposed revised title: "Starvation in e2e congestion control if FQ is= excluded within the network"

=0A

 

=0A

Particularly since the paper makes *broad* generalizations = - the only 2-out-of-3 argument is stated as if it applies to ALL congestion= control.

=0A

>
> For the CAP theorem, d= o 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 ?

=0A

 

=0A

It= has limited applicability for sure. Yet, it has become fashionable to act = as if it is a completely general truth.

=0A

 =0A

The CAP theorem, in the limited space of its assu= mptions, 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 an= y qualification, problems with the definitions of the words C A and P - ser= ious problems indeed that matter to a first order in real distributed syste= ms - it is often used to derive "impossibility".

=0A

 

=0A

I'll give you another example of a serio= us misuse of a theorem outside its range of applicability:

=0A

 

=0A

Shannon proved a channel cap= acity theorem: C =3D W log(S / N). The proof is mathematical, and correct.<= /p>=0A

But hiding in the assumptions are some very stro= ng and rarely applicable conditions. It was a very useful result in foundin= g information theory.

=0A

 

=0A

But... it is now called "Shannon's Law" and asserted to be true and= applicable to ALL communications systems. 

=0A

 

=0A

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 N= oise. They are not - they never are.

=0A

So, later i= nformation theorists discovered that where there are multiple signals recei= ved by a single receiving antenna, and only a little noise (usually from th= e RF Front End of the receiver, not the environment) the Slepian-Wolf capac= ity theorem applies C =3D W log(\sum(S[i]. i=3D1,N) /W). That's a LOT more = capacity than Shannon's Law predicts, especially in narrowband signalling.<= /p>=0A

And noise itself is actually "measurement error"= at the receiver, which is rarely Gaussian, in fact it really is quite pred= ictable and/or removable.

=0A

 

=0A

So a theorem can be correct (based on its assumptions) and ina= pplicable in most cases, because of its narrowness.

=0A

 

=0A

And this is why a limited (not very g= eneral) theorem of the 2-out-of-3 form is dangerous.

=0A

 

=0A

As for the CAP theorem, my Ph.D. the= sis was in this very area - multi-copy consistency in distributed data syst= ems. That was in 1978, 45 years ago.  I've followed that work since th= e time - both the pragmatics and the theory. I think I fully understand bot= h the context and how the axioms chosen by Brewer simplify reality in radic= al ways.

=0A

 

=0A

C A a= nd P are not booleans or binary quantities. So in a real sense the CAP theo= rem 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 is= n't homomorphic to boolean algebraic quantities.

=0A

 

=0A

And worse, there is no standard measure = of C A and P that captures what matters on any dimension.

=0A

 

=0A

So, aside from an intuition tha= t maybe C, A, and P trade off in some way in some model of reality, the the= orem is meaningless, and not very useful.

=0A

 =

=0A

I hope this helps understand what's behind my c= omments.

=0A

 

=0A

At co= re, a referee ought to have asked - how is this conclusion justified as a g= eneral conclusion about ALL e2e congestion control in all networks, when it= is only shown in a narrow, unrealistic case?

=0A

&n= bsp;

=0A

In my nearly 50 years of publishing in the = computing and communications world, I've done a LOT of refereeing, and serv= ed 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.

= =0A

 

=0A

I'm not sure why = this didn't happen here.

=0A

 

=0A

David

=0A

 

=0A

PS: compared to the post-publication comments to my first CS publicati= on, in a letter to my mentor from Edsgar Dijkstra, I think I'm being gentle= . It's motivated by getting the science right.

=0A

&= nbsp;

=0A

>
> Thanks
>
>= ; Hesham

=0A
 ------=_20220811153449000000_21922--