IETF MANET Working Group                                    Mario Gerla                                    Sung-Ju Lee
INTERNET-DRAFT                                              Guangyu Pei                                               William Su
Expiration: May December 1999                                        Sung-Ju Lee                                   Mario Gerla
                                  University of California, Los Angeles
                                                     Ching-Chuan Chiang
                                    Chung-Cheng Institute of Technology
                                                          November 1998
                                                              June 1999

   On-Demand Multicast Routing Protocol (ODMRP) for Ad-Hoc Ad Hoc Networks

                  <draft-ietf-manet-odmrp-00.txt>

                  <draft-ietf-manet-odmrp-01.txt>

Status of This Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026. This document is a
   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.

   This document is an Internet-Draft.  Internet-Drafts are working
   documents of the Internet Engineering Task Force (IETF), its areas,
   and its working groups.  Note that other groups may also distribute
   working documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six
   months and may be updated, replaced, or obsoleted by other documents
   at any time.  It is inappropriate to use Internet-Drafts as
   reference material or to cite them other than as "work in progress."

   To view the entire

   The list of current Internet-Drafts, please check
   the "1id-abstracts.txt" listing contained in the Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe),
   munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or
   ftp.isi.edu (US West Coast). can be accessed at
   http://www.ietf.org/shadow.html.

Abstract

   On-Demand Multicast Routing Protocol (ODMRP) is a multicast routing
   protocol designed for ad-hoc ad hoc networks with mobile hosts. ODMRP is
   a mesh-based, rather than a conventional tree-based, multicast
   scheme and uses a Forwarding Group forwarding group concept (only a subset of nodes
   forwards the multicast packets via scoped flooding). It applies
   on-demand procedures to dynamically set up build routes and maintain
   multicast group membership. ODMRP is well suited for ad-hoc ad hoc
   wireless networks with mobile hosts where bandwidth is limited,
   topology changes frequently and rapidly, and power is constrained.

                                Contents

Status of This Memo                                                   1

Abstract                                                              1

 1. Introduction                                                      3

 2. Terminology                                                       4
     2.1. General Terms . . . . . . . . . . . . . . . . . . . . . .   4
     2.2. Specification Language  . . . . . . . . . . . . . . . . .   5   4

 3. Protocol Overview                                                 6                                                 5
     3.1. Group Establishment and Route Setup . Construction  . . . . . . . . . .   6   5
           3.1.1. Mesh Creation . . . . . . . . . . . . . . . . . .   6   5
           3.1.2. Joining Adapting the Group . Refresh Interval via
                  Mobility Prediction . . . . . . . . . . . . . . .   7
           3.1.3. Leaving the Group . . . . . . . . . . . . . . . .   8
           3.1.4. Timers  . Soft State  . . . . . . . . . . . . . . . . . . . .   8   7
     3.2. Contents of Tables  . . . . . . . . . . . . . . . . . . .   9   8
           3.2.1. Member Routing Table . . . . . . . . . . . . . . . . . .   9   8
           3.2.2. Routing Forwarding Group Table  . . . . . . . . . . . . . . . . . .   9   8
           3.2.3. Message Cache . . . . . . . . . . . . . . . . . .   9   8
     3.3. Relationship with Unicast Routing Protocols Capability  . . . . . . .  10 . . . . . . . .   8

 4. Packet and Table Formats                                         11                                          9
     4.1. Join Request Data Packet Header  . . . . . . . . . . . . . . . . . .   11    9
     4.2. Join Table Packet  . . . . . . . . . . . . . . . . . . .   12   11

 5. Operation                                                        14                                                        13
     5.1. Forwarding Group Setup  . . . . . . . . . . . . . . . . .  14  13
           5.1.1. Originating a Join Request Data . . . . . . . . . . .  14 . .  13
           5.1.2. Processing a Join Request Data  . . . . . . . . . . . .  14 .  13
           5.1.3. Processing a Join Data When GPS is Used . . . . .  14
           5.1.4. Originating a Join Table  . . . . . . . . . . . .  15
           5.1.4.
           5.1.5. Processing a Join Table . . . . . . . . . . . . .  15
           5.1.6. Processing a Join Table When GPS is Used  . . . .  16
           5.1.7. Passive Acknowledgments . . . . . . . . . . . . .  17
     5.2. Handling a Multicast Data Packet Handling  . . . . . . . . . . . . .  15  17

 6. Configuration Parameters                                         16

 7. Protocol Applicability                                           17
  7.1.                                           18
  6.1. Networking Context . . . . . . . . . . . . . . . . . . . . .  17
  7.2.  18
  6.2. Protocol Characteristics and Mechanisms  . . . . . . . . . .  17  18

Acknowledgments                                                      20

References                                                           19                                                           20

Chair's Address                                                      20                                                      21

Authors' Addresses                                                   20                                                   22

1. Introduction

   This document describes the On-Demand Multicast Routing Protocol
   (ODMRP) developed by the Wireless Adaptive Mobility (WAM) Lab [11] [12]
   at UCLA. ODMRP applies "on-demand" routing techniques to avoid
   channel overhead and increase improve scalability. It uses the concept of
   "Forwarding Group,"
   "forwarding group,"[3] a set of nodes which is responsible for forwarding
   multicast data, to build a forwarding mesh for each multicast group.
   By establishing maintaining and using a mesh instead of a mesh, tree, the drawbacks of
   multicast trees in mobile wireless networks (e.g., intermittent
   connectivity, traffic concentration, frequent tree reconfiguration,
   non-shortest path in a shared tree, etc.) are avoided. The forwarding group
   infrastructure reduces storage overhead and can handle a much
   looser connectivity among A soft-state
   approach is taken to maintain multicast group members. The No explicit
   control message is required to leave the group. We believe the
   reduction of channel/storage overhead and the relaxed connectivity
   make ODMRP more scalable for large networks and more stable for
   mobile wireless networks.

   The following properties of ODMRP highlight its advantages
   as well as limitations. advantages.

   *   Low channel and storage overhead

   *   Usage of up-to-date and shortest stable routes

   *   Robustness to host mobility

   *   Maintenance and exploitation of multiple, multiple redundant paths

   *   Scalability to a large number of nodes

   *   Exploitation of the broadcast nature of wireless environments

   *   Independence from unicast routing protocols

   *   Ease of implementation

   *   Redundant forwarding due   Adaptivity to mesh configuration node movement patterns

   *   Growth of transmitting table size when the number   Reconstruction of group
       members increases

   The Forwarding Group Multicast Protocol (FGMP) was first introduced routes in [4] using a conventional routing structure (i.e., DSDV [8]). An
   extension anticipation of FGMP by incorporating on-demand scheme was proposed in
   [3]. ODMRP improves upon its predecessors by exploiting sender
   advertisement scheme which is more efficient than receiver
   advertisement scheme in a typical multicast environment where more
   receivers are present than multicast senders. Moreover, the sender
   advertisement fits better with unicast on-demand routing protocols. topology changes

2. Terminology

2.1. General Terms

   This section defines terminology used in ODMRP that is not already
   defined in [7]. ODMRP.

   node

      A device that implements IP.

   neighbor

      Nodes that are within the radio transmission range.

   forwarding group

       A group of nodes participating in multicast packet forwarding.

   multicast mesh

       The topology defined by the link connection between forwarding
       group members.

   join request data

       The special data packet sent by multicast sources to establish/update establish
       and update group memberships and routes.

   join table

       The table broadcasted by each multicast receiver and forwarding
       node to establish/update establish and update group memberships membership and routes

   member table

       The table maintained by multicast receivers containing
       information of multicast sources for each multicast group it is
       associated with.

   routing table

      Table maintained by each node containing route information
      (e.g., next hop node) of existing active routes.

2.2. Specification Language

   The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119 [1].

3. Protocol Overview

3.1. Group Establishment and Route Setup Construction

3.1.1. Mesh Creation

   In ODMRP, group membership and multicast routes are setup established and
   updated by the source on demand. While Similar to on-demand unicast
   routing protocols, a request phase and a reply phase comprise the
   protocol. When a multicast source has packets to send, send but no route
   and group membership is known, it periodically floods a member advertising
   packet. control packet with data
   payload attached. This packet, called a "Join Request" packet Data" (format will
   be shown in
   Section 4.1.), 4.1) is broadcasted periodically as long as broadcasted to the source has packets entire network to send. This periodic transmission refreshes
   refresh the membership information and updates the route in update the face of
   node movements. routes. When a
   node receives a Join Request Data packet, it stores multicast group ID, the source ID, ID and the
   sequence number to its "Message Cache" to detect duplicates. Previous The
   upstream node ID is stored inserted or updated as
   well the next node for a use which will be described later. the
   source node in its "Routing Table." If the Join Request Data packet is not
   a duplicate and the hop count does not exceed the Time-To-Live value, value is greater than zero,
   appropriate fields are updated and it is relayed. rebroadcasted (operation
   details are explained in Section 5.1.2).

   When the a Join Request Data packet reaches a multicast receiver, the
   receiving node creates or updates the source entry in its Member
   Table, whose format will be shown in Section 3.2.1. Expired entries
   are deleted from the member table. A multicast receiver also sends
   periodic control packets. Namely, from its "Member Table," receiver, it builds creates
   and broadcasts a "Join Table" and sends it to its neighbors. Section 4.2 will show
   the format of the Join Table. When a node receives
   a Join Table, it checks if the next node ID of one of the entries
   matches its own ID. If it does, the node realizes that it is on the
   path to the source and thus is part of the forwarding group;
   it sets the
   FORWARDING_GROUP_FLAG. FG_FLAG. It then broadcasts its own Join Table built
   upon matched entries. The next node ID field is filled in by
   extracting the information from its Member Cache of received Join
   Request packets. Namely, the next node ID is set to the previous
   node ID field of the Join Request that matches multicast group ID
   and sender ID of the Join Table just received. routing table. This way, the
   Join Table is propagated by each forward group member until it
   reaches the multicast source via the shortest delay selected path. This process sets up
   constructs (or updates) the route routes from source sources to each receiver receivers and
   builds a mesh of nodes, the forwarding group.

   +--+       +--+       +--+
   |S1|-------|I1|-------|R1|
   +--+\      +--+      /+--+  Join Table of Node R1 and Node I1
        \              /        +----------------+  +----------------+
         \            /         |Sender|Next Node|  |Sender|Next Node|
          \          /          |------+---------|  |------+---------|
           \        /           |  S1  |    I1   |  |  S1  |    S1   |
            \      /            |------+---------|  +----------------+
   +--+      \+--+/      +--+   |  S2  |    I2   |
   |S2|-------|I2|-------|R2|   +----------------+
   +--+       +--+       +--+

   Let us consider the above figure as an example of Join Table
   forwarding process. Nodes S1 and S2 are multicast sources, and nodes
   R1 and R2 are multicast receivers. Node R2 sends its Join Table 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,
   an intermediate node I1 sets the FORWARDING_GROUP_FLAG FG_FLAG and builds its own Join
   Table since there is a next node ID entry in the
   received Join Table received
   from R1 that matches its ID. Note that the Join Table build by I1
   has an entry for sender S1 but not for S2 because the next node ID
   for S2 in the
   join table received from R1 Join table is not I1. In the meanwhile, node
   I2 sets the FORWARDING_GROUP_FLAG, FG_FLAG, constructs its own Join Table and sends it to
   its neighbors. Note that I2 broadcasts the join table only once even
   though it receives two Join Tables from the
   receivers. This is receivers because the
   second table arrival carries no new source information. Channel
   overhead is thus reduced dramatically in cases where numerous
   multicast receivers share the same links to the source.

   After this group establishment and route setup construction process, a multicast
   source can transmit multicast packets to receivers via selected routes and
   forwarding groups. The periodic control packets are sent as long as While outgoing data packets to send are still present. exist, the source
   sends Join Data every REFRESH_INTERVAL. This Join Data and Join
   Table propagation process refreshes forwarding group and routes.
   When receiving the multicast data packet, a node forwards it only
   when it is not a duplicate and the setting of FORWARDING_GROUP_FLAG the FG_FLAG for the
   multicast group has not expired. This procedure minimizes the
   traffic overhead and prevents sending packets through stale routes.

3.1.2. Joining the Group

   If a node wants to join a particular multicast group as a source,
   it simply sends

3.1.2 Adapting the Refresh Interval via Mobility Prediction

   ODMRP requires periodic flooding of Join Request packet when it has data packets Data} to
   send. Thereafter, this packet build and refresh
   routes. Excessive flooding, however, is periodically sent as long as not desirable in ad hoc
   networks because of bandwidth constraints. Furthermore, flooding
   often causes congestion, contention, and collisions. Finding the
   node has data to multicast.

   If a node wants to join a particular multicast group as a receiver,
   it needs to send Join Table to its neighbors periodically as well as
   every time its Member Table
   optimal flooding interval is modified/updated.

3.1.3. Leaving critical in ODMRP performance. In
   highly mobile networks where nodes are equipped with GPS [9] (e.g.,
   tactical netwoks with tanks, ships, aircrafts, etc.), we can
   efficiently adapt the Group

   No explicit control packet needs REFRESH_INTERVAL to mobility patterns and
   speeds by utilizing the location and movement information. Note
   that ODMRP can still operate efficiently in networks where no such
   information is available, but the protocol can be sent further improved
   if those information can be utilized.

   We use the location and movement information to leave predict the group. duration
   of time routes will remain valid (the detail of the process is
   explained in 5.1.3). With the predicted time of route disconnection,
   Join Data are only flooded when route breaks of ongoing data
   sessions are imminent.

   A different route selection method is applied when we use the
   mobility prediction. The idea is inspired by the Associativity-Based
   Routing (ABR) protocol [11] 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 Data so that all possible routes
   and their route qualities will be known. The receiver then chooses
   the most stable route and broadcasts a Join Table. Route breaks will
   occur less often and the number of Join Data propagation will reduce
   because stable routes are used.

3.1.3. Soft State

   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
   stops sending any Join Request packet Data packets since it doesn't does not have any
   multicast data to send to the group. If a receiver no longer wants
   to receive from a particular multicast group, it removes the corresponding entries from its Member Table
   and does not forward send the
   Join Table for that group.

3.1.4. Timers

    ODMRP uses a soft state approach for maintaining routes and
    multicast/forwarding group members. The refresh and timeout
    intervals used in ODMRP are defined as follows:

    RTE_TIMEOUT

       Timeout interval for Routing Table entries (RTE).

    MEM_REFRESH

       Refresh period of transmitting Join Request by a source when it
       has data packets to send.

    MEM_TIMEOUT

       Timeout interval of Member Table entries.

    JT_REFRESH

       Refresh period of sending Join Tables when there are entries Nodes in
       Member Table.

    FG_TIMEOUT

       Timeout interval of FORWARDING_GROUP_FLAG by each the forwarding group members.

    Sender advertising packets (Join Requests) are issued by source
    members every MEM_REFRESH interval when there are data packets demoted
   to
    send; entries in the Member Table which have non-forwarding nodes if not been refreshed
    (did not receive (no Join Request Tables received)
   before MEM_TIMEOUT) are removed.
    Entries in routing table are deleted if the routes are not used in
    RTE_TIMEOUT period. Join they timeout.

3.2. Contents of Tables

   Nodes running ODMRP are issued every JT_REFRESH when
    valid entries exist in the Member Table. Any update of the member
    table triggers the transmission of a Join Table as well. If
    forwarding nodes are not refreshed (by receiving Join Tables)
    within FG_TIMEOUT, they are demoted to non-forwarding nodes. These
    parameters MUST be set to proper values in order to adapt to a
    rapidly changing topology.

3.2. Contents of Tables

   Nodes running ODMRP are required to maintain required to maintain the following tables.
   These tables MAY be implemented in any format, but MUST include the
   fields specified in this document.

3.2.1. Member Table

   Member table needs to be maintained by multicast receivers. For
   each multicast group they are participating, they should store
   multicast source IP address and the timestamp value to detect the
   expired source. If no Join Request is received from a source in the
   Member Table within MEM_TIMEOUT, it is removed from the Member
   Table.

3.2.2. Routing Table

   A routing table is created on demand and is maintained by each node.
   There
   An entry is no specific routing table format required by ODMRP.
   However, inserted or updated when a non-duplicate Join Data is
   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
   that propagated the Join Data). The routing table MUST include provides the next
   hop address for
   each destination maintained information when transmitting Join Tables.

3.2.2. Forwarding Group Table

   When a node is a forwarding group node of the multicast group, it
   maintains the group information in the routing forwarding group table. The
   multicast group ID and the time when the node was last refreshed are
   recorded.

3.2.3. Message Cache

   Message Cache

   The message cache is maintained by each node to detect duplicates and to
   provide next hop information of routes. duplicates.
   When a node receives a new Join Request, Data or data, it MUST insert stores the following information source
   address and the sequence number of the packet. Note that entries in
   the message cache need not be maintained permanently. Schemes such
   as LRU (Least Recently Used) or FIFO (First In First Out) can be
   employed to expire and remove old entries and prevent the
   Message Cache:

   * Multicast Group ID

   * Source Address

   * Sequence Number

   * Previous Hop Address size of
   the message cache to be extensive.

3.3. Relationship with Unicast Routing Protocols Capability

   One of the major strengths of ODMRP is its unicast routing
   capability. Not only ODMRP can coexist work with any unicast routing protocol since
   protocol, it finds
   its own routes independently. From the point of view of scalability can function as both multicast and mobility support, it makes most sense to use unicast. Thus, ODMRP in
   conjunction with on-demand
   can run without any underlying unicast protocol. Other ad hoc
   multicast routing protocols such as
   DSR AMRoute [2], ZRP CAMP [5], TORA [6], AODV [9], RBM [4],
   and ABR [10]. If, LAM [7] must be run on the other
   hand, top of a conventional table driven unicast routing protocol is used,
   then, a conventional, tree based multicast protocol may be adequate. protocol. CAMP,
   RBM, and LAM in particular, only work on top of certain underlying
   unicast protocols.

4. Packet and Table Formats

4.1. Join Request Data Packet Header

     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  |      Type     |   Reserved    |  Time To Live |   Hop Count   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                  Multicast Group IP Address                   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                       Sequence Number                         |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                      Source IP Address                        |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                   Previous Hop IP Address                     |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    Ver

        ODMRP version number.
    |                  Previous Hop X Coordinate                    |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                  Previous Hop Y Coordinate                    |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |   Previous Hop Moving Speed   | Previous Hop Moving Direction |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                 Minimum Link Expiration Time                  |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Type

        01; ODMRP source Join Request. Data.

   Reserved

        Sent as 0; ignored on reception.

   Time To Live

        Maximum number

        Number of hops this packet can traverse.

   Hop Count

        The number of hops traveled so far by this packet.

   Multicast Group IP Address

        The IP address of the multicast group.

   Sequence Number

        The sequence number assigned by the source to uniquely
        identify the packet.

   Source IP Address

        The IP address of the node originating the packet.

   Previous Hop IP Address

        The IP address of the last node that has processed this packet.

   Previous Hop X Coordinate (Optional)

        The x-coordinate of the last node that has processed this
        packet. The information can be obtained from the GPS. This
        field is required only when network hosts are GPS equipped.

   Previous Hop Y Coordinate (Optional)

        The y-coordinate of the last node that has processed this
        packet. The information can be obtained from the GPS. This
        field is required only when network hosts are GPS equipped..

   Previous Hop Moving Speed (Optional)

        The mobility speed of the last node that has processed this
        packet. The information can be obtained from the GPS or the
        node's own instruments and sensors (e.g., campus, odometer,
        speed sensors, etc.). This field is required only when network
        hosts are GPS equipped.

   Previous Hop Moving Direction (Optional)

        The moving direction of the last node that has processed this
        packet. The information can be obtained from the GPS or the
        node's own instruments and sensors (e.g., campus, odometer,
        speed sensors, etc.). This field is required only when network
        hosts are GPS equipped.

   Minimum Link Expiration Time (Optional)

        The minimum expiration time among the links taken by this
        packet so far. This field is required only when network hosts
        are GPS equipped.

4.2. Join Table 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
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |  Ver  |      Type     |    Count      |      |R|F|     Reserved              |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                  Multicast Group IP Address                   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                   Previous Hop IP Address                     |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                        Sequence Number                        |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                    Sender IP Address [1]                      |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                   Next Hop IP Address [1]                     |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                  Route Expiration Time [1]                    |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                               :                               |
    |                               :                               |
    |                               :                               |
    |                               :                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                    Sender IP Address [n]                      |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                   Next Hop IP Address [n]                     |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    Ver

        ODMRP version number.
    |                  Route Expiration Time [n]                    |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Type

        02; ODMRP receiver Join Table.

   Count

        Number of (Sender IP Address, Next Hop IP Address)
        combinations.

   R

        Acknowledgment request flag. This flag is set when active
        acknowledgment packet is requested.

   F

        Forwarding group flag. This flag is set when the packet is
        transmitted by a forwarding group node.

   Reserved

        Sent as 0; ignored on reception.

   Multicast Group IP address

        The IP address of the multicast group.

   Previous Hop IP Address

        The IP address of the last node that has processed this packet.

   Sequence Number

        The sequence number assigned by the previous hop node to
        uniquely identify the packet.

   Sender IP Address [1..n]

        The IP addresses of the sources of this multicast group.

   Next Hop IP Address [1..n]

        The IP addresses of next nodes that this packet is target to.

   Route Expiration Time [1..n] (Optional)

        The minimum route expiration times of this multicast group.
        This field is required only when network hosts are GPS equipped.

5. Operation

5.1. Forwarding Group Setup

5.1.1. Originating a Join Request Data

   When a multicast source has data packets to send, send but no route is
   known, it periodically originates a "Join Request" packets every MEM_REFRESH interval. Data" packet. The Type field MUST 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
   number MUST be large enough to prevent wraparound ambiguity, and the
   Hop Count is initially set to zero. The source puts its IP address
   in the Source IP Address and Last Hop IP Address field. Note that Join Request packet It appends
   its location, speed, and direction into JOIN DATA.

   When location and movement information is not sent when a utilized, it sets 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
   Join Tables from multicast packets to send. receivers, it selects the minimum RET
   (Route Expiration Time) among all the Join Tables received. Then the
   source can build new routes by originating a Join Data before the
   minimum RET approaches (i.e., route breaks of ongoing data sessions
   are imminent).

5.1.2. Processing a Join Request Data

   When a node receives a Join Request Data packet:

   1. Check if it is a duplicate by comparing the (Source IP Address,
      Sequence Number) combination with the  entries in Message Cache. message cache.
      If duplicate, then discard the packet. DONE.

   2. If it is not a duplicate, insert an entry into Message Cache message cache with
      the information of the received packet (i.e., Multicast
       Group IP Address, Sequence Number, Source IP Address, sequence number and
       Previous Hop
      source IP Address). address) and insert/update the entry for routing table
      (i.e., backward learning).

   3. If the node is a receiver member of the multicast group, then
       insert/update the information into the Member Table and
       originate it  originates a
      Join Table packet with the RET value enclosed (see Section 5.1.3.). 5.1.4).

   4. Increase the Hop Count field by 1 and decrease the TTL field by 1.

   5. If the Hop Count TTL field value is less than or equal to or larger than TTL, 0, then discard
      the packet. DONE.

   6. If the Hop Count TTL field value is less greater than TTL, 0, then set the node's IP
      Address into Last Hop IP Address field and broadcast. DONE.

5.1.3. Originating Processing a Join Table

    A multicast receiver broadcasts Data When GPS is Used

   When a node receives a "Join Table" packet every
    JT_REFRESH as long as there are any entries in its Member Table.
    The transmission of Join Table is also triggered by the update Data packet:

   1. Check if it is a duplicate by comparing the (Source IP Address,
      Sequence Number) combination with the  entries in message cache.
      If duplicate, then discard the packet. DONE.

   2. If it is not a duplicate, insert an entry into message cache with
      the information of the received packet (i.e., sequence number and
      source IP address) and insert/update the entry for routing table
      (i.e., backward learning).

   3. Predict the duration of time the link between the node and the
      upstream node will remain connected using the following equation.

      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
      MIN_LET field of the Join Data is included in the packet. The
      rationale is that as soon as a single link on the 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.

   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
      the last link expiration time and the MIN_LET value specified in
      the Join Data is the RET (Route Expiration Time).

      To select a route, a multicast receiver must wait for an
      appropriate amount of time after receiving the first Join Data
      so that all possible routes and their RET will be known. The
      receiver then chooses the most stable route (i.e., the route with
      the largest RET) and originates a Join Table packet with the RET
      value enclosed (see Section 5.1.3.).

   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
      the packet. DONE.

   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.

5.1.4. Originating a Join Table

   A multicast receiver transmits a "Join Table" packet after selecting
   the multicast route. Each sender IP address and next hop IP address
   of a multicast group are contained in the Join Table packet. The
   route expiration time is also included if the network hosts operate
   with GPS.

5.1.5. Processing a Join Table

   When a Join Table is 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
      nothing. DONE.

   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
       can be obtained from the routing table.

   3. Broadcast the Join Table packet to the neighbor nodes. DONE.

5.1.6. Processing a Join Table When GPS is Used

   When a Join Table is 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
      nothing. DONE.

   2. If one or more entries coincide with the node's IP Address, set
      the FG_FLAG and build its Member own Join Table. Each Sender If multiple Join Tables
      with different RET values are received (i.e., the node lies in
      paths from the same source to multiple receivers), it selects the
      minimum RET among them and attaches the chosen RET value. Next
      hop IP Address address can be obtained from the routing table.

   3. Broadcast the Join Table packet to the neighbor nodes.

   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
      flooding a Join Data before the minimum RET approaches (i.e.,
      route breaks of ongoing data sessions are imminent).

      In addition to the estimated RET value, other factors need to be
      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

      The reliable transmission of Join Tables plays an important role
      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 Next Hop IP Address
    pairs retransmissions are not
      sent. In ODMRP, the transmission of a multicast group Join Tables are contained in mostly
      broadcasted. Thus, the verification of Join Table packet.
    Next Hop IP Address information can be obtained from delivery and
      the Message
    Cache entries(Last Hop IP Address field of retransmissions must be done by the Join Request
    packet).

5.1.4. Processing ODMRP layer.

      We adopt a Join Table scheme that was used in [8]. When a node transmits a
      Join Table is received:

    1. The packet to the immediate upstream node looks up of the Next Hop IP Address field route,
      the immediate downstream node can hear the transmission if it is
      within the transmitter's radio range. Hence, the packet is used
      as an "passive acknowledgment." We can utilize this passive
      acknowledgments to verify the delivery of Join Tables. Multicast
      sources must send active acknowledgments to the received previous hops
      since they do not have any next hops to send Join Table entries. If Tables to
      unless they are forwarding group nodes. When no entries match acknowledgment is
      received within the node's IP Address,
       do nothing. DONE.

    2. timeout interval, the node retransmits the
      message. If one or more entries coincide with packet delivery cannot be verified after an
      appropriate number of retransmissions, the node's IP Address, set node considers the FORWARDING_GROUP_FLAG and build
      route to be invalidated. The node then broadcasts a message to
      its own Join Table. Next Hop
       IP Address information can neighbors specifying that the next hop to the source cannot
      be obtained from reached. Upon receiving this packet, the Join Cache
       entries (Last Hop IP Address field of neighboring node
      builds and unicasts the Join Request packet).

    3. Broadcast 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 packet. propagation
      phase.

5.2. Handling a Multicast Data Packet Handling

   Multicast sources broadcast send the Data whenever they have packets to send.
   Nodes relay data packets only if the packet is not a duplicate and
   the FORWARDING_GROUP_FLAG setting of FG_FLAG for the multicast group has not expired.

6. Configuration Parameters

   This section specifies default values associated with ODMRP
   operation. Note that some of the values SHOULD be adjusted to nodes'
   mobility speed and network size.

   FG_TIMEOUT                               480    milliseconds

   JT_REFRESH                               160    milliseconds

   MEM_REFRESH                              400    milliseconds

   MEM_TIMEOUT                              960    milliseconds

   RTE_TIMEOUT                              960    milliseconds

   RT_DISCV_TIMEOUT                          30    seconds

   TIME_TO_LIVE_VALUE                        32    hops

7. Protocol Applicability

7.1.

6.1. Networking Context

   ODMRP is best suited for mobile ad hoc wireless networks.

7.2.

6.2. Protocol Characteristics and Mechanisms

   * Does the protocol provide support for unidirectional links? (if so,
   how?)

      - No. We assume bidirectional links.

   * Does the protocol require the use of tunneling? (if so, how?)

      - No.

   * Does the protocol require using some form of source routing? (if
   so, how?)

      - No.

   * Does the protocol require the use of periodic messaging? (if so,
   how?)

      - Yes. The periodic messages are sent by multicast sources as
        long as there exist multicast packets to send. Multicast
        receivers also send periodic messages while there are multicast
        source entries in the Member Table. No.

   * Does the protocol require the use of reliable or sequenced packet
   delivery? (if so, how?)

      - No.

   * Does the protocol provide support for routing through a multi-
   technology routing fabric? (if so, how?)

      - No.

   * Does the protocol provide support for multiple hosts per router?
   (if so, how?)

      - No. In this document, we assume each mobile host is combined
        with a router, sharing the same IP address. It is possible,
        however, to extend the protocol to handle multiple hosts per
        router.

   * Does the protocol support the IP addressing architecture? (if so,
   how?)

      - Yes. The message contains host IP address as its identification.

   * Does the protocol require link or neighbor status sensing (if so,
   how?)

      - No.

   * Does the protocol have dependence on a central entity? (if so,
   how?)

      - No.

   * Does the protocol function reactively? (if so, how?)

      - Yes. For example, the source creates and maintains routes and
        multicast group membership only when it has data packets to
        send.

   * Does the protocol function proactively? (if so, how?)

      - No.

   * Does the protocol provide loop-free routing? (if so, how?)

      - Yes. By using the Message Cache, duplicate packets are detected
        and packets can only go through the loop-free route.

   * Does the protocol provide for sleep period operation? (if so, how?)

      - No. TBD. The work is in progress.

   * Does the protocol provide some form of security? (if so, how?)

      - TBD. The work is in progress.

   * Does the protocol provide support for utilizing multi-channel,
   link-layer technologies? (if so, how?)

      - This document assumed an arbitrary single channel link-layer
        protocol. The protocol can work with any MAC and link-layer
        technology. It can also support multi-channel link-layer
        technology (e.g., separate channels for data, control packets,
        etc.).

Acknowledgments

   Authors thank Ching-Chuan Chiang and Guangyu Pei for their initial
   contributions.

References

   [1] Scott Bradner.  Key words for use in RFCs to Indicate
       Requirement Levels.  RFC 2119, March 1997.

   [2] Josh Broch, David B. Johnson, and David E. Bommaiah, M. Liu, A. Maltz.  The Dynamic
        Source McAuley, and R. Talpade.   AMRoute:
       Adhoc Multicast Routing Protocol for Mobile Ad Hoc Networks.
        Internet-Draft, draft-ietf-manet-dsr-00.txt, March Protocol.   Internet Draft,
       draft-talpade-manet-amroute-00.txt, Aug. 1998. Work in progress.

   [3] Ching-Chuan Chiang and Mario Gerla.  On-Demand Multicast in
        Mobile Wireless Networks.  In proceedings of IEEE ICNP'98,
        Austin, TX, October 1998. pp. 262-270.

    [4] Ching-Chuan Chiang, Mario Gerla, and Lixia Zhang.  Forwarding
       Group Multicast Protocol (FGMP) for Multihop, Mobile Wireless
       Networks.  ACM/Baltzer Cluster Computing, vol. 1, no. 2, 1998.

   [4] M.S. Corson and S.G. Batsell.   A Reservation-Based Multicast
       (RBM) Routing Protocol for Mobile Networks: Initial Route
       Construction Phase.   ACM/Baltzer Wireless Networks, vol. 1,
       no. 4, Dec. 1999, pp. 427-450.

   [5] Zygmunt J. Haas J.J. Garcia-Luna-Aceves and Marc R. Pearlman.  The Zone E.L. Madruga.   A Multicast Routing
       Protocol (ZRP) for Ad Hoc Ad-Hoc Networks. Internet-Draft,
        draft-ietf-manet-zone-zrp-01.txt, August 1998. Work in
        progress.   In Proceedings of IEEE
       INFOCOM'99, New York, NY, Mar. 1999, pp. 784-792.

   [6] Vincent D. Park IEEE Computer Society LAN MAN Standards Committee.   Wireless
       LAN Medium Access Protocol (MAC) and M. Scott Corson.  Temporally-Ordered
        Routing Algorithm (TORA) Version 1 - Functional Physical Layer (PHY)
       Specification.
        Internet-Draft, draft-ietf-manet-tora-spec-01.txt, August 1998.
        Work in progress.

    [7] Charles E. Perkins.  Mobile Ad Hoc Networking Terminology.
        Internet-Draft, draft-ietf-manet-term-00.txt, October IEEE std 802.11-1997. The Institute of Electrical
       and Electronics Engineers, New York, NY, 1997.
        Work in progress.

    [8] Charles E. Perkins

   [7] L. Ji and Pravin Bhagwat.  Highly Dynamic
        Destination-Sequenced Distance-Vector Routing (DSDV) for
        Mobile Computers. M.S. Corson.   A Lightweight Adaptive Multicast
       Algorithm. In proceedings Proceedings of ACM SIGCOMM'94, London, UK,
        September 1994, IEEE GLOBECOM'98, Sydney,
       Australia, Nov. 1998, pp. 234-244.

    [9] Charles E. Perkins 1036-1042.

   [8] J. Jubin and Elizabeth M. Royer.  Ad Hoc On Demand
        Distance Vector (AODV) Routing. Internet-Draft,
        draft-ietf-manet-aodv-01.txt, August 1998. Work in progress. J.D. Tornow.   The DARPA Packet Radio Network
       Protocols.   Proceedings of the IEEE, vol. 75, no. 1, Jan. 1987,
       pp. 21-32.

   [9] E.D. Kaplan (Editor).   Understanding the GPS: Principles and
       Applications, Artech House, Boston, MA, Feb. 1996.

  [10] Chai-Keong S.-J. Lee, M. Gerla, and C.-C. Chiang.   On-Demand Multicast
       Routing Protocol.   In Proceedings of IEEE WCNC'99, New Orleans,
       LA, Sep. 1999 (to appear).

  [11] C.-K. Toh.  Associativity-Based Routing for Ad-Hoc Mobile
       Networks.   Wireless Personal Communications Journal, Special
       Issue on Mobile Networking and Computing Systems, Kluwer
       Academic Publishers, vol. 4, no. 2, March Mar. 1997, pp. 103-139.

   [11]

  [12] UCLA Wireless Adaptive Mobility (WAM) Laboratory.
       http://www.cs.ucla.edu/NRL/wireless

Chair's Address

   The Working Group can be contacted via its current chairs:

        M. Scott Corson
        Institute for Systems Research
        University of Maryland
        College Park, MD  20742
        USA

        Phone:  +1 301 405-6630
        Email:  corson@isr.umd.edu

        Joseph Macker
        Information Technology Division
        Naval Research Laboratory
        Washington, DC  20375
        USA

        Phone:  +1 202 767-2001
        Email:  macker@itd.nrl.navy.mil

Authors' Addresses

   Questions about this document can also be directed to the authors:

        Mario Gerla
        405 Hilgard Ave.

        Sung-Ju Lee
        3771 Boelter Hall
        Computer Science Department
        University of California
        Los Angeles, CA  90095  90095-1596
        USA

        Phone:  +1 310 825-4367 206-8589
        Fax:    +1 310 825-2273 825-7578
        Email:  gerla@cs.ucla.edu
        Guangyu Pei
        405 Hilgard Ave.  sjlee@cs.ucla.edu

        William Su
        3771 Boelter Hall
        Computer Science Department
        University of California
        Los Angeles, CA  90095  90095-1596
        USA

        Phone:  +1 310 825-1888 206-8589
        Fax:    +1 310 825-7578
        Email:  pei@cs.ucla.edu

        Sung-Ju Lee
        405 Hilgard Ave.  wsu@cs.ucla.edu

        Mario Gerla
        3732F Boelter Hall
        Computer Science Department
        University of California
        Los Angeles, CA  90095  90095-1596
        USA

        Phone:  +1 310 206-8589
        Email:  sjlee@cs.ucla.edu

        Ching-Chuang Chiang
        Computer Science Department
        Chung-Cheng Institute of Technology
        Ta-Shi, TaoYuan 335
        Taiwan

        Phone:  +886 3 380-9331 825-4367
        Fax:    +886 3 389-4770    +1 310 825-7578
        Email:  ccchiang@ccit.edu.tw  gerla@cs.ucla.edu