Classical mulitpath routing has been explored for two main reasons:
-
Load Balancing
-
Robustness
Load-balancing has as goal to conserve energy in sensor networks, but that is not the focus of BMR Protocol.
In ad-hoc networks, multipath routing is used to rapidly find alternate paths between source and destination, and so guarantee a better robustness of the network.
From the application's perspective, a desirable goal of multipath routing is to deliver data along the primary path. To recover from failure of this primary path, without flooding the network for rediscovery, multipath routing constructs and maintains a small number of alternative paths.
Definition
A simple and constructive definition of the Braided Multipath Routing Protocol is:
"For each node of the primary path, find the best path from the source to the destination that does not contain that node."
Idealized Braid
This alternate best path need not necessarily be completely another than the primary path. In
figure 1 we see an
idealized braided multipath. The links can be expected geographically close to the primary, and so it can be said, that the braid expends energy comparable to the primary path.
Figure 1
When the destination receives a route request, it sends out a primary path reinforcement to the most preferred neighbour
A. But the destination sends an alternate route inforcement to its second most important neighbour
B. When A receives the route reinforcement of the destination, it sends it to his most preferred neighbour and so on. In addition,
A ( an every other node on the way back to the source) originates an alternate path reinforcement to its most preferred neighbour. On this prinicipale, every node tries to find an alternate path around its immediate neighbour.
Localized Braid
In
figure 2 we see a Localized Braid, who uses the same mechanism as the Idealized Braid.
Figure 2
In this figure we see that node n(k+1) sends an alternate reinforcement to route around node n(k) that passes through a(i) and a(i-1) before rejoining the primary path at node n(k-2). But in practice this perfect detour around node n(k) could not always be made. It could be that the route reinforcement sent out by any node can follows any sequence of nodes, even possibly completely disjoint from the rest of the primary path, towards the source.
Equally, an alternate reinforcement send by node n(k-1) con rejoin the primary path an node n(k).
The difference between the Idealized- and the Localized- Braid in this figures is, that node n(k-1) has no alternate path back to the source.
Perfect Braid
In
figure 3 we can see an Perfect Braid, where all node of the primary path has one, and only one detour around his neighbour with only one node used!
Figure 3
All the references and pictures:
Ganesan2001
