一种新型的基于BC图的网络安全算法

Novel Network Security Algorithm of BC Graphs

BC图是一类较新的互连拓扑结构,它包含了超立方体结构及其变体结构。t/k-诊断策略是对系统级故障诊断的经典诊断策略的改进,它以牺牲很少部分的结点不能正确诊断为代价,显著提高了系统的诊断度。本文提出了一个O(Nlog2N)的t/k-诊断算法,该算法在系统中存在较多故障处理器的情况下,以至多误诊断3个结点为代价,正确诊断出系统中的全部故障结点。

The BC graphs are a class of newly introduced interconnection topologies,which include hypercube and its variants.As an improvement method of the classical diagnosis strategy of system-level diagnosis,the t/k-diagnosis strategy can significantly improve the diagnosability of multicomputer systems at the cost of few nodes being incorrectly identified as faulty.We present a t/k-diagnosis algorithm,which can operate in O（Nlog2N） time.Provided that there are much more faulty processors in the system,the diagnosis algorithm can diagnose all the faulty ones at the cost of at most three fault-free units being misdiagnosed.