Fwd: Re: Once again buffer bloat and CC. Re: A Cute Story. Or: How to talk completely at cross purposes. Re: [ih] When was Go Back N adopted by TCP

Forwarded for David Reed.

Joe (as list admin)

-------- Original Message --------
Subject: 	Re: [e2e] Once again buffer bloat and CC. Re: A Cute Story.
Or: How to talk completely at cross purposes. Re: [ih] When was Go Back
N adopted by TCP
Date: 	Wed, 20 Aug 2014 16:03:28 -0400 (EDT)
From: 	[email protected]
To: 	Detlef Bosau <[email protected]>, Kathleen Nichols
<[email protected]>
CC: 	[email protected], "Joe Touch" <[email protected]>

[Joe Touch - please pass this on to the e2e list if it is OK with you]

I'd like to amplify Detlef's reference to my position and approach to
end-to-end congestion management, which may or may not be the same
approach he would argue for:

To avoid/minimize end-to-end queueing delay in a shared internetwork, we=20
need to change the idea that we need to create substantial queues in
order to measure the queue length we want to reduce.  This is possible,
because of a simple observation: you can detect and measure the
probability that two flows sharing a link will delay each other before
they actually do...  call this "pre-congestion avoidance".

Rather than leave that as an exercise for the reader (it's only a Knuth
[20] problem at most, but past suggestions have not been followed up,
and I am working 16 hours per day in a startup), I will explain how:
packets need to wait for each other if the time interval  each spends
passing through a particular switch's outbound NIC "overlaps".  If you
remember recent flow histories (as fq_codel does, for example), you can
record when each flow recently occupied the switch's outbound link, and
with some robust assumptions of timing variability, one can estimate the=20
likelihood that a queue might have built up.  This information can be=20
reflected to the destination of all flows, just as ECN marks are used in=20
Jain's approach.   Since congestion control is necessarily done by=20
having the receiving end control the sending end (because you want to=20
move end-to-end queues back to the source entrypoint, where they must=20
exist for retransmission in any case), the receiver can use that "near=20
collision" detection notification to slow the sender to a non-congesting=20
rate that shares all links on the path such that queues will develop=20
with arbitrarily low probability.

Call this the "ballistic collision avoidance" model (and cite me if you
don't want to take all the credit).

It's one way to achieve what Detlef has described as "my position" while=20
retaining a simple model.

And if you need a mechanism for tracking packets that have passed
through a node in recent times, I suggest studying this paper very
carefully:  Deng and Rafei, "Approximately detecting duplicaes for
streaming data using Stable Bloom Filters".  Stable Bloom Filters can
use the switch memory not used by excess buffer space to prevent
unnecessary queueing, rather than to create queues in order to have
something to measure. They can detect the current density of packets on
the same flow (they are a version of Counting Bloom Filters that don't
need the delete() operation to reduce the "count", only requiring
insert() operations).

As they say in the patentability literature, that is a description of
the concept sufficient for someone skilled in the relevant (protocol
engineering) art to fully realize the invention.  I view this note as a
publication - thus no one can patent this idea from now on. This is
"prior art" and a "constructive realization" of the invention.  Thus I
grant it to the internetworking community to be used freely without a
license, which I hope is what will happen, as has happened with all
other internetworking concepts.  If it is turned into specific source
code or silicon design, you may want to copyright it, however, to
capture value from your labor in completing the implementation. I'm sure=20
there is also a great paper or two waiting to be written based on
exploring the idea's impact on real networking and comparing it with
other approaches.


On Wednesday, August 20, 2014 3:01pm, "Detlef Bosau"
<[email protected]> said:

  > And in addition, what queue length is concerned, I take the position
  > (which is similar to DPR's, IIRC) that a router should keep no more t=
han
  > one packet per flow at a given time, in the general case.
  >
  > I explicitly state that in wireless scenarios, there might be reasons=
 to
  > accept longer router queues, particularly in the context of
  > opportunistic scheduling. But in the general case, the very first ste=
p
  > to be taken is to keep packets out of router queues. I sometimes
  > observed RTTs by 20 ms or more between Stuttart and Karlsruhe, i,e.
  > about 60 kilometers.
  >
  > Perhaps, we have a special "opaque fibre" with reduced speed of light
  > there. However, I'm not convinced that this RTT is caused by the link=
s
  > and processcing delays. I would have a look at the memory graveyards
  > called "router" along the path.
  >
  >
  > --
  > ------------------------------------------------------------------
  > Detlef Bosau
  > Galileistra=C3=9Fe 30
  > 70565 Stuttgart Tel.: +49 711 5208031
  > mobile: +49 172 6819937
  > skype: detlef.bosau
  > ICQ: 566129673
  > [email protected] http://www.detlef-bosau.de
  >
  >