Peer-to-peer networks

General

  • Motivation
    • Share resources in volatile and decentralized network of independent and autonomous peers
  • Key features
    • Decentralized
    • Self-organizing
    • Direct data transfer between peers
  • Advantages
    • Low costs (usually no extra hardware needed)
    • High scalability / flexibility
  • Important issues
    • Resource discovery
    • Network organization
    • Data transfer
  • Shareable resources
    • Information (file/documents)
    • Bandwidth (load balancing/shared bandwidth)
    • Storage space (DAS, NAS, SAN)
    • Computing power

Definition

  • P2P network is a virtual overlay network
  • Identify network as graph
  • Based on TCP-Connections between peers
  • Characteristics
    • Independent from physical network (no relation between physical and overlay edges)
    • Separate addressing and routing scheme
  • Topology properties / Classification
    • Centralized/decentralized
    • Structured/unstructured (specific topology)
    • Flat/hierarchical

Bootstrapping

  • Process of a node joining a network
  • Techniques
    • Bootstrap cache (nodes from last session)
    • Stable node (permanently online)
    • Bootstrap server
      • Request list of active nodes
      • Return least recently connected nodes
      • Alternative: Randomly pick recently connected node (no loops, but can be outdated)
    • Broadcast IP layer (IP broadcast, limited to local network)
    • Bootstrap list (List of potential bootstrap servers outside network, e.g., from awebsite)

History

  • Enabling technology: Performance increase
  • Computers
    • 1992 (HDD 0.3 GB, 100 MHz)
    • 2002 (100 GB)
    • 2007 (3 GHz, 320 GB)
  • Internet
    • 1990 (56 kbps)
    • 1997/1998 (10 Mbps)
    • 1999 (DSL: 8.5 Mbps)
    • 2000+ (Bandwidth no problem, plentiful / cheap)
  • Innovations
    • 1960 (ARPANET, research project of DARPA)
    • 1979 (UseNet protocol)
    • 1999 (WWW at CERN by Tim-Berners Lee)
    • 1999 (Napster lawsuit)
    • 2001 (Napster convicted)
  • P2P Applications
    • File sharing (e.g, music/video)
    • Software updates (e.g., patches, linux distributions)
    • Routing/bridging (avoid bottlenecks, e.g., Skype)
    • P2P unicast (replicate index to peers)

Unstructured peer-to-peer

  • First generation
    • Centralized directory model
    • Pure peer-to-peer
  • Second generation
    • Hybrid peer-to-peer

Centralized directory model

  • First generation
  • Examples: Napster, PeerJS, Skype, Gnutella
  • Classification: Centralized, unstructured, flat
  • Central entity/index server
    • Works as bootstrap server
      • Peers connect to index server (join network)
  • Advantages
    • Fast/complete lookup
    • Central managing/trust authority
    • Easy bootstrapping
    • Guaranteed lookup
    • Routing complexity \( O(1) \)
  • Disadvantage
    • Central entity: Single point of failure
    • Bad scalability
    • Node state complexity at server: \( O(N) \)

../_images/p2p-centralized.png

Node arrival

  • Node connects to central server
  • Node sends file list (content announcement)

Routing

  • Routing table (file-to-peer-mapping)
  • Workflow
    • Peer queries index server
    • Result: List of peers providing content
    • Peer connects to providing peer
  • Protocols
    • Peer and central entity
      • Special P2P protocol
      • Registering to overlay network
      • Query content
      • Update content information
      • Update routing tables
    • Peer and peer
      • HTTP

Pure peer-to-peer

  • First generation
  • Example: Gnutella 0.4
  • Characteristics
    • Decentralized (no central entity, no content index)
    • Unstructured (random overlay network, peers are equal)
    • Flooding (used for routing)
    • Bootstrapping (no central node known)
  • Advantage
    • No single point of failure
    • Adaptable to physical network
    • Anonymity (possibly)
    • Node state \( O(1) \)
  • Disadvantage
    • No guaranteed lookup (false negative)
    • Unscalable (flooding, low-bandwidth peers are useless, random network)
    • High network traffic (flooding)
    • Communication overhead \( O(N) \)
    • Low-bandwidth-node: Bottleneck
    • Overlay not optimal (no coordinator)
      • Possible zig-zag-routes, loops
    • Peers are not really equal (performance)

../_images/p2p-pure.png

Routing

  • Based on flooding
  • Request
    • Send requests to neighbors
    • Neighbors forward request
  • Response
    • Send result notification to requesting node
    • Use caches for back-tracking
  • Problem: Network overload
    • Solution: Time-to-live + hop counter
    • Increase hop counter each hop
    • TTL is maximum number of hops
  • Problem: Cycles
    • Solution: Cache messages for short time
    • Do not forward if request is cached
  • Effects
    • No guaranteed lookup
    • Unscalable (too many messages)

Gnutella 0.4

  • Goal: Avoid weaknesses of Napster
  • Classification: Fully decentralized, unstructured, flat (pure P2P)
  • Network type: Scale-free network
  • Components
    • Router service
      • Flooding of requests (TTL)
      • Routing of responses (e.g., keep-alive messages, exploration-messages)
    • Lookup service
      • Initialize query request
      • Keep-alive-requests (ping-pong)
    • Download service (direct connection)
  • Workflow
    1. Use bootstrap to find peers
    2. Send Exploration-Ping-Pong to explore neighborhood
    3. Send query to neighbors
    4. Receive response (QUERYHIT)
    5. Connect to peer to download file
  • Disadvantage
    • Free-riding possible
Ping-Pong Message
  • Ping message is responded by a pong message
  • Types
    • Keel-alive-ping-pong
      • TTL=1
      • Test of neighbor is available
    • Exploration-ping-pong
      • Explore/gather information of nodes
      • Pongs contain information of peers (uptime, bandwidth, number of files)
      • Store in peer cache
  • Ping-pong cache
    • Select stable peers for next bootstrap (uptime, etc.)
    • Boost connectivity (additional links to strong neighbors)
    • Compensate neighbor failure (reconnect to other neighbor)
  • Problem: Bandwidth-intensive
Header structure (unnecessary)
  • GnodeID (host ID)
  • Function (ping/pong/search)
  • TTL
  • Hops
  • Payload length

Hybrid P2P

  • Second generation
  • Example: Gnutella 0.6, KaZaA, eDonkey
  • Idea
    • Use advantage of more powerful peers
    • Combine centralized and pure P2P
  • Aspects
    • Network topology
    • Node arrival
    • Routing
  • Advantages
    • No single point of failure
    • Anonymity possible
    • Node state complexity \( O(1) \)
  • Disadvantages
    • High signaling traffic (decentralized super peer layer)
    • No guarantees
    • Overlay topology not optimal (no coordinator)
    • Routing complexity \( O(N) \)

Network

  • Classification: Scale-free
  • Hierarchical network layout
    • Super peers
      • Form pure P2P network
      • Distributed file index (content from leafs)
      • Queries distributed among super-peers
      • High node degree (degree >> 20)
    • Leaf peers
      • Attach to at least one super peer (degree < 7)
      • Centralized P2P
  • Hub-based network (super peers)
  • Reduced signaling load (ping-pong only in super peer layer)
  • Super peer selection (voluntarily, statistics, evolving)

../_images/p2p-hybrid.png

Node arrival

  • Leaf node registers at super peer
    • Send shared files
    • Super peer updates routing tables (file-peer-mapping)
  • Super peer
    • Load balancing (redirect leaf peer, suggest promotion for super peer)

Routing

  • Based on flooding
  • Routing table
    • Mapping between file name and node address
  • Partly decentralized
    • Leaf node sends request to super peer
    • Super peer checks if content in its routing table
    • Super peer distributes request in super peer layer (flooding, pure P2P)
    • Send leaf node address back (backward routing)
  • Hybrid protocol
    • Reactive: Download connection on demand
    • Proactive: Content announcement on node arrival

Network connections (unnecessary)

  • Signaling connections
    • Stable
    • Protocol: TCP-based
    • e.g., keep-alive-ping-pong, content search
  • Content transfer connection
    • Temporary
    • Protocol: HTTP
    • Out-of-band (directly between peers, not using signaling routes)

Structured peer-to-peer

  • Idea: Index data with Distributed Hash Table

Hash tables

  • Data structure
  • Lookup \( O(1) \) (worst case \( O(N) \))
  • Components
    • Bucket array (fixed-size \( m \))
    • Hash function \( h \)
  • Operations
    • Insert (hash value and add to bucket)
    • Lookup (hash value and scan bucket)

Hash function

  • Mapping \( h: U\rightarrow [0,m-1] \)
  • Properties
    • Low cost
    • Determinism
    • Uniformity
      • Assumption: Objects distributed uniformly
      • Uniform distribution
      • Reduce collisions
      • e.g., Load balancing
    • Range variability (Variable hash range)
    • Avalanche or Continuity (behavior for small changes on key)
  • Avalanche property
    • Change one bit in key, change 50 % of the hash bits
    • Cryptographic applications
    • Distribute objects robustly
    • Example: SHA-2 (224/256/384/512 bit)
  • Continuity property
    • Small change in key, small change in hash
    • Similarity searches
    • Example: Adler32
  • Example functions
    • Modulo hash (\( h(x) = x \mod k \)
    • Cryptographic hash (variable input size, avalanche, no reverse-computing)

Distributed Hash Tables

  • Classification: Decentralized, structured, flat
  • Idea
    • Distribute hash table over multiple nodes
  • Usual assumptions
    • Fixed hash range
    • Node is responsible for certain interval
    • Route requests along the hash range
    • Use Interface (exchange implementation)
  • Advantages
    • Simple/efficient
    • Efficient routing \( O(log(N)) \) (exponential finger table)
    • Storage per node \( O(log(N)) \)
    • Guaranteed results
    • Resilient to failures (repair routing table)
    • Load balancing (uniform distribution of keys)
    • Self-organizing
    • Supporting wide spectrum of applications
  • Disadvantages
    • Lookup not in \( O(1) \)
    • Repair overhead
  • Examples: CHORD, CAN, Pastry, Symphony, Tapestry, Kademlia, P-Grid

Design decisions

  • Hash function
  • Storage location of objects (direct, indirect)
  • Responsibilities of nodes (random, hashing, evolving)
  • Routing of queries
  • Dealing with failures
Hash function
  • Hash range a lot bigger than number of stored objects
  • Question: What are good keys? (application-dependent)
  • Common keys
    • Filename/filepath (early approach)
    • Keywords (hash multiple times)
    • Info digest/meta data (file length, settings)
    • Peer identification (peer ID, IP/MAC address)
Storage location of objects
  • Direct storage
    • Node stores actual content
    • Use shipping
    • Problem: Large content (high traffic, expensive join/leave)
    • Problem: Loss of ownership (e.g., malicious node)
    • Good for storage space load balancing
  • Indirect storage
    • Node stores link (physical address) to object
    • DHT announces availability of object
    • Flexible for large content (easy joining/leaving)
    • Minimal communication overhead
Responsibility
  • Usual assumption: Hash space is ring
  • Node knows predecessor and successor
  • Node responsible for certain arc
    • Arc ending at nodes hash value (hash ID, IP, MAC)
  • Additional heuristics can be used for responsibility (must be dynamic)
Routing
  • Workflow for querying
    1. Send to query to any node
    2. Hash key
    3. Route query to responsible node (key-based routing)
    4. Transfer data from peer to peer
  • Types
    • Direct routing
      • Central server knows responsibility
      • Fully-meshed ring (each node knows each node)
      • Routing complexity \( O(1) \)
      • Node state complexity \( O(N) \)
    • Linear routing
      • Start query at some node
      • Route query along ring (successively)
      • Routing complexity \( O(N) \)
      • Node state complexity \( O(1) \)
    • Finger table routing
      • Node knows additional nodes (but not all)
      • Stored in finger table/routing table
      • Routing complexity \( O(log(n)) \)
      • Node state complexity \( O(log(n)) \)

Load balancing

  • Common assumptions:
    • Uniform key distribution (uniform hash function)
    • Equal data distribution (uniform data size)
    • Equal query distribution (uniform query load)
  • Problem:
    • User queries are not equally distributed (power law)
    • No uniform distribution
    • Significant difference of load distribution
  • Definition optimally balanced
    • Load of each node: \( \frac{1}{N} \)
  • Definition Heavy/overloaded node
    • Load significantly greater than \( \frac{1}{N} \)
  • Definition Light node:
    • Load significantly lower than \( \frac{1}{N} \)
  • Algorithms
    • Power of two choices
    • Virtual Servers
    • Thermal-Dissipation-based approach
    • Simple address-space/item balancing
Power of two choices
  • Byers, 2003
  • Idea:
    • Choose node with lowest load
    • Use soft states (adapt for changing load)
  • Multiple hash function
    • \( h_0 \) for nodes
    • \( h_1,...,h_d \) for data
  • Options
    • Data stored on one node only
    • Data stored on one node, other nodes store a pointer
  • Data insertion (periodically, due to soft states)
    1. Calculate results of \( d \) hash functions
    2. Store data on the node with the lowest load
    3. Optional: Store pointers to node on all other nodes
  • Data retrieval
    • Data stored on one node only
      1. Calculate results of \( d \) hash functions
      2. Query all nodes in parallel
    • Data is stored on one node + pointers
      1. Calculate one hash result
      2. Query node (retrieve link or data)
  • Advantages
    • Simple
    • Lower load than Virtual Servers
  • Disadvantages
    • Message overhead for inserting
    • Search overhead (no pointers)
    • Administration overhead (with pointers)
    • Theoretically, nodes without load
Virtual servers
  • Rao, 2003
  • Idea:
    • Node responsible for several intervals
    • Each interval is called virtual server
    • Virtual server can be created/transferred
    • If node is too heavy, transfer to another node
  • Transfer rules
    • Transfer from heavy to light
    • Receiving node must have enough capacity
    • Transferred virtual server is the lightest that makes the heavy node light
    • If there is no transferable node, transfer the heaviest one
  • Schemes
    • One to one
      • Light node picks random node \( x \)
      • Receive virtual if \( x \) is heavy
    • One to many
      • Light nodes report load to directories
      • Heavy node select light node from directory
    • Many to many
      • Directory manages transfer
      • Directory contains load of all nodes
  • Advantages
    • Easy load shifting (whole virtual server)
    • Theoretically, every node has load
  • Disadvantages
    • Increased administrative/message overhead (finger table)
    • A lot of load shifting
    • Higher load than Power of two choices

Data durability

  • Definition k-resilience: \( k-1 \) nodes can crash without data loss
  • Strategies
    • Indirect storage and soft states
    • Replication: Successor list
    • Replication: Multiple noes
Indirect storage
  • Use Soft states
  • Each key-value pair has a lifetime (decay timer)
  • Content providers (application) periodically republishes content (create new or reset lifetime)
  • Node failure: Content available after certain time
  • Content provider failure: Content disappears after certain time
Replication: Successor list
  • Replicate data to \( k-1 \) next nodes
  • Node failure:
    • Stabilize function repairs routing
    • Replicate until \( k \) nodes contain data
  • Advantage
    • No instant copying needed if node fails
  • Disadvantage
    • Higher data load (node stores \( k \) intervals)
    • Message overhead during repair (find new successors, replicate to new successors)
Replication: Multiple nodes
  • Address range shared by at least \( k \) nodes
  • Node arrival
    • Connect to successor
    • Receive copy of all data
    • Split range after threshold (e.g., \( 2k \))
    • Finger table to other nodes in same interval
    • Alternative: Pass node to next interval if full (interval is divided)
  • Data insertion
    • Replicate to all nodes in interval
  • Node failure
    • No copying necessary
    • Stabilize function
  • Advantage
    • No instant copying needed if node fails
    • Dynamic interval size
    • Query load balancing possible (\( k \) nodes)
  • Disadvantage
    • Less number of intervals (\( \approx \frac{1}{k} \))

CHORD

  • MIT, 2001
  • Topology: Partially meshed ring
  • Goals
    • Routing complexity \( (O(log(N)) \) (key-based-routing)
    • Node complexity \( O(\log N) \)
    • Self-organization
    • Robustness (node arrival/departure/failure)
  • Node responsibility: Modulo ring
  • Concepts
    • Finger table
    • Neighborhood table

../_images/chord.png

Hash function

  • Hash range \( 2^m-1 \) (usually SHA-1, 160 bit)
  • Node ID: hash IP address and port
  • Data ID: hash data name or hash payload (how?)

Routing

  • Use finger table
    • Routing
    • \( m \) entries (with SHA-1 use 160 entries)
    • Exponentially increasing distance to finger node
    • Entry stores distance, target ID, node ID
    • Build finger table
      • Compute target IDs (\( targetId = (currentId + 2^i) \mod 2^m \))
      • Query successor for target node IDs
  • Querying
    • Route query to most distant finger node with an target ID lower than the queried ID
    • Routing complexity \( O(log(N)) \) (binary search)

Organization

  • CHORD fully self-organized
  • Cases
    • Node arrival
    • Node departure
    • Node/network failures
  • Goal
    • Maintain routing features (available target node should be reachable)
    • Durability for stored data (handled by the application)
  • Use neighborhood table
    • Maintenance
    • Contains the \( k \) direct successors/predecessors
Node arrival / join
  1. Node hashes itself
  2. Contact any DHT node (bootstrapping)
  3. Contact node responsible for new node ID (normal routing)
  4. Split arc (move key-value-pairs to new node)
  5. Construct neighborhood table
    • Use already connected node
    • Request successor/predecessor list
  6. Construct finger table
    • Use normal queries
Stabilize / Maintenance
  • Maintain neighborhood table
    • Each node regularly executes stabilize function
      • Contact first direct successor
      • \( pred(succ(x)) = x \)
      • Erweiterung mit \( k>1 \)
        • Contact the k-th successor
        • \( pred(succ_k(x)) = [x, succ_1(x), ..., succ_{k-1}(x)] \)
    • If not, new node was inserted (tables are outdated)
    • Repair with neighborhood table/predecessor list of outdated successor
    • If no connection, node failed
      • Repeat with second direct successor
      • Tell second direct successor to take over the responsible arc
    • Problem: All direct successor failed (no solution)
  • Maintain finger table
    • Important to guarantee routing
    • Repair mechanism
      • Select finger node \( v \)
      • If node \( v \) can’t be reached, ask direct successor to contact a node with the same distance as the previously selected node: \( w \)
      • Assumption: Finger target \( w \) already repaired neighborhood
      • Finger target \( w \) knows correct finger node for \( v \)
    • Active maintenance
      • Periodically execute repair mechanism
      • Less often than normal stabilize
      • Issue: Maintenance traffic
    • Passive maintenance
      • If contacting finger fails, forward to previous finger
      • Execute repair mechanism for broken finger
      • May fail, no \( O(log(N)) \) guarantee
Node departure / leave
  • Assumption: Departure = failure
  • Detected by stabilize function
    • Repair tables

Data durability

  • Data durability usually handled by application
  • Simple CHORD implementation uses no replication
  • Indirect storage using Soft states
  • Simple replication technique
    • Successor list
    • Multiple noes

Load balancing

  • Power of two choices
  • Virtual servers

CAN

  • UC Berkeley, 2001
  • Topology: d-dimensional space (use multi-dimensional hash function)
  • Node responsibility
    • Each node for certain region (no specific coordinate)
  • Node state complexity: \( O(d) \)

Routing

  • Routing table
    • Store physical address of neighbors
    • Store region coordinates of neighbors
    • Logical extent of region
  • Routing algorithm:
    • Idea: Forward request to region closest to destination
    • Multiple paths exist
  • Routing complexity:
    • \( O(d N^{\frac{1}{d}}) \)
    • Inferior to CHORD \( O(\log n) \)
    • Superior to Pure/Hybrid P2P \( O(n) \) (e.g., Gnutella)

Node arrival

  • Randomly choose coordinate
  • Send join request to responsible node for this region (bootstrap node required)
  • Reject request: Pick new coordinate (e.g., local load balancing)
  • Accept request
    • Split region + content
    • Update routing tables of neighbors

Pastry

  • Microsoft, 2001
  • Hash space: Ring
  • Important: Small world property
  • Routing
    • Three finger tables
      • Leaf table (nodes with direct key space proximity)
      • Routing table (random nodes with high key space distance)
      • Neighborhood table (direct network proximity, determined by broadcast)
    • Workflow
      • Route request to node with most similar/closest hash key
      • Use physical network properties (cheap communication)
      • Use small world properties
        • Leaf table: Short distance links
        • Routing table: Long distance links

Symphony

  • Stanford, 2003
  • Hash space: Ring
  • Idea: Use properties of small world
  • Finger table
    • Random construction using PDF
    • Probability distribution function
      • \( \frac{1}{d \log N} \)
      • \( d \): Distance along ring (???)
      • \( N \) nodes (unknown, estimate)
      • Estimation of \( N \)
        • Assumption: Equal node distribution along ring
        • Use normalized arc length \( x_n=\frac{x}{2^m} \)
        • \( N\approx \frac{1}{x} \)
    • Result: Multiple short distance links, several medium distance links, some long distance links
  • Route queries to closest node

Kademlia

  • Similar to Pastry
  • Topology: Ring (Small world)
  • Hash function: SHA-1 (160 bit)
  • Uses replication
    • Data stored in the next \( k \) nodes
  • Node state:
    • Node maintains information about files, keywords from nodes close to it
    • Soft state: Nodes must refresh key-value pairs (usually all 24 hours)
  • Advantage
    • Routing complexity: \( O(\log N) \)
    • Replication
    • Resilient to attacks
    • Dynamic network
  • Disadvantage
    • Complex routing table: \( O(k*\log N) \)

Routing

  • Tree-based (prefix-tree of hashes)
  • Closeness measure: \( d(n_1, n_2) = n_1 \oplus n_2 \)
    • Effect: First differing bits result in greater distance
  • Routing table
    • 160 entries
    • Each entry address range from \( 2^i \) to \( 2^{i+1} \)
    • Each entry contains \( k \) peers within that distance (called k-bucket)
    • k-bucket starts with least recently seen
  • Parameter \( k \)
    • \( k \) nodes should not fail within an hour (usually \( k=20 \))
    • Result: A lot of near nodes stored, a few distant nodes
    • Setting \( k=1 \): Similar to CHORD
  • Query
    • Node computes distance to key (XOR)
    • Query all \( k \) nodes in the respective bucket (or sub-tree)

Network theory

  • Motivation
    • Prove specific properties
  • Desirable system properties
    • Decentralized
    • Self-organizing (maintenance without authority)
    • Scalability
    • Efficient searching/retrieving (small number of hops)
    • Reliability (robust w.r.t. node failures)
  • Desirable graph properties
    • Connectedness
    • k-Connectedness with large \( k \)
    • Low diameter \( d(G) \) (ensure reachability)
    • Low average path length \( d_{avg}(G) \) (efficient routing)
    • Low average node degree \( deg(G) \) (limit size of routing tables)
    • High average cluster coefficient (failure resistance)
  • Decision
    • Navigable in decentralized fashion: Small-world using Kleinberg
    • High risk of attack: Small-world with low node degree
    • Small/secure context: Scale-free

Graph basics

Directed graph

  • \( V \): Set of nodes
  • \( E\subseteq V\times V \): Set of edges
  • \( n=|V| \)
  • \( m=|E| \)

Neighbors set of node

  • \( N(v) = \{w\in V \mid (v,w) \in E\} \)

Node outdegree

  • \( deg^+(v) = |N(v)| \)

Node indegree

  • \( deg^-(v) = |\{w\in V \mid (w,v)\in E\}| \)

Node degree

  • \( deg(v) = deg^+(v) + deg^-(v) \)

Path

  • \( P(v,w) = (v_0,...,v_k), v_0=n, v_k=w, \forall 0 \leq i < k: (v_i, v_{i+1})\in E \)
  • Path length: \( |P(v,w)| - 1 \)
  • Distance \( d(v,w,) \): Shortest path between \( v \) and \( w \)

Connectedness

  • \( \forall v_i, v_j\in V: P(v_i, v_j) < \infty \)
  • k-Connectedness
    • Removal of \( k-1 \) nodes leaves the graph connected

Graph bisection width

  • \( bsw(g) \)
  • Minimal cohesion
  • Minimaml number of edges to remove to split graph into two unconnected subcomponents

Graph diameter

  • \( d(G) = \max_{v,w\in V}(d(v,w)) \)
  • Maximal distance of any pair of vertices

Average path length

  • \( d_{avg}(G) = \frac{\sum_{(v_i,v_j)\in E} d(v_i, v_j)}{n(n-1)} \)

Graph degree

  • Outdegree
    • \( deg^+(G) \)
    • Average outdegree of all nodes
  • Indegree
    • \( deg^-(G) \)
    • Average indegree of all nodes

Clustering coefficient

  • Degree of interconnectedness of neighbors
  • \( e(N(v)) \): Number of connections of neighbors of \( v \)
  • \( C(v) = \frac{e(N(v))}{deg^+(v)(deg^+(v)-1)} \)

Random network

  • Generative model
    • Erdös-Rényi random graph
    • Gilbert random graph
  • Examples:
    • Pure peer-to-peer
    • Dynamo with p=1

Erdös-Rényi Graph

  • \( g_{n,m} \) model
  • \( G_{n,m} \) set of all graphs with \( n \) vertices and \( m \) edges
  • Select instance of all graphs \( G_{n,m} \) with equal probability
  • \( |G_{n,m}| = \binom{\binom{n}{2}}{m} \)
  • Generation
    • No suitable
    • Extremely high number of possible graphs (\( |G_{6,6}|=5005 \))

Gilbert graph

  • \( g_{n,p} \) model
  • Edge has probability to be added
    • Probability is fixed
    • Assumption: Edges are independently
  • Useful for generation
  • Construction
    • Start with \( n \) vertices and no edges
    • Add edges iteratively

Asymptotical observation

  • \( n\rightarrow \infty \)
  • Assume \( m = f(n) \)
    • No fixed number of edges
    • New nodes create new connections
  • Gilbert and Erdös-Rényi behave asymptotically equivalent
    • For large number of edges
    • \( \lim\limits_{n \to \infty} \binom{n}{2} p = m \)
  • Graph properties
    • Phase transitions
    • Depend on probability \( p \)
    • Certain properties are extremely probable in certain phase
Connected components
  • Case: \( n*p<1 \)
    • Rarely any component larger than \( O(\log n) \)
    • Mainly unconnected
    • Threshold: \( m\leq 74 \)
  • Case: \( n*p=1 \)
    • Giant Connected component of size \( O(n^{\frac{2}{3}}) \)
    • \( m = 75, n=150, p=\frac{1}{150} \)
    • Appears if \( deg(G) = 1 \) (average node degree)
  • Case: \( n*p>1 \)
    • Only one component
    • Other components at most \( O(\log n) \)
Connectedness
  • Case: \( p<\frac{ln(n)}{n} \): Disconnected
  • Case: \( p>\frac{ln(n)}{n} \): Connected
Degree distribution
  • Modeled by Poisson distribution
  • Node degrees: \( \mathbb{P}(X=k)=\frac{\lambda^k}{k!} e^{-\lambda} \)
  • Expected value: \( E(X) = \lambda \)
  • \( \lambda = (n-1) * p \)
  • Large \( \lambda \): Normal distribution
Diameter
  • \( G \) must be connected
  • High probability: Diameter in \( O(\log n) \)
Clustering coefficient
  • Asymptotically equal to \( p \) for \( n\rightarrow\infty \)
  • With high probability
  • Low clustering coefficient

Small-world network

  • Many naturally networks are robust/efficient
  • Examples:
    • Social network
    • Neural network
    • Citation graph
  • P2P Networks
    • CHORD
    • Kademlia
    • Pastry
    • Symphony
    • Freenet
  • Six degrees of separation
    • 1967: Stanley Milgram
    • Task: Send letter from Kansas to Massachusetts
    • Observation: Only 6 mediators on average
    • Called small-world graph
    • First steps: Geographically largest
    • Later steps: Closing to target
  • Observation of natural networks
    • Power law degree distribution
    • High average cluster coefficients
    • Low average path length
  • Definition Small-world graph
    • Graph with dense local structure
    • Diameter comparable to random graph \( O(\log n) \)
    • Homogeneous node degree

Watts-Strogatz graph

  • Generative model for small-world graphs
  • Properties
    • Low average path length \( O(\log n) \)
    • High average cluster coefficient
    • Homogeneous node degree
  • Generation
    • Formalization
      • \( g_{ws; n,k,p} \)
      • \( n \): Number of nodes
      • \( k \): Neighborhood degree
      • \( p \): Rewrite probability
    • Build ring of \( n \) vertices
    • Connected each vertex with its \( k \) predecessors
    • Rewrite edge with probability \( p \) (keep source, select new target)
  • Properties
    • Case: \( p\rightarrow 0 \)
      • Clustering coefficient: \( C=\frac{3}{4}, p\rightarrow 0 \)
      • Diameter: \( O(n) \)
    • Case: \( p\rightarrow 1 \)
      • Regular random graph
      • Clustering coefficient \( C=\frac{k}{n} \)
      • Diameter \( O(\log n) \)
    • Node degree:
      • Homogeneous
      • Low variance
    • Clustering coefficient
      • Homogeneous
      • Higher than random

Kleinberg Navigation Model

  • Small-world routing
  • Idea:
    • Find short paths in distributed fashion in small-world?
    • Use heuristics (no flooding, too expensive)
    • Provide additional routing information
  • Formalization
    • Toroidal grid in d-dimensional space
    • Each node gets position \( pos(v)\in \mathbb{N}^d \)
    • Distance \( d_M(v,w) \) is Manhatten distance (important because of integer-hops)
    • Probability of edges depends on distance
      • \( P(v,w) \sim d_M(v,w)^{-\alpha} \)
      • Inverse power law
    • Important: \( \alpha = d \)
      • Arbitrary path length: \( O(\log n) \)
      • Case: \( \alpha < d \): Too few links
      • Case: \( \alpha > d \): Too many links, random walk
  • Result
    • Node connected to neighbors
    • Some long-range links to randomly chosen node
  • Mapping
    • Geographical location

Scale-free network

  • Naturally occurring
    • Large infrastructure
    • Strong hub-topology
    • Power grid
    • Internet
  • Examples:
    • Gnutella 0.4 (connect neighborhood, prefer strong nodes)
    • CAN
  • Definition scale-free graph
    • Graph with power-law node degree distribution
  • Properties
    • Most nodes have small degree
    • Few nodes have extremely high node degree (hubs)
    • Robustness against random failure (random node hits low-degree node)
    • Sensitive against attacks (Hub attack can harm network)
  • Formalization
    • Probability, that node connects to \( k \) other nodes:
    • \( P(k) \sim k^{-\gamma}, 2<\gamma\leq 3 \)

Barabási-Albert graph

  • Generational model for scale-free graphs
  • Formal
    • \( g_{ba; n,m} \)
    • \( n \): Number of nodes
    • \( m \): Number of edges per timestep
  • Initial graph:
    • \( n_0 \geq 2 \) nodes
    • \( deg(v) \geq 1 \)
  • Discrete time modeling
    • In each step, add a node
    • Connect new node to \( m \) other nodes
    • Stop when graph contains \( n \) nodes
  • Preferential attachment
    • Edges are added to higher-degree nodes
    • Probability
      • \( \Pi(v) \sim deg(v) \)
      • \( \Pi(v) = \frac{deg(v)}{\sum_{w\in V} deg(w)} \)

Comparison

  • Node degree
    • Random: Low
    • Small-world: Homogeneous
    • Scale-free: Power-law, hubs visible
  • Cluster coefficient
    • Random: Low
    • Small-world: Homogeneous
    • Scale-free: Power law, lower than small-world

Swarming

  • Scenario: Distribute large amounts of data
  • Early approach: Download complete file directly from peer
  • Problems:
    • Low reliability (connection problems, re-download)
    • Poor performance (asymmetric upload/download rate)
    • No load distribution (popular files high demand, low download speed)
  • Solution: Swarming strategy
  • Example: BitTorrent, Avalanche

Swarming strategy

  • Defintion Chunk
    • Split large files into chunks
    • Use hash value for identification and transfer protection (checksum)
  • Defintion Swarm
    • Group of nodes (seeder + leecher) that share a torrent
  • Parallelization
    • Download chunks from different sources simultaneously
  • Advantages
    • Increase throughput (use upload-rate from different nodes)
    • Resilient (peer failure no problem)
  • Important aspects
    • Chunk selection (Order of chunk selection, keep throughput high)
    • Fairness
      • Ensure fair usage
      • Avoid free-riding (peer should contribute)
      • Bandwidth balancing (no idling peers)

DETOUR: Game Theory

  • Theory of strategic behavior
  • Players maximize their gains
  • Application
    • Modern economics
    • Decision theory
    • Multi-agent systems
  • Neumann/Morgenstern
    • Zero-sum game (summarized outcomes are zero)
  • John Nash
    • Non-zero-sum game
    • Nash equilibrium (1950)
      • No player gains advantage when changing strategy
      • Knowing other players strategy
  • Harsayi/Selten
    • Incomplete information
  • Dominant strategy (strategy independent on opponent’s strategy)
  • Example: Prisoners Dilemma

BitTorrent

  • Protocol for swarming file distribution
  • Goal: decentrally/quickly distribute content
  • Questions:
    • Which chunk to download next?
    • Which peer to select for downloading/uploading?

Architecture

  • Components
    • Torrent site
      • Web server for search
      • Torrent: Available content, contains metadata
    • Tracker
      • Peer coordination
      • Centralized service maintaining the peer swarm
  • Chunks
    • Size: 32 KB - 4 MB
    • Identification: SHA-1 (160 bit)
  • Role of peers
    • Seeder (have all chunks, upload to swarm)
    • Leecher (have not all chunks, download from swarm, upload to swarm)
  • Torrent file
    • Tracker URL(s)
    • File name(s)
    • File length
    • Chunk size / piece length
    • SHA-1 hash of chunks (for integrity check)
    • Creation data
    • Info hash (uniquely identify torrent)

Workflow

  1. Search for torrent file (on torrent site)
  2. Connect to tracker (URL in torrent file)
  3. Join swarm (register with tracker and torrent)
  4. Receive list of peers with the torrent
  5. Connect to peers from the swarm (receive list of chunks)
  6. Download chunks

Chunk selection

  • Question: Which chunk to download next?
  • Priority actives (finish active chunks?)
  • Rarest first (improve availability of rare chunks)
  • Random first piece (get first chunk quickly to contribute)
  • Endgame mode (request last chunks from all peers to finish quickly)

Peer selection

  • Goals:
    • Avoid free-riding
    • Optimally use available resources
    • Reward cooperation
  • Issues:
    • Seeder: Who gets the chunk?
    • Leecher: From whom to download chunk?
  • Strategy: Tit for tat (“Zug um Zug”)
  • Implementation: Choking-mechanism
Tit for tat
  • From Game Theory
  • Strategy for repeated games
    • A initially cooperates
    • If B was cooperative, A is cooperative
    • If B wasn’t cooperative, A isn’t cooperative
  • Conditions
    • Agent cooperates unless provoked
    • If agent is provoked, agent retaliates
    • Agent forgives quickly
    • Repeated game
Choking as leecher
  • Mechanism for “Tit for tat” strategy
  • Idea:
    • Prefer bi-directional communication channels (i.e., upload to peers which offer chunks)
    • Prevent free-riding (punish peers which don’t upload)
  • Leecher exchanges missing chunks with another peer
  • Choke peer if it doesn’t upload for one minute
    • Refuse upload to peer
    • Keep downloading
    • Keep TCP connection open (no costs, congestion control)
  • Problem: Swarm health
    • New leechers instantly choked (due to no upload)
    • Peer choked due to network failures
  • Solution: Optimistic Unchoking
    • Randomly start uploading to a new/unconnected leecher
    • Randomly unchoke a choked connection (let peers return to swarm)
    • Anti-snubbing: Initiate a lot of unchoking connections (if previously choked by all peers)
Seeding policy
  • Problem: Limited upload-capacity
  • Question: Which peer to upload to?
  • Upload to peers with best upload/download ratio (peer with high ratio has download capacity)
  • Idea:
    • Ensure faster replication of chunks
    • Improve bandwidth usage
  • Problem: upload/download ratio hard to estimate
    • Central bookkeeping
    • Bookkeeping on own measures
    • Issue: Cheating?

Decentralized tracker

  • Problems centralized tracker:
    • Single Point of Failure
    • Single Point of Attack
    • Scalability (e.g., PirateBay tracker overloaded, 5 mio. peers)
  • Solution: Decentralized Tracker (use DHT)
  • Example: Kademlia
  • Node may join the DHT tracker (compatible client)
  • Mapping: Infohash to swarm peer list

Multi-tracker

  • Goal:
    • Increase performance
    • Increase resilience of torrent
  • Solution: Use multiple trackers
  • Optimal case: Multiple trackers specified in torrent file
  • Complex case: Peer Exchange (PEX)
    • Ask every peer in swarm for additional trackers

Anonymity

  • Problem: BitTorrent not anonymous
    • Peer list, IP address, port, upload/download-ratio
    • Track user behavior (privacy problem)
    • Legal issues
  • Problem: Real anonymity complicated (communication must be known)
  • Solution: Dark nets
    • Limit number of known nodes to trusted nodes (friend nodes)
    • Only communicate to friends
    • Friends forward any message anonymously to their friends (friend-to-friend routing)
  • Systems
    • Freenet (pure P2P, small-world, anonymous routing)
    • OneSwarm (BitTorrent extension, friend-to-friend routing)
  • Friend-to-friend routing
    • Request failed message: TTL expires or no neighbors
    • Success message: File is replicated on routing nodes, sending node’s address stored in routing table because pure P2P
    • Full routing table is full: Evict entries (Least-recently used strategy)

LOCKSS

  • Lots of copies keep stuff safe
  • Used by libraries
  • Goals:
    • Disaster-proof long-term preservation of digital content
    • Access and preservation of digitally replicable material
  • Idea: Distribute copies over network (easy access)
  • Dissemination to an archive:
    • Archives contain items which are hard to replicate
    • Archives have strong access control to ensure preservation
  • Central question:
    • Ensure that copies are not compromised and never lost?
  • Solution: P2P audit/repair protocol

Design goals

  • Affordability (cheap hardware, open-source, low administration)
  • High data resilience (replication)
  • Scalability (to rates of publishing)
  • Accessibility (allow search)

Architecture

  • Globally distributed P2P (hosted by libraries)
  • Commodity hardware / reduce maintenance costs
  • Replicate content (reduce correlations between sites)
  • Audit replicas proactively (detect damage)
  • Regularly migrate content (new hardware, new formats)
  • Avoid external dependencies (vendor, DRM)
  • Plan for data exit (?)

Issues with long term storage

  • Large-scale disaster
  • Non-technical faults
    • Human error
    • Economic faults
    • Organized attack
  • Technical problems
    • Media faults
    • Component faults
    • Hardware wear
    • Software/format wear
    • Lost context/metadata

Audit/repair protocol

  • Goal: Make it hard to change consensus of population
  • Workflow
    • Runs between peers (each peer is poller/voter)
    • Peer periodically audits own content
      • Run more frequently than hardware failure
      • Check integrity
      • Opinion poll to other peers every three months
      • Get repair from other peers
    • Raise alarm if attack detected (correlated failures, IP address spoofing, system slowdown)
    • Peer contains list of peers which share documents
    • Periodically start poll (send document hash to subset of peers)
    • Compare votes
      • Agreement (70%)
      • Disagreement (30%): Repair
      • 30 % to 70 %: Alarm
    • Re-poll after repair
  • Probability of irrecoverable damage
    • Up to 35 % for 40 % of damaged peers

Special purpose databases

  • Problem with all-purpose databases
    • Massive high query load (limited scaling)
    • Global application (latency, data should be close to users)
    • High availability constraint (hot-standby not enough)
  • Query types
    • OLTP
    • OLAP
  • NoSQL systems

OLTP

  • OnLine Transaction Processing
  • Business backend-data storage
  • Focus on data entry/retrieval
  • Usually prepared statements
  • High transaction load
  • Small transaction

OLAP

  • OnLine Analytical Processing
  • Business Intelligence queries
  • Load transaction load
  • Big transaction (complex, multi-dimensional)
  • High runtime

NoSQL systems

  • Principle: KISS (Keep it stupid simple)
  • Possible features
    • Massive scaling
    • Massive distribution
    • Extreme high availability
    • Extreme high OLTP performance
  • Sacrifices
    • Not all-purpose
    • No relational model
    • Relaxed ACID
    • No SQL
    • No typical query interfaces (JDBC)
  • Base motivations
    • Extreme requirements
    • Alternative data model
    • Alternative implementation
  • Trends
    • Distribute single-thread minimum-overhead shared-nothing parallel main-memory database (OLTP, VoltDB)
    • Sharded row store (OLAP, MySQL Cluster, Greenplum)

Extreme requirements

  • Extreme availability (using global replication)
  • Guaranteed low latency (data should be close to users)
  • Extremely high throughput (e.g., Amazon four million checkouts during holidays)

Alternative data model

  • Origin of NoSQL (from community)
  • Idea: Simple data model improves performance
  • Document store
    • Consists of multiple key-value pairs and a payload
    • Example: CouchDB, MongoDB
    • Interface: low-level, one-record-at-a-time
  • Key-value store
    • Each record is key-value pair
    • Simple get- and put-operations
    • Usually used on distributed hash table
    • Example: MemcacheDB + Amazon Dynamo
    • Interface: low-level, one-record-at-a-time
  • XML store
  • RDF store
  • Object-oriented store

Alternative implementation

  • OLTP overhead reduction
  • Idea: Avoid overhead (classic OLTP has a lot of overhead)
  • Overhead
    • Logging (17 %, log forced, duplicate writing)
    • Locking (21 %, ensure consistency, transaction must wait)
    • Latching (19 %, update to shared data structure, short-term lock)
    • Buffer management (35 %, receive block from disk)