Loop-Free Internet Routing Using Hierarchical Routing Trees

Abstract

The authors present a new hierarchical routing algorithm that combines the loop-free path-finding algorithm (LPA) with the area-based hierarchical routing scheme first proposed by McQuillan for distance-vector algorithms. The new algorithm, which they call the Hierarchical Information Path-based Routing (HIPR) algorithm, accommodates an arbitrary number of aggregation levels and can be viewed as a distributed version of Dijkstra's algorithm running over a hierarchical graph. HIPR is verified to be loop-free and correct. Simulations are used to show that HIPR is much more efficient than OSPF in terms of speed and the communication and processing overhead required to converge to correct routing tables. HIPR constitutes the basis for future Internet routing protocols that are as simple as RIPv2, but with no looping and better performance than protocols based on link states.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1997
Accession Number
ADA457721

Entities

People

  • J.J. Garcia-Luna-Aceves
  • Shree Murthy

Organizations

  • University of California, Santa Cruz

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Computer Networks
  • Computing Devices
  • Engineering
  • Information Operations
  • Internet
  • Internet Routing
  • Network Computing
  • Network Protocols
  • Recovery
  • Routing
  • Routing Protocols
  • Simulations

Fields of Study

  • Computer science

Readers

  • Computer Networking