[e2e] Yes, there IS a lost layer: The flow control layer, or "deadlock avoidance layer". Re: Lost Layer?

Detlef Bosau detlef.bosau at web.de
Mon Jan 13 03:46:08 PST 2014

Am 10.01.2014 20:34, schrieb Detlef Bosau:
> I would like to discuss the talk
> http://rina.tssg.org/docs/JohnDay-LostLayer120306.pdf
> given by John Day.
> What do you think, e.g., of the claim
>>>> TCP was split in the Wrong Direction!
>> • It is one layer, not two.
>> – IP was a bad idea.
> Detlef

Perhaps, the problem of a "lost layer" becomes much more clear when we
realize what is actually missing.

In order to make this clear, we could have a look at a typical paper
which does things completely wrong:

"An Improved Greedy Routing Algorithmfor Grid using Pheromone-Based
Landmarks" by Lada-On Lertsuwanakul and Herwig Unger,
World Academy of Science, Engineering and Technology Vol:35 2009-11-25

The idea behind this work is certainly some kind of "ant routing". And
despite all other considerations, the major fault is to regard a data
flow as set of blocks, "ants".

It doesn't really matter whether we talk about data flows or media flows

What is really required by the user/application (sic!!!!) is a flow that
can be successfully used or rebuilt from the packets, be it a byte flow
(in case of TCP) or a media flow (in case of RTP/UDP), a simple heap of
packets is of absolutely no use for the receiver, when the original flow
cannot be rebuilt. And because a receiver has finite (maybe huge but
finite!) space, the heap of received packets must not grow beyond all
limits, it even must not exceed the space which is available for flow
reconstruction AND it mus respect the simple fact that the receiver's
buffer space can only be delivered from data, when data can be forwarded
to the application in proper order, be it temporal order or the original
byte sequence.

Exactly that, and ONLY that, is the reason for both, the flow control
window AND the semantics of the TCP ACK field ("next byte expected") in
RFC 793.

Offering too much load to the receiver is not only a matter of space, it
is particularly a matter of data being available for forwarding to the
application. If this cannot happen and we cannot free buffer, we may see
a situation where the buffer is occupied and canot accept further data -
while no data can be forwarded to the application, and hence no buffer
space can be freed, because some indispensable packet is missing.

This is a typical deadlock situation.

And exactly this is the task of a flow control layer: Avoiding the
aforementioned deadlock. Call it "flow control layer" or "dead lock
avoidance layer", whatever you prefer.

The problem is extremely generic, it is a twist of state variables being
asynchronous in distributed systems, quite generally known as the "two
army problem".

In TCP and RFC 793 we work around this problem by killing flows after a
user defined timeout when nothing happens AND (certainly more important)
by, very literally, do-or-die Go Back N. (The receiver expects byte
4711, so send the packet - or die. Period.)

That's for the end points. And only for the end points.

That's not for flow control along the path. This is an orthogonal (and
in my opinion in TCP not yet solved) problem.

An interesting twist of the latter problem is that we need sufficiently
large buffers at the receiver for accepting all data in flight in case
of LFN and huge latency throughput products. Hence, we abuse the
"deadlock avoidance" window for flow control along the path.

As a consequence, TCP receivers must provide sufficiently large buffers
in order to allow the flow to utilize the path capacity. This lead to
some approaches like the "Remote Socket Architecture" by Schlager,
Wolisz. Why the heck does a smartphone with 10 kByte receiver buffer
space restrict a sender's data rate because it cannot keep a the path's
"whole delay throughput product"?

So the problem is that we miss a flow control layer. And we work around
this missing layer by intertwining flow control, rate control and
congestion control and by glueing things together which MUST be kept apart.

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