1.3 P2P Systems
- Why study P2P systems?
- P2P systems are the first distributed systems that seriously focused on scalability (w.r.t #nodes)
- P2P techniques abound in cloud computing systems. E.g., key-value stores use Chord p2p hashing (consistent hashing)
- When users upload files, the files are stored at client machines ("peers")
- The Napster servers store directory information (a list of <filename, ip_addr, port_num>)
- Napster search
- Client sends server keywords to search with
- Server searches (using ternary tree algorithm) and returns a list of hosts <ip_addr, port_num> to client
- Client pings each host in the list to find transfer rates
- Client fetches file from best host
- All communication uses TCP
- Joining a P2P system
- Send an HTTP request to a well-known URL for that P2P service
- Message routed to introducer, a well-known server that keeps track of some recently joined nodes in P2P system
- Introducer initializes new peer's neighbor table
- Problems
- Central servers: source of congestion/single point of failure
- No security: plain messages and passwords
- Indirect infringement: responsible for users' copyright violation
Napster structure
- Different from Napster, Gnutella eliminates the servers and have clients act as servers (servents), such that client machines search and retrieve amongst themselves
- In the overlay graph (overlay in the sense that it is overlayed on top of the internet), peers being neighbors means that they know about each other's ip addr and port num, and can send them messages
- Gnutella routes different messages within the overlay
- There are five main message types in the Gnutella protocol
- Query (search)
- Queries are flooded out (forwarded to all peers except the peer from which the Query was received), TTL-restricted, and are forwarded only once
- QueryHit (response to query)
- A QueryHit messages contains:
- Info about responder: <port, ip_addr, speed>
- Results: <fileindex, filename, fsize>
- servent_id: Unique identifier of responder (a function of its ip addr)
- QueryHits are reverse-routed: If A sends B a Query and B got a hit, B sends to A a QueryHit
- Push (used to initiate file transfer)
- After QueryHits are received, the requestor chooses the "best" responder, and then initiates HTTP request directly to responder's ip_addr:host
- IRL, responders may be behind firewalls that rejects incoming connections
- If a HTTP request fails, it routes a Push message via links in the overlay. The Push message contains ip_addr:host at which the requestor can accept incoming connections. When the peer receives this Push message, it can generate an outgoing TCP connection (sends GIV, receives GET)
- If the requestor is also behind a firewall, Gnutella gives up
- Alternative: use a modified version of Gnutella to transfer the file via the overlay links themselves (this might be slow)
- Ping (to probe network for other peers)
- Peers initiate Pings periodically, and Pings are flooded out
- Pong (reply to ping, contains address of another peer)
- Pongs are routed along reverse paths
- Pongs are used to keep neighbor lists fresh in spite of peers joining, leaving, and failing
- Problems
- Ping/Pong constitute 50% of the traffic
- Solutions: Multiplex, cache, and reduce frequency
- Repeated searches with same keywords
- Solutions: Cache query, QueryHits
- Modem-connected hosts do not have enough bandwidth for passing Gnutella traffic
- Solution: Use a central server to act as proxy for such peers
- Another solution: FastTrack
- Large number of freeloaders (only download files, never upload files)
- In 2000, 70% of the users are freeloaders
- Flooding causes excessive traffic
- To maintain meta info about peers in order for more intelligent routing, use structures P2P systems (e.g., Chord)
Gnuteella message header format
- Hybrid between Napster and Gnutella, takes advantages of "healthier" participants in the system
- Like Gnutella, but designate some peers as "supernodes"
- A supernode stores a directory listing a subset of nearby <filename, peer pointer> (similar to Napster servers)
- Supernode membership changes over time
- Any node may become a supernode, provided it has earned enough reputation
- E.g., reputation is affected by length of periods of connectivity and total number of uploads
- A peer searches by contacting a nearby supernode
FastTrack structure
- Files are split into blocks (32KB - 256KB)
- Download Local Rarest First block policy: Prefers early download of blocks that are least replicated among neighbors
- Tit for tat bandwidth usage: Provide blocks to neighbors that provided it the best download rates
- Incentivizes nodes to provide good download rates
- Choking: Limit number of neighbors to which concurrent uploads <= a number (5), i.e. the best neighbors. Everyone else is choked
- Prevents overloading of the upload bandwidth
- Periodically (e.g., 10s) re-evaluate this set
- Optimistic unchoke: Periodically (e.g., 30s) unchoke a random neighbor to keep the unchoked set fresh
BitTorrent structure
- Distributed hash tables: objects = files
- Performance concerns
- Load balancing
- Fault tolerance
- Efficiency of lookups and inserts
- Locality
- Napster, Gnutella, and FastTrack are all DHTs
- Chord: Consistent hashing on nodes' addresses
- SHA-1(ip_addr, port) -> 160-bit string, truncated to m bits -> peer id
- Each node stores peer pointers
- Successors
- Finger tables
- Used for routing queries quickly
Comparative performance
Finger tables
- Consistent hashing: With K keys and N peers, each peer stores O(K/N) keys
- Storing files
- Filenames are also mapped using the same consistent hash function
- File is stored at first peer with id greater than or equal to its key (mod 2^m)
- Searching files
- Takes O(log(N)) time
Chord searching
- Solution 1: Maintain multiple (2log(N)) successor entries
Yes, more math
- Solution 2: Replicate file/key at r successors and predecessors
- Dealing with dynamic changes (P2P systems have a high rate of churn: peers joining, leaving, and failing)
- Stabilization protocol is run by all nodes periodically (talk to neighbors to update finger table)
- New peers may need to copy some files/keys from other nodes
- A new peer affects O(log(N)) other finger entries in the system
- Number of messages per peer join = O(log(N) * log(N))
- Concurrent peer joins/leaves/failures
- Chord peers periodically run a stabilization algorithm that checks and updates pointers and keys, which ensures non-loopiness
- Hash can get non-uniform -> bad load balancing
- Solution: Virtual nodes (treat each node as multiple virtual nodes behaving independently)
- Just like Chord, assigns ids to nodes using a virtual ring
- Leaf set: Each node knows its successors and predecessors
- Routing table: Instead of "n+2^i" rule in Chord, use prefix matching -> log(N)
- Consider a peer with id 01110100101. It maintains a neighbor peer with an id matching each of the following prefixes: {*, 0*, 01*, 011*, ..., 0111010010*}
- For each prefix, among all the potential neighbors, the neighbor with the shortest RTT is selected
- Early hops/shorter prefixes have many more candidates -> likely to be closer -> hops are short, yet overall stretch (compared to direct Internet paths) stays short
- When it needs to route to a peer (e.g., 01110111001), it forwards to a neighbor with the largest matching prefix (011101*)
- Problems
- O(log(N)) lookup hops may be high
- Constant lookup cost to DHT
- Instead of virtual rings, we use k (~= sqrt(N)) affinity groups
- Each node is hashed (mod k) to a group
- A peer is neighbors with all other nodes in its affinity group
- Files are stored at whichever node uploaded them
- Kelips decouples file replication/location from querying
- Each filename hashed to a group
- All nodes in the group replicate pointer information (i.e., <filename, location>)
- Lookup
- Find affinity group
- Go to your contact for the file affinity group
- If fails, try another neighbor to find a contact
- Lookup = 1 hop (or a few under failures)
- Memory cost: O(sqrt(N))
- 1.93MB for 100K nodes, 10M files
Kelips structure
Kelips soft state
- Chord & Pastry & Kelips
- Range of tradeoffs (memory vs. lookup cost vs. background bandwidth (in order to keep neighbors fresh))
- Chord & Pastry use O(log(N)) for both memory & lookup
- Kelips uses more memory (O(N^2)) & background bandwidth to provide O(1) lookup
- All of them have provable properties
Hi, I have a question regarding question 8 in HW 3. My reasoning is as follows. Going down, we have 3 at level 3, 9 at level 4, 27 at level 5, making a total of 39. Going up, we have 1 at level 1, 2 at level 2, 6 at level 3, making a total of 9. Adding them up, it should be 48. I would appreciate it if someone can point out the mistake in my reasoning. Thanks in advance!To provide more context, the question is:A Gnutella topology looks like a balanced ternary tree with 4 levels of nodes, i.e., peers, as shown in the picture below. Thus, there is 1 root at Level 1, which has 3 children at Level 2, which each have 3 children at Level 3, which in turn each have 3 children at Level 4 – thus, there are a total of 40 nodes. If a child of the root (i.e., a Level 2 node in the tree) sends a Query message with TTL=3, then what are the number of nodes receiving the Query message, not including the originating node? Enter your answer as a numeric value in the text box below. (1 point)