Accession Number:

ADA061666

Title:

A Failsafe Distributed Routing Protocol

Descriptive Note:

Technical rept.

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR INFORMATION AND DECISION SYSTEMS

Personal Author(s):

Report Date:

1978-09-01

Pagination or Media Count:

78.0

Abstract:

An algorithm for constructing and adaptively maintaining routing tables in communication networks is presented. The algorithm can be employed in store-and-forward as well as line switching networks, uses distributed computation, provides routing tables that are loop-free for each destination at all times, adapts to changes in network flows and is completely failsafe. The latter means that after arbitrary failures and additions, the network recovers in finite time in the sense of providing routing paths between all physically connected nodes. Complete rigorous proofs of all these properties are provided.

Subject Categories:

  • Non-Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE