[Docs] [txt|pdf] [Tracker] [WG] [Email] [Nits]
Versions: 00
Mobile Ad Hoc Networking Working Group Elizabeth M. Royer
INTERNET DRAFT University of California, Santa Barbara
15 July 2000 Charles E. Perkins
Nokia Research Center
Multicast Ad hoc On-Demand Distance Vector (MAODV) Routing
draft-ietf-manet-maodv-00.txt
Status of This Memo
This document is a submission by the Mobile Ad Hoc Networking Working
Group of the Internet Engineering Task Force (IETF). Comments should
be submitted to the manet@itd.nrl.navy.mil mailing list.
Distribution of this memo is unlimited.
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at
any time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at:
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at:
http://www.ietf.org/shadow.html.
Abstract
The multicast operation of the Ad hoc On-Demand Distance Vector
(AODV) routing protocol (MAODV) is intended for use by mobile nodes
in an ad hoc network. It offers quick adaptation to dynamic link
conditions, low processing and memory overhead, and low network
utilization. It creates bi-directional shared multicast trees
connecting multicast sources and receivers. These multicast trees
are maintained as long as group members exist within the connected
portion of the network. Each multicast group has a group leader
whose responsibility is maintaining the group sequence number, which
is used to ensure freshness of routing information.
Royer, Perkins Expires 15 December 2000 [Page i]
Internet Draft Multicast AODV 15 July 2000
Contents
Status of This Memo i
Abstract i
1. Introduction 2
2. Overview 2
3. Route Tables 3
4. MAODV Terminology 5
5. Route Request (RREQ) Message Format 6
6. Route Reply (RREP) Message Format 6
7. Multicast Activation (MACT) Message Format 7
8. Group Hello (GRPH) Message Format 8
9. Protocol Operation 9
9.1. Maintaining Multicast Tree Utilization Records . . . . . 9
9.2. Generating Route Requests . . . . . . . . . . . . . . . . 9
9.2.1. Controlling Route Request broadcasts . . . . . . 10
9.3. Receiving Route Requests . . . . . . . . . . . . . . . . 10
9.4. Generating Route Replies . . . . . . . . . . . . . . . . 11
9.5. Forwarding Route Replies . . . . . . . . . . . . . . . . 12
9.6. Route Activation . . . . . . . . . . . . . . . . . . . . 12
9.7. Multicast Tree Pruning . . . . . . . . . . . . . . . . . 13
9.8. Repairing a Broken Link . . . . . . . . . . . . . . . . . 14
9.9. Tree Partitions . . . . . . . . . . . . . . . . . . . . . 16
9.10. Reconnecting Two Trees . . . . . . . . . . . . . . . . . 17
9.11. Maintaining Local Connectivity . . . . . . . . . . . . . 17
9.12. Group Hello Messages . . . . . . . . . . . . . . . . . . 18
9.13. Actions After Reboot . . . . . . . . . . . . . . . . . . 19
9.14. Interfaces . . . . . . . . . . . . . . . . . . . . . . . 20
10. Extensions 20
10.1. Multicast Group Leader Extension Format . . . . . . . . . 20
10.2. Multicast Group Rebuild Extension Format . . . . . . . . 21
10.3. Multicast Group Information Extension Format . . . . . . 21
11. Configuration Parameters 22
Royer, Perkins Expires 15 December 2000 [Page 1]
Internet Draft Multicast AODV 15 July 2000
12. Security Considerations 23
1. Introduction
The Multicast Ad hoc On-Demand Distance Vector (MAODV) protocol
enables dynamic, self-starting, multihop routing between
participating mobile nodes wishing to join or participate in a
multicast group within an ad hoc network. The membership of these
multicast groups is free to change during the lifetime of the
network. MAODV enables mobile nodes to establish a tree connecting
multicast group members. Mobile nodes are able to respond quickly
to link breaks in multicast trees by repairing these breaks in a
timely manner. In the event of a network partition, multicast trees
are established independently in each partition, and trees for the
same multicast group are quickly connected if the network components
merge.
One distinguishing feature of MAODV is its use of sequence numbers
for multicast groups. Each multicast group has its own sequence
number, which is initialized by the multicast group leader and
incremented periodically. Using these sequence numbers ensures that
routes found to multicast groups are always the most current ones
available. Given the choice between two routes to a multicast tree,
a requesting node always selects the one with the greatest sequence
number.
MAODV is the multicast protocol associated with the Ad hoc On-Demand
Distance Vector (AODV) routing protocol, and as such it shares many
similarities and packet formats with AODV. The Route Request and
Route Reply packet types are based on those used by AODV, as is the
unicast Route Table. Similarly, many of the configuration parameters
used by MAODV are defined by AODV. The reader is referred to the AODV
Internet draft [2] for the suggested values of those parameters, as
well as for details on the unicast operation of AODV.
2. Overview
Route Requests (RREQs), Route Replies (RREPs), Multicast Activations
(MACTs), and Group Hellos (GRPHs) are the message types utilized
by the multicast operation AODV. RREQs and RREPs are handled as
specified in [2], except for certain procedures controlled by new
flags (see section 5, 6). These message types are handled by UDP,
and normal IP header processing applies. So, for instance, the
requesting node is expected to use its IP address as the source IP
address for the messages. The range of dissemination of broadcast
RREQs can be indicated by the TTL in the IP header. Fragmentation is
typically not required.
Royer, Perkins Expires 15 December 2000 [Page 2]
Internet Draft Multicast AODV 15 July 2000
As long as the multicast group members remain connected (within
a ``multicast tree''), MAODV does not play any role. When a
node either wishes to join a multicast group or find a route to a
multicast group, the node uses a broadcast RREQ to discover a route
to the multicast tree associated with that group. For join requests,
a route is determined when the RREQ reaches a node that is already a
member of the multicast tree, and the node's record of the multicast
group sequence number is at least as great as that contained in the
RREQ. For non-join requests, any node with a current route to the
multicast tree may respond to the RREQ. A current route is defined as
an unexpired multicast route table entry whose associated sequence
number for the multicast group is at least as great as that contained
in the RREQ. The route to the multicast tree is made available by
unicasting a RREP back to the source of the RREQ. Since each node
receiving the request caches a route back to the source of the
request, the RREP can be unicast back to the source from any node
able to satisfy the request. Once the source node has waited the
discovery period to receive RREPs, it selects the best route to the
multicast tree and unicasts the next hop along that route a MACT
message. This message activates the route.
Nodes monitor the link status of next hops on the multicast tree.
When a link break on the multicast tree is detected, the tree branch
should be immediately repaired through the use of the RREQ/RREP/MACT
messages.
A multicast group leader is associated with each multicast group.
The primary responsibility of this node is the initialization and
maintenance of the group sequence number. A Group Hello message is
periodically broadcast across the network by the multicast group
leader. This message carries a multicast group and group sequence
number and corresponding group leader IP address. This information
is used for disseminating updated group sequence numbers throughout
the multicast group and for repairing multicast trees after a
previously disconnected portion of the network containing part of the
multicast tree becomes reachable once again.
3. Route Tables
MAODV is a routing protocol, and it deals with route table
management. Route table information must be kept even for ephemeral
routes, such as are created to temporarily store reverse paths
towards nodes originating RREQs. MAODV uses the following fields
with each route table entry, which are based on the route table
defined in the AODV Internet Draft [2]:
- Destination IP Address
Royer, Perkins Expires 15 December 2000 [Page 3]
Internet Draft Multicast AODV 15 July 2000
- Destination Sequence Number
- Hop Count (number of hops needed to reach destination)
- Last Hop Count (described in subsection 9.2.1)
- Next Hop
- Next Hop Interface
- List of Precursors
- Lifetime (expiration or deletion time of the route)
- Routing Flags
The following information is stored in each entry of the multicast
route table for multicast tree routes:
- Multicast Group IP Address
- Multicast Group Leader IP Address
- Multicast Group Sequence Number
- Next Hops
- Hop Count to next Multicast Group Member
- Hop Count to Multicast Group Leader
The Next Hops field is a linked list of structures, each of which
contains the following fields:
- Next Hop IP Address
- Next Hop Interface
- Link Direction
- Activated Flag
The direction of the link is relative to the location of the group
leader, i.e. UPSTREAM is a next hop towards the group leader, and
DOWNSTREAM is a next hop away from the group leader. A node on the
multicast tree must necessarily have only one UPSTREAM link. The IP
Address of a Next Hop MUST NOT be used to forward multicast messages
until after a MACT message has activated the route (see Section 9.6).
The Next Hop Interface fields in the Route Table and Next Hop field
of the Multicast Route Table are used for recording the outgoing
interface on which the next hop can be reached (see Section 9.14).
Nodes MAY also maintain a Group Leader Table, which is an association
between multicast groups and their corresponding group leaders. The
fields of the group leader table are the following:
Royer, Perkins Expires 15 December 2000 [Page 4]
Internet Draft Multicast AODV 15 July 2000
- Multicast Group IP Address
- Group Leader IP Address
This table can be used when discovering routes to multicast groups,
as described in Section 9.2.
4. MAODV Terminology
This protocol specification uses conventional meanings [1] for
capitalized words such as MUST, SHOULD, etc., to indicate requirement
levels for various protocol features. This section defines other
terminology used with MAODV that is not already defined in [3].
group leader
A node which is a member of the given multicast group
and which is typically the first such group member in the
connected portion of the network. This node is responsible for
initializing and maintaining the multicast group destination
sequence number.
group leader table
The table where ad hoc nodes keep information concerning each
multicast group and its corresponding group leader. There is
one entry in the table for each multicast group for which the
node has received a Group Hello (see Section 9.2).
multicast tree
The tree containing all nodes which are members of the
multicast group and all nodes which are needed to connect the
multicast group members.
multicast route table
The table where ad hoc nodes keep routing (including next hops)
information for various multicast groups.
reverse route
A route set up to forward a reply (RREP) packet back to the
source from the destination or from an intermediate node having
a route to the destination.
Royer, Perkins Expires 15 December 2000 [Page 5]
Internet Draft Multicast AODV 15 July 2000
5. Route Request (RREQ) Message Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type |J|R|G| Reserved | Hop Count |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Other fields as specified for AODV.......
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The format of the Route Request message remains as specified in [2],
except that the following flags have been added:
J Join flag; set when source node wants to join a
multicast group.
R Repair flag; set when a node wants to initiate
a repair to connect two previously disconnected
portions of the multicast tree.
When a node wishes to repair a multicast tree, it appends the
Multicast Group Rebuild extension (see Section 10.2). When a node
wishes to unicast the RREQ for a multicast group to the group leader,
it includes the Multicast Group Leader extension (see Section 10.1).
6. Route Reply (RREP) Message Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type |R| Reserved |Prefix Sz| Hop Count |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Other fields as specified for AODV.......
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The format of the Route Reply message remains as specified in [2],
except that the following flag has been added:
R Repair flag; set when a node is responding
to a repair request to connect two previously
disconnected portions of the multicast tree.
When the RREP is sent for a multicast destination, the Multicast
Group Information extension is appended (see Section 10.3).
Royer, Perkins Expires 15 December 2000 [Page 6]
Internet Draft Multicast AODV 15 July 2000
7. Multicast Activation (MACT) Message Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type |J|P|G|U|R| Reserved | Hop Count |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multicast Group IP address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source IP address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The format of the Multicast Activation message is illustrated above,
and contains the following fields:
Type 4
J Join flag; set when a node is joining the multicast
group, as opposed to finding a route to the group for
the transmission of data messages.
P Prune flag; set when a node wishes to prune itself
from the tree, unset when the node is activating a
tree link.
G Group Leader flag; set by a multicast tree member that
fails to repair a multicast tree link breakage, and
indicates to the group member receiving the message
that it should become the new multicast group leader.
U Update flag; set when a multicast tree member has
repaired a broken tree link and is now a new distance
from the group leader.
R Reboot flag; set when a node has just rebooted (see
Section 9.13).
Reserved Sent as 0; ignored on reception.
Hop Count The distance of the sending node from the multicast
group leader. Used only when the 'U' flag is set;
otherwise sent as 0.
Multicast Group IP Address
The IP address of the Multicast Group for which a
route is supplied.
Royer, Perkins Expires 15 December 2000 [Page 7]
Internet Draft Multicast AODV 15 July 2000
Source IP Address
The IP address of the sending node.
Source Sequence Number
The current sequence number for route information
generated by the source of the route request.
To prune itself from the tree (i.e., inactivate its last link to the
multicast tree), a multicast tree member sends a MACT with the 'P'
flag = 1 to its next hop on the multicast tree. A multicast tree
member that has more than one next hop to the multicast tree SHOULD
NOT prune itself from the multicast tree.
8. Group Hello (GRPH) Message Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type |U|O| Reserved | Hop Count |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Group Leader IP address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multicast Group IP address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multicast Group Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The format of the Group Hello message is illustrated above, and
contains the following fields:
Type 5
U Update flag; set when there has been a change in group
leader information.
O Off_Mtree flag; set by a node receiving the group
hello that is not on the multicast tree.
Reserved Sent as 0; ignored on reception.
Hop Count The number of hops the packet has traveled. Used by
multicast tree nodes to update their distance from the
group leader when the M flag is not set.
Group Leader IP Address
The IP address of the group leader.
Royer, Perkins Expires 15 December 2000 [Page 8]
Internet Draft Multicast AODV 15 July 2000
Multicast Group IP Address
The IP address of the Multicast Group for which the
sequence number is supplied.
Multicast Group Sequence Number
The current sequence number of the multicast group.
9. Protocol Operation
This section describes the scenarios under which nodes generate
control messages for multicast communication, and how the fields in
the messages are handled.
9.1. Maintaining Multicast Tree Utilization Records
For each multicast tree to which a node belongs, either because
it is a member of the group or because it is a router for the
multicast tree, the node maintains a list of next hops -- i.e., those
1-hop neighbors that are likewise a part of the multicast tree.
This list of next hops is used for forwarding messages received
for the multicast group. A node forwards a multicast message to
every such next hop, except that neighbor from which the message
arrived. If there are multiple next hops, the forwarding operation
MAY be performed by broadcasting the multicast packet to the node's
neighbors; only the neighbors that belong to the multicast tree
and have not already received the packet continue to forward the
multicast packet.
9.2. Generating Route Requests
A node sends a RREQ either when it determines that it should be a
part of a multicast group, and it is not already a member of that
group, or when it has a message to send to the multicast group but
does not have a route to that group. If the node wishes to join the
multicast group, it sets the `J' flag in the RREQ; otherwise, it
leaves the flag unset. The destination address of the RREQ is always
set to the multicast group address. If the node knows the group
leader and has a route to it, the node MAY place the group leader's
address in the Multicast Group Leader extension (Section 10.1), and
unicast the RREQ to the corresponding next hop for that destination.
Otherwise, if the node does not have a route to the group leader, or
if it does not know who the multicast group leader is, it broadcasts
the RREQ and does not include the extension field.
After transmitting the RREQ, the node waits for the reception of a
RREP. The node may resend the RREQ up to RREQ_RETRIES additional
Royer, Perkins Expires 15 December 2000 [Page 9]
Internet Draft Multicast AODV 15 July 2000
times if a RREP is not received. If a RREQ was unicast to a group
leader and a RREP is not received within RREP_WAIT_TIME milliseconds,
the node broadcasts subsequent RREQs for that multicast group across
the network. If a RREP is not received after RREQ_RETRIES additional
requests, the node may assume that there are no other members of that
particular group within the connected portion of the network. If it
wanted to join the multicast group, it then becomes the multicast
group leader for that multicast group and initializes the sequence
number of the multicast group. Otherwise, if it only wanted to send
packets to that group without actually joining the group, it drops
the packets it had for that group and aborts the session.
When the node wishes to join or send a message to a multicast group,
it first consults its Group Leader Table. Based on the existence
of an entry for the multicast group in this table, the node then
formulates and sends the RREQ as described at the beginning of this
section.
9.2.1. Controlling Route Request broadcasts
To prevent unnecessary network-wide broadcasts of RREQs, the source
node SHOULD use an expanding ring search technique as specified
in [2]. When a RREP is received, the Hop Count to the group leader
used in the RREP packet is remembered as Last Hop Count for that node
in the routing table. When a new route to the same multicast group
is required at a later time (e.g., upon a link break in the multicast
tree), the TTL in the RREQ IP header is initially set to this Last
Hop Count plus TTL_INCREMENT. Thereafter, following each timeout the
TTL is incremented by TTL_INCREMENT until TTL = TTL_THRESHOLD is
reached, as in [2].
9.3. Receiving Route Requests
When a node receives a RREQ, the node checks whether the 'J' flag of
the RREQ is set. If the 'J' flag is set, the node can only respond
if it is a member of the multicast tree for the indicated multicast
group, and if its record of the multicast group sequence number is
at least as great as that contained in the RREQ. If the 'J' flag is
not set, then the node can respond if it has an unexpired route to
the multicast group and the above multicast group sequence number
criteria is met.
If the node does not meet either of these conditions, it rebroadcasts
the RREQ from its interface(s) but using its own IP address in the IP
header of the outgoing RREQ. The Destination Sequence Number in the
RREQ is updated to the maximum of the existing Destination Sequence
Number in the RREQ and the multicast group sequence number in the
Royer, Perkins Expires 15 December 2000 [Page 10]
Internet Draft Multicast AODV 15 July 2000
multicast route table (if an entry exists) of the current node. The
TTL or hop limit field in the outgoing IP header is decreased by one.
The Hop Count field in the broadcast RREQ message is incremented by
one, to account for the new hop through the intermediate node.
The node always creates or updates a reverse route as specified
in [2]. This reverse route would be needed in case the node
receives an eventual RREP back to the node which originated the RREQ
(identified by the Source IP Address).
In addition to creating or updating the route table entry for the
source node, the node receiving the RREQ also creates a next hop
entry for the multicast group in its multicast route table. If no
entry exists for the multicast group, it creates one, and then places
the node from which it received the RREQ as next hop for that group.
It leaves the Activated flag associated with this next hop unset.
The direction for this next hop entry is DOWNSTREAM.
9.4. Generating Route Replies
If a node receives a join RREQ for a multicast group, and it is
already a member of the multicast tree for that group, the node
updates its multicast route table and then generates a RREP message.
The Source and Destination IP Addresses in RREQ message are copied
to corresponding fields in the RREP message. The RREP contains the
current sequence number for the multicast group and the IP address
of the group leader. Furthermore, the node initializes the Hop
Count field of the RREP to zero. Additional information about the
multicast group is entered into the Multicast Group Information
extension (see Section 10.3). It unicasts the RREP back to the node
indicated by the Source IP Address field of the received RREQ.
A node can respond to a join RREQ only if it is a member of the
multicast tree. If a node receives a multicast route request that
is not a join message, it can reply if it has a current route to the
multicast tree. Otherwise it continues forwarding the request. If a
node receives a join RREQ for a multicast group and it is not already
a member of the multicast tree for that group, it rebroadcasts the
RREQ to its neighbors.
When a node receives a RREQ for a multicast group which has its own
IP address in the Destination IP address of the IP header, that
means that the source node expects this destination node to be the
multicast group leader. In this case, if the node is in fact not the
group leader, it can simply ignore the RREQ. The source node will
time out after RREP_WAIT_TIME milliseconds and will broadcast a new
RREQ without the group leader address specified.
Royer, Perkins Expires 15 December 2000 [Page 11]
Internet Draft Multicast AODV 15 July 2000
Regardless of whether the multicast group leader or a multicast tree
member generates the RREP, the RREP fields are set as follows:
Hop Count 0
Destination IP Address
The IP address of the multicast group.
Destination Sequence Number
The current multicast group sequence number.
Lifetime The time for which nodes receiving the RREP consider
the route to be valid (only used it the RREQ is not a
join request).
The Multicast Group Information extension described in Section 10.3
is also included for join requests. If the node generating the RREP
is not on the multicast tree (because the RREQ was not a join RREQ),
it places its distance from the multicast tree in the Hop Count
field, instead of 0.
9.5. Forwarding Route Replies
If an intermediate node receives a RREP in response to a RREQ that it
has transmitted (or retransmitted on behalf of some other node), it
creates a multicast group next hop entry for the node from which it
received the RREP. The direction of this next hop is UPSTREAM, and
the Activated flag is left unset. Additionally, the node updates
the Lifetime field in the route table entry associated with the node
from which it received the RREP. It then increments the Hop Count and
Multicast Group Hop Count fields or the RREP and forwards this packet
along the path to the source of the RREQ.
When the node receives more than one RREP for the same RREQ, it saves
the route information with the greatest sequence number, and beyond
that the lowest hop count; it discards all other RREPs. This node
forwards the first RREP towards the source of the RREQ, and then
forwards later RREPs only if they have a greater sequence number or
smaller metric.
9.6. Route Activation
When a node broadcasts a RREQ message, it is likely to receive more
than one reply since any node in the multicast tree can respond. The
RREP message sets up route pointers as it travels back to the source
node. If the request is a join request, these route pointers may
eventually graft a branch onto the multicast tree. Also, because
Royer, Perkins Expires 15 December 2000 [Page 12]
Internet Draft Multicast AODV 15 July 2000
multicast data packets may be transmitted as broadcast traffic, the
route to the multicast tree must be explicitly selected. Otherwise,
each node with a route to the tree which receives a multicast data
packet will rebroadcast the packet, resulting in an inefficient use
of network bandwidth. Hence, it is necessary to activate only one
of the routes created by the RREP messages. The RREP containing
the largest destination sequence number is chosen to be the branch
added to the multicast tree (or the path to the multicast tree, if
the request was a non-join). In the event that a node receives more
than one RREP with the same (largest) sequence number, it selects the
first one with the smallest hop count, i.e., the shortest distance to
a member of the multicast tree.
After waiting RREP_WAIT_TIME milliseconds, the node must select the
route it wishes to use as its link to the multicast tree. This is
accomplished by sending a Multicast Activation (MACT) message. The
Destination IP Address field of the MACT packet is set to the IP
address of the multicast group. If the node is joining the multicast
group, it sets the join flag of this message. The node unicasts this
message to the selected next hop, effectively activating the route.
It then sets the Activated flag in the next hop Multicast Route Table
entry associated with that node. After receiving this message, the
node to which the MACT was sent activates the route entry for the
link in its multicast route table, thereby finalizing the creation of
the tree branch. All neighbors not receiving this message time out
and delete that node as a next hop for the multicast group in their
route tables, having never activated the route entry for that next
hop.
Two scenarios exist for a neighboring node receiving the MACT
message. If this node was previously a member of the multicast
tree, it does not propagate the MACT message any further. However,
if the next hop selected by the source node's MACT message was not
previously a multicast tree member, it will have propagated the
original RREQ further up the network in search of nodes which are
tree members. Thus it is possible that this node also received more
than one RREP, as noted in Section 9.5.
When the node receives a MACT selecting it as the next hop, it
unicasts its own MACT to the node it has chosen as its next hop,
and so on up the tree, until a node which was already a part of the
multicast tree is reached.
9.7. Multicast Tree Pruning
A multicast group member can revoke its member status at any time.
However, it can only actually leave the multicast tree if it is not a
tree router for any other nodes in the multicast group (i.e., if it
Royer, Perkins Expires 15 December 2000 [Page 13]
Internet Draft Multicast AODV 15 July 2000
is a leaf node). If a node wishing to leave the multicast group is
a leaf node, it unicasts to its next hop on the tree a MACT message
with the 'P' flag set and with the Destination IP Address set to the
IP address of the multicast group. It then deletes the multicast
group information for that group from its multicast route table.
When its next hop receives this message, it deletes the sending
node's information from its list of next hops for the multicast tree.
If the removal of the sending node causes this node to become a leaf
node, and if this node is also not a member of the multicast group,
it may in turn prune itself by sending its own MACT message up the
tree.
When the multicast group leader wishes to leave the multicast group,
it proceeds in a manner similar to the one just described. If it
is a leaf node, it may leave the group and unicast a prune message
to its next hop. The next hop acts in the manner described in
Section 9.10, since the prune message is coming from its upstream
neighbor. Otherwise, if the group leader is not a leaf node, it may
not prune itself from the tree. It takes the actions described in
Section 9.9, where it selects one of its next hops and unicasts to it
the MACT with set 'G' flag.
9.8. Repairing a Broken Link
Branches of the multicast tree become invalid if a broken link
results in an infinite metric being associated with the next hop
route table entry. When a broken link is detected between two nodes
on the multicast tree, the two nodes should delete the link from
their list of next hops for the multicast group. The node downstream
of the break (i.e., the node which is further from the multicast
group leader) is responsible for initiating the repair of the broken
link. In order to repair the tree, the downstream node broadcasts
a RREQ with destination IP address set to the IP address of the
multicast group and with the 'J' flag set. The destination sequence
number of the RREQ is the last known sequence number of the multicast
group. The node also includes the Multicast Group Leader Extension.
The Multicast Group Hop Count field of this extension is set to the
distance of the source node from the multicast group leader. A node
MUST have a hop count to the multicast group leader less than or
equal to the indicated value in order to respond. This hop count
requirement prevents nodes on the same side of the break as the node
initiating the repair from replying to the RREQ.
The RREQ is broadcast using an expanding rings search, as described
in Section 9.2.1. Because of the high probability that other
nearby nodes can be used to rebuild the route, the original
RREQ is broadcast with a TTL (time to live) field value equal to
TTL_INCREMENT plus the Multicast Group Hop Count. In this way,
Royer, Perkins Expires 15 December 2000 [Page 14]
Internet Draft Multicast AODV 15 July 2000
the effects of the link breakage may be localized. If no reply
is received within RREP_WAIT_TIME milliseconds, the node SHOULD
increment the TTL of each successive RREQ by TTL_INCREMENT, until
either a route is determined, or TTL_THRESHOLD is reached. After
this point, if a route is still not discovered, each additional RREQ
is broadcast with TTL = NET_DIAMETER. Up to RREQ_RETRIES additional
broadcasts may be attempted after TTL = NET_DIAMETER is reached.
A node receiving this RREQ can respond if it meets the following
conditions:
- It is a member of the multicast tree.
- Its record of the multicast group sequence number is at least as
great as that contained in the RREQ.
- Its hop count to the multicast group leader is less than or equal
to the contained in the Multicast Group Hop Count extension
field.
If the originating node receives more than one RREP, route activation
occurs as described in the previous section.
At the end of the discovery period, the node selects its next hop
and unicasts a MACT message to that node to activate the link, as
described in Section 9.6. Since the node was repairing a tree break,
it is likely that it is now a different distance from the group
leader than it was before the break. If this is the case, it must
inform its DOWNSTREAM next hops of their new distance from the group
leader. It does this by broadcasting a MACT message with the 'U'
flag set, and the Hop Count field set to the node's new distance
from the group leader. This 'U' flag indicates that multicast tree
nodes should update their distance from the group leader. When a
node on the multicast tree receives the MACT message with the 'U'
flag set, it determines whether this packet arrived from its UPSTREAM
neighbor. If it did not, the node discards the packet. Otherwise,
it increments the Hop Count value contained in the MACT packet and
updates it distance to the group leader to be this node value. If
this node has one or more downstream next hops, it in turn must send
a MACT message with a set 'U' flag to its next hops, and so on.
When a link break occurs, it is possible that the tree will be
repaired through different intermediate nodes. If the node UPSTREAM
of the break is not a group member, and if the loss of that link
causes it to become a leaf node, it sets a prune timer to wait
for the link to be repaired. This PRUNE_TIMEOUT should be larger
than RREP_WAIT_TIMEOUT to give the link time to be repaired. If,
when this timer expires, the node has not received a MACT message
selecting it to be a part of the repaired tree branch, it prunes
Royer, Perkins Expires 15 December 2000 [Page 15]
Internet Draft Multicast AODV 15 July 2000
itself from the tree by sending a MACT with set 'P' flag to its next
hop, as previously described.
9.9. Tree Partitions
It is possible that after a link breaks, the tree cannot be repaired
due to a network partition. If the node attempting to repair a tree
link break does not receive a response after RREQ_RETRIES attempts,
it can be assumed that the network has become partitioned and the
multicast tree cannot be repaired at this time. In this situation,
if the node which initiated the route rebuilding is a multicast group
member, it becomes the new multicast group leader for its part of the
multicast tree partition. It increments the group sequence number
and then broadcasts a Group Hello (GRPH) for this multicast group.
The 'U' flag in the GRPH is set, indicating that there has been a
change in the group leader information. All nodes receiving this
message update their group leader table to indicate the new group
leader information. Nodes which are a part of the multicast tree
also update the group leader and sequence number information for that
group in their multicast route table.
On the other hand, if the node which had initiated the repair is not
a multicast group member, there are two possibilities. If it only
has one next hop for the multicast tree, it prunes itself from the
tree by unicasting a MACT message, with the 'P' flag set, to its
next hop. The node receiving this message notes that the message
came from its upstream link, i.e., from a node that is closer to
the group leader than it is. If the node receiving this message
is a multicast group member, it becomes the new group leader and
broadcasts a GRPH message as indicated above. Otherwise, if it is
not a multicast group member and it only has one other next hop link,
it similarly prunes itself from the tree. This process continues
until a multicast group member is reached.
The other possibility is that the node which initiated the rebuilding
is not a group member and has more than one next hop for the tree.
In this case, it cannot prune itself, since doing so would partition
the tree. It instead selects one of its next hops and unicasts a
MACT with the 'G' flag set to that node. This flag indicates that
the next group member to receive this message should become the new
group leader. It then changes the direction of that link to be
UPSTREAM. If the node receiving the MACT is a group member, then this
node becomes the new group leader. Otherwise, the node unicasts its
own MACT message with the 'G' flag set to one of its next hops, and
changes the direction of that link. Once a group member is reached,
the new group leader is determined.
Royer, Perkins Expires 15 December 2000 [Page 16]
Internet Draft Multicast AODV 15 July 2000
9.10. Reconnecting Two Trees
In the event that a link break cannot be repaired, the multicast
tree remains partitioned until the two parts of the network become
connected once again. A node from one partition of the network knows
that it has come into contact with a node from the other partition of
the network by noting the difference in the GRPH message multicast
group leader information. The multicast group leader with the lower
IP address initiates the tree repair. For the purposes of this
explanation, call this node GL1. GL1 unicasts a RREQ with both
the 'J' and 'R' flags set to the group leader of the other network
partition (GL2), using the node from which it received the GRPH
as the next hop. This RREQ contains the current value of GL1's
multicast group sequence number. If any node that receives the RREQ
is a member of GL2's multicast tree, it MUST forward the RREQ along
its upstream link, i.e. towards GL2. This prevents any loops from
being formed after the repair. Upon receiving the RREQ, GL2 takes
the larger of its and the received multicast group sequence number,
increments this value by one, and responds with a RREP. This is the
group leader which becomes the leader of the reconnected multicast
tree. The 'R' flag of the RREP is set, indicating that this RREP is
in response to a repair request.
As the RREP is propagated back to GL1, nodes add the incoming and
outgoing links to the multicast route table next hop entries if
these entries do not already exist. The nodes also activate these
entries, thereby adding the branch on to the multicast tree. If a
node that was previously a member of GL1's tree receives the RREP, it
MUST forward the packet along its link to its previous group leader
(GL1). It then updates its group leader information to reflect GL2
as the new group leader, changes the direction of the next hop link
associated with GL1 to DOWNSTREAM, and sets the direction of the
link on which it received the RREP to UPSTREAM. When GL1 receives
the RREP, it updates its group leader information and sets the
link from which it received the RREP as its upstream link. The
tree is now reconnected. The next time GL2 broadcasts a GRPH, it
sets the `U' flag to indicate that there is a change in the group
leader information and group members should update the corresponding
information. All network nodes update their group leader table to
reflect the new group leader information.
9.11. Maintaining Local Connectivity
Each node on the multicast tree MUST keep track of its neighbors
which are next hops on the multicast tree. This is done as specified
in [2]. If a link to the next hop cannot be detected by any of the
methods specified therein, the forwarding node MUST assume that the
Royer, Perkins Expires 15 December 2000 [Page 17]
Internet Draft Multicast AODV 15 July 2000
link is broken, and take corrective action by following the methods
specified in Section 9.8.
Whenever the multicast tree is used for the transmission of data
packets, a node on the tree must hear from each of its next hop
neighbors every RETRANSMIT_TIME. The node can hear from its neighbors
through one of the methods previously described, or through the
reception of a rebroadcast of a data packet from these next hops,
if the data packets are being transmitted by broadcast. If a
node does not hear from one of its multicast tree next hops within
RETRANSMIT_TIME, and if the multicast tree is actively being used
to transmit data packets, then the node MUST assume the link to
its next hop is broken, and proceed as described in Section 9.8.
Decreasing the amount of time between when a node must hear from its
next hops from ALLOWED_HELLO_LOSS * HELLO_INTERVAL milliseconds to
RETRANSMIT_TIME allows for the quickest detection of broken links and
fewer data packet losses.
9.12. Group Hello Messages
If a node sends a RREQ to join a multicast group (`J' flag set)
and after RREQ_RETRIES attempts does not receives a response, it
then becomes the multicast group leader. The node initializes the
multicast group sequence number and then broadcasts a GRPH message
to inform network nodes that it is now the group leader for the
multicast group. To ensure nodes maintain consistent and up-to-date
information about who the multicast group leaders are, any node which
is a group leader for a multicast group broadcasts such a GRPH across
the network every GROUP_HELLO_INTERVAL milliseconds. The contents of
the GRPH fields are set as follows:
U Flag 0
M Flag 0
Hop Count 0
Group Leader IP Address
The IP Address of the group leader.
Multicast Group IP Address
The IP Address of the Multicast Group for which the
node is the group leader.
Multicast Group Sequence Number
One plus the last known sequence number of the
multicast group.
Royer, Perkins Expires 15 December 2000 [Page 18]
Internet Draft Multicast AODV 15 July 2000
Nodes receiving the GRPH increment the Hop Count field by one before
forwarding the message. When a node not on the multicast tree
receives the GRPH message, it sets the 'M' flag. This indicates that
this incarnation of the message has traveled off the multicast tree,
and hence cannot be used by group members to verify their distance
from the group leader. The 'U' flag is set by the group leader
whenever there has been a change in group leader information. It
informs nodes that they should update the group leader information
associated with the indicated multicast group.
A node receiving the GRPH message first verifies that is has
not already received the GRPH message with the same group IP
address/group sequence number pair in the last BCAST_ID_SAVE
milliseconds. If it has, it silently discards the message.
Otherwise, the node updates its group leader table to reflect
the current multicast group IP address/group leader IP address
combination, and increments the Hop Count value in the message. If
the node receiving the GRPH message is a member of the multicast
tree, it also updates this information in its multicast route table.
If the 'M' flag is unset, then this node can also use the Hop Count
value to verify its current distance from the group leader.
After processing the GRPH message, the node buffers the group
IP address/ group sequence number combination to avoid multiple
processings of the same GRPH message. It then rebroadcasts the
message to its neighbors.
9.13. Actions After Reboot
A node participating in the multicast tree that reboots (or
restarts the routing daemon) loses all of its multicast tree
information. Upon reboot, the rebooted node does not know whether
it was previously a member of the multicast tree. Hence, it should
unconditionally broadcast a MACT message with set Reboot ('R') flag
to inform neighboring nodes that it has lost its multicast group
information. When a node on the multicast tree receives the reboot
MACT message, it checks whether this message came from one of its
next hops on the multicast tree. If so, one of two situations
exists.
If the reboot MACT came from a downstream link, the node deletes that
link from its list of next hops and sets a prune timer according to
the guidelines in Section 9.8. Otherwise, if the reboot MACT came
from a node's upstream link, it must rebuild the tree branch as is
also indicated in Section 9.8.
Royer, Perkins Expires 15 December 2000 [Page 19]
Internet Draft Multicast AODV 15 July 2000
9.14. Interfaces
Because MAODV should operate smoothly over wired, as well as
wireless, networks, and because it is likely that MAODV will also be
used with multi-homed radios, the interface over which packets arrive
must be known to MAODV whenever a packet is received. This includes
the reception of RREQ, RREP, MACT, and GRPH messages. Whenever a
packet is received from a new neighbor, the interface on which that
packet was received is recorded into the route table entry for that
neighbor, along with all the other appropriate routing information.
Similarly, whenever a route to a new destination is learned, the
interface through which the destination can be reached is also
recorded into the destination's route table entry.
When multiple interfaces are available, a node receiving and
rebroadcasting a RREQ or GRPH message rebroadcasts that message on
all interfaces except the one on which it was received. If a node is
participating on the multicast tree, and if multicast data packets
are being sent as broadcast traffic, a multicast tree node should
only rebroadcast a packet on those interfaces which have multicast
tree next hops.
10. Extensions
This section specifies for multicast extensions for RREQ and RREP
messages, conforming to the format defined in [2].
10.1. Multicast Group Leader Extension Format
This extension is appended to a RREQ by a node wishing to repair a
multicast tree.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length | Multicast Group Leader IP ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... Address (continued) | Previous Hop IP Address ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... (continued) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type 3
Length 8
Royer, Perkins Expires 15 December 2000 [Page 20]
Internet Draft Multicast AODV 15 July 2000
Multicast Group Leader IP Address
The IP Address of the Multicast Group Leader.
Previous Hop IP Address
The IP Address of the node which previously received the
RREQ. This field is used when the RREQ is unicast to
the group leader when a node wishes to join a multicast
group.
This extension is used when unicasting the RREQ to the group leader.
Each node receiving the RREQ updates the Previous Hop IP Address
field to reflect its address.
10.2. Multicast Group Rebuild Extension Format
This extension is appended to a RREQ by a node wishing to repair a
multicast tree.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length | Multicast Group Hop Count |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type 4
Length 2
Multicast Group Hop Count
The distance in hops of the node sending the RREQ from
the Multicast Group Leader.
This extension is used for rebuilding a multicast tree branch. It is
used to ensure that only nodes as least as close to the group leader
as indicated by the Multicast Group Hop Count field respond to the
request.
10.3. Multicast Group Information Extension Format
The following extension is used to carry additional information for
the RREP message (see Section 6) when sent to establish a route to a
multicast destination.
Royer, Perkins Expires 15 December 2000 [Page 21]
Internet Draft Multicast AODV 15 July 2000
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length | Multicast Group Hop Count |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multicast Group Leader IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type 5
Length 6
Multicast Group Hop Count
The distance of the node from the Multicast Group Leader.
Multicast Group Leader IP Address
The IP Address of the current Multicast Group Leader.
This extension is included when responding to a RREQ to join a
multicast group. The node responding to the RREQ places its distance
from the group leader in the Multicast Group Hop Count field.
11. Configuration Parameters
This section gives default values for some important values
associated with MAODV protocol operations. A particular mobile node
may wish to change certain of the parameters, in particular the
NET_DIAMETER, MY_ROUTE_TIMEOUT, ALLOWED_HELLO_LOSS, RREQ_RETRIES,
and possibly the HELLO_INTERVAL. In the latter case, the node should
advertise the HELLO_INTERVAL in its Hello messages, by appending
a Hello Interval Extension to the RREP message. Choice of these
parameters may affect the performance of the protocol.
Royer, Perkins Expires 15 December 2000 [Page 22]
Internet Draft Multicast AODV 15 July 2000
Multicast Parameters Value
---------------------- -----
GROUP_HELLO_INTERVAL 5,000 Milliseconds
MTREE_BUILD 2 * REV_ROUTE_LIFE
PRUNE_TIMEOUT ACTIVE_ROUTE_TIMEOUT
RETRANSMIT_TIME 750 Milliseconds
Additional AODV Parameters
--------------------------
ACTIVE_ROUTE_TIMEOUT
ALLOWED_HELLO_LOSS
BCAST_ID_SAVE
DELETE_PERIOD
HELLO_INTERVAL
NET_DIAMETER
NEXT_HOP_WAIT
NODE_TRAVERSAL_TIME
REV_ROUTE_LIFE
RREP_WAIT_TIME
RREQ_RETRIES
TTL_START
TTL_INCREMENT
TTL_THRESHOLD
Please see [2] for a discussion of and the appropriate values for the
Additional AODV Parameters.
12. Security Considerations
Currently, MAODV does not specify any special security measures.
Route protocols, however, are prime targets for impersonation
attacks, and must be protected by use of authentication techniques
involving generation of unforgeable and cryptographically strong
message digests or digital signatures. It is expected that, in
environments where security is an issue, that IPSec authentication
headers will be deployed along with the necessary key management to
distribute keys to the members of the ad hoc network using MAODV.
Royer, Perkins Expires 15 December 2000 [Page 23]
Internet Draft Multicast AODV 15 July 2000
References
[1] S. Bradner. Key words for use in RFCs to Indicate Requirement
Levels. Request for Comments (Best Current Practice) 2119,
Internet Engineering Task Force, Mar. 1997.
[2] C. Perkins, E. Royer, and S. Das. Ad hoc on demand distance
vector (AODV) routing (work in progress). Internet Draft,
Internet Engineering Task Force, Mar. 2000.
[3] C. E. Perkins. Terminology for Ad-Hoc Networking (work in
progress). draft-ietf-manet-terms-00.txt, Nov. 1997.
Author's Addresses
Questions about this memo can be directed to:
Elizabeth M. Royer
Dept. of Electrical and Computer Engineering
University of California, Santa Barbara
Santa Barbara, CA 93106
+1 805 893 7788
+1 805 893 3262 (fax)
eroyer@alpha.ece.ucsb.edu
Charles E. Perkins
Communications Systems Laboratory
Nokia Research Center
313 Fairchild Drive
Mountain View, CA 94303
USA
+1 650 625 2986
+1 650 691 2170 (fax)
charliep@iprg.nokia.com
Royer, Perkins Expires 15 December 2000 [Page 24]
Html markup produced by rfcmarkup 1.128b, available from
https://tools.ietf.org/tools/rfcmarkup/