Towards a Scalable and Robust DHT

The problem of scalable and robust distributed data storage has recently attracted a lot of attention. A common approach in the area of peer-to-peer systems has been to use a distributed hash table (or DHT). DHTs are based on the concept of virtual space. Peers and data items are mapped to points in that space, and local-control rules are used to decide, based on these virtual locations, how to interconnect the peers and how to map the data to the peers. DHTs are known to be highly scalable and easy to update as peers enter and leave the system. It is relatively easy to extend the DHT concept so that a constant fraction of faulty peers can be handled without any problems, but handling adversarial peers is very challenging. The biggest threats appear to be join-leave attacks (i.e., adaptive join-leave behavior by the adversarial peers) and attacks on the data management level (i.e., adaptive insert and lookup attacks by the adversarial peers) against which no provably robust mechanisms are known so far. Join-leave attacks, for example, may be used to isolate honest peers in the system, and attacks on the data management level may be used to create a high load-imbalance, seriously degrading the correctness and scalability of the system. We show, on a high level, that both of these threats can be handled in a scalable manner, even if a constant fraction of the peers in the system is adversarial, demonstrating that open systems for scalable distributed data storage that are robust against even massive adversarial behavior are feasible. Supported by NSF-ANIR 0240551, NSF-CCF 0515080, and NSF-CCR 0311795.     

SemreX: Efficient search in a semantic overlay for literature retrieval

The World Wide Web is growing at such a pace that even the biggest centralized search engines are able to index only a small part of the available documents on the Internet. The decentralized structure, together with the features of self-organization and fault-tolerance, makes peer-to-peer networking an effective information-sharing model; however, content searching still remains a serious challenge of large scale peer-to-peer networks. In this paper we present SemreX, a semantic overlay for desktop literature/ document retrieval in peer-to-peer networks. We present a semantic overlay algorithm by which semantically similar peers are locally clustered together, and long-range connections are rewired for a short-cut in peer-to-peer networks. Based on the semantic overlay, a heuristic query routing algorithm is proposed for efficient content searching. We conduct a comprehensive simulation to evaluate the search performance of our algorithms. Results show that search in our SemreX semantic overlay greatly improves search efficiency.     

Limited Scale-Free Overlay Topologies for Unstructured Peer-to-Peer Networks

In unstructured peer-to-peer (P2P) networks, the overlay topology (or connectivity graph) among peers is a crucial component in addition to the peer/data organization and search. Topological characteristics have profound impact on the efficiency of a search on such unstructured P2P networks, as well as other networks. A key limitation of scale-free (power-law) topologies is the high load (i.e., high degree) on a very few number of hub nodes. In a typical unstructured P2P network, peers are not willing to maintain high degrees/loads as they may not want to store a large number of entries for construction of the overlay topology. Therefore, to achieve fairness and practicality among all peers, hard cutoffs on the number of entries are imposed by the individual peers, which limits scale-freeness of the overall topology, hence limited scale-free networks. Thus, it is expected that the efficiency of the flooding search reduces as the size of the hard cutoff does. We investigate the construction of scale-free topologies with hard cutoffs (i.e., there are not any major hubs) and the effect of these hard cutoffs on the search efficiency. Interestingly, we observe that the efficiency of normalized flooding and random walk search algorithms increases as the hard cutoff decreases.     

A dynamic coalition formation game for search efficient adaptive overlay construction in unstructured peer-to-peer networks

A great number of recent works deal with improving search in peer-to-peer systems, specifically by clustering peers into semantic groups. When the process of clustering is predetermined and static, it suffers from lack of adaptation to highly dynamic peer-to-peer environments. We model the problem as a non-superadditive coalition game with non-transferable utility characteristic function, and propose a distributed dynamic coalition formation algorithm through myopic best-reply with experiment rule to solve the coalition formation problem. Coalitions are formed by peers with similar interests considering geographical proximity. The overlay network is dynamically reconfigured over time based on the changes in the interests or locations of the individual peers. The convergence of the proposed algorithm using “core solution” concept is studied. The simulation results show that the proposed algorithm can efficiently reduce the search time, although the overhead of the overlay adaptation is slightly higher.     

T-Man: Gossip-based fast overlay topology construction

Large-scale overlay networks have become crucial ingredients of fully-decentralized applications and peer-to-peer systems. Depending on the task at hand, overlay networks are organized into different topologies, such as rings, trees, semantic and geographic proximity networks. We argue that the central role overlay networks play in decentralized application development requires a more systematic study and effort towards understanding the possibilities and limits of overlay network construction in its generality. Our contribution in this paper is a gossip protocol called T-Man that can build a wide range of overlay networks from scratch, relying only on minimal assumptions. The protocol is fast, robust, and very simple. It is also highly configurable as the desired topology itself is a parameter in the form of a ranking method that orders nodes according to preference for a base node to select them as neighbors. The paper presents extensive empirical analysis of the protocol along with theoretical analysis of certain aspects of its behavior. We also describe a practical application of T-Man for building Chord distributed hash table overlays efficiently from scratch.     

Building scalable and robust peer-to-peer overlay networks for broadcasting using network coding

We propose a scheme for building peer-to-peer overlay networks for broadcasting using network coding. The scheme addresses many practical issues such as scalability, robustness, constraints on bandwidth, and locality of decisions. We analyze the system theoretically and prove near optimal bounds on the parameters defining robustness and scalability. As a result we show that the effects of failures are contained locally, allowing the network to grow exponentially with server load. We also argue that adversarial failures are no more harmful than random failures. A preliminary version of this paper appeared in Proc. ACM Symp. Principles of Distributed Computation (PODC), Las Vegas, July 2005.     

HAMS: Scalable peer-to-peer multimedia streaming model in heterogeneous networks

In a peer-to-peer (P2P) overlay network, a large number and various types of peer processes are interconnected in networks and are cooperating by using multimedia contents like movies and music. Here, multimedia contents are in nature distributed to peers in various ways like downloading and caching to the peers. Multimedia streaming is a key technology to realize multimedia applications in networks. In multimedia streaming applications, multimedia contents are required to be reliable and continuously delivered to processes in a real-time manner. Some contents peer may not send packets of a content at a required rate due to limited computation resource and a communication channel may not support enough Quality of Service (QoS) due to congestions and faults. Thus, P2P overlay networks are in nature heterogeneous. In this paper, we newly discuss a heterogeneous asynchronous multi-source streaming (HAMS) model where multiple contents peers transmit packets of a multimedia content to a requesting leaf peer to increase the throughput, reliability, and scalability in P2P overlay networks. Here, some pair of channels between contents and leaf peers may support different QoS. Peers may be faulty and some pair of contents peers may have different transmission rates. Finally, we show the HAMS model can support higher throughput and shorter transmission time than the other models in the evaluation.     

一种令P2P覆盖网络拓扑相关的通用方法

利用分布式哈希表,有结构的对等(peer-to-peer,简称P2P)网络具备了较短的路由长度和较好的扩展性.然而,由此产生了覆盖网络和物理网络之间的不匹配问题,它严重阻碍了在大规模环境下建立有效的对等网络.提出一种通用的、协议无关的方法来解决该问题.该方法基于节点交换机制,通过发现并实施有利于覆盖网络和物理网络匹配的节点交换来降低网络时延、提高性能.实验表明,该方法在明显降低了覆盖网络的平均时延的同时,也保证了额外开销可控.此外,若与其他协议相关的方法相结合,系统性能还可以得到进一步提高.     

Psu: a novel low-latency constant-degree overlay network

Many structured peer-to-peer (P2P) systems supported by distributed hash table (DHT) schemas have been proposed recently to improve the scalability of distributed virtual application systems. By organizing the peers based on interconnection topologies, existing proposed schemas are purely based on the logical relationship without knowledge of the physical networks. In this paper, we propose a new structured DHT schema, which receives routing information not just from virtual neighbors in P2P overlay network, but also from nearby physical neighbors. The average degree of our model is 5, the diameter is logarithmic. The simulation shows that our model achieves shorter query path length, higher clustering, and better robustness than other overlay networks which have the same level of degree and diameter.     

Psu: a novel low-latency constant-degree overlay network

Many structured peer-to-peer (P2P) systems supported by distributed hash table (DHT) schemas have been proposed recently to improve the scalability of distributed virtual application systems. By organizing the peers based on interconnection topologies, existing proposed schemas are purely based on the logical relationship without knowledge of the physical networks. In this paper, we propose a new structured DHT schema, which receives routing information not just from virtual neighbors in P2P overlay network, but also from nearby physical neighbors. The average degree of our model is 5, the diameter is logarithmic. The simulation shows that our model achieves shorter query path length, higher clustering, and better robustness than other overlay networks which have the same level of degree and diameter.     

Assisted Peer-to-Peer Search with Partial Indexing

In the past few years, peer-to-peer (P2P) networks have become a promising paradigm for building a wide variety of distributed systems and applications. The most popular P2P application till today is file sharing, e.g., Gnutella, Kazza, etc. These systems are usually referred to as unstructured, and search in unstructured P2P networks usually involves flooding or random walking. On the other hand, in structured P2P networks (DHTs), search is usually performed by looking up a distributed inverted index. The efficiency of the search mechanism is the key to the scalability of a P2P content sharing system. So far, neither unstructured nor structured P2P networks alone can solve the search problem in a satisfactory way. In this paper, we propose to combine the strengths of both unstructured and structured P2P networks to achieve more efficient search. Specifically, we propose to enhance search in unstructured P2P overlay networks by building a partial index of shared data using a structured P2P network. The index maintains two types of information: the top interests of peers and globally unpopular data, both characterized by data properties. The proposed search protocol, assisted search with partial indexing, makes use of the index to improve search in three ways: first, the index assists peers to find other peers with similar interests and the unstructured search overlay is formed to reflect peer interests. Second, the index also provides search hints for those data difficult to locate by exploring peer interest locality, and these hints can be used for second-chance search. Third, the index helps to locate unpopular data items. Experiments based on a P2P file sharing trace show that the assisted search with a lightweight partial indexing service can significantly improve the success rate in locating data than Gnutella and a hit-rate-based protocol in unstructured P2P systems, while incurring low search latency and overheads.     

Peer counting and sampling in overlay networks based on random walks

In this article, we address the problem of counting the number of peers in a peer-to-peer system. This functionality has proven useful in the design of several peer-to-peer applications. However, it is delicate to achieve when nodes are organised in an overlay network, and each node has only a limited, local knowledge of the whole system. In this paper, we propose a generic technique, called the Sample&Collide method, to solve this problem. It relies on a sampling sub-routine which returns randomly chosen peers. Such a sampling sub-routine is of independent interest. It can be used for instance for neighbour selection by new nodes joining the system. We use a continuous time random walk to obtain such samples. The core of the method consists in gathering random samples until a target number of redundant samples are obtained. This method is inspired by the “birthday paradox” technique of Bawa et al. (Estimating aggregates on a peer-to-peer network, Technical Report, Department of Computer Science, Stanford University), upon which it improves by achieving a target variance with fewer samples. We analyse the complexity and accuracy of the proposed method. We illustrate in particular how expansion properties of the overlay affect its performance. We use simulations to evaluate its performance in both static and dynamic environments with sudden changes in peer populations, and verify that it tracks varying system sizes accurately.     

Building resilient low-diameter peer-to-peer topologies

As more applications rely on underlying peer-to-peer topologies, the need for efficient and resilient infrastructure has become more pressing. A number of important classes of topologies have emerged over the last several years, all with various strengths and weaknesses. For example, the popular structured peer-to-peer topologies based on distributed hash tables (DHTs) offer applications assured performance, but are not resilient to attacks and major disruptions that are likely in the overlay. In contrast, unstructured topologies where nodes create random connections among themselves on-the-fly, are resilient to attacks but can not offer performance assurances because they often create overlays with large diameters, making some nodes practically unreachable. We propose Phenix, a peer-to-peer algorithm for building resilient low-diameter peer-to-peer topologies that can resist different types of organized and targeted malicious behavior. Phenix leverages the strengths of these existing approaches without inheriting their weaknesses and is capable of building topologies of nodes that follow a power-law while being fully distributed requiring no central server, thus, eliminating the possibility of a single point of failure in the system. We present the design and evaluation of the algorithm and show through extensive analysis, simulation, and experimental results obtained from an implementation on the PlanetLab testbed that Phenix is robust to network dynamics such as bootstrapping mechanisms, joins/leaves, node failure and large-scale network attacks, while maintaining low overhead when implemented in an experimental network.     

Efficient, self-contained handling of identity in peer-to-peer systems

Identification is an essential building block for many services in distributed information systems. The quality and purpose of identification may differ, but the basic underlying problem is always to bind a set of attributes to an identifier in a unique and deterministic way. Name/directory services, such as DNS, X.500, or UDDI, are a well-established concept to address this problem in distributed information systems. However, none of these services addresses the specific requirements of peer-to-peer systems with respect to dynamism, decentralization, and maintenance. We propose the implementation of directories using a structured peer-to-peer overlay network and apply this approach to support self-contained maintenance of routing tables with dynamic IP addresses in structured P2P systems. Thus, we keep routing tables intact without affecting the organization of the overlay networks, making it logically independent of the underlying network infrastructure. Even though the directory is self-referential, since it uses its own service to maintain itself, we show that it is robust due to a self-healing capability. For security, we apply a combination of PGP-like public key distribution and a quorum-based query scheme. We describe the algorithm as implemented in the P-Grid P2P lookup system (http:// www.p-grid.org/) and give a detailed analysis and simulation results demonstrating the efficiency and robustness of our approach.     

Distributed multi-source streaming models in peer-to-peer overlay networks

A multimedia contents are distributed to peer computers (peers) and a contents peer which holds contents can provide other peers with the contents in peer-to-peer (P2P) overlay networks. Here, contents peers are mainly realized in less-reliable and low-performance personal computers. Multimedia streaming is more significant than downloading ways in multimedia applications from security and economical reasons. We discuss distributed multi-source streaming models to support peers with reliable and scalable multimedia streaming service. Here, a collection of multiple contents peers in parallel transmit packets of a multimedia content to a leaf peer to realize the reliability and scalability. Each of the contents peers send different packets from the other contents peers at slower rate. Even if not only some number of peers stop by fault and are degraded in performance but also some number of packets are lost and delayed in networks, a leaf peer has to receive every data of a content at the required rate. We discuss how to replicate data of a multimedia content by creating a parity packet for some number of packets and to allocate packets to each contents peer so that a leaf peer can deliver a packet without waiting for preceding packets from other contents peers in presence of the faults. Next, multiple contents peers are required to be synchronized to send packets to a leaf-peer so that the leaf-peer can receive every data of a content at the required rate. We discuss a pair of gossip-based flooding-based protocols, directed acyclic graph (DAG)-based coordination protocol (DCoP) and tree-based (TCoP) coordination protocol to synchronize multiple contents peers to send in parallel send to a leaf peer. First, some number of contents peers are selected and start transmitting packets to a leaf peer. Then, each of the selected peers selects some number of peers. Here, a peer can be selected by multiple peers in DCoP but by at most one peer in TCoP. Finally, every contents peer transmits packets to the leaf peer at the allocated rate. We evaluate the coordination protocols DCoP and TCoP in terms of how long it takes and how many messages are transmitted to synchronize multiple contents peers.     

H-P2PSIP: Interconnection of P2PSIP domains for global multimedia services based on a hierarchical DHT overlay network

The IETF P2PSIP WG is currently standardising a protocol for distributed multimedia services combining the media session functionality of SIP and the decentralised distribution and localisation of resources in peer-to-peer networks. The current P2PSIP scenarios only consider the infrastructure for the connectivity inside a single domain. This paper proposes an extension of the current work to a hierarchical multi-domain scenario: a two level hierarchical peer-to-peer overlay architecture for the interconnection of different P2PSIP domains. The purpose is the creation of a global decentralised multimedia services in enterprises, ISPs or community networks. We present a study of the routing performance and routing state in the particular case of a two-level distributed hash table hierarchy that uses Kademlia. The study is supported by an analytical model and its validation by a peer-to-peer simulator.     

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.     

A hierarchical overlay with cluster-based reputation tree for dynamic peer-to-peer systems

Traditional peer-to-peer technologies and systems assume that people operate with desktop computers in fixed broadband networks. When people with modern mobile devices now access Internet and Web services much in the manner they used to on desktop computers, the classical peer-to-peer overlay models can be vulnerable in wireless and mobile networks. This paper proposes a hierarchical overlay architecture based on partially central and semi-structured overlay models for the deployment of peer-to-peer systems in dynamic network environments. To keep up system scalability and efficacy, this architecture design exploits peer locality and network proximity, and contends with several problems of peer churn, peer mobility, search redundancy and traffic overhead that become much stickier in dynamic network environments. This design also integrates the reputation notion to mitigate the free-riding problem in peer-to-peer systems. According to a special cluster-based reputation tree, the hierarchical overlay is adjustable to moderate unfair or imbalanced resource utilization over the system. Furthermore, the cluster hierarchy is resilient to any points of failure at peer clusters in the overlay topology. Therefore, the effort of this study achieves an efficient and robust overlay architecture in dynamic network environments. Simulation results show that the proposed architecture is not only scalable to peer population, but also sustainable to peer- and network-initiated dynamics and influences in peer-to-peer systems.     

Overlay Design Mechanisms for Heterogeneous, Large-Scale, Dynamic P2P Systems

Large-scale, heterogeneous peer-to-peer (P2P) systems impose a set of diverse requirements. Current solutions do commonly only address a subset of these requirements since there are a number of trade-offs and constraints due to the different dimensions and aims they address. We present a novel approach for designing overlay networks for large-scale, highly dynamic, and heterogeneous P2P systems. A set of mechanisms is proposed to meet the complete set of requirements while keeping the trade-offs and constraints in balance. To handle effectively the large number of peers, they are clustered in manageable groups considering the requirements on their stability. The novelty in this approach is in the identification of the core services and operations of the aforementioned systems. On the basis of the requirements of those services and operations, peers are assigned the most suitable roles. Role relationships are further introduced to enable (and provide) incentives for the peers to adopt the most suitable roles while selecting an efficient overlay structure to preserve efficiency, robustness, and scalability. The proposed set of mechanisms is realized in Omicron, a novel hybrid P2P approach.