Accession Number:

ADA461943

Title:

A Loop-Free Path-Finding Algorithm: Specification, Verification and Complexity

Descriptive Note:

Corporate Author:

CALIFORNIA UNIV SANTA CRUZ DEPT OF COMPUTER ENGINEERING

Report Date:

1995-01-01

Pagination or Media Count:

10.0

Abstract:

The loop-free path-finding algorithm LPA is presented. LPA speci es the second-to-last hop and distance to each destination to ensure termination in addition, it uses an inter-neighbor synchronization mechanism to eliminate temporary loops. A detailed proof of LPAs correctness is presented and its complexity is evaluated. LPAs average performance is compared by simulation with the performance of algorithms representative of the state of the art in distributed routing, namely an ideal link-state ILS algorithm and a loop-free algorithm that is based on internodal coordination spanning multiple hops DUAL. The simulation results show that LPA is a more scalable alternative than DUAL and ILS in terms of the average number of steps, messages, and operations needed for each algorithm to converge after a topology change. LPA is shown to achieve loop freedom at every instant without much additional overhead over that incurred by prior algorithms based on second-to-last hop and distance information.

Subject Categories:

  • Numerical Mathematics
  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE