Distributed minimum spanning tree: Difference between revisions

Revision as of 22:37, 18 December 2011

Revision as of 18:46, 19 December 2011

Line 78:

* '''Absorb''': This operation occurs if Level(F) < Level(F’). The combined fragment will have the same level as F’.

Furthermore, when an "Absorb" operation occurs, F must be in the stage of changing the core while F’ can be in arbitrary stage. Therefore, "Absorb" operationoperations may be done differently depending on the state of F’. Let e be the edge that F and F’ want to combine with and nodelet n and n’ be the two nodes connected by e in F and F’, respectively. There are two cases to consider:<br/>

'''Case 1''': Node n’ has received broadcast message but it hasn’thas not sent a convergecast message back to the core.<br/>

In this case, fragment F can simply join the broadcast process of F’. Specifically, we image F and F’ have already combined to form a new fragment F’’, so we want to find the minimum weight outgoing edge of F’’. In order to do that, node n’ can initiate a broadcast to F to update the fragment ID of each node in F and collect minimum weight outgoing edge in F.<br/>

'''Case 2''': Node n’ has already sent a convergecast message back to the core.<br/>

Before node n’ sendingsent a convergecast message, it must have picked a minimum weight outgoing edge. As we discussed above, the way for n’ to dodoes that isby choosing its minimum weight basic edge, sending a test message to the other side of the chosen edge, and waitwaiting for the response. Suppose e’ is the chosen edge, we can conclude the followingsfollowing:

# e’ != e

# weight(e’) < weight(e)