Technical report detail

Spinneret: A log random substrate for P2P networks

by Rose, Jeff and Hall, Cyrus and Carzaniga, Antonio

Peer to peer overlay networks have evolved from the non-scalable Gnutella style of network wide floods, to the rigorously constructed and efficient distributed hash table (DHT) algorithms such as Chord, Kademlia, and Pastry. However, these algorithms suffer from a number of problems. First, in a large network with typical churn, their efficiency in routing can be outweighed by the cost of maintenance and keep-alive messages. Second, they require implicit trust relations between peers, which introduce security and fairness issues. Third, they support only a simple hash-table interface, where each object is referenced by a unique object identifier, which is less than ideal for a large set of peer-to-peer applications. In this paper we argue for the creation of a semi-structured overlay substrate, called Spinneret, which can serve as the base layer for a variety of structured and unstructured search algorithms. This layer maintains what amounts to a random graph where, given a distance function d between addresses, the probability of having a connection between peers i and j is proportional to 2^( d(i,j)). We argue that such a substrate strikes a balance between the resilience and reliability of unstructured networks and the efficiency of structured networks. In order to validate this claim, we present two algorithms simulated on top of the Spinneret substrate: an unstructured k-walker random walk search as well as a logarithmic DHT search.

Technical report 2006/06, December 2006

BibTex entry

@techreport{06spinneret, author = {Rose, Jeff and Hall, Cyrus and Carzaniga, Antonio}, title = {Spinneret: A log random substrate for P2P networks}, institution = {University of Lugano}, number = {2006/06}, year = 2006, month = dec }