Probabilistic Analysis To Mesh Network Fault Tolerance

Mesh network topology is one of the most important and attractive network topologies in parallel computer systems so far. In this thesis, we study the fault tolerance of mesh networks under a probabilistic model and propose a new concept called k-submesh structure in two- and three-dimensional mesh networks, which builds the basis of our proposed fault tolerant models, and we propose simple and efficient fault tolerant unicast and broadcast routing algorithms and apply probabilistic approach to validating the proposed models and algorithms.The thesis studies the fault tolerance of mesh networks under a more realistic model in which each network node has an independent failure probability and introduces k-submesh connectivity based on the concept of k-submesh structure. We prove that if the node failure probability is fixed, then the connectivity probability of mesh networks can be arbitrarily small when the mesh network size is sufficiently large. Thus, it is practically important for multicomputer systems manufacturer to determine the upper bound for node failure probability when the probability of network connectivity and the network size are given. We develop novel methods to formally derive lower bounds on the connectivity probability for mesh networks. Our results show that mesh networks of practical size can tolerate a large number of faulty nodes thus are reliable enough for multicomputer systems. We also show a number of advantages of three-dimensional mesh networks over other popular network topologies. Compared to two-dimensional mesh networks, three-dimensional mesh networks are much stronger in tolerating faulty nodes, while for practical network size, the fault tolerance of three-dimensional mesh networks is comparable with that of hypercube networks but enjoys much lower node degree.The thesis proposes efficient unicast routing algorithms for two- and three- dimensional mesh networks based on the concept of k-submesh, those algorithms are distributed and local information based. Due to the fact that our algorithms are designed based on k-submesh structure, we apply probabilistic analysis on the fault tolerance of ourrouting algorithms. Suppose each node has an independent failure probability, we derive the probability that our routing algorithms successfully return a fault-free routing path. Our algorithms run in liner time and our simulation results show that the length of the routing paths constructed by our algorithms are very close to the optimal length.The thesis develops efficient broadcast routing algorithms for two- and three- dimensional mesh networks based on the concept of &-submesh structure, these algorithms are distributed and local information based. Suppose each node has an independent failure probability, we derive the probability that our broadcast routing algorithms successfully broadcast a message for a given source node to all non-faulty nodes, our results show that broadcast tree by our algorithms can tolerant quite a few faulty nodes. Simulation results show that our algorithms are practically efficient and effective, and the time steps of our algorithms are very close to the optimum.We point out that these unicast and broadcast routing algorithms have practically important significance. On the one hand, our algorithms are local information based in the sense, because each node knows only its neighbors' status and no global information of the network is required by our algorithms in the course of routing, on the other hand, when routing algorithms are running in each /c-submesh, this A:-submesh can independently finish routing operations and doesn't consider operations in other &-submesh, so our algorithms are distributed based. In addition, our algorithms are valuable both in theory and in practice. Our scheme has very general significance for determining lower bounds on the network fault tolerance and fault tolerant routing algorithms. Our method is also applicable to study of other hierarchical network structures and other network communication problems.