Mobile Ad Hoc Networking Working Group                Charles E. Perkins
INTERNET DRAFT                                     Nokia Research Center
29 June 2005

                 IP Flooding in Ad hoc Mobile Networks
                    draft-perkins-manet-bcast-02.txt


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@ietf.org mailing list.

   This document is an Internet-Draft and is subject to all provisions
   of section 3 of RFC 3667.  By submitting this Internet-Draft, each
   author represents that any applicable patent or other IPR claims of
   which he or she is aware have been or will be disclosed, and any of
   which he or she becomes aware will be disclosed, in accordance with
   Section 6 of BCP 79.

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

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

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.


Abstract

   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 ad hoc network.







Perkins                Expires 29 December 2005                 [Page i]


Internet Draft        IP Flooding in Ad hoc Networks        29 June 2005


1. Introduction

   This document makes a particular specification for a well-known
   flooding algorithm, as it can be used to disseminate IP packets
   across ad hoc networks.  For the well-known flooding algorithm to
   work, the nodes flooding packets must ensure that each distinct
   packet that they send is uniquely identifiable, at least during the
   expected time taken for the flooded packet to disseminate though
   an ad hoc network.  In this document, the method used for insuring
   uniqueness depends upon whether an IPv4 or IPv6 packet is being
   transmitted.

   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 network-layer flooding.  The IPv4 address
   for "limited broadcast" is 255.255.255.255, 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 should
   not used for network-layer flooding.  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.

   The key words "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].


2. Applicability Statement

   The specification in this document is immediately useful for for
   network-layer flooding -- i.e., when the TTL or hop count in the IP
   header is initialized to a value greater than 1.  Note that there
   is another useful alternative for flooding in an ad hoc network.
   Namely, it is often the case information to be flooded requires the
   attention of some application at every node receiving the flooded
   information, before that node would further disseminate the flooded
   information.  For instance, a routing protocol might need to carry
   out several kinds of operations before allowing the packet to be
   retransmitted.  In those cases, it may be quite appropriate (or even
   preferable) to use the limited broadcast address, 255.255.255.255,
   with the understanding that the packet will not be retransmitted at
   the network layer by any of the node's neighbors.  This specification
   can be used to guarantee uniqueness for such packets even when the
   application makes no modification to the payload before it it is
   retransmitted.







Perkins                Expires 29 December 2005                 [Page 1]


Internet Draft        IP Flooding in Ad hoc Networks        29 June 2005


3. Flooding

   In this specification, new multicast groups for flooding to all
   nodes of an ad hoc network are specified for use with network-layer
   flooding.  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.  In other words, any node that is reachable,
   is automatically granted membership in these multicast groups.  For
   IPv6, the multicast address is specified to be "site-local".  The
   names of the multicast groups are given as "ALL_IPv4_MANET_NODES"
   (TBD) and "ALL_IPv6_MANET_NODES" (TBD). This document does not
   specify transmissions to any directed broadcast address.

   Every node maintains a list of those flooded packets which have
   already been received and retransmitted.  The list contains, for 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 4.

   When a node receives a flooded packet, it checks its list for the
   FPI of the flooded packet's IP header [3].  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 6) and may be changed by
   configuration or by protocol action.  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
   NET_TRAVERSAL_TIME.


4. FPI computation for IPv6

      DISCUSSION QUESTION: Is another cryptographic function
      better, or good enough but easier?

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




Perkins                Expires 29 December 2005                 [Page 2]


Internet Draft        IP Flooding in Ad hoc Networks        29 June 2005


      FPI = MD5 (IPv6 packet data).

   The IP packet data includes all unpredictable IPv6 headers and
   extensions [2], 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 5).

      DISCUSSION QUESTION: Should the same digestifying procedure
      be specified for IPv4 also?


5. Unique Identifier Destination Option

      DISCUSSION QUESTION: The IPv6 fragment header can serve this
      purpose very well, at a cost of only another two bytes.
      Should that be used instead of the Unique Identifier 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

         TBD

      Option Length

         2

      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.



Perkins                Expires 29 December 2005                 [Page 3]


Internet Draft        IP Flooding in Ad hoc Networks        29 June 2005


6. 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 compliant with the flooding protocol
   specified in this document.


7. 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
      ----------------------  -----
      BROADCAST_RECORD_TIME   2 * NET_TRAVERSAL_TIME
      NET_DIAMETER            35
      NODE_TRAVERSAL_TIME     40 milliseconds
      NET_TRAVERSAL_TIME      3 * NODE_TRAVERSAL_TIME * NET_DIAMETER / 2



   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, medium access delays, and
   propagation delays.  NET_TRAVERSAL_TIME is a conservative estimate of
   how long it should take for a message to traverse the entire ad hoc
   network.


8. 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.






Perkins                Expires 29 December 2005                 [Page 4]


Internet Draft        IP Flooding in Ad hoc Networks        29 June 2005


9. 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.


References

   [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.

   [2] S. Kent and R. Atkinson.  IP Authentication Header.  Request for
       Comments (Proposed Standard) 2402, Internet Engineering Task
       Force, November 1998.

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

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


A. Changes since the last revision

    -  Added applicability section.
    -  Changed author list
    -  Added discussion points
    -  Moved some text out of the introduction into the main body of the
       specification.
    -  Othe minor editorial corrections.


Author's Addresses

   Questions about this memo can be directed to:

      Charles E. Perkins
      Networking Technology Laboratory / Nokia Research Center
      313 Fairchild Drive
      Mountain View, CA 94303
      +1 650 625 2986
      +1 650 625-2502 (fax)
      Charles.Perkins@nokia.com




Perkins                Expires 29 December 2005                 [Page 5]


Internet Draft        IP Flooding in Ad hoc Networks        29 June 2005


Intellectual Property Statement

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the
   use of such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   ietf-ipr@ietf.org.


Disclaimer of Validity

   This document and the information contained herein are provided
   on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE
   REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE
   INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR
   IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.


Copyright Statement

   Copyright (C) The Internet Society (2005).  This document is subject
   to the rights, licenses and restrictions contained in BCP 78, and
   except as set forth therein, the authors retain all their rights.











Perkins                Expires 29 December 2005                 [Page 6]