Printed in the Proceedings of IFIP Congress Stockholm August 1974, pp 147-150
Donald W. DAVIES
The few packet switched data communication networks now in existence will soon be joined by many others which are at an advanced stage of planning or development.
The paper compares message and packet switching and draws conclusions about their future development.
A packet-switched communication system is described in terms of a 'primitive packet switch' to which a user-protocol is added for (multiplexed) communication between computers. If the network handles simple terminals, it is complicated by the need for extra facilities and the concept of a 'virtual circuit' necessarily enters into the design. Existing and planned packet-switched networks differ in the extent and the details of the facilities which they add to the primitive packet switch.
The implications for standardisation and interworking are described.
In the period since the 1971 IFIP Congress, packet switched data networks have moved from a tentative and uncertain position to become a matter of some interest in the computer world. In addition to the existing packet switched systems there are many others at a more or less advanced stage of planning or development. The close relationship between packet and message switching and the fact that many private networks use similar principles may lead to confusion about what precisely is meant by packet switching. The proposed networks offer rather varied facilities to their users - a fact which could lead to difficulties when international standardisation and interworking become a live issue. This paper attempts to clarify some of these points.
The prime existing example of a packet switched network is the ARPA network which comprises a data communication subsystem and a collection of. host computers which together make up a resource sharing network. Its design and properties have been well explained in the literature [1]. The packet switched local network at NPL addresses the same fundamental communication issues, but on a small scale [2]. Its distinctive feature is the incorporation of simple terminals as an integral part of the total design. This feature led to the extension through to the terminals of the flow control properties of the main network and the network's control signals, which greatly facilitates the connection of new types of terminal.
Among the networks in various stages of planning and implementation are the British Post Office's Experimental Packet Switched Service (EPSS), the French PTT Reseau a Commutation par Pacquets (RCP) and the other French official project called Cyclades with its packet switched subnet called Cigale. There is an international network project in Europe known as COST 11 or the European Informatics Network (EIN) and commercial derivatives of the ARPA network are planned to be operated as common carrier services in USA.
These networks vary considerably in their design and the facilities they offer to the users. Perhaps the only feature they all have in common is the employment of well-formatted, relatively short message units called 'packets'. But the same feature is shared by a number of private networks serving time-sharing systems, bank accounting, airline reservation and other functions.
The concept of packet switching which has been developed in different ways by different people was, to my knowledge, first explained in its modern form in Paul Baran's 1964 report 'On Distributed Communications' [3]. The application to switched data networks was elaborated by the NPL group in publications dating from 1967. Message switching, on the other hand, has a longer history, derived from the handling of telegraph messages, at first entirely manually and then by tearing off punched paper tapes And carrying them across the room to transmitters. By mechanising the remaining manual functions the automatic message switch was derived. Thus packet switching employed the processing and storage power of computers to create a new kind of service appropriate to computers whereas message switching concentrated on reproducing, with improvements, an existing service derived, by gradual changes, from a manually operated telegraph system.
The SITA network, operated for a large group of airlines, includes a 'high-level network' which provides message switching and a service very close to packet switching which is used to extend computer services, principally seat-reservations, to distant terminals. Other networks of the same type are the Australian Post Office's Common User Data Network (CUDN)[QUESTIONABLE /RDM] and a network operated by CTNE in Spain.
The main consideration in a message switched network is the certainty of delivering a message which has been entrusted to it. To this end, magnetic drum or disc storage is used to capture each message reliably in addition to handling it in duplicate in two computer's main stores. A log is kept of incoming messages so that the course of events can be reconstructed after a failure. Considerable delays are accepted to hold messages sent to an inoperative or busy terminal for later delivery and to smooth out the flow on heavily loaded lines over a moderately long time-scale. Because the delays are significant, priority levels are often provided. The delays go hand in hand with the large amounts of storage, quite different from packet switching where the storage capacity of switching nodes is deliberately held low.
Message switching systems usually provide for multiaddressing because in a widespread system this can be done with more economy in line usage than by sending many copies from the source. This comes from a situation in which line costs are dominant. Similar properties have not been incorporated in packet switching because the computer systems which they serve are usually selective in the way they distribute information. Requirements to broadcast messages to a number of users are not frequent enough to warrant a special mechanism in the communication subnet even if the saving of line coats were significant.
We see therefore that message switching provides a number of facilities valuable for messages passing between people. Saving of line costs seems to have been a major factor in the design, leading to the spreading of load by storage (and therefore delay) and the multi-address mechanism. The lack of acknowledgement from end to end within the network is associated with a complicated switch, able to assure delivery.
It is curious, however, that by following so closely the properties of the manual centres they replaced, some facilities which computers can offer to their users have been neglected. For example, the users get little help in formatting the messages, and this makes the system inaccessible to the casual user.
In the future I would expect a message switching system to be much more integrated with the composing and editing of messages, and their storage and retrieval from filing systems. These are all features which we have built into a service called 'Scrapbook' attached to the NPL packet switched network and which users have found very convenient. Today's message switching services mostly deliver the facilities which were familiar from telegraphy.
Suppose now that a data communication system is available which can satisfactorily serve computers as well as simple terminals. It then becomes possible to provide all the services of message switching by service computers attached to the data network and, making use of the greater volume of traffic occasioned by computer systems, message switching should be faster and cheaper. It will also become integrated with systems for handling messages within organisations -- for composing, editing, filing and printing them -- to the point that exchanging messages within one site becomes very similar to exchanging messages with distant sites. These developments will tend to submerge message switching in the general range of computer services. The development is already visible in the way that the mail box facility of the ARPA network is being developed and used and in new modes of communication such as 'teleconferencing'.
The technology of packet switching is developing rapidly and includes such things as routing algorithms, flow control, congestion control and the optimization of network layout. But these are mainly the problems of the network designer. To the user, the service provided can be regarded very simply as the acceptance and delivery of well-formatted packets. For the computer attached to the system (the host computer) a simple protocol is also required for the immediate link with the network, to deal with local flow and error control and with those control signals which are outside the stream of data packets.
A packet switched system with these simple functions can be called a 'primitive packet switch'. It lacks many of the properties that might be thought desirable. For example, a packet is launched into the network without knowing the state of the receiving device ,and a stream of packets might be sent which cannot be delivered. Furthermore, packets might be lost because the extremely high standards of assurance of delivery characteristic of message switching have not been built in. There is no doubt that the primitive packet switch does not provide all the data communication functions that are desirable. In particular, a simple terminal cannot use it because it requires fully formatted packets and has no end-to-end flow control. A slow terminal could be swamped by incoming packets.
Consider two computers using the primitive packet switch to transport data between them. The switch must be regarded as a slightly unreliable channel which, though it is unlikely to deliver a garbled packets, may lose a packet or duplicate one in transit. It can also change the packet sequence, on occasion, because of the variable delay due to routing and to retransmission following an error.
It is possible to construct an end-to-end protocol (host to host) which can deal effectively with all these deficiencies of the network. It can deal easily with large messages by breaking them into streams of packets, it gives them sequence numbers and it checks and reorders the received sequence, calling for retransmission when the packet is sufficiently overdue to be regarded as lost. Error checking between the two ends can also be added if the need is felt for this extra precaution.
Such a protocol is necessarily somewhat elaborate and must use a moderate amount of storage to deal with resequencing and retransmission if the data rate is high.
But it is extremely important to realise that the bulk transmission of data between computers is only a small part of the total requirements for data communication which such networks are intended to meet. The vast majority of terminals will be very simple with a small and intermittent data rate. It is important to keep in mind the cash dispenser, credit card validation and so forth, where a transaction involves a few messages in a fixed format passing alternately between the ends. For these applications the elaborate protocol appropriate to a multi-access computer would not be inappropriate. They can virtually use the primitive packet switch alone, with their own simple protocol added.
It therefore becomes questionable whether the communication network need have any concern with or knowledge of the protocols of its users. If all the users were large computers this would not be so and if all the users were the extremely simple terminals with fixed applications, each talking to a designated distant computer service, it would again not be so. But the issue is complicated by a third kind of terminal.
We refer now to a 'general purpose user terminal' on the network. This would typically be a VDU or keyboard and printer and its purpose would be to engage in conversational interactions with a number of distant computers, the destination being chosen by the subscriber himself. This kind of terminal is familiar to the telecommunications engineer because it has many of the properties of the telephone. The general purpose user terminal requires the logical equivalent of a circuit or path between itself and the computer with which it is corresponding. This has been called a 'virtual circuit' or sometimes a 'link'. A protocol is required to set up the link between the terminal and what is effectively a 'port' on the computer in addition to the procedure used over the link when it has been established. Since the terminal is, by definition, simple the protocols can best be carried out by some component of the network itself.
A complication in the handling of these general purpose terminals is the wide variation in the detailed design of the terminal device. In the ARPA network an attempt is made to reduce them to a common form of 'network virtual terminal' by conversion within the TIP, but the wide variation in terminal types makes this only partially successful. In the NPL network we made the adjustment to different terminal types within the serving computer, which limits the computer to the set of terminal types which it can recognise, five in the case of Scrapbook. The concept of a general purpose terminal is then no longer valid. Standardisation of the functions of a general purpose VDU is surely necessary and perhaps agreement on a limited number of real terminal types may displace the need for a network virtual terminal.
At all events, the apparently simple 'general purpose user terminal' gives the network much more work to do than the subscriber's computer. In the NPL network a 'terminal processor' was defined for this purpose and it was not very complex because of help from the hardware of the distribution network (which was specially engineered for the purpose) and the method by which we dealt with variations in the terminal.
A logically simple system design results from treating the terminal processor as just another computer attached to the network [4]. In the NPL network, although the TP was treated in this way it was actually implemented by, the same computer as the packet switch. This scheme implies that the terminal processor must contain within it the same kind of 'transmission control program' that is used in subscriber's computers to implement the end-to-end protocol mentioned before. For this reason a network, if it handles simple terminals in this way cannot be unaware of the protocols used by subscribing computers.
The first packet switching networks to be designed could not be constrained by thoughts of future standards and the problems of interworking. It was sufficient, at this stage, to prove the viability and economy of the method. Now that many networks are in prospect, questions of interworking have become extremely topical.
The ideal would be to have international agreement on standards covering interfaces and protocols at all levels of the networks. But this has not been achieved in the telephone case. There is flexibility in the design of telephone systems, subject to the requirements for interworking. Even if standardisation at all levels could be achieved, this would take many years and the rapid growth of data communication would have resulted in the meantime in a large number of different networks which had not had the benefit of the standards. It therefore seems desirable to leave as much flexibility as possible for individual design, standardising first at a level which most affects the users.
The critical question is the level in the hierarchy of protocols at which the networks interact. We have described above a view of a packet switched data communication network as a primitive packet switch to which has been added a user-protocol for interaction between computers.
To the users, a set of interconnected networks (of varied design) must appear as a single, well-defined service. We do not expect to know the details of different countries' telephone systems before making an international telephone call. There are basically two alternatives. Either the networks they can be connected as primitive packet switches and used with a common end-to-end user protocol or some means must be found to connect the networks by the higher level protocols. In the second scheme, each network will see, across the inter-network boundary, the equivalent of a subscriber's computer.
The difficulty with the second approach is that the facilities provided by each network at the higher level of protocol are all different. It becomes extremely difficult, if not impossible, to map the facilities of one network on another and when this process has been carried through several networks, it may become unclear to the end users exactly what facilities are being provided. For example, a description of the Cyclades protocol provided by the 'Station de Transport' can be compared with the protocols to be provided by EPSS or the Host-Host protocol of the ARPA Network. Though they are all capable of serving computers adequately, it is far from clear how to map one into the other.
The other approach in which the interconnected networks form a combined 'primitive packet switch' is much more clearly defined. A user protocol can be designed which is resilient to the differences of design in individual networks. For example it should handle networks which keep their packets in correct sequence and others which do not. It should, in principle, make use of networks with packets of different maximum length.
Suppose, however, that standardisation at more than one level proves to be possible. The achievement of a common user-protocol will not have been wasted. The ingenuity of design which enables it to be resilient to variations in the packet switch will still be useful in dealing with those networks that were constructed before the standard came into operation. For these networks, their existing user protocols will be kept in use, alongside the new inter-network protocol.
The practical possibility of an 'internetwork protocol' is demonstrated by the proposals [5] which are being discussed by IFIP committee TC 6.1.
Communication networks which only offer packet-level communication are not greatly affected by the adoption of an inter-network protocol. But where the communication subsystem also handles simple terminals as in the TIP or terminal processor, a profound change will be needed for interworking.
Not only must the new inter-network protocol be adopted, but unified methods are needed for setting up and clearing a call, and for dealing with the incompatibility of 'simple' terminals. It is possible that some kind of conversion can be made from the scheme by which these terminals are handled in an older network, but this remains to be proved. At the time of adoption of an inter-network standard it may be necessary, in existing networks, to have two procedures available for handling terminals.
The successful operation of an inter-network protocol depends on making the set of networks function as a combined 'primitive packet switch'. This, in turn, requires a number of agreements between network operators at this packet-switching level.
Agreement on the numbering of addressing of terminals is needed for interworking. Existing routing methods in constituent networks can still continue to operate, and the inter-network routing required to bring the packet to the destination network can be handled as a separate problem. More than one level of routing algorithm will, in any case, be necessary for large individual networks so the extension to inter-network routing will not involve new principles.
Flow control to avoid network congestion seems (both in simulation studies and in practice) not to require a separate overall network control system. This gives a reasonable hope that 'networks of networks' will not introduce extra flow control problems. It is important to discover whether this is true, perhaps by extensive simulation experiments.
Agreements are also required on the exchange of service signals, both those of local significance at the gateway and messages between network control centres concerning congestion, breakdown, etc.
There should also be agreement on tariff principles and accounting.
The packet format can differ in different networks but when packets are exchanged at a boundary they should be regarded as mapping into an internationally agreed packet format. The actual conversion used between networks could be agreed bilaterally in order to exploit any similarities between the networks being connected, and the standard format would then be used only as a means for defining the significance of fields.
Each network will have its own maximum packet size but an international agreement on a common maximum for future networks would clearly be desirable. The inter-network protocol can take account of variations between existing networks but a common standard for new networks produces greater efficiency in packet handling.
Supposing that a network employs smaller packets than the standard, then it must fragment incoming packets and the question arises whether it should be required to reassemble them to conform with the standard maximum packet size if they are in transit between other networks. It seems desirable to insist on this reassembly because it puts pressure on networks to change in due course to the standard. As an alternative to reassembly special paths can be provided between gateways for packets in transit up to the generally agreed maximum size.
There seems a strong case for attempting an agreement on maximum packet size as early as possible, to avoid conversion problems. Theoretical studies intended to derive an optimum packet size have shown a broad maximum, giving a wide choice, but the assumptions leave room for argument. Trends to higher speed transmission and cheaper stores will push up the optimum size. Our ignorance of future traffic patterns makes real optimisation impractical. General agreement on a maximum of 255 bytes of message field would seem to be within reach because this value has been used in several recent designs.
Public networks for data communication are needed to avoid the expensive proliferation of separate, incompatible private networks. The various public networks must then be able to interwork in order to provide a worthwhile service.
Among the kinds of data communication networks being widely developed at present are those employing store and forward methods. Message switching derived from telegraphy will, we believe be absorbed into the range of computer-based services that can be provided through the medium of an economical data communications system. Packet switching is specifically designed for computer communications and could be the basis of a widespread communications system serving computers and their users.
It seems unlikely that complete standardisation of the interfaces and protocols of data communication networks will be achieved, but interworking is possible with much less. As a first step it is proposed to agree an end-to-end user protocol for flow control, error control and the re-sequencing of packets. To operate this protocol requires sufficient agreement at a lower level to enable packets to be delivered to any destination. A start has been made on the study of the user protocol by IFIP working group TC 6.1. The handling of 'simple' terminals by the networks is a difficult remaining problem.
[1] L.G. Roberts and B.D. Wessler, Computer network development to achieve resource sharing, AFIPS SJCC Conference Proceedings, vol.36, May 1970, 543. (Together with four associated papers in the proceedings).Davies
[2] R.A. Scantlebury, A model for the local area of a data communication network - objectives and hardware organisation, Proc. ACM Symposium on Data Communications, October 1969, 179.
[3] P. Baran, On distributed communications, Rand Corporation Memorandum RM-3420-PR, August 1964.
[4] R.A. Scantlebury and P.T. Wilkinson. The design of a switching system to allow remote access to computer services by other computers and terminal devices, Proc. ACM/IEEE 2nd Symposium on Problems in the Optimization of Data Communication Systems, Palo Alto, October 1971, 160.
[5] V. Cerf and R. Kahn, Host and process level protocols for inter-network communication, ARPA Network Information Centre Paper No. 18764, September 1973.