MDVA: A Distance-Vector Multipath Routing Protocol

Abstract

Routing protocols using the Distributed Bellman-Ford (DBF) algorithm converge very slowly to the correct routes when link costs increase, and in the case where a set of link failures results in a network partition, DBF simply fails to converge, a problem that is commonly referred to as the count-to-infinity problem. In this paper, the authors present the first distance vector routing algorithm, the Multipath Distance-Vector Algorithm (MDVA), that uses a set of loop-free invariants to prevent the count-to-infinity problem. In addition, MDVA computes multipaths that are loop-free at every instant. In their earlier work, the authors showed how such loop-free multipaths can be used in traffic load-balancing and delay minimization, which otherwise are impossible to perform in current single-path routing algorithms.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2001
Accession Number
ADA460988

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
  • Computations
  • Computer Networks
  • Computer Science
  • Computers
  • Convergence
  • Distribution Functions
  • Networks
  • Phase Transformations
  • Probability
  • Probability Distribution Functions
  • Probability Distributions
  • Routing Protocols
  • Simulations
  • Simulators
  • Topology
  • Transitions

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Linear Algebra