8744802
On static and dynamic partitioning behavior of large-scale networks
In this paper, we analyze the problem of network disconnection in the context of large-scale P2P networks and understand how both static and dynamic patterns of node failure affect the resilience of such graphs. We start by applying classical results from random graph theory to show that a large variety of deterministic and random P2P graphs almost surely (i.e., with probability 1-o(1)) remain connected under random failure if and only if they have no isolated nodes. This simple, yet powerful, result subsequently allows us to derive in closed-form the probability that a P2P network develops isolated nodes, and therefore partitions, under both types of node failure. We finish the paper by demonstrating that our models match simulations very well and that dynamic P2P systems are extremely resilient under node churn as long as the neighbor replacement delay is much smaller than the average user lifetime
47232248
Graph-theoretic analysis of structured peer-to-peer systems: routing distances and fault resilience
This paper examines graph-theoretic properties of existing peer-to-peer networks and proposes a new infrastructure based on optimal-diameter de Bruijn graphs. Since generalized de Bruijn graphs exhibit very short average distances and high resilience to node failure, they are well suited for distributed hash tables (DHTs). Using the example of Chord, CAN, and de Bruijn, we study the routing performance, graph expansion, clustering properties, and bisection width of each graph. Having confirmed that de Bruijn graphs offer the best diameter and highest connectivity among the existing peer-to-peer structures, we offer a very simple incremental building process that preserves optimal properties of de Bruijn graphs under uniform user joins/departures. We call the combined peer-to-peer architecture optimal diameter routing infrastructure.
3443754
Residual-Based Estimation of Peer and Link Lifetimes in P2P Networks
Existing methods of measuring lifetimes in P2P systems usually rely on the so-called Create-Based Method (CBM), which divides a given observation window into two halves and samples users ldquocreatedrdquo in the first half every Delta time units until they die or the observation period ends. Despite its frequent use, this approach has no rigorous accuracy or overhead analysis in the literature. To shed more light on its performance, we first derive a model for CBM and show that small window size or large Delta may lead to highly inaccurate lifetime distributions. We then show that create-based sampling exhibits an inherent tradeoff between overhead and accuracy, which does not allow any fundamental improvement to the method. Instead, we propose a completely different approach for sampling user dynamics that keeps track of only residual lifetimes of peers and uses a simple renewal-process model to recover the actual lifetimes from the observed residuals. Our analysis indicates that for reasonably large systems, the proposed method can reduce bandwidth consumption by several orders of magnitude compared to prior approaches while simultaneously achieving higher accuracy. We finish the paper by implementing a two-tier Gnutella network crawler equipped with the proposed sampling method and obtain the distribution of ultrapeer lifetimes in a network of 6.4 million users and 60 million links. Our experimental results show that ultrapeer lifetimes are Pareto with shape alpha ap 1.1; however, link lifetimes exhibit much lighter tails with alpha ap 1.8.
3404450
Modeling the Evolution of Degree Correlation in Scale-Free Topology Generators
In this paper, we examine the asymptotic behavior of degree correlation (i.e., the joint degree distribution of adjacent nodes) in several scale-free topology generators GED [13], PLRG [1], GLP [10], BA [3], AB [2]. We present a unifying analytical framework that allows tractable analysis of degree correlation in all studied models and derive asymptotic formulas of two degree correlation metrics - assortativity and clustering. Our results indicate that all studied generators become uncorrelated as graph size increases, which is inconsistent with time-invariance of these metrics in real networks such as the Internet [36], [48], [50]. Since the class of degree-based generators is incapable of reproducing evolving characteristics of the Internet, we study three other models that evolve graphs using different rules than preference of degree (e.g., based on random walks [50], optimization [17], and geometry [23]) and show using simulations that these models are much more viable alternatives for replicating the complex structure of Internet-like graphs.
1669034
Modeling Heterogeneous User Churn and Local Resilience of Unstructured P2P Networks
Previous analytical results on the resilience of unstructured P2P systems have not explicitly modeled heterogeneity of user churn (i.e., difference in online behavior) or the impact of in-degree on system resilience. To overcome these limitations, we introduce a generic model of heterogeneous user churn, derive the distribution of the various metrics observed in prior experimental studies (e.g., lifetime distribution of joining users, joint distribution of session time of alive peers, and residual lifetime of a randomly selected user), derive several closed-form results on the transient behavior of in-degree, and eventually obtain the joint in/out degree isolation probability as a simple extension of the out-degree model.
3433910
Residual-Based Measurement of Peer and Link Lifetimes in Gnutella Networks
Existing methods of measuring lifetimes in P2P systems usually rely on the so-called create-based method (CBM), which divides a given observation window into two halves and samples users "created" in the first half every Delta time units until they die or the observation period ends. Despite its frequent use, this approach has no rigorous accuracy or overhead analysis in the literature. To shed more light on its performance, we flrst derive a model for CBM and show that small window size or large Delta may lead to highly inaccurate lifetime distributions. We then show that create-based sampling exhibits an inherent tradeoff between overhead and accuracy, which does not allow any fundamental improvement to the method. Instead, we propose a completely different approach for sampling user dynamics that keeps track of only residual lifetimes of peers and uses a simple renewal-process model to recover the actual lifetimes from the observed residuals. Our analysis indicates that for reasonably large systems, the proposed method can reduce bandwidth consumption by several orders of magnitude compared to prior approaches while simultaneously achieving higher accuracy. We finish the paper by implementing a two-tier Gnutella network crawler equipped with the proposed sampling method and obtain the distribution of ultrapeer lifetimes in a network of 6.4 million users and 60 million links. Our experimental results show that ultrapeer lifetimes are Pareto with shape a alpha ap 1.1; however, link lifetimes exhibit much lighter tails with alpha ap 1.9.
120708868
An energy equation for the weakly damped driven nonlinear Schro¨dinger equations and its application to their attractors
Abstract In this note we present an energy equation concerning the H 2 norm of a forced one-dimensional nonlinear Schrodinger equation. As an application we are able to corroborate recent results on attractors of weakly damped forced nonlinear Schrodinger equation, by proving that the attractor is an attractor in the strong topology of H 2 and its Hausdorff and fractal dimensions are finite in H 2 . The energy equation for the H 1 norm can be derived in the same fashion and it implies corresponding results for the attractor in H 1 .
122609601
Attractor dimension estimates for two-dimensional shear flows
Abstract We study the large time behavior of boundary and pressure-gradient driven incompressible fluid flows in elongated two-dimensional channels with emphasis on estimates for their degrees of freedom, i.e., the dimension of the attractor for the solutions of the Navier-Stokes equations. For boundary driven shear flows and flux driven channel flows we present upper bounds for the degrees of freedom of the form cα Re 3 2 where c is a universal constant, α denotes the aspect ratio of the channel (length/width), and Re is the Reynolds number based on the channel width and the imposed “outer” velocity scale. For fixed pressure gradient driven channel flows we obtain an upper bound of form c'α Re2, where c' is another universal positive constant and the Reynolds number is based on a velocity defined by the infimum, over all possible trajectories, of the time averaged mass flux per unit channel width. We discuss these results in terms of physical arguments based on small length scales in turbulent flows.
122233992
Effect of tangential derivative in the boundary layer on time averaged energy dissipation rate
Abstract We show that for shear driven flows the energy dissipation rate per unit volume is dominated by a function of the energy dissipation rate in the boundary layer due to the tangential derivatives of the tangential velocities or the tangential derivatives of the normal velocity. Hence if the energy dissipation rate in a (thick enough) boundary layer due to the tangential derivatives of the tangential velocities or the tangential derivatives of the normal velocity is small, the energy dissipation rate per unit volume has to be small as well. This leads to a possible explanation of the sub-Kolmogorov bound to the energy dissipation rate per unit volume for shear driven flows observed in laboratory data. However, the smallness of these tangential derivatives in the boundary layer in the averaged sense still needs to be proved rigorously from the Navier–Stokes equations. We hope that our result will stimulate discussion on modeling, numerical simulation and laboratory experiment on these tangential derivatives in the boundary layer.
14457115
General Method to Build Deterministic Small-World Networks Based on Cayley Graph
Many real-life networks, such as the WWW, biological realms, and social networks are small-world networks. Most previous researches on small-world networks have been based on probabilistic methods. In this paper, we present a general method by using Cayley graph to build deterministic small-world networks. We also analyze the cluster topology of the Cayley graph with small world properties by constructing its left Coset graph. This method has great value in constructing interconnection networks model and analyzing many other real network models.
2311114
A Novel Privacy and Copyright Protection Enforced Peer-to-Peer Network
Peer-to-peer (P2P) networks are widely used to share copyrighted contents and software illegally around the world. Development and applications of P2P technologies have faced strong legal and legislative challenges. A P2P network has to have built-in copyright protection to enable P2P technologies to advance on its own without court's and legislature's interference. In this paper, we propose a novel and practical P2P network with a strong privacy protection and reliable tracking mechanism to track the original uploader of any material in the P2P network. When a pirated material is found, its uploader is tracked down, and can be punished by revoking the access to the network, removing his or her uploaded materials, etc. The whole protection system is completely transparent to end users. The proposed scheme would effectively deter users from uploading illegally any copyrighted materials to and dramatically reduce copyrighted materials shared through our P2P network.