Fault Diagnosis Of Large-scale Interconnection Networks

In the increasingly unstable global cybersecurity landscape,global cyber attacks continue to occur.Data leaks,extortion software and security vulnerabilities are escalating and developing,and the crisis is unprecedentedly severe.Without network security,there is no national security.The number of network devices and links has experienced explosive growth recently.For any multiprocessor system based on networking,the failure of processors and links is inevitable,as the number of processors and physical links increases dramatically.The rapid diagnosis,location,detection,and isolation of faults not only improve the robustness and reliability of the system,but also provide a strong guarantee for building a safe and green network environment.This thesis focuses on fault diagnosis of large-scale regular interconnection network.The theoretical basis and methods needed include fault diagnosis theory based on integrated circuit,graph theory modeling,combinatorial network theory and so on.The main contributions of this thesis are summarized as follows.(1)Fault Diagnosis of Bicube-based Interconnection NetworkStarting from the hypercube with practical application background and good research foundation,this thesis first determines the g-good-neighbor conditional diagnosability and g-extra conditional diagnosability of a hypercube-based compound topology,bicube network,under PMC model and MM*model,respectively.The performance analysis results show that the g-good-neighbor conditional diagnosability performs better self-diagnosis and fault-tolerant capability compared with classic diagnosability and g-extra conditional diagnosability.(2)Component Fault Diagnosis of Regular Interconnection NetworksComponent diagnosability takes into account the number of component in the remaining network after being attacked.Existing works focus only on the component diagnosability of some specific networks.Therefore,this thesis suggests a general characterization to establish the relationship between component connectivity and component diagnosability of one class of interconnection networks under the PMC model,and obtain the empirical analysis of some classic networks.If the residual network possesses a large component,then in many cases it can still be used as a functional subsystem without causing severe performance degradation.Furthermore,we also investigate the topological characteristics of small components in the remaining network when a given number of vertices are attacked for the burnt pancake network.(3)Hybrid Fault Diagnosis of Triangle-free Interconnection NetworksThis thesis proposes a general method to characterize the h-restricted vertex diagnosability and r-restricted edge diagnosability of the triangle-free networks under the hybrid PMC model,including hypercube-based compound network,star network,burnt pancake network,bubble-sort star network and so on.The HPMC diagnostic model considers comprehensively the failure of processor and link within a network,and is a more effective diagnostic model in the actual network environment.(4)Fault Diagnosis of New Interconnection Network Based on Group Theory ConstructionThis thesis designs a class of interconnection network for Cayley graph based on symmetry group,and explores the corresponding algebraic and combinatorial properties,classic connectivity and extra connectivity,respectively.Furthermore,we take connectivity and extra connectivity as the bridges to determine its classic diagnosability and {1,2}-extra conditional diagnosability.The experimental analysis shows that the network topology we designed presents better reliability and invulnerability compared with the state-of-the-art interconnection networks.Different from the recursive structure of existing networks,the interconnection network we proposed divides subgraphs by fixing continuous two-dimensional coordinates,which concurrently provides a significant basis for exploring the diagnosability and diagnostic algorithms for the more complex interconnection networks.