ARPANET Routing Algorithm Improvements

Abstract

Abstract : This report describes progress during the first six months of a contract to make several improvements to ARPANET routing. Some principal conclusions are: Several problems have been discovered in the present congestion control, line up/down procedures, and loop suppression techniques through the use of a new real-time monitoring capability. Solutions to most of these problems have been developed; operational experience with these changes is presented. A new set of line up/down procedures with much better performance was developed and analyzed. Extensive measurements of network delay were carried out; delays fluctuate rapidly over a large range, making it difficult to devise effective estimation techniques. The present routing algorithm is itself a major contributor to network delay due to the computations and update messages it requires. A set of improvements was designed for the present routing algorithm to make it more efficient and effective. However, a new algorithm, based on performing the entire shortest path calculation at each node, incrementally for each network change, appears to be a better choice for installation in work change, appears to be a better choice for installation in the ARPANET.