A node in Phase 1 has only to forward data packets along the BMEPK1. This is be-cause, given the high energy level of each node, the rounds of encryption are far from being a constraint in making forwarding decisions. Each node has enough energy to perform M or more rounds of encryption by itself that is, each node can fully encrypt its own packets. In such a phase, control plane operations are as follows.
Each node tracks its own BMEPK1. Any changes in the BMEPK1 are advertised to neighboring nodes in order to avoid loops and so to ensure the use of an optimal6 path at all times.
5Entire routes are advertised. Loops are avoided on all forwarding paths by not considering any path that involves the node itself as a valid path for that node. This is true in all phases of operation at every node, irrespective of the network wide energy.
6Except for the fudge factor K1introduced to reduce signaling overhead.
3.4. Phase 1: High energy 51
Figure 3.1: Example of BMEP routing.
Each node also tracks its 2nd best ME path (2BMEPK1) and monitors the Highe-st 2BMEPK1’s ME value (H2BME) among all of its downstream neighbours7 (i.e.
neighbours it receives data packets from). This last task is accomplished by having each node piggyback their 2BMEPK1’s ME value on data packets sent to their up-stream neighbour (i.e. the next hop on their BMEPK1). The purpose of this is to avoid the overhead of having periodic updates of BMEPK1’s ME values and instead use H2BME to trigger control plane updates. Specifically, when a node sees that a down-stream neighbor’s H2BME > K1∗ MEBMEPK1, it sends a unicast advertisement with its own current MEBMEPK1 to that neighbor so that the neighbor can either switch immediately to its 2BMEPK1 with higher ME or forward this advertisement further downstream until the correct node is reached. Once the correct node is reached, it can decide to switch to its 2BMEPK1 or not.
Let’s look at two examples.
In Fig. 3.1, node A routes packets sent by nodes B and C i.e., the path from node A to the sink is the BMEP for both nodes B and C. Nodes B and C also piggyback,
7The sink is the most upstream node.
Figure 3.2: A second example of BMEP routing.
on their data packets to node A, information about their 2BMEPK1’s ME. If node A sees that node C, for example, has a 2BMEPK1’s ME value better than that of its own BMEP, then it sends a unicast update to node C with its BMEPK1’s ME value. In this way, node C knows that its 2BMEPK1 is now better than the BMEP via A and can switch to its 2BMEPK1, which is now promoted to BMEP for node C. In doing so, node A does not have to send periodic updates to nodes B and C about its BMEPK1’s ME value as this continuously changes due to energy consumption.
In Fig.3.2, nodes B and C piggyback, on their data packets to node A, information about their 2BMEPK1’s ME values. Node A computes the maximum between the ME values it just received by the two nodes and its own 2BMEPK1’s ME value (i.e., it computes H2BME1) and it piggybacks it on its data packets to node D. Node D will do the same (i.e., computes H2BME2) and so will do subsequent nodes in the path.
At some point in time, node E realizes that its BMEPK1’s ME value is now lower than H2BME2 and so will inform node D of this. If H2BME2 is equal to node D’s 2BMEPK1’s ME value, node D will switch to its 2BMEPK1 and will advertise this
3.4. Phase 1: High energy 53
change in BMEP as mentioned earlier. If, on the other hand, H2BME2is equal to the 2BMEPK1’s ME value of some other downstream node (i.e., H2BME1), node D will inform node A of the change in ME value on the BMEP. If H2BME1is equal to node A’s 2BMEPK1’s ME value, node A will switch to its 2BMEPK1 and will advertise this change in BMEP. If not, it behaves as in the previous example. In doing so, we avoid periodic updates in BMEP’s ME values and send only triggered updates when needed.
To ensure loop free operations: a) the 2BMEPK1must be loop free, and b) when a node starts using its 2BMEPK1 (i.e., now becoming the node BMEPK1), it advertises such change in BMEP to its neighbors via a broadcast packet. This advertisement allows other nodes to make sure that such a change in best path does not create a loop for them. If it does, nodes discard their BMEP with this node, as it now contains a loop, and search for a different (loop-free) BMEP. Furthermore, by the time a node switches to its 2BMEP, information regarding this path may be stale and there may be other paths that are now better. This is a direct consequence of having triggered updates instead of periodic updates. In order to avoid switching to a 2BMEP with stale information, the node does not only advertise the change in best path as descri-bed earlier, but it also advertises that such new best path is its second, possibly stale, best path. When the node’s neighbors receive this advertisement, knowing that the node has switched to its 2BMEP, they will inform the node of their current BMEPK1 if this is better, in terms of ME, of the second best path the node just switched to. In receiving such information, the node may then decide to switch to one of these paths instead of continuing using the stale 2BMEP.
As data and control packets keep flowing through the network, nodes consume energy. Eventually, the energy levels of some nodes will reduce to the point where the rounds of encryption may soon start becoming an active constraint on the routing.
This is Phase 2.