On-Demand Associativity-Based Multicast

ABAM

ABAM is an on-demand source-based routing protocol for mobile ad-hoc networks (MANETs). It establishes multicast sessions on demand and and utilizes the association stability concept that is adopted in the ABR for mobile ad-hoc unicast routing. For each multicast session a multicast tree is estabilished primarily based on association stability.

ABAM consists of 3 phases:

Multicast Tree Establishment
Multicast Tree Reconfigurations
Multicast Tree Deletion

Multicast Tree Establishment

A multicast sender node A broadcasts MBQ (Multicast Broadcast Query) messages throughout the network in order to activate the multicast session. Receiving nodes will add their addresses and other data to the MBQ message before the message is rebroadcasted.
==> Each MBQ message stacks information about the visited path while it is forwarded.

From all the possible routes back the most stable will be chosen and the MBQ-REPLY will be sent back to the multicast sender using the selected path. One MBQ-REPLY from each multicast receiver will be received by the multicast sender node A. The multicast sender node A computes a stable multicast tree with all incoming that results in shared links and generate an MC-SETUP message in order to establish the multicast tree. This MC-SETUP message will be published to all nodes along the tree. Consequently these nodes will be instructed to join in the multicast forwarding process.

As shown in the Figure above, the three receivers send MBQ-REPLY messages back to the sending node A. In the following, the A sends the MC-SETUP message in order to establish the multicast tree.

Multicast Tree Reconfiguration

Assuming the nodes moving within the tree, tree reconfigurations are necessary to match thee existing multicast tree. Different methods are embedded in ABAM to deal with mobility:

Branch Repair - when the receiver moves
Subtree Repair - when branching node moves
Full Tree Repair - when the source node moves

Generally, tree reconfiguration is needed when link breakage is observed. ABAM utilizes the localized repair strategy where the node upstream the broken link broadcasts a LQ (Local Query) message. The number of hops to the furthest hindered receiver determines the maximum number of hops the LQ message can be spread. In the following, the receiver replies with a LQ-REPLY message and the MC-SETUP message is again used to build the branch. In the case of failure of the LQ process the direct upstream node will be informed to start another LQ process. This will proceed as long as the LQ succeeds in finding either a path to the moved node or until the branching node is reached or even until the moved receiver node's timer has expired. Subsequently, the moved receiver will send a JQ join request to connect again to the multicast tree.
Several receivers, those who are not covered by the LQ process, will start their own JQ process. As a result, repair operations are allowed to be initiated by nodes on the tree as well as by moved nodes by themselves, in ABAM. Both, RN (Route Notification) and RU (Route Update) messages are helpful to simplify the reconfiguration process by informing about route failure and by updating the false state accordingly.

The ABAM protocol allows subtree repair, where the upstream node of the moved branching node starts a subtree operation. The main idea in this process is the performance of a scoped LQ broadcast to the farthest affected receiver. Consequently, a new partial tree is discovered and established in the same way as in the tree establishment process.

Multicast Tree Deletion

In the event that a receiver wants to leave a multicast group, he sends a LEAVE message. This causes a branch being pruned, if there is no other receiver in that branch. Assuming the case that all receivers want to leave the group, which means that the multicast group has no more receivers, the tree will be pruned incrementally. Furthermore, if the source node A no longer wants to act as a multicast sender he sends a multicast DELETE message and the multicast tree can be deleted consequently.

Handling Multicast Group Member Dynamics

In the ABAM protocol a new multicast receiver is allowed to join an existing multicast tree by performing a JQ broadcast. Comparable to the MBQ message, JQ accumulates the data of visited paths nodes as it is forwarded. Just the on-tree nodes will respond to this request by sending JQ-REPLY messages back to the new multicast receiver. In the following, the receiver or moved node selects the best quality path among all the JQ-REPLYs and sends a MC-ATTACH message to introduce a branch to the existing multicast tree.

Advantages

ABAM incurs smaller communication overhead than other protocols, like e.g. ODMRP and results in good end-to-end delay.

Disadvantages

During the Multicast Tree Establishment phase the MBQ broadcast allows the MBQ packets to be forwarded more than once if the succeeding MBQ assures a better route. Although this techniques offers better alternatives for route selection it results in a bit more overhead.
Furthermore, the amount of storage required by ABAM is very big. Assuming S to be the number of senders and G the number of groups. Usually the size of a unicast routing table is O(S) and the list of forwarding group flags is O(G), which is very small. The ABAM protocol is source-based, which means that it has to store tracks of multiple trees, for each multicast session one. Consequently, ABAM's routing table grows as O(S*G).

References

[Toh2000] Original paper

"On-Demand Associativity-Based Multicast" is mentioned on: Ad-Hoc Protocols (Classification)