Accession Number:

ADA461682

Title:

Distributed, Scalable Routing Based on Vectors of Link States

Descriptive Note:

Conference paper

Corporate Author:

CALIFORNIA UNIV SANTA CRUZ DEPT OF COMPUTER ENGINEERING

Report Date:

1994-09-01

Pagination or Media Count:

14.0

Abstract:

Link vector algorithms LVA are introduced for the distributed maintenance of routing information in large networks and internets. According to an LVA, each router maintains a subset of the topology that corresponds to adjacent links and those links used by its neighbor routers in their preferred paths to known destinations. Based on that subset of topology information, the router derives its own preferred paths and communicates the corresponding link-state information to its neighbors. An update message contains a vector of updates each such update specifies a link and its parameters. LVAs can be used for different types of routing. The correctness of LVAs is verified for arbitrary types of routing when correct and deterministic algorithms are used to select preferred paths at each router and each router is able to differentiate old updates from new. LVAs are shown to have better performance than the ideal link-state algorithm based on flooding and the distributed Bellman-Ford algorithm.

Subject Categories:

  • Computer Systems
  • Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE