Distributed Hash TablesPresentation OutlineWhat is DHT?Why DHTs?ApplicationsHow lookup works?Slide 7Slide 8Slide 9Slide 10Slide 11Alternatives to DHTsPerformance -- LookupPerformance -- Load BalancingSecurity – Incorrect Lookup (1)Security – Incorrect Lookup (2)Security – Incorrect Lookup (3)Security – Incorrect Lookup (4)Security – Inconsistent BehaviourSlide 20Slide 21Slide 22Comparison to Other FacilitiesResearch ProjectsSummaryReferencesDistributed Hash TablesDavid TamPatrick PangPresentation Outline•What is DHT (Distributed Hash Table)?•Why DHTs?•Applications•How lookup works?•Alternatives to DHTs•Performance – Routing•Performance – Load Balancing•Security – Routing Attack•Security – Inconsistent Behaviour•Comparison to Other Facilities•Current Research Projects•ConclusionWhat is DHT?Distributed hash tableDistributed applicationget (key)datanode node node….put(key, data)(Figure adopted from Frans Kaashoek)DHT provides the information look up service for P2P applications.• Nodes uniformly distributed across key space• Nodes form an overlay network• Nodes maintain list of neighbours in routing table• Decoupled from physical network topologyWhy DHTs?Why Do We Need DHTs?• Simplifies the development for large-scale distributed Apps • Better security and robustness• Simple API• Exploits P2P resourcesWhy Middleware?• Simplifies the development for large-scale distributed Apps • Better security and robustness• Simple APIApplications• Anything that requires a hash table• Databases, FSes, storage, archival• Web serving, caching• Content distribution• Query & indexing• Naming systems• Communication primitives• Chat services• Application-layer multi-casting• Event notification services• Publish/subscribe systems ?How lookup works?2141210750346891113start interval succ.3 [3,4) 54 [4,6) 56 [6,10) 710 [10,2) 10Finger Table for Node 2151Example: Chord [Stoica et. al.]How lookup works?214121075034689111315start interval succ.11 [11,12) 1212 [12,14) 1214 [14,2) 142 [2,10) 2Finger Table for Node 101Example: ChordHow lookup works?214121075034689111315start interval succ.11 [11,12) 1212 [12,14) 1214 [14,2) 142 [2,10) 2Finger Table for Node 101Example: ChordHow lookup works?1214121075034689111315start interval succ.15 [15,0) 150 [0,2) 12 [2,6) 26 [6,13) 7Finger Table for Node 14Example: ChordHow lookup works?1214121075034689111315start interval succ.15 [15,0) 150 [0,2) 12 [2,6) 26 [6,13) 7Finger Table for Node 14Example: ChordHow lookup works?2141210750346891115Now Node 2 can retrive information for key 0 from Node 1.1Example: ChordAlternatives to DHTs• Distributed file system• Centralized lookup• P2P flooding queriesServerClientClientClientClientInternetServer (Figures adopted from Frans Kaashoek)N4TargetStartN6N9N7N8N3N2N1N10N4TargetStartN6N9N7N8N3N2N1N10DBPerformance -- LookupPurpose -- to locate a target node•Each step, try to get closer to locating target node• Ask a closer neighbour• Performance & scalability tied directly to lookup algorithm2 Aspects to Scalability• size of routing table – O(log N)• lookup path length – O(log N)2 Aspects to Performance• Path latency• Lookup path length (# hops)3 Techniques• proximity lookup• proximity neighbour selection• geographic layoutPerformance -- Load BalancingIssues• Hot-spots • Content• Lookup• Heterogeneous nodes & paths• System fluxSolution• Replication is the key• Also good for fault-tolerance• Cache lookup answers backwards along pathSecurity – Incorrect Lookup (1)• When asked for the “next hop”, give a wrong answerstart interval succ.3 [3,4) 54 [4,6) 56 [6,10) 710 [10,2) 10Finger Table for Node 2Node 2 to Node 10: Please tell me how to reach key 0 ….2141210753468911131510Security – Incorrect Lookup (2)• When asked for the “next hop”, give a wrong answerstart interval succ.11 [11,12) 1212 [12,14) 1214 [14,2) 142 [2,10) 2Finger Table for Node 102141210750346891113151Node 2 to Node 10: Please tell me how to reach key 0 ….Node 10 answers: ask Node 14• When asked for the “next hop”, give a wrong answerstart interval succ.15 [15,0) 150 [0,2) 12 [2,6) 26 [6,13) 7Finger Table for Node 14214121075346891113151Node 2 to Node 14: Please tell me how to reach key 0 ….Node 14 answers: ask Node 10Security – Incorrect Lookup (3)0Security – Incorrect Lookup (4)Solution [Sit and Morris]:• “Define verifiable system invariant”• “Allow the querier to observe lookup progress” Our idea how this can be implemented:• Concretely, using an integral monotonically decreasing quantity to implement the idea of “progress”.• The concept of “monotonically decreasing quantity” has been used in program construction guaranteeing total correctness. [Parnas]Security – Inconsistent Behaviour• Inconsistent Behaviour, i.e., lie intelligibly• Sybil attack [Kaashoek] Solution 1: public key solutionSecurity – Inconsistent Behaviour• Inconsistent Behaviour, i.e., lie intelligibly• Sybil attack [Kaashoek] Solution 1: public key solutionSolution 2: Byzantine ProtocolByzantine Generals Problem:How to find out the traitors among the Generals? [Lamport]• Inconsistent Behaviour, i.e., lie intelligibly• Sybil attack [Kaashoek] Security – Inconsistent BehaviourSolution 1: public key solutionSolution 2: Byzantine ProtocolByzantine Generals Problem:How to find out the traitors among the Generals? [Lamport]CommanderLieutenant 1 Lieutenant 2“he said ‘retreat’”attackattackSecurity – Inconsistent Behaviour• Inconsistent Behaviour, i.e., lie intelligibly• Sybil attack [Kaashoek] Solution 1: public key solutionSolution 2: Byzantine ProtocolByzantine Generals Problem:How to find out the traitors among the Generals? [Lamport]CommanderLieutenant 1 Lieutenant 2retreatattack“he said ‘retreat’”Comparison to Other FacilitiesFacility Abstraction Easy Use/Prg Scalability Load-BalanceDHT high high high yesCentralized Lookup medium medium low noP2P flooding queries medium high low noDistributed FS low medium medium noFacility Fault-Tolerance Self-Org AdminDHT high yes lowCentralized Lookup low no mediumP2P flooding queries depends yes lowDistributed FS medium no highResearch ProjectsIris – security & fault-tolerance – US Gov’tChord – circular key spacePastry – circular key spaceTapestry – hypercube spaceCAN – n-dimensional key spaceKelips – n-dimensional