A store and forward packet switching: system has been introduced at Bell-Northern Research, Ottawa, Canada, to facilitate access to host computers from a geographically dispersed community of terminal users. This paper describes the major components of the network and the two network protocols which bind these components together: the Internal Network Protocol (INP) and the Network Access Protocol (NAP). Host computers can be interfaced to the network in two different modes: the combined node-front-end mode, using the IMP protocol only, and the disjoint node-front-end mode using the NAP protocol. These two protocols are outlined and their importance to the network and host sites are discussed.
1. INTRODUCTION
Bell-Northern Research operates a large time-sharing computer system at its headquarters in Ottawa, Canada. This system serves customers at several locations in Ontario and Quebec, mainly in the Ottawa, Montreal, and Toronto areas.
In order to provide a flexible access system to this computer, the development of a packet switching network was undertaken. The general objectives were to:
- provide a flexible basis for allowing customers to access the present host system (and each other)
- allow other hosts to be added to the network (at present many customers must access more than one host system)
-be the basis for a future, dispersed computing system in BNR in which the resources will not be so heavily centralized; that is, provide a network-oriented computer communication system rather than a host-oriented one
-provide practical experience in the development and operation of computer communication networks.
2. DESIGN CONSIDERATIONS
The network design had to provide flexibility for growth of services and the addition of hosts and terminals. In order to minimize interference with the normal operation of a time-sharing system, the facilities provided by the packet switching system are being introduced in three distinct phases or 'cutover' periods:
1) To meet BNR's most immediate requirements, introduction of the packet switching system without changes in the host operating system software. In this initial mode of operation, there is no physical separation between the user front-end and a network node; both functions coexist within a network node. This mode is called the combined node-front-end or simply, the combined mode.
2) Addition of a user-oriented network access protocol in the node software to facilitate the addition of hosts to the network. In this mode of operation, called the disjoint mode, the network functions are isolated from the user's host access functions, and a network node presents a standard interface to all host computers. Program modifications are required in the host operating software or associated front-end to access the network over a synchronous serial link.
3) After experience has been gained with the two previous modes of operation, additional hosts will be allowed to join the network, which may smoothly evolve into a network of computers during the remaining half of 1974.
The BNR network initially addresses itself to the problem of multiple host access from a community of distributed terminal users. An inherent master/slave relationship exists between a host and the terminals connected to it. Once a connection has been established, it is a major network responsibility to preserve this dependency, without intruding upon the normal use of a terminal. However, the nature of a packet switched network introduces delays not only in the transmission of a message but also in the orders sent by a host site to remote terminals.
The first phase provided us with an operational network for controlling the interaction between terminals and a host. The second phase centers around the definition of a formal procedure for controlling this interaction without imposing restrictions on the user's previous node of operation (circuit switching), such that a network can be considered as an extension to the user local facilities.
3. NETWORK COMPONENTS
The basic building block for the network is a node using DEC PDP-11 minicomputers as the control unit which interfaces line adapters designed to handle character terminals of various speeds and character code lengths.
A special adapter interfaces synchronous serial links between nodes.
The node software allows any mix of three basic computer communication functions:
- host access
- switching (routing)
- terminal access.
Combining all of the above functions in a single node yields a front-end, while distributing them over many nodes interconnected with synchronous serial links produces a packet switching network.
In combined and disjoint modes, network software modularity is preserved in both switching and terminal access functions. This is also the case for the Network Interface Control (NIC module, an interpreter which translates host commands into a form suitable for shipment to terminals throughout the network.
The NIC module is considered a network software module as opposed to a host-dependent software module responsible for 'driving' the host channel interface hardware: in our first application, an IBM 370 multiplexer channel interface to the PDP-11 minicomputer and supplied by DEC.
In the combined mode of operation, NIC is interposed between the host-dependent channel interface driver and the network router which accepts packets delivered in a rigid format prescribed by the INP protocol. Communication between NIC and the channel driver is via in-core tables.
In the disjoint mode, NIC is functionally the same: an interpreter, but instead of interfacing directly to a host channel controller of 'brand X', communicates over a serial synchronous link to the user front-end system. The ISO HDLC protocol has been selected for control of this serial synchronous link, and the NAP protocol must be implemented in the user front-end to communicate with the NIC module In the network node.
4. NETWORK PROTOCOLS
Two protocols are defined in the BNR network:
-The Internal Network Protocol (INP) ensures delivery of packets to various nodes in the network. Packets are reassembled into messages at the destination node.
-In the disjoint mode, the Network Access Protocol (NAP) exists to facilitate the exchange of messages and control information between a host and the terminals slaved to this host via the network.
Because synchronous serial links interconnect network nodes and also nodes to host computers, a single type of hardware interface (EIA RS232C) is presented to a network node. Therefore both protocols operate on a single type of channel.
The INP and NAP protocols have different formats, but essential terminal control functions are carried over from one protocol to the other. The major reason for the addition of the NAP protocol Is a matter of convenience to the host site. The INP protocol, which need not be known to the user, is complex to implement, its main objective being to optimize network throughput. On the other hand, the NAP protocol is user oriented. Its main objective being ease of implementation in order to facilitate access to the network. The NAP is message oriented while the INP deals with packets.
The NAP uses as an inner layer the proposed ISO HDLC procedure for control of a synchronous serial link. It isolates the network node from the user's front-end and attempts to present a standard interface between terminals connected to a network and a set of heterogeneous computers.
It is interesting to note that the BNR network can operate using only the INP protocol (combined mode) and that this mode of operation can run in parallel with the disjoint mode using both the INP and NAP protocols. This configuration illustrated in fig. 1, provides an experimental network for comparing both modes of operation.
4.1 Internal Network Protocol (INP)
Messages to and from terminals are broken into 40-character segments called packets, with a maximum of 4 packets per message. Both are system parameters which have been initially adjusted to the traffic characteristics of a time-sharing system. Transmission of packets is full-duplex between adjacent nodes, while transmission of messages is half-duplex between source and destination. Only one message per terminal is allowed to reside in the network at a given time, and it is controlled by the ready-for-next-message (RFNM) mechanism in the network. An RFNM received at the terminal indicates that the host has issued a READ command and Is prepared to accept a message from the terminal. The RFNM packet, which is sent at the highest priority, is equivalent to an acknowledgment normally returned by time-sharing systems, indicating successful processing by the host of the previous READ command.
Packets received from a terminal are sent immediately to their destination, where they are reassembled into messages following delivery of the last packet. For messages longer than the packet size, the first packet may arrive at its destination before the user has finished typing, thereby reducing overall transmission delays for long messages.
Various terminal codes are mapped into a virtual terminal, based on the ASCII code, for uniform transmission throughout the network. The network transmits messages only, such that start and end-of-message control characters are not transmitted over communication links. The proper control characters are inserted at the receiving end according to the terminal type.
A close examination of the header shown in fig. 2 reveals the major characteristics of this protocol.
Data characters of a packet are preceded by a six-byte header. The transmission block is preceded and terminated by the ISO framing characters 01111110, while two CRC characters precede the framing character of the next transmission block.
The first two bytes of the header contain acknowledgment information for error detection and correction by retransmission between adjacent nodes. The next two bytes contain end-to-end control information, and the last two contain addressing information for routing the packet to its destination.
The acknowledgment policy uses a strategy called ' multiple ACKs with implied NAK ', giving efficient line utilization in the presence of long transmission and/or propagation delays. Up to 63 packets can be sent to the neighboring node without waiting for an acknowledgment. Each packet is given a new serial number (PXMT) by the sender before transmission. In addition to its own serial number, the sender returns a second byte (ACK) containing a two-bit PPI field ( number of previous packets being acknowledged) to indicate that from one to four packets are being acknowledged. The remaining six bits Indicate the serial number of the highest packet number being acknowledged. The receiver knows how many packets it has transmitted, both the serial number of the packet and the number of contiguous packets being acknowledged, as indicated by the PPI field. Thus the receiver can retransmit any packet excluded from the acknowledgments.
For a given connection, the packet sequence number is incremented by the source and the last flag is set for the last packet of a message. This sequence number is not reset to zero following delivery to the network of the last packet of a message but is incremented for the packet of the next message. Thus messages are numbered indirectly to prevent the late arrival of a duplicate packet of the previous message being considered as the real packet of the current message.
The flag byte contains the RFWM or end-to-end acknowledgment and an attention bit which is reflected to the host after the user has signalled attention to the host ( terminal break key). The DEL bit is necessary to indicate to the destination that all packets of a received message should be purged at the distant end following certain errors. The extension flag indicates that the packet contains signalling information as opposed to text. In this case the text field is interpreted as network control information, such as request for connections, disconnects, host down, and no route available.
For flexibility, the address field is spilt into two subfields: the group number and the member number. The geographic location of a node defines a community of interest which is partitioned into groups. Each specific group is assigned a group number, which is, therefore, the reference number to all the member numbers having common properties.
For example, group 0 and group 1 can be assigned to node 0, the first group referencing all the terminals on node 0 and the second referencing all host port member numbers which are accessed through node 0. At each node, the group number is used as an index into a group-node correspondence table for routing the packet to the node pertaining to this group number. This table also contains a group type, useful for the destination to determine what process is related to this group type. With this open-ended numbering approach involving connection between groups, the network can restrict access between a host and a set of terminals. A group number is portable from node to node simply by changing the definition in the group-node correspondence table.
4.2 Network Access Protocol (NAP)
The combined node-front-end can cause problems at the user's site of software maintainability and, therefore, network reliability, not to mention security. To overcome these problems, the development of a formal network to host (front-end) protocol was started to isolate the front-end from all internal network problems and to make the modifications to existing front-ends as simple as possible. The protocol includes protection features to isolate the network from the front-end and vice versa.
All communications between the network and a front-end are over a full-duplex synchronous line in the range 2.4 to 56 kb/s. The International Organization for Standardization (ISO) is currently drafting proposals for a new framing structure, [1] and [2]. The current definition of the address and control bytes are used to operate a point-to point communication link between the node and the host site. All transmission blocks are framed by the serial bit stream 01111110. Transparency is implemented by inserting a zero into the data stream after each occurrence of five consecutive 1s. The framing sequence then delimits the start and end of transmission blocks.
The data is partitioned in a transmission block as follows:
| ISO CONTROL | MESSAGE HEADER | TEXT |
| 2 bytes | 6 bytes | 0 to 256 bytes |
The NAP protocol is supported by the message header and the various fields of this header are described below.
4.2.1 Message Header
The six bytes following the two ISO line control bytes constitute the message header of a block transferred between the network and the front-end. The message header directs the network in its function as a terminal controller and informs the front-end of all order terminations and unusual events. The bytes of the message header are as follows:
-The ORDER/REPLY byte is used by the network and front-end for terminal control and system control (synchronous line tests and diagnostic messages are classified under system control).
-The PORT byte selects 1 of 256 virtual terminal-port addresses between the network and the front-end. The front-end maps these addresses into its own addressing conventions, while the network maps port addresses into the full internal network address.
-The TEXT LENGTH is the length in bytes (ASCII characters) of the information following the message header. The current range is 0 to 256 (decimal) bytes. The TEXT LENGTH is zero with the returned REPLY from a WRITE order.
-The ANCILLARY control is a byte whose role depends on whether the message is an ORDER or REPLY. Its basic functions are error reporting for REPLYs and for sequencing after asynchronous events. Because of the distributed nature of the terminal control, ORDERs and REPLYs may 'pass' In different directions on the synchronous line, resulting in the network receiving an ORDER which does not reflect the current state of the terminal.
-One byte is reserved.
4.2.2 Orders
The majority of the orders are originated by the front-end and transmitted to the network. There are two main types of order: System Control and Terminal Control.
The network terminal always appears as an ASCII terminal to the front-end. Normally only one order is active per port address. The list of orders is given in table 1.
Table 1 ORDERS
1) System Control
| ORDER | MNEMONIC | HEX. | |
1) System Control | |||
| Reset All Ports | RSTA | 00 | |
| Proceed, All Ports Reset | PAPR | 01 | |
| Communication Status Report | CSR | 02 | |
| Echo | ECHO | 03 | |
| Request Control Block | RQCB | 04 | |
| Returning Control Block | RCB | 05 | |
| Host Down Message | HDMSG | 06 | |
2) Terminal Control | |||
| Enable | ENBL | 10 | |
| Read | READ | 11 | |
| Read with Time-Out | READT | 12 | |
| Write | WRITE | 13 | |
| Write - Read | WRITR | 14 | |
| Write-Read with Time- Out | WRITRT | 15 | |
| Disable | DISBL | 16 | |
| Dial | DIAL | 17 | |
| Halt Terminal | HT | 18 | |
| Reset Port | RSTP | 19 | |
4.2.3 Replies
All terminal orders sent by the front-end to the network are terminated by a reply indicating completion of the order. Since only one order per terminal may be active (HT and RSTP excepted), a reply signals the network's readiness to accept another order. The reply flags are listed in table 2.
Table 2 Reply Flags
| MNEMONIC | BIT | REPLY |
| OT | 7 | Order Terminated |
| ATTN | 6 | Attention Signalled |
| HTD | 5 | Halt Terminal Done |
| DISC | 4 | Disconnect |
| RD | 3 | Reset Done |
| RUO | 2 | Reply Unique to Order |
| PEC | 1 | Port Error Condition |
| REPLY | 0 | Reply |
A reply message is detected by a '1' in bit 0 of the ORDER/REPLY. The ANCILLARY control byte has additional information which is either unique to the order being terminated, or indicates an error condition involving the protocol sequence on that port.
The usual reply is OT. If the terminal user signals attention to the host (break signal) while an order is still active, OT+ATTN will be signalled. If the order is terminated by a HT, OT+HTD is signalled.
If the break key is hit while no order is active (terminal in wait state), ATTN without OT is presented. As a result of this asynchronous attention, the user expects the next order to reflect its occurrence. After transmitting ATTN to the front-end, the network will discard any order which does not acknowledge its receipt in the ANCILLARY control byte. This prevents an attention from being lost.
The DISC is returned when the user 'hangs up'. It is not returned as a result of the DISBL order. The DISC reply may be presented with OT. If not, the next order accepted by the network must include 'acknowledge asynchronous disconnect'. The DISC is handled like ATTN in this respect.
The reply presented after RSTP is RD and the RD flag is the only one set. The presence of additional information in the ANCILLARY control byte is indicated by RUO. This information is unique to the originating order.
The PEC bit denotes that the network aborted a valid order on the addressed port because of a violation in the terminal protocol or a condition in the network. The type of problem is indicated in the ANCILLARY control byte.
4.2.4 Ancillary Control
The ANCILLARY control byte is used by both orders and replies to contain supplementary information. This action is necessary to synchronize orders from the front-end with asynchronous events at the terminal. These events are attention (break) and disconnect while the terminal is in a 'wait state', which the terminal enters when no order is active. If a terminal user hits the attention key while in the wait state, the message, indicating attention which is sent to the front-end, could arrive after the front-end has issued a new order. If the network accepted the order, the user's terminal would respond as if no attention had been sent. If the network ignores the order and waits for the next one acknowledging the asynchronous attention, then the desired response at the terminal would occur. For example, suppose the order discarded was a write order. The observed effect is the same as hitting the attention key just as the first character of the write order is printed. The character would not be printed, and the terminal user would not be aware that the write occurred.
With replies, the ANCILLARY control byte has its usage indicated by the RUO and PEC flags. The RUO bit in the REPLY byte indicates that order-dependent terminating conditions are flagged in the ANCILLARY control byte. Time-out (TMO) for READT would be signaled here. Also, if a user message exceeds the maximum network message length, then it must be truncated, and this would be indicated in the ANCILLARY control byte.
A serious condition has occurred if the PEC bit is returned with the REPLY byte. This indicates that the network was unable to complete a valid order. For example, if the front-end cannot accept data causing a storage shortage in the network, the network may discard data from READ orders. If the network detects a protocol violation, the PV bit is set.
The network has two procedures for reporting protocol violations. If no host interface monitoring terminal is logged in, then the ANCILLARY control byte will be used to flag the error. The text field contains system diagnostic information and the connection may be terminated immediately with a RSTP order. If recovery is attempted, any new orders must be preceded by a HT.
5. CONCLUSION
A network access protocol has been presented to facilitate access to a packet switching network. This protocol was formulated by observation of various conditions encountered in interposing a network between an interactive time-sharing system and a set of distributed terminals.
The NAP presents a clear boundary between the user process and the network, with minimal intrusion in the host site operating system software. Furthermore, it is simple to implement and provides a protection mechanism between the network and a host computer.
Clearly, there is no substitute for experience in the design of network protocols. In this regard, the BNR network has provided a fertile ground for the difficult task of protocol definition.
ACKNOWLEDGMENTS
The authors wish to express their gratitude for the helpful suggestions and guidance from W.W. Clipsham and the excellent facilities provided by B.R. Smith during the development of this network. T. Gomi and W. Older contributed to the software development effort. J. Proctor and G. Jones designed and developed the hardware line adapters to meet the requirements of this network.
REFERENCES
[1] High-Level Data Link Control Procedures (Proposed Draft), International Standard on Frame Structure, ISO/TC 97/SC 6 (Geneva -3) 731, February 1973.
[2] High-Level Data Link Control Procedures (Proposed Draft), International Standard on Commands and Responses, ISO/TC 97/SC 6 (Stockholm - 9) 794, June 1973.