EECS 122: A Note on Project 3ProblemTwo ApproachesChord: Big PictureExample: Identifier to Node MappingStella Overview: Storing FilesBasic Operation: Route to a Given IDBasic Chord ProtocolJoining OperationJoining Operation: notify()Joining Operation: stabilize()/notify()Joining Operation (cont’d)Slide 13Achieving RobustnessFailure and Leaving OperationSlide 16Slide 17Slide 18Katz, Stoica F04EECS 122: A Note on Project 3 Computer Science DivisionDepartment of Electrical Engineering and Computer SciencesUniversity of California, BerkeleyBerkeley, CA 94720-17762Katz, Stoica F04ProblemEach node contains a set of files, and each file has associated a fileID Find a file given itsfileIDABCDEFE?3Katz, Stoica F04Two ApproachesCentralized index – 1st project-One node (server) maintains a IndexTable with entries of the form (fileID, node, fileName)-Given a fileID K, a client•Contacts the server •Gets back from server a set of entries of the form (K, nodei, fileNamei)•download fileNamei from nodei Decentralized index – 3rd project (Stella)-IndexTable distributed across nodes-Big question: given a fileID K, find corresponding entries?-We use a simple variant of Chord protocol-Note: at high level, this is how eDonkey works!4Katz, Stoica F04Chord: Big PictureAssume circular identifier (ID) space is 0..2m-1To each node we associate a unique ID in this identifier spaceEach node is responsible for all IDs between itself and its predecessor on this circle5Katz, Stoica F04Example: Identifier to Node MappingAssume m=6 ID space is 0..63 Node 8 is responsible for [5,8]Node 15 is responsible for [9,15]Node 20 is responsible for [16, 20]…Node 4 is responsible [59, 4]420323581544586Katz, Stoica F04Stella Overview: Storing FilesEach file has associated a fileID.fileID is mapped in the node ID spaceAn entry (fileID, node, fileName) is inserted at node responsible for fileID-node = (IPaddr, port)42032358154458A3B33C60D5(3, node44, A)(5, node20, D)(33, node44, B)(60, node32, C)7Katz, Stoica F04Basic Operation: Route to a Given IDEach node maintains its successor and predecessorE.g., -succ(58) = 4; succ(8) = 15-pred(58) = 44; pred(8) = 4Route packet (ID, data) to the node responsible for ID using successor pointers42032358154458route(34,data)8Katz, Stoica F04Basic Chord ProtocolEach node A periodically -sends a stabilize() message to its successor BUpon receiving a stabilize() message a node B-returns its predecessor B’ to A by sending a notify() messageUpon receiving notify() from B, -if B’ is between A and B, A updates its successor to B’; -otherwise A doesn’t do anything9Katz, Stoica F04Joining Operation4203235815445850Node with ID=50 joins the ringNode 50 needs to know at least one node already in the system-Assume known node is node1510Katz, Stoica F04Joining Operation: notify()4203235815445850Node 50 asks node 15 to forward join messageWhen join(50) reaches the destination (i.e., node 58), node 58 (1) updates its predecessor to 50, and (2) returns a notify message to node 50Node 50 updates its successor to 58join(50)notify(58)pred=50succ=58route(50, join, node50)11Katz, Stoica F04Joining Operation: stabilize()/notify()4203235815445850Node 44 sends a stabilize message to its successor, node 58Node 58 reply with a notify messageNode 44 updates its successor to 50succ=58stabilize()notify(predecessor=50)succ=50pred=5012Katz, Stoica F04Joining Operation (cont’d)4203235815445850Node 44 sends a stabilize message to its new successor, node 50Node 50 sets its predecessor to node 44succ=58succ=50Stabilize()pred=44pred=5013Katz, Stoica F04Joining Operation (cont’d)4203235815445850This completes the joining operation!succ=58succ=50pred=44pred=5014Katz, Stoica F04Achieving RobustnessTo improve robustness each node maintains the k (> 1) immediate successors instead of only one successorIn the notify() message, node A can send its k-1 successors to its predecessor BUpon receiving notify() message, B can update its successor list by concatenating the successor list received from A with A itself15Katz, Stoica F04Failure and Leaving OperationFailure and leaving are treated the same way!Assume each node maintains two successorsAssume node 44 failsNode 35: -if no notify() is received after three stabilize() messages remove successorNode 50: -if three stabilize() messages are missing remove predecessor4203235815445850succ=44succ’=50stabilize()pred = 4416Katz, Stoica F04Failure and Leaving OperationNode 35:-new succ=50-next stabilize() sent to 50Node 50: -update pred=354203235815445850succ=50succ’= ?stabilize()pred = ?17Katz, Stoica F04Failure and Leaving OperationNode 50:-send notify() to 35, including (pred=35,succ=58)Node 35:-update succ’=58 4203235815445850succ=50succ’= ?notify(pred=35,succ=58)pred = 3518Katz, Stoica F04Failure and Leaving OperationNode 50:-send notify() to 35, including (pred=35,succ=58)Node 35:-update succ’=58 4203235815445850succ=50succ’= 58notify(pred=35,succ=58)pred =
View Full Document
Unlocking...