Fault Tolerance Analysis Of Interconnection Network

With the rapid development of technologies such as big data,5G and artificial intelligence,the demand for big data processing and high-performance computing has also increased dramatically.At the same time,the fault-tolerant communication problem of multiprocessor systems based on internetworking has also attracted much attention.To this end,large-scale parallel and distributed multiprocessor systems are always committed to ensuring ensure high reliability and fault tolerance.This thesis is divided into five chapters.The first chapter introduces some basic concepts of graphs and the related definitions of connectivity,diagnosability and Hamiltonian laceability.In the second chapter,reliability and fault tolerance of divide-and-swap cube are considered.We mainly investigate(sub)structure connectivity.And we analytically compare(sub)structure connectivity between divide-and-swap cube and several wellknown variants of hypercube.Furthermore,we determine component connectivity and diagnosability of divide-and-swap cube.In the third chapter,we focus on cluster connectivity and super cluster connectivity of composite structure DQn,which is constructed based on disc-ring graph and hypercube.As by-products,we show that DQcube is super K1,r-(K1,r*-)connected(2≤r ≤3),and derive the 4-extra connectivity of DQcube.In the fourth chapter,we investigate Hamiltonian paths passing through prescribed linear forests of balanced hypercubes with faulty edges,and show that the balanced hypercube BHn is(2n-2)-edge fault-tolerant prescribed Hamiltonian laceable for n≥1,which improves existing results.In the last chapter,we summarize our results and look forward to the future research direction.