[e2e] A Cute Story. Or: How to talk completely at cross purposes. Re: [ih] When was Go Back N adopted by TCP

Detlef Bosau detlef.bosau at web.de
Tue Jun 3 05:43:51 PDT 2014

I presume that I'm allowed to forward some mail by DPR here to the list
(if not, DPR may kill me...), however the original mail was sent to the
Internet History list and therefore actually intended to reach the public.

A quick summary at the beginning: Yes, TCP doesn't manage for sent
packets a retransmission queue with copies of the sent packets but
maintains an unacknowledged data queue and does GBN basically. This
seems to be in contrast to RFC 793, but that's life.

A much more important insight into the history of TCP is the "workload
discussion" as conducted by Raj Jain and Van Jacobson.
Unfortunately, both talk completely at cross purposes and have
completely different goals......

Having read the congavoid paper, I noticed that VJ refers to Jains CUTE
algorithm in the context of how a flow shall reach equilibrium.

Unfortunately, this doesn't really make sense, because slow start and
CUTE pursue different goals.

- Van Jacobson asks how a flow should reach equlibrium,
- Raj Jain assumes a flow to be in equilibrium and asks which workload
makes the flow work with an optimum performance.

We often mix up "stationary" and "stable". To my understanding, for a
queueing system "being stable" means "being stationary", i.e.
the queueing system is positively recurrent, i.e., roughly, in human
speech: None of the queue lengths will stay beyond all limits for all
times but there is a probability > 0 for a queue to reach a finite
length at any time.

A queueing system is stationary when its arrival rate doesn't
permanently exceed its service rate, this is actually nothing else than
the "self clocking mechanism" and the equilibrium VJ is talking about.

>From RJ's papers I see a focus on the workload and the perfomance of
queueing systems. A possible performance metric is the quotient
p = average throughput / average sojourn time.

If the workload is too little, operators will have idle times, the
system is not fully loaded. (=> sojourn time acceptable, throughput to
If the workload is too large, too much jobs are not being serviced but
reside in queues. (=> throughput fine, sojourn time too large.)

>From Jain's work we conclude that a queueing system has an optimum
workload - which can be assessed by probing.
=> Set a workload, assess the system's performance, adjust the workload.

Van Jacobson will reach the equilibrium.
=> Set a workload, if we see drops, the workload is too large.

As a consequence, a system may stay perfectly in equilibrium state while
seeing buffer bloat in the sense of "a packet's queueing time is more
than a half of the packet's sojourne time.

I don't know yet, perhaps someone can comment on this one, whether
buffer bloat will affect a system's performance. (My gut feeling is:
"Yes it will". Because the sojourn time grows inadequately large.)

The other, more important, consequence is that probing for
"dropfreeness" of a system does not necessarily mean the same as
"probing for optimum performance".


Am 20.05.2014 16:49, schrieb David P. Reed:
> I really appreciate the work being done to reconstruct the diverse set
> of implementations of the end to end TCP flow, congestion, and
> measurement specs.
> This work might be a new approach to creating a history of the
> Internet... meaning a new way to do what history of technology does best.
> I'd argue that one could award a PhD for that contribution when it
> reaches a stage of completion such that others can use it to study the
> past. As a work of historical impact it needs citation and commentary.
> Worth thinking about how to add citation and commentary to a
> simulation - something like knuth's literate programming but for
> protocol systems.
> Far better than a list of who did what when, or a set of battles. It's
> a contribution to history of the ideas...
> On May 20, 2014, Detlef Bosau <detlef.bosau at web.de> wrote:
>     Am 19.05.2014 17:02, schrieb Craig Partridge:
>         Hi Detlef: I don't keep the 4.3bsd code around anymore, but
>         here's my recollection of what the code did. 4.3BSD had one
>         round-trip timeout (RTO) counter per TCP connection.
>     That's the way I find it in the NS2.
>         On round-trip timeout, send 1MSS of data starting at the
>         lowest outstanding sequence number.
>     Which is not yet GBN in its "pure" form, but actually it is, because
>     CWND is increased with every new ack. And when you call "send_much" when
>     a new ack arrives (I had a glance at the BSD code myself some years ago,
>     the routines are named equally there, as far as I've seen, the ns2 cod
>      e
>     and the BSD code are extremely similar) the behaviour resembles GBN very
>     much.
>         Set the RTO counter to the next increment. Once an ack is
>         received, update the sequence numbers and begin slow start
>         again. What I don't remember is whether 4.3bsd kept track of
>         multiple outstanding losses and fixed all of them before slow
>         start or not.
>     OMG. ;-) Who else should remember this, if not Van himself our you?
>     However, first of all I have to thank for all the answers here.
>     Detlef
> -- Sent from my Android device with *K-@ Mail
> <https://play.google.com/store/apps/details?id=com.onegravity.k10.pro2>*.
> Please excuse my brevity. 

Detlef Bosau
Galileistraße 30   
70565 Stuttgart                            Tel.:   +49 711 5208031
                                           mobile: +49 172 6819937
                                           skype:     detlef.bosau
                                           ICQ:          566129673
detlef.bosau at web.de                     http://www.detlef-bosau.de

More information about the end2end-interest mailing list