THINK Home Digital Archive Search Feedback

 

THINK  NPL

A Technical History of National Physical Laboratories (NPL) Network Architecture - A Technical Tour



Technical Detailed Tour

 

PDU
- Protocol Data Unit (PDU), Name: packet, Length: Variable Length, 128-bits to 1024 bits

The protocol data unit (PDU) is called a packet. It is Davies who coined the term, which represents the broken-up message blocks used in Paul Baran's distributed network, the Cyclades network, the ARPANET, and today's Internet.

A packet is a short message with a fixed format made up of 128-bit segments. The length of a packet can vary from 128 bits to 1024 bits. The small segments are designed to improve the efficiency of transmitting short packets. The first segment of a packet, called a header, differs from other segments because it contains a header information about the message transmission.

The format of each message is described in the following figure:

Connection
-
Type of network service provided, either connection-oriented or connectionless

The network implements connectionless protocol because there does not exist an initial handshaking or connection establishment procedure.

Addressing
- Scheme used to identify a computer on the network

The network implements a flat addressing scheme. Each computer on the network has a unique identifier.

Fragmentation and Reassembly
-
Breaking up messages into smaller transmittable units

The interface computer handles all fragmentation and reassembly of messages. The source computer fragments and encapsulates a message into packets, while the destination interface computer reassembles incoming packets.

Multiplexing
- Gathering data from different processes and encapsulating each piece of data with a header

Demultiplexing
- Using information contained in a packet header to direct it upward through a protocol stack.

Multiplexing took place at the interface computer using a demand sorter. Based on it's priority, a byte arriving at one of the eight inputs of a demand sorter would be transfered to the deamnd at the next level. At the top level data was transferred directly to the memory of the computer without software intervention. A three-bit address corresponding to the input of the demand sorter was attached to an incoming byte to help determine the origin at each stage by the program. A scheme of depth 3 multiplexing would allow a maximum of 512 devices to be connect. This was sufficient to handle the 200 devices initially estimated by the Davies. (Campbell-Kelly p231)

Routing
- Determining a good path from a source to a destination

There are three programs within the node computer that works concurrently to effectively manage the routing of the packets: the Main Processor (MP), Input Processor (IP) and the Output Processor (OP). The MP includes the 'Output Queue Subroutine' (OQS) and the 'Input Queue Subrouting' (IQS).

These programs inside the node computers are responsible for routing the packets through the network by using an adaptive routing strategy. First, the IQS selects the top packet in the input queue. Then it increments and checks the handover number, changes the packet indicator field and finds an appropriate output queue. The subroutine uses routing tables to decide which link a packet should be transmitted through. The tables include output link numbers, which represent the destination of each link. These link numbers are ranked from the highest preference to the lowest. The IQS selects the link with the highest preference whose queue is not empty and link is not down.

The OQS takes the top item off the output queue and checks to see if the outgoing link is available. If the link is available, then the indicator of the packet is placed into trace mode. The OQS checks the trace queue to see if it has room for the new packet. If there is space, then it initiates transmission.

The IP is responsible for placing packets in the input queue and putting the packet either at the end or the beginning of the queue based on it's priority. The OP's task is to signal when the hardware is free and to transmit outgoing packets.

Protocol
- Defines format, order of messages sent and received among network entities, and actions taken on message transmission and reception.

An alternating bit protocol was used to transmit data reliably over a serial link. Each unit of data transmitted is identified with a single bit. This bit alternates with between each successful transmission of units of data. (Barlett, Scantlebury, and Wilkinson p260, 13)

Congestion Control
- Network management strategy whose goal is to alleviate or avoid congestion

It is possible under heavy load conditions that a packet may be caused to circle around its required destination node. To prevent a packet from orbiting forever under these conditions, an 8-bit handover number is incremented at each node. When the handover number reaches a certain value, the packet can either be returned to its source or dropped.

A Shut-up message tells a node at the far end to stop sending because the receiving end is busy or broken.

Flow Control
- A mechanism in which the receiver of the data changes the transmission rate of the sender so data will not arrive too quickly to process

Multiplexing at the network level implements flow control. A 'round robin' scheme examines each of the eight input channels for incoming data. In the event that the buffers which holds incoming data are full, the multiplexer continues to 'take and envelope' from each channel, but does not receive data. Then the network reduces the rate of the fastest channel. These steps help resolve the congestion in the network.

Error Detection
- Noticing corrupted or lost data during the transmission over the network

Error detection is the responsibility of each link's receiving node computer. A checksum, which is included in every segment, is used by the hardware in the node computer to detect link errors. Once an error has been detected, a trace message is sent back to the sending node computer along the originating links using special hardware. The receiving computer then request for the sender to re-transmit the packet. After special hardware in the sending node computer receives the trace message, it re-transmit the packet.

Error Recovery

A trace queue holds the three most recent packets that have been sent out on the network. It re-sends lost packets or retransmit packets that have detected errors. If the new packet is the 4th packet of the trace queue, then the first packet of the queue was successfully at the next node. If a node computer detects a trace message, the sender takes appropriate action to re-transmit the packet.

Security

As an experimental architecture, security features such as authentication and privacy were only conjectured. Over connectivity provided safeguards against broken or damaged links.

 

<< BACK  >> NEXT

BACK TO TOP

 

Written by the THINK Protocols team, CS Dept, UT Austin
Please direct comments to Chris Edmondson-Yurkanan.

This document was last modified on Tuesday, 11-Jun-2002 10:18:02 CDT.