It’s worth stepping back slightly from the idea of messages to the idea that enabled the networks we have now, the model of packets. Almost every network now is built on these ideas, but it took well into the 1980s for the weight of networking to shift. This was a change from the previous view; the telephone companies that had created systems which literally spanned the world by the 1960s had at their heart the concept of a circuit.
This makes sense, as at its simplest a telephone is a device which turns the movements of a microphone into electrical signals on a wire, which on the other end are turned back into sound through movement of a speaker. This was an analog system, because what was transmitted was an analogue of the actual sound - when the air pressure on the microphone was higher, the electrical voltage was higher. To enable routing of calls, connecting any caller to any receiver, telephone networks had intermediary devices called switches that created a circuit by effectively plugging a wire from one person’s phone into the wire for another person’s.
To connect different switches trunks of many wires were run between them, allowing the phone company to create a path through the network. For a long time, the phone number itself represented this path - from a starting position, each digit or set of digits became a request to a switch further and further away to connect your circuit to the appropriate line or trunk, eventually finding its way to a point near the location of the receiver where their individual line was selected. Once the path had been found an electrical signal could be shared between two two points reliably.
The great problem with this was allocation of resource. By placing a call you requested a two way channel between you and the other party, and that channel was unreservedly yours, even if one or both parties weren’t speaking. The capacity of the network was how many calls it could handle at any point, and if there wasn’t enough capacity the call simply couldn’t be made. Increasing that capacity was primarily a case of adding more lines between two given points on a path.
As the networks became more reliant on automation to perform the switching processes, large computers like IBMs System/360 became popular control points. The QTAM and later TCAM (Queued/Telecommunication Access Method) systems provided a series of simple message queues which could receive and pass on control messages, keeping them in persistent storage. Still though, the voice data flowed up and down the trunks to get from switch to switch with its own dedicated circuit through the telephone network.
Packet Switched Networks
In the early 1960s in the US, Paul Baran was working as a researcher with the RAND corporation, tasked with building a network for radar communications that could survive destruction of various parts of the system. There were multiple lines between the different radar stations and the radar control locations, with their own switches, but because the network formed a tree, though a tree with some thick branches made of many connections, if part of it was destroyed it would cut off the leaves below it. Baran came up with a model that was more like a road network, where there can be multiple routes from one point to another. Then, to take advantage of this he came up with a system that encoded and decoded the information digitally, and chunked the stream of digital information into discrete, fixed size units, called packets.
A> The term “packet” was actually coined by Donald Davies, a Welsh computer scientist who went on to build the NPL (National Physical Laboratory) network, the first packet network in the UK. Davies independently discovered packet systems while noting the inefficient allocation of access to a mainframe while visiting MIT - each user connected took up an entire phone line, even if they weren’t doing very much. Regardless of whether the machine had extra capacity, if all the phone lines were used, no one else could connect.
By parcelling out streams of data into packets, Baran could take advantage of several benefits, in exchange for having to deal with a certain degree of extra complexity. The model Baran devised was less like a phone call, where all the work was done at the start setting up the path and then allowing data to flow freely down it, and more like the postal service, where the information was parcelled up, and each part placed in an envelope giving the destination. This meant that the packets didn’t all have to use the same path, so if part way through sending a stream of data the situation changed (for example a part of the path was destroyed) the packets could take another available route, without either sender or receiver having to be aware of it. It also meant that the whole network didn’t have to be aware of exactly where everything was, each switch just had to know the best place to forward a packet on to for a given destination.
The packets could also include error correction information to allow the receiver to detect packets that have been mistransmitted. Via use of a checksum, a short code that the sender and receiver could both independently compute from the packet data and check whether they agreed, the receiver could determine the data was bad and re-request or wait for fixed versions if so.
Of course, these benefits didn’t come for free. Sending the address each time in the envelope added size to the message being sent. The fact that packets could take different routes could lead to them arriving in a different order than they were sent in, so the receiver would have to put incoming packets into a buffer and ensure they were sorted into the correct order before delivering the data to the receiving application.
However, the really big benefit was the usage of the wire. Rather than having a dedicated path for each conversation, the communication only used as much of the available bandwidth as the size of the data being sent, plus the overhead for the envelope. If one side didn’t have any data to send, then it didn’t create any packets. This meant that the data from several communications could be multiplexed or combined to go down the same physical wire. The switches in-between could control how much was being sent, and if there wasn’t enough capacity, they could send packets down another path.
This was a remarkably different way of moving data from one place to another. Where the telephone networks created a link between any incoming wire and any outgoing wire, the switches in packet switched networks followed a store and forward model where they would receive a packet from an input, examine it, and determine which was the best output to send it through. This also meant that the structure of the network didn’t have to be pre-defined, or known by the data sender - each hop could make best efforts to move the data towards the destination. This may seem straightforward now, but caused some consternation among telephone engineers for a solid couple of decades.
We then were able to show that it did not take very long for the self-adaptive behavior to occur efficiently so the network would be able to learn quickly where each node was even though each node had zero information at the start. A byproduct of this phenomenon was that network users’ “names” never had to be tied to a physical location. The network could learn where its users were and be able to route traffic efficiently.
- Paul Baran1
The ARPANET
In response to the success of the project, the US Government created a new body, the Information Processing Techniques Office (IPTO), to extend the work done by Baran and his colleagues. It was tasked with the goal of developing components for standardised, reliable networks - in particular an experimental new network called ARPANET. A number of universities were involved in the collaboration around ARPANET, each of which had their own computer system and preferred ways of connecting to the network.
This created a new kind of problem - telephone companies had long kept very tight control over what equipment could be put on to their networks, in many places leasing telephone equipment rather than having their consumers purchase it in a store, even for regular phones. Therefore, they could tightly dictate standards that their network equipment should follow. In the ARPANET, everyone wanted to use their own kit, and it all worked differently.
To help with this, Lawrence Roberts at the IPTO took an idea proposed by Wes Clark to create what he called an Interface Message Processor or IMP. The idea behind this device was that each team could work on connecting their own computer system to the IMP, while the IMP would speak a single language or protocol to other IMPs. This was a practical and brilliant move - by standardising the transportation of data across the network via the IMP, ARPANET could allow different platforms to interoperate without an explosion of mappings between the different systems. The IMPs connecting to other IMPs could route messages flexibly, and implement the adaptive part of the networks, the fault tolerance and multiplexing that made them so powerful.
In 1969, Leonard Kleinrock’s team at UCLA sent the first message across the network to Doug Engelbart’s group at Stanford - though there was a bug, so the first message technically sent was ‘lo’ instead of the intended ‘login’. This was quickly followed up with a successful login and the start of the ARPANET as a real, working system.
To support their work, the designers of the IMP documented the protocol it used to communicate. They had to describe the format of each packet sent across the network, how the IMP should respond in various situations, how problems should be handled and so on. This document was released, modestly, as a Request For Comments, which has become the standard way of documenting and standardising protocols on the internet.
Information is transmitted from HOST to HOST in bundles called messages. A message is any stream of not more than 8080 bits, together with its header. The header is 16 bits and contains the following information:
Destination 5 bits Link 8 bits Trace 1 bit Spare 2 bitsThe destination is the numerical code for the HOST to which the message should be sent. The trace bit signals the IMPs to record status information about the message and send the information back to the NMC (Network Measurement Center, i.e., UCLA). The spare bits are unused.
- RFC 12
The IMP considered what it transported from one computer to another to be messages. The IMP would then divide the messages into individual packets, and the IMP nearest the receiver would reconstruct the packets into complete messages at the other end. This was a powerful new concept; adding layers to networking allowed processes to only have to worry about a limited level of scope without having to understand every detail of the way the communication was facilitated.
In a traditional world, such as that used by the mainframes the telcos used to control their networks, each hop was a complete communication: the sender would send the entire message to an intermediary, the intermediary would send the entire message to the receiver. By using packets, this communication happened on two levels - each packet was a complete communication, but it itself was part of a larger communication - a host would simply send a message to another host, not caring that there were intermediaries who were handling the fragmenting, transmission, and reassembly of individual parts of that message.
Internetworking
Throughout the 60s and 70s there were several other packet networks developed, and there was a strong interesting in internetworking between the ongoing research efforts. Taking design ideas from various networks, particularly CYCLADES in France, Vint Cerf, Bob Kahn and others developed a set of protocols: primarily TCP, the Transmission Control Protocol and IP, the Internet Protocol, to facilitate this internetworking.
Based on the learnings from ARPANET and others, some strong fundamental principles were baked into the design of the protocols with regards to dealing with the diversity of networks and clients. Cerf laid down some clear guidance in his initial specifications:
- Be resistant to failures in intermediate constituent networks and gateways.
- Be unaffected by the maximum message sizes permitted in constituent networks and by intra- and inter-network timing idiosyncrasies.
- Be capable of exactly reconstituting a message stream originating in a foreign HOST.
- Provide for high bandwidth and/or low delay transmission.
- Require no status information in gateways.
- Be relatively easy to implement.
- Permit the receiving HOST to control the flow from the sending HOST.3
These principles all have interesting consequences. Being resistant to failures required the ability to resend parts that were lost, and to handle issues of corrupted packets. Not being limited by maximum message sizes requires the separation of the transmission of the host to host data from the underlying method of transportation, as does the requirement to exactly reconstruct the stream. The lack of status information in gateways means that the status is inferred and that the network would be, in large part, automatically adaptive. The final requirement, that the receiver can control the flow of messages, is a vital point in managing overload and, eventually, congestion.
TCP started out with the same concept of transmitting messages (which would be broken up into packets along the way) from one host to a receiver, but eventually moved to the idea of a virtual circuit - that there was a stream of data coming from one host and going to another without a pre-defined endstop. The protocol was split so that IP handled delivery of individual packets, while TCP added on the sequential stream concept, managed reliable delivery and ordering of the stream, and implemented flow control, to manage the rate at which packets were sent.
By dividing these two into separate protocols, some beneficial functionality could arise - TCP only had to care about managing reliability, not how to actually route a packet through a network, and IP didn’t have to care about reliability at all - it could simply fail if it needed to and rely on the layers above it to resend or respond appropriately.
The eventual system that evolved into the Internet was of a series of networks, communicating via IP between routers - dedicated IP level communication devices that maintained a table that tracked which output links to push packets to for given sets of end addresses. Later on, similar devices such as load balancers would route traffic to specific servers based on higher layer protocols such as HTTP, the web protocol. All this was done to get traffic across this mesh of different services from the network of the consumer to the network of the service they were requesting, and back again.
Distributed Computing
Of course, once multiple machines were available via the network, people wanted to put them to work. One of the first protocols implemented on the ARPANET was RJE, Remote Job Entry. As machines became faster and users wanted results sooner, a style referred to as RPC or Remote Procedure Call developed as a method of sharing networked resources. This was first described in RFC 707 in 1976, with Xerox’s Courier application and Apollo’s Network Computer System influencing many future implementations.
The logic seemed sensible: local programming languages exposed procedures that executed and returned a result, and an RPC extended that facility so that the functionality could be executed on a remote system, and the local code would wait until the result was returned. However, moving beyond one machine added a great many constraints that were not clearly managed by the procedure call concept - there was latency of communication, competition for access, failing systems, failing networks, congested networks, version incompatibilities, and a host of other issues that made RPC facilities somewhat error prone. RPC coupled two different systems together tightly, and put extra application requirements on stable addresses or name resolution systems - so that the caller could find the system it needed to call.
In response to this many standards were developed: CORBA, the Common Object Request Broker Architecture, XML-RPC, SOAP, DCOM and an alphabet soup of others attempted to remove these barriers, and had remarkable success in many areas. However, the realisation over time was that the more these systems developed, the more they started to approach an idea which was gaining ground in other fields: messaging. While networks quietly, or sometimes loudly, revolutionised much of the world, the idea of messaging is next best looked at in perhaps the field it is most closely associated with, and which has seen some of its most successful use: Finance.