[ih] Flow Control in IP

[John Day]

For some reason, I didn’t get Detlief’s email, but I am total agreement with Steve’e response  with a few comments.

> On Apr 30, 2024, at 11:27, Steve Crocker via Internet-history <internet-history at elists.isoc.org> wrote:
> 
> Detlef,
> 
> In the Arpanet, the initial implementation of the IMPs had a flow control
> mechanism that attempted to protect the IMP subnet from being overloaded
> with too many packets.  This was implemented via an end-to-end protocol
> between the sending IMP and the receiving IMP that allowed only one message
> per link.

Absolutely, in fact, it was so flow controlled that congestion basically impossible. Also to some extent this was all they could do. If you do the math for 1000 bit packet at 56Kbpss, you will find that with the exception of a couple of lines (like Urbana to Salt Lake), the packet was longer than the distance. So only one packet could be on the line of most links anyway.
> 
> At the host level, the original host-host protocol -- later referred to as
> the Network Control Protocol (NCP) -- implemented virtual bitstreams.  It
> had a flow control mechanism that gave the receiving host control over how
> many bits and messages -- yes, both bits and messages were controlled --
> could be in flight over each connection.

Steve, At the time, I thought NCP was the name of the implementation of the Host-Host Protocol, Network Control Program. Although, you seldom ever heard the Host-Host Protocol mentioned and the distinction was often blurred. More recently, I have seen it referred to as you do. 

There was an early report by Jon Postel called A Survey of ARPANET NCPs, where it was definitely Program. (I remember because while Jon didn’t call it out, it was clear reading the report that there were two categories of NCPs: big ones and little ones. ;-) Big ones were OSs with little or no IPC and small ones were OSs with good IPC.  ;-) An important lesson there.
> 
> For those who do not remember or who have not studied the details of the
> Arpanet:
> 
> The IMPs were the routers.  A host was connected to an IMP.  The unit of
> transmission between a host and an IMP was a "message" of up to about 8,000
> bits.  The IMP receiving (Source IMP) the message from the sending host
> (Source host) chopped it into packets.  Each packet was up to about 1,000
> bits.  The Destination IMP reassembled the packets into a message and
> transmitted it to the Destination host.

Right. For a while, there was a deadlock situation where an IMP could have parts of multi-packet messages received and not enough memory to finish any of them.
> 
> From a protocol perspective, there were multiple layers:
> 
>   1. The IMP-IMP protocol governed the transmission of a packet from one
>   IMP to the next.  It included strong error detection and retransmission if
>   the packet was not acknowledged as having been received correctly.
> 
>   2. The End-to-End IMP protocol (my terminology) governegd the breakdown
>   of a message received from a host into packets and the reassembly of those
>   packets into a message at the destination IMP.  The End-to-End IMP protocol
>   imposed a limit of one message in transit per link.

Yes, in retrospect these were different layers. But as I said in my recent post, when I asked Dave Walden whether layers entered into their thinking when building the IMP subnet, he said no.  Which given their task doing the first packet switch network using what they could from existing datacomm (they didn’t have time to reinvent everything!), this makes sense to me. Layers in either of the senses we think of them today weren’t really important at that point.  (I have also read papers by Davies in the same time period (actually earlier ’66-67) working on the NPL network, where you can see him talking about what they were doing that were layers but they didn’t call them that.)

I still think that the introduction of layers was precipitated by Dijskstra’s THE paper (’68). It is hard to imagine the influence of CACM, when it was the only computer journal. (Did IEEE Trans, on Computers exist yet? It would have been the only other one.) So it was natural that layer first really appear with the problem of writing a device driver for the OSs of the hosts. For the hosts, it was very much into structuring things with layers and calling them that.

> 
>   3. The Host-IMP protocol governed the interaction between a host and its
>   connected IMP, as noted above.  Each message included a link number.  It
>   was intended that processes within two communicating hosts would use the
>   same link number for successive messages.  Thus, the End-to-Eund IMP
>   protocol limited the flow between two host level processes.  This scheme
>   did not limit the overall number of connections, nor did it prevent two
>   processes from using multiple connections if they chose to.  (And, as we
>   experienced, it was indeed possible to flood the IMPs with enough packets
>   to cause a system-wide lockup.)

Steve, one question:  Was IMP-Host a separate feedback loop and the end-to-end IMP-IMP protocol was a separate feedback loop? Although, they would have been clearly linked by the available memory. Or was the linkage tighter than that?

In my conversations with Walden, he was aware that they were over-controlling the subnet to some degree, but he was adamant then (and at the time) that the subnet did not lose data. I remember an early 70s meeting at BBN where he was *very emphatic* about that.  ;-)
> 
>   4. The host-host protocol, as noted above, implemented virtual
>   bitstreams between processes.  It included metering of both the number of
>   bits and the number of messages in transit between the processes.  The
>   receiving host controlled these quantities to avoid being overrun.
> 
> As you can see, there was more than one layer of flow control in the
> original Arpanet.  At the same time, there was strong interest in real-time
> use of the Arpanet for applications where timeliness was paramount and loss
> of a small percentage of packets was tolerable, e.g. speech.  Relatively
> early in the Arpanet development, an additional protocol was added to the
> IMPs in parallel with the End-to-End IMP protocol that did not impose flow
> control but also did not guarantee delivery.

Yes, those were Type 3 messages. When were they added? Was it around 1973. There were previous discussions on this list about how tightly controlled there use was.

>  Layers 2, 3 and 4 above were
> thus accompanied by parallel layers 2r, 3r and 4r (my terminology invented
> for the purpose of this explanation).
> 
> By the time IP was being designed, it was fully understood that it would
> not be possible to achieve perfect reliability within the packet-routing
> layer of the Internet.  Flow control as well as checksums and
> retransmission were included in the TCP layer.  Explicit flow control
> within the packet-routing layer was dropped, but achieved implicitly with
> feedback in the routing protocol via info about queue lengths and dropping
> of packets when memory was exceeded.
69
Correct. Some degree of error and flow control was provided by the IMP-IMP protocol (Data Link Layer) point-to-point. This reduced the error-rate seen by the Transport Layer sufficiently that end-to-end retransmission and flow control were cost-effective. In fact, IEN#1 proposes that ingress flow control was looking like a reasonable congestion control method. (It is for small diameter networks.) It should be noted here that everyone saw congestion as an issue: Davies in 1966, BBN with the design of the IMP subnet, Cyclades in 1972 when they adopted datagrams, etc. CYCLADES lucked out in that Eric Manning of the Univ of Waterloo was visiting IRIA about that time and they gave Waterloo a contract to work on it. They had a brilliant, doomed grad student named Merek Irland, who did some very good work.
> 
> In the early days, memory was quite limited.  

Boy, was it ever!! ;-) There is a very unknown 1968 paper by Denning showing that pooled buffers were orders of magnitude better than static buffers. One of the few no-brainers in this field.  When I recently mentioned this, I was reminded that we did pooled buffers in our first PDP-11 OS, not because we were so smart, but because we didn’t have enough memory to do anything else! ;-) That OS could support a lot of stuff going on at the same time without crashing, because of pooled buffers.

> Over time, Moore's law
> resulted in a complete reversal.  Memory became inexpensive and plentiful.
> Nowadays, the lack of flow control has led to enormously long queues of
> messages waiting to be delivered.  The term of art is bufferbloat.

Taking a lesson from the above and that early on bufferbloat wasn’t a problem because when one ran out of memory the processed blocked, I have suggested that the solution would be static buffers!! ;-) Increase the probability of running out so it isn’t a problem! ;-)

As for the flow control problem in CYCLADES, remember as I said yesterday, CYCLADES was built for a very different purpose than the ARPANET. It was a research platform and this was one of the questions to be considered. It should be said that one of the themes at the time was decentralized, stochastic solutions. Kind of structure the system so that it just worked. There was end-to-end flow control at the Transport Layer and sufficient error control at the Link Layer. The question then what else was needed. To that end, the work CYCLADES gave to Waterloo was exploring that question, and INRIA sponsored a conference on the topic in 1979 by which time Merek Irland had died.

Also, keep in mind that starting around 1975 X.25 was being pushed heavily by the phone companies and it did hop-by-hop flow control in the Network Layer. This was clearly too much and impaired the elasticity of the network. They were also using it as an argument that a Transport Layer was unnecessary, which we opposed strongly. This was directly opposite of what CYCLADES had introduced in 1972, i.e., best-effort datagram network with end-to-end Transport Protocol in the hosts.

Take care,
John

> 
> Steve
> 
> On Tue, Apr 30, 2024 at 3:41 AM Detlef Bosau via Internet-history <
> internet-history at elists.isoc.org> wrote:
> 
>> Dear all,
>> 
>> 
>> may I ask this question?
>> 
>> RFC 791 explicitly states that there is NO flow control in IP.
>> 
>> As far as I see, some packet switching networks provide flow control
>> mechanisms, while others don't. So, I have some rough idea, why this
>> design decision was taken.
>> 
>> I wonder, whether there was a general discussion of this issue in the
>> past, particularly as this issue should have been relevant for the
>> ARPANET as well.
>> 
>> Many thanks for any comments on this one
>> 
>> 
>> Detlef
>> 
>> --
>> Internet-history mailing list
>> Internet-history at elists.isoc.org
>> https://elists.isoc.org/mailman/listinfo/internet-history
>> 
> 
> 
> -- 
> Sent by a Verified
> [image: Sent by a Verified sender]
> <https://wallet.unumid.co/authenticate?referralCode=tcp16fM4W47y>
> sender
> -- 
> Internet-history mailing list
> Internet-history at elists.isoc.org
> https://elists.isoc.org/mailman/listinfo/internet-history