For years I’ve been maintaining a loosely organized collection of papers and notes in the area of peer-to-peer (P2P) networking. As I have been going through notes and papers while working on my dissertation I realized this would have been great to have early on in my research, so hopefully someone else will find it helpful. Over time I’ll try to organize things better and translate my vague notes into prose where I think there are some key ideas.

P2P: the big picture

Unlike client/server based systems, where many clients connect to a single server in order to lookup information, the goal in P2P networking is to create distributed services across a large number of peers.

First, it’s always good to jump into a new area by reading survey papers, so I’ll link some here:

• a survey of overlay network schemes from 2005 IEEE communications surveys

• a survey of search techniques for robust p2p

Besides grokking the big picture, it is also helpful to clearly state the problems that are trying to be solved. Here are a couple papers that help to layout the problem space:

• Looking up data in P2P systems looks mostly at DHTs

• The essence of P2P presents a reference model for P2P overlay networks, and while it mostly focuses on DHT type systems it presents a nice theoretical framework for thinking about P2P.

• In open problems in data sharing p2p systems the authors present a variety of challenges for P2P systems, such as supporting rich and expressive query languages, providing autonomy and security while being robust and efficient, etc.

Flooding and Random Walks

Gnutella was one of the first P2P systems to gain widespread popularity, and it is based on the simplest method possible for implementing a P2P system, flooding. When a peer joins the gnutella network it first asks a peer (any one it can find out about, normally from a bootstrap server or a list of previously known peers) for information about other active peers. Then it opens connections (sockets) to a bunch of these peers and inserts itself into the network. When a user searches for a file the peer sends the query to all of its neighbors, and they in turn forward the query on to all of there neighbors, thus flooding the network. After a certain number of hops (the so-called hops-to-live, typically 6 or 7), the query will no longer be forwarded.

• flooding wastes bandwidth, but has lowest possible latency

• querying a subset of peers in a random graphs like this can be viewed as a distributed sampling problem

• random walks try to be smarter about using bandwidth, in exchange for longer latency

Random Walks in Peer-to-Peer Networks shows the effectiveness of using random walks for search rather than gnutella style flooding, and they provide a good theoretical background for understanding random walk based sampling.

The BubbleStorm system is one of my favorite unstructured P2P projects. They use a combination of random walks and small, localized floods to efficiently distribute replicas and perform sample-based searches, all with low latency and very impressive search success rates. I think this is a good paper to read if you want to understand the balance between search and replication, latency and overhead.

In Percolation Search, designed for power-law networks, a peer replicates its content listing on other peers to increase the probability of locating items even when they are rare. The same authors also worked on SUPNET, which uses feedback to better maintain the network topology, and is capable of finding even a single item of data in a large network.

Efficiently querying as many peers as possible in the shortest amount of time is one side of the P2P search coin. The other is replication, which increases the chances of finding an item because it is available on more peers. Checkout Replication Strategies in Unstructured Peer-to-Peer Networks for a good presentation of the problem and theoretical analysis of some different replication strategies.

Super Peers and asymetric P2P

I’ve never been too interested in this class of P2P systems so I don’t have a lot here, but the general idea is to take advantage of special peers in the network that have more resources and maintain much larger routing tables than most peers. While this work came about as a result of Gnutella measurement studies that found some peers did in fact last much longer and hold connections to many more peers, I don’t like the idea of basing an architecture on such a thing because it puts too much importance on a subset of peers. Anyway, it can be interesting to understand.

Search in power-law networks shows how search can be greatly improved by taking advantage of networks where some peers maintain huge routing tables.

Distributed Hash Tables

A distributed hash table (DHT) provides key/value lookup across a set of network peers. The operations supported are basically just store, retrieve, update, and delete.

Started with research towards efficient, distributed web caches using consistent hashing, which used a hash function to randomly distributed objects across a set of network nodes and not require lots of rehashing on modification

Led to development of chord (see here for the long version), which organizes peers in a virtual ID space that wraps around ** in an 8-bit ID space the successor to the peer with ID 255 is the peer with ID 0

Other important DHTs are pastry, kademlia, can, and tapestry, which basically provide the same key/value storage function, but rather than being based on a ring structure they use different virtual topologies and routing strategies - importantly, they all result in O(logN) routing

The number of hops corresponds to the total network size and the amount of resources peers are willing to allocate to the task. Maintaining larger routing tables can provide much better performance. (See acccordion for a good analysis)

Engineering a DHT to perform well is not an easy task. Read this paper for good discussion and analysis where they try to optimize chord for high performance and minimal latency.

Maintaining the correct overlay topology can be difficult in the face of churn, and join/leave protocols as well as general maintenance algorithms seem to be the major complicating factor in DHT implementations. I like the Fuzzynet approach, which actually leverages churn rather than treating it as a problem. In Fuzzynet when a peer joins the DHT (ring structured overlay) it asks the peers in its local neighborhood for information about the object replicas that they maintain, and for the objects that don’t have enough replicas it republishes them again. When routing towards an object you then check each peer as you get close to the destination. This clever tactic spreads load when there are hotspots (popular items in the DHT), maintains replicas in the face of churn, and requires very little additional complexity.

Epidemic or Gossip Protocols

Gossip algorithms are becoming one of my favorite P2P techniques, because they are elegant, powerful and simple. In typical gossip systems each peer periodically shares data with one of its neighbors, allowing information to slowly and efficiently propagate around the network. These algorithms can be used to maintain network structure, distribute software or overlay updates, compute aggregate values, perform clustering, and more.

For a good overview by some of the key people in this area read Gossip-based Peer Sampling

One of the most promising areas for gossip algorithms as the basis for self organizing P2P topologies. Three good papers about forming topologies on top of gossip networks are Cyclon, T-Man, and D2HT.

Computing aggregate values is another possible function of gossip systems. Checkout practical summation via gossip for some work in this area.

Dealing with Churn

Churn is the constant joining and leaving of peers in an overlay network. It might be due to network partitions and machine failures or just users who quit a client program to do something else. Unfortunately, this coming and going can wreak havoc on carefully constructed overlay routing topologies.

Checkout Understanding Churn in Peer-to-Peer Networks for good data and analysis of churn in a number of real P2P systems.

Over time people have developed ways to combat churn, mostly resulting in hybrid systems that maintain structure while being more flexible than the original DHT proposals. Read Debunking some myths about structured and unstructured overlays for some good initial work in this regard, where they simulate structured and unstructured overlays and propose some mechanisms for handling churn.

Another nice paper in this area is this Usenix paper, Handling Churn in a DHT, where they describe how they deal with churn in the Bamboo DHT.

Hybrid Systems

Amazon’s Dynamo uses gossip and a dht.

Apache Cassandra, originally created by Facebook engineers, implements a BigTable like database on top of a DHT along the lines of Dynamo.

Clustering and Semantic P2P

Lots more to go here…

In Locating Data in (Small-World?) Peer-to-Peer Scientific Collaborations they cluster peers based on document content and gossip bloom filters to share membership information.

BitTorrent

Yes, BitTorrent) gets its own section. This software/protocol is responsible for a huge portion of internet traffic, and it has been studied widely.

Bram Cohen, the open-source hacker who created BitTorrent published a paper on how incentives build robustness in BitTorrent. In short, BitTorrent peers use a so-called tit-for-tat strategy when interacting with other peers so that sharing is encouraged by giving preferential treatment to peers who give you useful data and leaching is discouraged by dropping peers that don’t share with you.

See Modeling and Performance Analysis of BitTorrent for an academic and theoretical understanding of BitTorrent.

There have also been some good measurement studies looking at torrents over time and how it performs in flashcrowd situations.

P2P Streaming

If you are interested in realtime streaming checkout this survey on p2p video streaming.

The canonical streaming topology is a simple multicast distribution tree, but if an intermediate peer in the tree fails it can screw things up for downstream nodes. In SplitStream they use network coding to split a media stream into multiple streams which each get sent out on a multicast tree. In this way each peer is in multiple distribution trees, and no one tree or peer is especially important to the overall service. The cool thing is that you only need a subset of the derived streams to recreate the primary stream, so even if one of your incoming streams hiccups you can continue watching the video.

Network coding is a form of erasure coding used in storage systems, where a block of data is used to generate multiple blocks of data, and any subset of these blocks can be combined to recreate the initial block. I think this will be an increasingly important concept in P2P systems.

In an earlier system Bullet they use more of a BitTorrent style mesh to distribute data, with the goal of maximizing incoming bandwidth for each peer.

The CoolStreaming/DoNet paper is a good one because they discuss a system that is actively streaming video to clients. They stuck to a simple system where peers share their availability information and request from whoever’s got the data they need. Simple and it works, as they show.

The Spotify music service uses an interesting mix of a super-peer style P2P file distribution system and hosted servers to dramatically cut-down on their server bandwidth requirements while offering low-latency access to a huge library of audio files.

Interesting Stuff

Lots of interesting research has gone on in this area that isn’t easily categorized, so for now I’ll just throw them here…

In A Case for P2P Infrastructure for Social Networks - Opportunities & Challenges the authors motivate the development of a Facebook like platform on P2P infrastructure. I think this should be one of the major goals for the research community, as it sets a very high bar technically and any infrastructure that could support this kind of system could support a wide range of interesting activities.

Comments

Feel free to drop me a note or comment below if you have anything to add or something you think could be improved.