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

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/hh63t066t

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • 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.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Keyword
Subject
Rights Statement
Peer Reviewed
Language
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Laura Wilson(laura.wilson@oregonstate.edu) on 2014-01-17T00:34:13Z (GMT) No. of bitstreams: 1 AlsalehOmarI2014.pdf: 5623952 bytes, checksum: 4c4e93040f1d05de73fae19bb4507a7f (MD5)
  • description.provenance : Submitted by Omar Alsaleh (alsaleho@onid.orst.edu) on 2014-01-14T21:03:45Z No. of bitstreams: 1 AlsalehOmarI2014.pdf: 5623952 bytes, checksum: 4c4e93040f1d05de73fae19bb4507a7f (MD5)
  • description.provenance : Made available in DSpace on 2014-01-17T00:34:13Z (GMT). No. of bitstreams: 1 AlsalehOmarI2014.pdf: 5623952 bytes, checksum: 4c4e93040f1d05de73fae19bb4507a7f (MD5) Previous issue date: 2013-12-05
  • description.provenance : Approved for entry into archive by Julie Kurtz(julie.kurtz@oregonstate.edu) on 2014-01-16T18:38:45Z (GMT) No. of bitstreams: 1 AlsalehOmarI2014.pdf: 5623952 bytes, checksum: 4c4e93040f1d05de73fae19bb4507a7f (MD5)

Relationships

Parents:

This work has no parents.

Last modified

Downloadable Content

Download PDF

Items