EECS 122 A Note on Project 3 Computer Science Division Department of Electrical Engineering and Computer Sciences University of California Berkeley Berkeley CA 94720 1776 Katz Stoica F04 Problem Each node contains a set of files and each file has associated a fileID Find a file given itsfileID E F D E A C B Katz Stoica F04 2 Two Approaches Centralized 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 Katz Stoica F04 3 Chord Big Picture Assume circular identifier ID space is 0 2m 1 To each node we associate a unique ID in this identifier space Each node is responsible for all IDs between itself and its predecessor on this circle Katz Stoica F04 4 Example Identifier to Node Mapping Assume 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 4 58 8 15 44 20 35 32 Katz Stoica F04 5 Stella Overview Storing Files 3 node44 A 60 node32 C Each file has associated a fileID fileID is mapped in the node ID space An entry fileID node fileName is inserted at node responsible for fileID 4 58 5 node20 D 8 15 44 node IPaddr port 3 A 33 B 20 35 33 node44 B 5 D 32 60 Katz C Stoica F04 6 Basic Operation Route to a Given ID route 34 data Each node maintains its successor and predecessor E g 4 58 8 succ 58 4 succ 8 15 pred 58 44 pred 8 4 Route packet ID data to the node responsible for ID using successor pointers 15 44 20 35 32 Katz Stoica F04 7 Basic Chord Protocol Each node A periodically sends a stabilize message to its successor B Upon receiving a stabilize message a node B returns its predecessor B to A by sending a notify message Upon receiving notify from B if B is between A and B A updates its successor to B otherwise A doesn t do anything Katz Stoica F04 8 Joining Operation Node with ID 50 joins the ring Node 50 needs to know at least one node already in the system 4 58 8 Assume known node is node15 15 50 44 20 35 32 Katz Stoica F04 9 Joining Operation notify Node 50 asks node 15 to forward join message When join 50 reaches the destination i e node 58 node 58 1 succ 58 updates its predecessor to 50 50 and 2 returns a notify message to node 50 Node 50 updates its successor to 58 pred 50 notify 58 4 58 8 join 50 15 route 50 join node50 44 20 35 32 Katz Stoica F04 10 Joining Operation stabilize notify pred 50 r 5 0 4 8 dec e sso 58 y p re Node 44 sends a stabilize message to its successor node 58 Node 58 reply with a notify message Node 44 updates its succ 58 successor to 50 not if stabilize 15 50 succ 50 44 20 35 32 Katz Stoica F04 11 Joining Operation cont d pred 50 Node 44 sends a stabilize message to its new successor node 50 Node 50 sets its predecessor to node 44 4 58 8 succ 58 pred 44 50 succ 50 Stabilize 15 44 20 35 32 Katz Stoica F04 12 Joining Operation cont d This completes the joining operation pred 50 4 58 succ 58 pred 44 succ 50 8 50 15 44 20 35 32 Katz Stoica F04 13 Achieving Robustness To improve robustness each node maintains the k 1 immediate successors instead of only one successor In the notify message node A can send its k 1 successors to its predecessor B Upon receiving notify message B can update its successor list by concatenating the successor list received from A with A itself Katz Stoica F04 14 Failure and Leaving Operation Failure and leaving are treated the same way Assume each node maintains two successors pred 44 Assume node 44 fails 50 Node 35 if no notify is received after three stabilize messages remove successor 44 4 58 8 15 stabilize 20 Node 50 if three stabilize messages are missing remove predecessor 35 succ 44 succ 50 32 Katz Stoica F04 15 Failure and Leaving Operation Node 35 4 58 new succ 50 next stabilize sent to 50 Node 50 update pred 35 8 pred 50 15 44 stabilize 35 succ 50 succ 20 32 Katz Stoica F04 16 Failure and Leaving Operation Node 50 4 58 send notify to 35 including pred 35 succ 58 Node 35 update succ 58 8 pred 35 50 15 notify pred 35 succ 58 44 20 35 succ 50 succ 32 Katz Stoica F04 17 Failure and Leaving Operation Node 50 4 58 send notify to 35 including pred 35 succ 58 Node 35 update succ 58 8 pred 35 50 15 notify pred 35 succ 58 44 20 35 succ 50 succ 58 32 Katz Stoica F04 18
View Full Document
Unlocking...