ABSTRACT
The NPL Data Communication Network provides a "common carrier" service on the Laboratory site. It is organized so as to offer communications facilities both to computers and to terminal devices of a wide variety, using the store-and-forward "packet switched" method of operation. At present there are 12 computers attached to the network, some of which make services available to terminals and to other computers; there are also about 75 terminals attached.
The logical structure of the network provides separate mechanisms for handling computer and terminal subscribers. Two levels of protocol have been designed to control the intercommunication of computers and the communication between terminals and computers.
1. INTRODUCTION
The NPL Data Communication Network, which has been operational in its present form since June 1975 provides a "common carrier" service to the community of scientists and administration staff within the Laboratory. The Laboratory itself has a staff complement of some 1500 persons and covers an area of 32 hectares.
The purpose of the network is to provide switched digital data communication facilities between the various computers and used on the site, and between computers and various terminal devices, such as teletypes, data loggers, paper-tape preparation equipment etc. The network employs the store-and-forward packet switching method of operation.
At this time the NPL network has only one switching centre, analogous to an isolated local telephone exchange
The system represents one element of a national data network scheme proposed by NPL. Its construction, started in 1968, formed part of the research program of the Division of Computer Science, which has been conducting research into the principles of "packet-switching networks since 1966 [1] [2] [3] [4].
The network proposals put forward by NPL are similar in kind to the ARPA network in the USA, [5] [6] , and simulation studies based on these proposals are being carried out as part of the programme of work of Computer Science Division [7].
2. THE NOTION OF HIERARCHIES
An earlier paper [4] put forward the notion of assigning the various functions present in a complex communication system, to various levels in a nested hierarchy. The idea is illustrated in Figure 1 which identifies some of the layers in such an hierarchy that might be used for communication between a number of computers through a common carrier network (often referred to as the sub-net). The sub-net itself may have such layers within it, but these will not be apparent to the user.
The layers identified in the figure perform the following tasks:-
a) administration of the physical transmission medium, possibly including automatic error detection and recovery,
b) signalling between the subscriber computer and the communication network in order to effect delivery of the data,
c) administration of the liaison between the computers, perhaps effected within their operating systems,
d) intercourse between user programs or processes being executed in the computers.
This type of structure can be found in many networks, such as the French CYCLADES network [8], the ARPA network in the USA and the British Post Office Experimental Packet Switched Service [9].
If one maps, say the ARPA network onto this model, the subscribers are equivalent to Hosts, function (b) becomes the "Host-IMP" protocol, and. function (c) 'becomes the "Host-Host" protocol. If the communication sub-net is a packet switching network as in the case of the ARPA net-handling simple terminal devices like a teletype.
This problem can be resolved by first noticing that the human interface to the system exists at level (d) (ie with processes controlling locally connected terminals), and then by taking the step of creating within the sub-net a "logical Host" whose sole function is to handle terminals (eg the ARPA TIP [10] includes this function).
3. THE NPL NETWORK
The logical form of the NPL network is shown in Figure 2. having but one switching centre, the Packet Switch (PS). Subscribing computers (known as User Machines or UMs) communicate with each other by passing packets via the Packet Switch. Terminal devices, when not directly attached to a subscribing User Machine, can gain access to the network by means of the Terminal Processor (TP) which appears logically to the Packet Switch like any other User Machine, Physically the Terminal Processor co-exists with the Packet Switch in the same computer.
It will be noticed, that as a result of the above organisation, subscribers to the NPL network fall into two classes, namely User Machines and Terminals. The latter cannot be expected to generate packets in the required formats (see later) nor administer the various protocols. These functions are performed on behalf of the terminals by the Terminal Processor. The communication between terminals and the Terminal Processor is therefore conducted in a more traditional character-at-a-time mode. However, just as the individual functions of the Packet Switch and the Terminal Processor share the same communications processor, so too are the two classes of customer serviced by a common transmission bearer system.
Within the laboratory, high speed digital transmission and multiplexing is employed, a detailed description of which appears in reference [2]. Attachment of subscribers to the network is achieved by employing one of two types of Network Termination Unit (the choice depending on the above mentioned classes), which has outlets for subscribers equipment conforming either to BS 4421 [11] or to CCITT recommendation V24. Additionally, Terminal users are provided with a control panel having four illuminated pushbuttons, for the purpose of signaling to the Terminal Processor and allowing the user to see the current "state" of the Network Termination Unit.
In the case of User Machines this kind of signalling is accomplished, at the "packet" level (b in Fig l). They are therefore provided with a much simpler panel which has only a single switch allowing for manual isolation from the network.
4. THE PACKET SWITCH FUNCTIONS AND PROTOCOL
The principal function of the NPL Packet Switch (PS) is to allow the attached UMs to communicate with each other by sending and receving packets. UMs each have a single full-duplex link over which they may transfer packets to and from the PS. Communication between a pair of Ums, to carry out some particular user task (say), may involve the exchange of many packets. A UM executing several user tasks simultaneously may be handling many streams of packets to and from other UMs, and these streams will become interleaved on the single link from the UM to the PS. Every packet must therefore be handled as an independent concept.
A packet correctly received by the PS is placed at the end of a queue of packets awaiting output to the specified destination UM. The independence criterion requires that the destination address should appear in each packet dispatched to the PS. Similarly, the address of the originator must appear in every packet received from the PS.
All such information needed for the routing, identification and management of packets is collected into a fixed-format "header" section which precedes the main body (the "data" section) of each packet. The data section contains the specific information to be communicated from one UM to another. The PS is completely transparent to this part of a packet, making no examination of its content and placing no limitation thereon, apart from one of maximum overall size.
The packet format adopted for the NPL network is shown in Figure 3a. A 16 bit field is provided for the destination address, in the case of packets sent to the PS, or the originating UM address in the converse case. (it is clearly not essential to provide space for both addresses in packets traversing local links).
The communications hardware of the network is designed to handle individual octets of data. Packets therefore travel between UMs and the PS as streams of octets. The header must consist of an integral number of octets. The header section contains a field which specifies the number of octets, in the range 1 to 255 inclusive, in the data section. This Byte Count is intended to facilitate packet handling, for example it allows the loss or gain of octets to be detected.
The PS can inform UMs of errors in received packets, this information being conveyed in the Type Code field which is present on every packet. Figure 3a lists the packet types, which are distinguished by code values held in this field. Normal UM-UM traffic is indicated by the type "DATA" and this is the only packet type that a UM may generate. DATA packets are forwarded unchanged by the PS except that the destination address is replaced by that of the source. However, if a packet cannot be forwarded to its destination because one of the four kinds of error
Indicated in Figure 3a has occurred, then the PS will return it in its entirety to the originator with only the type code value changed to indicate the reason for non-delivery (ie DUD, DNA, ERBC or ERTC). Such packets are returned by placing them at the end of the queue of packets awaiting output to the originating UM.
Each UM is connected to the PS via a Network Termination Unit (which is referred to as "PCU-B" for historical reasons). A PCU-B is physically adjacent to its UM and the actual connection is achieved by means of a pair of British Standard Interfaces (BS4421). The PS is able to exchange special "status" signals with the PCU-B, enabling it to control the flow of packets along the link and to monitor or change the operational state of the link. These status signals represent an "internal protocol" of the network since they cannot be directly sent or received by a UM. However, some of these protocol functions are made available indirectly for a UM by the PCU-B, which can change, or respond to changes, in the state of certain control lines present in the BS interface.
One interface control line is used to signal the end of a packet. This data-independent mechanism permits the packet length checks mentioned above to he made. It is also essential in order to recover quickly from loss of packet synchronism. Other interface lines control the transfer of data octets in either direction; yet others permit each side of the interface to inform the other of its operational state. The main PS protocol, formed by the packet exchanges, does not therefore have to deal with natters of link control since these are all managed by the low-level, hardware-dependent "protocol".
Instantaneous flow control is achieved by the use of two status codes which enable the PS to set a PCU-B into a "sending" and "receiving" state (these two states existing independently because the link is full-duplex). When its PCU-B is in the sending state, the UM is allowed to transmit a single packet in its own time and at any convenient rate up to a limit determined by the effective bandwidth of the link. Generation of the end of packet signal by the UM causes the PCU-B to leave the sending state and transmit a status code to the PS. Similarly, Packet input timing is under the control of a UM once its PCU-B is in the "receiving" state. There is, however, a time limit on packet output imposed by the PS in order to prevent faulty UM operation from unduly degrading network throughput for other UMs by locking down packet buffers.
0 DATA Normal computer-computer data traffic
1 DHA Destination not currently available
2 DUB Destination undefined (nonexistent)
3 ERBC Error found in byte count (mismated)
4 ERTC Error found in type code (illegal code)
T = Type code
L = Length (byte count)
A = Address
| Type | Parameter n Significance | Type Code Significance | |
| 0 | CALL | Caller Send/Rec capability | Request to set up a logical channel |
| 1 | HELLO | Called Send/Rec capability | Confirmation of CALL request |
| 2 | GOODBYE | Reason for termination | Cleardown logical channel of reject CALL request |
| 3 | UM DATA | Sequence number | Normal UM-UM data transfer |
| 4 | INC DATA | Sequence number | UM-UM data transfer, terminal input incomplete (TP) |
| 5 | NEXT | Permit level | Set number of UM/INC DATA packets that can be sent |
| 6 | INTERRUPT | Unused (zero) | Interrupt signal from terminal (TP) |
| 7 | CANCEL | Unused (zero) | Cancel data output to terminal (TP) |
| 8 | DROP | Length of seq. number gap | Indicates packet loss to sender |
| 9 | ERROR | Unused (zero) | Signals receipt of short packet |
Figs. 3a & 3b Packet Formats
Expiry of the time limit results in the PS declaring the offending UM as "unavailable" and returning all queued packets to their originators as DNA responses.
The PS operates an overall flow control scheme which consists simply of a limit imposed on the number of packets that a UM may send to the PS and have stored awaiting output. There is no limit imposed on the length of an output queue, other than that determined by the size of the pool of packet buffers managed by the PS.
A significant consequence of the minimal protocol adopted for the NPL PS is that it provides no mechanism for responses being added to the end of the current output queue. This is the reason for returning the entire packet to its sender when an error is detected by the PS, rather than using a short (header-only) response. The UK may thus add information to the data section of each packet, such as a sequence number, providing the necessary packet identification to effect retransmission or recovery actions in the event of an error.
Even this escape mechanism is not fully adequate, however, since it cannot properly cope with situations when the packet has become corrupted (as may be the case when ERTC or ERBC responses are received). In these cases the identifying information carried within the packet is also suspect. There is no adequate substitute for a protocol based on acknowledgement with time-out initiated retransmission for providing a good level of data security. Thus there is a choice between the use of a very simple protocol with the advantage of minimizing the UM software overhead, and the use of a more sophisticated scheme providing better security. The NPL PS is designed according to the first of these choices and consequently offers a relatively unreliable transmission channel between UMs. This unreliability may however be eliminated at the next level in the communications hierarchy by adopting a suitably elaborate UM-UM protocol.
5. THE TERMINAL PROCESSOR FUNCTIONS AND PROTOCOL
The Terminal Processor (TP) is a User Machine connected to the NPL Packet Switch; its main task is to provide access to the network for simple peripheral devices. The TP acts analogously to a telephone exchange in that it allows a subscriber terminal to call another subscriber and when connected, to exchange data with it.
A terminal may only communicate with one other party at a time, this other party being either another terminal attached to the TP or a UM accessed via the PS. The "call" or "connection" is a virtual one since the TP buffers all data transfers. Packets as such are not sent to or received from terminals, communication with the TP being in terms of sequences of data octets. The TP assembles data from a sending terminal into a packet sized block, forwarding it when complete to the other party. In the case when the latter is another terminal, the block is disassembled and the individual octets transmitted. However, when it is a UM then a properly formatted packet will be generated and passed to the PS.
Each terminal consists of a Network Termination Unit (called PCU-A) to which may be attached, via a pair of BS interfaces, a peripheral device capable of generating and/or accepting data. Any device capable of operating with the interface may be used. A small console having four buttons and four lamps is provided, as part of the PCU-A, to act as a user signalling interface to the network.
The TP itself does not have to take account of any special features of the peripheral devices attached to the PCU-A since it is effectively insulated by the latter. Data transfers to or from the peripheral are controlled by its PCU-A. Each PCU-A is itself controlled by the TP through the medium of "status" signals which form an internal low-level protocol similar to that used by the PS. Data transfers between the TP and the peripheral are half-duplex, the TP setting a PCU-A into the "transmitting" or "receiving" state by sending the appropriate status signal. The PCU-A user console buttons cause status signals to be sent to the TP, while receipt of these signals may cause the console light display to change.
The TP is transparent to terminal data except when a call is being initiated; the identity of the called party is supplied in character form by the peripheral device itself. Numeric or alphanumeric forms of address are available, most of the service UMs being given mnemonics. A "private wire" mode of operation is also available in which a destination address stored in the TP is automatically called when the user presses the call-request
Since terminal users will generally require to have their assembled data forwarded to the recipient before the buffer is completely filled (eg when a short command has been typed and a response is required) a console button is provided for signalling this request. Normally, however, this "please forward" signal is automatically generated by the PCU-A following the detection of various events, the most important of which is the occurrence of one of a number of previously specified characters (such as "Carriage Return") in the data stream from the peripheral.
A simple protocol (the TP-UM protocol) has been defined to control the flow of information between UMs and the TP, thereby allowing UMs to access and control terminals. The protocol consists of a set of basic but general rules concerning the use of logical communication paths, with some extensions tailored to the terminal handling requirement. Because of its generality, the TP-UM protocol is in fact used as the standard for all UM to UM communications within the network.
Packets conforming to the TP-UM protocol have the format shown in Figure 3b. The necessary control information is collected together to form a 4-octet inner header (to which the PS is transparent) consisting of a UM type code defining the principal packet function, two reference numbers serving to identify the packet and a parameter field whose significance depends on the packet type. The type and parameter functions are summarised in Figure 5. The types UM DATA and INC DATA are used for transporting user-level data (eg data which has been received from or is to be output to a terminal, in the case of the TP) and only these may have a non-empty data
5.1 LOGICAL CHANNELS
In general, multiprogrammed UMs will engage in a number of simultaneous but logically distinct interactions with other UMs. There may be several such interactions taking place between a given pair of UMs, for example when a number of terminals are logged into a multiaccess service via the TP. It is therefore necessary to provide some means for deciding which particular interaction each incoming packet belongs to, in order that the UM's communications control program may pass it on to the correct service program or process.
This is achieved by the use of reference numbers, which are in effect local subaddresses, one reference being assigned by each of the two UMs involved in a particular interaction. A pair of references thus associated constitute a "logical channel". Since all TP-UM packets carry both references, it is possible for the receiving UM to identify unambiguously incoming packets.
A UM may request to establish a logical channel by issuing a CALL packet carrying a "My Reference" of the calling UM and a "Your Reference" of the called UM. A HELLO packet from the called UM carrying the same references indicates acceptance of the request, while a GOODBYE packet indicates rejection. The "My" and "Your" reference fields are always relative to the sender of a packet.
Since a calling UM may not know, or care about, the correct reference of the called UM, a zero Your Reference in the HELLO packet from the Your Reference on the initial CALL packet, and this would normally be expected in such a case. Once the logical channel is thus established, the association between the reference pair is fixed for the remainder of its existences. The channel may subsequently be closed at any time by either UM using a GOODBYE packet. The two reference values are thereby freed for use in other interactions.
The references may be regarded as a set of equivalent resources available to programs running in a UM and enabling them to communicate with programs in other UMs. The references may be allocated, and the protocol rules policed by a "network control" executive program in each UM. The mapping between user program identity and logical channels may be made internally by each executive program so that the references will act only as "intermediate" addresses who values have no particular significance themselves. This will usually be the situation with multiaccess UMs. Communication will initially be established with a "logon" program, say, the user supplying further information (by what therefore amounts to a higher level protocol) in order to identify the particular service or program he wishes to use.
In the case of the TP, however, the reference numbers are also the terminal addresses, so that their significance is fixed. When a "call" is set up between a terminal and a UM, then the TP and the UM in question establish a logical channel.
5.2 FLOW CONTROL
Each logical channel is full-duplex so that UM DATA and INC DATA packets may flow independently in either direction. However, no UM is allowed to send unsolicited data packets on any logical channel. A sender must await one or more "permits" from the potential receiver, these being allocated by using NEXT packets (whose parameter gives the number of permits granted). The implication of the NEXT is simply that its sender is prepared to accept the given number of data packets at any subsequent time. The permit level determines the determines the number of packets that may be sent, irrespective of their length. This flow rule necessarily only applies to the UM DATA and INC DATA pockets, and operates independently in the two directions of transfer.
A receiver is free to allocate new permits before previous allocations have been exhausted. This latitude makes the flow scheme less vulnerable to being locked-up by the loss of NEXT or data packets. Permit allocations are absolute rather than additive, so that the number of permits held by a sender will always be reset by the receipt of another NEXT. This rule allows a receiver to reduce or completely withdraw a previously granted allocation.
UM DATA and INC DATA packets carry a modulo 256 sequence number, running independently for each direction of packet flow. If a sequence gap is detected at one end of a logical channel, the other end is informed by using a DROP packet. This scheme is not intended to allow recovery by retransmission; it only ensures that both ends are informed of any data packet loss in order that corrective action may be taken, if desired, by the user programs. Thus, taking the familiar example of a terminal communicating with a multi-access service, the latter may repeat an output sequence or may request the terminal to repeat an input command, in the event of a data loss being detected.
The remaining packets, and the parameter fields on the CALL, HELLO and GOODBYE packets, relate mainly to the control of terminal operations and would not be used in general UM-UM interactions. Lack of space precludes a description of their functions here.
As with the PS protocol, the TP-UM protocol has been chosen with a view to simplicity and efficiency. Thus the burden of security provision is thrown onto the user who is concerned with this matter; those who are not do not suffer the overhead. Whether this choice is justified is at present hard to assess, but the experience so far gathered of operating the NPL network and the attached services indicates that it is quite usable despite the errors and corruptions which do occur. Network control programs are reasonably compact and easy to write, an important consideration in an environment where small computers are common and programming effort is limited.
6. SERVICES ATTACHED TO THE NPL NETWORK
Presently there are some 12 User Machines attached to the network but only a few of these provide "services" to other users. The rest merely use the network for access to other subscribers for private purposes.
There are also some 75 terminal subscribers representing a wide variety of terminal equipment, including teletypes, VDUs, small computers, printers, plotters, paper tape stations etc. Physically the present system is capable of being expanded to cater for 256 subscribers (terminals or User Machines).
The services currently available are:-
a) "SCRAPBOOK" information retrieval system,
b) "EDITOR" text manipulation system,
c) "FILE STORE" central filing system,
d) "BASIC" time sharing system,
e) "ELDON" multi-access system to central computer,
f) "IN QUICK" RJE to central computer.
The "SCRAPBOOK" system is implemented on a Modular 1 computer and offers a VDU-based information storage and retrieval service for textual files. These files can be linked within Scrapbook as an hierarchy of related records, providing a structured data base for information retrieval purposes.
The EDITOR system (PDP11) offers text manipulation and editing facilities to simple keyboard/printer users. These texts can then be sent on to other services, as the user requires, such as the FILE STORE which is used by EDITOR as a backing store. Texts can also be printed on a line printer or punched out on paper tape.
The FILE STORE as indicated above is intended to offer a data storage facility to small computers attached to the network. It is not intended to be accessed directly by Terminals, which will normally use the agency of EDITOR or some other service machine. For example a simple modification to standard DEC software has enabled PDP8 users on the network to use the FILE STORE as if it were a locally connected disc.
Additionally the FILE STORE provides a convenient "spooling" point for passing jobs to and from the central computers. (ICL KDF9). The FILE STORE service is run by a Honeywell DDP 516 and can have up to 100M characters of online storage. There are additionally magnetic tape back-up and archiving facilities. This service is described in a companion paper [12].
An elementary BASIC keyboard calculator is provided via the network by a PDP-8 computer. This is intended primarily for the naive user who does not require the full facilities of the KDF9 ELDON multiaccess time-sharing service, and who does not want to master more complex operating procedures.
The central computing facilities of the laboratory are provided by two ICL KDF9 computers. These support both batch and time sharing facilities, the latter being accessed by a number of directly connected teletypes. This system was operational long before the network was developed, and as a simple (and hopefully temporary) expedient, a number of the teletype ports on the machine have been patched across to terminal outlets on the network, thus allowing access to the ELDON system from other network terminals. Similarly a simple input/output stream between the machine and the network has been provided by connecting a spare magnetic tape channel to a network terminal outlet. This allows the KDF9 to access the FILE STORE and also for the KDF9 to accept bulk input from devices like paper tape readers.
This somewhat simple approach to patching an existing service to the network does not offer an entirely satisfactory service, and is no substitute for providing a long term solution.
7. CONNECTION OF THE NPL NETWORK TO OTHER SERVICES AND NETWORKS
Part of the research on networking has been to consider ways in which commercial services could be attached to the NPL network to provide enhanced computing facilities to the users.
More recently this energy has been channeled into considering means of interworking between the NPL network and. other networks such as the ARPA network, the British Post Office EPSS network, the French Cyclades network, and the COST project 11 (or European Informatics Network). [13].
To this end NPL are participating in the deliberations of the Internetwork Working Group, a working group of the IFIP committee TC6 (data transmission).
However, one point emerges from this work, namely that despite the effort going into establishing methods of interconnecting these networks and defining some standard way of allowing computers to exchange information, at the user-program level vast disparities are still apparent in Job Control Languages, commands to operating systems, logging-in (or on!) conventions, file structures etc.
It could be argued, that considerable effort has been expended by numerous workers in developing mechanisms for facilitating computer "networking", but not enough into analyzing the requirements of the end user and that the bottom-up synthesis should be accompanied by some top-down analysis. Perhaps there is after all something in the notion of the IBM "network machine".[14]
ACKNOWLEDGEMENTS
Valuable feedback on the use of the NPL network protocols, leading to some improvements, has been obtained from a number of users in other research groups in NPL, amongst whom should be mentioned, P.M. Cashin, B. Schofield and B. A Wichmann.
REFERENCES
[1] D.W. Davies et al, A digital communication network for computers giving rapid response at remote terminals, Proc ACM symposium on operating system principles, Gatlinburg USA, 1967, pp 2.1-2.7.
[2] R. Scantlebury, A model for the local area of a data communication network -- objectives and hardware organisation, Proc. ACM symposium on data communications. Pine Mountain, USA, 1969, pp 183-204.
[3] P. Wilkinson, A model for the local area of a data communication network -- software organisation, ibid, pp 155-81.
[4] R. 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 second symposium on problems in the optimisation of data communications, systems, Palo Alto USA Jan 1971, pp 160-7.
[5] L. Roberts and B. Wessler, Computer network development to achieve resource sharing, Proc AFIPS SJCC pp 545-549.
[6] J.M. McQuillan et al, Improvements in the design and performance of the ARPA Network, Proc. AFIPS 1972 FJCC Vol 41 pt II p 741.
[7] W.L. Price, Simulation Studies of an Isarithmically Controlled Store and Forward Data Communication Network, Proc. IFIP Stockholm 1974, pp 151-154.
[8] L. Pouzin, Presentation and major design aspects of the Cyclades computer network, Proc. 3rd ACM/IEEE data communications symposium, Florida, Nov. 1973 p 80.
[9] British Post Office specification Tg 30005.
[10] S.M. Ornstein, The terminal IMP for the ARPA computer network, Proc. AFIPS 1972 SJCC Vol 40 pp 243-254.
[11] BS4421 : 1969, A digital input/output interface for data collection systems. British Standards Institution, Sales Branch, 101 Pentonville Rd London N.1.
{Editor's Note: This standard is out of print. 4421 is described in this PDF "Experience with the use of the British Standard Interface in computer peripherals and communication systems" by D.L.A. Barber of NPL. /RDM}
[12] P.A. Bailey and B.M. Wood, A central file store for the data communications service of the National Physical Laboratory, Proc ICCC 74, Stockholm 1974.
[13] D.L.A. Barber, Progress with the European Informatics Network, Proc. ICCC 74, Stockholm 1974.
[14] D.B. McKay and D.P. Karp, Protocol for a computer network, IBM Systems Journal, Vol 12, No. 1 1973. p 94.