When the number of nodes increases, the chance that nodes or links fail increases. Then a fault-tolerant routing method is important to maintian the performance of the system. In the hypercube, safety levels and safety vectors provide the fault distribution information used to guide routing fault-tolerantly. The safety vectors for the hypercube describes the fault distribution more percisely than the safety level. The concept of safety levels has been applied to the star graph by other researchers. In this thesis, we apply the concept of the safety vectors in the hypercube to the star graph, and define three different safety vectors, including undirected safety vector, directed safety vector, and statistical safety vector. We first show the ability of the undirected safety vector. Then we extend the ideal to the directed safety vector and show it is better in deciding routing paths than the safety level for the star graph. We also show the reason that makes the directed safety vector not able to be used for derouting. In the previous result, a little change can make the directed safety vector usable for derouting in the hypercube. However, for the star graph, we can use only the information of neighbors to perform derouting with a slight modification in the directed safety vector. Then we set levels to the routing ability using the statistical safety vector. Try to make it contain more information of the fault distribution.

In the first part of the thesis we define an automorphism φn for each star graph Stn of degree n-1, which yields permutations of labels for the edges of Stn taken from the set of integers {1,..., [n/2c]}. By decomposing these permutations into permutation cycles, we are able to identify edge-disjoint Hamilton cycles that are automorphic images of a known two-labelled Hamilton cycle H1 2(n) in Stn. The search for edge-disjoint Hamilton cycles in star graphs is important for the design of interconnection network topologies in computer science. All our results improve on the known bounds for numbers of any kind of edge-disjoint Hamilton cycles in star graphs.

In this thesis, we focus on the design of the fault-tolerant routing algorithm for the (n, k)-star graph. We apply the idea of collecting the limited global information used for routing on the n-star graph to the (n, k)-star graph. First, we build the probabilistic safety vector (PSV) with modified cycle patterns. Then, our routing algorithm decides the fault-free routing path with the help of PSV. In order to improve the routing performance with more faulty nodes, we dynamically assign the threshold for our routing algorithm. The performance is judged by the average length of routing paths. Compared with distance first search and safety level, we get the best performance in the simulations.

No description available.