Accession Number:

ADA459117

Title:

Dynamics of a Loop-Free Path-Finding Algorithm

Descriptive Note:

Research paper

Corporate Author:

CALIFORNIA UNIV SANTA CRUZ DEPT OF COMPUTER ENGINEERING

Report Date:

1995-01-01

Pagination or Media Count:

6.0

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. LPAs performance is always significantly better than DUALs and significantly better than ILSs 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.

Subject Categories:

  • Computer Systems
  • Computer Systems Management and Standards
  • Telemetry
  • Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE