A More Efficient Path-Finding Algorithm

Abstract

In this paper, we present a new routing algorithm, which we call path-finding algorithm (PFA). It drastically reduces the possibility of temporary routing loops, which accounts for its fast convergence properties. Like other path-finding algorithms, PFA operates by specifying the second-to-last hop to each destination, in addition to the distance to the destination. A detailed proof of correctness and complexity is presented elsewhere. PFA's performance is compared quantitatively by simulation with DUAL (a loop-free routing algorithm) and an ideal link-state algorithm (ILS). A number of parameters, including the length of the messages and the number of steps required for convergence, are used in the comparison.

Open PDF

Document Details

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

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
  • Convergence
  • Engineering
  • Information Operations
  • Instructions
  • Monitoring
  • Security
  • Simulations
  • Simulators
  • Standards

Fields of Study

  • Computer science

Readers

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