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 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.