draft-ietf-manet-odmrp-01.txt   draft-ietf-manet-odmrp-02.txt 
IETF MANET Working Group Sung-Ju Lee IETF MANET Working Group Sung-Ju Lee
INTERNET-DRAFT William Su INTERNET-DRAFT William Su
Expiration: December 1999 Mario Gerla Expiration: July 2000 Mario Gerla
University of California, Los Angeles University of California, Los Angeles
June 1999 January 2000
On-Demand Multicast Routing Protocol (ODMRP) for Ad Hoc Networks On-Demand Multicast Routing Protocol (ODMRP) for Ad Hoc Networks
<draft-ietf-manet-odmrp-01.txt> <draft-ietf-manet-odmrp-02.txt>
Status of This Memo Status of This Memo
This document is an Internet-Draft and is in full conformance with This document is an Internet-Draft and is NOT offered in accordance
all provisions of Section 10 of RFC2026. This document is a with Section 10 of RFC2026, and the author does not provide the IETF
a submission to the Mobile Ad-hoc Networks (manet) Working Group with any rights other than to publish as an Internet-Draft. This
of the Internet Engineering Task Force (IETF). Comments should be document is a submission to the Mobile Ad-hoc Networks (manet)
submitted to the Working Group mailing list at 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. "manet@itd.nrl.navy.mil". Distribution of this memo is unlimited.
This document is an Internet-Draft. Internet-Drafts are working This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas, documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts. working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other documents months and may be updated, replaced, or obsoleted by other documents
at any time. It is inappropriate to use Internet-Drafts as at any time. It is inappropriate to use Internet-Drafts as
skipping to change at page 2, line 11 skipping to change at page 2, line 11
multicast group membership. ODMRP is well suited for ad hoc multicast group membership. ODMRP is well suited for ad hoc
wireless networks with mobile hosts where bandwidth is limited, wireless networks with mobile hosts where bandwidth is limited,
topology changes frequently and rapidly, and power is constrained. topology changes frequently and rapidly, and power is constrained.
Contents Contents
Status of This Memo 1 Status of This Memo 1
Abstract 1 Abstract 1
1. Introduction 3 1. Introduction 4
2. Terminology 4 2. Terminology 5
2.1. General Terms . . . . . . . . . . . . . . . . . . . . . . 4 2.1. General Terms . . . . . . . . . . . . . . . . . . . . . . 5
2.2. Specification Language . . . . . . . . . . . . . . . . . 4 2.2. Specification Language . . . . . . . . . . . . . . . . . 5
3. Protocol Overview 5 3. Protocol Overview 6
3.1. Group Establishment and Route Construction . . . . . . . 5 3.1. Multicast Route and Mesh Creation . . . . . . . . . . . . 6
3.1.1. Mesh Creation . . . . . . . . . . . . . . . . . . 5 3.2. Reliability . . . . . . . . . . . . . . . . . . . . . . . 8
3.1.2. Adapting the Refresh Interval via 3.3. Soft State . . . . . . . . . . . . . . . . . . . . . . . 10
Mobility Prediction . . . . . . . . . . . . . . . 7 3.4. Selection of Timer Values . . . . . . . . . . . . . . . . 10
3.1.3. Soft State . . . . . . . . . . . . . . . . . . . 7 3.5. Unicast Capability . . . . . . . . . . . . . . . . . . . 10
3.2. Contents of Tables . . . . . . . . . . . . . . . . . . . 8 3.6. Contents of Tables . . . . . . . . . . . . . . . . . . . 11
3.2.1. Routing Table . . . . . . . . . . . . . . . . . . 8 3.6.1. Routing Table . . . . . . . . . . . . . . . . . . 11
3.2.2. Forwarding Group Table . . . . . . . . . . . . . 8 3.6.2. Forwarding Group Table . . . . . . . . . . . . . 11
3.2.3. Message Cache . . . . . . . . . . . . . . . . . . 8 3.6.3. Message Cache . . . . . . . . . . . . . . . . . . 11
3.3. Unicast Routing Capability . . . . . . . . . . . . . . . 8 3.7. Mobility Prediction 12
3.7.1. Adapting the Refresh Interval via
Mobility Prediction . . . . . . . . . . . . . . . 12
3.7.2. Route Selection Criteria . . . . . . . . . . . . 14
3.7.3. Alternative Method of Prediction . . . . . . . . 14
4. Packet and Table Formats 9 4. Packet and Table Formats 15
4.1. Join Data Packet Header . . . . . . . . . . . . . . . . 9 4.1. Join Query Packet Header . . . . . . . . . . . . . . . 15
4.2. Join Table Packet . . . . . . . . . . . . . . . . . . . 11 4.2. Join Reply Packet . . . . . . . . . . . . . . . . . . . 17
5. Operation 13 5. Operation 19
5.1. Forwarding Group Setup . . . . . . . . . . . . . . . . . 13 5.1. Forwarding Group Setup . . . . . . . . . . . . . . . . . 19
5.1.1. Originating a Join Data . . . . . . . . . . . . . 13 5.1.1. Originating a Join Query . . . . . . . . . . . . 19
5.1.2. Processing a Join Data . . . . . . . . . . . . . 13 5.1.2. Processing a Join Query . . . . . . . . . . . . . 19
5.1.3. Processing a Join Data When GPS is Used . . . . . 14 5.1.3. Processing a Join Query When GPS is Used . . . . 20
5.1.4. Originating a Join Table . . . . . . . . . . . . 15 5.1.4. Originating a Join Reply . . . . . . . . . . . . 21
5.1.5. Processing a Join Table . . . . . . . . . . . . . 15 5.1.5. Processing a Join Reply . . . . . . . . . . . . . 21
5.1.6. Processing a Join Table When GPS is Used . . . . 16 5.1.6. Processing a Join Reply When GPS is Used . . . . 21
5.1.7. Passive Acknowledgments . . . . . . . . . . . . . 17 5.2. Handling a Multicast Data Packet . . . . . . . . . . . . 22
5.2. Handling a Multicast Data Packet . . . . . . . . . . . . 17
6. Protocol Applicability 18 6. Simulation and Implementation Status 23
6.1. Networking Context . . . . . . . . . . . . . . . . . . . . . 18
6.2. Protocol Characteristics and Mechanisms . . . . . . . . . . 18
Acknowledgments 20 7. Protocol Applicability 24
7.1. Networking Context . . . . . . . . . . . . . . . . . . . . . 24
7.2. Protocol Characteristics and Mechanisms . . . . . . . . . . 24
References 20 Acknowledgments 26
Chair's Address 21 References 26
Authors' Addresses 22 Chair's Address 29
Authors' Addresses 29
1. Introduction 1. Introduction
This document describes the On-Demand Multicast Routing Protocol This document describes the On-Demand Multicast Routing Protocol
(ODMRP) developed by the Wireless Adaptive Mobility (WAM) Lab [12] (ODMRP) [14][15] developed by the Wireless Adaptive Mobility (WAM)
at UCLA. ODMRP applies "on-demand" routing techniques to avoid Laboratory [20] at University of California, Los Angeles. ODMRP
channel overhead and improve scalability. It uses the concept of applies "on-demand" routing techniques to avoid channel overhead and
"forwarding group,"[3] a set of nodes responsible for forwarding improve scalability. It uses the concept of "forwarding group," [5]
multicast data, to build a forwarding mesh for each multicast group. a set of nodes responsible for forwarding multicast data, to build a
By maintaining and using a mesh instead of a tree, the drawbacks of forwarding mesh for each multicast group. By maintaining and using a
multicast trees in mobile wireless networks (e.g., intermittent mesh instead of a tree, the drawbacks of multicast trees in mobile
connectivity, traffic concentration, frequent tree reconfiguration, wireless networks (e.g., intermittent connectivity, traffic
non-shortest path in a shared tree, etc.) are avoided. A soft-state concentration, frequent tree reconfiguration, non-shortest path in a
approach is taken to maintain multicast group members. No explicit shared tree, etc.) are avoided. A soft-state approach is taken to
control message is required to leave the group. We believe the maintain multicast group members. No explicit control message is
reduction of channel/storage overhead and the relaxed connectivity required to leave the group. We believe the reduction of
make ODMRP more scalable for large networks and more stable for channel/storage overhead and the relaxed connectivity make ODMRP
mobile wireless networks. more attractive in mobile wireless networks.
The following properties of ODMRP highlight its advantages. The following properties of ODMRP highlight its advantages.
* Simplicity
* Low channel and storage overhead * Low channel and storage overhead
* Usage of stable routes * Usage of up-to-date shortest routes
* Reliable construction of routes and forwarding group
* Robustness to host mobility * Robustness to host mobility
* Maintenance and exploitation of multiple redundant paths * Maintenance and exploitation of multiple redundant paths
* Scalability to a large number of nodes
* Exploitation of the broadcast nature of wireless environments * Exploitation of the broadcast nature of wireless environments
* Adaptivity to node movement patterns * Unicast routing capability
* Reconstruction of routes in anticipation of topology changes
2. Terminology 2. Terminology
2.1. General Terms 2.1. General Terms
This section defines terminology used in ODMRP. This section defines terminology used in ODMRP.
node node
A device that implements IP. A device that implements IP.
skipping to change at page 4, line 28 skipping to change at page 5, line 28
forwarding group forwarding group
A group of nodes participating in multicast packet forwarding. A group of nodes participating in multicast packet forwarding.
multicast mesh multicast mesh
The topology defined by the link connection between forwarding The topology defined by the link connection between forwarding
group members. group members.
join data join query
The special data packet sent by multicast sources to establish The special data packet sent by multicast sources to establish
and update group memberships and routes. and update group memberships and routes.
join table join reply
The table broadcasted by each multicast receiver and forwarding The table broadcasted by each multicast receiver and forwarding
node to establish and update group membership and routes node to establish and update group membership and routes
2.2. Specification Language 2.2. Specification Language
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [1]. document are to be interpreted as described in RFC 2119 [4].
3. Protocol Overview 3. Protocol Overview
3.1. Group Establishment and Route Construction 3.1. Multicast Route and Mesh Creation
3.1.1. Mesh Creation
In ODMRP, group membership and multicast routes are established and In ODMRP, group membership and multicast routes are established and
updated by the source on demand. Similar to on-demand unicast updated by the source on demand. Similar to on-demand unicast
routing protocols, a request phase and a reply phase comprise the routing protocols, a request phase and a reply phase comprise the
protocol. When a multicast source has packets to send but no route protocol. When a multicast source has packets to send but no route
and group membership is known, it floods a control packet with data and group membership is known, it floods a member advertising packet
payload attached. This packet, called "Join Data" (format shown in with data payload piggybacked. This packet, called "Join Query"
Section 4.1) is periodically broadcasted to the entire network to (format shown in Section 4.1) is periodically broadcasted to the
refresh the membership information and update the routes. When a entire network to refresh the membership information and update the
node receives a Join Data packet, it stores the source ID and the routes. When a node receives a Join Query packet, it stores the
sequence number to its "Message Cache" to detect duplicates. The source address and the unique identifier of the packet to its
upstream node ID is inserted or updated as the next node for the "Message Cache" to detect duplicates. The upstream node address is
source node in its "Routing Table." If the Join Data packet is not inserted or updated as the next node for the source node in its
a duplicate and the Time-To-Live value is greater than zero, "Routing Table." If the Join Query packet is not a duplicate and
appropriate fields are updated and it is rebroadcasted (operation the Time-To-Live value is greater than zero, appropriate fields are
details are explained in Section 5.1.2). updated and it is rebroadcast (operation details are illustrated
in Section 5.1.2).
When a Join Data packet reaches the multicast receiver, it creates When a Join Query packet reaches the multicast receiver, it creates
and broadcasts a "Join Table" to its neighbors. When a node receives and broadcasts a "Join Reply" to its neighbors. When a node receives
a Join Table, it checks if the next node ID of one of the entries a Join Reply, it checks if the next node address of one of the
matches its own ID. If it does, the node realizes that it is on the entries matches its own address. If it does, the node realizes that
path to the source and thus is part of the forwarding group; it is on the path to the source and thus is part of the forwarding
it sets the FG_FLAG. It then broadcasts its own Join Table built group; it sets the FG_FLAG (Forwarding Group Flag). It then
upon matched entries. The next node ID field is filled in by broadcasts its own Join Reply built upon matched entries. The next
extracting the information from its routing table. This way, the node address field is filled in by extracting the information from
Join Table is propagated by each forward group member until it its routing table. This way, the Join Reply is propagated by each
reaches the multicast source via the selected path. This process forward group member until it reaches the multicast source via the
constructs (or updates) the routes from sources to receivers and selected path. This process constructs (or updates) the routes from
builds a mesh of nodes, the forwarding group. sources to receivers and builds a mesh of nodes, the forwarding
group.
+--+ +--+ +--+ +--+ +--+ +--+
|S1|-------|I1|-------|R1| |S1|-------|I1|-------|R1|
+--+\ +--+ /+--+ Join Table of Node R1 and Node I1 +--+\ +--+ /+--+ Join Replies of Node R1 and Node I1
\ / +----------------+ +----------------+ \ / +----------------+ +----------------+
\ / |Sender|Next Node| |Sender|Next Node| \ / |Sender|Next Node| |Sender|Next Node|
\ / |------+---------| |------+---------| \ / |------+---------| |------+---------|
\ / | S1 | I1 | | S1 | S1 | \ / | S1 | I1 | | S1 | S1 |
\ / |------+---------| +----------------+ \ / |------+---------| +----------------+
+--+ \+--+/ +--+ | S2 | I2 | +--+ \+--+/ +--+ | S2 | I2 |
|S2|-------|I2|-------|R2| +----------------+ |S2|-------|I2|-------|R2| +----------------+
+--+ +--+ +--+ +--+ +--+ +--+
Let us consider the above figure as an example of Join Table Let us consider the above figure as an example of Join Reply
forwarding process. Nodes S1 and S2 are multicast sources, and nodes forwarding process. Nodes S1 and S2 are multicast sources, and nodes
R1 and R2 are multicast receivers. Node R2 sends its Join Table to R1 and R2 are multicast receivers. Node R2 sends its Join Reply to
both S1 and S2 via I2, and R1 sends its packet to S1 via I1 and to both S1 and S2 via I2, and R1 sends its packet to S1 via I1 and to
S2 via I2. When receivers send their Join Tables to next hop nodes, S2 via I2. When receivers send their Join Replies to next hop nodes,
an intermediate node I1 sets the FG_FLAG and builds its own Join an intermediate node I1 sets the FG_FLAG and builds its own Join
Table since there is a next node ID entry in the Join Table received Reply since there is a next node ID entry in the Join Reply received
from R1 that matches its ID. Note that the Join Table build by I1 from R1 that matches its ID. Note that the Join Reply built by I1
has an entry for sender S1 but not for S2 because the next node ID has an entry for sender S1 but not for S2 because the next node
for S2 in the received Join table is not I1. In the meanwhile, node address for S2 in the received Join Reply is not I1. In the
I2 sets the FG_FLAG, constructs its own Join Table and sends it to meanwhile, node I2 sets the FG_FLAG, constructs its own Join Reply
its neighbors. Note that I2 broadcasts the join table only once even and sends it to its neighbors. Note that I2 broadcasts the Join
though it receives two Join Tables from the receivers because the Reply only once even though it receives two Join Replies from the
second table arrival carries no new source information. Channel receivers because the second table arrival carries no new source
overhead is thus reduced dramatically in cases where numerous information. Channel overhead is thus reduced dramatically in cases
multicast receivers share the same links to the source. where numerous multicast receivers share the same links to the
source.
After this group establishment and route construction process, a After this group establishment and route construction process, a
source can multicast packets to receivers via selected routes and source can multicast packets to receivers via selected routes and
forwarding groups. While outgoing data packets exist, the source forwarding groups. While outgoing data packets exist, the source
sends Join Data every REFRESH_INTERVAL. This Join Data and Join sends Join Query every REFRESH_INTERVAL. This Join Query and Join
Table propagation process refreshes forwarding group and routes. Reply propagation process refreshes forwarding group and routes.
When receiving the multicast data packet, a node forwards it only When receiving the multicast data packet, a node forwards it only
when it is not a duplicate and the setting of the FG_FLAG for the when it is not a duplicate and the setting of the FG_FLAG for the
multicast group has not expired. This procedure minimizes the multicast group has not expired. This procedure minimizes the
traffic overhead and prevents sending packets through stale routes. traffic overhead and prevents sending packets through stale routes.
3.1.2 Adapting the Refresh Interval via Mobility Prediction 3.2. Reliability
ODMRP requires periodic flooding of Join Data} to build and refresh The reliable transmission of Join Replies plays an important role
routes. Excessive flooding, however, is not desirable in ad hoc in establishing and refreshing multicast routes and forwarding
networks because of bandwidth constraints. Furthermore, flooding groups. Hence, if Join Replies are not properly delivered,
often causes congestion, contention, and collisions. Finding the effective multicast routing cannot be achieved by ODMRP. The IEEE
optimal flooding interval is critical in ODMRP performance. In 802.11 MAC (Medium Access Control) protocol [8], which is the
highly mobile networks where nodes are equipped with GPS [9] (e.g., emerging standard in wireless networks, performs reliable
tactical netwoks with tanks, ships, aircrafts, etc.), we can transmission by retransmitting the packet if no acknowledgment is
efficiently adapt the REFRESH_INTERVAL to mobility patterns and received. However, if the packet is broadcasted, no acknowledgments
speeds by utilizing the location and movement information. Note or retransmissions are sent. In ODMRP, the transmission of Join
that ODMRP can still operate efficiently in networks where no such Replies are often broadcasted to more than one upstream neighbors
information is available, but the protocol can be further improved since we are handling multiple sources (e.g., see the Join Reply
if those information can be utilized. from node R1 in the example of Section 3.1.). In such cases, the
hop-by-hop verification of Join Reply delivery and the
retransmission cannot be handled by the MAC layer. It must be done
indirectly by ODMRP. Another option for reliable delivery is to
subdivide the Join Reply into separate sub-tables, one for each
distinct next node. In the figure of Section 3.1. for example, the
Join Reply at node R1 is split into two Join Replies, one for
neighbor I1 and the other for neighbor I2. These Join Replies are
separately unicasted using a reliable MAC protocol such as IEEE
802.11 or MACAW [3]. Since the number of neighbors is generally
limited (typically, about six neighbors in the optimum in a
multihop network [12]), the scheme still scales well to large number
of sources. This option can actually be used as backup to the
passive acknowledgment option as discussed below.
We use the location and movement information to predict the duration We adopt a scheme that was used in [10]. When a node transmits a
of time routes will remain valid (the detail of the process is Join Reply packet to the immediate upstream node of the route, the
explained in 5.1.3). With the predicted time of route disconnection, immediate downstream node can hear the transmission if it is
Join Data are only flooded when route breaks of ongoing data within the transmitter's radio range. Hence, the packet is used as
sessions are imminent. an "passive acknowledgment." We can utilize this passive
acknowledgment to verify the delivery of a Join Reply. Note that
the source itself must send an active acknowledgment to the
previous hop since it does not have any next hop to send a Join
Reply to unless it is also a forwarding group node for other
sources.
A different route selection method is applied when we use the Considering the case in figure of Section 3.1. again, we note that
mobility prediction. The idea is inspired by the Associativity-Based once the nodes I1 and I2 receive the Join Reply from node R1, they
Routing (ABR) protocol [11] which chooses associatively stable will construct and forward their own Join Replies to next hops (in
routes. In our algorithm, instead of using the minimum delay path, this case, sources S1 and S2). In transmitting their Join Replies,
we can choose a route that is the most stable (i.e., the one that nodes I1 and I2 may overlap with each other. If I1 and I2} are
will remain connected for the longest duration of time). To select within receiving range, they will recover because of the carrier
a route, a multicast receiver must wait for an appropriate amount of sense feature in CSMA (Carrier Sense Multiple Access) [13]. However,
time after receiving the first Join Data so that all possible routes if they are out of range, they will be unaware of the "hidden
and their route qualities will be known. The receiver then chooses terminal" condition of node R1, which cannot hear the (overlapped)
the most stable route and broadcasts a Join Table. Route breaks will passive acknowledgments. Thus, a node may not hear the passive
occur less often and the number of Join Data propagation will reduce acknowledgments of its upstream neighbor because of conflicts due
because stable routes are used. to the hidden terminal problem. It will also not hear the passive
acknowledgment if the upstream neighbor has moved away. In either
case, when no acknowledgment is received within the timeout
interval, the node retransmits the message. Note that the node may
get acknowledgments from some, but not all upstream neighbors. As
an option, the retransmission could be carried out in unicast mode,
to selected neighbors, with reduced sub-tables. If packet delivery
cannot be verified after an appropriate number of retransmissions,
the node considers the route to be invalidated. At this point, the
most likely cause of route failure is the fact that a node on the
route has failed or has moved out of range. An alternate route must
be found "on the spot." The node thus broadcasts a message to its
neighbors specifying that the next hop to a set of sources cannot
be reached. Upon receiving this packet, each neighbor builds and
unicasts the Join Reply to its next hop if it has a route to the
multicast sources. If no route is known, it simply broadcasts the
packet specifying the next hop is not available. In both cases, the
node sets its FG_FLAG. In practical implementations, this
redundancy is sufficient to establish alternate paths until a more
efficient route is established during the next refresh phase. The
FG_FLAG setting of every neighbor may create excessive redundancy,
but most of these settings will expire because only necessary
forwarding group nodes will be refreshed in the next Join Reply
propagation phase.
3.1.3. Soft State 3.3. Soft State
In ODMRP, no explicit control packets need to be sent to leave the In ODMRP, no explicit control packets need to be sent to leave the
group. If a multicast source wants to leave the group, it simply group. If a multicast source wants to leave the group, it simply
stops sending any Join Data packets since it does not have any stops sending any Join Query packets since it does not have any
multicast data to send to the group. If a receiver no longer wants multicast data to send to the group. If a receiver no longer wants
to receive from a particular multicast group, it does not send the to receive from a particular multicast group, it does not send the
Join Table for that group. Nodes in the forwarding group are demoted Join Reply for that group. Nodes in the forwarding group are demoted
to non-forwarding nodes if not refreshed (no Join Tables received) to non-forwarding nodes if not refreshed (no Join Replies received)
before they timeout. before they timeout.
3.2. Contents of Tables 3.4. Selection of Timer Values
Timer values for route refresh interval and forwarding group
timeout interval can have impacts on ODMRP performance. The
selection of these soft state timers should be adaptive to network
environment (e.g., traffic type, traffic load, mobility pattern,
mobility speed, channel capacity, etc.). When small route refresh
interval values are used, fresh route and membership information
can be obtained frequently at the expense of producing more packets
and causing network congestion. On the other hand, when large route
refresh values are selected, even though less control traffic will
be generated, nodes may not know up-to-date route and multicast
membership. Thus in highly mobile networks, using large route
refresh interval values can yield poor protocol performance. The
forwarding group timeout interval should also be carefully
selected. In networks with heavy traffic load, small values should
be used so that unnecessary nodes can timeout quickly and not
create excessive redundancy. In situations with high mobility,
however, large values should be chosen so that more alternative
paths can be provided. It is important to note that the forwarding
group timeout value must be larger (e.g., 3 to 5 times) than the
value of route refresh interval.
3.5. Unicast Capability
One of the major strengths of ODMRP is its unicast routing
capability. Not only can ODMRP coexist with any unicast routing
protocol, it can also operate very efficiently as an unicast
routing protocol. Thus, a network equipped with ODMRP does not
require a separate unicast protocol. Other ad hoc multicast routing
protocols such as AMRoute [5], CAMP [7], RBM [6], and LAM [9]
must be run on top of a unicast routing protocol. CAMP, RBM, and
LAM in particular, only work with certain underlying unicast
protocols.
3.6. Contents of Tables
Nodes running ODMRP are required to maintain the following tables. Nodes running ODMRP are required to maintain the following tables.
These tables MAY be implemented in any format, but MUST include the These tables MAY be implemented in any format, but MUST include the
fields specified in this document. fields specified in this document.
3.2.1. Routing Table 3.6.1. Routing Table
A routing table is created on demand and is maintained by each node. A routing table is created on demand and is maintained by each node.
An entry is inserted or updated when a non-duplicate Join Data is An entry is inserted or updated when a non-duplicate Join Query is
received. The node stores the destination (i.e., the source of the received. The node stores the destination (i.e., the source of the
Join Data) and the next hop to the destination (i.e., the last node Join Query) and the next hop to the destination (i.e., the last
that propagated the Join Data). The routing table provides the next node that propagated the Join Query). The routing table provides
hop information when transmitting Join Tables. the next hop information when transmitting Join Replies.
3.2.2. Forwarding Group Table 3.6.2. Forwarding Group Table
When a node is a forwarding group node of the multicast group, it When a node is a forwarding group node of the multicast group, it
maintains the group information in the forwarding group table. The maintains the group information in the forwarding group table. The
multicast group ID and the time when the node was last refreshed are multicast group ID and the time when the node was last refreshed
recorded. are recorded.
3.2.3. Message Cache 3.6.3. Message Cache
The message cache is maintained by each node to detect duplicates. The message cache is maintained by each node to detect duplicates.
When a node receives a new Join Data or data, it stores the source When a node receives a new Join Query or data, it stores the source
address and the sequence number of the packet. Note that entries in address and the unique identifier of the packet. Note that entries
the message cache need not be maintained permanently. Schemes such in the message cache need not be maintained permanently. Schemes
as LRU (Least Recently Used) or FIFO (First In First Out) can be such as LRU (Least Recently Used) or FIFO (First In First Out) can
employed to expire and remove old entries and prevent the size of be employed to expire and remove old entries and prevent the size
the message cache to be extensive. of the message cache to be extensive.
3.3. Unicast Routing Capability 3.7. Mobility Prediction
One of the major strengths of ODMRP is its unicast routing 3.7.1 Adapting the Refresh Interval via Mobility Prediction
capability. Not only ODMRP can work with any unicast routing
protocol, it can function as both multicast and unicast. Thus, ODMRP ODMRP requires periodic flooding of Join Query to build and refresh
can run without any underlying unicast protocol. Other ad hoc routes. Excessive flooding, however, is not desirable in ad hoc
multicast routing protocols such as AMRoute [2], CAMP [5], RBM [4], networks because of bandwidth constraints. Furthermore, flooding
and LAM [7] must be run on top of a unicast routing protocol. CAMP, often causes congestion, contention, and collisions. Finding the
RBM, and LAM in particular, only work on top of certain underlying optimal flooding interval is critical in ODMRP performance. In
unicast protocols. highly mobile networks where nodes are equipped with GPS [11] (e.g.,
tactical networks with tanks, ships, aircrafts, etc.), we can
efficiently adapt the REFRESH_INTERVAL to mobility patterns and
speeds by utilizing the location and movement information. We use
the location and movement information to predict the duration
of time routes will remain valid. With the predicted time of route
disconnection, Join Queries are only flooded when route breaks of
ongoing data sessions are imminent. Note that ODMRP can still
operate efficiently in networks where no such information is
available, but the protocol can be further improved if those
information can be utilized.
In our prediction method, we assume a free space propagation model,
where the received signal strength solely depends on its distance
to the transmitter. We also assume that all nodes in the network
have their clock synchronized (e.g., by using the NTP (Network Time
Protocol) [16] or the GPS clock itself). Therefore, if the motion
parameters of two neighbors (e.g., speed, direction, radio
propagation range, etc.) are known, we can determine the duration
of time these two nodes will remain connected. Assume two nodes i
and j are within the transmission range r of each other. Let
(x_{i}, y_{i}) be the coordinate of node i and (x_{j}, y_{j}) be
that of node j. Also let v_{i} and v_{j} be the speeds, and
theta_{i} and theta_{j} (0 <= theta_{i}, theta_{j} < 2 * pi) be the
moving directions of nodes i and j, respectively. Then, the
duration of time that the link between two nodes will stay
connected, D_{t}, is given by:
-(a*b + c*d) + sqrt((a^{2} + c^{2})*r^{2} - (a*d - b*c)^{2})
D_{t} = ------------------------------------------------------------
a^{2} + c^{2}
where
a = v_{i}*cos(theta_{i}) - v_{j}*cos(theta_{j}),
b = x_{i} - x_{j},
c = v_{i}*sin(theta_{i}) - v_{j}*sin(theta_{j}), and
d = y_{i} - y_{j}.
Note that when v_{i} = v_{j} and theta_{i} = theta_{j}, D_{t} is
set to infinity without applying the above equation.
To utilize the information obtained from the prediction, extra
fields must be added into Join Query and Join Reply packets. When a
source sends Join Query, it appends its location, speed, and
direction. It sets the MIN_LET (Minimum Link Expiration Time) field
to the MAX_LET_VALUE since the source does not have any previous
hop node. The next hop neighbor, upon receiving a Join Query,
predicts the link expiration time between itself and the previous
hop using the above equation. The minimum between this value and
the MIN_LET indicated by the Join Query is included in the packet.
The rationale is that as soon as a single link on a path is
disconnected, the entire path is invalidated. The node also
overwrites the location and mobility information field written by
the previous node with its own information. When a multicast member
receives the Join Query, it calculates the predicted LET of the
last link of the path. The minimum between the last link expiration
time and the MIN_LET value specified in the Join Query is the RET
(Route Expiration Time). This RET value is enclosed in the Join
Reply and broadcasted. If a forwarding group node receives multiple
Join Replies with different RET values (i.e., lies in paths from
the same source to multiple receivers), it selects the minimum RET
among them and sends its own Join Reply with the chosen RET value
attached. When the source receives Join Replies, it selects the
minimum RET among all the Join Replies received. Then the source
can build new routes by flooding a Join Query before the minimum
RET approaches (i.e., route breaks).
In addition to the estimated RET value, other factors need to be
considered when choosing the refresh interval. If the node mobility
rate is high and the topology changes frequently, routes will
expire quickly and often. The source may propagate Join Query
excessively and this excessive flooding can cause collisions and
congestion, and clogs the network with control packets. Thus, the
MIN_REFRESH_INTERVAL should be enforced to avoid control message
overflow. On the other hand, if nodes are stationary or move slowly
and link connectivity remains unchanged for a long duration of time,
routes will hardly expire and the source will rarely send Join
Query. A few problems arise in this situation. First, if a node in
the route suddenly changes its movement direction or speed, the
predicted RET value becomes obsolete and routes will not be
reconstructed in time. Second, when a non-member node which is
located remotely to multicast members wants to join the group,
it cannot inform the new membership or receive data until a Join
Query is received. Hence, the MAX_REFRESH_INTERVAL should be set.
The selection of the MIN_REFRESH_INTERVAL and the
MAX_REFRESH_INTERVAL values should be adaptive to network
environments.
3.7.2. Route Selection Criteria
In ODMRP, a multicast receiver selects routes based on the minimum
delay (i.e., routes taken by the first Join Query received. A
different route selection method is applied when we use the
mobility prediction. The idea is inspired by the Associativity-Based
Routing (ABR) protocol [18] which chooses associatively stable
routes. In our algorithm, instead of using the minimum delay path,
we can choose a route that is the most stable (i.e., the one that
will remain connected for the longest duration of time). To select
a route, a multicast receiver must wait for an appropriate amount of
time after receiving the first Join Query so that all possible
routes and their route qualities will be known. The receiver then
chooses the most stable route and broadcasts a Join Reply. Route
breaks will occur less often and the number of Join Query
propagation will reduce because stable routes are used.
3.7.3. Alternative Method of Prediction
Since GPS may not work properly in certain situations (e.g.,
indoor, fading, etc.), we may not always be able to accurately
predict the link expiration time for a particular link. However,
there is an alternative method to predict the LET. This method is
based on a more realistic propagation model and has been proposed
in [1] and [17]. Basically, transmission power samples are measured
periodically from packets received from a mobile's neighbor. From
this information it is possible to compute the rate of change for a
particular neighbor's transmission power level. Therefore, the time
when the transmission power level will drop below the acceptable
value (i.e., hysteresis region) can be predicted. We plan to
investigate this option in our future work.
4. Packet and Table Formats 4. Packet and Table Formats
4.1. Join Data Packet Header 4.1. Join Query Packet Header
0 1 2 3 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 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Reserved | Time To Live | Hop Count | | Type | Reserved | Time To Live | Hop Count |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multicast Group IP Address | | Multicast Group IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Sequence Number | | Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
skipping to change at page 9, line 33 skipping to change at page 15, line 33
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Previous Hop Y Coordinate | | Previous Hop Y Coordinate |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Previous Hop Moving Speed | Previous Hop Moving Direction | | Previous Hop Moving Speed | Previous Hop Moving Direction |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Minimum Link Expiration Time | | Minimum Link Expiration Time |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type Type
01; ODMRP Join Data. 01; ODMRP Join Query.
Reserved Reserved
Sent as 0; ignored on reception. Sent as 0; ignored on reception.
Time To Live Time To Live
Number of hops this packet can traverse. Number of hops this packet can traverse.
Hop Count Hop Count
skipping to change at page 11, line 5 skipping to change at page 17, line 5
node's own instruments and sensors (e.g., campus, odometer, node's own instruments and sensors (e.g., campus, odometer,
speed sensors, etc.). This field is required only when network speed sensors, etc.). This field is required only when network
hosts are GPS equipped. hosts are GPS equipped.
Minimum Link Expiration Time (Optional) Minimum Link Expiration Time (Optional)
The minimum expiration time among the links taken by this The minimum expiration time among the links taken by this
packet so far. This field is required only when network hosts packet so far. This field is required only when network hosts
are GPS equipped. are GPS equipped.
4.2. Join Table Packet 4.2. Join Reply Packet
0 1 2 3 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 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Count |R|F| Reserved | | Type | Count |R|F| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multicast Group IP Address | | Multicast Group IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Previous Hop IP Address | | Previous Hop IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
skipping to change at page 11, line 38 skipping to change at page 17, line 38
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Sender IP Address [n] | | Sender IP Address [n] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Next Hop IP Address [n] | | Next Hop IP Address [n] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Route Expiration Time [n] | | Route Expiration Time [n] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type Type
02; ODMRP receiver Join Table. 02; ODMRP Join Reply.
Count Count
Number of (Sender IP Address, Next Hop IP Address) Number of (Sender IP Address, Next Hop IP Address)
combinations. combinations.
R R
Acknowledgment request flag. This flag is set when active Acknowledgment request flag. This flag is set when active
acknowledgment packet is requested. acknowledgment packet is requested.
skipping to change at page 13, line 9 skipping to change at page 19, line 9
Route Expiration Time [1..n] (Optional) Route Expiration Time [1..n] (Optional)
The minimum route expiration times of this multicast group. The minimum route expiration times of this multicast group.
This field is required only when network hosts are GPS equipped. This field is required only when network hosts are GPS equipped.
5. Operation 5. Operation
5.1. Forwarding Group Setup 5.1. Forwarding Group Setup
5.1.1. Originating a Join Data 5.1.1. Originating a Join Query
When a multicast source has data packets to send but no route is When a multicast source has data packets to send but no route is
known, it originates a "Join Data" packet. The Type field MUST be known, it originates a "Join Query" packet. The Type field MUST be
set to 01. TTL MAY be set to TIME_TO_LIVE_VALUE, but SHOULD be set to 01. TTL MAY be set to TIME_TO_LIVE_VALUE, but SHOULD be
adjusted based on network size and network diameter. The Sequence adjusted based on network size and network diameter. The Sequence
number MUST be large enough to prevent wraparound ambiguity, and the Number MUST be large enough to prevent wraparound ambiguity, and the
Hop Count is initially set to zero. The source puts its IP address Hop Count is initially set to zero. The source puts its IP address
in the Source IP Address and Last Hop IP Address field. It appends in the Source IP Address and Last Hop IP Address field. It appends
its location, speed, and direction into JOIN DATA. its location, speed, and direction into Join Query if nodes in the
network are equipped with GPS.
When location and movement information is utilized, it sets the When location and movement information is utilized, it sets the
MIN_LET (Link Expiration Time) field to the MAX_LET_VALUE since the MIN_LET (Link Expiration Time) field to the MAX_LET_VALUE since the
source does not have any previous hop node. When the source receives source does not have any previous hop node. When the source receives
Join Tables from multicast receivers, it selects the minimum RET Join Replies from multicast receivers, it selects the minimum RET
(Route Expiration Time) among all the Join Tables received. Then the (Route Expiration Time) among all the Join Replies received. Then the
source can build new routes by originating a Join Data before the source can build new routes by originating a Join Query before the
minimum RET approaches (i.e., route breaks of ongoing data sessions minimum RET approaches (i.e., route breaks of ongoing data sessions
are imminent). are imminent).
5.1.2. Processing a Join Data 5.1.2. Processing a Join Query
When a node receives a Join Data packet: When a node receives a Join Query packet:
1. Check if it is a duplicate by comparing the (Source IP Address, 1. Check if it is a duplicate by comparing the (Source IP Address,
Sequence Number) combination with the entries in message cache. Sequence Number) combination with the entries in the message
If duplicate, then discard the packet. DONE. cache. If a duplicate, then discard the packet. DONE.
2. If it is not a duplicate, insert an entry into message cache with 2. If it is not a duplicate, insert an entry into the message cache
the information of the received packet (i.e., sequence number and with the information of the received packet (i.e., sequence
source IP address) and insert/update the entry for routing table number and source IP address) and insert/update the entry for
(i.e., backward learning). routing table (i.e., backward learning).
3. If the node is a member of the multicast group, it originates a 3. If the node is a member of the multicast group, it originates a
Join Table packet with the RET value enclosed (see Section 5.1.4). Join Reply packet with the RET value enclosed (see Section 5.1.4).
4. Increase the Hop Count field by 1 and decrease the TTL field by 1. 4. Increase the Hop Count field by 1 and decrease the TTL field by 1.
5. If the TTL field value is less than or equal to 0, then discard 5. If the TTL field value is less than or equal to 0, then discard
the packet. DONE. the packet. DONE.
6. If the TTL field value is greater than 0, then set the node's IP 6. If the TTL field value is greater than 0, then set the node's IP
Address into Last Hop IP Address field and broadcast. DONE. Address into Last Hop IP Address field and broadcast. DONE.
5.1.3. Processing a Join Data When GPS is Used 5.1.3. Processing a Join Query When GPS is Used
When a node receives a Join Data packet: When a node receives a Join Query packet:
1. Check if it is a duplicate by comparing the (Source IP Address, 1. Check if it is a duplicate by comparing the (Source IP Address,
Sequence Number) combination with the entries in message cache. Sequence Number) combination with the entries in the message
If duplicate, then discard the packet. DONE. cache. If a duplicate, then discard the packet. DONE.
2. If it is not a duplicate, insert an entry into message cache with 2. If it is not a duplicate, insert an entry into the message cache
the information of the received packet (i.e., sequence number and with the information of the received packet (i.e., sequence
source IP address) and insert/update the entry for routing table number and source IP address) and insert/update the entry for
(i.e., backward learning). routing table (i.e., backward learning).
3. Predict the duration of time the link between the node and the 3. Predict the duration of time the link between the node and the
upstream node will remain connected using the following equation. upstream node will remain connected using the equation given in
Section 3.7.1.
Assume node i is the upstream node and node j is the current node.
Let (x_{i}, y_{i}) be the coordinate of node i and (x_{j}, y_{j})
be that of node j. Also let v_{i} and v_{j} be the speeds, and
theta_{i} and theta_{j} be the moving directions of nodes i and j,
respectively. The information of node i (the previous hop node)
can be obtained from the Join Data and the current node's
location and mobility information can be provided by the GPS. The
duration of time that the link between two nodes will stay
connected, D_{t}, is given by:
-(a*b + c*d) + sqrt((a^{2} + c^{2})*r^{2} - (a*d - b*c)^{2})
D_{t} = ------------------------------------------------------------
a^{2} + c^{2}
where
a = v_{i}*cos(theta_{i}) - v_{j}*cos(theta_{j}),
b = x_{i} - x_{j},
c = v_{i}*sin(theta_{i}) - v_{j}*sin(theta_{j}), and
d = y_{i} - y_{j}.
Note that when v_{i} = v_{j} and theta_{i} = theta_{j}, D_{t} is
set to infinity without applying the above equation.
The minimum between this D_{t} value and the indicated value in The minimum between the newly obtained D_{t} value and the
MIN_LET field of the Join Data is included in the packet. The indicated value in MIN_LET field of the Join Query is included in
rationale is that as soon as a single link on the path is the packet. The rationale is that as soon as a single link on the
disconnected, the entire path is invalidated. The node also path is disconnected, the entire path is invalidated. The node
overwrites the location and mobility information field written also overwrites the location and mobility information field
by the previous node with its own information. written by the previous node with its own information.
4. If the node is a member of the multicast group, it calculates the 4. If the node is a member of the multicast group, it calculates the
predicted LET of the last link of the path. The minimum between predicted LET of the last link of the path. The minimum between
the last link expiration time and the MIN_LET value specified in the last link expiration time and the MIN_LET value specified in
the Join Data is the RET (Route Expiration Time). the Join Query is the RET (Route Expiration Time).
To select a route, a multicast receiver must wait for an To select a route, a multicast receiver must wait for an
appropriate amount of time after receiving the first Join Data appropriate amount of time after receiving the first Join Query
so that all possible routes and their RET will be known. The so that all possible routes and their RET will be known. The
receiver then chooses the most stable route (i.e., the route with receiver then chooses the most stable route (i.e., the route with
the largest RET) and originates a Join Table packet with the RET the largest RET) and originates a Join Reply packet with the RET
value enclosed (see Section 5.1.3.). value enclosed (see Section 5.1.3.).
5. Increase the Hop Count field by 1 and decrease the TTL field by 1. 5. Increase the Hop Count field by 1 and decrease the TTL field by 1.
6. If the TTL field value is less than or equal to 0, then discard 6. If the TTL field value is less than or equal to 0, then discard
the packet. DONE. the packet. DONE.
7. If the TTL field value is greater than 0, then set the node's IP 7. If the TTL field value is greater than 0, then set the node's IP
Address into Last Hop IP Address field and broadcast. DONE. Address into Last Hop IP Address field and broadcast. DONE.
5.1.4. Originating a Join Table 5.1.4. Originating a Join Reply
A multicast receiver transmits a "Join Table" packet after selecting A multicast receiver transmits a "Join Reply" packet after selecting
the multicast route. Each sender IP address and next hop IP address the multicast route. Each sender IP address and next hop IP address
of a multicast group are contained in the Join Table packet. The of a multicast group are contained in the Join Reply packet. The
route expiration time is also included if the network hosts operate route expiration time is also included if the network hosts operate
with GPS. with GPS.
5.1.5. Processing a Join Table 5.1.5. Processing a Join Reply
When a Join Table is received: When a Join Reply is received:
1. The node looks up the Next Hop IP Address field of the received 1. The node looks up the Next Hop IP Address field of the received
Join Table entries. If no entries match the node's IP Address, do Join Reply entries. If no entries match the node's IP Address, do
nothing. DONE. nothing. DONE.
2. If one or more entries coincide with the node's IP Address, set 2. If one or more entries coincide with the node's IP Address, set
the FG_FLAG and build its own Join Table. The next hop IP address the FG_FLAG and build its own Join Reply. The next hop IP address
can be obtained from the routing table. can be obtained from the routing table.
3. Broadcast the Join Table packet to the neighbor nodes. DONE. 3. Broadcast the Join Reply packet to the neighbor nodes. DONE.
5.1.6. Processing a Join Table When GPS is Used 5.1.6. Processing a Join Reply When GPS is Used
When a Join Table is received: When a Join Reply is received:
1. The node looks up the Next Hop IP Address field of the received 1. The node looks up the Next Hop IP Address field of the received
Join Table entries. If no entries match the node's IP Address, do Join Reply entries. If no entries match the node's IP Address, do
nothing. DONE. nothing. DONE.
2. If one or more entries coincide with the node's IP Address, set 2. If one or more entries coincide with the node's IP Address, set
the FG_FLAG and build its own Join Table. If multiple Join Tables the FG_FLAG and build its own Join Reply. If multiple Join Replies
with different RET values are received (i.e., the node lies in with different RET values are received (i.e., the node lies in
paths from the same source to multiple receivers), it selects the paths from the same source to multiple receivers), it selects the
minimum RET among them and attaches the chosen RET value. Next minimum RET among them and attaches the chosen RET value. Next
hop IP address can be obtained from the routing table. hop IP address can be obtained from the routing table.
3. Broadcast the Join Table packet to the neighbor nodes. 3. Broadcast the Join Reply packet to the neighbor nodes.
4. If the node is a source, it selects the minimum RET among all the 4. If the node is a source, it selects the minimum RET among all the
Join Tables received. Then the source can build new routes by Join Replies received. Then the source can build new routes by
flooding a Join Data before the minimum RET approaches (i.e., flooding a Join Query before the minimum RET approaches (i.e.,
route breaks of ongoing data sessions are imminent). route breaks of ongoing data sessions are imminent).
In addition to the estimated RET value, other factors need to be 5.2. Handling a Multicast Data Packet
considered when choosing the refresh interval of Join Data. If
the node mobility rate is high and the topology changes
frequently, routes will expire quickly and often. The source may
propagate Join Requests excessively and this excessive flooding
can cause collisions, congestion, and clogs the network with
control packets. Thus, the MIN_REFRESH_INTERVAL should be
enforced to avoid control message overflow. On the other hand, if
nodes are stationary or move slowly and link connectivity remains
unchanged for a long duration of time, routes will hardly expire
and the source will rarely send Join Data. A few problems arise
in this situation. First, if a node in the route suddenly changes
its movement direction or speed, the predicted RET value becomes
obsolete and routes will not be reconstructed. Second, when a
non-member node which is located remotely to multicast members
wants to join the group, it cannot inform the new membership or
receive data until a Join Data is received. Hence, the
MAX_REFRESH_INTERVAL should be set. The selection of the
MIN_REFRESH_INTERVAL and the MAX_REFRESH_INTERVAL should be
adaptive to network situations (e.g., traffic type, traffic load,
mobility pattern, channel capacity, etc.).
5.1.7. Passive Acknowledgments Multicast sources send the data whenever they have packets to send.
Nodes relay data packets only if the packet is not a duplicate and
the setting of FG_FLAG for the multicast group has not expired.
The reliable transmission of Join Tables plays an important role 6. Simulation and Implementation Status
in establishing and refreshing multicast routes and forwarding
groups. Hence, if Join Tables are not properly delivered,
effective multicast routing cannot be achieved by ODMRP. The
IEEE 802.11 MAC protocol [6], which is the standard in wireless
networks, performs reliable transmission by retransmitting the
packet if no acknowledgment is received. However, if the packet
is broadcasted, the acknowledgments and retransmissions are not
sent. In ODMRP, the transmission of Join Tables are mostly
broadcasted. Thus, the verification of Join Table delivery and
the retransmissions must be done by the ODMRP layer.
We adopt a scheme that was used in [8]. When a node transmits a ODMRP has been implemented in both simulation and real ad hoc
Join Table packet to the immediate upstream node of the route, network testbed. For simulation, the protocols is implemented
the immediate downstream node can hear the transmission if it is within the GloMoSim library [19], which is written in PARSEC[1].
within the transmitter's radio range. Hence, the packet is used As for the real system implementation, ODMRP is developed on Linux
as an "passive acknowledgment." We can utilize this passive kernel version 2.0.36, the kernel version provided by the Red Hat
acknowledgments to verify the delivery of Join Tables. Multicast Linux version 5.2. All tools and software packages that are used
sources must send active acknowledgments to the previous hops in our development originate from software bundle incorporated
since they do not have any next hops to send Join Tables to within the Red Hat Linux version 5.2 operating system package with
unless they are forwarding group nodes. When no acknowledgment is the singular exception of Lucent WaveLan IEEE 802.11 device driver.
received within the timeout interval, the node retransmits the
message. If packet delivery cannot be verified after an
appropriate number of retransmissions, the node considers the
route to be invalidated. The node then broadcasts a message to
its neighbors specifying that the next hop to the source cannot
be reached. Upon receiving this packet, the neighboring node
builds and unicasts the Join Table to its next hop if it has a
route to the multicast source. If no route is known, it simply
rebroadcasts the packet specifying the next hop is not available.
In both cases, the node sets its FG_FLAG. The FG_FLAG setting of
every neighbors may create excessive redundancy, but most of
these settings will expire because only necessary forwarding
group nodes will be refreshed in the next Join Table propagation
phase.
5.2. Handling a Multicast Data Packet The papers presenting our simulation results and working wireless
testbed implementation can be downloaded from the following
website:
Multicast sources send the Data whenever they have packets to send. http://www.cs.ucla.edu/NRL/wireless
Nodes relay data packets only if the packet is not a duplicate and
the setting of FG_FLAG for the multicast group has not expired.
6. Protocol Applicability 7. Protocol Applicability
6.1. Networking Context 7.1. Networking Context
ODMRP is best suited for mobile ad hoc wireless networks. ODMRP is best suited for mobile ad hoc wireless networks.
6.2. Protocol Characteristics and Mechanisms 7.2. Protocol Characteristics and Mechanisms
* Does the protocol provide support for unidirectional links? (if so, * Does the protocol provide support for unidirectional links? (if so,
how?) how?)
- No. We assume bidirectional links. - No. We assume bidirectional links.
* Does the protocol require the use of tunneling? (if so, how?) * Does the protocol require the use of tunneling? (if so, how?)
- No. - No.
* Does the protocol require using some form of source routing? (if * Does the protocol require using some form of source routing? (if
so, how?) so, how?)
- No. - No.
* Does the protocol require the use of periodic messaging? (if so, * Does the protocol require the use of periodic messaging? (if so,
how?) how?)
- No. - Yes, but only when multicast sources have data packets to send.
* Does the protocol require the use of reliable or sequenced packet * Does the protocol require the use of reliable or sequenced packet
delivery? (if so, how?) delivery? (if so, how?)
- No. - No.
* Does the protocol provide support for routing through a multi- * Does the protocol provide support for routing through a multi-
technology routing fabric? (if so, how?) technology routing fabric? (if so, how?)
- No. - No.
skipping to change at page 20, line 8 skipping to change at page 26, line 8
- This document assumed an arbitrary single channel link-layer - This document assumed an arbitrary single channel link-layer
protocol. The protocol can work with any MAC and link-layer protocol. The protocol can work with any MAC and link-layer
technology. It can also support multi-channel link-layer technology. It can also support multi-channel link-layer
technology (e.g., separate channels for data, control packets, technology (e.g., separate channels for data, control packets,
etc.). etc.).
Acknowledgments Acknowledgments
Authors thank Ching-Chuan Chiang and Guangyu Pei for their initial Authors thank Ching-Chuan Chiang and Guangyu Pei for their initial
contributions. contributions. We also send our gratitude to Sang Ho Bae who
implemented ODMRP in a real ad hoc network testbed.
References References
[1] Scott Bradner. Key words for use in RFCs to Indicate [1] P. Agrawal, D.K. Anvekar, and B. Narendran. Optimal
Prioritization of Handovers in Mobile Cellular Networks. In
Proceedings of IEEE PIMRC'94, The Hague, Netherlands, Sep. 1994,
pp. 1393-1398.
[2] R. Bagrodia, R. Meyer, M. Takai, Y. Chen, X. Zeng, J. Martin,
and H.Y. Song. PARSEC: A Parallel Simulation Environment for
Complex Systems. IEEE Computer, vol. 31, no. 10, Oct. 1998,
pp.77-85.
[3] V. Bharghavan, A. Demers, S. Shenker, and L. Zhang. MACAW: A
Media Access Protocol for Wireless LANs. In Proceedings of ACM
SIGCOMM'94, London, UK, Sep. 1994, pp. 212-225.
[4] S. Bradner. Key words for use in RFCs to Indicate
Requirement Levels. RFC 2119, March 1997. Requirement Levels. RFC 2119, March 1997.
[2] E. Bommaiah, M. Liu, A. McAuley, and R. Talpade. AMRoute: [5] E. Bommaiah, M. Liu, A. McAuley, and R. Talpade. AMRoute:
Adhoc Multicast Routing Protocol. Internet Draft, Adhoc Multicast Routing Protocol. Internet Draft,
draft-talpade-manet-amroute-00.txt, Aug. 1998. Work in progress. draft-talpade-manet-amroute-00.txt, Aug. 1998. Work in progress.
[3] Ching-Chuan Chiang, Mario Gerla, and Lixia Zhang. Forwarding [5] C.-C. Chiang, M. Gerla, and L. Zhang. Forwarding Group
Group Multicast Protocol (FGMP) for Multihop, Mobile Wireless Multicast Protocol (FGMP) for Multihop, Mobile Wireless Networks.
Networks. ACM/Baltzer Cluster Computing, vol. 1, no. 2, 1998. ACM/Baltzer Cluster Computing, vol. 1, no. 2, 1998.
[4] M.S. Corson and S.G. Batsell. A Reservation-Based Multicast [6] M.S. Corson and S.G. Batsell. A Reservation-Based Multicast
(RBM) Routing Protocol for Mobile Networks: Initial Route (RBM) Routing Protocol for Mobile Networks: Initial Route
Construction Phase. ACM/Baltzer Wireless Networks, vol. 1, Construction Phase. ACM/Baltzer Wireless Networks, vol. 1,
no. 4, Dec. 1999, pp. 427-450. no. 4, Dec. 1999, pp. 427-450.
[5] J.J. Garcia-Luna-Aceves and E.L. Madruga. A Multicast Routing [7] J.J. Garcia-Luna-Aceves and E.L. Madruga. A Multicast Routing
Protocol for Ad-Hoc Networks. In Proceedings of IEEE Protocol for Ad-Hoc Networks. In Proceedings of IEEE
INFOCOM'99, New York, NY, Mar. 1999, pp. 784-792. INFOCOM'99, New York, NY, Mar. 1999, pp. 784-792.
[6] IEEE Computer Society LAN MAN Standards Committee. Wireless [8] IEEE Computer Society LAN MAN Standards Committee. Wireless
LAN Medium Access Protocol (MAC) and Physical Layer (PHY) LAN Medium Access Protocol (MAC) and Physical Layer (PHY)
Specification. IEEE std 802.11-1997. The Institute of Electrical Specification. IEEE std 802.11-1997. The Institute of Electrical
and Electronics Engineers, New York, NY, 1997. and Electronics Engineers, New York, NY, 1997.
[7] L. Ji and M.S. Corson. A Lightweight Adaptive Multicast [9] L. Ji and M.S. Corson. A Lightweight Adaptive Multicast
Algorithm. In Proceedings of IEEE GLOBECOM'98, Sydney, Algorithm. In Proceedings of IEEE GLOBECOM'98, Sydney,
Australia, Nov. 1998, pp. 1036-1042. Australia, Nov. 1998, pp. 1036-1042.
[8] J. Jubin and J.D. Tornow. The DARPA Packet Radio Network [10] J. Jubin and J.D. Tornow. The DARPA Packet Radio Network
Protocols. Proceedings of the IEEE, vol. 75, no. 1, Jan. 1987, Protocols. Proceedings of the IEEE, vol. 75, no. 1, Jan. 1987,
pp. 21-32. pp. 21-32.
[9] E.D. Kaplan (Editor). Understanding the GPS: Principles and [11] E.D. Kaplan (Editor). Understanding the GPS: Principles and
Applications, Artech House, Boston, MA, Feb. 1996. Applications, Artech House, Boston, MA, Feb. 1996.
[10] S.-J. Lee, M. Gerla, and C.-C. Chiang. On-Demand Multicast [12] L. Kleinrock and J. Silvester. Optimum Transmission Radii for
Packet Radio Networks or Why Six is a Magic Number. In
Proceedings of National Telecommunications Conference,
Birmingham, AL, Dec. 1978, pp. 4.3.2-4.3.5.
[13] L. Kleinrock and F.A. Tobagi. Packet Switching in Radio
Channels: Part I - Carrier Sense Multiple-Access Modes and Their
Throughput-Delay Characteristics. IEEE Transactions on
Communications, vol. COM-23, no. 12, Dec. 1975, pp. 1400-1416.
[14] S.-J. Lee, M. Gerla, and C.-C. Chiang. On-Demand Multicast
Routing Protocol. In Proceedings of IEEE WCNC'99, New Orleans, Routing Protocol. In Proceedings of IEEE WCNC'99, New Orleans,
LA, Sep. 1999 (to appear). LA, Sep. 1999, pp. 1298-1302.
[11] C.-K. Toh. Associativity-Based Routing for Ad-Hoc Mobile [15] S.-J. Lee, W. Su, and M. Gerla. Ad hoc Wireless Multicast with
Mobility Prediction. In Proceedings of IEEE ICCCN'99, Boston,
MA, Oct. 1999, pp. 4-9.
[16] D.L. Mills. Internet Time Synchronization: the Network Time
Protocol. IEEE Transactions on Communications, vol. 39, no. 10,
Oct. 1991, pp. 1482-1493.
[17] B. Narendran, P. Agrawal, and D.K. Anvekar. Minimizing
Cellular Handover Failures Without Channel Utilization Loss.
In Proceedings of IEEE GLOBECOM'94, San Francisco, CA,
Dec. 1994, pp. 1679-1685.
[18] C.-K. Toh. Associativity-Based Routing for Ad-Hoc Mobile
Networks. Wireless Personal Communications Journal, Special Networks. Wireless Personal Communications Journal, Special
Issue on Mobile Networking and Computing Systems, Kluwer Issue on Mobile Networking and Computing Systems, Kluwer
Academic Publishers, vol. 4, no. 2, Mar. 1997, pp. 103-139. Academic Publishers, vol. 4, no. 2, Mar. 1997, pp. 103-139.
[12] UCLA Wireless Adaptive Mobility (WAM) Laboratory. [19] UCLA Parallel Computing Laboratory and Wireless Adaptive Mobility
Laboratory. GloMoSim: A Scalable Simulation Environment for
Wireless and Wired Network Systems.
http://pcl.cs.ucla.edu/projects/domains/glomosim.html
[20] UCLA Wireless Adaptive Mobility (WAM) Laboratory.
http://www.cs.ucla.edu/NRL/wireless http://www.cs.ucla.edu/NRL/wireless
Chair's Address Chair's Address
The Working Group can be contacted via its current chairs: The Working Group can be contacted via its current chairs:
M. Scott Corson M. Scott Corson
Institute for Systems Research Institute for Systems Research
University of Maryland University of Maryland
College Park, MD 20742 College Park, MD 20742
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/