A Failsafe Distributed Routing Protocol

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1978
Accession Number
ADA061666

Entities

People

  • Adrian Segall
  • Philip M. Merlin

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Communication Networks
  • Computations
  • Computer Communications
  • Computer Science
  • Data Transmission
  • Digital Communications
  • Electrical Engineering
  • Electronics Laboratories
  • Engineering
  • Information Processing
  • Information Systems
  • Military Research
  • Network Protocols
  • Notation
  • Routing Protocols
  • Sequences

Fields of Study

  • Computer science

Readers

  • Computer Networking