The Fault Tolerance Of Hypercube-Like Networks With Respect To Maximally Local Connectivity

When the network of a multiprocessor system is modeled as a graph,the reliability of the network can be measured by the connectivity of the graph.The local connectivity of a graph is a more accurate indicator than the connectivity.It is well known that the larger the local connectivity,the more reliable the corresponding network.Maximally local connected graphs are a class of graphs with maximally local connectivity.In the process of multiprocessor system operation,failures are inevitable.Therefore,the fault tolerance of the system must be considered.The fault tolerance is a parameter to measure systems' fault-tolerant ability.The fault tolerance of a graph with respect to maximally local connectivity was proposed by combing the concepts of fault tolerance and maximally local connectivity.In actual applications,the distribution of faults in a system will follow some rules.Based on this,we generalize the fault tolerance with respect to maximally local connectivity and propose the g-gooa neighbor fault tolerance with respect to maximal local connectivity.In some applications,directed networks have more advantages than undirected networks,so it is meaningful to study the properties of directed networks.In this paper,we also extend the fault tolerance with respect to maximally local connectivity to directed graphs,and propose the concept of the fault tolerance with respect to maximally local connectivity of directed graphs.The hypercube becomes one of the most popular networks because of its good topolog-ical properties and simple implementation.In order to improve and generalize hypercubes,some hypercube-like networks have been proposed,such as k-ary n-cubes and unidirec-tional k-ary n-cubes.In this paper,we study the fault tolerance with respect to maximally local connectivity of hypercubes,k-ary n-cubes and unidirectional k-ary n-cubes in four chapters.The first chapter mainly introduces some terminology and notation in graph theory,as well as the research background and the main concepts involved in this thesis.Chapter 2 first studies some properties of the k-ary n-cube networks,and proves that the k-ary n-cube is maximally local connected graph,and then determines that the fault tolerance with respect to maximally local connectivity of the k-ary n-cube is ?(Qnk)=2n—2.Chapter 3 first studies the topological properties of unidirectional k-ary n-cubes Qnk,and proves that when up to 2n--2 vertices are removed from Qnk,there is still a large strongly connected component in the resulting graph.Based on this result,we prove that the fault tolerance of the u1idirectional k-ary n-cube Qnk with respect to maximally local connectivity is ?(Qnk)=n-1.In Chapter 4,we first show the upper and lower bounds on the g-good neighbor fault tolerance ?g(Qn)with respect to maximally local connectivity of the hypercube Qn as follows:?g(Qn)?(g+1)n-(g+1)(g+2)/2+1-n for n?4 and 1?g?n-2;?g(Qn)?(2g-g)(n-g)-1 for n?3 and 1?g?[n/2].Then we determine that the 1,2,3-good neighbor fault tolerance with respect to maximally local connectivity of the hypercube Qn are ?1(Qn)=n-2,?2(Qn)=2n-5 and ?3(Qn)=5n-16.