SKR 5302: Advanced Distributed Computing

9.10. Peer-to-Peer Networks: BitTorrent

BitTorrent history and motivation

• 2002: B. Cohen debuted BitTorrent
• Key motivation: popular content
• Popularity exhibits temporal locality (Flash Crowds)
• E.g., Slashdot effect, CNN Web site on 9/11, release of a new movie or game
• Focused on efficient fetching, not searching
  • Distribute same file to many peers
  • Single publisher, many downloaders
• Preventing free-loading

BitTorrent: Simultaneous Downloading

• Divide large file into many pieces
  • Replicate different pieces on different peers
  • A peer with a complete piece can trade with other peers
  • Peer can (hopefully) assemble the entire file
• Allows simultaneous downloading
  • Retrieving different parts of the file from different peers at the same time

BitTorrent Components

• Seed
  • Peer with entire file
  • Fragmented in pieces
• Leacher
  • Peer with an incomplete copy of the file
• Torrent file
  • Passive component
  • Stores summaries of the pieces to allow peers to verify their integrity
• Tracker
• Allows peers to find each other
• Returns a list of random peers

BitTorrent: Overall Architecture

1.

2. 

3.

4.

5.

6.

7.

File distribution: BitTorrent

BitTorrent (1)

• file divided into 256KB chunks.
• peer joining torrent: 
  • has no chunks, but will accumulate them over time
  • registers with tracker to get list of peers, connects to subset of peers (“neighbors”)
• while downloading,  peer uploads chunks to other peers. 
• peers may come and go
• once peer has entire file, it may (selfishly) leave or (altruistically) remain

BitTorrent (2)

Pulling Chunks

• at any given time, different peers have different subsets of file chunks
• periodically, a peer (Alice) asks each neighbor for list of chunks that they have.
• Alice sends requests for her missing chunks
• rarest first

Sending Chunks: tit-for-tat

• Alice sends chunks to four neighbors currently sending her chunks at the highest rate 
  • re-evaluate top 4 every 10 secs
• every 30 secs: randomly select another peer, starts sending chunks
  • newly chosen peer may join top 4
  • “optimistically unchoke”

1. Alice “optimistically unchokes” Bob
   
2. Alice becomes one of Bob’s top-four providers; Bob reciprocates
   
3. Bob becomes one of Alice’s top-four providers
   

Free-Riding Problem in P2P Networks

Vast majority of users are free-riders

• Most share no files and answer no queries
• Others limit # of connections or upload speed

A few “peers” essentially act as servers

• A few individuals contributing to the public good
• Making them hubs that basically act as a server

BitTorrent prevent free riding

• Allow the fastest peers to download from you
• Occasionally let some free loaders download