Peer-To-Peer Networks

From Clients And Servers To Peers

Most services you use follow the client-server model. A client, such as your phone, asks. A server, a computer run by a company, answers. The roles are fixed: clients request and servers serve. This is the centralized shape from week 1.

In a peer-to-peer network, often shortened to P2P, every participant plays both roles. Each computer, called a peer, asks for things and also serves things to others. When more peers join, the network gains both more demand and more supply.

That last point is the main attraction. A server has a fixed capacity, and a sudden crowd can overwhelm it. A P2P network grows its capacity with its crowd. Each new peer brings its own bandwidth and storage.

P2P is old. Napster (1999) let users search for music files held on each other's machines, but its search index sat on a central server, and that server was the weak point. Later systems removed such centers. This week follows that path: how do peers find each other, and find content, when nobody keeps the list?

BitTorrent: Sharing A File In Pieces

Bram Cohen designed BitTorrent, released in 2001, to move large files efficiently. The central idea is to cut a file into many pieces. A peer downloads different pieces from different peers at the same time, and as soon as it holds a piece, it offers that piece to others.

A small file called a torrent describes the content. It lists the size of each piece and a cryptographic hash of each piece. A hash is a fixed-length fingerprint computed from data. If a single bit of the data changes, the hash changes completely. Peers check every received piece against its hash, so a dishonest peer cannot slip in corrupted data.

To start, a new peer needs addresses of other peers in the swarm, the group sharing that file. Originally a server called a tracker supplied the list. Later versions added a distributed method, described below, so that the swarm can function without the tracker.

BitTorrent also encourages fairness. Peers favor those who upload to them, an approach called tit-for-tat. Peers that only download are served last. A peer holding the complete file and uploading to others is called a seeder.

Finding Things: The Lookup Problem

Suppose a million peers each hold some data. You want the item named 'holiday.jpg'. Who has it? You could ask everyone, but that does not scale. You could keep a central directory, but then you rebuilt the centralized design.

Early networks such as Gnutella used flooding: each peer asks its neighbors, who ask their neighbors, and so on. Flooding finds things but produces enormous message traffic as the network grows.

A better answer is structured lookup: arrange the network so that each peer knows where to send a question to get closer to the answer. That is the job of a distributed hash table.

Distributed Hash Tables

A hash table is a familiar data structure: you store a value under a key, and a hash function turns the key into a location. A distributed hash table, or DHT, spreads that table over many peers. Each peer is responsible for a share of the keys.

In the DHT called Kademlia (Petar Maymounkov and David Mazieres, 2002), every peer and every key gets a long number, called an ID. A peer is responsible for the keys whose IDs are closest to its own ID. 'Closest' is measured with an operation named XOR, which gives a symmetric notion of distance.

Each peer keeps a short list of contacts, many with IDs near its own and a few from far across the ID space. To look up a key, a peer asks the contacts closest to the key to name even closer contacts. Each step roughly halves the remaining distance. In a network of a million peers, about twenty steps are usually enough. In general the cost grows with the logarithm of the network size, which is why lookups stay fast as the network grows.

Kademlia underlies the BitTorrent DHT and is the model for the lookup system in IPFS (week 5) and Ethereum's peer discovery. A DHT stores small records, such as 'peer X has piece Y', not large files.

• Every key and peer has an ID
• A peer stores keys close to its own ID
• Each lookup step moves closer to the key
• Cost grows slowly with network size

Four Generations Of Peer To Peer

System	Year	How peers find content
Napster	1999	Central index server
Gnutella	2000	Flooding queries to neighbors
BitTorrent	2001	Tracker, later DHT
Kademlia	2002	Structured lookup by key distance

Each step removed one more central piece or made search cheaper. Source: Original system papers and releases; Maymounkov and Mazieres, Kademlia, 2002

Idealized Lookup Steps In A DHT

steps

Illustrative. Lookup cost grows with the logarithm base 2 of the network size, so a thousand times more peers adds only about ten steps. Source: Idealized log2 n for a Kademlia style DHT; illustrative of the scaling idea

A DHT Lookup

1. Hash the key
2. Ask the closest peer you know
3. Peer returns peers even closer
4. Repeat until nobody is closer
5. Fetch the value

Each round roughly halves the remaining distance.

Gossip Protocols

Gossip works like a rumor. A peer that learns something new picks a few random peers and tells them. Each of those picks a few random peers and tells them, and so on. After some rounds, nearly everyone knows.

The spread is fast. If each informed peer tells two random others each round, the number of informed peers roughly doubles every round, so a network of a million peers is covered in a few dozen rounds. No peer needs to know the whole network, and no central coordinator exists.

Gossip tolerates failure well. If a peer crashes, other paths still carry the message. This fits the lessons from week 2: messages may be lost, so redundancy protects against loss.

The cost is some waste, because peers hear the same rumor many times, and information arrives at different peers at different moments. That makes gossip a natural fit for eventual consistency. Many databases use it to share membership lists, and blockchains such as Bitcoin and Ethereum use gossip to spread new transactions and blocks.

The NAT Problem

For two peers to talk directly, each must be able to reach the other's address. Most home computers cannot be reached this way. Your router uses Network Address Translation, or NAT. Many devices in your home share one public IP address, and the router keeps a table that maps outgoing connections to inside devices.

NAT allows connections that start inside and let replies return. It drops unexpected incoming connections, since the router does not know which device they are for. If both peers sit behind NAT, neither can start a connection to the other.

P2P software has several remedies. With UPnP or port mapping, a peer asks the router to open a port. With hole punching, both peers contact a helper server that tells each one the other's public address and port, and then both send packets to each other at the same moment. Each router sees the outgoing packet and lets the matching reply in. STUN is a standard protocol for learning your public address, and ICE combines the techniques.

If everything fails, peers fall back on a relay: a public machine forwards traffic between them. Relays work reliably but cost bandwidth and bring back a small amount of centralization. The honest picture is that real P2P networks mix direct connections with helper servers.

How Peers Find Each Other The First Time

A new peer faces a bootstrap problem. It knows nobody, so whom does it ask first? Almost every P2P network ships with a short list of well-known addresses, called bootstrap nodes or seed nodes, written into the software or published in a place such as DNS. The new peer contacts one, learns about others and then continues with the DHT or gossip.

Bootstrap nodes are a point of trust, since a dishonest one could feed a newcomer only malicious peers. Networks reduce the risk by keeping many bootstrap nodes, by letting users supply their own, and by checking data with hashes.

Attacks deserve attention too. In a Sybil attack, one actor creates a very large number of fake identities to dominate the network. In an eclipse attack, an actor surrounds a victim's connections so the victim sees only the attacker's version of the world. Defenses include limiting how many peers may come from the same address range and choosing contacts partly at random. Week 6 returns to the identity side of this problem.

P2P design therefore combines three layers: a way to discover peers, a way to find data, and a way to check what you received.

Key Terms

Peer-to-peer (P2P)

A network where every participant both requests and provides resources.

Swarm

The group of peers sharing the same file in BitTorrent.

Hash

A fixed-length fingerprint computed from data that changes completely if the data changes.

Tracker

A server that tells BitTorrent peers about other peers in a swarm.

Distributed hash table (DHT)

A lookup table whose keys are spread over many peers that each know where to send a query.

Gossip

A way of spreading information by having each peer tell a few random peers.

NAT

A router feature that lets many devices share one public address and blocks unexpected incoming connections.

Hole punching

A technique where two peers behind NAT send packets to each other at once so that both routers allow the traffic.

Bootstrap node

A well-known peer that a newcomer contacts first to learn about the network.

Exercise: Gossip In A Hundred Peers

1. Install Python 3 and create gossip.py.
2. Paste the code from the 'Gossip simulation' slide and run it. Note how many rounds it needs for 100 peers.
3. Change the number of peers to 1000 and run it again. Compare the rounds with the first run.
4. Change the fanout (how many peers each informed peer tells) from 2 to 1 and then to 3. Record the rounds each time.
5. Add a line that makes 20 percent of messages get lost (use random.random() > 0.2) and measure again.
6. Write three sentences on what the results say about gossip and network size.

Further Reading

• Incentives Build Robustness in BitTorrent, Bram Cohen, 2003
• Kademlia: A Peer-to-peer Information System Based on the XOR Metric, Petar Maymounkov and David Mazieres, IPTPS 2002
• Peer-to-Peer Communication Across Network Address Translators, Bryan Ford, Pyda Srisuresh and Dan Kegel, USENIX 2005
• Epidemic Algorithms for Replicated Database Maintenance, Alan Demers and colleagues, PODC 1987
• Distributed Systems, 4th edition (chapter on peer-to-peer systems), Maarten van Steen and Andrew Tanenbaum