Adaptive Demand-Driven Multicast Routing

ADMR

Adaptive Demand-Driven Multicast Routing protocol (ADMR) has been designed especially for the use in Ad-Hoc networks. The Multicast Routing state in ADMR is established dynamically and maintained only for groups that have at least one receiver and one active sender in the network. Multicast routing state in ADMR is dynamically established and maintained only for groups that have at least one receiver and one active sender in the network. Each multicast data packet is forwarded along the shortest delay path with multicast forwarding state, from the sender to the receivers. Here, sendders are not required to start or stop sending data to the group, or to join the group to which they wish to send. Furthermore, receivers dynamically adapt to the sending pattern of senders and mobility in the network. ADMR also detects when mobility in the network is too high to efficiently maintain multicast routing state, and instead reverts to flooding for a short period of time it determines that the high mobility has subsided.

Assumptions

• All nodes that wish to communicate with other nodes within the ad hoc network are willing to participate fully in the protocols of the network, e.g. Forwarding packets for other nodes in the network

• Diameter of the network is small (e.g. 5 or 10 hops) but often > 1 hop: Minimum number of hops necessary for a packet to reach from any node located at one extreme edge of the network to another node located at the opposite extreme
• Packets may be lost or corrupted in transmission on the wireless network; A node that receives such a packet can detect the error and discards the packet

• ADMR operates only over bidirectional links

• The multicast forwarding state for a given multicast group G and sender S is represented as a multicast forwarding tree rooted at S

Data Structures

The multicast forwarding state of ADMR is maintained locally by every node in the following three tables:

• Sender Table: Contains one entry for each multicast group address for which this node is an active sender. Each entry includes the inter-packet time for this node sending to the group and a count of consecutive keep-alive packets sent to the group since the last data packet sent to the group by this node.

• Membership Table: Contains one entry for each combination of multicast group address and sender address for which this node is either a receiver member or a forwarder characterized by a flag. Each entry includes the inter-packet time for the sender sending to this group and the keep-alive count from packets received for the group.

• Node Table: Contains for each node in the network from which this node has received a tree flooded or network flooded ADMR packet. Each entry in this table includes a Sequence Number from the ADMR header of the most recent such packet and a bitmap representing a number of previous sequence numbers of packets from this sender in order to detect and discard duplicate packets during a flood. Furthermore, each entry in this table includes the previous hop address.

ADMR consists of 3 phases:

1. Multicast State Setup
2. Multicast Packet Forwarding
3. Multicast State Maintenance

Multicast State Setup

This phase is set up when some new multicast sender S starts sending to a group G for which at least one receiver exists in the network, or when a receiver joins a group G for which there is at least one source in the network.

When an application running at source S sends a multicast packet targeted at group G when no routing state yet exists for this sender and group, the routing layer on S adds an ADMR header to the data packet and sends the data packet as a network flood. Each node in the network that receives this packet forwards it unless it has already forwarded a copy of it. In addition, the node records in its Node Table the MAC address of the node from which it received the packet, and the sequence number stored in the packet's ADMR header. This information will not only be used for duplicate detection but also for forwarding packets back to S. Furthermore, receivers for group G send a Reciever Join packet back towards S. Every node that forwards this packet creates a forwarding entry in its Membership Table for source S and group G, indicating that it is a forwarder for this sender and this group.

==> The collection of paths with forwarding state between S and the receivers for G produces the Forwarding Tree

==>

Multicast Packet Forwarding

Any packet with a multicast or broadcast destination containing an ADMR header will be flooded according to the flood type indicated by the flood type-flag in the header of ADMR packets which is mostly set to tree flood. In this case the packet will be forwarded only among those nodes belonging to the multicast forwarding tree indicated by the source address and destination address in the packet.



When a node receives such a packet it checks its Membership Table entry for this group and source to determine if it should forward the packet. The packet flows along the tree from the sender to the group receiver. If instead, the flood flag in the ADMR header indicades a network flood for the packet, the packet will be flooded among all nodes. For each kind of flood, each nodes Node Table and the sequence number in a packet`s ADMR header reliably limit any node that should forward the packet to do so at most once.

In the case, a node receives such a packet, wheater or not it forwards the packet, the receiving node compares the hop count in the received packets ADMR header to the hop count in this node`s Node Table entry for the source of the packet.
If the new hop count is less than that alredy recorded in the Node Table, this node updates the entry with the new value and sets the previous hop address in the entry to the MAC-Layer source address from which it received the packet. Additionally, if the node forwards the packet before, it increments the hop count field in the packet header and copies the MAC-Layer source address into the ADMR header previous hop address field.
Finally, the node checks its Membership Table to determine if it is a receiver member for this group and source and if so, it passes the packet up within the protocol stack to allow the packet to be processed as a received multicast packet.

Multicast State Maintenance

This mechanisms within ADMR is responsible for monitoring the forwarding tree for link breaks and for repairing these breaks when they occur. Maintenance in ADMR begins as soon as the multicast forwarding state is set up, and continues as long as the source application generates packets and there are receivers in the network interested in receiving these packets.

One of the fields in the ADMR header is the inter-packet time at which new packets should be expected from this sender S for this group G. This field in the ADMR header is initialized by S for each packet originated. This inter-packet time is used by members of the multicast forwarding tree to adaptively detect disconnection in the forwarding tree (e.g. Link Breaks), as well as inactive periods during which the source application does not send data temporarily and it will be more resource-efficient to expire the multicast state.

When some node C detects disconnection, it initiates a local repair of the multicast forwarding tree. Node C first sends a Repair Notification packet to the other nodes in the subtree "below" node C in the multicast distribution tree for group G and sender S. Here, the subtree "below" is defined by the previous hop address recorded in the Node Table of each node for sender S, such that any node whose previous hop for S is node C or is some other node below C is defined to be below C in the tree. After sending the Repair Notification packet, node C waits for a period of time REPAIR_DELAY before proceeding with its local repair.

Advantages

ADMR detects when mobility in the network is too high to efficiently maintain multicast routing state, and instead reverts to flooding for a short period of time it determines that the high mobility has subsided. Compared to other Multicast Ad-Hoc protocols like e.g. MAODV ADMR is the most efficient and has the lowest normalized packet overhead.

References

[Jor2001] Original Paper






"Adaptive Demand-Driven Multicast Routing" is mentioned on: Ad-Hoc Protocols (Classification)