The new ARPANET routing algorithm is an improvement over the old procedure in that it uses fewer network resources, operates on more realistic estimates of network conditions, reacts faster to important network changes, and does not suffer from long-term loops or oscillations. In the new procedure, each node in the network maintains a database describing the complete network topology and the delays on all lines, and uses the database describing the network to generate a tree representing the minimum delay paths from a given root node to every other network node. Because the traffic in the network can be quite variable, each node periodically measures the delays along its outgoing lines and forwards this information to all other nodes. The delay information propagates quickly through the network so that all nodes can update their databases and continue to route traffic in a consistent and efficient manner. An extensive series of tests were conducted on the ARPANET, showing that line overhead and CPU overhead are both less than two percent, most nodes learn of an update within 100 ms, and the algorithm detects congestion and routes packets around congested areas.

The original routing algorithm of the ARPANET, in service for over a decade, has recently been removed from the ARPANET and replaced with a new and different algorithm. Although the new algorithm, like the old, is a distributed, adaptive routing algorithm, it is not similar to the old in any other important respect. In the new algorithm, each node maintains a data base describing the delay on each network line. A shortest-path computation is run in each node which explicitly computes the minimum-delay paths (based on the delay entries in the data base) from that node to all other nodes in the network. The average delay on each network line is measured periodically by the nodes attached to the lines. These measured delays are broadcast to all network nodes, so that all nodes use the same data base for performing their shortest-path computations. The new routing algorithm was extensively tested on the ARPANET before being released. This paper describes the algorithm and summarizes the results of these tests.

This paper presents a comprehensive review of the ARPANET routing algorithm, from its original implementation to our plans for future modifications. We hope that by collecting this information, and by providing considerable details, we can provide others with a useful reference document concerning some of the practical problems of network algorithm design. Much of the discussion below assumes a basic familiarity with the principles of packet switching, the ARPANET implementation, and some of the relevant terminology, information which can be found, for example, in [4]. Sections 1 and 2 give a brief summary of basic routing concepts and of the original routing algorithm, respectively. The following two sections describe in detail subsequent modifications and the actual implementation currently in use. Section 5 then discusses some problems that have developed over the past few years, as network usage has grown considerably. The final sections outline some explanations for these problems and some mechanisms for improving performance. We are in the process of implementing these and other changes to the routing algorithm.

An interleaver/de-interleaver can be used to improve the performance of a Viterbi decoder in the presence of bursty noise. This note describes the design and a method for testing block interleavers which can be used to combat the effects of periodic pulsed RFI. Simulations show that satisfactory decoder performance can be obtained over a range of RFI parameters.

The advantages of utilizing the extremely low frequency (ELF) band for communications to submarines are principally the low attenuation rate of ELF signals in seawater and the low attenuation rate in the earth-ionospheric waveguide. ELF transmitters, however, require high input power. Efficient signaling schemes and sophisticated receiver designs help minimize the required transmitter power and hence system cost. One such signaling schemeconvolutional encoding and binary antipodal modulation-and an experimental receiver were successfully field tested and are described. Tests included real-time reception of messages aboard a submerged submarine in the Atlantic Ocean. It is concluded that the receiver, which included adaptive nonlinear noise processing, notch filtering, ocean channel compensation, and sequential decoding makes extremely efficient usage of available signal strength and demonstrates the technical feasibility of communication in the ELF band.