Internet Draft L. Ji, UMD
Expiration: January 12, 2001 M. S. Corson, UMD
July 12, 2000
Differential Destination Multicast (DDM) Specification
<draft-ietf-manet-ddm-00.txt>
Status of this Memo
This document is an Internet-Draft and is NOT offered in accordance
with Section 10 of RFC2026, and the author does not provide the IETF
with any rights other than to publish as an Internet-Draft. This
document is a submission to the Mobile Ad-hoc Networks (manet)
Working Group of the Internet Engineering Task Force (IETF). Comments
should be submitted to the Working Group mailing list at
"manet@itd.nrl.navy.mil". Distribution of this memo is unlimited.
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.
Distribution of this memo is unlimited.
Abstract
This draft describes a multicast routing protocol for mobile ad hoc
networks (MANETs). The protocol---termed Differential Destination
Multicast (DDM)---differs from common approaches proposed for ad hoc
multicast routing in two ways. Firstly, instead of distributing
membership control throughout the network, DDM concentrates this
authority at the data sources (i.e. senders) thereby giving senders
knowledge of group membership. Secondly, differentially-encoded,
variable-length destination headers are inserted in data packets
which are used in combination with unicast routing tables to forward
multicast packets towards multicast receivers. Instead of requiring
that multicast forwarding state be stored in participating nodes,
Ji and Corson [Page 1]
Internet Draft Differential Destination Multicast July 12, 2000
this approach also provides the option of stateless multicasting.
Each node independently has the choice of maintaining cached
forwarding state, or requesting its upstream neighbor to insert this
state into self-routed data packets, or some combination thereof.
The protocol is best suited for use with small multicast groups
operating in dynamic networks of any size.
1. Introduction
The Differential Destination Multicast (DDM) protocol is designed
with several goals in mind.
The first goal is to minimize multicast routing protocol's
communication channel use especially the number of channel access.
Due to the fact that commonly all MANET nodes operate in broadcast
media, the extra cost of each protocol channel access imposed by
lower layers is very expensive compared to the case that protocols
working primarily with point-to-point links.
The second purpose of the design of DDM is to introduce a protocol
which enables centralized group membership management. Most MANET
multicast protocols [1,2,3,4] follow the footsteps of their wired
network counterparts [5,6,7]. They distribute membership control (or
lack thereof) over the network. The protocols themselves do not have
the mechanism to prevent any party from joining the group. Thus, the
sources have no way to control how its data is distributed. If a
data source wants to limit the distribution scope, it has to use
other external means such as key distribution. Even so, such
external mechanisms do not prevent data being received by
unauthorized parties. In many applications, especially for small
multicast groups, a centralized approach is more in favor because it
establishes a better ground for implementing security/pricing
features.
The third goal is to make the protocol as flexible as possible. Due
to the highly dynamic nature of MANETs, the protocol should leave
enough configuration space so each node may adaptively choose its own
operation parameters according to its own behavior and local
environment.
The resultant protocol is significantly different from other MANET
multicast protocols proposed to this group. Unlike in other
protocols, DDM lets the sources control the membership. All
membership changes need to be directed to the sources. Also
different from traditional multicasting, DDM encodes multicast
receiver (destination) addresses in multicast data packets using a
special DDM Data Header. This way it is not necessary for each node
to maintain per-session multicast forwarding states. Thus, it is
Ji and Corson [Page 2]
Internet Draft Differential Destination Multicast July 12, 2000
more scalable with respect to the number of sessions. Although the
number of multicast destinations of each session is limited by
header/packet size, given the relatively small size (compared to the
wired Internet) of MANETs, such approach may well serve a large
population of applications.
2 Terminology
Node: A device that implements IP.
Multicast Session: The basic unit for multicasting organization.
Each multicast session is identified by a group ID and a data source.
Multicast Destinations: Each node with multicast data receiving
application running is a multicast destination.
Forwarding Set (FS): The address set each DDM node uses to record to
which multicast destinations it needs to forward multicast data.
Direction Set (DS): The address set each DDM node uses to record via
a particular next hop, to which multicast destinations multicast data
are forwarded.
3 Protocol Overview
3.1 Protocol Description
The proposed approach is, motivated, in part, by the approach to
unicast routing of Dynamic Source Routing (DSR) [10] and derived, in
part, from the work of [8,9]. The latter has recently been named
Explicit Multicasting (or xcast for short).
In DDM, the source controls multicast group membership to ease
certain aspects of security administration. More importantly, and a
departure from all proposed MANET multicast protocols to date, DDM
encodes the multicast destinations in each data packet header in a
fashion different from [8,9]. This "in-band" information can be used
to establish soft-state routing entries if desired. Using such an
approach has two advantages for MANETs. Firstly, there is no control
overhead expended when the group is idle; a characteristic shared
with DSR. Since many multicast applications do not have continuous
traffic flows, it can be expensive in terms of network control
overhead to maintain multicast forwarding state in routers during
idle periods. In-band control avoids this problem because if there
is no data traffic, there is no need for any control information
either. Secondly, it is not necessary for the nodes along the data
forwarding paths to maintain multicast forwarding state. When one
Ji and Corson [Page 3]
Internet Draft Differential Destination Multicast July 12, 2000
intermediate node receives a DDM data packet, it need only look at
the DDM header to decide how to forward the packet; another
similarity to DSR. Assuming that routers can handle this processing
cost, this stateless mode can be very reactive and efficient. This
stateless approach also avoids loading the network with pure
signaling traffic; a third trait shared with DSR. In so doing, the
hope is that the unicast algorithm can converge that much *faster*,
with DDM then making immediate use of this knowledge.
While the fixed network and MANETs can benefit from stateless,
explicit multicasting because of its savings in storage complexity,
it is desirable to follow this approach in MANETs for other reasons
as well. Firstly, media access is expensive in wireless broadcast
channels. Although packing routing information together with data
traffic will enlarge data packet size, it reduces the total number of
channel accesses because it reduces the number of control packets
generated by the protocol. Therefore such approach can be more
efficient overall in many scenarios. Secondly in broadcast networks,
when a node needs to send to more than one neighbor, it only needs to
broadcast the packet once. So this approach has better bandwidth
consumption and channel access properties in broadcast networks than
in point-to-point networks. Lastly, one argument against explicit
multicasting in the wired Internet is that the relatively complex
header processing prevents fast path forwarding at routers.
Presently in MANETs, the effect of per-packet processing on
forwarding rate is not significant relative to bandwidth and energy
constraints.
In scenarios where the stateless approach is not favorable, DDM may
also operate in a "soft-state" mode. It is here that DDM markedly
departs from the work of [8,9]. In this mode, as data packets with
in-band information are routed through the network, each node along
the forwarding path remembers the destinations to which it forwarded
the last time and how the data was forwarded (i.e. which next hop was
used for each destination). By storing this information, the
protocol no longer needs to list all the destinations in every data
packet header. When changes occur in the underlying unicast routing,
an upstream node only needs to inform its downstream neighbors (i.e.
its next hops) regarding the *differences* in destination forwarding
since the last packet; hence, the name "Differential Destination"
Multicast. Reporting only these differences significantly reduces
DDM header sizes. Ideally, in a stable network where the topology
and membership remain unchanged, only the first data packet needs to
contain destination addresses and all subsequent packets would
contain no DDM routing information. In practice, the state kept at
each node along the forwarding paths is "soft". Each time data
forwarding occurs, this state is refreshed. Stale state eventually
times-out and is removed.
Ji and Corson [Page 4]
Internet Draft Differential Destination Multicast July 12, 2000
Also different from Explicit Multicasting, DDM takes advantage of the
broadcasting medium. Multiple DDM blocks, which is the per next hop
forwarding information unit, may be aggregated together so one data
packet transmission can forward data to multiple neighbors (next
hops). On the other hand, DDM again provides the flexibility for
each forwarding node to choose by itself. In an environment
discriminates against broadcasting but in favor of unicasting, if
high data throughput is critical to the application, forwarding nodes
may decide not to aggregate DDM Blocks together. In this case,
multicast data is forwarded in unicast envelop to each next hop.
Within each such packet, the DDM header only contains the DDM
Block(s) for the intended receiver.
DDM is not a general purpose multicast protocol in the conventional
sense. The header-encoded destination mechanism does not scale well
with group size. The stateless mode (in common with other xcast-
based approaches), however, does scale well with the number of
multicast groups, as no per-group state is required in any routers.
In MANETs, if the number of multicast groups is small enough to
permit state storage, then the soft-state version using
differentially-encoded header processing can be used to reduce
average packet header size and save bandwidth. This approach,
however, has essentially little applicability to fixed networks as
the complexity of the differentially-encoded header processing would
significantly slow down forwarding rates in high-speed networks.
3.2 Route Correctness
DDM replies on the underlying unicast routing protocol to provide the
"next hop" information. DDM is loop-free as long as the underlying
unicast routing is loop-free. Since the DDM routing (FS to DS
partition) calculation is carried out for every data packet, only the
most recent unicast routing information is used. Transient loops are
still possible during unicast routing convergence period, but will
disappear as the unicast protocol recovers. Some data packets may
have been errantly sent using erroneous route information. In this
case, these data packets will either dropped when the IP TTL reaches
zero, or will exit the loop and head towards the destination when
some forwarding node finally corrects the loop.
The same argument holds for broken routes. In many other
multicasting protocols, broken links, if used by the protocol
forwarding topology, should be discovered as soon as possible so they
can be repaired. In DDM, it is not necessary to inform DDM when a
link used in multicast forwarding goes down. The old DS and the old
FS on either end of a broken link are left alone to be deleted on
time-out. As soon as the unicast routing recovers, DDM will use the
new next hops (if available) when forwarding the next multicast data
Ji and Corson [Page 5]
Internet Draft Differential Destination Multicast July 12, 2000
packet. With these new next hops, DDM will use new and likely
different DS's.
When there is new link to be added, DDM does not react either. In
fact, DDM is not aware of the change if this new link is not used in
DDM routing. Only after the unicast routing protocol designates this
link as a next hop for some DDM destination will DDM utilize the new
link. DDM will when set up a new DS for this new link.
Data packets may be lost during transmission. When nodes are
opearting in "statefree" mode, each data packet is processed
independently from the previous packets. Therefore the loss does not
affect the forwarding correctness of future packets. When operating
"soft-state" mode, if the lost packet does not contain any multicast
destination updates, it is simply a data loss. No future forwarding
will be affected eiother. If the packet does contain updates, the
loss may de-synchronize the FS sets on the receiving ends from the
matching DS sets on the sending ends. However, since all packets
contain DDM Block Sequence Number, the receiving end of the lossy
link will discover the loss of an informative DDM header when
receiving the next data packet. A RSYNC is then sent back asking for
a R packet to re-synchronize the FS sets and the DS sets.
4 DDM Protocol Specification
DDM asumes that there is a unicast routing protocol running on each
MANET node. Through this unicast routing protocol, DDM can obtain
the "next hop" information for a particular destination. Also DDM
may use this unicast routing protocol to deliver unicast packets.
4.1 Data Structures
At each source node, there is a Member List. This list is used to
keep track of the admitted members for each session the source is
originating data. It contains the addresses of all the multicast
group members who have successfully joined the session.
At each node, there is one Forwarding Set (FS) for each multicast
session. It records to which destinations this node forwards
multicast data. At the source node, the FS contains the same set of
node addresses as the ML. At other nodes, the FS is actually the
union of several subsets. Each subset FS_k records the multicast
destinations included in data packets received from upstream neighbor
k. After receiving a data packet from an upstream neighbor k, the
receiving node will update the corresponding subset FS_k set and then
the unioned set FS is recalculated.
Ji and Corson [Page 6]
Internet Draft Differential Destination Multicast July 12, 2000
Associated with each set FS_k, there is one sequence number
SEQ(FS)_k. This is used to record the last DDM Block Sequence Number
seen in a received DDM data packet from upstream neighbor k. The
reason for this sequence number is to detect the loss of DDM data
packets containing forwarding set updates. For each multicast
session, there is a data sequence number cache kept by each node. It
is used to record recently seen data sequence numbers. This cache is
used to avoid duplicated forwarding of the same data packet. In
addition, each node needs to remember if itself is a receiver member
of a particular multicast session.
When a node is forwarding a data packet received from an upstream
neighbor k, it duplicates the data packet (if forwarding to multiple
neighbors is necessary) and sends the packet(s) to the next-hop
neighbor(s). The FS contains all the multicast destinations for this
session to which this node needs to forward. However, these
destinations may be reached via different paths (i.e. next hops).
Therefore, the FS needs to be partitioned into subsets according to
the next hops these destinations require. The destinations in the FS
who use the same downstream neighbor (next hop) will be put into the
same subset. These subsets resulting from partitioning the FS are
called Direction Sets (DS) (a DS_l exists for each downstream
neighbor l). For each DS_l there is also a sequence number
SEQ(DS)_l. It is initialized to 0 when the DS_l is created for the
first time. Each DS_l contains a "Forced Refreshing" (FR) flag.
This flag has three states: no forcing, forcing once and forcing
always. The use of this flag will be explained in sections 4.4 and
4.5.
4.2 Packet Formats
DDM employs two types of packets: control packets and data packets,
where it is understood that data packets may also contain control
information. There are five types of control packets: JOIN, ACK,
LEAVE, RSYNC, and CTRL_DATA. All of them are unicast IP packets.
The first three are used only by the membership control part of the
algorithm. The fourth is used to coordinate between a pair of
neighboring nodes. The last one is used to encapsulate multicast
data so it can be delivered to a particular multicast destination via
unicast routing. Regular multicast data packets are D-class IP
packets with DDM Data Header. However, multicast data may also be
encapsulated within unicast IP packets to be forwarded to the next
hop neighbors if uncasting is used as the primary data transmission
means. This encapsulation is different from the CTRL_DATA because it
is only for downstream neighbors one hop away.
Ji and Corson [Page 7]
Internet Draft Differential Destination Multicast July 12, 2000
4.2.1 Base DDM Control Packet Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multicast Group Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Ver | Type | Unused |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
All DDM control messages contain this common base. Depending on the
control message type, certain extensions may follow. The "Ver" field
contains the DDM version number. The "Type" field contains the
control message type. The "Multicast Group Address" contains the ID
of the multicast group of interest.
4.2.2 JOIN Packet
This packet is used to express a node's interest towards a particular
multicast session. This packet is a unicast IP packet sent from the
joining node to the multicast session source. The "Type" field of
the base format is set to 0. The joiner's address is used as the
source address of the IP packet. The multicast session source's
address is used as the destination address of the IP packet. The TTL
field of the IP packet is set to the estimated NETWORK_DIAMETER.
4.2.3 ACK Packet
This packet serves as a notification of admission to a particular
multicast session. It is a unicast IP packet sent from the multicast
session source to the interested joining node. The "Type" field of
the base format is set to 1. The joiner's IP address is used as the
destination address of the IP packet. The multicast session source's
ID is used as the source address of the IP packet. The TTL field of
the IP packet is set to the estimated NETWORK_DIAMETER.
4.2.3 LEAVE Packet
This packet serves as a resignation from a particular multicast
session. It is a unicast IP packet sent from the multicast member
node to the multicast session source. The "Type" field of the base
format is set to 2. The leaving node's address is used as the source
address of the IP packet. The multicast session source's address is
used as the destination address of the IP packet. The TTL field of
the IP packet is set to the estimated NETWORK_DIAMETER.
4.2.3 RSYNC Packet
Ji and Corson [Page 8]
Internet Draft Differential Destination Multicast July 12, 2000
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multicast Session Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| DDM Blk Seq | FR| Unused |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
RSYNC extension
RSYNC (Request to Synchronization) packet is used to synchronize the
multicast destination address sets between a pair of neighboring
nodes. It is unicast IP packet sent from the downstream neighbor to
the upstream neighbor. The communicating neighbors are used as the
source and destination fields of the IP header. The TTL field of the
IP header is set to 1. The "Type" field of the base format is set to
3. Other than the common base, RSYNC packet also contains the above
extension. In this extension, the re-synchronization requester needs
to specify the multicast session source and the DDM Block Sequence
Number. The "FR" (Force Refreshing) flag can have the value of "no
forcing", forcing once", and "forcing always".
4.2.3 CTRL_DATA Packet
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multicast Session Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
CTRL_DATA extension
This packet is used to encapsulate multicast data in a unicast packet
so it can be forwarding via unicasting to reach a particular
multicast destination. It is a unicast IP packet sent from the
forwarding node who needs to forward the data to the multicast
destination. The TTL field of the IP packet is set to the estimated
NETWORK_DIAMETER. The "Type" field of the base format is set to 4.
It also carries the above extension so upon receiving such packet,
the multicast destination can identify to which multicast session the
data belongs.
4.2.4 DATA Packet
Ji and Corson [Page 9]
Internet Draft Differential Destination Multicast July 12, 2000
|0 1 2 3 4 5 6 7|8 9 0 1 2 3 4 5|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| DDM Blk Seq | type |Num Adr|
+---------------+---------------+
DDM Block
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|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-----+
| Ver |P| Len | TOL | Data Sequence Number |Summary
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multicast Group Address |Section
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multicast Session Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-----+
| DDM Block 0 | DDM Block 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-----+
| Destination (member) 0 for Receiver 0 | D |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ D |
| Destination (member) 1 for Receiver 0 | M |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| ... ... | B |
~ ... ... ~ L |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ K |
| Destination (member) m_1 - 1 for Receiver 0 | 0 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-----|
| Destination (member) 0 for Receiver 1 | D |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ D |
| Destination (member) 1 for Receiver 1 | M |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| ... ... | B |
~ ... ... ~ L |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ K |
| Destination (member) m_1 - 1 for Receiver 1 | 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-----+
DDM Data Header Format (Unicast)
Ji and Corson [Page 10]
Internet Draft Differential Destination Multicast July 12, 2000
0 1 2 3
|0 1 2 3 4 5 6 7|8 9 0 1 2 3 4 5|6 7 8 9 0 1 2 3|4 5 6 7 8 9 0 1|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-----+
| Ver |P| Len | TOL | Data Sequence Number |Summary
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Sender |Section
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-----+
| DDM Block 0 | DDM Block 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| DDM Block n-1 | Padding |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-----+
| Receiver 0 | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ D |
| Destination (member) 0 for Receiver 0 | D |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ M |
| Destination (member) 1 for Receiver 0 | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ B |
| ... ... | L |
~ ... ... ~ K |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Destination (member) m_1 - 1 for Receiver 0 | 0 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-----+
| Receiver 1 | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ D |
| Destination (member) 0 for Receiver 1 | D |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ M |
| Destination (member) 1 for Receiver 1 | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ B |
| ... ... | L |
~ ... ... ~ K |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Destination (member) m_1 - 1 for Receiver 1 | 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-----+
| ... ... |
~ ... ... ~ ~
| ... ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-----+
| Receiver n-1 | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ D |
| Destination (member) 0 for Receiver n-1 | D |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ M |
| Destination (member) 1 for Receiver n-1 | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ B |
| ... ... | L |
| ... ... | K |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
Ji and Corson [Page 11]
Internet Draft Differential Destination Multicast July 12, 2000
| Destination (member) m_(n-1) - 1 for Receiver n-1 | n-1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-----+
DDM Data Header Format (Multicast)
The above are the formats for DDM Data Header. This header is
inserted into data packets before the data payload. The IP data
packet's destination address may be set to the multicast group
address while the multicast session source address is used as the
source address of the IP packet. This is shown in "DDM Data Header
Format (Multicast)". Or, when forwarding node chooses to use unicast
to forward a data packet to a next hop, it needs to use its own
address as the IP source and the next hop address as the IP
destination address. The group address and the multicast session
source address are hidden in the DDM Data Header. This is shown in
"DDM Data Header Format (Unicast)".
At the beginning of the DDM Data Header it is the summary section.
In the summary section, after the DDM version field, it is the POLL
flag for membership refreshing. The "Len" field indicates how many
DDM Blocks there are in the header. The "TOL" (Time Of Life) field
indicates the life time of the FS set on the intended receivers of
this packet. Then it is followed by the DDM data sequence number.
The next is the address of the packet sender (the forwarding node).
In the case of unicasting, the packet sender is in the IP source
field. Instead, the summary section contains the multicast group
address and the session source address.
The rest of the header contains all the DDM Blocks and the addresses
used by them. Each DDM Block contains a Block Sequence Number, a
Block Type, and a Number of Addresses field. There are four types of
DDM Blocks. They are Empty (E), Replace (R), Incremental Difference
(Di), and Decremental Difference (Dd) blocks, and their types are 0,
1, 2, and 3 respectively. E Block does not list any multicast
destination. R block lists all multicast destinations to which the
receiving node needs to forward. Di and Dd Blocks (both may be
referred as D blocks in the rest of the draft) contain different
destination addresses from the last forwarding. The multicast
destination lists used by the blocks will be referred as L list (for
R header), L_i list (for Di Block), or L_d list (for Dd Block).
Since R and D Blocks contain destination list updates, they may be
referred as "informative" in the rest of the description.
When a node uses broadcast to forward data to next hops, the first
node address used by any DDM Block is always the intended receiver
for this DDM Block. However, when a node uses unicast to forward
data to individual next hop, this intended receiver field is omitted
since the intended receiver is the IP destination. Other addresses
Ji and Corson [Page 12]
Internet Draft Differential Destination Multicast July 12, 2000
used by a DDM Block are the multicast destinations to whom data needs
to be forwarded by the intended receiver of this DDM block. To align
the header better, all DDM Blocks are concatenated together, then
followed by an archive of all the addresses used by all the DDM
blocks. These addresses are serialized in the same order as the DDM
Blocks using them.
4.3 Membership Management
In contrast with traditional multicast algorithms, a multicast data
source plays an important role in the DDM protocol. The protocol
proceeds independently for each source sending to a multicast group,
and the remaining description applies to a single source. The source
acts as an admission controller for the information it is sending.
When a node (the "joiner") is interested in a particular multicast
session, it needs to join the session by unicasting a JOIN message to
the source for that session. This JOIN message include the ID of the
group to which the node wants to join. The joiner's ID and the
source ID are used as the source and destination fields of the IP
header of the JOIN message. After receiving the JOIN message and
verifying its own role of being the source for the interested
multicast session, the source decides if the JOIN can be accepted.
The admission policies and protocols are beyond the scope of this
draft.
Upon receiving a JOIN message, if the joiner passes the session's
admission requirements, the source adds the ID of the "joiner" into
its Member List (ML). The source then acknowledges the JOIN message
by unicasting an ACK message back to the joiner.
Back at the joiner, after the JOIN message is sent, the joiner waits
for one JOIN_WAITING_PERIOD. If it has not received an ACK till the
end of this period, the joiner needs to resend the JOIN message.
When sending the JOIN messages, the waiting period is exponentially
backed off for every consequent JOIN sent. That is, the waiting
period for the i-th JOIN message is:
(2 ** (i - 1)) * JOIN_WAITING_PERIOD
The sending of JOIN messages is stopped when either an ACK message is
received or MAX_JOIN_RETRY JOIN messages have been sent and the
waiting period for the last JOIN message has passed. The first case
indicates a successful join while the latter indicates failure.
Reception of a DDM data packet intended for this joiner prior to
reception of an ACK may or may not indicate a successful join,
depending on the security mechanism (if any) in use and whether or
not an ACK is required as part of this mechanism. Security-related
mechanisms are beyond the scope of this draft. This draft
Ji and Corson [Page 13]
Internet Draft Differential Destination Multicast July 12, 2000
essentially describes an insecure session. When a join process is
successfully completed on ACK reception, any activate join waiting
timer is canceled and no further JOIN messages are generated.
The ML kept at the source node needs to be refreshed from time to
time to maintain up-to-date membership information. Due to the
dynamic nature of wireless networks, node reachability may change
unpredictably. The source needs to be able to purge stale members.
In DDM member refreshing is source-initiated. Once every
MEMBERSHIP_REFRESH_PERIOD data packets, the source sets the POLL flag
in the next outgoing data packet. Upon receiving such data packet, a
multicast session member needs to unicast a JOIN message again to the
source to express its continued interest. If after
MAX_REFRESH_TIMEOUT such polling data packets have been sent and
there is still no JOIN message received from one member, the source
assumes that this member has left the multicast session. This member
is then removed from the ML and excluded from future forwarding
computations. JOIN "implosion" at the sender is not expected to be a
problem due to small expected group sizes and different hop distance
between members and the source. If necessary, random delay jitter
may be added to the transmission times of JOINs sent in response to
POLL packets to reduce congestive effects at the source.
This "polled" membership refreshment is used as a secondary mechanism
to detect an absent member. An explicit LEAVE message is defined as
the preferred way for a session member to leave the source's ML. It
is a unicast message sent from the leaving member to the session
source. When received by the source, this LEAVE message terminates
the member's membership. The member is removed from the ML and is
excluded from future forwarding computations. To increase
robustness, instead of sending just one message, MAX_LEAVE_RETRY
LEAVE messages may be unicast to the source when a node leaves the
session. After these transmissions, a member node removes any
information associated with the multicast session. The source may
also dismiss a receiver by removing it from the ML at any time if its
security mechanism suggests so.
4.4 Forwarding Processing
Most of the processing consists of set operations. The computation
complexity on each participating node is bounded by O(n log n), with
n being the number of members in the multicast session.
When a node receives a multicast DDM data packet from an upstream
neighbor k, it first tries to locate the "DDM Block" intended for
itself. Walking through the DDM Blocks in the DDM Data Header, the
receiving node matches the 1st node address used by each DDM Block
Ji and Corson [Page 14]
Internet Draft Differential Destination Multicast July 12, 2000
(the intended receiver) with its own. If it is indeed the intended
receiver of one of the DDM Blocks, the processing continues.
Otherwise, the data packet is dropped and the forwarding processing
stops. If the received data is unicast, this step is not necessary
because only the intended receiver will receive such data packet.
After finding the DDM block, the receiving node compares the Data
Sequence Number in the summary section of the DDM Data Header with
the local data sequence number cache for the same multicast session.
If this packet has been seen before, it is discarded and no further
processing is needed. If the packet is new, its data sequence number
is inserted into the cache. DDM also needs to see if itself is a
multicast destination. If so, a copy of the data packet is made and
the DDM Data Header is striped off from this data packet. The
restored data is re-injected into the network kernel of the node for
local delivery.
The receiving node extracts all multicast destination addresses for
the DDM Block from the header. The upstream neighbor is also
identified, either from the "Sender" field of the summary section or
the IP source of the packet depending on if the data packet is
received as D-class data packet. Then the receiving node accesses
the FS_k set for this upstream neighbor k. If no such set is found
and the received DDM Block is a R block, a new FS_k is create. The
newly created set is initialized to empty. The SEQ(FS)_k number is
initialized to be 1 lower than the DDM Block Sequence Number in the
received DDM Block. However, if the block is E or D-type, this means
that the FS_k set is out of synchronization with the Direction Set on
the upstream sender end. In this case, the receiving node sends a
RSYNC packet back to the sending upstream neighbor and the data
packet is dropped. In this RSYNC message, the "DDM Block Sequence
Number" field is set to the same sequence number as the received DDM
Block's. The "Forced Refreshing (FR)" flag is set to "forcing once"
unless the node is operating in "statefree" mode, which will be
described later in section 4.6.
Before a node proceeds further, it compares its SEQ(FS)_k value with
the "DDM Block Sequence Number" in the received DDM block. The
reason for this step is to detect destination set update losses.
Because of the differential approach, it is very important to quickly
detect any packet losses which contain destination list updates.
When a node sends out a DDM Block, it stamps the block with a DDM
Block Sequence Number. This sequence number is incremented by one
every time a node sends out an informative DDM Block. The sending of
E headers does not change the sequence number since there is no
change in the destination list. Still, an E header carries the
current sequence number so a receiving node may detect previous
losses.
Ji and Corson [Page 15]
Internet Draft Differential Destination Multicast July 12, 2000
If the packet "DDM Block Sequence Number" is at least one greater
than the SEQ(FS)_k and the DDM block is an E or at least two greater
and the DDM block is a D, the receiving node knows that at least one
packet was lost and the packet(s) contains destination list updates.
So the receiving node sends a RSYNC packet back to the sending
upstream neighbor, and the data packet is dropped. This check is
unnecessary for R blocks since they contain the entire multicast
destination list for this node to forward.
After verifying the DDM Block Sequence Number, the SEQ(FS)_k value is
updated to the DDM Block sequence number in the packet. If the
received data packet has an E header, the receiving node only needs
to forward one copy of the data packet to each downstream neighbor l
whose current DS_l is not empty.
If the data packet has a R block, the node replaces its FS_k by the
list L in the header.
FS_k = L
When a node receives a Di or Dd block, it updates the corresponding
FS_k according to the D header: removing the addresses in the L_d
from its FS_k then adding the addresses in the L_i into its FS_k set.
If the received block is a Dd block, the receiving node needs to look
one block beyond to see if the next block following the Dd is a Di
block for itself. If so, the L_i list in that D_i block needs to be
processed together.
FS_k = (FS_k - L_d) U L_i
After updating the FS_k, the receiving node updates the union FS.
Then it partitions the new overall FS set into DS'_l sets according
to the "next hops" l used by the unicast routes towards the
destinations in the FS. All destinations in the same DS'_l share a
common "next hop" l.
By comparing the contents of the new DS' sets and the existing DS
sets, the node assembles new DDM Blocks for the outgoing DDM Data
Header. If there is a DS'_l but there is no matching DS_l for a
particular "next hop" l, an R-type DDM Block is constructed for l.
The DDM Block Sequence Number for this DDM Block is set to 0.
Alternatively, if there is one DS_l set but there is no DS'_l, no DDM
Block is constructed.
For the case that there are both a DS'_l and a DS_l, the processing
checks if the DS_l's "Forced Refreshing" flag is set to either
"forcing once" or "forcing always". If so, a R block is constructed
which contains all destination addresses in the DS'_l. Otherwise the
Ji and Corson [Page 16]
Internet Draft Differential Destination Multicast July 12, 2000
contents of them need to be compared. If the DS'_l set is the same
as the DS_l set, an E block is used since there is no change.
Otherwise, R or D block(s) is constructed. By default D block(s) are
tried first. All destination addresses that are in the DS'_l (new
Direction Set) but not in the DS_l (old Direction Set) form the
incremental list L_i. All addresses that are in the DS_l but no
longer in the DS'_l form the decremental list L_d. Addresses that
are common in both sets appear in neither list. If the total length
of the L_i and L_d lists is not shorter than the destination list in
DS'_l, a R block is used instead to cut down number of addresses in
header. Otherwise, a Dd Block is constructed then followed by a Di
Block. Of course when either L_i or L_d list is empty, its
corresponding DDM Block is not needed. For D or R-type DDM Blocks,
the SEQ(DS)_l is incremented by one while it remains the same for E
blocks. The final SEQ(DS)_l is used as the DDM Block Sequence Number
in the constructed DDM Block.
R header: L = DS_l or
D header: L_i = DS_l - DS'_l
L_d = DS'_l - DS_l
After the DDM Block is ready it is packed into the header of the data
packet. The multicast destination list of the DS_l set are replaced
by the one of DS'_l set and kept in memory for the next forwarding
computation. After the construction of the outgoing DDM Block, the
"forced refreshing" flag of the DS_l set is reset to "no forcing" if
the current value if "forcing once".
If DDM header aggregation is not in use, the data packet can be
forwarded to the downstream neighbor using unicasting right away.
Otherwise, more DDM Blocks will be packed into the same DDM Data
Header until the number of DDM Blocks in the DDM Data Header exceeds
MAX_DDM_BLOCKS. The above DDM Block construction is repeated until
all DS' sets are processed. New DDM Blocks are inserted into the
packet header if the header size does not exceed the limit.
Otherwise, the filled data packet is sent out, and a new data packet
with the same payload is allocated. New DDM Blocks are inserted into
the header of this new data packet.
4.5 Forwarding Set Synchronization
When operating in soft-state mode, usually only the differences of
the multicast destination lists are included in data packet headers.
It is very important to keep the Direction Set on the upstream side
and the Forwarding Set on the downstream side synchronized. The DDM
algorithm uses a DDM Block Sequence Number to maintain
Ji and Corson [Page 17]
Internet Draft Differential Destination Multicast July 12, 2000
synchronization. The sequence number on the DS (upstream) side must
match with the sequence number of the FS (downstream) side.
This sequence number is carried inside each DDM Block and its
advertisement is data-driven. Only nodes which are not exchanging
data may remain out of synchronization for extended periods. If the
receiver detects missing sequence numbers, it knows that some data
messages containing informative DDM Blocks for it have been lost and
its Forwarding Set is out of synchronization with the Direction Set
on the upstream neighbor. It needs to notify its upstream neighbor
using a RSYNC message. When used for resynchronization purpose, this
message contains a flag telling the upstream neighbor to set the
"Forced Refreshing" flag for the Direction Set to "forcing once".
The message is unicast to the upstream neighbor.
On the upstream end, upon receiving a RSYNC message, it locates the
DS set used for the sender of this RSYNC message and sets the "forced
refresh" flag to what the message's FR flag says. When the upstream
neighbor is forwarding the next data packet, if it sees the "forced
refresh" flag is set for a DS set, a R Block is constructed. Since R
block contains the full list, upon reception the downstream neighbor
will have its FS set synchronized again.
4.6 Timers and Dual Modes of DDM
DDM is a dual-mode algorithm where each participating node can
operate in "stateless" mode or "soft-state" mode. Timers, the
"Forced Refresh" flag, and the TOL field in each DDM Data Header are
the mode control parameters.
There are timers associated with each set (both FS_k sets and DS_l
sets). When any of the timers expires, the corresponding set is
removed. Every time there is a packet received from neighbor k, the
timer associated with the FS_k is reset to expire in TOL seconds as
specified in the received DDM Data Header.
FS_k timer value = TOL
Every time a DS_l set is used for forwarding, the forwarding node
picks an expiration period for the timer associated with this DS_l.
Then in the outgoing packet, its TOL field is set to:
TOL = DS_l life timer value * R (R > 1)
This action helps ensuring that, over a given link, the timer for the
Direction Set on the upstream side expires before the timer for the
Forwarding Set on the downstream side. Otherwise if the DS set lives
longer than its downstream FS set, the upstream neighbor may use an E
Ji and Corson [Page 18]
Internet Draft Differential Destination Multicast July 12, 2000
or a D header and the downstream node will only transmit an unneeded
RSYNC packet. Although the timer setting scheme does not avoid this
from happening completely (packet loss may still cause the same
problem), it should sufficiently reduce the probability of this
undesired event. Also, by making the timer value for the DS sets a
local decision, nodes are given the opportunity to adapt the timer
values to their local environment. For example, if a node moves
rapidly relative to its surrounding nodes, it is reasonable to choose
a smaller timer value.
The preceding applies to "soft-state" operation. If "stateless"
forwarding is desired at a node, it needs to inform its upstream
neighbor about its decision. If the upstream neighbor is also
operating in "stateless" mode, there will be no need to do so since
all DDM Blocks coming from it are R-type. If the upstream neighbor
is in "soft-state" mode, when receiving an E or D header the
downstream "stateless" node needs to send back a RSYNC message with
the "force refreshing" flag set to "forcing always". After receiving
such RSYNC message the upstream neighbor only sends R-Blocks from the
next data packet onwards since the DS block corresponding to this
"stateless" downstream neighbor has a "forcing always" flag. In a
"stateless" node, all FS and DS set timers are set to zero so that
none of the sets are kept. Later on, if a "stateless" node ever
wants to switch back to "soft-state" again, it needs to send another
RSYNC message to its upstream neighbor to cause the latter to reset
its "force refreshing" flag to "no forcing".
Using a combination of RSYNC message, TOL, and "force refreshing"
flag, neighboring nodes can operate in different modes but still work
together.
4.6 Multicast Data Encapsulation
During the partition of the overall Forwarding Set, DDM needs to
query the unicast routing protocol for the next hop information. In
the case when there is no route, or the underlying unicast protocol
is on-demand, such next hop information may not be available
immediately. In this case DDM will encapsulate the multicast data
packet in a CTRL_DATA control message. This message is a unicast
message from this forwarding node to the multicast destination to
whom the next hop is unknown. This message is passed to the unicast
routing protocol for forwarding. During the forwarding of this
unicast packet, the underlying unicast routing protocol will
construct the route. This way, soon the next hop information will
become available for DDM. In the case such multicast destination is
unreachable, the data packet will eventually be dropped by the
unicast routing protocol.
Ji and Corson [Page 19]
Internet Draft Differential Destination Multicast July 12, 2000
When a node receives a valid CTRL_DATA message, it decapsulates the
original multicast data packet. Then it uses the information stored
in CTRL_DATA header to restore the D-class IP header for the data
packet. Finally, the restored multicast data packet is loop-back to
the IP kernel of the same node for local delivery.
5 Conclusion
This draft proposes a multicast routing protocol intended for use
with small multicast groups in ad hoc networks of any size. The
protocol is source-initiated and controlled, and uses in-band,
destination-encoded data packet headers to control a distributed
routing computation. The result is a simple, efficient, and robust
protocol suitable for small multicast groups. The protocol offers
the option of choosing between "stateless" and "soft-state" modes.
Simulation shows that DDM is efficient both in terms of bandwidth and
channel access. It is nearly ideal for multicasting to small groups
in networks that already have unicast routing support. Also DDM is
highly robust and flexible.
Ongoing work on DDM is focusing in 2 areas: (a) more simulation
studies to explore different modes and options of the DDM and (b) a
Linux multicasting daemon implementation to study DDM's performance
in real system.
6. ACKNOWLEDGMENTS
This work was performed under a grant from the Army Research Lab
(ARL) ATIRP program.
Ji and Corson [Page 20]
Internet Draft Differential Destination Multicast July 12, 2000
References
[1] J. J. Garcia-Luna-Aceves and E. Madruga, "A Multicast Routing Protocol
for Ad-Hoc Networks", Proceedings of IEEE INFOCOM'99, March, 1999.
[2] S. Lee, W. Su and M. Gerla, "On-Demand Multicast Routing Protocol
(ODMRP)", Internet Draft draft-ietf-manet-odmrp-02.txt, work in progress,
January, 2000.
[3] E. Royer and C. Perkins, "Multicast using Ad hoc On-Demand Distance
Vector Routing", Proceedings of ACM/IEEE MOBICOM '99, 1999.
[4] L. Ji and M. Corson, "Light-weight Adaptive Multicast", In Proceedings
of IEEE GLOBECOM '98, November, 1998.
[5] J. Moy, "Multicast Extensions to OSPF", RFC1584, March, 1994.
[6] A. Ballardie, "Core Based Trees (CBT version 2) Multicast Routing --
Protocol Specification", RFC2189, September, 1997.
[7] D. Estrin et al, "Protocol Independent Multicast-Sparse Mode (PIM-SM):
Protocol Specification", RFC2362, June, 1998.
[8] R. Boivie, "A New Multicast Scheme for Small Groups", IBM Research
Report RC21512(97046), June, 1999.
[9] D. Ooms and W. Livens, "Connectionless Multicast", Internet Draft
draft-ooms-cl-multicast-01.txt, October, 1999.
[10] D. Johnson and D. Maltz, "Dynamic Source Routing in Ad Hoc Wireless
Networks", Mobile Computing, 1996.
Author's Addresses
Lusheng Ji, M. Scott Corson
Institute for Systems Research
University of Maryland
College Park, MD 20742
(301) 405-6630
{lji,corson}@isr.umd.edu
Ji and Corson [Page 21]
