Skip to content

Instantly share code, notes, and snippets.

@mrtazz

mrtazz/summary.md

Created September 13, 2010 20:50
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mrtazz/578018 to your computer and use it in GitHub Desktop.
Save mrtazz/578018 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
summary.md

P2P Networks

Overview of P2P lecture Summer 2010 University of Freiburg

Napster

  • Star topology
  • Query via server
  • Download directly from Peer

Gnutella

  • Neighbourhood lists
  • List of usually online Clients
  • lookup => flooding to usual depth of 5
  • Gnutella2
    • Supernodes (high bandwidth) connected via Gnutella protocol
    • Clients are only connected to supernodes

DHT

  • conventional hashing is bad
    • new peer changes all entries
    • how to assign numbers to peers
    • avg. linear time
    • 50% of peers in the middle
  • consistent hashing
    • hash peers and data into area

CAN

  • DHT based
    • index entries mapped to square [0,1]^2
    • areas are always divided by half
    • Expected size of a peer's area: 1/n
    • Area not being hit: (1-1/n)^n <= 1/e
    • Data fairness: bounded by c ln n (avgamount)
  • Network structure
    • neighbour lists
      • avg degree: O(d)
      • hops: O(n^(1/d) )
    • insertion like leafs in random tree, depth: O(log n)
    • test neighbour for existence
    • Defragmentation

Chord

  • DHT ring
  • predecessor/successor link
  • finger links
  • Balance: peer stores O(k/nlogn) entries
  • E["distance between peers"] = **2^(m/n) **
  • Inserting new peer: **O(log^2 n) ** messages
    • out-pointers can be adopted from neighbour peers
  • DHash++ (Improved routing for Chord)
    • Data layout
      • store reference information
      • distributed data storage
      • distributed block-wise storage
    • Recursion instead of iteration
    • Replication

Analysis of DHT

  • Size of Holes: Omega(log n/n)
  • Dense areas: Omega(log n/(loglog n))
  • Averaging effect: Theta(log n) elements in interval 1/n
  • Chernoff-Bounds
    • for independent bernoulli experiments
    • c > 0: P[Sn geq (1+c) E[Sn]] leq e^(-1/3*pn*min{c,c^(2)})
    • 1 > c > 0: P[Sn leq (1-c) E[Sn]] leq e^(-1/2*pn*c^(2))

Pastry

  • DHT ring
  • 128bit ID
  • unique/uniformly distributed
  • Routing table
    • At most **O(2^(b(logn)/b)) ** entries
    • w.e.h.p no peer of same prefix with length **(1+eps)(logn)/b **
    • hence equally many rows
  • Leafset
    • l/2 neighbours in each direction
  • Neighborhood list
  • New peer enters
    • copy neighborhood list of known host
    • search for own ID
    • copy leafset and routing table from z
  • Locality

Distance Halving

  • Continuous graph
  • Left Edges: (x,x/2)
  • Right Edges: (x, 1/2+x/2)
  • plus opposing edges
  • Principle of multiple choice
    • test c log n intervals
    • choose largest
    • interval sizes: 1/(2n), 1/n or 2/n w.h.p
  • Lookup
    • left edges until new start and target are near and then backwards
    • Complexity: 2logn + O(1) messages/hops

Skip-Net and Skip-Graph

  • Skip-List
    • start with directly connected list
    • select nodes with p=50%
    • connect nodes as link list in next level
  • Skip-Graph
    • doubly connected
    • "losers" also form groups
  • Efficient search for Name or Num(random numbers) ID
  • Lookup
    • O(logn) hops and messages
  • Locality
    • hosts can be sorted according to local domain
  • Range Search
    • O(log n) for first element constant time for successing

Anonymity

  • Anonymity
  • Unlinkability
  • Unobservability
  • Pseudonymity
  • Chaum's mix Cascade
    • Implemented by TOR
  • Free-Net
    • files stored encrypted on target and lookup path
    • storage peers cannot read data
    • secret keys stored elsewhere
    • Network structure
      • similar to Gnutella
      • decode files via signed subspace key
  • Dark-Net
    • exclusive club for anonymous people

Network Coding

  • optimize network flow
  • max data flow = minimal cut = max data to sink
  • Linear network codes
    • solve matrix equations
  • Galois Fields
    • lookup table
    • numbers/polynomial representation/decimal from pol as binary
    • x*y = exp(log(x) + log(y))

Fast Download

  • IP multicast
  • Scribe
    • based on Pastry
    • Group ID via Pastry index
  • Bottleneck Remover
    • Overloaded peer notifies farthest peer, erases edge
    • rebalance with new farthest peer
  • Split-Stream
    • file partition
    • several multicast trees
  • BitTorrent
    • Splitstream similar
    • multiple parts
    • multiple phases
      • Rarest First
      • Random First
      • Endgame Mode
    • Choking/Reward system
    • Coupon Collector
  • Pair coding
    • connected block components
    • decode when different block components
    • Complexity: O(n * ackermann(n))
  • Forward error correction
    • plain blocks plus k linearly independent code blocks
    • Reed Solomon Code
  • Treecoding
    • fixed linear coefficients for all blocks
    • Xor of two nodes creates parent node
    • k different trees
    • root nodes are equivalent to network coding blocks
    • leaves are equivalent to uncoded blocks

Game Theory

  • Dominant strategy
    • always better than any other strategy
  • Nash Equilibrium
    • best for both
  • not necessary Pareto-optimal
  • Pareto optimal == better for some without being worse for other

Self-Organization

  • Pareto Distribution
  • Heavy Tail Distribution
  • Small World Network
    • Everyone knows everyone via ca 6 people

Random Networks

  • Properties
    • Soundness
    • Generality
    • Feasibility
    • Convergence
  • Simple Switching
    • disconnects graph with positive probability
    • choose two edges and switch cross-wise
  • Push => converges to star
  • Pull => converges to single nodes with loop
  • Push-Pull
  • The 1-Flipper
    • flipping edges
    • hub edges
  • The k-Flipper
    • flipping edges
    • k-long hub

Kelips

  • Affinity Groups
  • links to all group neighbours and random peer in other groups
  • Lookup
    • Complexity: O(1)
    • Routing table size: O(n^(1/2) )
  • Epidemic Models
    • SI Model: susceptible => infected
    • SIS Model: susceptible => infected => susceptible
    • SIR Model: susceptible => infected => recovered
    • differential equations
  • Random Call Model
    • Push Model => infect others
    • Pull Model => get infected
    • Push/Pull Model => both
  • Max-Counter Algorithm
    • if rumour is older than TTL, stop transmission
    • critical choice of TTL
  • Shenker's Min Counter
    • age counter for each rumor

Hole Punching

  • Relaying => Rendezvous server as message switcher
  • connection reversal => use Server to announce request for cr
  • UDP hole punching
  • STUN
    • Client Server for exchanging external adresses
  • TCP Hole Punching
  • STUNT
  • NATBlaster
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment