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 onetomany NDP routing is useful.
Unlike parallel systems with sharedmemory, 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 onetomany 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 onetomany 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 

NonAcademic Affiliation 

Keyword 

Subject 

Rights Statement 

Peer Reviewed 

Language 

Replaces 

Additional Information 
 description.provenance : Approved for entry into archive by Julie Kurtz(julie.kurtz@oregonstate.edu) on 20140116T18:38:45Z (GMT) No. of bitstreams: 1
AlsalehOmarI2014.pdf: 5623952 bytes, checksum: 4c4e93040f1d05de73fae19bb4507a7f (MD5)
 description.provenance : Made available in DSpace on 20140117T00:34:13Z (GMT). No. of bitstreams: 1
AlsalehOmarI2014.pdf: 5623952 bytes, checksum: 4c4e93040f1d05de73fae19bb4507a7f (MD5)
Previous issue date: 20131205
 description.provenance : Approved for entry into archive by Laura Wilson(laura.wilson@oregonstate.edu) on 20140117T00: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 20140114T21:03:45Z
No. of bitstreams: 1
AlsalehOmarI2014.pdf: 5623952 bytes, checksum: 4c4e93040f1d05de73fae19bb4507a7f (MD5)
