Reliable communication in the hypercube with the safety vectors is discussed in this thesis. In the hypercube, the safety levels and the safety vectors, used to guide fault-tolerant routing, is a kind of limited global information based methods. The transmission cost of the safety vectors is O(n2) for each node. For increasing the probability of optimal routing, we attempt to increase the transmission cost for obtaining more information. We propose two methods with O(n3) transmission cost in each node, the enhanced safety vector and the spanning safety vector, to achieve the goal. We also propose the probabilistic safety vector which provides the probability of optimal routing for each node. Finally, our experiments show that the routing with the enhanced safety vector is more reliable than the safety vectors and the extended safety vectors, which were propose the probabilistic safety vector.

Message routing is a fundamental function of a network, and fault-tolerance is an important tool to ensure the quality of service of a network. Assume that network contain only one faulty element. In order to ensure the message can be arrived. We present a fault-tolerant message routing algorithm which being the secondary path, as the optimal path can't be connected in the double-loop networks.

Growing complexity of Systems on Chip (SoC) introduces interconnection problems. As a solution for communication bottleneck the new paradigm, Networks on Chip (NoC), has been proposed. Along with high performance and reliability, NoC brings in area and energy constraints. In this thesis we mainly concentrate on keeping communication-centric design environment fault-tolerant while considering area overhead. The previous researches suggest the adoption solution for fault-tolerance from multiprocessor architectures. However, multiprocessor architectures have excessive reliance on buffering leading to costly solutions. We propose to reconsider general router model by introducing central buffers which reduces buffer size. Besides, we offer a new fault-tolerant routing algorithm which effectively utilizes buffers at hand without additional buffers out of detriment to performance.

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.