Browsing by Author "Hsu, SJ"

Now showing 1 - 6 of 6

A network reduction axiom for efficient computation of terminal-pair reliability
(2000-07-01)
Hsu, SJ
;
Yuang, MC
;
資訊工程學系
;
Department of Computer Science
Terminal-pair reliability (TR) in network management determines the probabilistic reliability between two nodes (the source and sink) of a network, given failure probabilities of all links. It has been shown that TR can be effectively computed by means of the network reduction technique. Existing reduction axioms, unfortunately, are limited to trivial rules such as valueless link removal and series-parallel link reduction. In this paper, we propose a novel reduction axiom, referred to as triangle reduction. The triangle reduction axiom transforms a graph containing a triangle subgraph to that excluding the base of the triangle. The computational complexity of the transformation is as low as O(1). With triangle reduction, the number of subproblems generated by partition-based TR algorithms, for simplified grid networks, can be reduced to O(((1 + root 5)/2)(n)). The paper further provides an assessment of the effectiveness of triangle reduction on partition-based TR algorithms with respect to the number of subproblems and computation time through experimenting on published benchmarks and random networks. Experimental results demonstrate that, incorporating triangle reduction, the path-based (cut-based) partition TR algorithm yields a substantially reduced number of subproblems and computation time for all (most of the) benchmarks and random networks. (C) 2000 Elsevier Science Ltd. All rights reserved.
Efficient computation of marginal reliability-importance for reducible(+) networks
(2001-03-01)
Hsu, SJ
;
Yuang, MC
;
資訊工程學系
;
Department of Computer Science
Marginal reliability importance (MRI) of a link with respect to terminal-pair reliability (TR) is the rate to which TR changes with the modification of the success probability of the link. It is a quantitative measure reflecting the importance of the individual link in contributing to TR of a given network. Computing MRI for general networks is an NP-complete problem. Attention has been drawn to a particular set of networks (reducible networks), which can be simplified to source-sink (2-node) networks via 6 simple reduction rules (axioms). The computational complexity of the MRI problem for such networks is polynomial bounded. This paper proposes a new reduction rule, referred to as triangle reduction. The triangle reduction rule transforms a graph containing a triangle subgraph to that excluding the base of the triangle, with constant complexity. Networks which can be fully reduced to source-sink networks by the triangle reduction rule, in addition to the 6 reduction rules, are further defined as reducible(+) networks. For efficient computation of MRI for reducible(+) networks, a 2-phase (2-P) algorithm is given. The 2-P algorithm performs network reduction in phase 1. In each reduction step, the 2-P algorithm generates the correlation, quantified by a reduction factor, between the original network and the reduced network. In phase 2, the 2-P algorithm backtracks the reduction steps and computes MRI, based on the reduction factors generated in phase 1 and a set of closed-form TR formulas. As a result, the 2-P algorithm yields a linearly bounded complexity for the computation of MRI for reducible+ networks. Experimental results from real networks and benchmarks show the superiority, by two orders of magnitude, of the 2-P algorithm over the traditional approach.
Efficient computation of terminal-pair reliability using triangle reduction in network management
(1998)
Hsu, SJ
;
Yuang, MC
;
資訊工程學系
;
Department of Computer Science
Terminal-pair Reliability (TR) in network management determines the probabilistic reliability between two nodes (the source and sink),of a network, given failure probabilities of all links. It has been shown that TR can be effectively computed by means of the network reduction technique. Existing reduction axioms, unfortunately, are limited to simple rules such as valueless link removal and series-parallel link reduction. In this paper, we propose a novel reduction axiom, referred to as triangle reduction. The triangle reduction axiom transforms a graph containing a triangle subgraph to that excluding the base of the triangle. The computational complexity of the transformation is as low as O(I). The paper further provides an assessment of the effectiveness of triangle reduction on partition-based TR algorithms with respect to the number of subproblems and computation time. Experimental results demonstrate that, incorporating triangle reduction, the partition-based TR algorithms yield a substantially reduced number of subproblems and computation time for all benchmarks and random networks.
Efficient minimization of homogeneous FSMs for fault diagnosis
(1998-03-01)
Lin, RS
;
Yuang, MC
;
Hsu, SJ
;
資訊工程學系
;
Department of Computer Science
On the base of the Finite State Machine (FSM) model, the fault diagnosis problem deals with the identification of a faulty implementation against its specification represented by an FSM. In particular, to efficiently identify potential faulty implementations caused by a transfer error in an FSM, cross-verification over the FSM is performed after all potential faulty FSMs have been minimized. Existing minimization algorithms become inefficient due to the lack of taking advantage of the homogeneity of these potential faulty FSMs. In this paper, we propose a two-phase algorithm for the efficient and simultaneous minimization of a set of homogeneous faulty FSMs. Disregarding the suspicious transition, the first phase of the algorithm performs minimization of these faulty FSMs via a common digraph of th FSMs. These faulty FSMs are considered minimized if the distinguishing sequences of all state-pairs can be discovered from the common digraph. Otherwise, the algorithm in the second phase performs minimization for each faulty FSM by individually restoring its corresponding unexpected transition in the reduced common digraph. To demonstrate the efficiency of the two-phase algorithm, we carried out experiments on a number of realistic protocol specifications, including the Alternation Bit Protocol (ABP), Transport Protocol Class 4 (TP4), and ISDN Basic Rate Interface (BRI) protocol. Experimental results show that the algorithm renders the minimization complexity greatly reduced for most of the realistic protocol FSMs.
Terminal-pair Reliability in ATM Virtual Path networks
(1997)
Chen, YG
;
Hsu, SJ
;
Yuang, MC
;
交大名義發表
;
資訊工程學系
Terminal-pair Reliability (TR) in an Asynchronous Transfer Mode (ATM) Virtual Path (VP) network corresponds to probabilistic quantization of robustness between two VP terminators, given a VP layout and failure probabilities of physical links. Existing TR algorithms are unviable for ATM VP networks owing to either high complexity or failure dependency among VPs. The goal of the paper is to propose two efficient algorithms for TR computation between two VP terminators by means of variants of path-based and cut-based partition methods which have been effectively used for TR computation in traditional networks. The first variant, called the Path-based Virtual Path Reliability (PVPR) algorithm, partitions the search space based on a physical path embedding the shortest route of VPs from the source to the destination terminator. The second variant, called the Cut-based Virtual Path Reliability (CVPR) algorithm, in lieu, performs the partition on the basis of a physical cutset separating the source from the remaining terminators. In both algorithms, each subproblem is recursively processed by means of partition until the source and destination terminators are contracted or disconnected. Experimental results reveal that, CVPR outperforms PVPR with respect to computation time. Moreover, compared to one of the most promising TR algorithms, both CVPR and PVPR exhibit superior performance. The two algorithms and their promising results consequently facilitate the real-time computation of the reliability or robustness of ATM VP networks.
Terminal-pair reliability in ATM virtual path networks
(2000-09-01)
Hsu, SJ
;
Chen, YG
;
Yuang, MC
;
資訊工程學系
;
Department of Computer Science
Terminal-pair reliability (TR) in an asynchronous transfer mode (ATM) Virtual path (VP) network corresponds to probabilistic quantification of robustness between two VP terminators, given the VP layout and the failure probabilities of physical links. Existing TR algorithms are shown to be unviable for ATM VP networks owing to either high complexities or failure dependency among VPs. The goal of the paper is to propose efficient algorithms for the computation of TR between two VP terminators by means of variants of path-based and cut-based partition methods which have been effectively used for the computation of TR in traditional networks. The first variant, called the path-based virtual path reliability (PVPR) algorithm, partitions the search space based on a physical path embedding the shortest route of VPs from the source terminator to the destination terminator. The second variant, called the cut-based Virtual path reliability (CVPR) algorithm, in lieu, performs the partition on the basis of a physical outset separating the source from the remaining terminators. In both algorithms, each subproblem is recursively processed by means of partition until the source and destination terminators are contracted or disconnected. Experimental results demonstrate that, compared to one promising TR algorithm (called EBRM), both the PVPR and CVPR algorithms improve the running time by five orders of magnitude. In particular, the CVPR outperforms EBRM more than PVPR does in terms of computation time. The two algorithms and their promising results consequently facilitate the real-time computation of the reliability or robustness of ATM VP networks. (C) 2000 Elsevier Science Ltd. All rights reserved.