Robert Morris, M. Frans Kaashoek, David Karger, Hari Balakrishnan, Ion Stoica, David Liben-Nowell, Frank Dabek Chord: A scalable peer-to-peer look-up protocol for internet applications Christine KieferOverviewThe lookup problemRouted queries (Freenet, Chord, etc.)What is Chord?Chord softwareSlide 7The Chord algorithm – Construction of the Chord ringSlide 9Slide 10The Chord algorithm – Simple node localizationThe Chord algorithm – Scalable node localizationSlide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25The Chord algorithm – Node joins and stabilizationSlide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34The Chord algorithm – Impact of node joins on lookupsSlide 36Slide 37The Chord algorithm – Failure of nodesSlide 39Slide 40Slide 41Slide 42Applications: Time-shared storageApplications: Chord-based DNSSummaryQuestions?Robert Morris, M. Frans Kaashoek, David Karger, Hari Balakrishnan, Ion Stoica, David Liben-Nowell, Frank Dabek Chord: A scalable peer-to-peer look-up protocol for internet applicationsChristine KieferOverviewIntroductionThe Chord AlgorithmConstruction of the Chord ringLocalization of nodesNode joins and stabilizationFailure of nodesApplicationsSummaryQuestionsThe lookup problemInternetN1N2N3N6N5N4PublisherKey=“title”Value=MP3 data…ClientLookup(“title”)?Routed queries (Freenet, Chord, etc.)N4PublisherClientN6N9N7N8N3N2N1Lookup(“title”)Key=“title”Value=MP3 data…What is Chord?Problem adressed: efficient node localizationDistributed lookup protocolSimplicity, provable performance, proven correctnessSupport of just one operation: given a key, Chord maps the key onto a nodeChord software3000 lines of C++ codeLibrary to be linked with the applicationprovides a lookup(key) – function: yields the IP address of the node responsible for the keyNotifies the node of changes in the set of keys the node is responsible forOverviewIntroductionThe Chord AlgorithmConstruction of the Chord ringLocalization of nodesNode joins and StabilizationFailure/Departure of nodesApplicationsSummaryQuestionsThe Chord algorithm –Construction of the Chord ringthe consistent hash function assigns each node and each key an m-bit identifier using SHA 1 (Secure Hash Standard). m = any number big enough to make collisions improbableKey identifier = SHA-1(key)Node identifier = SHA-1(IP address)Both are uniformly distributedBoth exist in the same ID spaceThe Chord algorithm –Construction of the Chord ringidentifiers are arranged on a identifier circle modulo 2 => Chord ring mThe Chord algorithm –Construction of the Chord ringa key k is assigned to the node whose identifier is equal to or greater than the key‘s identifierthis node is called successor(k) and is the first node clockwise from k.The Chord algorithm –Simple node localization// ask node n to find the successor of idn.find_successor(id) if (id (n; successor]) return successor; else // forward the query around the circle return successor.find_successor(id);=> Number of messages linear in the number of nodes !The Chord algorithm –Scalable node localizationAdditional routing information to accelerate lookupsEach node n contains a routing table with up to m entries (m: number of bits of the identifiers) => finger tablei entry in the table at node n contains the first node s that succeds n by at least 2s = successor (n + 2 )s is called the i finger of node ni-1ththi-1The Chord algorithm –Scalable node localizationFinger table:finger[i] = successor (n + 2 )i-1The Chord algorithm –Scalable node localizationFinger table:finger[i] = successor (n + 2 )i-1The Chord algorithm –Scalable node localizationFinger table:finger[i] = successor (n + 2 )i-1The Chord algorithm –Scalable node localizationFinger table:finger[i] = successor (n + 2 )i-1The Chord algorithm –Scalable node localizationFinger table:finger[i] = successor (n + 2 )i-1The Chord algorithm –Scalable node localizationFinger table:finger[i] = successor (n + 2 )i-1The Chord algorithm –Scalable node localizationFinger table:finger[i] = successor (n + 2 )i-1The Chord algorithm –Scalable node localizationFinger table:finger[i] = successor (n + 2 )i-1The Chord algorithm –Scalable node localizationFinger table:finger[i] = successor (n + 2 )i-1The Chord algorithm –Scalable node localizationFinger table:finger[i] = successor (n + 2 )i-1The Chord algorithm –Scalable node localizationImportant characteristics of this scheme:Each node stores information about only a small number of nodes (m)Each nodes knows more about nodes closely following it than about nodes farer awayA finger table generally does not contain enough information to directly determine the successor of an arbitrary key kThe Chord algorithm –Scalable node localizationSearch in finger table for the nodes which most immediatly precedes idInvoke find_successor from that node=> Number of messages O(log N)!The Chord algorithm –Scalable node localizationSearch in finger table for the nodes which most immediatly precedes idInvoke find_successor from that node=> Number of messages O(log N)!The Chord algorithm –Node joins and stabilizationThe Chord algorithm –Node joins and stabilizationThe Chord algorithm –Node joins and stabilizationThe Chord algorithm –Node joins and stabilizationTo ensure correct lookups, all successor pointers must be up to date=> stabilization protocol running periodically in the backgroundUpdates finger tables and successor pointersThe Chord algorithm –Node joins and stabilizationStabilization protocol:Stabilize(): n asks its successor for its predecessor p and decides whether p should be n‘s successor instead (this is the case if p recently joined the system).Notify(): notifies n‘s successor of its existence, so it can change its predecessor to nFix_fingers(): updates finger tablesThe Chord algorithm –Node joins and stabilizationThe Chord algorithm –Node joins and stabilization• N26 joins the system• N26 aquires N32 as its successor• N26 notifies N32• N32 aquires N26 as its predecessorThe Chord algorithm –Node joins and stabilization• N26 copies keys• N21 runs stabilize() and asks its successor N32 for its