The Study On Fault Tolerance Of Several Interconnection Networks

The topological structure of interconnection network is the connection form among units in computer systems and communication systems, and is an important facter to determine the properties of the systems. Graph theory is one of the most useful tools to study and analyse the topological structures of networks, and plays an important role in investigating the efficiency and fault tolerance of networks.In this paper, firstly we introduce some basic knowledges on graphs, some more accurate measures to judge the eficiency and fault tolerance of interconnection networks and the development of studying.Then we study several important parameters of the Pyramid network, Star network, and Hyper-Star network, which are widely used in parallel computing systems.The main work of the dissertation can be summarized as follows:1. The Pyramid network is one of the important structures in parallel computing and image processing. A new method to proof its restricted connectivity is presented by studying the topological structures of the pyramid network, and the restricted edg-connectivity of the pyramid network is obtained.2. The Star netwok, which has been considered as an attractive alternative to the hypercube network, has many good topological properties. In this paper, we compare two methods of its restricted connectivity by analysing the topological structures of the Star network, and obtain its restricted edg-connectivity.3. The hyper-star graph is introduced as a new interconnection networks, and its restricted connectivity and restricted edg-connectivity are investigated. Then we introduce its variation------ folded hyper-star graph which is more superior than the hypercube network, and get its connectivity and edge-connectivity.