This paper was originally published in: NATO Advanced Study Institute on Computer Communication Networks, University of Sussex, held in 1973 pp 435-44. Proceedings were published by Noordhoff - Leyden in 1975.

EXPERIMENTAL PACKET SWITCHING PROJECT OF THE UK POST OFFICE

Part 1: Facilities and Customer Participation

Roy D. Bright

UK Post Office, Data Communications Division,
Marketing Department.

Network Configuration and Access Arrangements

For the purposes of this experimental Service, a three node network has been designed. This consists of three packet switching exchanges (PSEs) located at centres of high data concentration in the UK including London, Manchester and Glasgow. These, incidentally, are approximately 200 miles apart. The three exchanges will be fully interconnected by 48 kHz lines operating at 48 kbit/s.

Opening in early 1975, the service will be limited to 4 hours continuously per day, but this will be progressively increased to 24 hours per day, if demand warrants, within two years of opening.

Each PSE will be equipped with two types of interface with users' equipment; a packet interface and a character interface. The former will be used for intelligent devices including computers and will convey formatted packets and acknowledge their delivery. This mode of access is significantly different from some other packet switching networks elsewhere, which look to the user for conventional character by character operation with the node taking on the role of packet assembly/ disassembly. This latter mode of access is also available in the EPSS character terminals typically keyboard/printer terminals operating at 110 and 300 bit/s asynchronously. This facility may not, in fact, be required as a permanent feature but is primarily designed to facilitate user participation in the experiment. Similarly, each user is expected to handle packets at one end of their link with EPSS if not all terminal points. It is the ability of user configurations to interface at a packet level which is of prime importance in the experiment. Thus users operating terminals with packet handling capabilities will access PSE at 2.4 Kbit/s or 48 Kbit/s; in addition provision has been made for 4.8 and 9.6 Kbit/s access should this be required by some users. Both telephone switched network and/ or direct access will be permitted utilising normal Datel arrangements including 2400 Dial-up.

Facilities

In addition to packet assembly/disassembly mentioned earlier a number of important facilities are also to be tested out in conjunction with the users.

(i) Interleaved Packets This is possibly one of the most significant areas insofar as it will allow the establishment of several simultaneous calls over one link between the user's computer and a number of distant terminals. The value of this facility is enhanced by its ability to handle packets in a dynamic fashion rather than on dedicated time slots as would be the case in a conventional multiplexer.

(ii) Data Rate Conversion will be provided by the service rather than the user incurring the cost in his terminal equipment thus the ability to link terminals operating at different speeds will be an inherent feature of the service.

(iii) Code Conversion The potential requirement to allow communication between character terminals operating in IA2 and IA5 codes will be tested.

(iv) Link by Link Error Control Currently, a good leased line provides an undetected error rate of 1:10 6. Using a 16-bit error-checking code, this should be improved by four or five orders of magnitude. This check will be applied at each stage of the packet's transmission between PSEs and for terminals operating in the packet mode will also apply on the access links.

(v) Closed User Groups On joining the service, users will be able to nominate those terminals etc. to which he wishes to restrict access. The PSE will effect this by the use of interlock codes designed to bar access from unauthorised terminals.

Cost/Benefits

A key objective in defining the service was to combine the advantages of leased and dial-up operation while minimizing their respective short-comings. Thus an existing leased line user will no longer pay a rental for a circuit extending tens or hundreds of miles but will rent only access lines. This will still provide the wide range of speeds and could also reduce the incremental cost of changing to a higher speed e.g. from 9.6 kbit/s to 48 kbit/s by several orders of magnitude enabling future growth of traffic to be accommodated without expensive upgrading of both lines and equipment. Similarly, the dial-up user while retaining the ability to pay only for usage will gain the benefit of the wide range of speeds (up to 48 kbit/s) previously restricted to leased line users. Other operational benefits can be cited including automatic protection against 'call cut-offs' and automatic re-routing - not previously available to the leased line user. Coupled with the numerous novel facilities identified earlier, there should emerge a significant opportunity for users to reduce their data communications costs, but, as in many cases these represent less than 10 per cent of the total system costs it is the foreseeable impact of the service on this latter cost which could have the most dramatic effects on users' attitudes.

While it would be premature to make positive claims in this area, a number of potential savings seem attainable:

(i) less buffering required at the users' host computer site with no commensurate increase at the remote terminals.

(ii) a measure of standardisation and some simplification of the communication OS module thereby freeing core for other uses.

(iii) elimination of the wider needs for customer provided concentrators/multiplexers.

(iv) more efficient processing by virtue of the standard formatted messages.

(v) some reduction in complexity and therefore cost of the front-end processor

(vi) improved diagnostic capabilities.

Participation

Following a gradual build-up of interest since the plans for EPSS were first announced, potential users, encouraged by swingeing tariff concessions for the first twelve months, are appearing in growing numbers. To date some twenty organisations have declared their intention to participate; the latest commitment those of a Central Government department and the National Engineering Laboratory at East Kilbride. The range of applications and equipment configurations now represented is extensive; among the commercial users are two joint stock banks' - Barclays and Midland; a consortium of Trustee Savings Banks; Joseph Lucas - a large manufacturer of automotive electrical equipment and two commercial service bureaux - SCICON and CRC Information with others expected. Many main-frames and front-enders are represented; among others are a Burroughs 6500/6700, Univac 1108, Sigma 9, IBM 560/40 and various PDPs, Modular 1s etc. As expected, several non-commercial organisations such as Universities and research establishments will also take part including NPL with its in-house packet network and the Institute of Computer Science of London University with its ARPA TIP.

A number of interesting developments have already been stimulated by the EPSS proposals. For example, NPL and the Computer Aided Design Centre, Cambridge, are to collaborate in using EPSS customer protocols over a leased 48 kbit/s circuit throughout 1974. This will enable some pre-service experience to be obtained prior to the opening of the first (London) PSE at which time the link will be rerouted to incorporate the switch disciplines. Secondly, a study is being mounted to consider the feasibility of utilising EPSS as a means of interconnexion between a large number of British universities and allied centres thereby eliminating the growing matrix of leased lines. In a similar manner, there are signs of a potential use for serving a group of nationalised industry needs where a measure of commonality can be seen to exist.

These and other emergent trends - both national and international underline the potential value of a packet switched service and more than justify "the decision to mount the experiment. Now under active consideration by the UK Post Office is the next step which, assuming a successful experiment, will be the need to expand and develop into a national packet switching service.

Part 2: Technical Specification and Development

Michael A. Smith

UK Post Office, Data Network Development Coordination Division
Telecommunications Development Department.

Note: In view of the very brief period available for this description, the main topic covered is the packet interface between Customers and the Network, which is possibly the most unique and critical feature of the system.

Network Structure

More than one arrangement of switching nodes could be used to provide communications paths between customers' equipment, the two extremes of which may be regarded as a 'mesh' with switching nodes located only at customers' premises and a 'star' "with only one switching node located centrally. In the first case the switching costs are high, network maintenance personnel access to the switches is very difficult to guarantee at all times, and. hence reliability may be low. In the second case line costs will be high and the lines will be underutilised, but the reliability of the switching node could be made very high by equipment duplication and with continuous maintenance staffing if necessary. A compromise between these two extremes seems to be desirable and this has led to the arrangement described by Roy Bright.

Customer to PSE Packet Transfer Procedures.

In this area of the system definition the question of standards is very important. The UK Post Office endeavour is to work harmoniously with Industry, Users and through established International bodies like the ISO and CCITT to achieve such standards. Initially, the methods of connecting customers' equipment to the PSEs will depend mainly on modems, but eventually it is intended to utilise elements of the UK DDS (Digital Data Service) for this purpose. To summarise:-

a. Contiguous 8 bit bytes will be transmitted by the customers' equipment and PSE between and during packets

b. The customers' equipment is required to return bytes in a fixed relationship with the received bytes

c. Each line signal (byte) depends on the incoming byte

d. Only one packet may be sent before an acknowledgement is received

e. A packet may only be transmitted after the receipt of three particular line signals

f. A packet is acknowledged by returning 3 identical bytes

g. An acknowledgement is transmitted (i) by the customers' equipment after 40 bits delay (max.) and (ii) by the PSE within 8 bits delay (max.)

h. An acknowledgement will interrupt any packet in transmission but does not pass through the cyclic redundancy check (CRC)

i. The receiving end detects the acknowledgement from a knowledge of the loop delay

j. The acknowledgement bears the following diagnostic aids.

(i) If the packet has any detected errors
(ii) If the link sequence number is in sequence
(iii) If the receiver has the resources to handle the packet

k. Packets are only retransmitted, after receiving 3 Idle 1 bytes

l. The PSE has a maximum of 3 attempts at transmitting a packet

To amplify some of the detail of the above summary, the following is offered;

Loop delay measurement

The procedure will be carried out

(i) After powering up of the line interfacing equipment
(ii) After loss of byte synchronism (see next heading)
(iii) After three unsuccessful attempts to transmit a packet

Sequence of bytes transmitted between the customer and the PSE;

OCR ERRORS FIX IN HTML

W  2 2 2 T C B H H H H H H H 1 1 1 1 1 1 1 H H H A1A1A11 1 1 1
X  2 2 2 2 T C|B H H H H H H H 1 1 1 1 1 1 1 H H H A1A1A11 1 1
Y  H H H H H H|H H A2A2A2H H H H H H H T C B|H H H H H H|H 1 1
Z  H H H H H H|H H H A2A2A2H H H H H H H T C|B H H H H H|H H 1
              |           |                 |           |
              |           |                 |           |
              | PSE sets  |                 | Cust. sets|
              |   delay   |                 |   delay   |
              |           |                 |           |
Where    1  Idle 1      H  Packet Hold      A2  Ack 2
         2  Idle 2      A1 Ack 1            N2  Nack 2
         T C B  Loop delay measurement packet (SOP/Type+check)
and      W is the stream of bytes transmitted by the PSE
         X is the stream of bytes received by the customer
         Y is the stream of bytes transmitted by the customer
         Z is the stream of bytes received by the PSE

Assuming:  the delay at the customers' equipment = 8 bits
           The delay at the PSE                  = 8 bits
           The physical loop delay               = 16 bits

Note 1: If the correct response is not received after 50 bytes of Packet Hold being transmitted following the sending of the loop delay measurement packet, a further loop delay measurement packet will be sent.

Note 2: If three unsuccessful attempts are made to send a packet the loop delay measurement packet will be sent after 15 Packet Hold line signals have been transmitted. If a packet is received during this period, the loop delay measurement packet will be sent after at least 15 Packet Hold line signals and the acknowledgement (A2A2A2) or (N2N2N2) to the received packet.

Note 3: Loop delay measurement packets may be sent whilst Packet Hold is being received.

Loop Synchronism

Under the previous heading the concept 'Loss of byte synchronism' was introduced, and this is defined as follows:-

'When 3 contiguous identical line signals are received which do not correspond with the previous byte synchronism counter position, providing a packet is not being received'.

If this condition is detected by (a) the customers' equipment, the outgoing byte stream will be realigned with the incoming stream (if a packet is being transmitted, this is done at the end of the packet) and the loop delay will be redetermined; or (b) by the PSE, the received stream byte synchronism counter will be repositioned and the loop delay will be redetermined.

Line Signals

When no packets or acknowledgements are to be sent (quiescent state) the conditions for the transmission of line signals are as follows:-

Line Signal
Transmitted
Idle 1When Idle 1, Idle 2, Packet Hold, Ack 1, Ack 2
or Ack 3 is being received, and incoming packets can be handled
Packet
Hold
When Idle 1, Idle 2, Packet Hold, Ack 1, Ack 2
or Ack 3 is being received and incoming packets
cannot be handled, or a packet is being received
Idle 3When the conditions for the transmission of Idle 1
or Packet Hold do not obtain, and no packet is to be sent

When acknowledgements are to be sent i.e. after the receipt of a packet, they will consist of three identical contiguous line signals which are unique except where shown. The significance of the signals and. the action taken following their occurrence are as follows;-

Line
Signal
(3)
CRC
Check
OK?
Seq.
No.in
order?
Can
Handle
Packet?
Action
Transmitting End
Action
Receiving End
Ack 1YESYESYESSend next packet
(if any) without
delay
Pass packet to next level of protocol
Ack 2YESYESNOThe packet is retransmitted after receiving
3 IDLE 1 signals
Packet
discarded
Ack 3YESNO- Send packet with next sequence no. without delay Packet
discarded
Nack 1
(Idle 1)
NO-YES The packet
is retransmitted
without delay
-
Nack 2
(Packet
Hold)
NO-NO The packet
is retransmitted
after receiving
3 Idle 1 signals
-

The transmission of each line signal or acknowledgement from customers' equipment may be delayed by a fixed number of bits in the range 1 to 40 bits after the byte or packet to which it refers has been received.

Conditions for Transmission of Packets

A packet may only be transmitted.. if the last three line signals received are Idle 1, Ack 1 or Ack 3. If a packet is being received at the time at which a packet is to be sent, the last three line signals received are defined as the three line signals which immediately preceded the packet. If line signals are being received at the time at which a packet is to be sent, the last three line signals to be received are defined as the three line signals which immediately precede the fixed delay in the customers' equipment.

Sequence Numbering of Packets

In order to enable receiving equipment to detect duplicate packets (e.g. arising 'because an acknowledgement was corrupted by 'noise', and the duplicate results from retransmission) and discard them, each packet transmitted will bear a 'Customer-to-PSE link sequence number i.e. 0, 1, 0, 1, etc. To initialise this sequence (e.g. after powering up equipment) the first packet will bear the sequence number 2 [sic RDM], the next 0 and so on.

Conditions for Retransmission of Packets

A packet will be retransmitted within 50 bytes of the time out (i.e. loop delay) expiring providing that three Idle 1 bytes have been received. If the 50 byte period expires and 3 contiguous Idle 1 bytes have not been received, the packet will be retransmitted as soon as three contiguous Idle 1 bytes have been received.

Packet Formats

A packet consists of three main fields: header, containing address, call label and control information; data field, which contains customers' data if the packet is originated by a customer' s terminal or computer, or may contain service signals if generated by the network (PSE); and these two fields are followed contiguously by the error check information. Efforts have been made to reduce the overhead represented by the header field by the use of short headers for packets forming part of a call; only the packets used for originating a call are required to contain the full address and control information. The PSE attaches full addressing, routing and interlock code information before transmitting the packet to a distant PSE, which removes this additional information before delivery to the recipient.

Studies of possible uses of packet switching systems have shown a wide variation of numbers of bytes or characters likely to be included within each packet data field. Systems which use fixed length data fields can have quite high overheads as a result of this variability which leads to numbers of packets with most of the data field unused. The EPSS uses a variable length data field packet, with the length of the packet indicated in bytes by an 8 bit sub-field of the header. This method of indicating the length of the packet has been chosen to avoid restricting binary sequences in the data field which would result from the use of a special terminating byte, and to avoid the overheads which result from the use of bit-stuffing coding methods, e.g. HDLC.

The error check polynomial used is x16 + x12 + x5 + 1, which corresponds to that used in CCITT Recommendation V 41 (Vol. VIII*).