Graduate Thesis Or Dissertation
 

One-to-many node disjoint paths routing in generalized hypercube, dense Gaussian, and hexagonal mesh networks

Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/hh63t066t

Descriptions

Attribute NameValues
Creator
Abstract
  • Routing from a single source node to multiple destination nodes using node disjoint paths (NDP) has many important applications in parallel systems. For example, if a source node wants to send distinct messages to distinct destination nodes, then the one-to-many NDP routing is useful. Unlike parallel systems with shared-memory, each node in most of the current parallel systems is a standalone processing unit with a processor and memory. The nodes communicate with each other by passing messages using a standard message passing mechanism such as the Message Passing Interface (MPI). The probability of failure in delivering the messages between the nodes directly affects the computing performance. This probability increases as the number of nodes increases. Therefore, it is critical to find a set of mutually node disjoint paths in order to establish communication routes under such faulty environment. Moreover, the one-to-many NDP routing increases the throughput of the networks. In this work, we provide some novel and efficient routing algorithms that construct a set of NDP from a single source node to the maximum number of destination nodes in three promising interconnection networks. They are Generalized Hypercube, dense Gaussian, and Hexagonal Mesh networks. In Chapter two, two efficient algorithms that construct a set of NDP from a single source node to the maximum number of destination nodes in Generalized Hypercube networks are given. Also, the lower and upper bounds of the path length from the source node to any destination node are derived. Finally, some simulations of the algorithms are performed and the results show that in most cases the maximum path length is equal to the shortest distance plus one. In Chapter three and Chapter four, efficient constant time complexity algorithms that construct a set of one-to-many NDP in dense Gaussian and Hexagonal Mesh networks are given, respectively. For the dense Gaussian network, the lower and upper bounds of the sum of the NDP lengths are derived. Also, via execution of the algorithm, it is shown that on average the sum of the lengths of NDP given by the algorithm is only about 10% more than the sum of the lengths of the shortest paths.
License
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Publisher
Peer Reviewed
Language
Replaces

Relationships

Parents:

This work has no parents.

In Collection:

Items

Thumbnail Title Date Uploaded Visibility Actions
file details AlsalehOmarI2014.pdf 2017-08-23 Public Download