Integration of the IP/MPLS network and the WDM optical mesh network is a promising approach to realizing an efficient backbone network. Because of the great volumes of traffic carried, the social cost incurred by a failure will be extremely high, so survivability is very important in the backbone network. In survivable IP/MPLS over WDM backbone networks, cooperation of the optical level fault recovery and the IP/MPLS level fault recovery is essential. This paper analyzes cost characteristics of the optical level fault recovery and the IP/MPLS level fault recovery. A mathematical programming method is proposed to minimize the initial network cost when the IP/MPLS level fault recovery is utilized in the survivable IP/MPLS over WDM networks. Using this method, the initial network cost needed for the IP/MPLS level fault recovery is compared with that for the optical level fault recovery. The initial network cost for the LSP (Label Switched Path) protection scheme is smaller than that for the shared light-path protection scheme and larger than that for the pre-plan type light-path restoration scheme. The LSP protection scheme is suitable for the best-effort type traffic while the shared light-path protection scheme may be suitable for the bandwidth guaranteed type traffic.

We define a d-matched digraph and propose a recursive procedure for designing an optimal d-matched digraph without bidirectional edges. The digraph represents an optimal highly structured system which is a special class of self-diagnosable systems and identifies all of the faulty units independently and locally in O(|E|) time complexity. The procedure is straightforward and gives a system flexible in network connections. Hence the procedure is applicable to real systems such as the Internet or cooperative robotic systems which change their topology dynamically.

This paper considers a reconfiguration problem on a processor array model based on single-and-half-track switches, which is proposed for a fault tolerance technique at the fabrication time. The focus of this paper is to achieve the optimal reconfigurability, which means that whenever there exists a solution for successful reconfiguration, the designed method can find the solution. The paper consists of two parts. In the first part, we show two essential constraints that have been assumed in most of the previous studies, and make four reconfiguration classes that differ in the assumed essential constraints. Then, we present some inclusion relations among the four reconfiguration classes. As a result, it becomes clear that the most restrictive class including most of the previous methods never achieves the truly optimal reconfigurability. In the second part, we present a reconfiguration method based on sequential routing (RMSR). Although the worst-case time complexity of the RMSR is exponential in the number of processing elements, the reconfigurability of the RMSR is optimal within the most restrictive reconfiguration class. The effectiveness of the RMSR is shown by a computer simulation.

The network duplicating can achieve significant improvements of the Local Area Network (LAN)'s performance, availability, and security. For LAN duplicating, a Dual-Path Ethernet Module (DPEM) is developed. Since a DPEM is simply located at the front end of any network device as a transparent add-on type independent hardware machine, it does not require sophisticated server reconfiguration. We examine the desirable properties and the characteristics on the Dual-LAN structure. Our evaluation results show that the developed scheme is more efficient than the conventional Single-LAN structures in various aspects.

Model checking is a technique that can make a verification for finite state systems absolutely automatic. We propose a method for automatic verification of fault-tolerant concurrent systems using this technique. Unlike other related work, which is tailored to specific systems, we are aimed at providing an approach that can be used to verify various kinds of systems against fault tolerance. The main obstacle in model checking is state explosion. To avoid the problem, we design this method so that it can use a symbolic model checking tool called SMV (Symbolic Model Verifier). Symbolic model checking can overcome the problem by expressing the state space and the transition relation by Boolean functions. Assuming that a system to be verified is modeled as a guarded command program, we design a modeling language and propose a translation method from the modeling language to the input language of SMV. We show the results of applying the proposed method to various examples to demonstrate the feasibility of the method.

In this paper, a useful technique is proposed for realizing high speed IDDQ tests. By using the technique, load capacitors of the CMOS logic gates can be charged quickly, whose output logic values change from L to H by applying a test input vector to a circuit under test. The technique is applied to built-in IDDQ sensor design and external IDDQ sensor design. It is shown experimentally that high speed IDDQ tests can be realized by using the technique.

In recent years, the domino logic has received much attention as a design technique of high-speed circuits. However, in the case of standard domino logic, only non-inverting functions are allowed. Then, the clock-delayed (CD) domino logic that provides any logic function is proposed in order to overcome such domino's drawback. In addition, domino circuits are more sensitive to circuit noise compared with static CMOS circuits. In particular, crosstalk causes critical problems. Therefore, we focus our attention on crosstalk faults in CD domino circuits. However, in CD domino circuits, there are faults that don't propagate faulty values to any primary output even though crosstalk pulses are generated. Then, we remove such faults from the target fault list by considering structures of CD domino circuits, and perform a fault simulation for the reduced target fault list using two kinds of fault simulation method together. We realize CD domino circuits in VHDL and perform the proposed fault simulation for the combinational part of some benchmark circuits of ISCAS'89 on a VHDL simulator. Fault coverage for random vectors was obtained for s27 to s1494 under the limitation of simulation time.

An n-detection testing for stuck-at faults can be used not only for delay fault testing but also for detection of unmodeled faults. We have developed a hybrid BIST circuit; that is, a method consisting of a shift register with partial rotation and a procedure that selects test vectors from ATPG ones. This testing method can perform at-speed testing with high stuck-at fault coverage. During the at-speed testing, a subset of the ATPG vectors is input by using a low-speed tester. Computer simulations on ISCAS'85, ISCAS'89, and ITC'99 circuits are conducted for n = 1, 2, 3, 5, 10, and 15. The simulation results show that the amount of test vectors can be reduced to ranging from 52.3% to 0.9% in comparison with that of the ATPG vectors. As a result, the proposed method can reduce the cost of at-speed testing.

A procedure to remove redundancies in sequential circuits is proposed using strongly unreachable states, which are the states with no incoming transitions. Test generation is used to find undetectable faults related to two or more strongly unreachable states. Experimental results show the new procedure can find more redundancies of sequential circuits.

This paper presents a practical fault model for delay testing, called a multiple-threshold gate-delay fault model, to obtain high quality tests that guarantee the detection of delay faults for various extra-delays. Fault efficiencies for multiple thresholds of the extra-delay are introduced as a coverage metric that describes the quality of tests. Our approach guarantees that each gate-delay fault is tested on the path that is almost the longest one passing through the faulty line by using two-pattern tests with pattern-independent timing. We present the procedures of the path selection, fault simulation, and the test generation, where the path-status graph technique is used as not to rely on the enumeration of paths. Experimental results for benchmark circuits demonstrate that the proposed metric gives useful information that transition fault efficiency cannot, and that the proposed test generation can achieve high fault efficiencies for multiple-threshold gate-delay faults.

The EB tester line delay fault localization algorithm for combinational circuits is proposed where line delay fault probabilities are utilized to narrow fault candidates down to one efficiently. Probabilities for two main causes of line delay faults, defects of contact/vias along interconnections and crosstalk, are estimated through layout analysis. The algorithm was applied to 8 kinds of ISCAS'85 benchmark circuits to evaluate its performance where the guided probe (GP) diagnosis was used as the reference method. The proposed method can cut the number of probed lines to about 30% in average compared with those for the GP method. The total fault localization time was 31% of the time for the GP method and was 6% less than that of our previous method where the fault list generated in concurrent fault simulation is utilized.

In this paper we propose two diagnosis methods for crosstalk-induced pulse faults in sequential circuits using crosstalk fault simulation. These methods compare observed responses and simulated values at primary outputs to identify a set of suspected faults that are consistent with the observed responses. The first method is a restart-based method which determines the suspected fault list by using the knowledge about the first and last failures of the test sequence. The advantage of the restart-based method over a method using full simulation is its reduction of the number of simulated faults in a process of diagnosing faults. The second method is a resumption-based method which uses stored state information. The advantage of the resumption-based method over the restart-based method is its reduction of the CPU time for diagnosing the faults. The effectiveness of the proposed methods is evaluated by experiments conducted on ISCAS '89 benchmark circuits. From the experimental results we show that the number of suspected faults obtained by our methods is sufficiently small, and the resumption-based method is substantially faster than the restart-based method.

For checkpointing to be practical, it has to introduce low overhead for the targeted application. As a means of reducing the overhead of checkpointing, this paper proposes a probabilistic checkpointing method, which uses block encoding to detect the modified memory area between two consecutive checkpoints. Since the proposed technique uses block encoding to detect the modified area, the possibility of aliasing exists in encoded words. However, this paper shows that the aliasing probability is near zero when an 8-byte encoded word is used. The performance of the proposed technique is analyzed and measured by using experiments. An analytic model which predicts the checkpointing overhead is first constructed. By using this model, the block size that produces the best performance for a given target program is estimated. In most cases, medium block sizes, i.e., 128 or 256 bytes, show the best performance. The proposed technique has also been implemented on Unix based systems, and its performance has been measured in real environments. According to the experimental results, the proposed technique reduces the overhead by 11.7% in the best case and increases the overhead by 0.5% in the worst case in comparison with page-based incremental checkpointing.

An n-dimensional crossed cube, CQn, is a variation of the hypercube. In this paper, we prove that CQn is (n-2)-Hamiltonian and (n-3)-Hamiltonian connected. That is, a ring of length 2n-fv can be embedded in a faulty CQn with fv faulty nodes and fe faulty edges, where fv+fen-2 and n3. In other words, we show that the faulty CQn is still Hamiltonian with n-2 faults. In addition, we also prove that there exists a Hamiltonian path between any pair of vertices in a faulty CQn with n-3 faults. The above results are optimum in the sense that the fault-tolerant Hamiltonicity (fault-tolerant Hamiltonian connectivity respectively) of CQn is at most n-2 (n-3 respectively). A recent result has shown that a ring of length 2n-2fv can be embedded in a faulty hypercube, if fv+fen-1 and n4, with a few additional constraints. Our results, in comparison to the hypercube, show that longer rings can be embedded in CQn without additional constraints.

Most conventional studies on self-stabilization have been indifferent to the vulnerability under convergence. This paper investigates how mutual exclusion property can be achieved in self-stabilizing rings even for illegitimate configurations. We present a new method which uses a state with a large state space to detect faults. If some faults are detected, every process is reset and not given a privilege. Even if the reset values are different between processes, our protocol mimics the behavior of Dijkstra's unidirectional K-state protocol. Then we have a fast and safe mutual exclusion protocol. Simulation study also examines its performance.

With increasing Internet traffic congestion, the provision of reliable transmission and packet loss recovery continues to be of substantial importance. In this paper, we analyze a new recovery method using punctured convolutional codes, demonstrating the simplicity and efficiency of the proposed method for the recovery of lost packets. The analysis provides a method for determining the recoverability and the post-reconstruction receiving rate for a given convolutional code. The exact expressions for calculating the recovery rate are derived for a number of convolutional codes and the (2, 1, m) punctured convolutional code. Where packet loss probabilities are in the range typically found in Internet transmissions, the convolutional code-based method delivers superior performance over the traditional parity method with the same redundancy.

We consider diagnosability of butterfly networks under the comparison approach proposed by Maeng and Malek. Sengupta and Dahbura discussed characterization of diagnosable systems under the comparison approach, and designed a polynomial time algorithm to identify the faulty processors. However, for a general system, it is not algorithmically easy to determine its diagnosability. This paper proposes two comparison schemes for generating syndromes on butterfly networks, and determine the diagnosability of the network.

In this paper, we propose and analytically evaluate the use of punctured convolutional codes for recovering packets lost in multicast transmission. An independent erasure channel is assumed for packets transmission over a star topology. The analysis provides a method for determining the recoverability and the post-reconstruction receiving rate for a given convolutional code. We theoretically evaluate the effectiveness of the proposed approach taking into account two different parameters: the number of transmissions per packet and the number of packets needed to be sent to guarantee the reception of data. Finally, we compare the proposed approach with the scheme when parity packets are generated based on Reed-Solomon codes.

In interconnection networks, deadlock recovery has been studied in routing strategy. The routing strategy for the deadlock recovery is intended to optimize the routing performance when deadlocks do not occur. On the other hand, it is important to improve the routing performance by handling deadlocks if they occur. In this paper, a routing strategy for suspensive deadlock recovery called an escape-restoration routing is proposed and its performance is evaluated. In the principle of the proposed techniques, a small amount of exclusive buffer (escape-buffer) at each router is prepared for handling one of deadlocked packets. The transmission of the packet is suspended by temporarily escaping it to the escape-buffer. After the other deadlocked packets were sent, the suspended transmission resumes by restoring the escaped packet. Evaluation results show that the proposed techniques can improve the routing performance more than that of the previous recovery-based techniques in handling deadlocks.

In this paper, we study system-level diagnosis under the comparison approach proposed by Maeng and Malek. Sengupta and Dahbura designed an O(n5) time diagnosis algorithm for identifying all faulty nodes in general graphs (n is the number of nodes in a system). We consider diagnosis on a butterfly network BF(k,r) and propose O(k2 n) time diagnosis algorithms for locating all faulty nodes in BF(k,r).