The Search/Discovery ProblemDesign GoalsSpectrum of “Purity”MetricsP2P File-sharingNapsterNapsterNapsterGnutellaGnutellaGnutellaGnutellaCurrent Techniques: Gnutella: Breadth-First Search (BFS)Iterative DeepeningIterative DeepeningDirected BFSDirected BFSDirected BFS: HeuristicsLocal IndicesLocal Indices (r=1)Distributed Hashing — General ApproachDistributed Hashing — General ApproachDistributed Hashing — General ApproachChord - Basic IdeaChord - Basic IdeaChord - Basic IdeaChord: ResolutionChord: PerformanceCAN: Basic IdeaCAN: Basic IdeaCAN: simple exampleCAN: simple exampleCAN: simple exampleCAN: simple exampleCAN: simple exampleCAN: simple exampleCAN: routing tableCAN: routingCAN: node insertionCAN: node insertionCAN: node insertionCAN: node insertionCAN: node insertionCAN: node failuresCAN: scalabilitySummary9/12/2002 Internet and Grid Computing - Fall 20021Search/Discovery (and Insertion) in Distributed SystemsLecture Coverage1. Survey of Approaches2. Napster/Gnutella3. Distributed Hash Table Based Systems1. Chord2. Can3. Freenet4. Semantic (keyword search)5. Topology Aware Routing and SearchAssumed KnowledgePublic Key EncryptionHashing Algorithms9/12/2002 Internet and Grid Computing - Fall 20022Search/Discovery (and Insertion) in Distributed SystemsThe Search/Discovery Problem• “Location Resolution”Given an object (might be name, attribute, or even content)Return a channel to a node (peer) that hasthat object• Approaches:– Centralized Index (Napster)– Broadcast information to be resolved (Gnutella)– Search Strategies– Distributed Hashing9/12/2002 Internet and Grid Computing - Fall 20023Search/Discovery (and Insertion) in Distributed SystemsDesign Goals• Scalability• Low latency (efficient resolution)• Load balancing• Completely distributed/self-organizing• Robust• Deployable•Simple9/12/2002 Internet and Grid Computing - Fall 20024Search/Discovery (and Insertion) in Distributed SystemsSpectrum of “Purity”• Hybrid– Centralized index, P2P file storage and transfer• Super-peer– A “pure” network of “hybrid” clusters•Pure– functionality completely distributed9/12/2002 Internet and Grid Computing - Fall 20025Search/Discovery (and Insertion) in Distributed SystemsMetrics• Cost (aggregate)– Bandwidth– Processing Power• Quality of Results– Number of results– Satisfaction (true if # results >= X, false otherwise)– Time to satisfaction9/12/2002 Internet and Grid Computing - Fall 20026Search/Discovery (and Insertion) in Distributed SystemsP2P File-sharing• Napster– Decentralized storage of actual content• transfer content directly from one peer (client) to another – Centralized index and search• Gnutella– Like Napster, with decentralized indexing– Search via flooding– Direct download9/12/2002 Internet and Grid Computing - Fall 20027Search/Discovery (and Insertion) in Distributed SystemsNapsterxyz.mp3, 128.1.2.3)(128.1.2.3Central Napster server9/12/2002 Internet and Grid Computing - Fall 20028Search/Discovery (and Insertion) in Distributed SystemsNapsterxyz.mp3 ?128.1.2.3128.1.2.3Central Napster server9/12/2002 Internet and Grid Computing - Fall 20029Search/Discovery (and Insertion) in Distributed SystemsNapster128.1.2.3xyz.mp3 ?Central Napster server9/12/2002 Internet and Grid Computing - Fall 200210Search/Discovery (and Insertion) in Distributed SystemsGnutella9/12/2002 Internet and Grid Computing - Fall 200211Search/Discovery (and Insertion) in Distributed SystemsGnutellaxyz.mp3 ?9/12/2002 Internet and Grid Computing - Fall 200212Search/Discovery (and Insertion) in Distributed SystemsGnutella9/12/2002 Internet and Grid Computing - Fall 200213Search/Discovery (and Insertion) in Distributed SystemsGnutellaxyz.mp39/12/2002 Internet and Grid Computing - Fall 200214Search/Discovery (and Insertion) in Distributed SystemsCurrent Techniques: Gnutella: Breadth-First Search (BFS)= forwardquery= processedquery= source= foundresult= forwardresponse9/12/2002 Internet and Grid Computing - Fall 200215Search/Discovery (and Insertion) in Distributed SystemsIterative Deepening• Interested in satisfaction, not # of results• BFS returns “too many” results expensive• Iterative Deepening: common technique to reduce the cost of BFS– Intuition: A search at a small depth is much cheaper than at a larger depth9/12/2002 Internet and Grid Computing - Fall 200216Search/Discovery (and Insertion) in Distributed SystemsIterative Deepening= source= forwardquery= processedquery= foundresult= forwardresponse?9/12/2002 Internet and Grid Computing - Fall 200217Search/Discovery (and Insertion) in Distributed SystemsDirected BFS• Sends query to a subset of neighbors • Maintains statistics on neighbors – E.g., ping latency, history of number of results• Chooses subset intelligently (via heuristics), to maximize quality of results– E.g., Neighbors with shortest message queue, since long message queue implies neighbor is saturated/dead9/12/2002 Internet and Grid Computing - Fall 200218Search/Discovery (and Insertion) in Distributed SystemsDirected BFS?= source= forwardquery= processedquery= foundresult= forwardresponse9/12/2002 Internet and Grid Computing - Fall 200219Search/Discovery (and Insertion) in Distributed SystemsDirected BFS: HeuristicsHighest degreeDEGShortest message queueQLENSent our client greatest # of messagesMSGHad smallest avg. # hops for response messages in pastHOPSHad shorted avg. time to satisfaction in pastTIMEReturned greatest # results in pastRES(Random)RANDSIMPLE9/12/2002 Internet and Grid Computing - Fall 200220Search/Discovery (and Insertion) in Distributed SystemsLocal Indices• Each node maintains index over other nodes’ collections– r is the radius of the index– Index covers all nodes within r hops away• Can process query at fewer nodes, but get just as many results backr9/12/2002 Internet and Grid Computing - Fall 200221Search/Discovery (and Insertion) in Distributed SystemssdfnrdsdfnrdsdfnrdsdfnrdLocal Indices (r=1)= source= forwardquery= processedquery= foundresult= forwardresponse9/12/2002 Internet and Grid Computing - Fall 200222Search/Discovery (and Insertion) in Distributed SystemsDistributed Hashing — General ApproachNodesObjects1. Map both objects and nodes into some topology (“id space”)9/12/2002 Internet and Grid Computing - Fall 200223Search/Discovery (and Insertion) in Distributed SystemsDistributed Hashing — General ApproachNodesObjects1. Map
View Full Document
Unlocking...