6.824 Lecture 8: Peer-to-peer systems: File sharing

Today's instance of the content distribution problem.

A home user wants to share a popular song or video, but isn't always
online and has limited bandwidth.  Depending on which machines are
being aggregated you get two different cases, again: (1) if the
machines are home PCs, then bittorrent is useful; (2) if the machine
are powerful, well-connected, then UsenetNews might be good (or
Bittorrent).

This lecture's case study bittorrent

Usages: static bulk content
  Songs and videos
  Linux distributions
  ...

Usage model: cooperative
  user downloads file from someone using simple user interface
  while downloding, bittorrent serves file also to others
  bittorrent keeps running for a little while after download completes

Goal: get file out to many users quickly
  Encourage everyone to upload file

Challenges:
  Tracking which peer has what
  Handling high churn rates
  Download rate proportional to upload rate

Approach:
  Publisher a .torrent file on a Web server (e.g., suprnova.org)
    URL of tracker
    file name, length, secure hash
  Seed posts the URL for .torrent with tracker
    Seed must have complete copy of file
    Every peer that is online and has copy of a file becomes a seed
  Peer asks tracker for list of peers to download from
    Tracker returns list with random selection of peers
  Peers contact peers to learn what parts of the file they have etc.
    Download from other peers

Transport
  Peers pipeline on top of TCP
    divide a file part further in 16Kbyte subpieces
    keep typically 5 requests in flight

Which pieces to download
  strict?
  rarest first?
    ensures that every piece is widely available
    also helps with the seed and bootstrapping rapidly
  random?
    avoid overloading seed when starting download
  parallel download of same pieces?
    avoid waiting on slowest
  final algorithm
    random for first piece, then rarest-first, parallel for last piece

Fairness
  Goal: avoid peers that don't upload
  Approach:
    peers maximize download rate, but uploader can choke
    peers reciprocrate uploading to peers that upload to them  
  Which peers to unchoke?
    the ones who provide the highest download rate
      pick best 4
      rate is calculated over 20s average
      best are recalculated every 10s
    every 30s unchoke unused peer
      to see if it gives a good download rate
  What if you are choked by your peers?
    choke those peers if yon't receive a piece in 1 min
  What if donwload finished?
    use upload rate as the metric
    
How well does BitTorrent in practice?
  Anecdotally it works great---many happy users
  Difficult to answer precisely, but let's check the measurement paper

figures 1, 2, 3, 5, and 6

Efficiency
  How long does it take for a high-upload capacity find other
  high-performance peers?

  If there are a few high-upload peers and many low-upload peers, does
  Bittorrent perform at its best?  (Best = the total download time is
  at its lowest.)

Fairness
  Do high-upload peers receive download rates proportional to their
  upload rate?

http://www.cs.washington.edu/homes/piatek/papers/BitTyrant.pdf