CS433/533 Computer NetworksOutlineRecap: Two ProblemsRecap: The Lookup Problem (A Data Centric Internet)Recap: Unstructured P2PRecap: FreenetUnderstanding Freenet Self-Organization: Freenet GraphExperiment: Freenet Graph: InitExample: Search EffectExperiment: Evolution of Freenet GraphFreenet Evolves to Small-World NetworkSmall-WorldThe Computer Networks Distributed Search QuestionWhat Should the Long-Distance Links Look?Slide 15Slide 16Distributed SearchSmall WorldFreenet: IssuesSummaryDistributed Hash Tables (DHT): HistoryDHT: OverviewDHT ApplicationsDHT: Basic IdeaDHT: Basic Idea (2)DHT: Basic Idea (3)DHT: Basic Idea (4)DHT: Basic Idea (5)DHT: APISlide 30Key Design Issues in each DHTPowerPoint PresentationCANCAN Example: Two Dimensional SpaceSlide 35Slide 36Slide 37Slide 38CAN Insert: Example (1)CAN Insert: Example (2)CAN Insert: Example (3)CAN Insert: RoutingCAN Insert: Example (4)CAN Retrieve: ExampleSlide 45CAN Insert: Join (1)CAN Insert: Join (2)CAN Insert: Join (3)CAN EvaluationsSlide 50ChordChord: Storage using a RingHow to Search: One ExtremeHow to Search: the Other ExtremeChord Solution: “finger tables”Joining the RingDHT: Chord Node JoinSlide 58Slide 59Slide 60Slide 61Slide 62DHT: Chord Insert ItemsDHT: Chord RoutingChord/CAN SummaryThere are other DHT algorithmsSummary: DHTSummary: the Lookup ProblemSlide 69An Upper Bound on ScalabilityThe Scalability ProblemTheoretical Capacity: upload is bottleneckWhy not Building the Trees?Key Design IssuesDiscussion: How to handle the issues?Slide 76BitTorrentSlide 78Slide 79BitTorrent: LookupMetadata (.torrent) File StructureTracker ProtocolSlide 83Slide 84Piece-based SwarmingDetail: Peer ProtocolPeer RequestKey Design PointsRequest: Block AvailabilityBlock Availability: RevisionsBitTorrent: UnchokeOptimistic UnchokingBitTorrent Fluid AnalysisSystem EvolutionSystem Evolution: Download Time TBitTorrent: SummarySummary: P2POptional SlidesSkip ListForward Web Proxy/CacheAside: Search Time?Aside: All Peers Equal?Aside: Network ResilienceCS433/533Computer NetworksLecture 14Structured P2P (DHT) and BitTorrent2/23/20121OutlineAdmin and recapoP2P networksoThe lookup problemoUnstructured P2PoStructured P2PoThe scalability problem23Recap: 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 authenticityedge. serversC0client 1client 2client 3client nDNSoriginRecap: The Lookup Problem (A Data Centric Internet)InternetN1N2N3N6N5N4PublisherKey=“title”Value=MP3 data…ClientLookup(“title”)?find where a particular file is stored5Recap: Unstructured P2P Napstercentral query server; distributed data serverGnutelladecentralized, floodingFreenetsearch by routing6Recap: 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 itself7Understanding 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……8Experiment: 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 = 125i-2 i-1 i i+1i+2id next_hop file……9Example: 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 linksi-2 i-1 i i+1i+2id next_hop file……10Experiment: 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 keyEvolution of path length and clustering;Clustering is defined as percentage of local links11Freenet 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 file12Small-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 !13The 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 difftypes of links.Q: what is a good alpha?14What 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 2Da1aDa2aDa3aDana15What Should the Long-Distance Links Look?16What 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 search17Distributed SearchIn the general case, α