Fault-tolerance In Interconnection Networks

The rapid development of information technology has pushed the quick in-creasing of the quantity of information and the amount of calculation. There is an urgent need to improve the computing power and performance of computer systems. This reason has motivated the research on the parallel computer systems. In order to improve the performance dramatically, a parallel computer system takes some interconnection network as underlying topology, and its multiple arithmetic units are connected to perform parallel operations. Obviously, the functions of parallel computer systems rely heavily on the interconnection networks of these systems. Fault-tolerance of the interconnection networks is an ability to remain some proper-ties in the presence of failures, and is also a crucial factor to evaluate the performance of the interconnection networks. An interconnection network can be modelled as a graph, where each vertex in the graph corresponds to a processor, and each edge in the graph corresponds to a communication link. In this thesis, using graph theory as a tool, we study the interconnection networks’ability to remain three proper-ties:the existence of perfect matchings or almost perfect matchings, the existence of subnetworks, and the edge connectivity.This thesis consists of five chapters. In Chapter 1, after a brief introduction to the background of interconnection networks, the used basic notation and terminology on graphs and the properties of some famous interconnection networks are given. Finally, we give a survey on research advance of the related works and list our main results.The k-ary n-cube is one of the most commonly used interconnection topologies for parallel computing systems. Several parallel systems have been built based on the k-ary n-cube, and so it is meaningful to study the fault-tolerance of k-ary n-cubes. In Chapter 2, we first consider k-ary n-cubes’ ability to remain the property of having a perfect matching or an almost perfect matching in the presence of failures. We establish the minimum number of failures that make the faulty k-ary n-cube having neither a perfect matching nor an almost perfect matching, and characterize all the corresponding faulty sets. Secondly, we are interested in finding fn,m, the minimum number of faulty edges that make every k-ary (n - m)-cube faulty in a k-ary n-cube under edge failure models. We derive the exact values of fn,m for some special cases, and obtain a better upper bound on fn,m for the general case.The torus network is a generalizing interconnection topology of the k-ary n-cube, and has drawn considerable research attention. The study of fault-tolerance in torus networks is helpful in choosing the underlying interconnection topologies of parallel computing systems. In Chapter 3, we mainly study torus networks’ ability to remain the property of having a perfect matching or an almost perfect matching in the presence of failures. We first establish the minimum number of failures that make the faulty bipartite torus network having neither a perfect matching nor an al-most perfect matching, and characterize all the corresponding faulty sets. Secondly, we establish the minimum number of failures that make the faulty 2-dimensional nonbipartite torus network having neither a perfect matching nor an almost perfect matching, and characterize all the corresponding faulty sets except for some special cases.The network-on-chip is a crucial factor in multicore technology, and has drawn considerable attention. Some systems-on-chip have been built based on the star network because of its desirable properties. The (n, k)-arrangement graph was pro-posed as a generalization of the star network. The study of fault-tolerance in (n, k)-arrangement graphs is helpful in choosing the underlying interconnection topologies of systems-on-chip. In Chapter 4, we first investigate Fm(n, k) (resp. fm(n, k)), the minimum number of faulty vertices (resp. edges) that make every (n - m, k - m)-arrangement graph faulty in an (n, k)-arrangement graph under vertex (resp. edge) failure models. We derive the exact values of Fm(n, k) and fm(n, k) for some spe-cial cases, and obtain better upper bounds on Fm(n,k) and fm(n,k) for the gen-eral case. Secondly, we consider (n, k)-arrangement graphs’ ability to remain the property of having a perfect matching or an almost perfect matching in the pres-ence of failures and establish the minimum number of failures that make the faulty (n, k)-arrangement graph having neither a perfect matching nor an almost perfect matching.The reliable networks can remain connected in the presence of failures. It is desirable to choose reliable interconnection networks for systems. The edge connectivity is a crucial index to evaluate the reliability of interconnection net-works. As a more refined index than the edge connectivity, k isoperimetric edge connectivity was proposed. The k-isoperimetric edge connectivity of a network G is defined as γk(G) = min{|[X,X]|:X C V(G),|X|> k,|X|> k}. Generally, βk(G)= min{|[X,X]|:X C V(G),|X| = k} is an upper bound on γk(G). G is called a γk-optimal network if γk(G)= βk(G). An edge cut S= [X, X] is called a γk-cut if|S| = γk(G), X (?) V(G),|X|≥k and |X|≥ k. Moreover, G is called a super-γk network if every γk-cut [X, X] of G has the property that either |X|= k or |X| = k. In view of recent studies, it seems that the γk-optimal (or super-γk) networks are more reliable. In Chapter 5, we present neighborhood conditions for γk-optimal networks and super-γk networks. Our results are useful in designing large scale reliable interconnection networks.