Award Date

1-1-2001

Degree Type

Thesis

Degree Name

Master of Science (MS)

Department

Computer Science

First Committee Member

Ajoy Kumar Datta

Number of Pages

69

Abstract

The Pivot Interval Routing (PIR) scheme [EGP98] divides the nodes in the network into pivots and clients of the pivots. A pivot acts as a center for the partition of the network formed by its clients. Each node can send messages directly only to a small subset of vertices in its nearby vicinity or to the pivots; An algorithm is called self-stabilizing [Dij74] if, starting from an arbitrary initial state, it is guaranteed to reach a correct state in finite time and with no exterior help. In this thesis, we present a self-stabilizing PIR algorithm. The algorithm starts with no knowledge of the network architecture and, eventually, each node builds its own routing table of size O(n1/2log3/2 n + Deltaupsilon, log n) bits with a total of O(n3/2 log3/2 n) bits. The stabilization time of the algorithm is O&parl0;dn1+logn &parr0; time units, where n is the number of nodes and d is the diameter of the network. (Abstract shortened by UMI.).

Keywords

General; Interval; Networks; Routing; Scheme; Self; Stabilizing

Controlled Subject

Computer science

File Format

pdf

File Size

1945.6 KB

Degree Grantor

University of Nevada, Las Vegas

Language

English

Permissions

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 digitalscholarship@unlv.edu and include clear identification of the work, preferably with URL.

Rights

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

Download


COinS