DOC PREVIEW
UT CS 395T - Introduction to P2P Systems

This preview shows page 1-2-3-4-5-6-43-44-45-46-47-48-87-88-89-90-91-92 out of 92 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 92 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 92 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 92 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 92 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 92 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 92 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 92 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 92 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 92 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 92 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 92 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 92 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 92 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 92 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 92 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 92 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 92 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 92 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 92 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Search/Discovery Design GoalsSpectrum of “Purity”Metrics for Discovery/Insertion/JoinP2P 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 ArchitectureConsistent HashingChord Uses log(N) “Fingers”Chord Finger TableChord LookupNew Node Join ProcedureNew Node Join Procedure (2)New Node Join Procedure (3)Chord PropertiesBuilding Systems with ChordNaming and AuthenticationNaming and Fault ToleranceNaming and Load BalanceNaming and CachingOverviewConsistent hashingKey LocationLookup(id)Lookup PseudoCodeLookup costNode Join/LeaveJoin PseudoCodeJoin/leave costStabilizationStabilization cont’dFailures and replicationAlgorithmsDocument Routing – CANCAN Example: Two Dimensional SpaceCAN Example: Two Dimensional SpaceCAN Example: Two Dimensional SpaceCAN Example: Two Dimensional SpaceCAN Example: Two Dimensional SpaceCAN Example: Two Dimensional SpaceCAN: Query ExampleCAN: Query ExampleCAN: Query ExampleCAN: Query ExampleNode Failure RecoveryDoc Routing – Tapestry/PastryCAN: node failuresCAN: scalabilityComparing GuaranteesSummary9/11/2003 Internet and Grid Computing - Fall 20031Introduction to P2P SystemsLecture Coverage1. Characteristics, Properties and Requirements2. Survey of Approaches3. Napster/Gnutella4. Distributed Hash Table Based Systems1. Chord2. Can5. Similarity Metric Based Systems1. Freenet9/11/2003 Internet and Grid Computing - Fall 20032Introduction to P2P SystemsPure P2P Systems- PropertiesFully distributed, fully symmetric controlCommon knowledge – Initialization and by DiscoveryDiscovery is essentialDiscovery is via peer interaction protocolsFunctionality is composed from independent componentsSelf-organizing behaviorsProtocols:Join , Leave, Insertion, Discovery, Replication9/11/2003 Internet and Grid Computing - Fall 20033Introduction to P2P SystemsSearch/Discovery • “Location Resolution”Given an object (might be name, attribute, or even content)Return a channel to a node (peer) that hasthat objectOr the object itself• Approaches:– Centralized Index (Napster)– Broadcast information to be resolved (Gnutella)– Similarity metric based searches– Distributed Hashing9/11/2003 Internet and Grid Computing - Fall 20034Introduction to P2P SystemsDesign Goals• Scalability• Low latency (efficient resolution)• Load balancing• Completely distributed/self-organizing• Robust – fault-tolerance• Deployable•Simple9/11/2003 Internet and Grid Computing - Fall 20035Introduction to P2P SystemsSpectrum of “Purity”• Hybrid– Centralized index, P2P file storage and transfer• Super-peer or Hierarchical– A “pure” network of “hybrid” clusters•Pure– functionality completely distributed9/11/2003 Internet and Grid Computing - Fall 20036Introduction to P2P SystemsMetrics for Discovery/Insertion/Join• Cost (aggregate)– Number of Messages or Interactions– Bandwidth– Processing Power• Quality of Results– Number of results– Satisfaction (true if # results >= X, false otherwise)– Time to satisfaction9/11/2003 Internet and Grid Computing - Fall 20037Introduction to P2P 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/11/2003 Internet and Grid Computing - Fall 20038Introduction to P2P SystemsNapsterCentral Napster server(xyz.mp3, 128.1.2.3)128.1.2.39/11/2003 Internet and Grid Computing - Fall 20039Introduction to P2P SystemsNapsterCentral Napster serverxyz.mp3 ?128.1.2.3128.1.2.39/11/2003 Internet and Grid Computing - Fall 200310Introduction to P2P SystemsNapsterCentral Napster server128.1.2.3xyz.mp3 ?9/11/2003 Internet and Grid Computing - Fall 200311Introduction to P2P SystemsGnutella9/11/2003 Internet and Grid Computing - Fall 200312Introduction to P2P SystemsGnutellaxyz.mp3 ?9/11/2003 Internet and Grid Computing - Fall 200313Introduction to P2P SystemsGnutella9/11/2003 Internet and Grid Computing - Fall 200314Introduction to P2P SystemsGnutellaxyz.mp39/11/2003 Internet and Grid Computing - Fall 200315Introduction to P2P SystemsCurrent Techniques: Gnutella: Breadth-First Search (BFS)= forwardquery= processedquery= source= foundresult= forwardresponse9/11/2003 Internet and Grid Computing - Fall 200316Introduction to P2P 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/11/2003 Internet and Grid Computing - Fall 200317Introduction to P2P SystemsIterative Deepening= source= forwardquery= processedquery= foundresult= forwardresponse?9/11/2003 Internet and Grid Computing - Fall 200318Introduction to P2P 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/11/2003 Internet and Grid Computing - Fall 200319Introduction to P2P SystemsDirected BFS= source= forwardquery= processedquery= foundresult= forwardresponse?9/11/2003 Internet and Grid Computing - Fall 200320Introduction to P2P SystemsDirected BFS: HeuristicsRAND (Random)RES Returned greatest # results in pastTIME Had shorted avg. time to satisfaction in pastHOPS Had smallest avg. # hops for response messages in pastMSG Sent our client greatest # of messagesQLEN Shortest message queueDEG Highest degreeSIMPLE9/11/2003 Internet and Grid Computing - Fall 200321Introduction to P2P 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/11/2003 Internet and Grid Computing - Fall 200322Introduction to P2P SystemssdfnrdsdfnrdsdfnrdLocal Indices (r=1)= source= forwardquery=


View Full Document

UT CS 395T - Introduction to P2P Systems

Documents in this Course
TERRA

TERRA

23 pages

OpenCL

OpenCL

15 pages

Byzantine

Byzantine

32 pages

Load more
Download Introduction to P2P Systems
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Introduction to P2P Systems and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Introduction to P2P Systems 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?