MANET Working Group Vijay Devarapalli INTERNET DRAFT Nokia Research Center 19 July 2001 Ali A. Selcuk Deepinder Sidhu MCTR, UMBC MZR: A Multicast protocol for Mobile Ad Hoc networks draft-vijay-manet-mzr-01.txt Status of This Memo 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. This document is an individual submission for the manet 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. Abstract This document proposes a multicast protocol for Mobile Ad Hoc networks, called the Multicast routing protocol based on Zone Routing (MZR). MZR is a source-initiated on-demand protocol, in which a multicast delivery tree is created using a concept based on the zone routing mechanism. It belongs to the family of source-tree-based protocols, in which a delivery tree rooted at the source is created for each active multicast session. MZR does not depend on any underlying unicast protocol for a global routing substructure. The protocol's reaction to topological changes is restricted to a node's neighborhood and is not propagated throughout the network. Devarapalli, Selcuk, Sidhu Expires 19 January 2002 [Page i] Internet Draft Multicast Protocol for MANET 19 July 2001 Contents Status of This Memo i Abstract i 1. Introduction 2 2. Terminology 2 3. Route Tables 3 3.1. Zone Routing Table . . . . . . . . . . . . . . . . . . . 4 3.2. Multicast Routing Table . . . . . . . . . . . . . . . . . 4 3.3. Message Cache . . . . . . . . . . . . . . . . . . . . . . 4 3.4. Neighbor Table . . . . . . . . . . . . . . . . . . . . . 4 4. Protocol Description 5 4.1. Zone Routing . . . . . . . . . . . . . . . . . . . . . . 5 4.2. Zone Construction . . . . . . . . . . . . . . . . . . . . 6 4.3. Zone Maintenance . . . . . . . . . . . . . . . . . . . . 6 4.4. Multicast Tree Creation . . . . . . . . . . . . . . . . . 6 4.5. Routing Mechanism . . . . . . . . . . . . . . . . . . . . 8 4.6. Maintaining the Multicast Tree . . . . . . . . . . . . . 8 4.6.1. Tree Refresh . . . . . . . . . . . . . . . . . . 9 4.6.2. Reaction to Link Breaks . . . . . . . . . . . . . 9 4.7. Tree Prunes . . . . . . . . . . . . . . . . . . . . . . . 10 4.8. Joining a Multicast Session . . . . . . . . . . . . . . . 10 5. Message Formats 10 5.1. ADVERTISEMENT . . . . . . . . . . . . . . . . . . . . . . 10 5.2. TREE-CREATE . . . . . . . . . . . . . . . . . . . . . . . 11 5.3. TREE-PROPAGATE . . . . . . . . . . . . . . . . . . . . . 12 5.4. TREE-CREATE-ACK . . . . . . . . . . . . . . . . . . . . . 13 5.5. JOIN . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5.6. JOIN-PROPAGATE . . . . . . . . . . . . . . . . . . . . . 15 5.7. JOIN-ACK . . . . . . . . . . . . . . . . . . . . . . . . 15 5.8. PRUNE . . . . . . . . . . . . . . . . . . . . . . . . . . 17 6. Configurable Parameters 17 7. Security Considerations 17 Addresses 18 Devarapalli, Selcuk, Sidhu Expires 19 January 2002 [Page 1] Internet Draft Multicast Protocol for MANET 19 July 2001 1. Introduction In this document, we propose a new multicast protocol for Mobile Ad Hoc networks, called the Multicast routing protocol based on Zone Routing (MZR). MZR is a source-tree-based, source-initiated, on-demand routing protocol, which is based on the concept of zone routing. The zone routing mechanism was originally described in the Zone Routing Protocol [2] developed by the Wireless Networks Lab at Cornell University. It is a hybrid approach between the proactive and reactive routing protocols, where routing is proactive inside the zones (i.e., a unicast route is proactively maintained between every pair of nodes in a zone) and reactive between the zones (i.e., a route between two nodes in different zones is created when needed). This hybrid approach provides a balance between the efficient packet delivery of proactive routing and the low maintenance cost of reactive routing. MZR is a source-tree-based multicast routing protocol. For each multicast session identified by a pair, a multicast delivery tree rooted at the source is created. One advantage of the source-tree-based routing protocols over the shared-tree-based protocols is that they do not have a single point of failure like the group leader (or the rendezvous point) as in the shared-tree protocols. This is significant when it comes to ad hoc networks because of the frequent mobility of the nodes. Network mobility further increases the overhead of group leader election. Also, in the source-tree approach, traffic is evenly distributed over the network rather than being concentrated on the shared tree. The MZR protocol is source-initiated, which means that a multicast delivery tree is created when the source needs to send multicast data to its group members; and it is on-demand, which means that the delivery tree is created only when there is data to be sent to the group members. MZR does not depend on any underlying unicast routing protocol for its operation as other multicast protocols do [3, 4, 5]. 2. Terminology This protocol specification uses conventional meanings as specified in RFC 2119 for capitalized words such as MUST, SHOULD, etc., to indicate requirement levels for various protocol features. Other terminology used by the protocol are defined in this section. Node Any device participating in the ad hoc network. Devarapalli, Selcuk, Sidhu Expires 19 January 2002 [Page 2] Internet Draft Multicast Protocol for MANET 19 July 2001 Zone Routing A hybrid approach combining advantages of proactive and reactive protocols, where routing is proactive inside the zones and reactive between the zones. [2] has more details. Zone A node's local neighborhood specified by a zone radius. Zone radius Radius of each node's zone in terms of network hops. Border Node A node which is on the periphery of a zone. The distance from the border node to the zone's center (to which the zone belongs) in terms of network hops is equal to the zone radius. Upstream The next hop on the multicast source tree towards the source of the multicast session. Downstream The next hop in the multicast source tree away from the source of the multicast session. Proactive Routing Protocols Routing protocols which constantly exchange routing information to keep the routing tables at each node current and up-to-date. Reactive Routing Protocols Routing protocols which do an on-demand route discovery when data needs to be sent to a particular destination. 3. Route Tables MZR as a routing protocol uses the following data structures for its operation. Devarapalli, Selcuk, Sidhu Expires 19 January 2002 [Page 3] Internet Draft Multicast Protocol for MANET 19 July 2001 3.1. Zone Routing Table Each mobile node participating in MZR maintains a Zone Routing Table, which contains unicast routes to all nodes inside its zone. The routing information in this table is kept current by the proactive component running inside each zone. Each route entry in the zone routing table has a timer associated with it. If the timer expires, the corresponding entry is removed. A zone route entry SHOULD contain atleast the following fields - Destination IP Address - Next Hop - Outgoing Interface - Hop Count - Lifetime timer - Routing Flags 3.2. Multicast Routing Table A multicast routing table is maintained at each node running MZR. If a node were on a multicast tree, identified by a pair, then it would have a multicast route entry corresponding to that tree. Each multicast route entry has a timer associated with it, which is refreshed, whenever a node gets a refresh packet on the multicast tree. The route entry has a pointer to the upstream node towards the source. It also has a list of downstream nodes, to which data is replicated and forwarded. Each multicast route entry SHOULD contain atleast the following fields. - Multicast Tree id - Upstream node - List of downstream nodes - Lifetime timer - Routing Flags 3.3. Message Cache Each node MUST maintain a message cache for detecting duplicate data and control packets. A Least Recently Used (LRU) scheme MAY be used to to prevent the cache from growing uncontrollably. 3.4. Neighbor Table Each node SHOULD maintain a neighbor table where it stores the list of all its one hop neighbors with the corresponding interface address to reach them. Devarapalli, Selcuk, Sidhu Expires 19 January 2002 [Page 4] Internet Draft Multicast Protocol for MANET 19 July 2001 4. Protocol Description MZR has two parts to it. A proactive protocol runs inside each zone, maintaining an up-to-date zone routing table at each node. A reactive multicast tree creation is initiated when a source needs to send multicast data to its group members. The following sections describe the protocol. 4.1. Zone Routing Existing routing protocols can be classified either as proactive or reactive protocols. Both these classes of protocols suffer from disadvantages when it comes to ad hoc networks. The Zone Routing approach is a hybrid approach [2], which tries to incorporate the advantages from both proactive and reactive protocols. The original Zone Routing Protocol is described in [2]. It initiates the route determination procedure on-demand, but at limited search cost. It limits the scope of the proactive procedure only to the node's zone. On the other hand, the global search for the destination (anywhere in the network), is done efficiently by querying only selected nodes in the network, as opposed to querying all the network nodes. Each node in the network defines a zone around itself with the zone radius measured in terms of network hops. A zone routing table containing unicast routes to all zone nodes is maintained at each node. This table is kept current by running a proactive protocol inside each zone. The important difference from pure proactive protocols is that the routing updates (carrying routing information) are restricted to the zone, and are not sent to the entire network. For routes to destinations outside a node's zone, a reactive route discovery process is initiated. The beauty of the zone routing protocol is the way in which the global flood search algorithm is implemented. Instead of flooding the route request packet throughout the network, a node selectively queries its border nodes for a route to a particular destination. These border nodes first look in their zones for the destination. If not found, they query their border nodes in turn. The destination node eventually gets the route discovery packet and replies to the source. As the zone radius is significantly smaller than the network radius, the cost of learning the zone topologies is a very small fraction of the cost required by a global proactive mechanism. Zone routing is also much cheaper (in term of control traffic and congestion) and faster than a global reactive route discovery mechanism, as the number of nodes queried in the process is [r_zone / r_network]^2 of the number of nodes queried by a global flooding process (r_zone is the zone radius and r_network is the network radius) [2]. MZR makes use of this querying mechanism for building a source-based multicast delivery tree. Devarapalli, Selcuk, Sidhu Expires 19 January 2002 [Page 5] Internet Draft Multicast Protocol for MANET 19 July 2001 4.2. Zone Construction Each mobile node participating in an ad hoc network constructs a zone around itself with a pre-configured zone radius. A simplified distance vector protocol is implemented for creating zones and for maintaining a Zone Routing Table at each node. Every node in the mobile ad hoc network periodically broadcasts an ADVERTISEMENT packet, identifying itself. The propagation of the advertisement packets is restricted to a zone by setting the time-to-live (TTL) value of these packets to the zone radius. The nodes that are within the transmission range of a node A pick up the advertisement packet sent by A. Each node that receives an ADVERTISEMENT packet rebroadcasts it if the TTL of the packet is still valid. Before the packet is rebroadcasted, the TTL of the packet is decremented by one. When a node B receives the advertisement packet from A, a route entry for A is created and stored in B's zone routing table. The distance to A from B is set to the hop count in the advertisement packet and the next hop in the route entry is set to the node from which B received A's advertisement packet. A soft state approach is followed to remove stale routes from the zone routing table. Route entries expire if they are not periodically refreshed by advertisement packets from the corresponding nodes. 4.3. Zone Maintenance The zone routing table is kept up-to-date through the proactive protocol built on periodic advertisements. Routes to destinations that moved away are removed when they expire. Routes to new destinations are added to a node's zone routing table, when it receives advertisement packets from these destinations. Also, the protocol's reaction to the changes in topology is localized to a zone. Only the nodes within a zone are affected and only they need to update their zone routing tables. By looking at the zone routing table, a node can identify the interior zone nodes and the border nodes. If the distance metric in a route entry is equal to the zone radius, the corresponding destination becomes a border node. All the other nodes, whose route entries contain distances less than the zone radius become the interior zone nodes. Each node SHOULD maintain a Neighbor Table, which contains all those nodes from which a node received ADVERTISEMENT packets with a hop count of one. 4.4. Multicast Tree Creation For each multicast session in the ad hoc network, a tree rooted at the source and identified by a pair is created. Multicast group information is distributed separately and is not within the scope of this protocol. Every node maintains a multicast routing table, Devarapalli, Selcuk, Sidhu Expires 19 January 2002 [Page 6] Internet Draft Multicast Protocol for MANET 19 July 2001 which contains route entries corresponding to each active multicast session in the ad hoc network. A multicast route entry is identified by the multicast session id, a pair, and contains the IP address of the upstream node and a list of downstream nodes on the corresponding multicast tree. A multicast source initiates the creation of a multicast data delivery tree. The tree creation is done in a two-stage process. The source initially tries to extend the tree inside its zone and then tries to extend the tree to the entire network. The corresponding data packet and the subsequent data packets for the session are queued up for transmission until after the tree is created. The source sends a TREE-CREATE to each zone node, through unicast routes obtained from the zone routing table. A TREE-CREATE packet is uniquely identified by the corresponding session id. The TTL of the TREE-CREATE packet is set to the zone radius and decremented by one each time it is forwarded. When the TTL becomes zero, the packet is not forwarded further. As the TREE-CREATE packet is propagated to a zone node, reverse route entries are created at each intermediate node. The reverse routes are basically multicast route entries with the list of downstream nodes empty and the upstream node set to the node which forwarded the TREE-CREATE packet. If the receiving node is not able to determine the identity of the node which forwarded the packet based on the interface id, it uses its zone routing table to figure out the upstream node. It chooses the next hop node in its zone routing entry for the node which originated the TREE-CREATE packet. These multicast route entries at the intermediate nodes are set to inactive when they are created. When a zone node, interested in the multicast group session, receives the TREE-CREATE packet, it creates a multicast route entry and replies with a TREE-CREATE-ACK packet. The TREE-CREATE-ACK is sent to the one hop neighbor which forwarded the TREE-CREATE packet. The TREE-CREATE-ACK packet is finally sent back to the source through the reverse route created by the TREE-CREATE packet. As the TREE-CREATE-ACK travels back to the source, the corresponding multicast route entry at each intermediate node is completed, activated and the node from which the TREE-CREATE-ACK was received is added to the list of the downstream nodes. When the multicast route entry is activated at a node, it signals the creation of a new tree branch on which multicast data can be forwarded. Even nodes, which are not interested in the multicast session, become members of the multicast tree if they provide connectivity to downstream member nodes. Through this mechanism, the source succeeds in creating a multicast tree, rooted at the source and extending throughout its zone. Once the source is done with its zone, it tries to extend the multicast tree to the entire network. The source identifies all the border nodes for its zone and sends a TREE-PROPAGATE message to each one of them. The TTL of the TREE-PROPAGATE packet is set to the zone radius and the packet is unicasted to the border nodes. The TTL is decremented by one Devarapalli, Selcuk, Sidhu Expires 19 January 2002 [Page 7] Internet Draft Multicast Protocol for MANET 19 July 2001 each time the packet is forwarded. If the TTL becomes zero, the packet is not forwarded. Each TREE-PROPAGATE packet is uniquely identified by the corresponding multicast session id. A TREE-PROPAGATE packet basically tells a node to extend the multicast tree inside its zone. An optimization would be for the source to indicate to the border nodes to propagate the tree by setting a flag in the TREE-CREATE packets sent to them. This will eliminate the need for separate TREE-PROPAGATE messages. When a border node receives a TREE-PROPAGATE packet, it creates a multicast route entry for the session, and then sends a TREE-CREATE packet to each of its zone nodes. This is done, even if the border node is not interested in the multicast session. If a node in the border node's zone is interested in the session, it replies to the border node with a TREE-CREATE-ACK. The same procedure as described in the previous section is followed to create multicast route entries at each intermediate node. The border node in turn sends a TREE-CREATE-ACK packet, unicasted to the source. This basically extends the multicast tree into the border node's zone with a unicast link between the source and the border node and multiple tree branches within the border node's zone. Once the border node is done with its zone nodes, it MUST send a TREE-PROPAGATE message to all its border nodes. These border nodes in turn try to extend the multicast tree inside their zones. This continues till every mobile node in the ad hoc network gets a TREE-CREATE packet corresponding to the multicast tree being created. A node can be a member of multiple routing zones at the same time because the routing zones heavily overlap. It is possible that a node receives multiple TREE-CREATE and TREE-PROPAGATE messages. This is prevented by early detection and termination of duplicate TREE-PROPAGATE threads. 4.5. Routing Mechanism The source starts transmitting data packets to the group members once the multicast delivery tree is created. Each tree member has a valid multicast route entry with the upstream node set to the node from which it receives data packets and a list of downstream nodes on the tree. When a node on the multicast tree receives a data packet from its upstream node, it replicates the data packet and sends a copy to each node in the downstream list. A node SHOULD stop transmitting data packets to a downstream node, if the downstream node migrates and moves out of its transmission range. 4.6. Maintaining the Multicast Tree In a mobile ad hoc network, frequent changes in the network topology due to node mobility can cause tree links to break. To ensure continuous multicast data delivery in the presence of node mobility, the multicast Devarapalli, Selcuk, Sidhu Expires 19 January 2002 [Page 8] Internet Draft Multicast Protocol for MANET 19 July 2001 tree has to be reconfigured quickly. The following sections describe two mechanisms, one to maintain up-to-date multicast routing information at each tree member node and another for repairing tree link breaks. 4.6.1. Tree Refresh Each route entry in a node's multicast routing table has a timer associated with it. When the timer expires, the corresponding multicast route entry is removed. This is necessary to remove stale multicast information. To ensure that the multicast route entries do not expire for the duration of the multicast session, the source MUST send a TREE-REFRESH packet every REFRESH-INTERVAL down the tree. The TREE-REFRESH packet is identified by a unique session id, a pair. When a tree member receives a refresh packet, it updates the timer for the corresponding multicast route entry, and sends the refresh packet to all the downstream nodes on the tree. The source stops sending refresh packets once it finishes sending all the data for the corresponding session. This mechanism ensures that a data delivery tree is maintained as long as the session is active. The source SHOULD piggyback the refresh packet on any data packet whenever possible. 4.6.2. Reaction to Link Breaks The downstream nodes are responsible for detecting link breaks and reconfiguring the tree. When a link to an upstream node breaks, the downstream node can easily detect this by looking at its neighbor table or the zone routing table. A node (say, A) initiates branch reconstruction when it loses connection to its upstream node and is still interested in the ongoing multicast session. The node A initiates a search for the multicast tree by using the zone routing mechanism. It first sends JOIN packets to all its zone nodes. Each JOIN is uniquely identified by the corresponding multicast session id. The TTL of the JOIN packet is set to the zone radius and is decremented by one each time it is forwarded. The packet is not forwarded if the TTL becomes zero. If any of the nodes in A's zone is on the multicast tree and has a valid multicast route entry, it replies to A with a JOIN- ACK packet. The node, before replying with a JOIN-ACK packet adds the node from which it received the JOIN request to the list of downstream nodes in the corresponding multicast route entry. Multicast route entries are also set up at the intermediate nodes. If node A does not get a reply from its zone nodes, it tries to propagate its join request through the entire network, hoping it could connect to the multicast tree through some node. It sends a JOIN-PROPAGATE packet to all its border nodes. JOIN-PROPAGATEs are restricted to the zone by setting the TTL to the zone radius. These border nodes in turn send join requests to their zone nodes. If they Devarapalli, Selcuk, Sidhu Expires 19 January 2002 [Page 9] Internet Draft Multicast Protocol for MANET 19 July 2001 get a response from any of their zone nodes, they reply to A with a JOIN-ACK. If not, they MUST send a JOIN-PROPAGATE packet to their border nodes. Using this mechanism, node A's join request is propagated to the entire network. If A does not get a reply at all, it assumes that the network has been partitioned and it cannot connect to the existing multicast tree. The main advantage with this rejoin process is that the branch reconstruction is localized if A manages to find a multicast tree node within its zone. 4.7. Tree Prunes Group membership is dynamic, where nodes are free to join and leave the multicast session in progress. When a tree member is no longer interested in the group, it sends an explicit PRUNE message to its upstream node, which in turn removes it from its list of downstream nodes. If the downstream list becomes empty as a result of this action and the node itself is not interested in the group, it sends an explicit prune message to its upstream node. 4.8. Joining a Multicast Session Joining a multicast session is very similar to the mechanism in which a node which loses connection to its upstream node tries to rejoin the tree. 5. Message Formats This following sections describe the message formats for the messages used by MZR. Note that MZR is a protocol under development. The following message formats are not final and could be changed in the next versions of this draft. 5.1. ADVERTISEMENT ADVERTISEMENT messages are used by the unicast routing protocol running inside each zone to maintain the zone routing table. They are also used Devarapalli, Selcuk, Sidhu Expires 19 January 2002 [Page 10] Internet Draft Multicast Protocol for MANET 19 July 2001 to maintain a neighbor table at each node containing all its one hop neighbors. The format of the ADVERTISEMENT packet is as follows. 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 | Reserved | Hop Count | TTL | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ IP fields: Source Address IP address of the node originating this packet. The node receiving the packet considers the source IP address as the next hop towards the node being advertised. Destination Address Broadcast IP address Advertisement fields: Type 1 Hop count Set to zero initially. Incremented by one each time it is rebroadcasted. TTL (Time to Live) Set to the zone radius, so that the propagation of the packet is restricted to the zone. Decremented by one each time it is broadcasted. Address The IP address that is being advertised Sequence number A sequence number which taken together with the address being advetisement uniquely identifies the advertisment packet. The sequence number is generated by the node whose adress is being advertised. It is incremented each time the advertised node sends a new advertisment. 5.2. TREE-CREATE TREE-CREATEs are unicast messages from a node propagating the tree to the nodes belonging to its zone, informing them about a particular Devarapalli, Selcuk, Sidhu Expires 19 January 2002 [Page 11] Internet Draft Multicast Protocol for MANET 19 July 2001 source tree being created. The intermediate nodes are chosen as upstream nodes in the multicast tree. The format of the TREE-CREATE message is as follows. 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 |P| Reserved | TTL | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multicast Source IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multicast Group IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ IP fields: Source Address IP address of the node initiating tree creation inside a zone Destination Address IP address of a zone node Tree-Create fields: Type 2 P when set, the receiving node should propagate the multicast tree inside its zone. TTL (Time to Live) Set to the zone radius, so that the propagation of the packet is restricted to the zone. Multicast Source IP Address and Multicast Group IP Address Uniquely identify the source tree being created. Sequence number Combined with the multicast source address and multicast group address, uniquely identifies the packet. 5.3. TREE-PROPAGATE TREE-PROPAGATEs are unicast messsages from a node propagating a source tree, to all its border nodes, telling them to propagate the source tree inside their respective zones. The format is the same as TREE-CREATE Devarapalli, Selcuk, Sidhu Expires 19 January 2002 [Page 12] Internet Draft Multicast Protocol for MANET 19 July 2001 message defined in section 5.2. It can also be sent with TREE-CREATE message by setting the flag P. Type 3 5.4. TREE-CREATE-ACK TREE-CREATE-ACK is sent when a node receives a TREE-CREATE message and it is interested in the corresponding multicast session. TREE-CREATE-ACK is a one hop message sent by a node to its upstream node to active the multicast tree link. The format of the message is as follows. 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 | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multicast Source IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multicast Group IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ IP fields: Source Address IP address of the node which received the TREE-CREATE message and is interested in joining the multicast session. Destination Address IP address of the upstream node Tree-create-ack fields: Type 4 Multicast Source IP Address and Multicast Group IP Address Uniquely identify the multicast tree being created. Devarapalli, Selcuk, Sidhu Expires 19 January 2002 [Page 13] Internet Draft Multicast Protocol for MANET 19 July 2001 5.5. JOIN JOIN message is a broadcast message used by a node to join/rejoin an existing multicast session. The progagation of the JOIN message is restricted to the node's zone. The format of the message is as follows. 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 | Reserved | TTL | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multicast Source IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multicast Group IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ IP fields: Source Address IP address of the node originating this packet Destination Address Broadcast IP address Join fields: Type 5 Source IP Address IP address of the initiating the join/rejoin Multicast Source IP address and Multicast Group IP address Uniquely identify a multicast session Sequence number Combine with the source IP address, uniquely identifies the packet Devarapalli, Selcuk, Sidhu Expires 19 January 2002 [Page 14] Internet Draft Multicast Protocol for MANET 19 July 2001 5.6. JOIN-PROPAGATE This message is sent by a node trying to join or rejoin a multicast tree. This is sent only when the node is unable to find a multicast member inside its zone. It is unicasted to the border nodes. 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 | Reserved | TTL | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multicast Source IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multicast Group IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ IP fields: Source Address IP address of the node originating this packet Destination Address IP address of a border node Join-Propagate fields: Type 6 Source IP address IP address of the node initiating the join/rejoin. Multicast source IP address and Multicast group IP address Uniquely identify a multicast session. Sequence number Combined with the source IP address, uniquely identifies the packet. 5.7. JOIN-ACK JOIN-ACK is sent by a node which is already on the multicast tree in reponse to a node which has sent an explicit JOIN message to it. It is a one hop message sent to the next hop towards the node listed as the Devarapalli, Selcuk, Sidhu Expires 19 January 2002 [Page 15] Internet Draft Multicast Protocol for MANET 19 July 2001 source IP address in the corresponding JOIN packet. The format of the message is as follows 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 | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Address (of node which originated the JOIN) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multicast Source IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multicast Group IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ IP fields: Source Address IP address of the node originating this packet Destination Address IP address of the next hop towards the node which originated the JOIN packet Join-Ack fields: Type 7 Address IP address of the node which originally broadcast the JOIN packet in its own zone. This node could either be the one which lost its upstream connection or one which is doing a JOIN-PROPAGATE on another node's behalf. Multicast source IP address and Multicast group IP address Uniquely identify a multicast session. Devarapalli, Selcuk, Sidhu Expires 19 January 2002 [Page 16] Internet Draft Multicast Protocol for MANET 19 July 2001 5.8. PRUNE PRUNE is a one hop message sent by a node which is no longer interested in a particular multicast session to its upstream node. 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 | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multicast Source IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multicast Group IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ IP fields: Source Address IP address of the node originating this packet Destination Address IP address of the upstream node in the corresponding multicast route entry Prune fields: Type 8 6. Configurable Parameters The following are some of the important parameters that would affect the performance of the protocol. The default values for these parameters are specified in this section. Each mobile node MAY modify these parameters if required. Parameters Default Values ---------- -------------- ZONE_RADIUS 2 REFRESH_INTERVAL 5 seconds ADVERTISE_INTERVAL 1 second ZONE_ROUTE_TIMEOUT 3 * ADVERTISE_INTERVAL 7. Security Considerations The security to any routing protocol, including MZR, requires a mechanism for the authentication of the routers (i.e., nodes) in the network. The specifics of the routing security mechanism to be deployed would depend on the specifics of the underlying node authentication Devarapalli, Selcuk, Sidhu Expires 19 January 2002 [Page 17] Internet Draft Multicast Protocol for MANET 19 July 2001 mechanism available (a public-key infrastructure, or a Kerboros-like secret-key authentication system, etc.). At this point, MZR does not specify any security mechanism. References [1] Vijay Devarapalli and Deepinder Sidhu, "MZR: A Multicast Protocol for Mobile Ad Hoc Networks", Proceedings of ICC 2001, June 2001 [2] Z.J. Haas and M.R. Pearlman, "The Zone Routing Protocol (ZRP) for Ad Hoc Networks," Internet Draft, draft-ietf-manet-zone-zrp- 02.txt, June 1999 [3] Elizabeth M. Royer and Charles Perkins, Multicast Operation of the Ad-Hoc On-Demand Distance Vector Routing Protocol, Proceedings of MobiCom'99, August 1999 [4] J.J Garcia-Luna-Aceves and E.L. Madruga, "The Core-Assisted Mesh Protocol", IEEE Journal on Selected Areas in Communication, vol. 17, no. 8, August 1999 [5] Bommaiah, Ethendranath, and et.al., AMRoute: Adhoc Multicast Routing Protocol, Intenet-Draft, draft-talpade-manet-amroute- 00.txt, August 1998 [6] S.-J. Lee and et. al., "A Performance Comparison Study of Ad Hoc Wireless Multicast Protocols", Proceedings of IEEE INFOCOM 2000, March 2000. [7] S.-J. Lee, M. Gerla, and C.-C. Chiang, "On-Demand Multicast Routing Protocol", Proceedings of IEEE WCNC'99, September 1999 [8] Z.J. Haas and Mark Pearlman, "Determining the Optimal configuration for the Zone Routing Protocol", IEEE JSAC, special issue on Ad Hoc Networks, vol. 17, no. 8, August 1999 [9] C.W. Wu and Y.C. Tay, "AMRIS: A Multicast Protocol for Ad hoc Wireless Networks", Proceedings of IEEE Military Communications (MILCOM) conference, 1999. Addresses The Working Group can be contacted via its current chairs: Scott Corson Flarion Technologies Bedminster One Devarapalli, Selcuk, Sidhu Expires 19 January 2002 [Page 18] Internet Draft Multicast Protocol for MANET 19 July 2001 135 Route 202/206 South Bedminster, NJ 07921, USA Email: corson@flarion.com Joseph Macker Information Technology Division Naval Research Laboratory Washington, DC 20375, USA Phone: +1 202 767 2001 Email: macker@itd.nrl.navy.mil Questions about this memo can also be directed to the authors: Vijay Devarapalli Communications Systems Lab Nokia Research Center 313 Fairchild Drive Mountain View, California 94043 USA Phone: +1-650 625 2320 EMail: vijay.devarapalli@nokia.com Fax: +1 650 625-2502 Ali A. Selcuk Maryland Center for Telecommunications Research University of Maryland Baltimore County 1000 Hilltop Circle Baltimore, MD 21250 USA Phone: +1 410 455 3063 Email: aselcu1@umbc.edu Deepinder Sidhu Maryland Center for Telecommunications Research University of Maryland Baltimore County 1000 Hilltop Circle Baltimore, MD 21250 USA Phone: +1 410 455 3028 Email: sidhu@umbc.edu Devarapalli, Selcuk, Sidhu Expires 19 January 2002 [Page 19]