On constructing the minimum orthogonal convex polygon for the fault-tolerant routing in 2-D faulty meshes

The rectangular faulty block model is the most commonly used fault model for designing fault-tolerant, and deadlock-free routing algorithms in mesh-connected multicomputers. The convexity of a rectangle facilitates simple, efficient ways to route messages around fault regions using relatively few or no virtual channels to avoid deadlock. However, such a faulty block may include many nonfaulty nodes which are disabled, i.e., they are not involved in the routing process. Therefore, it is important to define a fault region that is convex, and at the same time, to include a minimum number of nonfaulty nodes. In this paper, we propose an optimal solution that can quickly construct a set of minimum faulty polygons, called orthogonal convex polygons, from a given set of faulty blocks in a 2-D mesh (or 2-D torus). The formation of orthogonal convex polygons is implemented using either a centralized, or distributed solution. Both solutions are based on the formation of faulty components, each of which consists of adjacent faulty nodes only, followed by the addition of a minimum number of nonfaulty nodes to make each component a convex polygon. Extensive simulation has been done to determine the number of nonfaulty nodes included in the polygon, and the result obtained is compared with the best existing known result. Results show that the proposed approach can not only find a set of minimum faulty polygons, but also does so quickly in terms of the number of rounds in the distributed solution.     

Fault-Tolerant Mesh-Based NoC with Router-Level Redundancy

The aggressively scaled CMOS technology is increasingly threatening the dependability of network-on-chips (NoCs) architecture. In a mesh-based NoC, a faulty router or broken link may isolate a well functional processing element (PE). Also, a set of faulty routers may form isolated regions, which can degrade the design. In this paper, we propose a router-level redundancy (RLR) fault-tolerant scheme that differs from the traditional microarchitecture-level redundancy (MLR) approach to relieve the problem of isolated PE and isolated region. By simply adding one spare router within each router set in a mesh, RLR can be created and connection paths between adjacent routers can be diversified. To exploit this extra resource, two reconfiguration algorithms are demonstrated to detour observed faulty routers/links. The proposed RLR fault-tolerant scheme can tolerate at most one faulty router within a router set. After the reconfiguration, the original mesh topology is maintained. As a result, the proposed architecture does not need any support from the network layer routing algorithms. The scheme has been evaluated based on the three fault-tolerant metrics: reliability, mean time to failure (MTTF), and yield. The experimental results show that the performance RLR increases as the size of NoC grows; however, the relative connection cost decreases at the same time. This characteristic makes our architecture suitable for large-scale NoC designs.

     

Fault Tolerance of Switch Blocks and Switch Block Arrays in FPGA

A new application-independent approach for evaluating the fault tolerance of field-programmable gate-array (FPGA) interconnect structures is presented. Signal routing in the presence of faulty resources at switch block and FPGA levels is analyzed; this problem is directly related to the fault tolerance of FPGA interconnects for testing and reconfiguration at manufacturing and run-time applications. Two criteria are proposed and used as figure-of-merit for evaluating different FPGA interconnect architectures. The proposed approach is based on the number of available paths between pairs of end points and the probability to establish a one-to-one mapping between all input and output end points. A probabilistic approach is also presented to evaluate the fault-tolerant routing of the entire FPGA by connecting switch blocks in chains, as required for testing and to account for the input–output (I/O) pin restrictions of an FPGA chip. All possible interconnect faults for programmable switches and wiring channels are considered in the fault model. The proposed method is applicable to arbitrary switch block structures. Experimental results on commercial as well as academic designed FPGAs are presented and analyzed.     

基于内建自测技术的Mesh结构NoC无虚通道容错路由算法

 在Zhang's算法绕行思想的基础上,提出了一种2D-Mesh结构片上网络无虚通道容错路由算法,用于解决多故障节点情况下片上网络的无虚通道容错路由问题.算法利用内建自测试机制获取故障区域的位置信息,通过优化绕行策略来均衡故障区域周围链路的负载并减少部分数据的绕行距离.针对8×8的2D-Mesh网络的仿真表明,与Chen's算法相比,在故障区域大小为2×2,网络时延为70 cycles的情况下,随着故障区域位置的变化所提算法可提高1.2%到4.8%的网络注入率.且随着故障区域面积的扩大,所提算法在减少通信时延,提高网络吞吐量方面的作用更为明显.     

A cluster based WSN fault tolerant protocol

A Wireless Sensor Network(WSNs) fault-tolerant protocol is proposed in this paper.By setting up a robust cluster topology,the fault-tolerant algorithm can search any faulty node in the path and revise the path furthermore.Once the cluster head fails,it will be substituted by other alternative cluster heads with the lowest cost,and the path will be re-established.Experiments show that this algorithm can not only locate the faulty nodes in the path accurately,shield the influence of the error node in clusters...     

An ellipse-guided routing algorithm in wireless sensor networks

In wireless sensor networks, sensor nodes are deployed to collect data, perform calculations, and forward information to either other nodes or sink nodes. Recently, geographic routing has become extremely popular because it only requires the locations of sensor nodes and is very efficient. However, the local minimum phenomenon, which hinders greedy forwarding, is a major problem in geographic routing. This phenomenon is attributed to an area called a hole that lacks active sensors, which either prevents the packet from being forwarded to a destination node or produces a long detour path. In order to solve the hole problem, mechanisms to detect holes and determine landmark nodes have been proposed. Based on the proposed mechanisms, landmark-based routing was developed in which the source node first sends a packet to the landmark node, and the landmark node then sends the packet to the destination. However, this approach often creates a constant node sequence, causing nodes that perform routing tasks to quickly run out of energy, thus producing larger holes. In this paper, a new approach is proposed in which two virtual ellipses are created with the source, landmark, and destination nodes. Then guide the forwarding along the virtual ellipses. Furthermore, a recursive algorithm is designed to ensure a shortcut even if there are multiple holes or a hole has multiple landmarks. Thus, the proposed approach improves both geographic routing and energy efficiency routing. Simulation experiments show that the proposed approach increases the battery life of sensor nodes, lowers the end-to-end delay, and generates a short path.     

A scalable built-in self-recovery (BISR) VLSI architecture and design methodology for 2D-mesh based on-chip networks

On-Chip Networks (OCNs) have been proposed to solve the complex on-chip communication problems. In Very Deep-Submicron era, OCN will also be affected by faults in chip due to technologies shrinking. Many researches focused on fault detection and diagnosis in OCN systems. However, these approaches didn’t consider faulty OCN system recovery. This paper proposes a scalable built-in self-recovery (BISR) design methodology and corresponding Surrounding Test Ring (STR) architecture for 2D-mesh based OCNs to extend the work of diagnosis. The BISR design methodology consists of STR architecture generation, faulty system recovery, and system correctness maintenance. For an n×n mesh, STR architecture contains one controller and 4n test modules which are formed as a ring-like connection surrounding the OCN. Moreover, these test modules generate test patterns for fault diagnosis during warm-up time. According to these diagnosis results, the faulty system is recovered. Finally, this paper proposes a fault-tolerant routing algorithm, Through-Path Fault-Tolerant (TP-FT) routing, to maintain the correctness of this faulty system. In our experiments, the proposed approach can reduce 68.33∼79.31% unreachable packets and 4.86∼23.6% latency in comparison with traditional approach with 8.48∼13.3% area overhead.     

Fault-tolerant routing in adversarial mobile ad hoc networks: an efficient route estimation scheme for non-stationary environments

Designing routing schemes that would successfully operate in the presence of adversarial environments in Mobile Ad Hoc Networks (MANETs) is a challenging issue. In this paper, we discuss fault-tolerant routing schemes operating in a network with malfunctioning nodes. Most existing MANET protocols were postulated considering scenarios where all the mobile nodes in the ad hoc network function properly, and in an idealistic manner. However, adversarial environments are common in MANET environments, and misbehaving nodes certainly degrade the performance of these routing protocols. The need for fault tolerant routing protocols was identified to address routing in adversarial environments in the presence of faulty nodes by exploring redundancy-based strategies in networks. It turns out that since the nodes are mobile, the random variables encountered are non-stationary, implying that estimation methods for stationary variables are inadequate. Consequently, in this paper, we present a new fault-tolerant routing scheme that invokes a stochastic learning-based weak estimation procedure to enhance a route estimation phase, which, in turn, is then incorporated in a route selection phase. We are not aware of any reported method that utilizes non-traditional estimates to achieve the ranking of the possible paths. The scheme, which has been rigorously tested by simulation, has been shown to be superior to the existing algorithms.     

Fault tolerance techniques for high capacity RAM

As the complexity and size of the embedded memories keep increasing, improving the yield of embedded memories is the key step toward improving the overall chip yield of a SOC design. The most well known way to improve the memory yield is by using redundant elements to replace the faulty cells. However, the repair efficiency mainly depends on the type, and the amount of redundancy; and on the redundancy analysis algorithms. Therefore, new types of redundancy based on divided bit-line (DBL), and divided word-line (DWL) techniques are proposed in this work. A memory column (row), including the redundant column (row), is partitioned into column blocks (row blocks), respectively. A row/column block is used as the basic replacement element instead of a row/column for the traditional approaches. Based on the new types of redundancy, three types of fault-tolerant memory (FTM) systems are also proposed. If a redundant row/column block is used as the basic replacement element, then the row block-based FTM (RBFTM)/column block-based (CBFTM) system is used. If both the DWL, and DBL techniques are implemented onto a memory chip, then the hybrid FTM (HFTM) system is achieved. The storage and remapping of faulty addresses can be implemented with a CAM (content addressable memory) block. To achieving better repair efficiency, a novel hybrid block-repair (HBR) algorithm is also proposed. This algorithm is suitable for hardware implementation with negligible overhead. For the HFTM system, the hardware overheads are less than 0.65%, and 0.7% for 64-Kbit SRAM, and 8-Mbit DRAM, respectively. Moreover, the repair rate can be improved significantly. Experimental results show that our approaches can improve the memory fabrication yield significantly. The characteristics of low power and fast access time of DBL and DWL techniques are also preserved.     

A general framework for developing adaptive fault-tolerant routingalgorithms

It is shown that Cartesian product (CP) graph-based network methods provide a useful framework for the design of reliable parallel computer systems. Given component networks with prespecified connectivity, more complex networks with known connectivity and terminal reliability can be developed. CP networks provide systematic techniques for developing reliable fault-tolerant routing schemes, even for very complex topological structures. The authors establish the theoretical foundations that relate the connectivity of a CP network, the connectivity of the component networks, and the number of faulty components: present an adaptive generic algorithm that can perform successful point-to-point routing in the presence of faults: synthesize, using the theoretical results, this adaptive fault-tolerant algorithm from algorithms written for the component networks: prove the correctness of the algorithm: and show that the algorithm ensures following an optimal path, in the presence of many faults, with high probability     

Online BIST and BIST-based diagnosis of FPGA logic blocks

We present the first online built-in self-test (BIST) and BIST-based diagnosis of programmable logic resources in field-programmable gate arrays (FPGAs). These techniques were implemented and used in a roving self-testing areas (STARs) approach to testing and reconfiguration of FPGAs for fault-tolerant applications. The BIST approach provides complete testing of the programmable logic blocks (PLBs) in the FPGA during normal system operation. The BIST-based diagnosis can identify any group of faulty PLBs, then applies additional diagnostic configurations to identify the faulty look-up table or flip-flop within a faulty PLB. The ability to locate defective modules inside a PLB enables a new form of fault-tolerance that reuses partially defective PLBs in their fault-free modes of operation.     

A novel Topology Aggregation approach for shared protection in multi-domain networks

Routing for shared protection in multi-domain networks is more difficult than that in single-domain networks because of the scalability requirements. We propose a novel approach for shared protection routing in multi-domain networks where the key feature is a special Topology Aggregation. In this Topology Aggregation, only some potential intra-domain paths (intra-paths for short) are selected for carrying working and backup traffic between domain border nodes. The abstraction of each intra-path to a virtual edge makes the original multi-domain network to become an aggregated network. On the aggregated network, a single-domain routing algorithm for shared protection can be applied for obtaining the complete routing solutions. The experiments show that the proposed approach is scalable. Moreover it is close to the optimal solution in single-domain networks and outperforms the previously proposed scalable solutions in multi-domain networks.     

Routing Using Genetic Algorithm in a Wireless Sensor Network

In this paper we probe the routing algorithm that maximizes the quality of the network. In this regard, we present various scenarios for comparisons among different routing algorithms in a wireless sensor network. Using simulations conducted in NS-2, we compare the performance of genetic algorithm (GA) to the Dijkstra algorithm, Ad hoc On-Demand Distance Vector (AODV), GA-based AODV Routing (GA-AODV), grade diffusion (GD) algorithm, directed diffusion algorithm and GA combined with the GD algorithm. We assume the presence of faulty nodes and work on finding out the performance that enhances the lifespan of the sensor network. In this regard, we have simulated routing algorithms while considering faulty nodes up to 50% of the functioning nodes. Nodes are considered to be dynamic and we assumed different mobility speeds of the nodes. Our results demonstrate that GA can be used in different network configurations as it shows a better performance in the wireless sensor network.

     

An ant colony optimization based routing algorithm for extending network lifetime in wireless sensor networks

Reducing the energy consumption of network nodes is one of the most important problems for routing in wireless sensor networks because of the battery limitation in each sensor. This paper presents a new ant colony optimization based routing algorithm that uses special parameters in its competency function for reducing energy consumption of network nodes. In this new proposed algorithm called life time aware routing algorithm for wireless sensor networks (LTAWSN), a new pheromone update operator was designed to integrate energy consumption and hops into routing choice. Finally, with the results of the multiple simulations we were able to show that LTAWSN, in comparison with the previous ant colony based routing algorithm, energy aware ant colony routing algorithms for the routing of wireless sensor networks, ant colony optimization-based location-aware routing algorithm for wireless sensor networks and traditional ant colony algorithm, increase the efficiency of the system, obtains more balanced transmission among the nodes and reduce the energy consumption of the routing and extends the network lifetime.     

Mobile-agent-based collaborative signal and information processing in sensor networks

In this paper, we develop an energy-efficient, fault-tolerant approach for collaborative signal and information processing (CSIP) among multiple sensor nodes using a mobile-agent-based computing model. In this model, instead of each sensor node sending local information to a processing center for integration, as is typical in client/server-based computing, the integration code is moved to the sensor nodes through mobile agents. The energy efficiency objective and the fault tolerance objective always conflict with each other and present unique challenge to the design of CSIP algorithms. In general, energy-efficient approaches try to limit the redundancy in the algorithm so that minimum amount of energy is required for fulfilling a certain task. On the other hand, redundancy is needed for providing fault tolerance since sensors might be faulty, malfunctioning, or even malicious. A balance has to be struck between these two objectives. We discuss the potential of mobile-agent-based collaborative processing in providing progressive accuracy while maintaining certain degree of fault tolerance. We evaluate its performance compared to the client/server-based collaboration from perspectives of energy consumption and execution time through both simulation and analytical study. Finally, we take collaborative target classification as an application example to show the effectiveness of the proposed approach.     

超立方体网络中基于局部安全信息的广播容错路由研究

针对具有错误节点和故障链路的超立方体网络,改进了一种算法实现可靠的容错广播路由。在没有安全结点的不安全的超立方体网络中,将网络分成一系列最大安全子立方体,根据提出的故障链路处理方法和选择广播路由的准则,改进了基于局部安全信息的广播路由算法。证明了根据文中算法,这些最大安全子立方体在满足文中要求的情况下,仍有可能实现可靠的广播路由,有效地提高了信息路由的可靠性。提供了实例介绍文中算法的原理和优点。     

基于网络监控器的专用片上网络动态容错路由

针对专用片上网络（Network on Chip,NoC）全局通信事务管理和可靠性设计问题,提出片上网络监控器的概念,用于获取全局网络实时状态信息及执行路径分配算法,基于此提出一种动态路由机制DyRS-NM.该机制能检测和定位NoC中的拥塞和故障链路,并能区分瞬时和永久性链路故障,采用重传方式避免瞬时故障,通过重新路由计算绕开拥塞和永久性故障.设计实现了RTL级网络监控器和与之通信的容错路由器模块,并将MPEG4解码器应用映射至基于网络监控器的4×4Mesh结构NoC体系结构中,验证了系统性能以及面积功耗开销.相比静态XY路由和容错动态路由FADR,DyRS-NM机制在可接受的开销代价下获得了更优的性能.     

Deadlock Avoidance in Store-and-Forward Networks--I: Store-and-Forward Deadlock

Store-and-forward deadlock in store-and-forward networks may be avoided by forwarding messages from buffer to buffer in accordance with a loop-free directed buffer graph which accommodates all the desired message routes. Schemes for designing such buffer graphs are presented, together with methods for using them to forward the messages in an efficient and deadlock-free manner. These methods can be implemented by a set of counters at each node. Such an implementation increases the efficiency of buffer use, and simplifies jumping between normal lowoverhead operation when deadlock is far and more careful operation when deadlock is near. The proposed deadlock avoidance mechanism works for any network topology and any finite routing algorithm.     

Fault-tolerant multicasting in MINs for ATM switches

This article proposes a fault-tolerant multicast routing algorithm in multistage interconnection networks (MINs) for ATM switch architectures. It employs both region and cube encoding schemes as the header encoding scheme. A multicast packet can be routed to its destinations in only two phases through the MIN having a single faulty element     

Multilayered Distributed Routing for Power Efficient MANET Performance

In this paper a new power efficient routing algorithm for MANETs with self-organizing and self-routing features is described and its performance analyzed in different simulation scenarios. The algorithm has the logic of a non-cooperative routing algorithm based on the evaluation of a weight parameter, the latter being a function of properties of the MANET nodes related to the nominal available power and the transmission range. A self-estimation of this weight parameter for each node is introduced in the routing process based on the status and functional history of the node. The routing is based on network layering, formation of service areas in each layer and choice of nodes from these areas to have the functionality of default gateways. The proposed algorithm, named service zone gateway prediction (SZGP), is a hybrid type of routing mechanism, incorporating pre-computed multipath hop-by-hop distributed routing, with a periodically updated hierarchical multilayered structure. The results from the simulation experiments show that the performance of the proposed SZGP algorithm in relation to the basic performance parameters such as packet delivery ratio, delay and throughput are similar to those of the well-known AODV algorithm, but in relation to power efficiency the proposed algorithm outperforms AODV significantly. This is due to the fact that such an approach reduces the overall number of broadcasts in the network and ensures a reliable and energy efficient connection by balancing the load among the nodes.