Distributed hash tables (DHTs) share storage and routing responsibility among all nodes in a peer-to-peer network. These networks have bounded path length unlike unstructured networks. Unfortunately, nodes can deny access to keys or misroute lookups. We address both of these problems through replica placement. We characterize tree-based routing DHTs and define MaxDisjoint, a replica placement that creates route diversity for these DHTs. We prove that this placement creates disjoint routes and find the replication degree necessary to produce a desired number of disjoint routes. Using simulations of Pastry (a tree-based routing DHT), we evaluate the impact of MaxDisjoint on routing robustness compared to other placements when nodes are compromised at random or in a contiguous run. Furthermore, we consider another route diversity mechanism that we call neighbor set routing and show that, when used with our replica placement, it can successfully route messages to a correct replica even with a quarter of the nodes in the system compromised at random. Finally, we demonstrate a family of replica query strategies that can trade off response time and system load. We present a hybrid query strategy that keeps response time low without producing too high a load.

Despite many improvements on original unstructured P2P networks, these systems still suffer from many problems, the most important of which are, (a) lack of guarantees on the integrity of the network topology in the face of churns, (b) excessive traffic cost, and (c) poor quality of search results. This paper introduces an end-to-end scalable unstructured P2P networking solution called SUPNET to address many of these issues. The solution consists of two sub-protocols, SUPNET-T and SUPNET-S, which are, respectively, responsible for network management and search. We investigate the end-to-end performance of our solution, both analytically and empirically. SUPNET-T is a scalable, highly robust protocol, capable of utilizing the heterogenous distribution of network resources. The high stability of SUPNET-T is the result of implementation of a novel distributed feedback mechanism. SUPNET-S, on the other hand, is capable of locating every item, even if a single copy of that item exists in the network. SUPNET-S does this while producing a traffic that scales provably sub-linear with the network size. The protocol also contains mechanisms for efficient search of popular items as well as distributed tuning algorithms. All this, along with a relative ease of implementation and a solid analytical foundation, make SUPNET a compelling solution for unstructured P2P networking.

To achieve higher efficiency over their unstructured counterparts, structured peer-to-peer systems hold each node responsible for serving a specified set of keys and correctly routing lookups. Unfortunately, malicious participants can abuse these responsibilities to deny access to a set of keys or misroute lookups. We look to address both of these problems through replica placement. Using Chord as an example, we present an equally-spaced replication scheme and prove that it can be tuned to produce any desired number of disjoint routes. To be specific, we prove that d disjoint routes can be produced by placing 2d-1replicas around a fully populated Chord ring in an equally-spaced fashion. In this situation, we also prove that there exists a route to at least one replica, which contains only uncompromised nodes, even if an attacker controls more than a quarter of the contiguous identifier space in the system. Simulation experiments demonstrate that this scheme performs better than previously proposed replica placement schemes in rings that are sparsely populated, populated in clusters, or populated partially by compromised nodes