A New Approach to On-demand Loop-Free Multipath Routing

Abstract

We present and verify ROAM, an on-demand routing algorithm that maintains multiple loop-free paths to destinations. Each router maintains entries only for those destinations for which data flows through the router, which reduces storage space requirements and the amount of bandwidth needed to maintain correct routing tables. In ROAM, routes are established and maintained on demand using diffusing computations. A router does not send updates for active destinations, unless its distance to them increases beyond a given threshold. ROAM maintains state that informs routers when a destination is unreachable and prevents routers from sending unnecessary search packets attempting to find paths to an unreachable destination. ROAM is shown to converge in a finite time after an arbitrary sequence of topological changes and is shown to be loop-free at every instant. The time and communication complexities of ROAM are analyzed.

Open PDF

Document Details

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

Entities

People

  • J.J. Garcia-Luna-Aceves
  • Jyoti Raju

Organizations

  • University of California, Santa Cruz

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • California
  • Collision Avoidance
  • Computations
  • Computer Networks
  • Engineering
  • Floods
  • Information Operations
  • Networks
  • Notation
  • Routing Protocols
  • Sequences

Fields of Study

  • Computer science

Readers

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

Technology Areas

  • Space