Internet Engineering Task Force Bommaiah, McAuley and Talpade INTERNET-DRAFT Bellcore Liu Univ of Maryland August 6, 1998 Expires: February 7, 1999 AMRoute: Adhoc Multicast Routing Protocol Status of this Memo This document is an Internet-Draft. 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.'' To learn the current status of any Internet-Draft, please check the ``1id-abstracts.txt'' listing contained in the Internet- Drafts Shadow Directories on ftp.ietf.org (US East Coast), nic.nordu.net (Europe), ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific Rim). Abstract The Adhoc Multicast Routing Protocol (AMRoute) allows for robust IP Multicast in mobile adhoc networks by exploiting user-multicast trees and dynamic cores. It creates a bidirectional shared-tree for data distribution using only the group senders and receivers as tree nodes. Unicast tunnels are used as the tree links to connect neighbors on the 'user-multicast tree.' Thus, AMRoute does not need to be supported by network nodes that are not interested/capable of multicast, and cost is incurred only by group senders and receivers. AMRoute makes certain nodes "core nodes" to initiate the signaling component of AMRoute, such as detection of group members and tree setup. Core nodes differ significantly from those in CBT and PIM-SM, since they are not a central point for data distribution and can migrate dynamically among member nodes. AMRoute is INTERNET-DRAFT August 6, 1998 independent of the specific unicast routing protocol; therefore, it can operate seamlessly over separate domains with different unicast protocols. Bommaiah, Liu, McAuley and Talpade [Page 2] INTERNET-DRAFT August 6, 1998 1 Introduction This document describes the Adhoc Multicast Routing Protocol (AMRoute), which enables the use of IP Multicast in mobile adhoc networks ([?], [?]). Existing multicast protocols ([?], [?], [?]) do not work well in adhoc networks as the frequent tree reorganization can cause excessive signaling overhead and frequent loss of datagrams. AMRoute emphasizes robustness even with rapidly changing membership or highly dynamic networks; it does not attempt to provide the absolute minimum bandwidth or latency guarantees in a given topology. It borrows many of the best features of existing multicast protocols; however it has two key new features that make it more robust and efficient in ad-hoc networks: * User-multicast trees, where replication and forwarding is only performed by group members. * Dynamic migration of core node according to group membership and network connectivity. The user-multicast tree includes only the group senders and receivers as its nodes. Each node is aware of its tree neighbors, and forwards data on the tree links. Multicast state is maintained by the group nodes only, and is not required by other network nodes. In fact, AMRoute does not even require non-member nodes to support any IP multicast protocol. The elimination of state in other network nodes clearly saves node resources, especially when compared with broadcast-and-prune native multicast protocols that require per source and per group state at all network nodes. More importantly, especially in highly dynamic adhoc networks, user-multicast trees also eliminate the need to change the tree as the network changes. Neighboring tree nodes are inter-connected by IP-in-IP tunnels, similar to the approach adopted for connecting multicast routers on the MBONE. Consequently, assuming unicast connectivity is maintained among member nodes, the AMRoute distribution tree will continue to function despite network changes. Each group in the network has at least one logical core that is responsible for discovering new group members and creating the multicast tree for data distribution. This logical core is significantly different from the core in CBT and the RP in PIM-SM as it is not the central point on the data path Bommaiah, Liu, McAuley and Talpade [Page 3] INTERNET-DRAFT August 6, 1998 (only for signaling), it is not a preset node (chosen from among currently known members) and it can change dynamically. The absence of a single point of failure is an important requirement for adhoc networks. Other features of AMRoute include some of the best features of other multicast protocols. Like CBT [?] and PIM-SM [?] it uses shared-trees, so only one tree is required per group, improving its scalability. Like DVMRP [?], CBT and PIM the protocol is independent from specific semantics of the underlying unicast routing protocol. Although some efficiency gains are possible by tying the protocol closely with a unicast protocol, we see the independence as more important. Its independence allows use of the optimal ad-hoc unicast protocol for the network and can work transparently across domains supporting different unicast protocols. Like DVMRP and PIM-DM AMRoute provides robustness by periodic flooding, without requiring special core-nodes. Instead of flooding data, AMRoute periodically floods a small signaling message. Although AMRoute has been designed for adhoc networks, the use of shared user multicast trees may also be appropriate for wired networks. We do not describe this wider application here, except to briefly discuss its possible application when group membership is sparsely distributed. As members become more sparse more packet replication is done closer to a source, and the bandwidth saving with multicast become less. Current multicast protocols require per group (and possibly per source) state to be maintained at all intermediate routers on the tree (and possibly all routers in the network); so, even with limited sparseness, the costs of multicast can outweigh the bandwidth savings. Using User Multicast trees (using a version of AMRoute without the expanding search) is better for these sparse members because it does not require group state at intermediate network nodes. 2 Assumptions (or lack thereof) AMRoute assumes the existence of an underlying unicast routing protocol that can be utilized for unicast IP communication between neighboring tree nodes. However, no assumptions are made about the syntax or semantics of the unicast protocol, and the same unicast protocol is not required to be used in all domains. The actual paths followed by the two directions of a unicast tunnel connecting neighboring group members may be different. It is not required that all network nodes support AMRoute or any other IP Multicast protocol. Non-multicast routers only need to support unicast, and forward the control packets (without any protocol processing) if the IP-level TTL is non-zero during the expanding ring search. Bommaiah, Liu, McAuley and Talpade [Page 4] INTERNET-DRAFT August 6, 1998 All member nodes must be capable of processing IP-in-IP encapsulation. No group members need have more than one interface or act as unicast routers (we can build a tree entirely from host computers). However, at least one member, and ideally all nodes, must be capable of being AMRouters: forwarding and replicating datagrams to other members. AMRoute routers must be able to set the TTL field in the IP headers (decrementing the inner IP TTL field before a datagram is repackaged and forwarded). We assume that the diameter of an adhoc network will be limited. Packets may be lost or corrupted in transmission on the wireless network. 3 Terminology 3.1 General Terms * Node: A device that implements IP. * Router: A node that forwards IP packets not explicitly addressed to itself. In case of adhoc networks, all nodes are at least unicast routers. * AMRouter: A node that implements the AMRoute protocol. * Host: Any node that is not a router. * Link: A communication facility or medium over which nodes can communicate at the link layer, such as an Ethernet (simple or bridged). * Interface: A node's attachment to a link. * Group Member/Node: A node that is either a receiver or sender of an IP multicast group. * Logical Core (Node): A group member that is responsible for initiating and maintaining the multicast tree in AMRoute. * Non-core node: A group member that is not a core node. * Mesh: A per group densely connected graph with group members as nodes. * Tree: A per group non-cyclic tree that connects all receivers and possibly sources. Bommaiah, Liu, McAuley and Talpade [Page 5] INTERNET-DRAFT August 6, 1998 * Tree/Mesh link: A unicast tunnel connecting neighboring nodes in a tree/mesh. * Tree/Mesh segment: A set of connected nodes of a group and the associated tree/mesh links. A network could have multiple disjoint segments for the same multicast group. * Native Multicast tree: A tree that is built using branches between directly connected nodes. * User-multicast tree: A tree that is built using virtual branches between group members. 3.2 Specification Language The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119. 4 Overview AMRoute creates a per group multicast distribution tree using unicast tunnels connecting group members. The protocol has two key parts: mesh creation and tree creation. AMRoute continuously creates a mesh of bidirectional tunnels between a pair of group members that are "close" together. Using a subset of the available virtual mesh links, the protocol periodically creates a multicast distribution tree. Only "logical core" nodes initiate mesh and tree creation; however, unlike conventional core based protocols the core can migrate dynamically according to group membership and network connectivity. 4.1 User-Multicast Distribution Trees Bommaiah, Liu, McAuley and Talpade [Page 6] INTERNET-DRAFT August 6, 1998 G* X *G | * | * / | * | * / | *| * / X----G----X----X----X \ * \ * \ * \* G------X---X----X *| * \ | * | * \ | * | * \ | G---X * X----X / \ * | / \ * | / \ * | X X G G = group member router (AMRoute capable) X = non-member router (need not be multicast or AMRoute capable) ---- = link **** = virtual user-multicast tree Figure 1: A Virtual User-Multicast tree Figure 1 shows a user-multicast tree connecting six members. The group members forward and replicate multicast traffic along the branches of the virtual tree. The datagram sent between logically neighboring nodes is physically sent on a unicast tunnel through potentially many intermediate routers. The path taken by the unicast tunnel can change without affecting the User-multicast tree. There are two key advantages to implementing our multicast protocol using only members: * Provided there remains a path among all nodes connected by mesh branches, the user-multicast tree need not change because of network changes (e.g., because of router movement). This independence improves robustness and reduces signaling overhead. * Non-members are not required to perform packet replication or even support any IP multicast protocol. This places the processing and storage overhead needed to support the multicast tree only on members. The penalty paid for using a user-multicast tree is reduced efficiency. Clearly, bandwidth efficiency is reduced as non-member routers are not allowed to perform packet replication. Furthermore, the delay is often increased. It can be shown, however, that there is at most a doubling in Bommaiah, Liu, McAuley and Talpade [Page 7] INTERNET-DRAFT August 6, 1998 bandwidth needs and increase in delay. Moreover, as the network becomes more dynamic, maintaining a more optimal path will become harder and require increasingly higher signaling overhead. Just as there are many ways to create native multicast trees, there are many ways to create user-multicast trees. We now describe a way that is well suited to ad-hoc networks. 4.2 Logical core and non-core members In the AMRoute protocol each group has at least one logical core that is responsible for initiating signaling actions, specifically: a) mesh joins (discovering new group members and disjoint mesh segments as described in Section 4.3) and b) multicast tree creation (see Section 4.4). A non-core node cannot initiate these two operations, acting only as a passive responding agent. Limiting the number of nodes that perform these two functions (ultimately to a single logical core) ensures that AMRoute can scale, without causing excessive signaling or processing overhead. An immediate reaction on hearing about using core nodes is that "Yes, a core improves scalability (as shown by CBT or PIM-SM, but it also causes robustness problems in dynamic networks." However, the AMRoute logical core node is different from a CBT core and PIM-SM RP in several fundamental aspects. In particular, an AMRoute core node: * is not a central point for all data. Forwarding can continue on working branches of the tree irrespective of the status of the logical core and links to the logical core. * is not a preset node. Each multicast tree segment designates one of its nodes to be the core based on the "core resolution algorithm." * changes dynamically. The core node migrates according to group membership and network connectivity. The core resolution algorithm is run in a distributed fashion by all nodes. The goal of the algorithm is to ensure that any group segment has exactly one core node and that the core node migrates to maintain a robust and efficient multicast tree. An AMRoute segment can temporarily have more than one core node for a group after new nodes join or disjoint segments merge together. A network node designates itself as a core when first joining a group. As a logical core Bommaiah, Liu, McAuley and Talpade [Page 8] INTERNET-DRAFT August 6, 1998 a node can quickly discover new group members and join the mesh and tree with its closest neighbors (not just to the existing core (see Section ??). When multiple core nodes exist in a segment, they will advertise their presence by sending out tree creation messages. Core nodes use the reception of tree creation messages from other cores to decide whether to remain as a core (see Section ??). An AMRoute segment can also have no core nodes because the core node disappears (e.g., leaves the group) or an existing segment is split into multiple disjoint segments (e.g., because of link or node failure). If a segment does not have a core node, one of the nodes will designate itself as the core node at some random time, on not receiving any join or tree creation messages (Section ??). A key issue with any algorithm that assigns a single core node is that it can centralize the multicast tree and indeed the mesh links on itself. AMRoute prevents centralization in a number of ways: * A non-core node is not allowed to graft to its own logical core. Without this limitation all group members would ultimately be connected to the core. * All nodes, including the core, are only allowed to have a limited number of tree links. If the limit is reached the node must drop the link furthest (at highest cost) from its current location. * A logical core will only take responsibility as core for a limited time or until some event makes changing the core desirable. A new logical core can be picked, for example when the core's mesh connectivity limit is reached. Clearly the core resolution and change algorithms are key to the robustness and performance of the AMRoute protocol. However, it is also desirable to contain the complexity of the algorithms. Simulations are hence being planned to determine the tradeoffs between simplicity, robustness and efficiency. Any experience or insights other researchers might have had with similar problems are welcome. 4.3 Mesh Creation An AMRoute mesh is a graph where each node is a member (sender or receiver) of the group and every link is a bi-directional unicast tunnel. While the mesh establishes connectivity across all the members of a group, a tree is Bommaiah, Liu, McAuley and Talpade [Page 9] INTERNET-DRAFT August 6, 1998 needed for forwarding the data (see Section ??). We use a two step process of creating a mesh before the tree because it is simpler and more robust. A mesh is much simpler to maintain a mesh (that could potentially have loops) than a tree (with no loops) at every stage of member mutual discovery phase. For example, a very naive merging algorithm could result in a loop when three disjoint trees discover each other. In addition, the redundant mesh links contribute towards increased robustness in the case of node/link failures. (Note that the use of unicast tunnels between neighboring nodes of the mesh itself contributes towards robustness in the face of intermediate node/link failures along routes between them as the unicast protocol is expected to establish a separate route around the failed network node/link). 4.3.1 Periodic JOIN-REQ Broadcast To create a mesh encompassing all the members (senders or receivers) of a specific group, mechanisms are needed to allow members to discover each other. The expanding ring search mechanism based on TTL-limited broadcasts is adopted. All core nodes periodically broadcast JOIN-REQ messages. The period between JOIN-REQ will be proportional to the TTL value associated with the last JOIN-REQ message. Each member begins by identifying itself to be the core of a 1-node mesh consisting of only itself. The core node sends out JOIN-REQ packets with increasing TTL to discover other members of the group. When a member (core or non-core) node receives a JOIN-REQ from a core for a different mesh for the same group, the node responds back with a JOIN-ACK. A new bi-directional tunnel is established between the core and the responding node of the other mesh. As a consequence of mesh mergers, a mesh will have multiple cores. One of the cores will emerge as the "winning" core of the unified mesh as a result of the core resolution algorithm. 4.3.2 Becoming a Passive Non-core node Only logical core nodes initiate the discovery of other disjoint meshes, while both core and non-core nodes respond to the discovery messages. It is simpler and more scalable (in bandwidth usage) to have only the core node initiate discovery as against every node of the mesh. However, to avoid the situation where every merger adds a link to a core (which might result in too many links from the core), non-core nodes can participate in the mergers by responding to discovery messages. Bommaiah, Liu, McAuley and Talpade [Page 10] INTERNET-DRAFT August 6, 1998 4.3.3 Leaving the group If a node leaves a group, they send out a single JOIN-NAK message to their neighboring nodes. If they subsequently receive any data or signaling message for that group they can send out further JOIN-NAK messages. 4.3.4 Limitation on link connectivity Whenever, the number of links adjacent to a node exceeds LINK-THRESHOLD, a node must break one or more of its links. Each of the links could be associated with a weight representing the "distance" (example, number of hops) from the neighbor. The links chosen to be broken could be the ones with the farthest neighbors. The farthest neighbor is notified about the link breakage using a JOIN-NAK message. If the message is lost and data is received from this non-neighbor, the JOIN-NAK message will be resent. Periodic mesh reconfiguration is necessary to maintain a reasonably optimal mesh in the face of mobility; however, removing links may result in temporary loss of data and additional overhead. When the links are broken, the mesh might be fragmented into disjoint meshes. Fragmentation is handled in the same manner as node failures. 4.3.5 Dynamic Core Migration There might be a need for dynamically migrating the logical core so as to make the tree more optimal. If the core is "closer" to the senders, then the tree may be a close approximation of a source-based tree (which is shared). If the core is at the "center" of the mesh, then TREE-CREATE messages (described in the next section) reach all the nodes of the mesh faster than when the core is at the "edge". In addition, as the core is involved in discovering and merging with other disjoint meshes, dynamically changing the core might help in avoiding the situation where there are excessive links adjacent to a core node. Policies and mechanisms for node changes are still under research. 4.4 Tree Creation This section discusses the creation of a tree for data forwarding purposes once a mesh has been established. The core is responsible for initiating the tree creation process. From the point of view of individual nodes of Bommaiah, Liu, McAuley and Talpade [Page 11] INTERNET-DRAFT August 6, 1998 the mesh, this phase involves identifying the subset of links adjacent to it that belong to the tree. 4.4.1 Periodic TREE-CREATE Broadcast The core sends out periodic TREE-CREATE messages along all the links adjacent to it in the mesh. (Note that TREE-CREATE messages are sent along the unicast tunnels in the mesh and are processed by group members only, while JOIN-REQ messages are broadcast messages that are processed by all network nodes). The periodicity of the TREE-CREATE messages depends on the size of the mesh and also on the mobility of the nodes of the mesh. As the mesh nodes are mobile, the number of hops between neighbors keeps changing dynamically. Thus, newer and more optimal trees might be created when TREE-CREATE messages are sent out. Group members receiving non-duplicate TREE-CREATEs forward it on all mesh links except the incoming, and mark the incoming and outgoing links as tree links. If a node has a collection of neighbors all 1-hop away on the same broadcast capable interface, then the node can send a single broadcast message to all 1-hop neighbors simultaneously. 4.4.2 TREE-CREATE-NAK If a link is not going to be used as part of the tree, the TREE-CREATE message is discarded and a TREE-CREATE-NAK is sent back along the incoming links. On receiving a TREE-CREATE-NAK, a group member marks the incoming link as a mesh link and not a tree link. Thus each non-core node considers the link along which a non-duplicate TREE-CREATE message was received and every other link along which no TREE-CREATE-NAK message was received to be part of the tree for a specific group. (Core considers every link adjacent to it to be part of the tree). Note that all these tree links are bidirectional tunnels. The choice of using ACK or NAK in response to the TREE-CREATE messages is dictated by whether robustness or saving bandwidth is more important. If a ACK-based (positive acknowledgment) scheme is used, then data may not be delivered along links where ACKs were lost. This results in loss of data, but no wasting of bandwidth. However, if a NAK (negative acknowledgment) based scheme is used, loss of NAKs can only result in same data being forwarded more than once (which is discarded by the downstream node on reception). When data arrives at a node along one of the tree links, the node forwards Bommaiah, Liu, McAuley and Talpade [Page 12] INTERNET-DRAFT August 6, 1998 the data along all other tree links. However, if data arrives along a non-tree link a TREE-CREATE-NAK message is (again) sent back along that link and the data is discarded. 4.4.3 Transient Loops The tree created by the th TREE-CREATE message might not be the same as the one created by th message. A situation may exist where some nodes are forwarding data according to the older tree and some according to the newer tree, which may result in loops or data loss. Such a phase is to be expected due to the dynamic nature of adhoc networks. However it is considered to be transient and AMRoute recovers from it as soon as the network reduces its dynamicity. 4.4.4 Node Failures and Group Leaves Nodes leaving a group or node failures are only partially handled by the redundant links in the mesh. In some situation, node failures might result in splitting the mesh into multiple disjoint meshes, where only one of these meshes has the core. Each node in the mesh expects to periodically receive TREE-CREATE messages. In case this message is not received within a specific timeout, the node designates itself to be the core after a random time. The node whose timer expires the earliest succeeds in becoming the core and initiates the processes of discovering other disjoint meshes as well as tree creation. Multiple cores that may arise in this case are resolved by the core resolution procedure. 4.4.5 Core Resolution In the event of mesh mergers, there might be multiple active cores in the new mesh. Nodes in the mesh become aware of this situation when they receive TREE-CREATE messages from multiple cores. The nodes execute a core resolution algorithm to decide on a unique core for the mesh and forward TREE-CREATE messages arriving from the unique core and discard TREE-CREATE messages from other cores. As the multiple cores in the mesh will also become aware of the existence of other cores, they will also execute the same core resolution algorithm. All the cores except the "winning" core will demote themselves to non-core state. One simple core resolution Bommaiah, Liu, McAuley and Talpade [Page 13] INTERNET-DRAFT August 6, 1998 algorithm could pick the winning core to be the one with the highest IP address. 4.4.6 Picking which branch to use for the Tree There are several possible algorithms that can be used to decide which mesh branches to use for the tree. The simplest approach is to simply accept the first TREE-CREATE message that is received and discard and duplicate TREE-CREATE messages using the sequence number included in each TREE-CREATE message. This results is a reasonable tree, but it is not necessarily the most bandwidth efficient (e.g., using minimum number of total hops) or lowest latency. We are therefore investigating the tradeoff of increasing the complexity of branch selection in order to improve bandwidth efficiency or reduce latency. To improve bandwidth efficiency a node can select the branch from which it received a TREE-CREATE from its closest neighbor (based on the TTL value in the outer IP header). However, in order to prevent the tree from becoming broken (not connecting all group members), the algorithm must a) be able to tell when the TREE-CREATE message has been received before, and b) not change the initial selection until the next round of TREE-CREATE messages are received. To detect duplicates it necessitates the use of a path-vector field in the TREE-CREATE message 5 Message Formats AMRoute uses five control messages for signaling purposes: JOIN-REQ, JOIN-ACK, JOIN-NAK, TREE-CREATE, TREE-CREATE-NAK. These are sent directly over IP. JOIN-REQ is the only message broadcast using the expanded ring search, while the other control messages are unicast between group members. The data packets are sent over UDP/IP, with no separate encapsulation for AMRoute. 5.1 JOIN-REQ This is broadcast periodically by a logical core for detecting other group segments. Bommaiah, Liu, McAuley and Talpade [Page 14] INTERNET-DRAFT August 6, 1998 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version | Message-ID | Unused | Initial-TTL | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source IP Address | IP Multicast Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5.2 JOIN-ACK This is generated by a tree node in response to receiving a JOIN-REQ from a different logical core. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version | Message-ID | Unused | Initial-TTL | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source IP Address | IP Multicast Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5.3 JOIN-NAK This is generated by a tree node if its application leaves the group. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version | Message-ID | Unused | Initial-TTL | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source IP Address | IP Multicast Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Bommaiah, Liu, McAuley and Talpade [Page 15] INTERNET-DRAFT August 6, 1998 5.4 TREE-CREATE This is generated periodically by a logical core to refresh the group spanning 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version | Message-ID | Seq-Number | Unused | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source IP Address | IP Multicast Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Path Vector (only used with optimized trees) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5.5 TREE-CREATE-NAK This is generated by a tree node to convert a tree link into a mesh link. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version | Message-ID | Seq-Number | Unused | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source IP Address | IP Multicast Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5.6 Field Descriptions * Version: Version number of AMRoute being used. * Message-ID: Identifies message type; 1: JOIN-REQ 2: JOIN-ACK 3: JOIN-NAK 4: TREE-CREATE 5: TREE-CREATE-NAK * Seq-Number: Monotonically increasing sequence number is used to identify messages uniquely from same source. * Initial-TTL: Set by source of message; indicates number of IP hops traversed when used along with TTL value in IP header. Bommaiah, Liu, McAuley and Talpade [Page 16] INTERNET-DRAFT August 6, 1998 * Source-IP-Address: IP address of original source of message. * IP-Multicast-Address: Identifies multicast group that the message pertains to. * Path Vector: Used to distinguish among replicated versions of the same TREE-CREATE messages when more bandwidth or latency optimal trees are desired. Initially it is set to 0. Each node that performs any replication modifies the value at each replication (see Section 6). 6 Detailed Node Operation The detailed operation at each AMRoute-capable node in the adhoc network is now described. The current emphasis of the protocol is on simplicity, hence some of the optimizations (such as dynamic core migration) described in earlier sections are not specified in this version of AMRoute. 6.1 State Diagram +------------+ | NON-MEMBER |<------------------------------------ +------------+ ^ | ^ | | | | | | | JOIN | | LEAVE LEAVE | ------------- | | ----- ----- | snd JOIN-REQ | | snd JOIN-NAK snd JOIN-NAK| & TREE-CREATE | | | | | | | | | | | rcv TREE-CREATE & lose | V | ---------------------- | +------------+ x +----------+ | CORE |----------------------------->| NON-CORE | | |<-----------------------------| | +------------+ TREE-CREATE timeout +----------+ -------------------------- snd JOIN-REQ & TREE-CREATE FIGURE 2: Simplified AMRoute Node State Diagram Bommaiah, Liu, McAuley and Talpade [Page 17] INTERNET-DRAFT August 6, 1998 Figure 2 shows the three main AMRoute states and state transitions (with causing events and resulting actions). The states can be interpreted as follows : * NON-MEMBER - a node does not belong to the multicast group. * CORE - a node currently recognizes itself to be a logical core. * NON-CORE - a node is currently a non-core member in the multicast group. A node transitions from the NON-MEMBER state when an application on the node joins a group and transitions to it from all other states when the application leaves the group. A node transitions to the CORE state when an application joins a group, and by default sets itself to be a logical core. A logical core sends out periodic JOIN-REQ messages and TREE-CREATE messages. A logical core becomes a non-core node if it loses in the core resolution procedure that ensues when it receives a TREE-CREATE message from another core belonging to the same multicast group, which means the other core becomes the new core. A non-core member expects periodic TREE-CREATE messages from a logical core. If it does not receive one within the specified period, the associated timer expires and the node resets itself to be a core. 6.2 Timers A logical core keeps two timers, namely the JOIN-REQ-SEND timer and the TREE-CREATE-SEND timer. The expiry of JOIN-REQ-SEND causes the node to compute the new TTL value to use for the expanding ring search, broadcast a new JOIN-REQ with this TTL value and reset the timer. The TREE-CREATE-SEND timer is kept to send out periodic TREE-CREATE messages. A non-core member uses a TREE-CREATE-RCV timer. When it expires, the node waits for some random amount of time before it resets itself to be a core, and starts sending out JOIN-REQs and TREE-CREATEs. This period is set to be random to prevent multiple non-core nodes from becoming cores simultaneously. Bommaiah, Liu, McAuley and Talpade [Page 18] INTERNET-DRAFT August 6, 1998 6.3 Data Structures Each member keeps two tables, each containing a set of neighbors, the neighbors on the mesh and the neighbors on the multicast tree. Note that these neighbors are connected by unicast tunnels rather than being physical neighbors. The member also keeps a "hop-count" associated with each mesh link. This hop-count is obtained at the time of mesh link creation, and is updated by the periodic control messages (control messages have original TTL value used by source in the headers). A node tracks the ID of the logical core it currently recognizes, which can be itself. We allow the existence of multiple logical cores in a same group. However, each node only recognizes one logical core at any instant. This information is updated when the node receives a TREE-CREATE from a logical core it did not recognize, or when the node resets itself to be core, as described in detail in the next section. 6.4 State Functions 6.4.1 NON-MEMBER When a node does not belong to any multicast group, it basically forward any packets it receives, behaving as an intermediate router. 6.4.2 CORE Upon entering this state, a node sets its CORE ID to be itself. A logical core sends out two periodic messages: 1) JOIN-REQ This message is used to detect other group members. An expanding ring search is used whereby successive JOIN-REQs are broadcast with increasing TTL values every JOIN-REQ-SEND time units. The TTL value can only be increased to a specific upper bound, after which all JOIN-REQs are broadcast using the same value. 2) TREE-CREATE This message is used to build the multicast tree. This message is transmitted over the existing mesh links, i.e., this message is sent Bommaiah, Liu, McAuley and Talpade [Page 19] INTERNET-DRAFT August 6, 1998 through unicast tunnels to mesh neighbors. On transmission of a TREE-CREATE, a logical core considers its mesh neighbors as its tree neighbors also until informed otherwise by a TREE-CREATE-NAK. Note that when a node joins a group and sets itself to be a logical core, it has no mesh neighbors prior to receiving a JOIN-ACK or JOIN-REQ. Therefore, the TREE-CREATE message is not transmitted until one or more mesh neighbors exist. A logical core processes the following received messages pertaining to the same multicast group for which it is the core : 1) JOIN-ACK * If the JOIN-ACK is responding to a JOIN-REQ sent out by this core, the logical core marks the source of the JOIN-ACK as its mesh neighbor and drops the JOIN-ACK. 2) JOIN-REQ * If the JOIN-REQ was transmitted by this core itself (because of the broadcast medium), it is ignored. * If this core is in the same group as the JOIN-REQ indicates and does not have a mesh or tree link to the source of the JOIN-REQ, it returns a JOIN-ACK and drops the JOIN-REQ. (Note that the JOIN-ACK is unicast to the source of the JOIN-REQ). The core marks the source of the JOIN-ACK as its mesh neighbor. * Otherwise the core decrements the TTL of the JOIN-REQ and re-broadcasts it. 3) JOIN-NAK * The logical core deletes any existing mesh and tree links with the source of the JOIN-NAK. 4) TREE-CREATE * TREE-CREATE messages can only be generated by a logical core. * On receiving the message, the logical core uses the core resolution algorithm to determine the winner. If the core itself wins, the TREE-CREATE is dropped. If the source of this message wins, the receiving node becomes a non-core member and transitions into the NON-CORE state. The receiving node also marks the winning core as a mesh neighbor, and recognizes it as the new logical core. The TREE-CREATE message is forwarded onto downstream mesh links, which are Bommaiah, Liu, McAuley and Talpade [Page 20] INTERNET-DRAFT August 6, 1998 then marked as tree links. 5) TREE-CREATE-NAK * The incoming link is marked as a mesh link, instead of a tree link, and the message is dropped. 6.4.3 NON-CORE A non-core member does not send out control messages until the TREE-CREATE-RCV timer expires. It then resets itself to be a logical core after a random wait. Similar to a logical core, a non-core member processes the following received messages pertaining to its multicast group : 1) JOIN-ACK * A non-core member will NEVER receive a JOIN-ACK message since JOIN-ACK is sent to the source of a JOIN-REQ, which can only be a logical core. Hence any JOIN-ACK received is dropped. 2) JOIN-REQ * If this JOIN-REQ comes from a logical core that this node recognizes (which means they are already on the same mesh), decrement the TTL value of the JOIN-REQ and rebroadcast it. * If this JOIN-REQ comes from a different logical core from that recognized by this node, the node returns a JOIN-ACK to the source and marks the source as a mesh neighbor. * If this JOIN-REQ is for a different group, the node decrements the TTL of the JOIN-REQ and re-broadcasts it (acting as an intermediate router). 3) JOIN-NAK * The node deletes any existing mesh and tree links with the source of the JOIN-NAK. 4) TREE-CREATE * If the source of this TREE-CREATE is the same core as that recognized by this node, and the message has a new sequence number (not a Bommaiah, Liu, McAuley and Talpade [Page 21] INTERNET-DRAFT August 6, 1998 duplicate), the node marks the incoming link as a tree link. It also forwards the message to neighbors along its downstream mesh links and marks them as tree links. * If this TREE-CREATE is a duplicate from the same core as that recognized by this node, the node marks the incoming link as a mesh link. It also sends a TREE-CREATE-NAK message to the upstream node and drops this TREE-CREATE. * If this TREE-CREATE comes from a different logical core from that recognized by this node, it runs the core resolution algorithm to decide the new core. If the new core wins, the node sets the CORE ID to the new core, forwards the TREE-CREATE onto all its downstream mesh links, and marks the incoming and outgoing links as tree links. If the source loses in the core resolution, this TREE-CREATE is dropped. The TREE-CREATE path vector is modified if a node performs does any replication. The node reads the current content of path vector looking for the least significant "1" (Initially the path vector is set to zero) 5) TREE-CREATE-NAK * The incoming link is marked as a mesh link, instead of a tree link, and the message is dropped. 7 Security [TO BE DONE] Similar to issues in other IP Multicast protocols, but it has the advantage that only group members are involved in the tree creation. 8 Current Status Several issues related to the AMRoute protocol design have to be resolved. An extremely simple version of the protocol has been specified above. Depending on feedback received from the MANET working group and experience gained from our simulations, the protocol shall be augmented to improve the tree efficiency. Bommaiah, Liu, McAuley and Talpade [Page 22] INTERNET-DRAFT August 6, 1998 9 ACKNOWLEDGMENTS This work was done under a grant from the Army Research Lab (ARL) ATIRP program. The initial idea of using user-multicast trees was suggested to us by C. Huitema. 10 Author Information Bommaiah, Ethendranath (ethen@bellcore.com) Liu, Mingyan (Univ of Maryland, daphnel@isr.umd.edu) McAuley, Anthony (mcauley@bellcore.com) Talpade, Rajesh (rrt@bellcore.com) Bellcore, 445, South St., Morristown, NJ 07960 Bommaiah, Liu, McAuley and Talpade [Page 23] INTERNET-DRAFT August 6, 1998 References [1] Ballardie, T., "Core based Trees (CBT) Multicast Routing Architecture", RFC 2201, September, 1997. [2] Deering, S., et al, "Protocol Independent Multicast-Sparse Mode (PIM-SM): Motivation and Architecture", Internet Draft, draft-ietf-idmr-pim-arch-04.txt, October, 1996. [3] Pusateri, T., "Distance Vector Multicast Routing Protocol", Internet Draft, draft-ietf-idmr-dvmrp-v3-06.txt, March 1998. [4] Corson, S., and J. Macker, "Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations", Internet Draft, draft-ietf-manet-issues-00.txt, September, 1997. [5] Perkins, C., "Mobile Ad hoc Networking Terminology", Internet Draft, draft-ietf-manet-term-00.txt, October, 1997. Bommaiah, Liu, McAuley and Talpade [Page 24]