Accession Number:

ADA461655

Title:

Scalable Link-State Internet Routing

Descriptive Note:

Conference paper

Corporate Author:

CALIFORNIA UNIV SANTA CRUZ DEPT OF COMPUTER ENGINEERING

Report Date:

1998-01-01

Pagination or Media Count:

11.0

Abstract:

We present and verify the Adaptive Link-State Protocol ALP, a new link-state routing protocol that does not require the state of each link to be flooded to the entire internetwork, or to entire areas if hierarchical routing is used. A router in ALP disseminates link-state updates incrementally to its neighbors for only those links along paths used to reach destinations. Link-state updates are validated using time stamps and contain the same information used in other link-state protocols. For the case of neighbor routers connected through a broadcast medium, a designated router is distributedly elected for each link state reported over the medium, rather than requiring a designated router to report every topology change over the broadcast medium, like OSPF does. Simulation experiments illustrate that ALP is as efficient as the Distributed-Bellman Ford algorithm when distances to destinations do not increase and resources do not fail, and more efficient than traditional link-state protocols based on flooding after distances increase or resources fail. ALP also outperforms the link-vector algorithm LVA, which is the only prior routing algorithm based on selective dissemination of link states.

Subject Categories:

  • Operations Research
  • Computer Systems
  • Computer Systems Management and Standards

Distribution Statement:

APPROVED FOR PUBLIC RELEASE