A Path-Finding Algorithm for Loop-Free Routing

Abstract

A loop-free path-finding algorithm (LPA) is presented: this is the first routing algorithm that eliminates the formation of temporary routing loops without the need for internodal synchronization spanning multiple hops or the specification of complete or variable-size path information. Like other previous algorithms, LPA operates by specifying the second-to-last hop and distance to each destination; this feature is used to ensure termination. In addition, LPA uses an inter-neighbor synchronization mechanism to eliminate temporary routing loops. A detailed proof of LPA's correctness and loop-freedom property is presented and its complexity is evaluated.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2006
Accession Number
ADA457377

Entities

People

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

Organizations

  • University of California, Santa Cruz

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Availability
  • California
  • Classification
  • Computers
  • Contracts
  • Cooperation
  • Engineering
  • Information Operations
  • Instructions
  • Monitoring
  • Mountains
  • Recovery
  • Security
  • Specifications
  • Standards

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computer Networking