Routing in the Internet using partial link state information

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.