Oregon State University

Calendar

Calendars

Event Details

PhD Oral Preliminary Examination – Omar Alsaleh


Thursday, March 14, 2013 11:00 AM - 1:00 PM

One-to-Many Node Disjoint Paths Routing in Generalized Hypercube and Gaussian Interconnection Networks
In parallel systems, the probability of faults becomes higher because of the continuous increase in the number of cores. Therefore, it is critical to find mutually node disjoint paths (NDP) in order to establish communication routes under such a faulty environment. Routing from a single source node to multiple destination nodes using NDP is called one-to-many NDP routing. This routing is fundamental and essential for ensuring fault tolerance in parallel systems. Also, it has many important applications. For example in one-to-many personalized communications algorithm, a node sends different messages to different nodes, and so efficient algorithms can be designed based on NDP.

The cores in parallel systems are connected using interconnection networks. Some of the topologies are hypercube, mesh, torus, tree, De Bruijn, etc. In this work, we consider the Generalized Hypercube (GH) and Gaussian interconnection networks. Unlike the existing types of hypercube, the GH interconnection networks support any number of nodes. However, they possess a small average message distance and a low traffic density, thereby making it highly fault tolerant. The Gaussian interconnection networks can accommodate more nodes with less communication latency while maintaining a regular grid-like structure and a low node degree.

In this work, we first design efficient algorithms that find NDP from a single source node to the maximum number of destination nodes in GH and Gaussian interconnection networks. Then, we prove that these algorithms always return a solution. Also, we derive the lower bound and upper bound of the path lengths and the time complexity of the algorithms. For the GH interconnection networks, we show via simulation that most of the time the upper bound is less than the theoretical upper bound.

Major Advisor: Bechir Hamdaoui
Co-Major Advisor: Bella Bose
Committee: Huaping Liu
Committee: Eduardo Cotilla-Sanchez
GCR: Harold Parks 


Kelley Engineering Center (campus map)
1114
Nicole Thompson
1 541 737 3617
Nicole.Thompson at oregonstate.edu
Sch Elect Engr/Comp Sci
This event appears on the following calendars: