Search

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 + √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.

Protocol testing leads to the synchronization problem should test sequences be applied to multiple distanced testers, namely under the multiparty configuration. This paper presents a novel synchronization paradigm which seamlessly unifies two synchronization techniques, self-synchroniable sequences and external synchronization operations, by means of the state expansion transformation . In the paradigm, the protocol specification is first transformed into a state expansion digraph with two pieces of datum augmented. They are: 1. (a) a zero cost assigned to each synchronization-problem-free crossing from one transition to another transition, and 2. (b) a weighted cost assigned to each external synchronization operation whenever the synchronization is deemed necessary. On the basis of the state expansion transformation, synchronizable, optimal sequences for testing can be efficiently derived. To demonstrate the viability of the proposed paradigm, we present the generations of two synchronizable sequences, namely the synchronizable preamble and the synchronizable distinguishing sequence, which have previously been used for the testing of the correctness of a protocol's transition. The paper also shows that the complexities of the two sequences generations are also polynomial-bounded, i.e., O (( np 2 ) log( np )) and O (( n 2 p 2 ) log( np )), respectively, where n and p are the numbers of states and input symbols of the protocol specification.

Call Admission Control (CAC) has been accepted as a potential solution for supporting diverse, heterogeneous traffic sources demanding different Quality of Services (QOSs) in ATM networks. Also, CAC is required to consume a minimum of time and space to make call acceptance decisions. In this paper, we present an efficient neutral-network-based CAC (NNCAC) mechanism for ATM networks with heterogeneous arrivals. All heterogeneous traffic calls are initially categorized into various classes. Based on the number of calls in each class, NNCAC efficiently and accurately estimates the cell delay and cell loss ratio of each class in real time by means of a pre-trained neutral network. According to our decent study which exhibits the superiority of the employment of analysis-based training data over simulation-based data, we particularly construct the training data from a heterogeneous-arrival dual-class queueing model M^[^N^"^1^] + I^[^N^"^2^]/D/1/K, where M and I represent the Bernoulli and interrupted Bernoulli processes, and N"1 and N"2 represent the corresponding numbers of calls, respectively. Analytic results of the queueing model are confirmed by simulation results. Finally, we demonstrate the profound agreement of our neural-network-based estimated results with analytic results, justifying the viability of our NNCAC mechanism.