Reliability evaluation for distributed computing networks withimperfect nodes

This paper examines two compensating methods that: (1) account for imperfect nodes, and (2) can be embedded in most symbolic network reliability algorithms that presume perfect nodes. The Aggarwal method can be exponential in time with the number of links, whereas the Torrieri method is always linear. However the Torrieri method can yield incorrect results for some undirected networks. This paper points out such incorrectness and then proposes an efficient reliability evaluation algorithm (ENR/KW) accounting for imperfect nodes in distributed computing networks. Based on the concept of network partition, ENR/KW exploits some simple efficient techniques to handle the unreliable nodes, for directly computing the network reliability expression considering imperfect nodes instead of using any compensating method. The basic idea of ENR/KW is to partition the network directly into a set of smaller disjoint subnetworks by only considering link elements as if all nodes are perfect. Each disjoint subnetwork is generated by maintaining a specific directed graph structure to consider the effect of imperfect nodes. Therefore, the reliability expression for imperfect nodes can be obtained directly from the disjoint subnetwork and the specific directed graph. ENR/KW can be generalized to evaluate various network reliability measures considering imperfect nodes such as terminal-pair reliability, K-terminal reliability, and distributed-program reliability. Many experiments for evaluating the terminal-pair reliability and distributed-program reliability were performed on a SUN workstation to show the efficiency of ENR/KW in terms of the number of generated subnetworks and overall computation time     

Maximum Reliability Route Subject to M Improvements In A Nondirected Network

The network consists of imperfect nondirected links and perfect nodes. For each link, some i.i.d. parallel redundant links will be attached, thus improving the reliability of communication between that pair of nodes. The problem is to determine the maximum-reliability route and optimally distribute a given number, M, of parallel redundant links on this path. Each redundant link has the reliability of the original link between the two nodes. Policy iteration technique of dynamic programming is used to solve the problem.     

A Simple Method for Reliability Evaluation of a Communication System

Very few techniques exist for reliability evaluation of communication systems where links as well as nodes have certain probability of failure. This correspondence describes a technique by which the reliability expression for such a system can be conveniently derived. It is also shown that using the concept of this correspondence, it is possible to extend all the existing reliability-evaluation algorithms to communication systems with little effort.     

Optimal design of k-out-of-n:G subsystems subjected to imperfect fault-coverage

Systems subjected to imperfect fault-coverage may fail even prior to the exhaustion of spares due to uncovered component failures. This paper presents optimal cost-effective design policies for k-out-of-n:G subsystems subjected to imperfect fault-coverage. It is assumed that there exists a k-out-of-n:G subsystem in a nonseries-parallel system and, except for this subsystem, the redundancy configurations of all other subsystems are fixed. This paper also presents optimal design polices which maximize overall system reliability. As a special case, results are presented for k-out-of-n:G systems subjected to imperfect fault-coverage. Examples then demonstrate how to apply the main results of this paper to find the optimal configurations of all subsystems simultaneously. In this paper, we show that the optimal n which maximizes system reliability is always less than or equal to the n which maximizes the reliability of the subsystem itself. Similarly, if the failure cost is the same, then the optimal n which minimizes the average system cost is always less than or equal to the n which minimizes the average cost of the subsystem. It is also shown that if the subsystem being analyzed is in series with the rest of the system, then the optimal n which maximizes subsystem reliability can also maximize the system reliability. The computational procedure of the proposed algorithms is illustrated through the examples.     

Enumeration of minimal cutsets of an undirected graph

Cutsets and tiesets are needed to calculate reliability of or maximal flow through a network. Algorithms for enumeration of these cutsets and tiesets are being designed to facilitate these calculations. However, these algorithms either involve advanced mathematics or are based on technical notions and ideas such as fault tree analysis, etc. We have given here two different algorithms for enumerating minimal cutsets of an undirected graph (i.e. with feedback). An algorithm, proposed to enumerate minimal cutsets of an acyclic directed graph with adjacent nodes, is also shown to hold for an undirected one with some modifications; the second one is for finding minimal cutsets of a general undirected graph, which holds good for a directed one as well. Our algorithms are simple and do not need any prior knowledge of reliability notions or ideas, or advanced mathematics. Three examples are given to illustrate the algorithms.     

On the utility of MIMO multi-relay networks for modulation identification over spatially-correlated channels

The necessity to perfectly monitor the intercepted signals for spatially-correlated multiple-input multiple-output (MIMO) systems, involves modulation identification algorithms. In this paper, we present an algorithm dedicated to the modulation identification for correlated MIMO relaying broadcast channels with direct link using multi-relay nodes. By modeling spatially-correlated MIMO channels as Kronecker-structured and the imperfect channel state information of both the source-to-destination and the relay-to-destination errors as independent complex Gaussian random variables, we firstly derive the ergodic capacity of the proposed transmission system. It turns out that the ergodic capacities improve with the number of relay nodes. Based on a pattern recognition approach using the higher order statistics features and the Bagging classifier, we show that the probability to distinguish among M-ary shift keying linear modulation types without any priori modulation information is enhanced compared to the decision tree (J48), the tree augmented naive Bayes, the naive Bayes using discretization and the multilayer perceptron classifiers. We also study the effect of increasing the number of relay nodes. Numerical simulations show that the proposed algorithm using the cooperation of multi-relay nodes with the source node can avoid the performance deterioration in modulation identification caused by both spatial correlation and imperfect CSI.     

Bounds on the reliability of distributed systems with unreliable nodes & links

The reliability of distributed systems & computer networks in which computing nodes and/or communication links may fail with certain probabilities have been modeled by a probabilistic network. Computing the residual connectedness reliability (RCR) of probabilistic networks under the fault model with both node & link faults is very useful, but is an NP-hard problem. Up to now, there has been little research done under this fault model. There are neither accurate solutions nor heuristic algorithms for computing the RCR. In our recent research, we challenged the problem, and found efficient algorithms for the upper & lower bounds on RCR. We also demonstrated that the difference between our upper & lower bounds gradually tends to zero for large networks, and are very close to zero for small networks. These results were used in our dependable distributed system project to find a near-optimal subset of nodes to host the replicas of a critical task.     

无线广播网络的可靠性分析

本文提出了一个计算无线广播网络的Ｋ－终点可靠度方法。因为ＲＢＮ的Ｋ－终点可靠度问题是个ＮＰ－困难问题,所以已有的结果只是一些近似算法和针对某些特殊ＲＢＮ的算法。     

Determining terminal-pair reliability based on edge expansiondiagrams using OBDD

For calculating terminal-pair reliability, most published algorithms are based on the sum of disjoint products. However, these tree-based partitions lack the capability to avoid redundant computation due to the isomorphic sub-problems. To overcome these problems, an efficient methodology to evaluate the terminal-pair reliability, based on edge expansion diagrams using OBDD (ordered binary decision diagram) is presented. First, the success path function of a given network is constructed based on OBDD by traversing the network with diagram-based edge expansion. Then the reliability of the network is obtained by directly evaluating on this OBDD recursively. The effectiveness of this approach is demonstrated by performing experiments on benchmarks collected by previous works including the larger networks (from 4 to 2 ⁹⁹ paths). A dramatic improvement, as demonstrated by the experimental results for a 2-by-n lattice network is that the number of OBDD nodes is only linearly proportional to the number of stages, and is much better than previous algorithms which have exponential complexity by using the sum of disjoint products. The CPU time of reliability calculation for a 100-stage lattice network is only about 2.5 seconds with 595 nodes generated on a SPARC 20 workstation with 128 MBytes of memory. Thus, with this approach, the terminal-pair reliability of large networks can be efficiently evaluated better than thought possible     

An efficient fault-tolerant distributed channel allocation algorithm for cellular networks

A channel allocation algorithm in a cellular network consists of two parts: a channel acquisition algorithm and a channel selection algorithm. Some of the previous works in this field focused on centralized approaches to allocating channels. But, centralized approaches are neither scalable nor reliable. Recently, distributed dynamic channel allocation algorithms have been proposed, and they have gained a lot of attention due to their high reliability and scalability. But, in most of the algorithms, the cell that wants to borrow a channel has to wait for replies from all its interference neighbors and, hence, is not fault-tolerant. In this paper, we propose a new algorithm that is fault-tolerant and makes full use of the available channels. It can tolerate the failure of mobile nodes as well as static nodes without any significant degradation in service.     

Distributed differential space-time coding for asynchronous two-way relaying networks with Nakagami-m fading

A signal detection scheme was proposed for two-way relaying networks (TWRNs) using distributed differential space-time coding (DDSTC) under imperfect synchronization. Unlike most existing work perfect with synchronization assumed, a relative delay between the signals transmitted from both sources to the relay was considered. Since perfect channel state information (CSI) is difficult to be acquired in fast fading, the scenarios and computation complexity will be increased especially when there appear multiple relays, CSI is assumed unavailable at all nodes. Therefore, the article proposes a differential signal detection scheme based on estimating and cancelling the imperfect synchronization component in the received signal at the two source nodes, followed by a least square (LS) decoder. Simulations, using the Nakagami-m fading channel due to its versatile statistical distribution property, show that the proposed scheme for both source nodes are effective in suppressing the inter-symbol interference (ISI) caused by imperfect synchronization while neither the source nodes nor the relay nodes have any knowledge of CSI.     

Adding the Reliability on Tree Based Topology Construction Algorithms for Wireless Sensor Networks

Topology control is a technique used in wireless sensor networks to maximize energy efficiency and network lifetime. In previous literature, many tree based techniques have been proposed to save energy and increase the network lifetime. In tree based algorithms, the most promising solution is the formation of a network backbone, which serves on behalf of rest of the nodes in the network and therefore leading towards Connected Dominating Set (CDS) formulation. However, one imminent problem with all tree based solution is a compromise on network reliability. Therefore, to address reliability issues in tree based solutions, in this paper, we propose Poly3 which maintains cliques of size three in order to achieve network reliability on top of the CDS algorithm. This makes the network more robust to link removal. Our empirical and mathematical analysis reveals that Poly3 provides better reliability than algorithms of the same kind.     

Novel quantization‐based spectrum sensing scheme under imperfect reporting channel and false reports

In this paper, a novel sensing scheme, uniform quantization for cooperative sensing (UniQCS), that employs a uniform quantizer is proposed. UniQCS is based on energy detection and uses weight vector for global decision function. It performs better than hard decision algorithms such as majority and k‐out‐of‐n in terms of probability of detection and false alarm at the cost of a marginal increase in overhead bits under imperfect reporting channel and false reports. The probability of detection is maximized for a given probability of false alarm constraint by the proposed method. For detailed analysis, the UniQCS is compared with equal gain combiner scheme, which performs far better than hard decision algorithms, via highest bandwidth requirement. The proposed algorithm performs close to equal gain combiner. Moreover, the robustness of UniQCS to sensing error is analyzed when some nodes always report false decisions to the fusion center and the reporting channel is imperfect. For probability of false alarm equal to 0.01, performance gain of UniQCS is at least 45% compared with the other methods when there are two false reporting nodes. UniQCS performance gain is at least 15% compared with other methods for probability of reporting channel error equal to 0.001. Copyright © 2012 John Wiley & Sons, Ltd.     

约束条件下随机流网络可靠度的计算

在质量管理的角度上,系统可靠度的计算是随机流网络的一个很重要的方面。一般计算网络可靠度的方法是在考虑边有可能无效,节点保持完好且没有流量的限制的情况下进行的。文中提出一种在既考虑节点流量的限制又考虑整个网络成本预算的约束条件下计算网络可靠度的方法,使其更接近实际。     

A Classification Tree Based Approach for the Development of Minimal Cut and Path Vectors of a Capacitated Network

This paper presents a holistic method that links together Monte-Carlo simulation, exact algorithms, and a data mining technique, to develop approximate bounds on the reliability of capacitated two-terminal networks. The method uses simulation to generate network configurations that are then evaluated with exact algorithms to investigate if they correspond to a network success or failure. Subsequently, the method implements commercially available software to generate a classification tree that can then be analyzed, and transformed into capacitated minimal cut or path vectors. These vectors correspond to the capacitated version of binary minimal cuts & paths of a network. This is the first time that these vectors are obtained from a decision tree, and in this respect, research efforts have been focused on two main directions: 1) deriving an efficient yet intuitive approach to simulate network configurations to obtain the most accurate information; and given that the classification tree method could for some applications provide imperfect or incomplete information without the explicit knowledge of the reliability engineer, 2) understand the relationship between the obtained vectors, and the real capacitated minimal cut & path vectors of the network, and its reliability. The proposed method has been tested on a set of case networks to assess its validity & accuracy. The results obtained show that the technique described is effective, simple, and widely applicable.     

A coherent model for reliability of multiprocessor networks

Graph G has perfectly reliable nodes and edges that are subject to stochastic failure. The network reliability R is the probability that the surviving edges induce a spanning connected subgraph of G. Analysis problems concern determining efficient algorithms to calculate R, which is known to be NP-hard for general graphs. Synthesis problems concern determining graphs that are, according to some definition, the most reliable in the class of all graphs having a given number of edges and nodes. In applications where the edges are perfectly reliable and the nodes are subject to failure, another measure (residual node connectedness reliability) is defined as the probability that the surviving nodes induce a connected subgraph of G. Referring to such a subset as an operating state, the measure is not coherent because a superset of an operating state need not be an operating state. This paper proposes a new definition of network reliability that handles the case of node failures; it is coherent. We determine many of its properties, and present several analysis and synthesis results     

An overview of reliable multicast transport protocol II

This document provides an overview of the reliable multicast transport protocol II, RMTP-II. RMTP-II is a reliable multicast protocol, designed to reliably and efficiently send data from a few senders to large groups of simultaneous recipients. It works over both symmetric networks and asymmetrical network topologies such as those provided by satellite, cable modem, or ADSL carriers. Before sending, each sender must connect with a trusted top node to receive permission and control parameters for its data stream. The top node provides network managers with a single point of control for the senders, allowing them to monitor and control the traffic being sent. RMTP-II builds on a rich field of existing work, and adds to it the following novel contributions. It differentiates the roles of the nodes in the protocol, provides algorithms for smoothing and control of the return (TRACK) traffic, and provides explicit support for highly asymmetrical networks. It provides explicit network management controls through a centralized point of control, a fully distributed membership protocol that enables positive confirmation of data delivery, and fault recovery algorithms which are integrated to the reliability semantics of the protocol. It includes a novel reliability level called time bounded reliability, and offers a unique combination of TRACKs, NACKs, and FEC for increased scalability and real-time performance. Finally, it integrates distributed algorithms for RTT calculation to each receiver, and provides automatic configuration of receiver nodes     

Distributed access algorithms for portable meshed vsat networks

In recent years technological evolution has made it possible to develop portable meshed VSAT networks (PMVN). Among the distinguishing features of this satellite network family we can cite the following: portable terminals, direct connectivity is allowed between any pair of network nodes (meshed topology), the network may comprise a high number of terminals, the network is intended to offer low rate voice and data communication services. For this satellite network family, the most widely used technique of resource allocation is centralized allocation. But in any network with a high number of nodes, the dependence on a single resource is a potential bottleneck of the network, in terms of flexibility, reliability and scalability of costs. In order to avoid this drawback, two distributed access algorithms are proposed in this paper. Both algorithms are based on carrier sensing (CS). In order to evaluate their performance, a model for PMVNs is proposed. This model is used to study the behaviour of the conventional access technique (central allocation) and the proposed distributed algorithms. We conclude that the use of the proposed distributed algorithms is feasible with present technology, with a performance comparable to that of the central allocation algorithm, but with the advantages associated with distributed algorithms concerning flexibility, reliability and cost.     

无线传感器网络基于多元簇首的分簇数据收集算法

为了提高数据收集可靠性和延长网络生命周期,该文提出基于多元簇首的分簇数据收集算法。算法将网络划分为大小相等的栅格,由每个栅格中的节点各自构成一个簇,根据节点失效概率从每个栅格中选出多个簇首,并由同一栅格中的多个簇首协作完成栅格中节点的数据收集任务。此外,算法还采取了一些降低能量开销的措施。仿真实验结果表明,与现有相关算法相比,该算法具有较高的数据收集可靠性,并能够显著延长网络生命周期。     

Bounding algorithms for two-terminal network reliability

Determining the exact reliability of a complex network involves extremely large amount of computation. Consequently, it is appropriate to discuss method for approximating network reliability. This paper develops methods for obtaining upper and lower bounds for two-terminal network reliability. Construction of different layers for a network is used to develop an algorithm to compute an upper bound for the reliability of a network. The nodes of this network are completely reliable and arcs fail statistically independently with known probabilities. A simple approach, to obtain a lower bound for the reliability of the network is also presented. Examples illustrate the use of the algorithms and show that the proposed bounds fare better than the well-known Esary and Proschan bounds.