Award Date

12-2010

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Ajoy K. Datta, Chair

Second Committee Member

Lawrence L. Larmore

Third Committee Member

Yoohwan Kim

Graduate Faculty Representative

Emma E. Regentova

Number of Pages

126

Abstract

Link failure is a common reason for disruption in communication networks. If communication between processes of a weighted distributed network is maintained by a spanning tree T, and if one edge e of T fails, communication can be restored by finding a new spanning tree, T’. If the network is 2-edge connected, T’ can always be constructed by replacing e by a single edge, e’, of the network. We refer to e’ as a swap edge of e.


The best swap edge problem is to find the best choice of e’, that is, that e which causes the new spanning tree T’ to have the least cost, where cost is measured in a way that is determined by the application. Two examples of such measures are total weight of T‘ and diameter of T’.


The all best swap edges problem is the problem of determining, in advance of any failure, the best swap edge for every edge in T. The justification for this problem is that we wish to be ready, when a failure occurs, to quickly activate a replacement for the failed edge.


In this thesis, we give algorithms for the all best swap edges problem for six different cost measures. We first present an algorithm which can be adapted to all six measures, and which takes O (d2) time, where d is the diameter of T. This algorithm is essentially a form of distributed dynamic programming, since we compute the answers to sub problems at each node of T.


We then present a novel paradigm for speeding up distributed computations under certain conditions. We apply this paradigm to find O(d)-time distributed algorithms for the all best swap edge problem for all but one of our cost measures.


Formal algorithms and their correctness proofs will be given.

Disciplines

Computer and Systems Architecture | Computer Sciences | Digital Communications and Networking | OS and Networks

File Format

pdf

Degree Grantor

University of Nevada, Las Vegas

Language

English

Rights

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

Download


Share

COinS