Peer-to-Peer Networks ●● Distributed algorithms for p2P ●●●● Distributed hash tables ●●0 0●●● P Felber Pascal. Felberd eurecom fr
Peer-to-Peer Networks Distributed Algorithms for P2P Distributed Hash Tables P. Felber Pascal.Felber@eurecom.fr http://www.eurecom.fr/~felber/
●●●● ●●●● ●●●● ●●●● Agenda ●●●● ●●●● o What are dhTs? Why are they useful? What makes a good dht design ● Case studies Chord ● Pastry(ocat!y) TOPLUS( topology-awareness) What are the open problems? Peer-to-Peer Networks -P. Felber
Peer-to-Peer Networks — P. Felber 2 Agenda ⚫ What are DHTs? Why are they useful? ⚫ What makes a “good” DHT design ⚫ Case studies ⚫ Chord ⚫ Pastry (locality) ⚫ TOPLUS (topology-awareness) ⚫ What are the open problems?
●●●● ●●●● ●●●● ●●●● What is p2P? ●●●● ●●●● A distributed system architecture o no centralized control e Typically many nodes, but unreliable and heterogeneous Nodes are symmetric in function Internet ake advantage of distributed shared resources (bandwidth, CPU, storage)on peer-nodes Fault-tolerant, self-organizing ● Operate in dynamic environment, frequent join and leave is the norm Peer-to-Peer Networks -P. Felber
Peer-to-Peer Networks — P. Felber 3 What is P2P? ⚫ A distributed system architecture ⚫ No centralized control ⚫ Typically many nodes, but unreliable and heterogeneous ⚫ Nodes are symmetric in function ⚫ Take advantage of distributed, shared resources (bandwidth, CPU, storage) on peer-nodes ⚫ Fault-tolerant, self-organizing ⚫ Operate in dynamic environment, frequent join and leave is the norm Internet
●●●● ●●●● ●●●● ●●●● P2P Challenge: Locating Content0000 Who has have it this paper? I have it Simple strategy: expanding ring search until content is found If r of N nodes have copy, the expected search cost is at least N/r, i.e., O(N) Need many copies to keep overhead smal Peer-to-Peer Networks -P. Felber
Peer-to-Peer Networks — P. Felber 4 P2P Challenge: Locating Content ⚫ Simple strategy: expanding ring search until content is found ⚫ If r of N nodes have copy, the expected search cost is at least N / r, i.e., O(N) ⚫ Need many copies to keep overhead small Who has this paper? I have it I have it
●●●● ●●●● ●●●● ●●●● Directed searches ●●●● ●●●● o Idea Assign particular nodes to hold particular content (or know where it is) o When a node wants this content, go to the node that is supposes to hold it (or know where it is ● Challenges Avoid bottlenecks: distribute the responsibilities evenly' among the existing nodes o Adaptation to nodes joining or leaving(or failing Give responsibilities to joining nodes Redistribute responsibilities from leaving nodes Peer-to-Peer Networks -P. Felber
Peer-to-Peer Networks — P. Felber 5 Directed Searches ⚫ Idea ⚫ Assign particular nodes to hold particular content (or know where it is) ⚫ When a node wants this content, go to the node that is supposes to hold it (or know where it is) ⚫ Challenges ⚫ Avoid bottlenecks: distribute the responsibilities “evenly” among the existing nodes ⚫ Adaptation to nodes joining or leaving (or failing) ⚫ Give responsibilities to joining nodes ⚫ Redistribute responsibilities from leaving nodes