Internet Engineering Task Force Bommaiah, McAuley and Talpade
INTERNET-DRAFT Bellcore
Liu
Univ of Maryland
August 6, 1998
Expires: February 7, 1999
<draft-talpade-manet-amroute-00.txt>
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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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 <n>th TREE-CREATE message might not be the same as
the one created by <n-1>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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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 <draft-manet-amroute-00.txt> 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]
