Dynamics of a Loop-Free Path-Finding Algorithm

Abstract

The dynamics of a loop-free path-finding algorithm (LPA) based on predecessor information and a single-hop internodal synchronization mechanism is investigated. LPA is compared with a loop-free algorithm based on diffusing computations, DUAL, and an ideal link-state (ILS) algorithm based on topology broadcast. Comparisons include the dynamic response of the algorithms to single and multiple link-cost changes as well as single link and router failures and recoveries. The results show that LPA requires a significantly smaller number of messages than ILS and DUAL to update routing tables when multiple changes in link costs occur. LPA's performance is always significantly better than DUAL's and significantly better than ILS's after node failures and resource additions (in some instances, ILS requires almost four times as many messages). After a link failure, LPA requires approximately the same time to converge as ILS and at most twice as many messages.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1995
Accession Number
ADA459117

Entities

People

  • J.J. Garcia-Luna-Aceves
  • Shree Murthy

Organizations

  • University of California, Santa Cruz

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Networks
  • Data Science
  • Dynamic Response
  • Dynamics
  • Information Operations
  • Information Science
  • Network Topology
  • Networks
  • Probability
  • Recovery
  • Routing Protocols
  • Simulations
  • Simulators
  • Statistical Distributions
  • Topology

Fields of Study

  • Computer science

Readers

  • Computer Networking