ARPANET Routing Algorithm Improvements

Abstract

This report describes progress during the second six months of a contract to make several improvements to ARPANET routing. A new line up/down protocol has been designed and implemented, and its performance has been extensively measured under actual network conditions. The protocol is described and the measurements are presented. Software routines to measure and report average packet delays on a per-hop basis have been designed and implemented. The routines are described, and measurements which have been performed using the routines are presented. A rigorous mathematical analysis of the stability of the SPF algorithm is presented. A protocol to ensure the rapid and reliable transmission of routing update message has been designed. It is described, and the reasons for choosing it are discussed. A preliminary design of enhanced message capabilities for the ARPANET (logical addressing, broadcast addressing, and group addressing) is presented. Finally, the interactions between routing and congestion control are discussed.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1978
Accession Number
ADA086338

Entities

People

  • D. P. Bertsekas
  • E. C. Rosen
  • I. Richer
  • J. M. Mcquillan

Organizations

  • BBN Technologies

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Accuracy
  • Computations
  • Computer Networks
  • Control Systems
  • Databases
  • Equations
  • Hypervelocity Flow
  • Load Monitoring
  • Mathematical Analysis
  • Message Processing
  • Multiple Access
  • Network Topology
  • Networks
  • Ring Networks
  • Simulations
  • Statistics
  • Three Dimensional

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Computer Science.