[Search] [txt|pdfized|bibtex] [Tracker] [Email] [Nits]
Versions: 00                                                            
Mobile Ad Hoc Networking Working Group                Charles E. Perkins
INTERNET DRAFT                                     Nokia Research Center
8 July 2006                                              Thomas Clausen,
                                                        Philippe Jacquet
                                              INRIA Rocquencourt, France

   Multicast With Minimal Congestion Using Connected Dominating Sets
                    draft-perkins-manet-smurf-00.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
   Flooding is useful for many reasons in ad hoc networks, but
   causes congestion that can block traffic.  Selecting multi-point
   relays (MPRs) reduces congestion due to flooding, but has several
   disadvantages.  It is possible to select a subset of the MPRs to
   do the same job more effectively.  In this document, signaling is
   specified for identifying a relatively small connected dominating set
   that can still manage the flooding operation.








Perkins                 Expires 8 January 2006                  [Page 1]


Internet Draft            Low-Congestion Flooding            8 July 2006


1. Introduction

   Flooding is useful for many reasons in ad hoc networks, but causes
   congestion that can block traffic within such a network.  The goal
   of this document is to specify a flooding algorithm that greatly
   reduces the number of packet retransmissions needed to flood the
   whole network.  Since there a many fewer retransmissions, the amount
   of congestion due to flooding will be greatly reduced.

   In order to reduce the total number of retransmissions, we can reduce
   the number of nodes that perform the retransmissions, as long as
   all nodes still receive at least one transmission of the flooded
   packet.  If a particular node can determine its one-hop and two-hop
   neighborhoods, then it can identify a subset of its neighboring nodes
   that still be able to reach every node of the two-hop neighborhood.
   The nodes in such a subset are called "multi-point relays" (MPRs)
   in the OLSR specification [7].  There are various ways to pick
   enough MPRs so that, when each MPR retransmits a packet, the two-hop
   neighborhood will be completely covered.  These neighboring MPRs will
   themselves have selected some of their other neighbors to be MPRs.
   When the neighboring MPRs retransmit, then some of their neighbors
   will again retransmit, until eventually the whole network is covered.

   Selecting multi-point relays MPRs, as specified in OLSR [7] is
   beneficial to reduce congestion due to flooding, but has several
   disadvantages.  Another related concept is that of a "connected
   dominating set" (CDS). There are many distributed algorithms for
   computing a CDS, with a variety of interesting properties.  The set
   of MPRs that retransmit a packet originated from a source node within
   an ad hoc network is also a CDS. Otherwise, the set of MPRs would not
   be able to cover the network by retransmission hop-by-hop.

   In this document, signaling is specified for identifying a relatively
   small connected dominating set that can still manage the flooding
   operation.

   The names of the multicast groups used for flooding are given as
   "ALL_IPv4_MANET_NODES" and "ALL_IPv6_MANET_NODES" [5].  The backbone
   nodes selected for flooding packets can, however, be used for
   flooding to any designated multicast address as long as the members
   of that multicast group form a connected subgraph of the ad hoc
   network.  Specifications for future multicast groups intended for
   flooding or very dense dissemination should specifically indicate
   that their members should communicate across the SMURF backbone.
   Future documents may offer improved algorithms for the purpose of
   identifying backbone nodes, while still utilizing the protocol in
   this document for periodic updates to the necessary neighborhood
   information.




Perkins                 Expires 8 January 2006                  [Page 2]


Internet Draft            Low-Congestion Flooding            8 July 2006


      DISCUSSION: should there be a version field to handle
      unforeseen future incompatibilities?


2. SMURF Terminology

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

   This section defines other terminology that is not already defined
   in [3].

      MPR

         A "multi-point relay" -- that is, a neighboring node that can
         relay flooded packets, thus assisting with the dissemination of
         those packets throughout the network

      broadcast

         Transmit to the IPv4 Limited Broadcast address,
         255.255.255.255, or else for IPv6 to the link-local
         AllNodesMulticast address.

      neighborhood, one-hop neighborhood

         The neighborhood (also called the one-hop neighborhood) of a
         node is the set of nodes which are directly reachable by that
         node.

      two-hop neighborhood

         The two-hop neighborhood of a node is the set of nodes which
         are either directly reachable by that node, or directly
         reachable by one of the neighbors of that node.

      dominating set

         A subset of a graph is a dominating set if every node in the
         graph is eiher a member of the subset, or else a neighbor of at
         least one node in the subset.

      connected set

         A set with more than one element is connected if every node in
         the subset is a neighbor of some other node in the subset.  A
         set with fewer than two elements is connected.




Perkins                 Expires 8 January 2006                  [Page 3]


Internet Draft            Low-Congestion Flooding            8 July 2006


      CDS (connected dominating set)

         A subset of a graph is a CDS if it is a dominating set, and it
         is connected.

      flooding backbone

         The flooding backbone of an ad hoc network is a CDS which is
         used for flooding packets throughout the network, considering
         every node in the ad hoc network as a node in a graph with
         edges defined by the (one-hop) communication links that are
         available between the nodes in the ad hoc network.

      backbone

         in this document, ``backbone'' always means the flooding
         backbone


3. Overview

   Each node listens for advertisements from its neighbors.  From the
   advertisements, the node updates its stored information about its
   one-hop neighborhood and its two-hop neighborhood.  The sender of
   the advertisement is a member of the node's one-hop neighborhood,
   and the sender's neighbors are either members of the node's one-hop
   neighborhood or its two-hop neighborhood.

   There are two kinds of periodic local topology advertisements,
   which are used to enable each node to construct a representation
   of its two-hop neighborhood and subsequently select MPRs.  The
   first is called the "full advertisement", which has complete lists
   of all the necessary data.  The second is called the "incremental
   advertisement", which only has information that has changed since
   the last full advertisement.  It is expected that the incremental
   advertisement will be much smaller than the full advertisement.

   A node's neighborhood is considered to be composed of three mutually
   exclusive subsets:

    -  undistinguished first hop neighbors
    -  MPRs
    -  the node itself

   Likewise, a node's two hop neighborhood is considered to be composed
   of four mutually exclusive subsets:

    -  second hop neighbors
    -  undistinguished first hop neighbors



Perkins                 Expires 8 January 2006                  [Page 4]


Internet Draft            Low-Congestion Flooding            8 July 2006


    -  MPRs
    -  the node itself

   If a node is described as being in any one of these subsets, then
   by convention and agreement it does not belong to any of the other
   subsets.  This eliminates overlap of information in the local
   topology advertisements.

   The following information is present in full advertisements:

    -  advertisement sequence number
    -  reluctance for offering service as a backbone node
    -  first hop neighbors
    -  MPRs
    -  flags

   The following information is present in incremental advertisements:

    -  advertisement sequence number of the last full advertisement
    -  reluctance for offering service as a backbone node
    -  addresses of new first hop neighbors
    -  addresses of new MPRs
    -  addresses of lost nodes
    -  flags

   Any address in the lost node list has to be deleted from the neighbor
   list or the MPR list of the last full advertisement, and the nodes in
   these two lists reclassified if they were classified differently in
   the last full advertisement.

   A neighboring node cannot be considered for selection as an MPR until
   the link to that node has been verified as bidirectional.  For each
   neighbor, two conditions must be verified:

    1. an advertisement has been recently heard from the neighbor

    2. the node itself must appear as a member of the one-hop neighbors
       reported by that neighbor.

   Once each node has constructed its two-hop neighborhood, it uses
   any reasonable algorithm to identify a subset of neighbors which
   are to be designated as MPRs.  One algorithm that works well is the
   so-called "greedy algorithm":

    1. Initialize the set of uncovered two-hop neighbors to contain all
       known two-hop neighbors

    2. Pick the neighbor that is within range of the largest number of
       uncovered nodes in the two-hop neighborhood.



Perkins                 Expires 8 January 2006                  [Page 5]


Internet Draft            Low-Congestion Flooding            8 July 2006


    3. Mark the two-hop neighbors reachable by that neighbor's local
       broadcasts as already covered.

    4. If there are no more uncovered two-hop neighbors, stop.

    5. Otherwise, iterate steps (2) -- (4).

   Once the nodes have identified the MPRs in their neighborhoods, each
   node must also determine whether to prune itself from the flooding
   backbone (i.e., the connected dominating set of nodes which will take
   responsibility for disseminating flooded data).

   In order for a node to prune itself to the flooding backbone, it uses
   the following algorithm [1]:

    1. It forms a "CDS identifier" by appending its IP address to its
       last advertised "reluctance" value.

    2. If it is the node with a CDS identifier lower than any of its
       neighbors, then it must continue to participate as a member of
       the flooding backbone.

    3. Otherwise, if it not a MPR of its neighbor with the lowest CDS
       identifier, then it may prune itself from the flooding backbone.

   A node advertises the status of its decision to prune itself from the
   CDS backbone in its advertisement messages.


4. Full Advertisement

   The Full Advertisement has the following format:

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
                                   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                                   |     Type      |    Length     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |        Sequence #         |Rel| #1-hop  |  #MPRs  | reserved|C|
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   :            List of IP addresses of 1-hop neighbors            :
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   :             List of IP addresses of MPR neighbors             :
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

      Type

         Type == 1.




Perkins                 Expires 8 January 2006                  [Page 6]


Internet Draft            Low-Congestion Flooding            8 July 2006


      Length

         Length of the full advertisement data, in bytes, including all
         fields except for the Type and Length.

      Sequence #

         Advertisement sequence number

      Rel

         Reluctance (2 bits).  A node selects a low value for its
         reluctance, if it is willing to be identified as an MPR, and
         thus potentially as a member of the connected dominating set.

      #1-hop

         Number of one-hop neighbors

      #MPRs

         Number of one-hop neighbors reclassified as MPRs

      'C'

         The 'C' flag is set if the advertising node has selected itself
         as a member of the connecting dominating set for flooding

      1-hop list

         List of IP addresses of 1-hop neighbors (#1-hop total
         addresses)

      MPR list

         List of IP addresses of MPR neighbors (#MPRs total addresses)

   The IP header TTL for the Full Advertisement packet MUST be 1.

      DISCUSSION: is 255 better?

      DISCUSSION: Is the Length field needed, or should we spend
      the bits on enlarging the other fields?


5. Incremental Advertisement

   The Incremental Advertisement has the following format:




Perkins                 Expires 8 January 2006                  [Page 7]


Internet Draft            Low-Congestion Flooding            8 July 2006



    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
                                   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                                   |     Type      |    Length     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |        Sequence #         |Rel| #1-hop|#MPRs| #lost |reservd|C|
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   :            List of IP addresses of 1-hop neighbors            :
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   :             List of IP addresses of MPR neighbors             :
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   :             List of IP addresses of lost neighbors            :
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

      Type

         Type == 2.

      Length

         Length of the incremental advertisement data, in bytes,
         including

      Sequence #

         Advertisement sequence number

      Rel

         Reluctance (2 bits).  A node selects a low value for its
         reluctance, if it is willing to be identified as an MPR, and
         thus potentially as a member of the connected dominating set.

      #1-hop

         Number of new one-hop neighbors

      #MPRs

         Number of new nodes classified as MPRs

      #lost

         Number of nodes no longer in the one-hop neighborhood
         (and, thus, not possibly MPRs) as shown in the last full
         advertisement





Perkins                 Expires 8 January 2006                  [Page 8]


Internet Draft            Low-Congestion Flooding            8 July 2006


      'C'

         The 'C' flag is set if the advertising node has selected itself
         as a member of the connecting dominating set for flooding

      1-hop list

         List of IP addresses of new 1-hop neighbors (#1-hop total
         addresses)

      MPR list

         List of IP addresses of new MPR neighbors (#MPRs total
         addresses)

      lost list

         List of IP addresses of former neighbors that have not
         exhibited local connectivity recently (#lost total addresses)

   The IP header TTL for the Incremental Advertisement MUST be 1.

      DISCUSSION: is 255 better?

      DISCUSSION: Is the Length field needed, or should we spend
      the bits on enlarging the other fields?


6. Security Considerations

   This draft specifies a general mechanism for identifying a flooding
   backbone 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.
   It does not make any provision for ensuring that the nodes of the
   flooding backbone are operating as expected.  It does not make any
   provision to guarantee the correctness of information presented
   within the advertisement messages.  The use of local broadcast for
   the advertisement messages precludes the use of point-to-point
   security associations such as might be used for constructing
   Authentication Header digests.

   In the future, if further security measures are to be undertaken,
   one could attempt to utilize public keys for the purpose of
   authenticating the flooded data, as long as the public keys were
   known to be properly associated with the node in question (to avoid
   man-in-the-middle attacks).





Perkins                 Expires 8 January 2006                  [Page 9]


Internet Draft            Low-Congestion Flooding            8 July 2006


7. IANA considerations

   New multicast addresses have to be allocated.  A new UDP port number
   has to be allocated for the neighborhood messages.  ICMP is another
   possibility.


8. Acknowledgments

   Thomas Clausen and Emmanuel Baccelli were frequent contributors to
   the conversation which inspired the production of this document.  The
   algorithm for identifying the flooding backbone was published as
   Research Report 4597 [1] by Cedric Adjih et al.


References

   [1] Cedric Adjih, Phlippe Jacquet, and Laurent Veinnot.  Computing
       Connected Dominating Sets with Multipoint Relays.  Technical
       report, Institut National de Recherche en Informatique et en
       Automatique (INRIA).  INRIA RR 4597, October 2002.

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

   [3] Ed. J. Manner and Ed. M. Kojo.  Mobility Related Terminology.
       Request for Comments (Informational) 3753, Internet Engineering
       Task Force, June 2004.

   [4] C. Perkins.  Minimal Encapsulation within IP.  Request for
       Comments (Proposed Standard) 2004, Internet Engineering Task
       Force, October 1996.

   [5] Charles E. Perkins.  IP Flooding in Ad hoc Networks (Work In
       Progress).  Internet Draft, Internet Engineering Task Force.
       draft-perkins-manet-bcast-02.txt, June 2005.

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

   [7] Ed. T. Clausen and Ed. P. Jacquet.  Optimized Link State Routing
       Protocol (OLSR).  Request for Comments (Experimental Protocol)
       3626, Internet Engineering Task Force, June 2004.


Author's Addresses

   Questions about this memo can be directed to:



Perkins                 Expires 8 January 2006                 [Page 10]


Internet Draft            Low-Congestion Flooding            8 July 2006


      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

      Thomas Heide Clausen
      INRIA Rocquencourt, BP 105,
      78153 Le Chesnay Cedex
      France
      +33 1 3963 5133
      Thomas.Clausen@inria.fr


Full Copyright Statement

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

   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.





















Perkins                 Expires 8 January 2006                 [Page 11]