OnetoMany Node Disjoint Paths Routing in Generalized Hypercube, Dense Gaussian, and Hexagonal Mesh Networks
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 a faulty environment. Moreover, the onetomany NDP routing increases 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.
CoMajor Advisor: Bella Bose
CoMajor Advisor: Bechir Hamdaoui
Committee: Huaping Liu
Committee: Eduardo CotillaSanchez
GCR: Harold Parks
Kelley Engineering Center (campus map) 

4107 

Nicole Thompson 

1 541 737 3617 

Nicole.Thompson at oregonstate.edu 

Sch Elect Engr/Comp Sci 