Routing in the Internet Using Partial Link State Information

Abstract

This thesis focuses on routing in wired and wireless segments of the Internet using partial link-state information. Although efficient algorithms have been proposed based on both link-state and distance-vector information, link-state routing is more efficient than distance-vector routing when constraints are placed on the paths offered to destinations, which is the case for QoS routing offering paths with required delay, bandwidth, reliability, cost, or other parameters. We present a new link-state routing protocol for wired internetworks called ALP (adaptive link-state protocol). In ALP, a router sends updates to its neighbors regarding the links in its preferred paths to destinations. Each router decides which links to report to its neighbors based on its local computation of preferred paths. A router running ALP does not ask its neighbors to delete links; instead, a router simply updates its neighbors with the most recent information about those links it decides to take out of its preferred paths. We introduce and analyze two routing algorithms for wireless networks: the source- tree adaptive routing (STAR) protocol, and the neighborhood-aware source routing (NSR) protocol. STAR is the first example of a table-driven routing protocol that is more efficient than prior table-driven and on-demand routing protocols by exploiting link-state information to allow paths taken to destinations to deviate from the optimum in order to save bandwidth without creating loops. NSR is an on-demand routing protocol based on partial topology information and source routing. STAR is shown to be more efficient than the dynamic source routing (DSR) protocol in small ad hoc networks, and NSR is shown to outperform STAR and DSR in large wireless networks with mobile nodes.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 2001
Accession Number
ADA461710

Entities

People

  • Marcelo Spohn

Organizations

  • University of California, Santa Cruz

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Ad Hoc Networks
  • Algorithms
  • Computer Networks
  • Distribution Functions
  • Internet
  • Internet Routing
  • Mesh Networks
  • Network Computing
  • Network Protocols
  • Network Topology
  • Networks
  • Routing Protocols
  • Simulations
  • Time Intervals
  • Wireless Networks

Fields of Study

  • Computer science

Readers

  • Computer Networking