The Fault-tolerant Analysis Of Interconnection Networks

The first step in the designing and implementing large scale parallel computing system is to construct interconnection networks topological structure. Interconnection networks is also foundation of implementing all kinds of protocol and it plays an important role in the performance, system dependability, and cost of the networks. Interconnection networks are often modeled as a graph with vertex representing processor and an edge representing communication channel between processors. So the study of topological structure of interconnection networks is turned to the study structure of graph. And the study of fault-tolerant of network can transform to the study the parameter of graph. The parameters to evaluate the performance of interconnection networksare as follows:(1)Hardware complexity: It can be evaluated by the degree of vertex of topological graph.(2)Commuication expenses: It can be evaluated the diameter or average distance of topological graph.(3)Expandability: It can be come down to the problem of embedability of some special structures.(4)Fault tolerance: It can be evaluated by the connectivity, edge-connectivity, fault-tolerant diameter, width diameter, restricted connectivity, restricted edge connectivity of graph.The widely studied topological structure are mesh-connected networks, tree networks, hypercube networks and star networks. We mainly consider the faulttolerant properties of these networks in this thesis. Our research concentrate on the following:First, We survey the fault tolerant parameters of topological structure of interconnection networks such as communication delay, fanlt-tolarant diameter, width diamater and connectivity. based on this, we propose some problem that worth further studying. Then, we studied the subgraph of hypercube-Extended Fibonacci cube.The Extended Fibonacci cube are widely studied, many parameters are determined, including connectivity,recursion,embed ring and mesh,diameter. In this thesis, we studied the fault-tolerant diameter, width diameter, restricted edge connectivity, extra edge connectivity of Extended Fibonacci cubes and proved that the fault tolerant diameter, width diameter is equal to diameter plus 1, determined 1-restricted edge connectivity and 1-extra edge connectivity of Extended Fibonacci cubes.