SkyEye: A tree-based peer-to-peer monitoring approach

Peer-to-Peer overlays, used by applications like distributed online social networks, need the ability to adjust their system parameters and thus the system performance to provide a certain level of quality, i.e. to ensure maximum response times. For the control of p2p network, a reliable information basis about the system’s state is essential, i.e. what the current average response time is. A precise and rapidly adapting monitoring mechanism can provide the desired knowledge. In this paper we propose SkyEye, a tree-based monitoring approach which operates on top of an existing structured p2p overlay. It provides through a lightweight, error-prone protocol a continuous monitoring of all peers in the network. It gathers and disseminates sophisticated statistics on a wide range of metrics from all peers, to all peers. Evaluation shows a superior precision and adapting rate compared to an implementation of the gossip-based push-sum algorithm in scenarios with churn and without churn.     

A novel robust on-line protocol for load-balancing in structured peer-to-peer systems

In this paper, we revisit the problem of load-balancing structured peer-to-peer systems with on-line protocols. Load-balancing is of major significance for large-scale decentralized networks in terms of enhanced scalability and performance. The main incentives behind balancing schemes are under-utilization of bandwidth and computer resources. Therefore, our methods focus mainly on task-skew. Specifically, we address the problem with on-line protocols on the basis of migration and enhanced availability. In particular, the cornerstones of our methods are the notions of virtual nodes, replication and Multiple realities, combined altogether with allocation techniques based on balls-in-bins games. The rationale of our dynamic protocol to depend exclusively on peer load distribution preserves intact the structural properties and search efficiency of the overlay used as an indexing infrastructure, while preserving the semantic information of the data (e.g., range partitioned network). We also propose an effective load-aware mechanism to facilitate robust operations that counteract against contingent churn failures. Finally, our work is complemented with extensive experiments using both real and synthetic data sets.     

MobiStore: A system for efficient mobile P2P data sharing

MobiStore is a P2P data store for decentralized mobile computing, designed to achieve high availability and load balance. As P2P platforms, mobile devices connected to the Internet through WiFi or cellular networks are different from wired devices in two main aspects: (1) higher churn due to mobility, weak wireless signals, or battery constraints, and (2) significant variability in bandwidth and latency based on the point of attachment. These problems affect the stored content availability and skew the content serving load over the peers. MobiStore structures the mobile P2P network into clusters of redundant peers. The topology uses both algorithmically-defined and random edges among the peers of different clusters. The routing information is updated using a gossip-based protocol. Thus, MobiStore achieves, with high probability, O(1) lookup operations despite high churn and link variability. Inside the clusters, all peers replicate the content, which improves the content availability. Furthermore, based on the current load, MobiStore dynamically changes the number of peers inside the clusters and routes content request to randomly selected peers. These two dynamic techniques along with using consistent hashing to map content to peers balance the load over the peers. While some of these techniques are well known, the main contribution is on the novel ways of applying them to design and implement an efficient mobile P2P data store. Simulation results show MobiStore achieves an availability, i.e., lookup success rate, between 12–48 % higher than two baseline systems built over the MR-Chord and Chord P2P protocols; and it reduces the latency up to 9 times compared to these protocols. Finally, the results show MobiStore adapts to churn and workload to evenly distribute the requests across clusters and peers better than both baseline solutions.     

A quorum-based protocol for searching objects in peer-to-peer networks

Peer-to-peer (P2P) system is an overlay network of peer computers without centralized servers, and many applications have been developed for such networks such as file sharing systems. Because a set of peers dynamically changes, design and verification of efficient protocols is a challenging task. In this paper, we consider an object searching problem under a resource model such that there are some replicas in a system and the lower bound of the ratio /spl rho/=n'/n is known in advance, where n' is a lower bound of the number of peers that hold original or replica for any object type and n is the total number of peers. In addition, we consider object searching with probabilistic success, i.e., for each object search, object must be found with at least probability 0相似文献   

Delay Management in Mesh-Based P2P Live Streaming Using a Three-Stage Peer Selection Strategy

Peer-to-peer (P2P) live streaming systems have gained popularity due to the self-scalability property of the P2P overlay networks. In P2P live streaming, peers retrieve stream content from other peers in the system. Therefore, peer selection strategy is a fundamental element to build an overlay which manages the playback delay and startup delay experienced by the peers. In this paper, we propose a peer selection strategy which manages to build a minimum delay overlay using three different stages of overlay construction. In the first stage, the tracker suggests some peers as prospective partners to a new peer. In the second stage, the peer selects its partners out of these peers such that delay is minimized. The third stage is the topology adaptation phase of peers, where peers reposition themselves in the overlay to maintain minimum delay during peer churn. In the proposed peer selection strategy, peers are selected in all the stages based on parameters such as propagation delay, upload capacity, buffering duration and buffering level. The proposed strategy is compared with two existing strategies in the literature: Fast-Mesh (Ren et al. in IEEE Trans Multimed 11: 1446, 2009) and Hybrid live p2p streaming protocol (Hammami et al., 2014) using simulations. Our results show that playback delay and startup delay are reduced significantly with the help of proposed strategy. We demonstrate that the stability of the system also improves during peer churn.     

DHT协议设计选项与抖动问题关联分析

因节点加入和离开引起的抖动是增加结构化P2P网络路由表更新代价的主要原因。为了找出影响网络抖动的关键因素,分析了影响抖动的路由方式、邻居选择、节点加入和节点离开以及并行查找等策略因素,发现任意两种DHT网络分别采用的五种策略都至少有两种不同,对两种DHT网络直接进行比较就很难确定哪些策略能更有效地降低抖动。因此,提出在同一网络内用不同的单个策略对网络抖动进行比较和分析的方法,称之为CSP。通过对现有DHT算法进行改进,使用CSP方法对不同的单个策略进行比较,得出以下结论:迭代路由、快速加入和周期性恢复策略和有效的邻居选择算法能更有效地降低网络的抖动。     

Building a peer-to-peer content distribution network with high performance,scalability and robustness

Content distribution networks (CDN) are fundamental, yet expensive technologies for distributing the content of web-servers to large audiences. The P2P model is a perfect match to build a low-cost and scalable CDN infrastructure for popular websites by exploiting the underutilized resources of their user communities. However, building a P2P-based CDN is not a straightforward endeavor. In contrast to traditional CDNs, peers are autonomous and volunteer participants with their own heterogeneous interests that should be taken into account in the design of the P2P system. Moreover, churn rate is much higher than in dedicated CDN infrastructures, which can easily destabilize the system and severely degrade the performance. Finally and foremostly, while many P2P systems abstract any topological information about the underlying network, a top priority of a CDN is to incorporate locality-awareness in query routing in order to locate close-by content. This paper aims at building a P2P CDN with high performance, scalability and robustness. Our proposed protocols combine DHT efficiency with gossip robustness and take into account the interests and localities of peers. In short, Flower-CDN provides a hybrid and locality-aware routing infrastructure for user queries. PetalUp-CDN is a highly scalable version of Flower-CDN that dynamically adapts to variable rates of participation and prevent overload situations. In addition, we ensure the robustness of our P2P CDN via low-cost maintenance protocols that can detect and recover from churn and dynamicity. Our extensive performance evaluation shows that our protocols yield high performance gains under both static and highly dynamic environments. Furthermore, they incur acceptable and tunable overhead. Finally we provide main guidelines to deploy Flower-CDN for the public use.     

结构化P2P系统中副本一致性管理的一种新算法

结构化P2P系统通常使用数据复制来提高数据可用性,但P2P环境中的节点搅动、多节点并发更新以及恶意节点的存在也为副本的一致性管理带来了新的挑战.基于协商的算法要求节点间以全交换的方式通讯,在P2P环境中其可伸缩性不够理想.本文针对结构化P2P系统提出一种基于Quorum的副本管理算法:使用混合失效模型降低容错开销,利用DHT服务处理节点搅动,将数据存储与其元信息管理分离,使数据可靠性和数据可用性得以独立调整.模拟实验表明该算法可以明显改善系统的可伸缩性,减少系统的容错开销.     

Proactive replication for rare objects in unstructured peer-to-peer networks

Unstructured peer-to-peer (P2P) networks have become a very popular architecture for content distribution in large-scale and dynamic environments. The search efficiency problem in unstructured P2P networks has not been adequately addressed so far, especially concerning search for rare objects. In this paper, we propose a proactive replication strategy to improve search efficiency for rare objects. It uses an object-probing technique for peers to decide whether or not to establish replications for their objects when they join the network. This strategy can effectively increase the popularity of rare objects in order to enhance search efficiency. We also present a rare object search algorithm to reduce the overhead caused by the replication strategy. When a peer forwards a search request, the forward probability is calculated according to its neighbors' degrees and the number of neighbors' objects. Therefore, the search request is forwarded to the peers more likely containing target objects. Simulations show that our proactive replication strategy greatly improves search efficiency for rare objects with moderate communication overhead. The rare object search algorithm not only improves search efficiency for rare objects, but also achieves load balance in search.     

Virtual Tree: A robust architecture for interval valid queries in dynamic distributed systems

This paper studies the problem of answering aggregation queries, satisfying the interval validity semantics, in a distributed system prone to continuous arrival and departure of participants. The interval validity semantics states that the query answer must be calculated considering contributions of at least all processes that remained in the distributed system for the whole query duration. Satisfying this semantics in systems experiencing unbounded churn is impossible due to the lack of connectivity and path stability between processes. This paper presents a novel architecture, namely Virtual Tree, for building and maintaining a structured overlay network with guaranteed connectivity and path stability in settings characterized by bounded churn rate. The architecture includes a simple query answering algorithm that provides interval valid answers. The overlay network generated by the Virtual Tree architecture is a tree-shaped topology with virtual nodes constituted by clusters of processes and virtual links constituted by multiple communication links connecting processes located in adjacent virtual nodes. We formally prove a bound on the churn rate for interval valid queries in a distributed system where communication latencies are bounded by a constant unknown by processes. Finally, we carry out an extensive experimental evaluation that shows the degree of robustness of the overlay network generated by the virtual tree architecture under different churn rates.     

Fuzzynet: Ringless routing in a ring-like structured overlay

Many structured overlay networks rely on a ring invariant as a core network connectivity element. The responsibility ranges of the participating peers and navigability principles (greedy routing) heavily depend on the ring structure. For correctness guarantees, each node needs to eagerly maintain its immediate neighboring links - the ring invariant. However, the ring maintenance is an expensive task and it may not even be possible to maintain the ring invariant continuously under high churn, particularly as the network size grows. Furthermore, routing anomalies in the network, peers behind firewalls and Network Address Translators (NATs) create non-transitivity effects, which inevitably lead to the violation of the ring invariant. We argue that reliance on the ring structure is a serious impediment for real life deployment and scalability of structured overlays. In this paper we propose an overlay called Fuzzynet, which does not rely on the ring invariant, yet has all the functionalities of structured overlays. Fuzzynet takes the idea of lazy overlay maintenance further by dropping any explicit connectivity and data maintenance requirement, relying merely on the actions performed when new Fuzzynet peers join the network. We show that with sufficient amount of neighbors (O(log N), comparable to traditional structured over-lays), even under high churn, data can be retrieved in Fuzzynet w.h.p. We validate our novel design principles by simulations as well as PlanetLab experiments and compare them with ring based overlays.     

Topological Implications of Selfish Neighbor Selection in Unstructured Peer-to-Peer Networks

Current peer-to-peer (P2P) systems often suffer from a large fraction of freeriders not contributing any resources to the network. Various mechanisms have been designed to overcome this problem. However, the selfish behavior of peers has aspects which go beyond resource sharing. This paper studies the effects on the topology of a P2P network if peers selfishly select the peers to connect to. In our model, a peer exploits locality properties in order to minimize the latency (or response times) of its lookup operations. At the same time, the peer aims at not having to maintain links to too many other peers in the system. By giving tight bounds on the price of anarchy, we show that the resulting topologies can be much worse than if peers collaborated. Moreover, the network may never stabilize, even in the absence of churn. Finally, we establish the complexity of Nash equilibria in our game theoretic model of P2P networks. Specifically, we prove that it is NP-hard to decide whether our game has a Nash equilibrium and can stabilize.     

Performance evaluation of a Kademlia-based communication-oriented P2P system under churn

The phenomenon of churn has a significant effect on the performance of Peer-to-Peer (P2P) networks, especially in mobile environments that are characterized by intermittent connections and unguaranteed network bandwidths. A number of proposals have been put forward to deal with this problem; however, we have so far not seen any thorough analysis to guide the optimal design choices and parameter configurations for structured P2P networks. In this article, we present a performance evaluation of a structured communication-oriented P2P system in the presence of churn. The evaluation is conducted using both simulation models and a real-life prototype implementation. In both evaluation environments, we utilize Kademlia with some modifications as the underlying distributed hash table (DHT) algorithm, and Peer-to-Peer Protocol (P2PP) as the signaling protocol. The results from the simulation models created using Nethawk EAST (a telecommunication simulator software) suggest that, in most situations, a lookup parallelism degree of 3 and resource replication degree of 3 are enough for guaranteeing a high resource lookup success ratio. We also notice that, with the parallel lookup mechanism, a good success ratio is achieved even without the KeepAlive traffic that is used for detecting the aliveness of nodes. A prototype system that works in mobile environment is implemented to evaluate the feasibility of mobile nodes acting as full-fledged peers. The measurements made using the prototype show that, from the viewpoints of CPU load and network traffic load, it is feasible for the mobile nodes to take part in the overlay. Through energy consumption measurements, we draw the conclusion that in general the UMTS access mode consumes slightly more power than the WLAN access mode. Protocol packets with sizes of 200 bytes or less are observed to be the most energy efficient in the UMTS access mode.     

Distributed processing of continuous sliding-window k-NN queries for data stream filtering

A sliding-window k-NN query (k-NN/w query) continuously monitors incoming data stream objects within a sliding window to identify k closest objects to a query. It enables effective filtering of data objects streaming in at high rates from potentially distributed sources, and offers means to control the rate of object insertions into result streams. Therefore k-NN/w processing systems may be regarded as one of the prospective solutions for the information overload problem in applications that require processing of structured data in real-time, such as the Sensor Web. Existing k-NN/w processing systems are mainly centralized and cannot cope with multiple data streams, where data sources are scattered over the Internet. In this paper, we propose a solution for distributed continuous k-NN/w processing of structured data from distributed streams. We define a k-NN/w processing model for such setting, and design a distributed k-NN/w processing system on top of the Content-Addressable Network (CAN) overlay. An extensive evaluation using both real and synthetic data sets demonstrates the feasibility of the proposed solution because it balances the load among the peers, while the messaging overhead within the P2P network remains reasonable. Moreover, our results clearly show the solution is scalable for an increasing number of queries and peers.     

Chams: Churn-aware overlay construction for media streaming

Overlay networks support a wide range of peer-to-peer media streaming applications on the Internet. The user experience of such applications is affected by the churn resilience of the system. When peers disconnect from the system, streamed data may be delayed or lost due to missing links in the overlay topology. In this paper, we explore a proactive strategy to create churn-aware overlay networks that reduce the potential of disruptions caused by churn events. We describe Chams, a middleware for constructing overlay networks that mitigates the impact of churn. Chams uses a ??hybrid?? approach??it implicitly defines an overlay topology using a gossip-style mechanism, while taking the reliability of peers into account. Unlike systems for overlay construction, Chams supports a variety of topologies used in media streaming systems, such as trees, multi-trees and forests. We evaluate Chams with different topologies and show that it reduces the impact of churn, while imposing only low computational and message overheads.     

P2P data replication and trustworthiness for a JXTA-Overlay P2P system using fuzzy logic

P2P systems are very important for future distributed systems and applications. In such systems, the computational burden of the system can be distributed to peer nodes of the system. Therefore, in decentralized systems users become themselves actors by sharing, contributing and controlling the resources of the system. This characteristic makes P2P systems very interesting for the development of decentralized applications. Data replication techniques are commonplace in P2P systems. Data replication means storing copies of the same data at multiple peers thus improving availability and scalability. The trustworthiness of peers also is very important for safe communication in P2P system. The trustworthiness of a peer can be evaluated based on the reputation and actual behaviour of peers to provide services to other peers. In this paper, we propose two fuzzy-based systems for data replication and peer trustworthiness for JXTA-Overlay P2P platform. The simulation results have shown that in the first system, replication factor increases proportionally with increase of number of documents per peer, replication percentage and scale of replication per peer parameters and the second system can be used successfully to select the most reliable peer candidate to execute the tasks.     

Dealing with network partitions in structured overlay networks

Structured overlay networks form a major class of peer-to-peer systems, which are touted for their abilities to scale, tolerate failures, and self-manage. Any long-lived Internet-scale distributed system is destined to face network partitions. Although the problem of network partitions and mergers is highly related to fault-tolerance and self-management in large-scale systems, it has hardly been studied in the context of structured peer-to-peer systems. These systems have mainly been studied under churn (frequent joins/failures), which as a side effect solves the problem of network partitions, as it is similar to massive node failures. Yet, the crucial aspect of network mergers has been ignored. In fact, it has been claimed that ring-based structured overlay networks, which constitute the majority of the structured overlays, are intrinsically ill-suited for merging rings. In this paper, we present an algorithm for merging multiple similar ring-based overlays when the underlying network merges. We examine the solution in dynamic conditions, showing how our solution is resilient to churn during the merger, something widely believed to be difficult or impossible. We evaluate the algorithm for various scenarios and show that even when falsely detecting a merger, the algorithm quickly terminates and does not clutter the network with many messages. The algorithm is flexible as the tradeoff between message complexity and time complexity can be adjusted by a parameter.     

Securing Passive Objects in Mobile Ad-Hoc Peer-to-Peer Networks

Security and privacy in mobile ad-hoc peer-to-peer environments are hard to attain, especially when working with passive objects (without own processing power, e.g. RFID tags). This paper introduces a method for integrating such objects into a peer-to-peer environment without infrastructure components while providing a high level of privacy and security for peers interacting with objects. The integration is done by associating public keys to passive objects, which can be used by peers to validate proxies (peers additionally acting on behalf of objects). To overcome the problem of limited storage capacity on small embedded objects, ECC keys are used.     

Node-Capability-Aware Replica Management for Peer-to-Peer Grids

Data objects have to be replicated in large-scale distributed systems for reasons of fault tolerance, availability, and performance. Furthermore, computations may have to be scheduled on these objects, when these objects are part of a grid computation. Although replication mechanism for unstructured peer-to-peer (P2P) systems can place replicas on capable nodes, they may not be able to provide deterministic guarantees on searching. Replication mechanisms in structured P2P systems provide deterministic guarantees on searching but do not address node capability in replica placement. We propose Virat, a node-capability-aware P2P middleware for managing replicas in large-scale distributed systems. Virat uses a unique two-layered architecture that builds a structured overlay over an unstructured P2P layer, combining the advantages of both structured and unstructured P2P systems. Detailed performance comparison is made with a replication mechanism realized over OpenDHT, a state-of-the-art structured P2P system. We show that the 99th percentile response time for Virat does not exceed 600 ms, whereas for OpenDHT, it goes beyond 2000 ms in our test bed, created specifically for the aforementioned comparison.     

An analytical study on optimizing the lookup performance of distributed hash table systems under churn

The phenomenon of system churn degrades the lookup performance of distributed hash table (DHT) systems greatly. To handle the churn, a number of approaches have been proposed to date. However, there is a lack of theoretical analysis to direct how to make design choices under different churn rates and how to configure their parameters optimally. In this paper, we analytically study three important aspects on optimizing DHT lookup performance under churn, i.e. lookup strategy, lookup parallelism and lookup key replication. Our objective is to build a theoretical basis for designers to make better design choices in the future. We first compare the performance of two representative lookup strategies—recursive routing and iterative routing—and explore the existence of better alternatives. Then we study the effectiveness of lookup parallelism in systems with different churn rates and show how to select the optimal degree of parallelism. Owing to the importance of key replication on lookup performance, we also analyze the reliability of the replicated key under two different replication policies, and show how to perform proper configuration. Besides the analytical study, our results are also validated by simulation, and Kad is taken as a case to show the meaningfulness of our analysis. Copyright © 2007 John Wiley & Sons, Ltd.