Super connectivity of Kronecker products of graphs

Let G₁ and G₂ be two connected graphs. The Kronecker product G₁×G₂ has vertex set V(G₁×G₂)=V(G₁)×V(G₂) and the edge set . In this paper, we show that if G is a bipartite graph with κ(G)=δ(G), then G×Kn(n?3) is super-κ.     

指令级的变量容错恢复

提出一种抵抗瞬时故障的自动编译容错恢复方法,用源码中的变量信息在指令级别进行冗余错误流裁剪,在LCC上加以实现,并获得良好的容错性能。实验结果表明,该方法仅增加0.043倍的时间损耗及0.69倍的空间损耗,在时空损耗上优于现有的其他方法。     

可靠的网格作业调度机制

针对网格环境的动态性特征,提出了一种可靠的网格作业调度机制(DGJS)。按照作业完成时间期限,DGJS将作业分为：高QoS级、低QoS级和无QoS级,不同QoS级作业有不同的调度优先权;基于资源可用性预测,DGJS采用基于可靠性代价的作业调度策略,将作业尽可能调度到可靠性高的资源节点;另外,DGJS对不同QoS级作业采用不同的容错策略,在保证故障容错的同时,节省网格资源。实验表明：在动态的网格环境下,较之传统的网格作业调度算法,DGJS提高了作业成功率,减少了作业完成时间。     

Redirection based recovery for MPLS network systems

To provide a reliable backbone network, fault tolerance should be considered in the network design. For a multiprotocol label switching (MPLS) based backbone network, the fault-tolerant issue focuses on how to protect the traffic of a label switched paths (LSP) against node and link failures. In IETF, two well-known recovery mechanisms (protection switching and rerouting) have been proposed. To further enhance the fault-tolerant performance of the two recovery mechanisms, the proposed approach utilizes the failure-free LSPs to transmit the traffic of the failed LSP (the affected traffic). To avoid affecting the original traffic of each failure-free LSP, the proposed approach applies the solution of the minimum cost flow to determine the amount of affected traffic to be transmitted by each failure-free LSP. For transmitting the affected traffic along a failure-free working LSP, IP tunneling technique is used. We also propose a permission token scheme to solve the packet disorder problem. Finally, simulation experiments are performed to show the effectiveness of the proposed approach.     

胖树中的分布式动态容错路由

面向云计算的超大规模互连网络增加了对网络容错的要求,容错已成为互连网络的重要问题.为了保证网络的高可用性和高性能,文中基于胖树网络拓扑提出了一种分布式的动态容错路由方法.该方法通过引入一套链路失效消息传播机制和一套基于链路失效信息的动态容错路由算法来实现胖树网络的分布式动态容错.相比已有方法,该方法不增加网络硬件和路由路径长度,并且具有高执行效率和高性能.实验结果表明,在m端口交换机构成的胖树中,该方法可以容忍任意m/2-1条失效链路并以高概率容忍更多条失效链路的组合,同时保持网络的高性能.     

Biswapped网络(BSN)的拓扑性质研究:点对称性和极大容错性

Biswapped网络(BSN)是一类两层结构的互连网络,它以任意图为模块且模块间采用一种完全两部图方式互连.BSN的互连形式与OTIS网络(即Swapped网络)类似但互连规则更一致,使得BSN展现出更好的性能.文中主要研究BSN的点传递性和容错性能.首先证明BSN能继承因子网络的点传递性质,为BSN上的分析和算法简单性找到理论依据.其次,通过直接构造网络中两点间最大数目的点不相交路径证明以任意连通图为因子网络的BSN是一致极大容错的.这些结果表明BSN既能继承因子网络的理想性能还展现某些好的新特性.最后,通过与OTIS网络、卡式积网络等层次类网络比较表明,BSN提供了一种构建可扩展性、模块化、容错性的大规模并行计算机系统的潜在有竞争力的体系结构形式.     

针对t-可诊断多处理器系统的遗传诊断算法

结合诊断模型与遗传算法,提出一种针对t-可诊断多处理器系统的遗传诊断算法。通过运用模型的诊断性质提高初始种群的质量,并定义判断结点状态的诊断方程,设计基于该方程的适应度函数。理论分析和模拟实验表明,算法具有较好的最优解搜索能力和较快的收敛速度。     

Improving the yield of NoC-based systems through fault diagnosis and adaptive routing

We propose an effective and low cost method to increase the yield and the lifetime of torus NoCs. The method consists in detecting and diagnosing NoC interconnect faults using BIST structures and activating alternative paths for the faulty links. Alternative paths use the inherent redundancy of the torus topology, thus leading to minimal performance, area, and power overhead. We assume an extended interconnect fault model comprising stuck-at and pairwise shorts within a single link or between any two links in the network. Experimental results for a 3×3 NoC show that the proposed approach can correctly diagnose 93% of all possible interconnect faults and can mitigate 42% of those faults (representing 94.4% of the solvable faults) with a worst case performance penalty of 8% and 1% of area overhead. We also demonstrate the scalability of the method by presenting its application to larger NoCs.     

Damage assessment and repair in attack resilient distributed database systems

Preventive measures sometimes fail to defect malicious attacks. With attacks on data-intensive applications becoming an ever more serious threat, intrusion tolerant database systems are a significant concern. The main objective of such systems is to detect attacks, and to assess and repair the damage in a timely manner. This paper focuses on efficient damage assessment and repair in distributed database systems. The complexity caused by data partition, distributed transaction processing, and failures makes intrusion recovery much more challenging than in centralized database systems. This paper identifies the key challenges and presents an efficient algorithm for distributed damage assessment and repair.     

Fault tolerant machine learning for nanoscale cognitive radio

We introduce a machine learning-based classifier that identifies free radio channels for cognitive radio. The architecture is designed for nanoscale implementation, under nanoscale implementation constraints; we do not describe all physical details but believe future physical implementation to be feasible. The system uses analog computation and consists of cyclostationary feature extraction and a radial basis function network for classification. We describe a model for nanoscale faults in the system, and simulate experimental performance and fault tolerance in recognizing WLAN signals, under different levels of noise and computational errors. The system performs well under expected non-ideal manufacturing and operating conditions.