|
| ||
|
|
||
Binary Decision Diagram (binary + decision_diagram)
Selected AbstractsEfficient packet classification on network processorsINTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, Issue 1 2008Koert Vlaeminck Abstract Always-on networking and a growing interest in multimedia- and conversational-IP services offer an opportunity to network providers to participate in the service layer, if they increase functional intelligence in their networks. An important prerequisite to providing advanced services in IP access networks is the availability of a high-speed packet classification module in the network nodes, necessary for supporting any IP service imaginable. Often, access nodes are installed in remote offices, where they terminate a large number of subscriber lines. As such, technology adding processing power in this environment should be energy-efficient, whilst maintaining the flexibility to cope with changing service requirements. Network processor units (NPUs) are designed to overcome these operational restrictions, and in this context this paper investigates their suitability for wireline and robust packet classification in a firewalling application. State-of-the-art packet classification algorithms are examined, whereafter the performance and memory requirements are compared for a Binary Decision Diagram (BDD) and sequential search approach. Several space optimizations for implementing BDD classifiers on NPU hardware are discussed and it is shown that the optimized BDD classifier is able to operate at gigabit wirespeed, independent of the ruleset size, which is a major advantage over a sequential search classifier. Copyright © 2007 John Wiley & Sons, Ltd. [source] An efficient real-time method of analysis for non-coherent fault treesQUALITY AND RELIABILITY ENGINEERING INTERNATIONAL, Issue 2 2009Rasa Remenyte-Prescott Abstract Fault tree analysis is commonly used to assess the reliability of potentially hazardous industrial systems. The type of logic is usually restricted to AND and OR gates, which makes the fault tree structure coherent. In non-coherent structures not only components' failures but also components' working states contribute to the failure of the system. The qualitative and quantitative analyses of such fault trees can present additional difficulties when compared with the coherent versions. It is shown that the binary decision diagram (BDD) method can overcome some of the difficulties in the analysis of non-coherent fault trees. This paper presents the conversion process of non-coherent fault trees to BDDs. A fault tree is converted to a BDD that represents the system structure function (SFBDD). An SFBDD can then be used to quantify the system failure parameters but is not suitable for the qualitative analysis. Established methods, such as the meta-products BDD method, the zero-suppressed BDD (ZBDD) method and the labelled BDD (L-BDD) method, require an additional BDD that contains all prime implicant sets. The process using some of the methods can be time consuming and is not very efficient. In addition, in real-time applications the conversion process is less important and the requirement is to provide an efficient analysis. Recent uses of the BDD method are for real-time system prognosis. In such situations as events happen, or failures occur, the prediction of mission success is updated and used in the decision-making process. Both qualitative and quantitative assessments are required for the decision making. Under these conditions fast processing and small storage requirements are essential. Fast processing is a feature of the BDD method. It would be advantageous if a single BDD structure could be used for both the qualitative and quantitative analyses. Therefore, a new method, the ternary decision diagram (TDD) method, is presented in this paper, where a fault tree is converted to a TDD that allows both qualitative and quantitative analyses and no additional BDDs are required. The efficiency of the four methods is compared using an example fault tree library. Copyright © 2008 John Wiley & Sons, Ltd. [source] The use of not logic in fault tree analysisQUALITY AND RELIABILITY ENGINEERING INTERNATIONAL, Issue 3 2001J. D. Andrews Abstract Risk and safety assessments carried out on potentially hazardous industrial systems commonly employ fault tree analysis to predict the probability or frequency of system failure. Causes of the system failure mode are developed in an inverted tree structure where the events are linked using logic gates. The type of logic is usually restricted to AND and OR gates which makes the fault tree structure coherent. The use, directly or indirectly, of the NOT logic gate is generally discouraged as this can result in a non-coherent structure. Non-coherent structures mean that components' working states contribute to the failure of the system. The qualitative and quantitative analysis of such fault trees can present additional difficulties when compared to the coherent versions. This paper examines some of the difficulties that can occur, and what potential benefits can be derived from the incorporation of NOT logic. It is shown that the binary decision diagram (BDD) method can overcome some of the difficulties in the analysis of non-coherent fault trees. Copyright © 2001 John Wiley & Sons, Ltd. [source] Comparison of two new approaches to variable ordering for binary decision diagramsQUALITY AND RELIABILITY ENGINEERING INTERNATIONAL, Issue 3 2001L. M. Bartlett Abstract Fault tree analysis, FTA, is one of the most commonly used techniques for safety system analysis. There can be problems with the efficiency and accuracy of the approach when dealing with large tree structures. Recently the binary decision diagram (BDD) methodology has been introduced which significantly aids the analysis of the fault tree diagram. The approach has been shown to improve both the efficiency of determining the minimal cut sets of the fault tree, and also the accuracy of the calculation procedure used to quantify the top event parameters. To utilize the BDD technique the fault tree structure needs to be converted into the BDD format. Converting the fault tree is relatively straightforward but requires the basic events of the tree to be placed in an ordering. The ordering of the basic events is critical to the resulting size of the BDD, and ultimately affects the performance and benefits of this technique. There are a number of variable ordering heuristics in the literature, however the performance of each depends on the tree structure being analysed. These heuristic approaches do not yield a minimal BDD structure for all trees, some approaches generate orderings that are better for some trees but worse for others. Within this paper two approaches to the variable ordering problem have been discussed. The first is the pattern recognition approach of neural networks, which is used to select the best ordering heuristic for a given fault tree from a set of alternatives. The second examines a completely new heuristic approach of using the structural importance of a component to produce a ranked ordering. The merits of each are discussed and the results compared. Copyright © 2001 John Wiley & Sons, Ltd. [source] | ||||||||||