[ih] early networking

Mon Apr 29 12:57:46 PDT 2024

I apologize for leaving this so long without replying, but end of the semester ha been getting in the way.

Yes, I think Brian hit the nail on the head with these two papers. Actually, there is a precursor to INWG60:

Pouzin, L.  Interconnection of Packet Switched Networks, SCH 523.1, INWG 42, Oct 73.

It is probably worth explaining the differences between the ARPANET and CYCLADES because they are significant. I am going to skim over this. One could write a considerable amount on the subtleties of all of this.

As we all know, the ARPANET was the first major packet switching network. It was built to be a production network to lower the cost of computing for ARPA Projects.  Cyclades was built to be a network to do research on networks. Cyclades was a platform, what today would be called a clean-slate approach having seen the ARPANET. (There was considerable interaction between BBN and CYCLADES: As Dave Walden (who led IMP team) told me, so ’they wouldn’t make the same mistakes we did.’ ;-) And Jean-Louis Grangé (led the CIGALE team) spent a fair amount of time at BBN.) 

Because Roberts had gotten considerable resistance from the potential host sites when he proposed just a network of hosts, the IMPs were proposed to ‘off-load’ the network from the hosts. Hence for the ARPANET, the host used the IMP-Host protocol to allocate a ‘connection’ to the destination and then the Host-Host Protocol created a connection between processes in the two machines. The applications were built on top of it. (Note NCP did flow control but no retransmissions because the IMP subnet was reliable.) This is when layers were first introduced. (Again, Walden confirmed for me that there were no layer diagrams of the IMP subnet and I wouldn’t have expected them then.) This is when the idea that networking was IPC began. Walden wrote a very early RFC proposing IPC for a resource sharing network.)

Being a network to do research on networks, the Cyclades team tried to adopt the minimal requirements for a network, and then determine what else was needed.  They adopted the concept proposed by Donald Davies at NPL* and called it datagrams. As we know, Cyclades proposed the 5-layers, we have come to use: Physical, Data Link, Network, Transport, Application. For CYCLADES, the Link Layer was an HDLC-like protocol (which is reliable point-to-point between the CIGALE routers); a 'best-effort' datagram Network Layer, where the sources of loss were congestion and rare memory errors during relaying; and the Transport Layer consisting primarily of a protocol to recover Network Layer losses and flow control between the hosts, which basically provides IPC; and then the applications are built on top of the Transport Layer. (Notice that this first does (at the Data Link Layer) error and flow control over the small scope of point-to-point lines, which limits the errors at the larger scope for the Transport Layer. While for that environment, the Link Layer was reliable, that was not a hard requirement. The requirement was that the Link Layer should keep the error rate well-below that incurred by the Network Layer. (Recovering errors in a larger scope is more expensive than in a smaller scope.) So that here it is possible to say that the Link Layer should have an error-rate much less than the rate expected at the Network Layer, especially since there will be multiple Data Link Layers. But the Data Link Layer doesn’t have to be perfect, it only has to make a ‘best-effort’ as well. Of course, the classic example of this is Ethernet, which is ‘best-effort’ at the Link Layer. (This is the common 90/10 rule (or whatever ratio), that it is easy to get most of the errors but the last rare small amount are expensive so they are left to the larger scope, because they don’t really add that much.

*Yes, Paul Baran had proposed the same idea, but it appears Pouzin was unaware of Baran’s work and says in an interview he adopted the idea from Davies.

Another major difference was that in the ARPANET a host had to be within 10m of the IMP. (Yes, later the DH and VDH interfaces were built.) While in Cyclades, it was assumed that the host was not located near the CIGALE switch (router) and a host could be connected to more than one switch, initially by serial lines. Hence in the ARPANET, a host’s address was (initially) its IMP number (and later its IMP port number), i.e., the interface. What BBN did for the addressing was common for the small networks of the time. Simply enumerating the IMPs as they were installed was sufficient. In Cyclades, a host’s address was the address of the host at the Transport Layer. The Transport Layer addresses had greater scope than the CIGALE addresses in the Network Layer. Multihoming was supported in CYCLADES as a consequence of their architecture.

As Vint has related and is covered in the May 74 paper, he and Bob Kahn were looking at the internetworking problem from the point of view of protocol translation at the boundaries (gateways) between networks. This was known to be a messy problem, an n x n problem. The big question was how to avoid it.  Pouzin’s insight proposed in INWG 42 and INWG 60 is to finesse whole the problem, by noticing that all one had to do was change the name of the Transport Layer to the "Internet Transport Layer.” The serial lines connecting the host to the CIGALE router could simply be replaced by a network and nothing changed. Treat the Transport Layer as an overlay. In this approach, network layer addresses belong to the individual networks and have smaller scope. Internet Transport Layer addresses are Internet addresses of greater scope. (This is what Saltzer’s 1982 paper later called point-of-attachment addresses and node addresses.)

This avoids the protocol translation issue entirely because each network independently supports the overlay layer. The only issue then is defining the minimal requirements the supporting networks must meet. The only changes to the Transport Layer would be potentially larger address fields, longer RTT, and fragmentation at the gateways.  

CYCLADES had solved that problem too quite elegantly. Earlier Elie and Zimmermann working on the Transport Protocol had discovered that the protocol naturally cleaves into data transfer and feedback, ack and flow control decoupled through the state vector. (Actually this applies to every data transfer protocol from HDLC to QUIC.) This is contained in INWG 43 and INWG 61 and dates back to a Transport Protocol document in French from Nov. 72. INWG 43 provides the capability during connection establishment to select whether ack and flow control are present. (Think of the two parts as UDP+IP and an Ack/Credit feedback packet with IP.) Besides supporting multihoming, notice that this solution provides UDP and doesn’t break fragmentation at the boundaries between networks, the way IP does. (lThe fragments use the Transport sequence numbers, not a distinct packet-id. so retransmissions of the same data are still recognized by the destination as part of the same packet. Path MTU Discovery is not necessary.)

In a later email in this thread, Vint pointed at IEN48. It contains two errors. One of which caused by the figures they used. They were trying to be abstract to get a general solution (which is good), but diagrams of links and nodes lead one to conclude that a path ends at the boundary with the node. It doesn’t. It ends where all of the links terminating at that node come together. One needs a layer diagram for that to be apparent. In the ARPANET, we saw that when Tinker AFB joined the net and wanted connections to two IMPs. IEN 48 concludes that addresses name the interface, which they do at the network layer, but not at the Internet Transport Layer.

The other error is that IEN 48 proposes that network addresses can be formed by concatenating lower layer address with an upper layer identifier to form an upper layer address. This one is more subtle and definitely seems like a good idea. However, addresses should be location-dependent and route-independent. (The address should be different to get there by different paths.) A careful analysis of a packet moving through the layers shows that this makes the address route-dependent. This was surprising. We do this all the time! We do it for files!  However, remember that Multics called a file name a pathname. It defines a path, which is what we don’t want.  There is a way to do this but it is a long explanation. 

There are many other simplifications that derive from all of this, but I have already written too much and they will have to left for later. I have already taken too long to get this written.

Take care,
John

> On Apr 20, 2024, at 17:07, Brian E Carpenter <brian.e.carpenter at gmail.com> wrote:
> 
> On 20-Apr-24 23:31, John Day via Internet-history wrote:
>> In the early 70s, people were trying to figure out how to interwork multiple networks of different technologies. What was the solution that was arrived at that led to the current Internet?
> 
> It's for Vint to comment, but I have always understood that Pouzin's two 1974 papers were the recipe. If that's not the case, I really don't understand the question. But it's not what they built. IPv4 is one protocol to rule them all.
> 
> Of course, we have been exploring a closely related question for 30 years: how to interwork two slightly different technologies. One discussion of that is at this rather alarming URL:
> https://github.com/becarpenter/book6/blob/main/3.%20Coexistence%20with%20Legacy%20IPv4/3.%20Coexistence%20with%20Legacy%20IPv4.md .
> 
> L. Pouzin, A Proposal for Interconnecting Packet Switching Networks, dated March 1974, presented at Eurocomp, Brunel University, May 1974. (Also INWG60 and Cyclades SCH 527.)
> 
> L. Pouzin, Interconnection of Packet Switching Networks, 7th Hawaii International Conference on System Sciences, Supplement, pp. 108-109, 1974.
> 
>    Brian
> 
>> I conjectured yesterday that the fundamental solution must have been in hand by the time Cerf and Kahn published their paper.
>> Are you conjecturing that the solution was gateways? and hence protocol translation at the gateways?
>> Take care,
>> John
>>> On Apr 19, 2024, at 23:57, Matt Mathis <matt.mathis at gmail.com> wrote:
>>> 
>>> Due to a missing reply all or something, some of us never saw the beginning of the thread.    What was your precise question?
>>> 
>>> Questions of the form "When was X invented" almost always have answers that are successive approximations.  i.e. The ideas were around for a long time, but didn't really work in the early days.   The final answer ends up depending on splitting hairs on whether version N-k is "functionally the same" and version N, but version N-k-1 is not.   I don't find such definitions very useful, but the thread connecting the historical evolution of a concept is fascinating.  e.g. the evolution of gateways connecting networks over thousands of years is interesting.   Drawing the line between between two and calling one the first modern gateway is not.   That line will move as gateways continue to evolve.
>>> 
>>> Thanks,
>>> --MM--
>>> Evil is defined by mortals who think they know "The Truth" and use force to apply it to others.
>>> -------------------------------------------
>>> Matt Mathis  (Email is best)
>>> Home & mobile: 412-654-7529 please leave a message if you must call.
>>> 
>>> 
>>> 
>>> On Fri, Apr 19, 2024 at 6:33 PM John Day via Internet-history <internet-history at elists.isoc.org <mailto:internet-history at elists.isoc.org>> wrote:
>>>> All week and still don’t have an answer to my question.  That is very unusual for this list. ;-)
>>>> 
>>>> So far there has been a lot of conjecture, not even hearsay, but no facts.
>>>> 
>>>> Having a few moments, I went back to look at the May 1974 paper to see if had any clues, after all the title is "A Protocol for Packet Network Intercommunication.” I assume the answer was found prior to that paper. Is that true?
>>>> 
>>>> I found two major topics there: the early part of the paper spends time discussing protocol translation between networks and the rest of course describes the protocol that became TCP.
>>>> 
>>>> Is one of these insight to the solution?  Just trying to understand what it was.
>>>> 
>>>> Take care,
>>>> John
>>>> 
>>>>> On Apr 14, 2024, at 16:07, John Day <jeanjour at comcast.net <mailto:jeanjour at comcast.net>> wrote:
>>>>> 
>>>>> I am surprised that there was not a lively discussion of this.  It is an honest question. It is unclear to me what precisely the solution to internetworking was?  I don’t want to suggest anything and affect the answer, but I guess I could.
>>>>> 
>>>>> Take care,
>>>>> John
>>>>> 
>>>>>> On Apr 9, 2024, at 06:24, John Day via Internet-history <internet-history at elists.isoc.org <mailto:internet-history at elists.isoc.org>> wrote:
>>>>>> 
>>>>>> sorry forgot to hit reply-all
>>>>>> 
>>>>>>> Begin forwarded message:
>>>>>>> 
>>>>>>> From: John Day <jeanjour at comcast.net <mailto:jeanjour at comcast.net>>
>>>>>>> Subject: Re: [ih] early networking
>>>>>>> Date: April 9, 2024 at 06:22:45 EDT
>>>>>>> To: Sivasubramanian M <6.internet at gmail.com <mailto:6.internet at gmail.com>>
>>>>>>> 
>>>>>>> Nor was there about virtual circuits and X.25, but it was packet switching.
>>>>>>> 
>>>>>>> We have known this was totally different for 50+ years.  That isn’t the question. There are probably lots of ways to solve this problem. What was the solution adopted?
>>>>>>> 
>>>>>>> John
>>>>>>> 
>>>>>>>> On Apr 9, 2024, at 00:06, Sivasubramanian M <6.internet at gmail.com <mailto:6.internet at gmail.com>> wrote:
>>>>>>>> 
>>>>>>>> John,
>>>>>>>> 
>>>>>>>> There was hardly anything redudant, 'multi-path', decentralised, end-to-end free, open about telegrams.  OUR "InterNetWorks"  is something totally and fundamentally different from THEIR telephones and telegrams, hence it is unwise to allow THEM to trace the history of Internetworking to the telegram switches bought by the Army, Navy and Airforce !
>>>>>>>> 
>>>>>>>> On Tue, 9 Apr, 2024, 09:19 John Day, <jeanjour at comcast.net <mailto:jeanjour at comcast.net> <mailto:jeanjour at comcast.net <mailto:jeanjour at comcast.net>>> wrote:
>>>>>>>>> I guess this begs the question, what was the solution to internetworking?
>>>>>>>>> 
>>>>>>>>>> On Apr 8, 2024, at 23:33, Sivasubramanian M via Internet-history <internet-history at elists.isoc.org <mailto:internet-history at elists.isoc.org> <mailto:internet-history at elists.isoc.org <mailto:internet-history at elists.isoc.org>>> wrote:
>>>>>>>>>> 
>>>>>>>>>> This history video narrated by an AI-like voice traces the history of the
>>>>>>>>>> Internet to telegraph switching and makes a passing suggestion that US
>>>>>>>>>> Army, Navy and Airforce instituted automated telegraph switching euipment
>>>>>>>>>> ... this was perhaps the first Internetwork. Clever argument.
>>>>>>>>>> 
>>>>>>>>>> 
>>>>>>>>>> 
>>>>>>>>>> On Tue, 9 Apr, 2024, 03:35 Vint Cerf via Internet-history, <
>>>>>>>>>> internet-history at elists.isoc.org <mailto:internet-history at elists.isoc.org> <mailto:internet-history at elists.isoc.org <mailto:internet-history at elists.isoc.org>>> wrote:
>>>>>>>>>> 
>>>>>>>>>>> interesting pre-Arpanet/Internet history
>>>>>>>>>>> 
>>>>>>>>>>> https://www.youtube.com/watch?v=XFkwWZ6ujy0
>>>>>>>>>>> 
>>>>>>>>>>> --
>>>>>>>>>>> Please send any postal/overnight deliveries to:
>>>>>>>>>>> Vint Cerf
>>>>>>>>>>> Google, LLC
>>>>>>>>>>> 1900 Reston Metro Plaza, 16th Floor
>>>>>>>>>>> Reston, VA 20190
>>>>>>>>>>> +1 (571) 213 1346
>>>>>>>>>>> 
>>>>>>>>>>> 
>>>>>>>>>>> until further notice
>>>>>>>>>>> --
>>>>>>>>>>> Internet-history mailing list
>>>>>>>>>>> Internet-history at elists.isoc.org <mailto:Internet-history at elists.isoc.org> <mailto:Internet-history at elists.isoc.org <mailto:Internet-history at elists.isoc.org>>
>>>>>>>>>>> https://elists.isoc.org/mailman/listinfo/internet-history
>>>>>>>>>>> 
>>>>>>>>>> -- 
>>>>>>>>>> Internet-history mailing list
>>>>>>>>>> Internet-history at elists.isoc.org <mailto:Internet-history at elists.isoc.org> <mailto:Internet-history at elists.isoc.org <mailto:Internet-history at elists.isoc.org>>
>>>>>>>>>> https://elists.isoc.org/mailman/listinfo/internet-history
>>>>>>>>> 
>>>>>>> 
>>>>>> 
>>>>>> -- 
>>>>>> Internet-history mailing list
>>>>>> Internet-history at elists.isoc.org <mailto:Internet-history at elists.isoc.org>
>>>>>> https://elists.isoc.org/mailman/listinfo/internet-history
>>>>> 
>>>> 
>>>> -- 
>>>> Internet-history mailing list
>>>> Internet-history at elists.isoc.org <mailto:Internet-history at elists.isoc.org>
>>>> https://elists.isoc.org/mailman/listinfo/internet-history