Self-stabilizing interval routing algorithm with low stretch factor

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.

Name thesis:degree_name

Master of Science (MS)

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

University of Nevada, Las Vegas

Year

2001

Author dc:creator

• Sundaram, Sripriya

Contributors dc:contributor

• Ajoy Kumar Datta

Statement dc:rights

• IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Language dc:language

English

Identifier

https://oasis.library.unlv.edu/rtds/1263

OAI identifier oai:identifier

oai:oasis.library.unlv.edu:rtds-2262