Dynamics of a Loop-Free Path-Finding Algorithm

reportActive / Technical Report | Accession Number: ADA459117 | Open PDF

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.

Author(s):
Murthy, Shree ; Garcia-luna-aceves, J. J.
Author Organization(s):
CALIFORNIA UNIV SANTA CRUZ DEPT OF COMPUTER ENGINEERING
Descriptive Note:
Research paper
Supplementary Note:
Sponsored in part by the Advanced Research Projects Agency (ARPA).
Pagination:
0006

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release
Distribution Statement:
Approved For Public Release; Distribution Is Unlimited.

RECORD

Collection: TR
Identifying Numbers
Contract/Grant Number(s):
N00014-92-J-1807, F19628-93-C-0175
Monitor Series:
ONR
 Subject Terms
Joint Capability Areas:
JCA_6.1.3_Switching and Routing; JCA_6_Net Centric; JCA_6.1_Information Transport; JCA_5_Command and Control; JCA_5.2.3_Share Knowledge and Situational Awareness; JCA_5.2_Understand; JCA_1.2.5_Lessons Learned; JCA_8_Building Partnerships; JCA_5.3_Planning; JCA_8.2_Shape; JCA_1_Force Support; JCA_8.2.5_Strengthen Global Defense Posture
Communities of Interest:
No COI(s) Identified
Descriptor(s):
*DYNAMIC RESPONSE, *ROUTING, *MESSAGE PROCESSING, *COMPUTER NETWORKS, *PACKET SWITCHING, *WIRELESS LINKS, *COMMUNICATIONS PROTOCOLS, ALGORITHMS, COMPUTERIZED SIMULATION, RECOVERY, FAILURE, COSTS, STATISTICAL ANALYSIS, DELAY, NODES, PATHS, PERFORMANCE(ENGINEERING), COMPARISON
Field(s)/Group(s):
Computer Systems, Computer Systems Management and Standards, Telemetry, Radio Communications
Keyword(s):
*LPA ALGORITHM, LPA(LOOP FREE PATH FINDING ALGORITHM), LOOP FREE ALGORITHMS, *DUAL ALGORITHM, *ILS ALGORITHM, ILS(IDEAL LINK STATE ALGORITHM), COMPARATIVE ANALYSIS, ROUTING TABLES, PREDECESSOR INFORMATION, INTER NEIGHBOR SYNCHRONIZATION MECHANISM, FEASIBILITY CONDITION, DUAL(DIFFUSING UPDATE ALGORITHM), ARPANET TOPOLOGY, LINK COST CHANGES, LINK FAILURE, LINK RECOVERY, NODE FAILURE, NODE RECOVERY
Report Date:
1994 Jan 01
Creation Date:
2007 Jan 10