This paper presents a factoring algorithm for computing source-to- K terminal (SKT) reliability, the probability that a source s can send message to a specified set of terminals K, in acyclic directed networks (AD-net...This paper presents a factoring algorithm for computing source-to- K terminal (SKT) reliability, the probability that a source s can send message to a specified set of terminals K, in acyclic directed networks (AD-networks) in which both nodes and edges can fail. Based on Pivotal decomposition theorem, a new formula is derived for computing the SKT reliability of AD-networks. By establishing a topological property of AD-networks, it is shown that the SKT reliability of AD- networks can be computed by recursively applying this formula. Two new Reliability- Preserving Reductions are also introduced. The recursion tree generated by the presented algorithm has at most 2 leaf nodes, where V and K are the numbers of nodes and terminals, respectively, while C is the number of the nodes satisfying some specified conditions. The computation complexity of the new algorithm is O (E. V. 2) in the worst case, where E is the number of edges. For source-to-all-terminal (SAT) reliability, its computation complexity is O(E). Comparison of the new algorithm with the existing ones indicates that the new algorithm is more efficient for computing the SKT reliability of AD-networks.展开更多
Computer communication network architectures for CIMS are based on the OSI Reference Model. In this paper, CIMS network protocol model is set up on the basis of the corresponding service model. Then the authors presen...Computer communication network architectures for CIMS are based on the OSI Reference Model. In this paper, CIMS network protocol model is set up on the basis of the corresponding service model. Then the authors present a formal specification of transport protocols by using an extended Predicate/Transition net system that is briefly introduced in the third part. Finally, the general methods for the Petri nets based fornlal specification of CIMS network protocols are outlined.展开更多
文摘This paper presents a factoring algorithm for computing source-to- K terminal (SKT) reliability, the probability that a source s can send message to a specified set of terminals K, in acyclic directed networks (AD-networks) in which both nodes and edges can fail. Based on Pivotal decomposition theorem, a new formula is derived for computing the SKT reliability of AD-networks. By establishing a topological property of AD-networks, it is shown that the SKT reliability of AD- networks can be computed by recursively applying this formula. Two new Reliability- Preserving Reductions are also introduced. The recursion tree generated by the presented algorithm has at most 2 leaf nodes, where V and K are the numbers of nodes and terminals, respectively, while C is the number of the nodes satisfying some specified conditions. The computation complexity of the new algorithm is O (E. V. 2) in the worst case, where E is the number of edges. For source-to-all-terminal (SAT) reliability, its computation complexity is O(E). Comparison of the new algorithm with the existing ones indicates that the new algorithm is more efficient for computing the SKT reliability of AD-networks.
文摘Computer communication network architectures for CIMS are based on the OSI Reference Model. In this paper, CIMS network protocol model is set up on the basis of the corresponding service model. Then the authors present a formal specification of transport protocols by using an extended Predicate/Transition net system that is briefly introduced in the third part. Finally, the general methods for the Petri nets based fornlal specification of CIMS network protocols are outlined.
