[Search] [txt|pdfized|bibtex] [Tracker] [WG] [Email] [Nits]
Versions: 00                                                            
Mobile Ad Hoc Networking Working Group                Charles E. Perkins
INTERNET DRAFT                                     Nokia Research Center
14 November 2001                              Elizabeth M. Belding-Royer
                                 University of California, Santa Barbara
                                                            Samir R. Das
                                                University of Cincinnati

                 IP Flooding in Ad hoc Mobile Networks

Status of This Memo

   This document is a submission by the Mobile Ad Hoc Networking Working
   Group of the Internet Engineering Task Force (IETF).  Comments should
   be submitted to the manet@itd.nrl.navy.mil mailing list.

   Distribution of this memo is unlimited.

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.  Internet-Drafts are working
   documents of the Internet Engineering Task Force (IETF), its areas,
   and its working groups.  Note that other groups may also distribute
   working documents as Internet-Drafts.

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

   The list of current Internet-Drafts can be accessed at:
   The list of Internet-Draft Shadow Directories can be accessed at:


   An ad hoc mobile network is a collection of nodes, each of which
   communicates over wireless channels and is capable of movement.
   Nodes participating in such an ad hoc network communicate on
   a peer-to-peer basis.  Flooding is often a desired form of
   communication in these networks, as it can enable both the
   dissemination of control information and the delivery of data
   packets.  This document describes a method for sending packets to
   every node in an d hoc networks.

Perkins, Belding-Royer, Das         Expires 14 May 2002         [Page i]

Internet Draft      IP Flooding in Ad hoc Networks      14 November 2001

1. Introduction

   This document makes a particular specification for a classical
   flooding algorithm, as it can be used to disseminate IP packets
   across ad hoc networks.  Flooding is needed in many circumstances; in
   particular, it is useful for the kind of route discovery operations
   that are required for on-demand route acquisition in several
   candidate manet protocols.

   This protocol specification works when the nodes flooding packets
   ensure that each distinct such packet that they send is tagged with a
   distinct value in the ident field of the IP header.

   In IPv4, there are two kinds of broadcast address, and it seems
   that neither one of them is likely to present a good choice for the
   IP address to be used for flooding.  The IPv4 address for "limited
   broadcast" is, and is not supposed to be forwarded.
   Since the nodes in an ad hoc network are asked to forward the flooded
   packets, the limited broadcast address is a poor choice.  The other
   available choice, the "directed broadcast" address, would presume a
   choice of routing prefix for the ad hoc network and thus is not a
   reasonable choice.

   Thus, in this specification, new multicast groups for flooding to all
   nodes of an ad hoc network are specified.  These multicast groups
   are specified to contain all nodes of a contiguous ad hoc network,
   so that packets transmitted to the multicast address associated with
   the group will be delivered to all nodes as desired.  For IPv6,
   the multicast address is specified to be "site-local".  The names
   of the multicast groups are given as "ALL_IPv4_MANET_NODES" and

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   document are to be interpreted as described in RFC 2119 [1].

2. Flooding

   For the purposes of this document, the IPv4 flooding address is
   "ALL_IPv4_MANET_NODES" (TBD). The analogous address for transmissions
   to all IPv6 ad hoc network nodes is "ALL_IPv6_MANET_NODES" (TBD).
   This document does not specify transmissions to any directed
   broadcast address.  Transmissions to the IPv4 "limited broadcast"
   address, that is, are not forwarded by nodes obeying
   this specification.

   Every node maintains a list to keep track of which flooded packets
   have already been received and retransmitted.  The list contains, for

Perkins, Belding-Royer, Das         Expires 14 May 2002         [Page 1]

Internet Draft      IP Flooding in Ad hoc Networks      14 November 2001

   each distinct flooded packet received, a value called the Flooded
   Packet Identifier (FPI). For IPv4, this FPI is composed of the source
   IP address, the IP ident value, and the fragment offset values
   obtained from the IP header of the flooded packet.  For IPv6, the FPI
   is calculated as specified in section 3.

   When a node receives a flooded packet, it checks its list for the
   FPI of the flooded packet's IP header [2].  If there is such a list
   entry with matching FPI, the node silently discards the flooded
   packet since it has already been received and forwarded.  The node
   then checks to see whether it is enabled for retransmitting flooded
   packets.  By default, all nodes in the ad hoc network are so enabled;
   however, this is not required (see section 5) and may be changed by
   configuration.  If the node is not enabled for retransmitting flooded
   packets, it takes no further action.  If there is no existing list
   entry containing the same FPI, and if the node has been enabled to
   forward flooded packets, the node retransmits the packet.

   List entries SHOULD be kept for at least BROADCAST_RECORD_TIME
   before the node expunges the record.  BROADCAST_RECORD_TIME
   is a configurable parameter, but it MUST be at least equal to

3. FPI computation for IPv6

   To obtain the FPI for IPv6 packets, a node uses MD5 [3] to perform
   the following calculation for the incoming flooded packet:

      FPI = MD5 (IPv6 packet data).

   The IP packet data includes all non-mutable IPv6 headers and
   extensions, as well as any higher-level protocol data.  The source
   node for each flooded packet MUST ensure that this FPI is distinct
   from the FPI from every other flooded packet which the node has
   transmitted during the last BROADCAST_RECORD_TIME. In the unlikely
   event that the FPI value is identical to some such recently
   transmitted packet, the source node MUST add a Unique Identifier
   Destination Option to the flooded packet (see section 4).

Perkins, Belding-Royer, Das         Expires 14 May 2002         [Page 2]

Internet Draft      IP Flooding in Ad hoc Networks      14 November 2001

4. Unique Identifier Destination Option

   The Unique Identifier option is encoded in type-length-value (TLV)
   format as follows:

    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
                                   |  Option Type  | Option Length |
   |       Uniquifying Value       |

      Option Type


      Option Length


      Uniquifying Value

         The 16-bit Uniquifying Value is chosen to make the flooded
         packet FPI computation different than that for any other
         flooded packet from the same source node.

   The Unique Identifier MUST be placed in the Destination Options
   before the Routing Header (and, thus, before the fragment header).
   This allows proper handling by all intermediate forwarding nodes

5. Selective Retransmission for Flooded Packets

   By default, each node in the ad hoc network is enabled to retransmit
   each distinct flooded packet that it receives.  However, in some
   cases, there may be additional control signaling in place that is
   used to reduce the number of nodes that perform this retransmission,
   in order to reduce the overall bandwidth consumption and congestion
   which can be caused by excessive flooding.  This document does not
   specify any such control protocol to disable or enable such node
   selection.  However, an ad hoc network which employs such a node
   selection protocol can still be considered to be compliant with the
   flooding protocol specified in this document.

Perkins, Belding-Royer, Das         Expires 14 May 2002         [Page 3]

Internet Draft      IP Flooding in Ad hoc Networks      14 November 2001

6. Configuration Parameters

   This section gives default values for some important values
   associated with flooding operations.  Mobile nodes in particular
   ad hoc networks may wish to change certain of the parameters, in
   particular the NET_DIAMETER and NODE_TRAVERSAL values.  Choice of
   these parameters may affect the robustness of the flooding operation.

      Parameter Name          Value
      ----------------------  -----
      NET_DIAMETER            35
      NODE_TRAVERSAL_TIME     40 milliseconds

   NET_DIAMETER measures the maximum possible number of hops between
   two nodes in the network.  NODE_TRAVERSAL_TIME is a conservative
   estimate of the average one hop traversal time for packets and should
   include queuing delays, interrupt processing times and transfer
   times.  NET_TRAVERSAL_TIME is a conservative estimate of how long it
   should take for a message to traverse the entire ad hoc network.

7. Security Considerations

   This draft specifies a general mechanism for flooding packets in an
   ad hoc network.  It does not make any provision for securing the
   contents of the flooded data, either to protect against tampering or
   to protect against unauthorized inspection of the data.

8. Acknowledgments

   This flooding method is a codification of a well known algorithm
   which has been assumed for general use in various ad hoc protocols.
   Thus, the protocol specification in this draft should be considered
   the joint work of many engineers who have worked on producing ad hoc
   network protocols.  The authors of this draft hope that we have been
   able to faithfully and usefully represent the work of these many


   [1] S. Bradner.  Key words for use in RFCs to Indicate Requirement
       Levels.  Request for Comments (Best Current Practice) 2119,
       Internet Engineering Task Force, March 1997.

Perkins, Belding-Royer, Das         Expires 14 May 2002         [Page 4]

Internet Draft      IP Flooding in Ad hoc Networks      14 November 2001

   [2] J. Postel.  Internet Protocol.  Request for Comments (Standard)
       791, Internet Engineering Task Force, September 1981.

   [3] R. Rivest.  The MD5 Message-Digest Algorithm.  Request for
       Comments (Informational) 1321, Internet Engineering Task Force,
       April 1992.

Perkins, Belding-Royer, Das         Expires 14 May 2002         [Page 5]

Internet Draft      IP Flooding in Ad hoc Networks      14 November 2001

A. Changes since the last revision

    -  Changed terminology from "broadcast" to "flood", to avoid
       ambiguity with the various flavors of IPv4 broadcast.

    -  Specified a new IPv4 multicast address and a new IPv6 multicast

Author's Addresses

   Questions about this memo can be directed to:

      Charles E. Perkins
      Communications Systems Laboratory / Nokia Research Center
      313 Fairchild Drive
      Mountain View, CA 94303
      +1 650 625 2986
      +1 650 625-2502 (fax)

      Elizabeth M. Royer
      Dept. of Electrical and Computer Engineering
      University of California, Santa Barbara
      Santa Barbara, CA 93106
      +1 805 893 7788
      +1 805 893 3262 (fax)

      Samir R. Das
      Dept. of Electrical and Computer Engineering & Computer
      University of Cincinnati
      Cincinnati, OH 45221-0030
      +1 513 556 2594
      +1 513 556 7326 (fax)

Perkins, Belding-Royer, Das         Expires 14 May 2002         [Page 6]