Associativity-Based Routing

ABR

ABR was invented and developed by C.K. Toh at the Cambridge University in 1996. It is a source-initiated routing protocol, which means that there is no need for periodic route updates. ABR selects route based on the temporal stability of the links between the nodes.
ABR is beacon-based, so that each node generates periodic beacons (hello messages) to signify its existence to the neighbors. These beacons are used to update the associativity table of each node. With the temporal stability and the associativity table the nodes are able to classify each neighbor link as stable or unstable. ABR takes up a few metrics like.
The fundamental objective of ABR is to find longer-lived routes.

ABR consists of 3 phases:

1. Route Discovery
2. Route Repair/Reconstruction
3. Route Delete

Route Discovery

If node A has in his Route Cache a route to the destination E, this route is immediately used. If not, the Route Discovery protocol is started:

1. Flooding the network with RouteRequest messages. These messages are only forwarded once by each intermediate node, like in DSR. On receiving a RouteRequest message, the intermediate node appends its address and its associativity ticks to the packet.
2. When the RouteRequest message arrives at the target, this one will wait a period of time before selecting the best route by examining the associativity ticks along each path. If multiple routes have the same overall degree of stability, the route with the minimum number of hops will be selected.
3. Once the route as been chosen, the target sends a Reply packet back to the source along the same path

3 routes possible from 1 to 15: 1-5-10-14-15
1-5-4-12-15
1-2-4-8-13-15

ABR selects route 3 because of the highest percentage of stable links on this path.

Route Repair/Reconstruction

1. Link is broken
The broken link is detected by all the neighbor nodes through the beacons. Now the closest node to the source, initiates a local route repair process. First the node broadcasts a RouteRepair packet (local query LQ) to his neighbors. These packets contains a limited TTL (time to live). In the example below the TTL is too. After the broken link can be passed locally without flodding a new broadcast query from the source node.

If this node can't repair the broken link, the next node in direction to the source (the uplink node) reinitiates the local query broadcast. This process continues until the node in the middle of the broken path fails to repair the dead link. After the source is informed to start a new Route Discovery process.



Broken path: 8-13-15/Node 8 initiates the LQ broadcast/New path: 8-12-15

2. Node is moving
First the last node before the destination erases its route. Then a LQ process is initiated to check if the node is still reachable. If the target is reachable, it selects the best partial route and replies. Otherwise the LQ process is forwarded to the next upstream node. A Route Notification message is sent to the next upstream node to erase the invalid route and inform this node that it should take over the LQ process.
If this process results in backtracking more than halfway to the source, the LQ process is discontinued and the source initiates a new broadcast query process.

Route Delete

If a discovered route is no longer needed, the source node initiates a RouteDelete RD broadcast. All nodes along the route, delete the route entry from their routing list. The RD message is full broadcasted, because the source is not able to know if any path has changed during Route Reconstruction.

Advantages

Stable routes have a higher preference compared to shorter routes. Fewer pathes will break which reduces flooding (->bandwidth). In ABR a broken link is repaired locally, so the source node won’t start a new path-finding-process when a broken link appears.

Disadvantages

Stability informations are only used during the route selection process. Sometimes the chosen path may be longer than the shortest path, because of the preference given to stable paths, which is not nessacary a disadvantage. Local query broadcasts may result in high delays during the route repair.

References

[Murthy2004] All pictures
[Toh1996] Original paper
[Toh1997]
[Toh1999]

"Associativity-Based Routing" is mentioned on: Ad-Hoc Protocols (Classification) | Ad-Hoc Protocols (History) | Ad-Hoc Workshop Winter 04/05 (Termine) | On-Demand Associativity-Based Multicast | Signal Stability-based Adaptive Routing Protocol