MPATH: A Loop-free Multipath Routing Algorithm

Abstract

We present a distributed routing algorithm for computing multiple paths between each source-destination pair in a computer network, such that the paths are loop-free at all times and are not necessarily of equal length. In this algorithm, routers exchange second-to-last hop on the shortest path to destinations in addition to shortest distances, which are used to prevent the well-know count-to-infinity problem. The safety and liveness properties of the algorithm are proved and its performance is analyzed.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 2000
Accession Number
ADA457391

Entities

People

  • J.J. Garcia-Luna-Aceves
  • Srinivas Vutukury

Organizations

  • University of California, Santa Cruz

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • California
  • Computations
  • Computer Networks
  • Computer Science
  • Computers
  • Convergence
  • Engineering
  • Information Operations
  • Mathematics
  • Network Topology
  • Networks
  • Recovery
  • Routing Protocols
  • Simulations
  • Simulators
  • Topology

Fields of Study

  • Computer science

Readers

  • Computer Networking