When the size of the network gets larger, it is natural that there are some faulty nodes. When considering the connectivity property of faulty networks, traditional researches consider the lowest number of faulty nodes to disconnect the networks. However, only under rare situations is a network disconnected by the minimum number of faulty nodes. Practically, a network with even many more faulty nodes still has a good chance to be connected. Thus the fault tolerance property of networks is greatly underestimated under the traditional definition. In this thesis, we will use a more realistic model to analyze the fault tolerance property of two important network topologies for large multicomputer systems: hypercube networks and mesh networks.; We evaluate the fault tolerance property of faulty networks using a probability model. In particular, we consider the connectivity property of faulty mesh networks. We estimate the connectivity probability of a mesh network when the node failure probability is given. We also prove that the connectivity probability approaches zero when the size of a mesh network gets large for a fixed node failure probability.; Routing is an important operation in computer networks. We consider how to route between two nonfaulty nodes and estimate the success probability of finding a short path. We propose a group of routing algorithms for hypercube networks. The algorithms can find a feasible path, whose length is at most twice of the Hamming distance plus a small constant with very high probability even when the node failure probability is as large as 20%. For mesh networks, we design a Quasi-Manhattan Routing Algorithm, which returns a path of length less than 3.1 times the Manhattan distance plus a constant with a high probability when the node failure probability is bounded by 1%. To the author's knowledge, these results are the first group of fault tolerance results for networks that are based on probabilistic analysis obtained by formal and thorough mathematical proofs.
展开▼
