 |
 |
 |
 |
| |
|
|
|
|
SECAN-Lab Home News Projects SECAN-LAB Mesh Sequencer U-2010 NARTUS EFIPSANS IRMA SECRICOM The Group Members Publications Theses Teaching Presentations Topics Mobile Computing Ad-Hoc Networks Ad-Hoc Protocols Mesh Computing Trust Related Stuff L-101 Laboratory Systems AS28 Systems 802.11 Network Simulator Internships Conferences Publications Standards Projects Links Partners OSTN Miscellaneous Contact About Job Opportunities Search |
Braided Multipath Routing
Classical mulitpath routing has been explored for two main reasons:
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 "Braided Multipath Routing" is mentioned on: Ad-Hoc Protocols (Classification) | Ad-Hoc Workshop Winter 04/05 (Termine) |