A Distributed Algorithm for Multipath Computation

Abstract

Today's Internet routing protocols either provide a single path between each source-destination pair, or multiple paths of equal length. Furthermore, the paths provided by RIP and OSPF are not free of loops during times of network transition. Single-path routing algorithms are inherently slow in responding to congestion and temporary traffic bursts; consequently, the delays experienced by packets in these networks are far from optimal. Recently, we developed a framework for designing routing algorithms that offer "near-optimal" delays; a key component in this framework consists of using a fast responsive routing protocol that builds multipaths for each destination in the computer network, such that they are loop-free at all times. This paper studies the performance of MPATH (multipath routing algorithm) by simulation and compares it against the performance of other state-of-the-art routing algorithms.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1999
Accession Number
ADA461703

Entities

People

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

Organizations

  • University of California, Santa Cruz

Tags

DTIC Thesaurus Topics

  • Algorithms
  • California
  • Computations
  • Computer Networks
  • Computer Science
  • Contrast
  • Convergence
  • Information Operations
  • Network Topology
  • Networks
  • Recovery
  • Routing Protocols
  • Sequences
  • Simulations
  • Simulators
  • Steady State
  • Topology

Fields of Study

  • Computer science

Readers

  • Computer Networking