Master of Science (MS)
First Committee Member
Ajoy Kumar Datta
Number of Pages
A compact routing scheme is a routing strategy which suggests routing tables that are space efficient compared to traditional all-pairs shortest path routing algorithms. An Interval Routing algorithm is a compact routing algorithm which uses a routing table at every node in which a set of destination addresses that use the same output port are grouped into intervals of consecutive addresses. Self-stabilization is a property by which a system is guaranteed to reach a legitimate state in a finite number of steps starting from any arbitrary state. A self-stabilizing Pivot Interval Routing (PIR) algorithm is proposed in this work. The PIR strategy allows routing along paths whose stretch factor is at most five, and whose average stretch factor is at most three with routing tables of size O(n3/2log 23/2n) bits in total, where n is the number of nodes in the network. Stretch factor is the maximum ratio taken over all source-destination pairs between the length of the paths computed by the routing algorithm and the distance between the source and the destination. PIR is also an Interval Routing Scheme (IRS) using at most 2n( 1+lnn)1/2 intervals per link for the weighted graphs and 3n(1+ lnn)1/2 intervals per link for the unweighted graphs. The preprocessing stage of the PIR algorithm consists of nodelabeling and arc-labeling functions. The nodelabeling function re-labels the nodes with unique integers so as to facilitate fewer number of intervals per arc. The arc-labeling is done in such a fashion that the message delivery protocol takes an optimal path if both the source and the destination are located within a particular range from each other and takes a near-optimal path if they are farther from each other.
Algorithms; Factor; Interval; Low; Routing; Self; Stabilizing; Stretch
University of Nevada, Las Vegas
If you are the rightful copyright holder of this dissertation or thesis and wish to have the full text removed from Digital Scholarship@UNLV, please submit a request to email@example.com and include clear identification of the work, preferably with URL.
Sundaram, Sripriya, "Self-stabilizing interval routing algorithm with low stretch factor" (2001). UNLV Retrospective Theses & Dissertations. 1263.