Reliability Study Based On Network Topology Connectivity Parameters

Interconnection network in the actual operation process,it is inevitable that failures will occur,resulting in immeasurable losses,so it is necessary to design a good performance interconnection network.Reliability is a key indicator of the performance of interconnection networks,which was first studied in the context of telecommunication switched network systems.The failure of components in a network system leads to a decrease in the total communication capacity of the network system and induces call congestion,which is usually measured by the connectivity metric.The standard for measuring the reliability of a network system in terms of connectivity states that a network system can function properly as long as the system,its main parts,or the parties that need to communicate are connected,and this reliability is called fault tolerance.Connectivity and edge connectivity are classical parameters for measuring the fault tolerance of graph and interconnection networks,however,it has been found that they are deficient in measuring the fault tolerance of the network,i.e.,they do not take into account the situation of the residual graphs after graph cleavage.To address these problems,scholars have promoted the concept of connectivity,which not only considers the connectivity of the network,but also the degree of damage to the system caused by node or link failures,such as conditional connectivity,structure connectivity,substructure connectivity,etc.,which have been shown to be a better measure of the fault tolerance of networks.In this thesis,we use graph structure analysis,inverse method,graph decomposition method,classification discussion method and inductive hypothesis method to measure the reliability and fault tolerance level of the network by studying the connectivity of the network,and give the exact values of conditional connectivity and structure(substructure)connectivity of several types of typical networks,which are described as follows.First,component edge connectivity of general graphs(topologies of general networks)is studied.Results are given for the component edge connectivity of some special graphs:trees,cycles,complete graphs,complete bipartite graphs;carving out the component edge connectivity of a given component edge connectivity cλr(G)=1,2,3,(2n-r)(r-1)/2-1,(2n-r)(r-1)/2-2 and cλr(G)=(2n-r)(r-1)/2-l of the class of graphs where 1≤l ≤n-1 and 2≤r≤n;exact values are given for the three extremal problems of component edge connectivity of the graphs:the values of the two Erdos-Gallai-type problems,and the value of the problem of the minimum size of the graph for a given parameter.Second,the reliability of hypercube networks is studied.Hypercube networks are the most classical underlying network model,and many of the new parameters of connectivity have been proposed starting from hypercubes.Result is given for 2extra 3-component connectivity of hypercubes;the concept of g-good r-component connectivity of graphs is proposed and the value of 2-good 3-component connectivity of hypercubes is studied;the notion of h-extra H-structure(substructure)connectivity of graphs is proposed,the results for the hypercubes when h=1 and the structure H is a path are studied;The concept of r-component block connectivity of a graph is introduced.A general result on the r-component block connectivity of hypercubes is studied.Subsequently,experimental analyses are carried out,and the results show that the conditional connectivity obtained in this chapter can be a more accurate measure of network reliability.Then,the reliability of folded hypercube networks is studied.Folded hypercube networks are an important variant of hypercube networks and one of the fundamental network models.Several parallel systems have used folded hypercube networks as the underlying topology,such as ATM switches,PM21 networks,and 3D-FOLHDOC networks.General results on the h-fault block connectivity of folded hypercube networks are given,and the results are analyzed experimentally,which shows that the h-faulty block connectivity of folded hypercube networks is always larger than the hextra connectivity.A larger h-faulty block connectivity means that an attacker must launch an attack on a larger block of connected nodes so that each remaining component is not too small,which in turn limits the size of the larger components.The larger the h-faulty block connectivity,the harder it is for an attacker to achieve this goal.Finally,the reliability of the data center network Dcell is investigated.Data center network Dcell,using only commercial switches can support millions of servers with high network capacity.As a result,such data center networks are one of the most frequently utilized networks in real life.The structure(substructure)connectivity of the data centre network Dcell based on the star structure Sm and the double-order star structure S2m are given.General results are given for the star structure Sm and for the double-order star structure S2m when m=3.In this paper,we use conditional connectivity and structure(substructure)connectivity to study the reliability of interconnection networks,and the results of this study will provide a theoretical basis for network engineers to design and select interconnection networks,and provide theoretical support for the design of reliability engineering algorithms to maintain the network.