The node-reliability polynomial nRelG(p) measures the probability that a connected network remains connected given that each node functions independently with probability p. Computing node-reliability polynomials nRelG(p) exactly is NP-hard. Here we propose efficient approximations. First, we develop an accurate Monte Carlo simulation, which is accelerated by incorporating a Laplace approximation that captures the polynomial’s main behavior. We also introduce three degree-based stochastic approximations (Laplace, arithmetic, and geometric), which leverage the degree distribution to estimate nRelG(p) with low complexity. Beyond approximations, our framework addresses the reliability-based Global Robustness Improvement Problem (k-GRIP) by selecting exactly k links to add to a given graph so as to maximize its node reliability. A Greedy Lowest-Degree Pairing Link Addition (Greedy-LD) Algorithm, is proposed which offers a computationally efficient and practically effective heuristic, particularly suitable for large-scale networks.

Predicting future dynamics on networks is challenging, especially when the complete and accurate network topology is difficult to obtain in real-world scenarios. Moreover, the higher-order interactions among nodes, which have been found in a wide range of systems in recent years, such as the nets connecting multiple modules in circuits, further complicate accurate prediction of dynamics on hypergraphs. In this work, we proposed a two-step method called the topology-agnostic higher-order dynamics prediction (TaHiP) algorithm. The observations of nodal states of the target hypergraph are used to train a surrogate matrix, which is then employed in the dynamical equation to predict future nodal states in the same hypergraph, given the initial nodal states. TaHiP outperforms three latest Transformer-based prediction models in different real-world hypergraphs. Furthermore, experiments in synthetic and real-world hypergraphs show that the prediction error of the TaHiP algorithm increases with mean hyperedge size of the hypergraph, and could be reduced if the hyperedge size distribution of the hypergraph is known.

In this paper, we propose closed-form analytic approximations for the number of controllable nodes in sparse communication networks from the aspect of network controllability, considering link-based random attack, targeted attack, as well as random attack under the protection of critical links. We compare our approximations with simulation results on communication networks. Results show that our approximations perform well for all three attack strategies as long as the fraction of removed links is small. Only when the fraction of removed links is large, our approximation for targeted attacks does not fit well with simulation results. Finally, we validate our approximations using 200 communication networks and some synthetic networks. Results show that our approximations perform well in most cases.

Due to their importance to society, communication networks should be built and operated to withstand failures. However, cost considerations make network providers less inclined to take robustness measures against failures that are unlikely to manifest, like several failures coinciding simultaneously in different geographic regions of their network. Considering networks embedded in a two-dimensional plane, we study the problem of finding a critical region-a part of the network that can be enclosed by a given elementary figure of predetermined size-whose destruction would lead to the highest network disruption. We determine that only a polynomial, in the input, number of nontrivial positions for such a figure needs to be considered and propose a corresponding polynomial-time algorithm. In addition, we consider region-aware network augmentation to decrease the impact of a regional failure. We subsequently address the region-disjoint paths problem, which asks for two paths with minimum total weight between a source (s) and a destination (d) that cannot both be cut by a single regional failure of diameter D (unless that failure includes s or d). We prove that deciding whether region-disjoint paths exist is NP-hard and propose a heuristic region-disjoint paths algorithm.

It is important that our vital networks (e.g., infrastructures) are robust to more than single-link failures. Failures might for instance affect a part of the network that resides in a certain geographical region. In this paper, considering networks embedded in a two-dimensional plane, we study the problem of finding a critical region - that is, a part of the network that can be enclosed by a given elementary figure (a circle, ellipse, rectangle, square, or equilateral triangle) with a predetermined size - whose removal would lead to the highest network disruption. We determine that there is a polynomial number of non-trivial positions for such a figure that need to be considered and, subsequently, we propose a polynomial-time algorithm for the problem. Simulations on realistic networks illustrate that different figures with equal area result in different critical regions in a network.

Mean-field deterministic epidemic models have been successful in uncovering several important dynamic properties of stochastic epidemic spreading processes over complex networks. In particular, individual-based epidemic models isolate the impact of the network topology on spreading dynamics. In this paper, the existing models are generalized to develop a class of models that includes the spreading process in multilayer complex networks. We provide a detailed description of the stochastic process at the agent level where the agents interact through different layers, each represented by a graph. The set of differential equations that describes the time evolution of the state occupancy probabilities has an exponentially growing state-space size in terms of the number of the agents. Based on a mean-field type approximation, we developed a set of nonlinear differential equations that has linearly growing state-space size. We find that the latter system, referred to as the generalized epidemic mean-field (GEMF) model, has a simple structure characterized by the elements of the adjacency matrices of the network layers and the Laplacian matrices of the transition rate graphs. Finally, we present several examples of epidemic models, including spreading of virus and information in computer networks and spreading of multiple pathogens in a host population .

We develop a performance model for the availability of a MobileTV service in a caching hierarchy network. The probability that bandwidth for the service is available is calculated as a function of channel popularity, the number of available channels, cache sizes, network configuration, and content viewing behavior. The system performance and the key factors that affect the performance are analyzed.

The Reddit score reflects a common appraisal by a community of Reddit subscribers of a submitted item, called a story. The general random walk with random maximum boundary is demonstrated to describe the distribution function of the Reddit score of an arbitrary story in the online social news aggregator Reddit.com. Exponential tails, predicted by the analysis, are observed, while a curious intermediate “power law-like” region seems to correspond to a remarkable empirical observation that the total number of downvotes depends in “power law” fashion on the total number of upvotes. Stronger even, those downvotes increase faster than the upvotes, which is a surprising fact that asks for a (socio-psychological?) explanation.

The rise of social media aggregating websites provides platforms where users can actively publish, evaluate, and disseminate content in a collaborative way. In this paper, we present a large-scale empirical study about “Digg.com”, one of the biggest social media aggregating websites. Our analysis is based on crawls of 1.5 million users and 10 million published stories on Digg. We study the distinct network structure, the collaborative user characteristics, and the content dissemination process on Digg. We empirically illustrate that friendship relations are used effectively in disseminating half of the content, although there exists a high overlap between the interests of friends. A successful content dissemination process can also be performed by random users who are browsing and digging stories. Since 88% of the published content on Digg is defined as news, it is important for the content to obtain sufficient votes in a short period of time before becoming obsolete. Finally, we show that the synchronization of users' activities in time is the key to a successful content dissemination process. The dynamics between users' voting activities consequently decrease the efficiency of friendship relations during content dissemination. The results presented in this paper define basic observations and measurements to understand the underlying mechanism of disseminating content in current online social news aggregators. These findings are helpful to understand the influence of service interfaces and user behaviors on content dissemination.

Physical impairments, such as noise and signal distortions, negatively affect the quality of information transfer in optical networks. The effect of physical impairments predominantly augments with distance and bit rate of the signal to the point that it becomes detrimental to the information transfer. To reverse the effect of physical impairments, the signal needs to be regenerated at nodes that have regeneration capabilities. Regenerators are costly and are, therefore, usually only sparsely placed in the network, in which case it is referred to as a translucent network. This paper deals with two problems in translucent networks, namely: (1) how to incorporate impairment awareness in the routing algorithms, and (2) how many regenerators to place inside the network and where. We propose exact and heuristic algorithms for impairment-aware path selection and, through simulations, show that our heuristic TIARA is computationally efficient and performs very close to our exact algorithm EIARA. Subsequently, we propose a greedy algorithm for placing regenerators that, contrary to previous proposals, is suitable for multiple impairment metrics, has polynomial complexity for a single impairment metric, and is cheaper in terms of the number of regenerators needed.

Security breaches and attacks are critical problems in today's networking. A key-point is that the security of each host depends not only on the protection strategies it chooses to adopt but also on those chosen by other hosts in the network. The spread of Internet worms and viruses is only one example. This class of problems has two aspects. First, it deals with epidemic processes, and as such calls for the employment of epidemic theory. Second, the distributed and autonomous nature of decision-making in major classes of networks (e.g., P2P, ad- hoc, and most notably the Internet) call for the employment of game theoretical approaches. Accordingly, we propose a unified framework that combines the N-intertwined, SIS epidemic model with a noncooperative game model. We determine the existence of a Nash equilibrium of the respective game and characterize its properties. We show that its quality, in terms of overall network security, largely depends on the underlying topology. We then provide a bound on the level of system inefficiency due to the noncooperative behavior, namely, the "price of anarchy" of the game. We observe that the price of anarchy may be prohibitively high, hence we propose a scheme for steering users towards socially efficient behavior.

Recently, there has been a growing interest in academic and commercial environments for video-on-demand (VoD) using peer-to-peer (P2P) technology. Unlike centralized solutions for VoD services, P2P technology lets the clients distribute video content among themselves. In this paper,we propose an analytical model for P2PVoD and we compare that model to a realistic P2PVoD simulator. With our model, parameters that affect the system performance can be observed, and the system stability can be investigated. Our model leads to design rules for achieving a good and stable system performance. This work is, to our knowledge,the first analytical work to model mesh-based P2PVoD.

We analyze the performance of searching with multiple random walk queries on Erdos-Renyi (ER) random graphs and power law graphs generated using preferential attachment. Our simulations show that searching with multiple random walk queries reduces message overhead as compared to flooding with sequence numbers. Moreover, the performance of searching by using multiple random walk queries is better in ER random graphs than in power law graphs grown by preferential attachment rule.

Abstract — Trade-off curves for the exact and the relaxed QoS routing problem are presented and discussed. In addition, an efficient parametric linear programming algorithm to compute the trade-off curve of the relaxed problem is given. Trade-off curves enable a network operator to choose the set of constraints according to its QoS portfolio and are useful in the design of the network. In particular, the trade-off curves represent for the operator’s network the possible basic feasible solutions that can be computed rapidly. In some sense, we reverse the QoS routing problem by giving the network operator the means to advertise an appropriate set of QoS constraints for its network. Instead of offering the user the freedom to require desirable endto-end QoS levels from the operator, the user now can choose from the advertised QoS constraints portfolio those that best fit his application. The trade-off curve of the approximate, relaxed problem also gives insight in the computational complexity of QoS routing. I.

Personal networks (PNs) are future communication systems that combine wireless and infrastructure based networks to provide users a variety of services anywhere and anytime. PNs introduce new design challenges due to the heterogeneity of the involved technologies, the need for self-organization, the dynamics of the PN composition, the application-driven nature, the co-operation with infrastructure-based networks, and the security hazards. This paper discusses the challenges of security, service discovery and QoS provisioning in designing self-organized PNs and combines them all into an integrated architectural framework

Dynamic networks appear in several contexts: QoS rout-ing faces the difficult problem of accurately and efficiently maintaining, distributing and updating network state infor-mation, and in wireless ad hoc networking, signal strength fluctuations complicate the choice of stable paths. In this paper we will focus on the stability of paths in a network with dynamically changing link weights. The level of path stability has a direct relation to the number of updates that are necessary to maintain an accurate view of the network state. If a small change in the network state does not affect the shortest path, then such a change need not be distrib-uted throughout the network. We evaluate path stability by adding noise and observing the change in paths.

Application Layer (AL) multicast emerged as a response to a slow deployment of IP multicast. However, the gain of AL multicast over unicast is questionable. Here, we investigate the efficiency of the two prominent protocols, MCAN and Scribe, in terms of the number of hops. We compare the efficiency of these algorithms to the efficiency of unicast and IP multicast via extensive simulations, as well as via measurements on the PlanetLab network. We introduce modifications to the MCAN algorithm that lead to a reduction in the hopcount. Finally, we demonstrate that the topology unawareness under certain conditions can make these schemes less efficient than unicast.

The increasing importance of large networks in our "linked" world necessitates to enhance out understanding of their most characteristic behaviors. We discuss how to describe large networks and argue that a stochastic approach is most appropriate. The "robustness" of large networks is not uniquely defined. The robustness is approached from two angles: we are studying the influence of the topology and of the link weight structure on the network's robustness.

The log-normal shadowing radio model has frequently been used to model radio propagation conditions. There exist accurate calculation methods for estimation of interference power sum statistics in fixed-topology wireless networks based on this radio model. Here we publish essential additions to these estimation methods to expand their use to sensor networks and ad-hoc networks with changing topology. To our best knowledge this has not been done before. Taking into account radio propagation conditions, density of nodes, size of the network, traffic load per node and MAC protocol characteristics, we present a calculation method for the estimation of interference power sum statistics in wireless ad-hoc and sensor networks. The accuracy of the calculation method is verified by simulations. We highlight the influence of MAC protocols on interference and show that an increase in network size or in node density does not necessarily lead into higher interference values. Our results can be deployed to estimate the network capacity.

Finding a path in a network based on multiple constraints (the MCP problem) is often considered an integral part of quality of service (QoS) routing. QoS routing with constraints on multiple additive measures has been proven to be NP-complete. This proof has dramatically influenced the research community, resulting into the common belief that exact QoS routing is intractable in practice. However, to our knowledge, no one has ever examined which "worst cases" lead to intractability. In fact, the MCP problem is not strong NP-complete, suggesting that in practice an exact QoS routing algorithm may work in polynomial time. The goal of this paper is to argue that in practice QoS routing may be tractable. We will provide properties, an approximate analysis, and simulation results to indicate that NP-completeness hinges on four conditions, namely: 1) the topology; 2) the granularity of link weights; 3) the correlation between link weights; and 4) the constraints. We expect that, in practice, these conditions are manageable and therefore believe that exact QoS routing is tractable in practice.

The underlying concepts of an exact QoS routing algorithm are explained. We show that these four concepts, namely 1) nonlinear definition of the path length; 2) a /spl kappa/-shortest path approach; 3) nondominance; and 4) look-ahead, are fundamental building blocks of a multiconstrained routing algorithm. The main reasons to consider exact multiconstrained routing algorithms are as follows. First, the NP-complete behavior seems only to occur in specially constructed graphs, which are unlikely to occur in realistic communication networks. Second, there exist exact algorithms that are equally complex as heuristics in algorithmic structure and in running time on topologies that do not induce NP-complete behavior. Third, by simply restricting the number /spl kappa/ of paths explored during the path computation, the computational complexity can be decreased at the expense of possibly loosing exactness. The presented four concepts are incorporated in SAMCRA, a self-adaptive multiple constraints routing algorithm.

Finding a path in a network based on multiple constraints (the MCP problem) is often referred to as QoS routing. QoS routing with constraints on multiple additive metrics has been proven to be NP-complete. This proof has dramatically influenced the research community, resulting in the common belief that exact QoS routing is intractable in practice. Hence, many heuristics for this problem were proposed, while hardly any exact algorithms. However, to our best knowledge, no one has ever examined which "worst-cases" cause NP-complete behavior. In fact, the MCP problem is not strong NP-complete, suggesting that in practice an exact QoS algorithm may work in polynomial time, making guaranteed QoS routing possible. The goal of this paper is to provide some properties and simulation results that indicate that NP-complete behavior hinges on a specific correlation structure between the link weights, which will be hardly ever encountered in practice.

Most of the currently deployed multicast protocols (e.g. DVMRP, PIM, MOSPF) build one shortest path multicast tree per sender, the tree being rooted at the sender's subnetwork. This paper examines the stability of such a tree, specifically, how the number of links change as the number of multicast users in a group changes. We make two modelling assumptions: (a) packets are delivered along the shortest path tree; (b) the m multicast group member nodes are chosen uniformly out of the total number of nodes N. The probability density function for the number of changed edges, /spl Delta//sub N/(m), when one multicast user joins or leaves the group is studied. For random graphs of the class G/sub p/(N) with N nodes, link density p and with uniformly (or exponentially) distributed link weights, the probability density function, Pr[/spl Delta//sub N/(m)=k], is proved to tend to a Poisson distribution for large N. The proof of this theorem enables a generalization to an arbitrary topology. Simulations, mainly conducted to quantify the validity of the asymptotic regime, reveal that the Poisson law seems more widely valid than just in the asymptotic regime where N/spl rarr//spl infin/. In addition, the effect of the link weight distribution on the stability of the multicast tree is investigated. Finally, via simulations, the stability of a Steiner tree connecting m multicast users is compared to the shortest path tree.

The average number of joint hops in a shortest-path multicast tree from a root to m arbitrary chosen group member nodes is studied. A general theory for all graphs, hence including the graph representation of the Internet, is presented which quantifies the multicast reduction in network links compared to m times unicast. For two special types of graphs, the random graph G/sub p/(N) and the k-ary tree, exact and asymptotic results are derived. Comparing these explicit results with previously published Internet measurements indicates that the number of routers in the Internet that can be reached from a root grows exponentially in the number of hops with an effective degree of approximately 3.2.

Design issues for an integrated routing architecture for IP and ATM are outlined. Two separate aspects of this integration are: (1) a common routing architecture for IP and ATM (layer integration) and (2) integrating best-effort (BE) and QoS routing architecture (service integration). Whereas the first level of integration is highly recommended, we show that the second level of integration is not desirable because BE and QoS traffic have, in terms of routing, contradictory requirements. Four criteria are proposed, namely, route refreshing vs. route pinning, hop by hop vs. explicit routing, pre-computed routes vs. on-demand route computation and stable vs resource related metrics. A fifth alternative is whether or not to integrate in the routing architecture the capability to compute shortcut paths, that are bypassing layer 3 (L3) nodes and using only layer 2 (L2) devices. Using this framework, we conclude that BE traffic flows are well served by a combination of route refreshing, hop by hop routing pre-computed routes and static routing metrics while QoS routing is built on route pinning, explicit routing, on-demand route computation and resource related metrics. Finally, the ability to compute L2 shortcuts in an L2/L3 integrated routing architecture is an added value simplifying the overall network design and optimising the efficacy of the forwarding path.

The throughput optimality of priority management strategies in a single buffer has been studied for a general aggregate arrival law. The tight upper bounds found are useful to understand optimality in utilization of specific priority schemes such as push-out buffer (POB) and partial buffer sharing (PBS). This paper further focuses on the maximum allowable load /spl rho//sub max/ versus the priority mix /spl alpha/ for a PBS and a random push-out buffer (R POB) of size K for a wide variety of arrival processes. The role of priorities in a special type of bursty arrivals, the compound Poisson process with constant burst length and random priority assignment within the burst, is found to be less pronounced than that of 'pure' Poisson arrivals. On the other hand, the results for on-off cell arrivals modeled by a MMPP(2), MMPP(3), and higher order Markov modulated processes closely follow the behaviour of the maximum allowable load in the R POB with Poisson arrivals, however scaled to lower loads. The results indicate that the priority mix distribution within the aggregate arrival flow influences the shape of /spl rho//sub max/(/spl alpha/)-curve more than the aggregate arrival distribution itself.