CS433/533 Computer Networks Lecture 14 Structured P2P (DHT) and BitTorrent 2/23/2012 1Outline q Admin and recap o P2P networks o The lookup problem o Unstructured P2P o Structured P2P o The scalability problem 23 Recap: Two Problems ❒ The scalability problem ❍ How to use the resources (storage and bandwidth) of individual clients to improve scalability/robustness ❒ The lookup problem ❍ More generally, moving from a host-centric Internet to a “data-centric” Internet supporting data persistency, availability, and authenticity edge. servers C0 client 1 client 2 client 3 client n DNS originRecap: The Lookup Problem (A Data Centric Internet) Internet N1 N2 N3 N6 N5 N4 Publisher Key=“title” Value=MP3 data… Client Lookup(“title”) ? find where a particular file is stored5 Recap: Unstructured P2P ❒ Napster ❍ central query server; distributed data server ❒ Gnutella ❍ decentralized, flooding ❒ Freenet ❍ search by routing6 Recap: Freenet ❒ Query using routing ❍ Distributed DFS search guided by closeness to target key ❒ Integration of query and caching ❍ adaptive to usage patterns • popular data will be transparently replicated and will exist closer to requestors ❍ as nodes process queries, connectivity increases ❍ free speech: attempts to discover/supplant existing files will just spread the files ! ❒ Provide publisher anonymity ❍ each node probabilistically replaces originator with itself7 Understanding Freenet Self-Organization: Freenet Graph ❒ We create a Freenet reference graph ❍ creating a vertex for each Freenet node ❍ adding a directed link from A to B if A refers to an item stored at B id next_hop file … …8 Experiment: Freenet Graph: Init - Assume a network of n=1000 nodes, with node id 0 to 999 - Each node can store 50 data items, and 200 references - Assume initially each node i has item i, and knows the storage of i – 2, -1, i + 1, i + 2 (all mod 1000) - thus a regular, locally-clustered graph with avg path length: n / 8 = 1000/8 = 125 i-2 i-1 i i+1 i+2 id next_hop file … …9 Example: Search Effect - What is the effect that if the first search is node 0 searching for item 490 (assume no probabilistic replacement to hide origin)? - Nodes 0, 2, 4, 6, …, 488 all cache item 490, and has a pointer to node 490 - The search forms many long-distance links i-2 i-1 i i+1 i+2 id next_hop file … …10 Experiment: Evolution of Freenet Graph ❒ At each step ❍ pick a node randomly ❍ flip a coin to determine search or insert • if search, randomly pick a key in the network • if insert, pick a random key Evolution of path length and clustering; Clustering is defined as percentage of local links11 Freenet Evolves to Small-World Network ❒ With usage, the regular, highly localized Freenet network evolved into one irregular graph ❒ High percentage of highly connected nodes provide shortcuts/bridges ❍ make the world a “small world” ❍ most queries only traverse a small number of hops to find the file12 Small-World ❒ First discovered by Milgrom ❍ in 1967, Milgram mailed 160 letters to a set of randomly chosen people in Omaha, Nebraska ❍ goal: pass the letters to a given person in Boston • each person can only pass the letter to an intermediary known on a first-name basis • pick the person who may make the best progress ❍ result: 42 letters made it through ! ❍ median intermediaries was 5.5---thus six degree of separation ❍ a potential explanation: highly connected people with non-local links in mostly locally connected communities improve search performance !13 The Computer Networks Distributed Search Question ❒ Question: what kind of long distance links to maintain so that distributed network search is effective? ❒ Assume that each node has ❍ a fixed # (say p distance away) local links ❍ a small # (say a total of q) long-distance links s.t. the probability of a link between nodes x and y is some (α) inverse-power of the distance d(x, y) of x and y ❍ Different alpha’s give diff types of links. ❍ Q: what is a good alpha?14 What Should the Long-Distance Links Look? ❒ Consider the simple case of one dimensional space. ❒ Which alpha leads to best performing distributed search alg? 0 1 2 n 2 Δα1αΔα2αΔα3αΔαnα15 What Should the Long-Distance Links Look? 0.0001$0.001$0.01$0.1$1$1$ 3$ 5$ 7$ 9$ 11$ 13$ 15$ 17$ 19$ 21$ 23$ 25$ 27$ 29$ 31$ 33$ 35$ 37$ 39$ 41$ 43$ 45$ 47$ 49$ 51$a=0.5$a=2$a=1$16 What Should the Long-Distance Links Look? ❒ For 1-d space, for any distributed algorithm, the expected # of search steps, for different α’s: ❍ 0 ≤α < 1 : ≥ k1n(1-α)/2 ❍ α > 1 : ≥ k1n(α-1)/α ❍ α = 1 : O(log2n) greedy search17 Distributed Search ❒ In the general case, α should be the dimension ❒ In other words, a guideline on long-distance links: roughly the same number of nodes in each region A1, A2, A4, A8, where A1 is the set of nodes who are one lattice step away, A2 is those two steps away, A4 is four steps away… probability is proportional to (lattice steps)-d18 Small World Saul Steinberg; View of World from 9th Ave19 Freenet: Issues ❒ Does not always guarantee that a file is found, even if the file is in the network ❒ Good average-case performance, but a potentially long search path in a large network ❍ approaching small-world…20 Summary ❒ All of the previous p2p systems are called unstructured p2p systems ❍ Napster (central query server) ❍ Gnutella (decentralized, flooding) ❍ Freenet (search by routing) ❒ Advantages of unstructured p2p ❍ algorithms tend to be simple ❒ Disadvantages ❍ hard to make performance guarantee ❍ failure even when files existDistributed Hash Tables (DHT): History ❒ Academic researchers jumped on to the p2p bandwagon after unstructured p2p ❒ Motivation: ❍ frustrated by popularity of all these “half-baked” P2P apps. We can do better! (so they said) ❍ guaranteed lookup success for data in system ❍ provable bounds on search time ❍ provable scalability to millions of node22 DHT: Overview DHT Distributed application get (key) node node node …. put(key, data) ❒ Abstraction: a