Hi Michael, Thanks for the reply. I found a paper "Bootstrapping Chord in Ad Hoc Network: Not Going Anywhere for a While" that gave a detailed example and that helped me alot in understanding the sequence.
I'm currently trying to understand how Chord claims that maintaining a successor list maintains stability in the case of node failure. For example if there are three node 2042, 2129, 2186 and 2129 fails. 2042 will next stabilize with 2129 and will not receive a reply after a timeout period. It will therefore look up the next successor in its successor list 2186 and stabilize with it. If 2186 has in the meantime sent a predecessor ping to 2129 it will have realised 2129 has failed, will have set its predecessor to nil and when it receives the stabilize message from 2042 will return an answer of nil so that when 2042 sends 2186 a notify message it will accept 2042 as its predecessor. That means everything works fine. However if 2186 hasn't sent a ping to its predecessor in the meantime there's a problem. 2042 will stabilize with 2186 who will reply saying 2129 is its predecessor and 2042 will simply update 2129 as its successor (after just removing it). I can't find any information describing the maintenance of successor lists and how they're supposed to work in detail. I suppose I can assume 2042 somehow knows 2129 is the incorrect answer from 2186 (maybe by maintaining a timer or something to allow 2186 to update) and then this might work....it seems to get very messy though synchronizing of timers and I suppose I'm just concerned that I'm missing the point of the successor list? Thanks in advance. Aisling On Fri, Jun 25, 2010 at 8:48 PM, Michael Rogers <m.rog...@cs.ucl.ac.uk>wrote: > Hi Aisling, > > This might not be the solution you're looking for, since I don't know > whether it's mentioned in the SIGCOMM paper, but would it make sense for > a node to check whether the sender of a notify message should become its > successor as well as its predecessor? That would mean that after m's > notify message, the pointers would be Ns = m, Np = m, Ms = n, Mp = n, > and m's subsequent lookups through n would populate its finger table > with a mixture of ms and ns. > > Cheers, > Michael > > Aisling O' Driscoll wrote: > > I am currently implementing a Chord model in OPNET and am anxious to > > ensure my implementation is correct (as per the Chord SIGCOMM paper). I > > have read a lot about Chord but I still cannot work out how the ring > > should be constructed in a distributed manner (I understand quite well > > how it should work once fully formed). > > > > I describe a scenario below (Please point out if any of my logic or the > > sequence is incorrect). > > > > 1. > > Node n wishes to join a Chord ring. There are no other nodes in > > the ring. > > 2. It sets its successor = n and its predecessor = NIL. It builds its > > finger table so that all finger successor entries are set to > itself. > > 3. Subsequently node m wishes to join the network. Node m queries > > node n for its successor. > > 4. Node n replies that m’s successor is itself, n. > > 5. Node m sets its successor = n and its predecessor = NIL. > > 6. As per the Chord node joining procedure, node m then triggers the > > notify function informing node n of its existence so that it can > > update its predecessor pointer to m. At this point, Ns = n, Np = > > m, Ms = n, Mp = NIL. > > 7. Now this is where I am confused: Ordinarily, in a fully formed > > Chord ring, node n would at some point send a periodic stabilize > > function to its successor querying its predecessor. In this way it > > would learn about a new node that has joined in between node n and > > its successor, update it successor and notify the new node to > > update its predecessor pointer. > > > > Clearly node n’s successor should now be node m and node m’s predecessor > > should be node n. But node N is not going to send a stabilize packet to > > itself so I don’t know how the pointers will be correctly updated. > > > > 8. I also don’t understand how node m’s finger tables will be > > correctly constructed. Node m will construct its finger table by making > > node n do a lookup for each entry. But this will always return node n > > (as that is all that’s currently located in node n’s finger table) so > > node m will never be referenced either node’s finger table (which is > > incorrect). > > > > I would greatly appreciate if someone could clarify the above as I'm > > stuck in my implementation at the moment. > > > > Many thanks in advance, > > > > > > > > > > > > > > > > ------------------------------------------------------------------------ > > > > _______________________________________________ > > p2p-hackers mailing list > > p2p-hackers@lists.zooko.com > > http://lists.zooko.com/mailman/listinfo/p2p-hackers > >
_______________________________________________ p2p-hackers mailing list p2p-hackers@lists.zooko.com http://lists.zooko.com/mailman/listinfo/p2p-hackers
