1 Computer Communications - CSCI 551 Copyright © William C. Cheng CS551Distributed Hash TablesUnstructured SystemsBill Chenghttp://merlot.usc.edu/cs551-f122 Computer Communications - CSCI 551 Copyright © William C. Cheng Distributed Hash Tablesput(key, data) stores a data item with the specified keyIdea is easy, and defined by the interfaceget(key) retrieves data item(s) corresponding to keykey is usually a hash of data contentsImplementation is distributed over the wide area3 Computer Communications - CSCI 551 Copyright © William C. Cheng Uses of DHTsfile sharingA network-wide structure can enable a wide variety ofapplicationsdistributed file systemsanonymous publishing systemsflexible rendezvous for multicast applications4 Computer Communications - CSCI 551 Copyright © William C. Cheng DHT Implementationa document is accessed using a descriptive title of thecontent rather than the location where the document isstoreda data object is represented by a point in a key spaceUsually implemented as an overlay networkA special class of overlays: content-addressable overlaynetworksat the core lies the distributed algorithm for contentlookup and disseminationWhy distributed?no such consensus existsdocument key and node identifier are irrelevantUnstructured systemexampleGnutella, Freenet5 Computer Communications - CSCI 551 Copyright © William C. Cheng Structured vs. Unstructuredthere is global consensus on which network node adocument is storedalgorithmic mapping between document key and nodeidentifierStructured systemexampleCAN, CHORD, Tapestry, Pastry6 Computer Communications - CSCI 551 Copyright © William C. Cheng Structured vs. Unstructured (Cont...)advantageefficient queryStructured systemguarantee retrieval of existing documentsdisadvantagehard to provide anonymityproblem caused by DoS and selective attacksadvantagesimplicity in network maintenanceUnstructured systemresistant to attacksdisadvantageretrieval cost not boundedsearch may fail even if the requested data exists7 Computer Communications - CSCI 551 Copyright © William C. Cheng CS551Freenet[Clarke02a]Bill Chenghttp://merlot.usc.edu/cs551-f128 Computer Communications - CSCI 551 Copyright © William C. Cheng FreenetEarly peer-to-peer systemanonymity for publisherGoals:anonymity for consumerdeniability for participants in the overlaysearchAlgorithms forinsertion9 Computer Communications - CSCI 551 Copyright © William C. Cheng Keys in Freenethash the entire content of a file using SHA1like a directoryContent-hash keyvery low probability of collisionbut how do you find a file?create a container file that describes a collection of filesor documentsSigned-subspace keycontainer file hashed by a descriptive nameto access this file, you need to know the name of thecontainer file10 Computer Communications - CSCI 551 Copyright © William C. Cheng Basic Idea: Inserting Datasteepest ascent hill climbingEach node has routing table that maps keys to neighborsLet k be the key of the data item to be insertedIn routing table, find k’ that is closest to kuse second closest key k" if this action would cause a loopSend data item to the associated neighborCache data at each intermediate node11 Computer Communications - CSCI 551 Copyright © William C. Cheng Basic Idea: Retrieving DataAlgorithm similar to insertionTTL might be exceeded without hitting a cached copyData retrieval can failwe’ll see exampleAggressive caching: as data is being retrieved, intermediatenodes cache copyover time, different nodes specialize in different parts ofthe key space (a node is likely to store data items whosekeys are near each other)Key to good performance12 Computer Communications - CSCI 551 Copyright © William C. Cheng An Example Search in Freenet NetworkE has a copyof key 8B’s Routing TableKey PointerCD710...D’s Routing TableKey PointerE8...A BEDC13 Computer Communications - CSCI 551 Copyright © William C. Cheng A Search in Freenet NetworkE has a copyof key 8B’s Routing TableKey PointerCD710...D’s Routing TableKey PointerE8...A BEDCKey 8?14 Computer Communications - CSCI 551 Copyright © William C. Cheng A Search in Freenet NetworkE has a copyof key 8B’s Routing TableKey PointerCD710...D’s Routing TableKey PointerE8...A BEDCKey 8?15 Computer Communications - CSCI 551 Copyright © William C. Cheng A Search in Freenet NetworkE has a copyof key 8B’s Routing TableKey PointerCD710...D’s Routing TableKey PointerE8...A BEDCNo,sorry16 Computer Communications - CSCI 551 Copyright © William C. Cheng A Search in Freenet NetworkE has a copyof key 8B’s Routing TableKey PointerCD710...D’s Routing TableKey PointerE8...A BEDCKey 8?17 Computer Communications - CSCI 551 Copyright © William C. Cheng A Search in Freenet NetworkE has a copyof key 8B’s Routing TableKey PointerCD710...D’s Routing TableKey PointerE8...A BEDCKey 8?18 Computer Communications - CSCI 551 Copyright © William C. Cheng A Search in Freenet NetworkE has a copyof key 8B’s Routing TableKey PointerCD710...D’s Routing TableKey PointerE8...A BEDCKey 8!19 Computer Communications - CSCI 551 Copyright © William C. Cheng A Search in Freenet NetworkE has a copyof key 8B’s Routing TableKey PointerCD710...D’s Routing TableKey PointerE8...A BEDCKey 8!20 Computer Communications - CSCI 551 Copyright © William C. Cheng A Search in Freenet NetworkE has a copyof key 8B’s Routing TableKey PointerC7...D’s Routing TableKey PointerE8...A BEDCKey 8!E8D1021 Computer Communications - CSCI 551 Copyright © William C. Cheng A Search in Freenet NetworkE has a copyof key 8B’s Routing TableKey PointerC7...D’s Routing TableKey PointerE8...A BEDCA’s Routing TableKey Pointer...E8...D10E822 Computer Communications - CSCI 551 Copyright © William C. Cheng A Search in Freenet NetworkE has a copyof key 8B’s Routing TableKey PointerC7...D’s Routing TableKey PointerE8...A BEDCA’s Routing TableKey Pointer...E8...D10E823 Computer Communications - CSCI 551 Copyright © William C. Cheng A Search in Freenet NetworkE has a copyof key 8B’s Routing TableKey PointerC7...D’s Routing TableKey PointerE8...A BEDCA’s Routing TableKey Pointer...B8...Anonymity optioncan be turned onD10D824 Computer Communications - CSCI 551 Copyright © William C. Cheng Anonymitydata insertion tracks source, but any node can claim itselfto be the source (and any node can claim it’s just passingdata along)Publisher anonymityforwarder deniabilityConsumer anonymityfile contents are
View Full Document
Unlocking...