An efficient ternary content addressable memory (TCAM) encoding scheme using a binary reflected Gray code (BRGC) and the concept of elementary intervals is presented for efficiently storing arbitrary ranges in TCAM. The proposed layered BRGC range encoding scheme (L-BRGC) groups ranges into BRGC range sets in which each range can be encoded into a single ternary vector. The results of experiments performed on real-life and synthesized rule tables show that L-BRGC consumes less TCAM than all the existing range encoding schemes for all rule tables, except that the direct conversion scheme (EIGC) using elementary intervals and BRGC codes performs best for a small real-life ACL rule table.

Packet classification problem has received much attention and continued to be an important topic in recent years. In packet classification problem, each incoming packet should be classified into flows according to a set of pre-defined rules. Grid-of-tries (GoT) is one of the traditional algorithmic schemes for solving 2-dimensional packet classification problem. The advantage of GoT is that it uses the switch pointers to avoid backtracking operation during the search process. However, the primary data structure of GoT is base on binary tries. The traversal of binary tries decreases the performance of GoT due to the heights of binary tries are usually high. In this paper, we propose a scheme called GST (Grid of Segment Trees). GST modifies the original GoT by replacing the binary tries with segment trees. The heights of segment trees are much shorter than those of binary tries. As a result, the proposed GST can inherit the advantages of GoT and segment trees to achieve better performance. Experiments conducted on three different kinds of rule tables show that our proposed scheme performs better than traditional schemes, such as hierarchical tries and grid-of-tries.

A dynamic multiway segment tree (DMST) is proposed for IP lookups in this paper. DMST is designed for dynamic routing tables that can dynamically insert and delete prefixes. DMST is implemented as a B-tree that has all distinct end points of ranges as its keys. The complexities of search, insertion, deletion, and memory requirement are the same as the existing multiway range tree (MRT) and prefix in B-tree (PIBT) for prefixes. In addition, a pipelined DMST search engine is proposed to further speed up the search operations. The proposed pipelined DMST search engine uses off-chip SRAMs instead of on-chip SRAMs because the capacity of the latter is too small to hold large routing tables and the cost of the latter is too expensive. By utilizing current FPGA and off-chip SRAM technologies, our proposed five-stage pipelined search engine can achieve the worst case throughputs of 33.3 and 41.7 million packets per second (Mpps) with 144-bit and 288-bit wide SRAM blocks, respectively. Furthermore, a straightforward extension of the pipelined search engine with multiple independent off-chip SRAMs can achieve the throughput of 200 Mpps which is equivalent to 102 Gbps for minimal Ethernet packets of size 64 bytes.

This paper deals with the traditional IP address lookup problem with fast updates. We propose a B-tree data structure, called MMSPT (multiway most specific prefix tree), which is constructed by using the most specific prefixes in routing tables. MMSPT arranges the most specific prefixes as the keys in B-tree. Unlike the previous schemes, every prefixes in routing tables is stored exactly once in our MMSPT. For a routing table of n prefixes, MMSPT requires O(n) memory, and the time for search, insertion and deletion operations are O(logmn), O(mlogmn), and O(mlogmn), respectively (m is the order of the B-tree). Our experimental results conducted by using five real IPv4 routing tables show that MMSPT outperforms two existing B-tree data structures, PIBT (prefix in B-tree) and MRT (multiway range tree), in all aspects. Moreover, since the complexities of MMSPT is not subject to the length of IP addresses, the proposed MMSPT can be easily extended to fit the IPv6.

In this paper, we develop a segment tree data structure for solving dynamic table lookup problems. The proposed dynamic segment tree (DST) uses all of the distinct end points of ranges as the keys based on a new range end point scheme. The new end point scheme generates fewer end points than the traditional end point scheme. DST is implemented as a balanced binary search tree augmented with a range set in each node. The performance of accessing and updating the ranges stored in each node is improved by an efficient range set data structure that combines the priority queue and the interval tree. Based on the proposed data structures, the time complexities of search, insertion, and deletion in a set of N arbitrary ranges are O(log N), O(log N times log Max), and O(Max times log N times log Max), respectively, where Max is the maximum number of ranges covering any address. In practical routing tables, Max is a small constant (six for the routing tables we tested). The memory requirement for DST is O(N log N). The experimental results using real Internet Protocol version 4 (IPv4) routing tables show that both the DST and prefix binary tree on binary tree (PBOB) by Lu et al. (2004) perform much better than the multiway range tree (MRT) by Warkhede et al. (2004) and prefix in B-tree (PIBT) by Lu et al. (2005) in terms of update speed and memory consumption, but DST performs much better than PBOB and a little slower than MRT and PIBT in terms of search speed

In this paper, we propose two fault-diagnosis methods for improving multiple-fault diagnosis resolution. The first method, based on the principle of single-fault activation and single-output observation, employs a new circuit transformation technique in conjunction with the use of a special type of diagnostic test pattern, named single-observation single-location-at-a-time (SO-SLAT) pattern. Given a list of candidate suspects (which could be stuck-at, transition, bridging, or other faults obtained by any existing diagnosis method), we generate a set of SO-SLAT patterns, each of which attempts to activate only one fault in the list and propagate its effects only to a specific observation point. Observing the responses of the circuit under diagnosis to the SO-SLAT patterns helps more precisely determine whether each fault suspect is a true or false candidate. The method can tolerate most of the timing hazards for a more accurate diagnosis of failures caused by timing faults. The second method generates and applies limited-cycle sequential tests, based on a Boolean satisfiability solver, to identify multiple defective signals which can jointly explain the circuit’s faulty behavior. These two methods can be applied independently and/or jointly after any existing state-of-the-art diagnosis process to further improve the diagnosis resolution. The experimental results demonstrate the effectiveness of the proposed methods for diagnosing multiple faults, including timing faults.

Conventionally, many researchers and experts are only focused on studies of routing protocol over the MANET. Currently, the pervasion of Internet applications causes TCP as the standard transmission protocol for most of the networking applications. For the reliable packets delivery, TCP can support the mechanisms of flow and congestion control. Due to the unconstrained movement of the mobile nodes, TCP is unable to notice network congestion or link down to activate related controls on the MANET. Hence, the main purposes of this paper are to refine the influence parameters and to establish their setting rules for TCP performance on the MANET. First, we discuss several TCP parameters, which affect the performance. According to these parameters, we can statically adjust related RTO parameters and analyze Congestion Window in congestion control for evaluating the performance through the simulation on the MANET. Also, we did propose the tuning rules to improve the TCP performance based on simulation results. Consequently, the final result of this paper can be the reference for further studies in QoS features and other applications on the MANET

In this paper, we propose a new circuit transformation technique in conjunction with the use of a special diagnostic test pattern, named SO-SLAT pattern, to achieve higher multiple-fault diagnosis resolutions. For a given list of candidate faults, which could be stuck-at, transition, bridging, or other faults, we generate a set of SO-SLAT patterns, each of which attempts to activate only one fault in the list and propagate its effects to only one observation point. Observing the responses to SO-SLAT patterns helps more precisely identify fault candidates. The method can also tolerate most of the timing hazards for more accurate diagnosis of failures caused by timing faults. The experimen tal results demonstrate the effectiveness of the proposed method for diagnosing multiple faults.

In this paper, we propose a unified approach to test generation, test stimulus compression, and test response compaction. By integrating virtual models of the decompressor and the compactor with the CUT, a standard ATPG tool can be used to generate compressed tests and their corresponding compacted responses as a unified process. In comparison with the existing solutions which treat them as separate tasks, this unified approach could potentially achieve a higher fault coverage and obtain higher input compression and output compaction ratios. Such a unified approach also offers better flexibility for evaluating various test volume reduction architectures. Our experimental results demonstrate the effectiveness of the proposed method

Recent research results have shown that the traditional structural testing for delay and signal integrity faults may result in overtesting due to the nontrivial number of such faults that are untestable in the functional mode although testable in the test mode. This paper presents a pseudofunctional-test methodology that attempts to minimize the overtesting problem of the scan-based circuits in automatic test pattern generation (ATPG) and built-in self-test (BIST) test generation approaches. The first pattern of a two-pattern test is still delivered by scan in the test mode but the pattern is generated in such a way that it does not violate the functional constraints extracted from the functional logic. The second pattern is then generated in a functional mode using the functional justification (also called broadside) test application scheme. The authors use a sequential boolean satisfiability solver to extract a set of functional constraints that consists of illegal states and internal signal correlation. The functional constraints are imposed upon an ATPG tool to generate pseudofunctional tests and/or implemented as a monitor in the BIST environment to allow only functional-like patterns generated from the random test pattern generator as tests. The experimental results for delay faults indicate that the percentage of functionally untestable delay faults is nontrivial for many circuits. This finding supports the hypothesis of the overtesting problem in delay testing. In addition, the results indicate the effectiveness of the proposed constraint extraction method and the proposed BIST scheme.

Watershed segmentation has recently become a popular tool for image segmentation. There are two approaches to implementing watershed segmentation: immersion approach and toboggan simulation. Conceptually, the immersion approach can be viewed as an approach that starts from low altitude to high altitude and the toboggan approach as an approach that starts from high altitude to low altitude. The former seemed to be more popular recently (e.g., Vincent and Soille), but the latter had its own supporters (e.g., Mortensen and Barrett). It was not clear whether the two approaches could lead to exactly the same segmentation result and which approach was more efficient. In this paper, we present two "order-invariant" algorithms for watershed segmentation, one based on the immersion approach and the other on the toboggan approach. By introducing a special RIDGE label to achieve the property of order-invariance, we find that the two conceptually opposite approaches can indeed obtain the same segmentation result. When running on a Pentium-III PC, both of our algorithms require only less than 1/30 s for a 256 x 256 image and 1/5 s for a 512 x 512 image, on average. What is more surprising is that the toboggan algorithm, which is less well known in the computer vision community, turns out to run faster than the immersion algorithm for almost all the test images we have used, especially when the image is large, say, 512 x 512 or larger. This paper also gives some explanation as to why the toboggan algorithm can be more efficient in most cases.

Recent research results have shown that the traditional structural testing for delay and crosstalk faults may result in over-testing due to the non-trivial number of such faults that are untestable in the functional mode while testable in the test mode. This paper presents a pseudo-functional test methodology that attempts to minimize the over-testing problem of the scan-based circuits for the delay faults. The first pattern of a two-pattern test is still delivered by scan in the test mode but the pattern is generated in such a way that it does not violate the functional constraints extracted from the functional logic. In this paper, we use a SAT solver to extract a set of functional constraints which consists of illegal states and internal signal correlation. Along with the functional justification (also called broad-side) test application scheme, the functional constraints are imposed to a commercial delay-fault ATPG tool to generate pseudo-functional delay tests. The experimental results indicate that the percentage of untestable delay faults is non-trivial for many circuits which support the hypothesis of the over-testing problem in delay testing. The results also indicate the effectiveness of the proposed constraint extraction method.

In this paper, we propose a diagnostic test generation method in conjunction with an efficient sequential SAT-based diagnosis procedure to precisely identify multiple defective signals which can jointly explain the circuit's faulty behavior. This method can be applied after any existing state-of-the-art diagnosis process to further improve the diagnosis resolution. The proposed diagnosis method generates limited-cycle sequential tests for SAT-based diagnosis which results in significantly higher diagnosis accuracy for multiple faults. The experimental results demonstrate the effectiveness of the proposed method.

This paper presents a pseudo-functional BIST scheme that attempts to minimize the over-testing problem of logic BIST for delay and crosstalk-induced failures. The over-testing problem is evident from the non-trivial number of structurally testable while functionally untestable (ST-FU) faults. Such faults can be detected by some scan/BIST patterns but not by any functional pattern. The goal of this BIST scheme is to allow only functional-like patterns generated from the BIST random test pattern generator (RTPG) as tests. This is done by inserting a Monitor at the output of the RTPG, which indicates whether the current pattern violates some pre-extracted functional constraints. In case of violation, the pattern is skipped. In our implementation, a SAT solver is used to analyze and extract a set of functional constraints from the functional logic. These functional constraints are then implemented in hardware as the Monitor. Even though the extracted functional constraints can not be exhausted, the proposed BIST scheme can detect and filter out, in real-time, a substantial subset of the nonfunctional patterns, and thus minimizing the over-testing problem. We present some experimental results to demonstrate the effectiveness of the proposed BIST scheme.