4.4 Flooding a New Leaf Set Member
Assume that there is a registered node with a Local ID of Y and that its Leaf Set consists of {B, C, D, E, F} on one side and {G, H, I ,J, K} on the other. Assume that Node Y learns about a new Route Entry with the ID of X, which is closer than G currently is.
Figure 7: Leaf Set node arrangement example
The following will now take place.
Note This sequence illustrates the cascading flood activity when a new ID is learned. Prior to any node propagating a FLOOD message, the node will send an INQUIRE message to the new node that it has just learned about. The node will propagate the FLOOD message only when an AUTHORITY message has been received back from the new node.
X displaces K in Y's Leaf Set. This is the first wave of flooding.
Y selects the two nearest route entries in its cache with one being less than Y and one being greater than Y. In this case, nodes F and G are chosen.
Y builds a FLOOD message with an Already Flooded List containing an address that Y is using and one of the addresses of both F and G. The FLOOD message will now be sent to F and G.
When F receives the FLOOD message from Y of node X, Y checks to see whether it already knows about X. If Y does, it drops the FLOOD message with no further action. It does not, so it adds X to its Leaf Set.
F selects the two nearest route entries to its local ID, which do not have addresses in the Already Flooded List, with one being less than F and one being greater than F. E and H will be chosen.
F builds a FLOOD message with the Already Flooded List having an address of E and H appended to it. The list will now contain {Y, F, G, E, H}.
F now sends the FLOOD message of X to E and H.
When G receives the FLOOD message from Y of Node X, Y checks to see if it already knows about X. If it did, it would drop the FLOOD message with no further action. It does not, so it adds X to its Leaf Set.
G selects the two nearest route entries to its local PNRP ID, which do not have addresses in the Already Flooded List with one being less than F and one being greater than F. E and H will be chosen.
G builds a FLOOD message with the Already Flooded List having an address of E and H appended to it. The list now contains {Y, F, G, E, H}.
G now sends the FLOOD message of X to E and H.
The second wave of flooding for Node X begins.
Both Node E and Node H receive two copies of the FLOOD message of X, one forwarded from F and one forwarded from G. When processing the second instance of the flood, E and H ignore the second one because X will be either in their Leaf Set or in a list of route entries being checked.
E and H repeat the process, Flooding to D and I. The Already Flooded List will contain {Y, F, G, E, H, D, I}.
The third wave of flooding for Node X begins.
Nodes D and I receive the FLOOD message of X. Both D and I forward the FLOOD message to two neighbors, but because the Already Flooded List will already contain all the nodes in half or each node's Leaf Set, one of the flood targets will likely not be the next nearest neighbor in that direction.
D forwards to C, which is in its Leaf Set, but does not necessarily flood to J because J is outside its Leaf Set. In this example, it forwards to L because it does not know about J or K. The Already Flooded List contains {Y, F, G, H, D, I, C, L}.
I forwards to J, which is in its Leaf Set, but does not necessarily forward to C because C is outside its Leaf Set. In this example, it forwards to A because it does not know about B and C. The Already Flooded List contains {Y, F, G, H, D, I, A, J }.
The fourth wave of flooding for Node X begins.
Nodes A, C, J, and L receive the FLOOD message of X. A and L do not forward the FLOOD message because X falls outside their Leaf Sets.
Nodes C and J forward the FLOOD message because X is still in their Leaf Sets.
C sends a FLOOD message to B and to some other node falling outside the Leaf Set.
J sends a FLOOD message to K and some other node falling outside the Leaf Set.
The fifth wave of flooding of X begins.
B does not forward the FLOOD message because X does not fall in its Leaf Set.
K ends forwarding of the FLOOD message because X still falls within its Leaf Set. K sends a FLOOD to L and some other node that is outside its Leaf Set.
The sixth wave of flooding begins.
L does not forward the FLOOD message because X does not fall within its Leaf Set. Any of the other more remote nodes will also not forward the FLOOD message.
Additionally, all of the nodes that added X to their Leaf Set will send FLOOD messages to with their own route entry back to X. In this way, X learns of all the nodes that consider X to be in their Leaf Set. These transactions are not included in the figure to reduce the clutter.