Studies On Reliability Of Some Networks

The topological structure of interconnection network is the connection form among units in computer systems and communication systems, and is one of important facters to determine the properties of the systems. It is a new field to study and analyse the effects of the network developing in the past decade years. Combinatorial mathematics is most useful tool to study and analyse the topological structures of networks. In particular the concepts and methods of graph theory play an important role in investigating the efficiency and fault tolence of networks. With studying and analysing of the topological structures of networks, many problems of nerworks and concepts of graph theory are proposed, which can measure the efficiency and fault tolerance of networks more accurately.In a faulty network, the failure of nodes and(or) lines will result in the increasing of the delay of digital transformation. In order to know what the effects of the faulty stations are, that is to say, the maximum delay in a faulty network, people introduce a new concept: fault diameter.In the network of parallel computing, information is parallelly transformed through a collection of internally vertex-disjiont paths. For the network, it is not enough to consider connectivity and diameter alone. Although the network is high-connectivity and small-diameter, some paths maybe very long when information is parallelly transformed by a collection of internally vertex-disjiont paths. So the transformation delay is large, the time interval of news reached is very long. This affects the efficiency of the whole system. So we consider the connectivity and diameter synthesisly and present the wide diameter. In addition, a new measure: (l, k)-dominating number is proposed to study the parallel system in which resources is shared.When we analyse the network with the previous concepts, it has generally been assumed that any subset of system components (processors or links) can potentially fail at the same time. But in some networks, it can be supposed that some subsets of system components can't fail at the same time. For the network, it is unaccurate for classical connectivity to measure the fault-tolerance property. So some new concepts are proposed, such as restricted connectivity, restricted edge connectivity, restricted fault diameter. They can analyse the reliability of networks more accurately.In this paper, the previous concepts are investigated on mesh network, pyramid network, butterfly network which are widely used in parallel computing system.The following is the main work of the paper.Chapter one. Firstly we give some concepts, notations and fundamental theorems of graph theory which are used in following chapters. Secondly we simplely introduce some fundamental topological structures of networks. Finally significantly introduce some measures to judge the efficiency and fault tolerance of interconnection networks and the development of studying.Chapter two. We introduce the definition of mesh network and prove the wide diameter and (l, k) -dominating number of mesh network by the internally vertex-disjoint paths between two arbitrary vertexs.Chapter three. Firstly we introduce the definition of the pyramid network and give the recurrence form of the pyramid network which is used in proving the theorems in this chapter. The pyramid network is one of the important structures in parallel and network computing and image processing. Secondly we determine the (l, k)-dominating number by the wide distance between the root and any other node. Thirdly we investigate the restricted connectivity and the restricted edge connectivity. In a faulty pyramid network, we present the restricted fault diameter by constructive algorithm.Chapter four. We introduce the definition of the butterfly network. Proceeding we determine the (l, k)-dominating number by wide distance. In the forbidden faulty set, we consider the restricted diameter.