April 26, 2000
Janne Salmi
Department of Computer Science and Engineering
Helsinki University of Technology
janski@cs.hut.fi
AODV is an ad hoc IP routing protocol that supports unicast, broadcast, and multicast. The routing decisions are made using distance vectors. The multicast operation of the protocol enables nodes that are not part of any multicast group to participate in forwarding the data and signal packets. A short comparison with a few other IP multicast routing protocols is included to provide perspective.
2.1 Route discovery
2.2 Route management
3.1 Route discovery
3.3 Multicast tree maintenance
3.4 Triggered repair of broken links
4 Comparison of AODV multicast features with other protocols
This paper discusses the multicast features of the Ad hoc On-demand Distance Vector [1] routing protocol. A short introduction to multicasting and ad hoc networking is given below.
There are three types of IPv4 addresses: unicast, broadcast, and multicast. Unicast addresses can be used for transmitting packets to a single destination. Broadcast addresses are used for sending datagrams to an entire subnetwork. Multicast addresses enable sending of datagrams to a set of hosts that may have zero or more members. The recipient hosts must be members of a multicast group, and they may reside in more than one subnetwork.
Multicasting is connectionless, and the traffic is datagram-based, much like a standard unicast IP datagram. Multicast datagrams are not guaranteed to reach all members of a group. Neither do they necessarily arrive in the same order which they were transmitted.
The difference between a multicast IP packet and a unicast IP packet is a 'group address' in the Destination Address field of the IP packet header. Multicast packets use a Class D address format, which ranges from 224.0.0.0 to 239.255.255.255 [2].
As a reactive protocol, the unicast operation of AODV consists of two modes of operation: route discovery and route management.
When a source node has to send data to a node for which no routing information exists, path discovery is initiated (Figure 1). The source node broadcasts a route request (RREQ) packet to its immediate neighbors.
The RREQ packet contains the address of the source node, the address of the destination node, a broadcast ID field, source sequence number (SSN), destination sequence number (DSN), and a hop count. The broadcast ID is unique to each RREQ that a given source node sends. DSN is used by intermediate nodes to determine whether their route for the destination is fresh enough. SSN is used for the same purpose when creating and maintaining reverse routes back to the source node.
When a node receives a RREQ message it has not seen before, it sets up a reverse route back to the node where the RREQ came from. The reverse route entry is stored along with the information about the requested destination address. If the node does not have the route to the requested destination, the RREQ is rebroadcast to the node's immediate neighbors. RREQ messages that have been seen before are not processed to avoid duplicate work and slower routes.
When a RREQ message is received by a node that has the requested route, the node generates a Route Reply (RREP) packet that contains the address of the source node, the address of the destination node, the broadcast ID field, source sequence number (SSN), destination sequence number (DSN), and the hop count. The RREP is sent to the node that relayed the RREQ.
When a node receives a RREP message it checks if the RREP has a higher DSN for the destination than possibly existing entries. This guarantees the freshness of the routes. The node where the RREP came from is set up as the next hop towards the destination.
If the source node moves during an active session, it can start a new route discovery process. Conversely, if an intermediate node or the destination node moves, it must send an unsolicited RREP informing the source node (and possible other intermediate nodes along the reverse path) of this.
If a node notices that a next hop on any of its routes is unreachable, it sends an unsolicited RREP message with a new destination sequence number and infinite hop count to the ``upstream'' members of its neighbor list that would need this hop. This kind of RREP is interpreted as a `teardown'' message and the affected routes are deleted. The message is forwarded until all affected source nodes are reached. A source node will begin a new route discovery process for the broken routes only if they are needed, so that excess signaling is avoided.
AODV supports a way of finding neighbors by means of special ``hello'' messages. These messages are unsolicited RREP messages with a time-to-live (TTL) value of 1, meaning that they will not be forwarded beyond the closest neighbors. The hello messages are sent periodically, and if a node stops receiving them from a neighbor, it is to assume that the link to the neighbor has gone down. Hello messages are not required, and they are redundant if the link layer technology provides a way of being aware of working links.
The AODV multicast algorithm uses similar RREQ and RREP messages as in unicast operation. The nodes join the multicast group on-demand, and a multicast tree is created in the process. The tree consists of the group members and nodes connected to the group members [2]. This enables a recipient host to join a multicast group even if it is more than one hop away from a multicast group member. The unicast operation of the protocol also benefits from the information that is gathered while discovering routes for multicast traffic. This cuts down the signaling traffic in the network.
When a node wishes to find a route for a multicast group, it sends an RREQ message. The destination address in the RREQ message is set to the address of the multicast group.
If the node wants to join the group in question, i.e., to become a multicast router, the J_flag in the message is set.
Any node may respond to a RREQ merely looking for a route, but only a router in the desired multicast tree may respond to a join RREQ. The corresponding RREP message may travel through nodes that are not members of the multicast group. This means that the eventual route may also include hops through non-member nodes (Figure 2).
The multicast RREP message is slightly different from the unicast RREP. The address of the multicast group leader is stored in a field called Group_Leader_Addr. In addition, there is a field called Mgroup_hop. This field is initialized to zero and it is incremented at each hop along the route. Mgroup_hop contains the distance in hops of the source node to the nearest member of the multicast tree.
Because the protocol relies on a group-wide DSN to ensure fresh routes, the group leader broadcasts periodical Group Hello messages. The Group Hello is an usolicited RREP message that has a TTL greater than the diameter of the network. The message contains extensions that indicate the multicast group addresses and the corresponding sequence numbers of all the groups for which the node is the group leader. The sequence number for each group is incremented each time the Group Hello is broadcast. The Hop_Cnt field in the message is initialized as zero and incremented by the intermediate nodes.
The nodes receiving the Group Hello use the information contained therein to update their request tables. If a node does not have an entry for the advertised multicast group, one is inserted. The hop counts are used to determine the current distance from the group leader.
In an network consisting of mobile nodes, link breakages are bound to happen. The breakages should be repaired promptly to ensure maximal connectivity of the multicast group. Multicast tree maintenance has three different scenarios: activating a link when a new node joins the group, pruning the tree when a node leaves the group, and repairing a broken link. Repairing consists of re-establishing the branches when a link goes down and reconnecting the tree after a possible partition in the network.
If a node receives more than one RREP to a RREQ it has sent, it must pick only one RREP as the next hop. This way no extra branches are added to the tree and loops are avoided. The source node waits for a specified Route Discovery timeout after it has sent an RREQ.
After the timeout period has passed, the received route that has the greatest DSN and the fewest hops to the nearest member of the multicast tree is selected. The node then unicasts a a multicast-specific message called Multicast Activation (MACT) to the selected next hop.
The MACT message carries the source address, SSN, destination address and flags P_flag and GL_flag. P_flag is used in case of pruning and GL_flag is set when choosing the multicast group leader, as will be explained later.
When a group member receives a MACT message, it enables the entry for the source node in the its own multicast routing table. If a node that is not a group member receives a MACT message, it acts in a similar way as the source node. A new MACT is sent to the best next hop towards the multicast group. Those nodes that have generated or forwarded RREP messages delete the corresponding route entries from their routing tables if they do not receive a MACT within a specified Multicast Tree Build timeout period.
The multicast tree can never have multiple paths to any tree node because the MACT messages are only propagated through one path. Hence, the tree is indeed a tree. Because the nodes forward data only along the activated routes in their routing tables, the data can never be forwarded to the source node by multiple intermediate nodes.
Multicast group members sometimes remove themselves from the group. If a non-leaf node decides to leave the group it must continue as a router for the multicast tree. Leaf nodes may prune themselves by sending a MACT message with the P_flag (prune) set. The Dest_addr of the message points to the multicast group in question.
Because a leaf node can only have one next hop node for the multicast group, the MACT can be unicast to that node. After the MACT has been sent, information about the group can be removed from the route table. When the recipient of the MACT notices the P_flag it deletes the entry for the sender of the MACT from its own route table. If the recipient is not a member of the multicast group and it would become a leaf node after this operation, it can prune itself from the multicast tree using the same method. The pruning process terminates when it reaches either a multicast group member or a non-leaf node.
Timeouts and node mobility cause links to break within the multicast tree. In multicast operation routes must be reconstructed when a link goes down because the group members must stay connected.
If a node does not receive Group Hello messages from a neighbor within an acceptable timeout period, the link between the two nodes is considered broken (Figure 3). The node that is further from the multicast group leader tries to rejoin the group as explained earlier. The RREQ carries a Multicast Group Leader Extension with a Hop Count that equals the distance to the group leader. However, the RREQ message is first broadcast with a restricted TTL value (two more than the recorded Multicast Group Hop Count). Because only one node starts the repair process, loops and duplicate work can be avoided. The use of small TTL is an effort to keep the effects of the link breakage local. Only if no RREP is received within a timeout period, the RREQ is rebroadcast over the whole network.
Only a node that is nearer to the group leader than the RREQ hop count indicates is allowed to respond to the request. Duplicate RREPs are discarded. When a RREP has been received, the route must be activated. If the node was not a leaf node, it must also inform the downstream nodes of possible changes in distance to the group leader. In this case, a MACT message with a U_flag (Update) is broadcast. The update messages are ignored by those nodes who are not downstream neighbors of the sender.
If the node that started the repair process never gets a RREP after a set number of retries, there has been a partition of the network (Figure 4). In this case a new group leader must be elected. If the said node was a part of the multicast group, it becomes the new group leader. Otherwise it sends a pruning MACT message to its next hop, if there is only one of them. When the next hop node receives the MACT with P_flag set, it has the same options as the originating node. This is repeated until a new group leader is found.
If there are more than one next hop downstream, a node cannot prune itself. Instead it sends a MACT with GL_flag (Group Leader) set to the first of its next hops. This process is repeated until a multicast group member receives the MACT. This node then becomes the new group leader and it broadcasts a Group Hello message with U_flag set. The nodes who receive the Hello then update their route tables accordingly.
Meanwhile, if the node upstream of the breakage became a non-member leaf node, it waits for a MACT from the downstream node. If it is not received within a set timeout period, the node prunes itself from the tree.
After a network partition there are two group leaders (Figure 5). A node can detect reconnection of the partitions if it receives a Group Hello with conflicting information about the group leader and hop count. The group leader that has the lower IP address (L2) initiates the repair process by sending a RREQ with R_flag(Repair) and J_flag set to the other group leader with the higher IP address (L1). The RREQ is sent via the next hop from which the Hello message was received. The current DSN for L2 is included in the message. The RREQ is only propagated upstream towards L1 so no loops can appear.
When L1 receives the RREQ it creates a new DSN that is higher than its own or the one carried by the RREQ. It sends back a RREP message with the R_flag set and becomes the new leader.
The nodes that used to belong to the group lead by L2 propagate the RREP towards L2. The node where the RREP was received from is marked as the next hop upstream and the next hop towards L2 is marked as being downstream. When L2 finally receives the message, it acknowledges L1 as the new leader, thus completing the reconnection of the tree. The next time that L1 sends a Hello message, it sets the U_flag so that all the nodes will update their routing information.
Traditional IP routing protocols for multicasting such as DVMRP [4] and MOSPF [5] also work by sending advertisement messages similar to the Group Hello messages of AODV. The algorithms for actually creating the paths between routers differ. AODV is also different in the way that any node that is not a multicast group member itself can always act as a router for hosts willing to join the group.
DVRMP and MOSPF do not try actively to repair broken links like AODV. However, MOSPF routers adapt to changes in multicast tree topology by recalculating link states according to the advertisement messages they receive. DVRMP is more passive when a link breakage occurs.
Understandably none of the mentioned protocols can make use of each others' messages. Even so, because the multicast addressing scheme is standard, a router running MOSPF can forward multicast packets to an AODV router if a static route is set up between the two.
At the moment there are two other proposals for multicast ad hoc routing protocols by the MANET working group, ODMRP [6] and Dynamic Source Routing (DSR) [7]. ODMRP is only a multicast routing protocol. Instead of creating a tree, ODMRP uses a mesh-based solution. DSR is similar in AODV in that it is both unicast and multicast -capable. It is based on the source routing concept which can limit its usefulness in existing IP network frameworks which are usually designed for next hop -based routing. On the other hand, DSR supports unidirectional links which is an advantage in wireless networks.
This paper has discussed the features of AODV multicast operation. Its nature as an ad hoc multicasting protocol makes it very useful for wireless networks with a need for multi-hop routes. Because any node can join the multicast group through multiple hops via non-member nodes, the need for broadcast traffic in such networks is effectively reduced. In wireless multi-hop networks this can mean considerable savings in power consumption of the nodes that are not participating in the multicast tree.
Because AODV can be used both for unicast and multicast routing, the two operational modes can benefit from each other's signaling messages. This makes designing an implementation of the routing software easier than having to design communication between separate unicast and multicast protocols. It also helps reduce signaling traffic.
Simulated comparison with DSR has shown that AODV does not perform well in networks with few nodes and little mobility [8]. In networks with more load, more nodes and higher mobility AODV outperformed DSR, at the expense of generating more routing load on the network.
The protocol adapts to topology changes, link breakages, and network partitions actively. These features make AODV more usable for a mobile user than traditional multicast routing protocols. However, there are also other ad hoc multicast protocols proposed by the MANET working group and others are yet to be introduced. What will be the future MANET standard protocol for ad hoc multicast routing, remains to be seen.
| [1] | Ad Hoc On Demand Distance Vector (AODV) protocol, Internet Draft
(work in progress) < http://www.ietf.org/internet-drafts/draft-ietf-manet-aodv-05.txt > |
| [2] | RFC 1112 Requirements for Internet Hosts -- Communication Layers < ftp://ftp.funet.fi/pub/doc/rfc/rfc1112.txt > |
| [3] | Royer, Perkins: Multicast operation of the AODV routing protocol
(Proceedings of MobiCom '99, Seattle, WA, August 1999, pp. 207-218) < http://alpha.ece.ucsb.edu/~eroyer/txt/aodv_Mobicom.ps > |
| [4] | RFC 1075 Distance Vector Multicast Routing Protocol < ftp://ftp.funet.fi/pub/doc/rfc/rfc1075.txt > |
| [5] | RFC 1584 Multicast Open Shortest Path First (MOSPF) < ftp://ftp.funet.fi/pub/doc/rfc/rfc1584.txt > |
| [6] | On-Demand Multicast Routing Protocol (ODMRP), Internet Draft (work
in progress) < http://www.ietf.org/internet-drafts/draft-ietf-manet-odmrp-02.txt > |
| [7] | Dynamic Source Routing (DSR), Internet Draft (work in progress) < http://www.ietf.org/internet-drafts/draft-ietf-manet-dsr-03.txt > |
| [8] | Das, Perkins, and Royer: Performance Comparison of Two On-demand
Routing Protocols for Ad Hoc Networks (Proceedings of the IEEE
Conference on Computer Communications (INFOCOM), Tel Aviv, Israel,
March 2000, pp. 3-12.) < http://beta.ece.ucsb.edu/~eroyer/txt/aodv_infocom.ps > |
