This paper focuses on helping network providers to carry out network capacity planning and sales projection by answering the question: For a given topology and capacity, whether the network can serve current flow demands with high probabilities? We name such probability as “ flow availability” and present the -flow availability estimation (FAVE) problem, which is a generalisation of network connectivity or maximum flow reliability estimations. Realistic networks are often large and dynamic, so flow availabilities cannot be evaluated analytically and simulation is often used. However, naive Monte Carlo (MC) or importance sampling (IS) techniques take an excessive amount of time. To quickly estimate flow availabilities, we utilize the correlations among link and flow failures to figure out the importance of roles played by different links in flow failures, and design three “sequential importance sampling” (SIS) methods which achieve “bounded or even vanishing relative error” with linear computational complexities. When applying to a realistic network, our method reduces the flow availability estimation cost by 900 and 130 times compared with MC and baseline IS methods, respectively. Our method can also facilitate capacity planning by providing better flow availability guarantees, compared with traditional methods.
Other reliabilities : Some works also study the connection availability @cite_13 and service availability @cite_3 , and consider the probability that a connection or service is available. Authors in ! @cite_13 evaluate the connection availability by computing the connection probability of a small subset of nodes exactly. Authors in @cite_3 evaluate the service availability by using IS to estimate path availabilities. The problem considered in @cite_13 @cite_3 can be transformed to a problem of determining the connectivity of certain nodes, where the network topology is given. Hence, @cite_13 @cite_3 are essentially the same with the NCR related work.
@cite_13 @cite_3
2129219909 2017999041 2545435035 2009235272
In this paper we consider the problem of maximizing the number of supported connections in arbitrary wireless networks where a transmission is supported if and only if the signal-to-interference-plus-noise ratio at the receiver is greater than some threshold. The aim is to choose transmission powers for each connection so as to maximize the number of connections for which this threshold is met. We believe that analyzing this problem is important both in its own right and also because it arises as a subproblem in many other areas of wireless networking. We study both the complexity of the problem and also present some game theoretic results regarding capacity that is achieved by completely distributed algorithms. We also feel that this problem is intriguing since it involves both continuous aspects (i.e. choosing the transmission powers) as well as discrete aspects (i.e. which connections should be supported). Our results are: ldr We show that maximizing the number of supported connections is NP-hard, even when there is no background noise. This is in contrast to the problem of determining whether or not a given set of connections is feasible since that problem can be solved via linear programming. ldr We present a number of approximation algorithms for the problem. All of these approximation algorithms run in polynomial time and have an approximation ratio that is independent of the number of connections. ldr We examine a completely distributed algorithm and analyze it as a game in which a connection receives a positive payoff if it is successful and a negative payoff if it is unsuccessful while transmitting with nonzero power. We show that in this game there is not necessarily a pure Nash equilibrium but if such an equilibrium does exist the corresponding price of anarchy is independent of the number of connections. We also show that a mixed Nash equilibrium corresponds to a probabilistic transmission strategy and in this case such an equilibrium always exists and has a price of anarchy that is independent of the number of connections. This work was supported by NSF contract CCF-0728980 and was performed while the second author was visiting Bell Labs in Summer, 2008. Reliability and availability have always been important characteristics of systems but become even more critical and complex issues on networks. Due to the high complexity of accurate calculation methods, simulation methods for network reliability and availability evaluation have been a popular area of research, and received significant attention. In this paper the network topology model, the failure driven simulation method and the reliability and availability statistical algorithms are put forward, and then the network reliability and availability simulation flow based on the Monte Carlo method was designed. This simulation method can be used to calculate the reliability and availability of a network whose nodes and links may be failure. Two repair policies, immediate repair and delay repair, are provided to choose. Finally, the backbone of CERNET (China Education and Research Network) is taken as an example and the simulation results are analyzed. In this paper we consider a network where the nodes locations are modeled by a realization of a Poisson point process and remains fixed or changes very slowly over time. Most of the literature focuses on the spatial average of the link outage probabilities. But each link in the network has an associated link-outage probability that depends on the fading, path loss, and the relative locations of the interfering nodes. Since the node locations are random, the outage probability of each link is a random variable and in this paper we obtain its distribution, instead of just the spatial average. This work supplements the existing results which focus mainly on the average outage probability averaged over space. We propose a new notion of transmission capacity (TC) based on the outage distribution, and provide asymptotically tight bounds for the TC. We address content discovery in wireless networks with infrastructure, where mobile nodes store, advertise, and consume content while Broker entities running on infrastructure devices let demand and offer meet. We refer to this paradigm as match-making, highlighting its features within the confines of the standard publish-and-subscribe paradigm. We study its performance in terms of success probability of a content query, a parameter that we strive to increase by acting as follows: 1) We design a credit-based scheme that makes it convenient for rational users to provide their content (thus discouraging free-riding behavior), and it guarantees them a fair treatment. 2) We increase the availability of either popular or rare content, through an efficient caching scheme. 3) We counter malicious nodes whose objective is to disrupt the system performance by not providing the content they advertise. To counter the latter as well as free riders, we introduce a feedback mechanism that enables a Broker to tell apart well- and misbehaving nodes in a very reliable manner, and to ban the latter. The properties of our match-making scheme are analyzed through game theory. Furthermore, via ns-3 simulations, we show its resilience to different attacks by malicious users and its good performance with respect to other existing solutions.