Abstract

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.

Keywords

Computer scienceComputer networkNode (physics)Overhead (engineering)Network packetNetwork topologyAlgorithmNetwork delayNetwork performanceRouting (electronic design automation)Distributed computingEngineering

Related Publications

Publication Info

Year
1980
Type
article
Volume
28
Issue
5
Pages
711-719
Citations
680
Access
Closed

External Links

Social Impact

Social media, news, blog, policy document mentions

Citation Metrics

680
OpenAlex

Cite This

John M. McQuillan, I. Richer, Eric Rosen (1980). The New Routing Algorithm for the ARPANET. IRE Transactions on Communications Systems , 28 (5) , 711-719. https://doi.org/10.1109/tcom.1980.1094721

Identifiers

DOI
10.1109/tcom.1980.1094721