CCE Theses and Dissertations

Structural Design of a Fast Convergence Algorithm: A Semi-Universal Routing Protocol

Date of Award

2000

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Graduate School of Computer and Information Sciences

Advisor

S. Rollins Guild

Committee Member

Lee J. Leitner

Committee Member

Gregory Simco

Abstract

The function of a routing algorithm is to guide packets through the communication network to the correct destinations. The goal of this study was to design and to analyze a loop-free fast-convergence routing algorithm. The introduction consisted of a general framework on which the algorithm was based. This general model formed the basis of a proposal for a routing protocol suitable to heterogeneous environments. This research focused on link-state algorithms.

The subject of this investigation was a new routing algorithm called fast convergence algorithm (FEA). FEA did not only reduce the number of cases in which a temporary routing loop could occur but also was designed to be loop free at every instant. The hierarchical characteristics of FEA allowed the new algorithm to handle aggregation of routing information, a technique that was mandatory for accommodating the increasing number of Internet users. FEA was shown to converge in finite time after an arbitrary sequence of link cost or topological changes and to outperform all other loop-free routing algorithms already proposed.

In FEA, each router maintained a subset of the topology corresponding to the links used by its neighbor routers in their preferred paths to known destinations. Based on that subset of topology information, routers derived their own preferred paths and communicated the corresponding link-state information to their neighbors. Simulations were used to show FEA to be much more efficient than the diffusing update algorithm and the shortest path algorithm in terms of speed, communication and processing overhead required to converge to correct routing tables. FEA’s correctness was verified for arbitrary types of routing when correct and deterministic algorithms were used to select preferred paths at each router. To increase the responsiveness of a routing protocol and to guarantee the quality of service required by users, FEA integrated routing and congestion control mechanisms.

This feature ensured that packets arriving into a packet-switched network were delivered unless a resource failure occurred. This technique ensured a high level of performance for network flows. Update messages from a node were sent only to its neighbors. Each such message contained a distance vector of one or more entries, and each entry specified the length of the selected path to a network destination, as well as an indication of whether the entry constituted an update, a query, or a reply to a previous query.

This document is currently not available here.

  Link to NovaCat

Share

COinS