[Docs] [txt|pdf] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 RFC 6621

Network Working Group                                  J. Macker, editor
Internet-Draft                                                       NRL
Expires: December 3, 2005                                SMF Design Team
                                                           IETF MANET WG
                                                               June 2005

               Simplified Multicast Forwarding for MANET

Status of this Memo

   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-

   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

   This Internet-Draft will expire on December 3, 2005.

Copyright Notice

   Copyright (C) The Internet Society (2005).


   This document describes the Simplified Multicast Forwarding (SMF)
   protocol that provides a basic IP multicast forwarding capability
   within mobile ad-hoc networks (MANET).  SMF is designed to have
   limited applicability as a forwarding mechanism for multicast packets
   within MANET routing areas.  In addition, it provides mechanisms to
   support interoperability with a connected wired infrastructure.  SMF
   uses a simplified forwarding mechanism that delivers multicast

Macker, editor & SMF Design Team  Expires December 3, 2005      [Page 1]

Internet-Draft                SMF for MANET                    June 2005

   packets to all MANET multicast receivers within a MANET routing area.
   The core design does not use group specific information in favor of
   reduced complexity and state maintenance within the mobile topology.
   The design accounts for the unique nature and behavior of MANET
   interfaces and takes advantage of efficient relay set algorithms
   previously designed and applied in the MANET routing control plane.
   This document described the SMF forwarding process in detail and
   describes several efficient relay set algorithms that have been
   implemented in conjunction with SMF.

Macker, editor & SMF Design Team  Expires December 3, 2005      [Page 2]

Internet-Draft                SMF for MANET                    June 2005

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  4
     1.1.  Terminology  . . . . . . . . . . . . . . . . . . . . . . .  6
     1.2.  Applicability  . . . . . . . . . . . . . . . . . . . . . .  6
   2.  SMF Design Considerations  . . . . . . . . . . . . . . . . . .  7
     2.1.  Previous Related Work  . . . . . . . . . . . . . . . . . .  8
   3.  SMF Packet Processing and Forwarding . . . . . . . . . . . . .  9
   4.  SMF Duplicate Packet Detection . . . . . . . . . . . . . . . . 12
     4.1.  SMF IPv4 Duplicate Packet Detection  . . . . . . . . . . . 13
     4.2.  SMF IPv6 Duplicate Packet Detection  . . . . . . . . . . . 14
       4.2.1.  IPv6 SMF-DPD Header Option Format  . . . . . . . . . . 15
   5.  Relay Set Selection  . . . . . . . . . . . . . . . . . . . . . 16
   6.  SMF Multicast Border Gateway Considerations  . . . . . . . . . 17
     6.1.  Forwarded Multicast Groups . . . . . . . . . . . . . . . . 17
     6.2.  Multicast Group Scoping  . . . . . . . . . . . . . . . . . 17
     6.3.  Duplicate Packet Detection Marking . . . . . . . . . . . . 17
     6.4.  Interface with Exterior Multicast Routing Protocols  . . . 18
     6.5.  Multiple Gateways  . . . . . . . . . . . . . . . . . . . . 18
   7.  Security Considerations  . . . . . . . . . . . . . . . . . . . 19
   8.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 20
   9.  Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . . 21
   10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 22
     10.1. Normative References . . . . . . . . . . . . . . . . . . . 22
     10.2. Informative References . . . . . . . . . . . . . . . . . . 22
   Appendix A.  Source-based Multipoint Relay (S-MPR) . . . . . . . . 23
     A.1.  S-MPR Relay Set Selection  . . . . . . . . . . . . . . . . 23
     A.2.  S-MPR Forwarding Rules . . . . . . . . . . . . . . . . . . 24
     A.3.  Neighborhood Discovery Requirements  . . . . . . . . . . . 24
   Appendix B.  Essential Connecting Dominating Set (E-CDS)
                Algorithm . . . . . . . . . . . . . . . . . . . . . . 25
     B.1.  E-CDS Relay Set Selection  . . . . . . . . . . . . . . . . 25
     B.2.  E-CDS Forwarding Rules . . . . . . . . . . . . . . . . . . 25
     B.3.  Neighborhood Discovery Requirements  . . . . . . . . . . . 25
   Appendix C.  Multipoint Relay Connected Dominating Set
                (MPR-CDS) Algorithm . . . . . . . . . . . . . . . . . 26
     C.1.  MPR-CDS Relay Set Selection  . . . . . . . . . . . . . . . 26
     C.2.  MPR-CDS Forwarding Rules . . . . . . . . . . . . . . . . . 26
     C.3.  Neighborhood Discovery Requirements  . . . . . . . . . . . 26
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 27
   Intellectual Property and Copyright Statements . . . . . . . . . . 28

Macker, editor & SMF Design Team  Expires December 3, 2005      [Page 3]

Internet-Draft                SMF for MANET                    June 2005

1.  Introduction

   Design and implementation progress has been made in developing and
   implementing more efficient ways to flood control packets within
   MANET wireless routing protocol designs.  For example, algorithms
   within MANET RFC 3626 [RFC3626]and RFC 3684 [RFC3684] specify
   distributed methods of dynamically electing reduced relay sets for
   the purposes of optimizing the flooding routing control packets to
   all MANET nodes.  In this document, we specify the Simplified
   Multicast Forwarding (SMF) framework.  The main purpose of SMF is to
   adapt efficient flooding designs in MANET environments and apply
   these mechanisms to IP multicast packet forwarding.  When efficient
   flooding is a sufficient technique, SMF can make multicast forwarding
   available to data flows within a MANET routing area.  The SMF
   baseline design limits the scope to basic, best effort multicast
   forwarding and its applicability is intended to be constrained within
   a MANET routing area.  Figure 1 provides an overview of the logical
   SMF node architecture, consisting of "Neighborhood Discovery", "Relay
   Set Selection" and "Forwarding Process" components.  Typically, relay
   set selection (or even self-election) will occur based on input from
   a neighborhood discovery process, and the forwarding process will be
   controlled by status based upon relay set selection.  In some cases,
   the forwarding decision for a packet may also depend on previous hop
   or incoming interface information.  The asterisks (*) in Figure 1
   mark the primitives and relationships needed by relay set algorithms
   requiring previous-hop packet forwarding knowledge.

Macker, editor & SMF Design Team  Expires December 3, 2005      [Page 4]

Internet-Draft                SMF for MANET                    June 2005

       ______________                _____________
      |              |              |             |
      | Neighborhood |              |  Relay Set  |
      |  Discovery   |------------->|  Selection  |
      |   Protocol   |   neighbor   |  Algorithm  |
      |______________|     info     |_____________|
             \                              /
              \                            /
       neighbor\                          /fowarding
         info*  \      ____________      /  status
                 \    |            |    /
                  `-->| Forwarding |<--'
                      |  Process   |
    incoming packet,                 forwarded packets
    interface id, and
    previous hop*

           Fig. 1 - SMF Node Architecture

   This document describes a network layer multicast forwarding process
   compatible with different neighborhood discovery protocols and relay
   set selection algorithms.  Different discovery mechanisms or relay
   set algorithms may be applicable for different MANET routing
   protocols and deployments.  In the simplest case, Classical Flooding
   (CF) can be supported, eliminating the need for any relay set
   algorithm or neighborhood topology information.  However, it is
   expected that more efficient flooding techniques will be preferred
   due to expected gains in network efficiency and reductions in
   wireless congestion and contention.  Efficient flooding is realized
   by selecting a _subset_ of all possible nodes in a MANET area as the
   forwarding relay set.  Algorithms exist that can make use of local
   network neighborhood topology information to determine an appropriate
   relay set in a distributed, dynamic fashion.  These relay set
   selection algorithms can be used to provide a distribution tree for
   user multicast data[MDC04].  A few such relay set selection
   algorithms are described in Appendices of this document, but it is
   possible that additional relay set algorithms or extensions may be
   specified in the future for use with SMF.

   As noted, neighborhood topology information is usually needed for a
   relay set selection algorithm to determine an appropriate set of
   forwarding nodes.  In many cases, it is expected that neighborhood
   topology discovery functions may be provided by a MANET unicast
   routing protocol or neighbor discovery implementation running in
   concurrence with SMF.  Or, in other cases, it is possible that some
   wireless link layer or multiple access protocols may provide the
   necessary neighborhood information through an enhanced interface.

Macker, editor & SMF Design Team  Expires December 3, 2005      [Page 5]

Internet-Draft                SMF for MANET                    June 2005

   Different relay set algorithms and associated forwarding decision
   logic may have differing neighborhood discovery demands than other
   relay set algorithms.  While this document states specific
   requirements for neighborhood discovery with respect to the
   forwarding process and relay set selection algorithms described
   herein, it is left to other documents or protocol specifications to
   define a specific neighborhood discovery protocol [TBD - REF "MANET
   Neighborhood Discovery Protocol" document].

   Note that Figure 1 provides a notional architecture for _typical_
   MANET SMF-capable nodes.  However, a goal is that simple end-system
   (non-forwarding) wireless nodes may also participate in multicast
   traffic transmission and reception with standard network layer
   semantics.  Also, a multicast border gateway mechanism MUST be used
   when interoperating with other IP multicast routing in the wired
   world (e.g., PIM).  In present experiments, MLD proxying methods have
   been used to enable some gateway functionality at MANET border
   gateways operating with wired multicast routing protocol interfaces.
   Although SMF may be extended or combined with other protocols to
   provide increased reliability and group specific forwarding state,
   the details of those methods will be discussed in other documents.

1.1.  Terminology

      MANET : Mobile Ad hoc Networks

      SMF : Simplified Multicast Forwarding

      CF : Classical Flooding

      CDS : Connected Dominating Set

      MPR : Multi-point Relay

      DPD: Duplicate Packet Detection

1.2.  Applicability

   A basic packet forwarding service that reaches all destinations
   participating within a MANET environment can be a useful generic
   group communication mechanism for an application layer.  While the
   design requirements for this are similar to those often needed by the
   control plane of many MANET unicast routing protocol layers, it is
   desirable to provide a more generic forwarding function for use by
   other applications.  There are a number of application areas that
   could take advantage of a simple ALL_NODES delivery service within a
   MANET routing region (e.g., multimedia streaming, peer-to-peer
   middleware multicasting, auto-configuration, and discovery services).

Macker, editor & SMF Design Team  Expires December 3, 2005      [Page 6]

Internet-Draft                SMF for MANET                    June 2005

2.  SMF Design Considerations

   The simplest design often conceived and adapted for MANET packet
   flooding is something we designate as the "classical flooding" (CF)
   algorithm.  In CF, each participating forwarder node is required to
   rebroadcast packets intended for dissemination once and only once.
   This approach is extremely simple and only requires only some means
   of duplicate packet detection (DPD) and a basic forwarding mechanism.
   However, it is well known that using CF, especially within dense
   networks, results in a significant number of redundant transmissions
   often referred to as the broadcast storm problem [NTSC99].  Within
   wireless multi-hop network direct contention and interference is
   often experienced beyond the single hop interface and reducing
   unnecessary channel contention within a MANET can also significantly
   improve network performance.  Therefore, minimizing the number of
   required relay nodes is a heightened design goal in this environment.
   Unfortunately, reducing the number of relay nodes in a MANET
   environment may also decrease the robustness of packet delivery in a
   mobile topology.  There exists an interdependent design tradeoff
   between relay efficiency and delivery robustness that is scenario and
   system dependent and should be considered carefully.  If needed,
   additional reliability mechanisms MAY be considered for use with
   reduced relay sets (e.g., backup and redundant relay set) but the use
   of limited hop-by-hop retransmission schemes at the network layer are
   considered out of scope for this document.  If needed by an
   application, the use of IETF reliable multicast transport layer
   protocols (e.g., RMT) should be transparently supported by SMF's best
   effort delivery mechanism.  The basic design goal of SMF is support
   both a simple CF-based forwarding capability and to supplement this
   with reduced relay set algorithms for increased efficiency.

   At a theoretic level, work in the area of minimizing packet
   forwarders, or relay node sets, is often related to basic graph
   theory problems.  In graph theory, a dominating set (DS) for a graph
   is a set of vertices that, along with their neighbors, constitute all
   the vertices in the graph.  A connected DS (CDS) is a DS where the
   subgraph induced is connected.  A minimum CDS (MCDS) is a set such
   that the number of vertices is the minimum required to form a CDS.
   Finding a small dominating set is one of the most fundamental
   problems of traditional graph theory and is often related to the
   problem of optimizing flooding algorithms in MANET routing protocols.
   Finding an MCDS in a given graph is known to be NP-hard [GJ79].
   These basic static graph theoretic issues are important to apply in
   developing efficient relay sets, but in addition MANET relay set
   designs require distributed and dynamic operation.  To better explain
   the design requirement, we formulated the following characteristics
   desired of an effective MANET flooding algorithm solution for use in

Macker, editor & SMF Design Team  Expires December 3, 2005      [Page 7]

Internet-Draft                SMF for MANET                    June 2005

   1.  A resultant cover set that is small compared to the total number
       of nodes as the network scales in size and density.

   2.  A robust approach somewhat resilient to network mobility and link

   3.  A cover set election/maintenance mechanism that is lightweight,
       distributed, and adaptive in nature.

2.1.  Previous Related Work

   Previous novel work on MANET flooding and reduced relay set
   mechanisms has been done and this document borrows from and builds
   off previous work accomplished.  In [WC02], a taxonomy of flooding
   algorithms for use in MANET environments was presented and the work
   examined performance issues related to various approaches.  Other
   important work has developed distributed mechanisms that select and
   maintain reduced relay node sets.  As we have already mentioned, the
   design tradeoffs are further complicated by wireless contention,
   topological classes, and the robustness of packet delivery and set
   election under mobility scenarios.  In addition, the actual protocol
   implementation for IP multicast forwarding based upon these flooding
   algorithms raises additional design tradeoffs and issues.  This
   includes maintenance of protocol state, duplicate packet detection
   mechanisms, packet processing requirements, expected traffic patterns
   (e.g., one -to-many vs. many-to-many), requirements for robust
   performance, and associated protocol signaling required by any
   associated mechanism.

Macker, editor & SMF Design Team  Expires December 3, 2005      [Page 8]

Internet-Draft                SMF for MANET                    June 2005

3.  SMF Packet Processing and Forwarding

   The SMF Packet Processing and Forwarding actions are conducted with
   the following packet handling activities:

   1.  Interception of outbound, locally-generated multicast packets.

   2.  Reception of inbound packets on a specific network interface(s).

   In the case that sequence-based DPD as described later (see
   Section 4)is used, the purpose of intercepting outbound, locally-
   generated multicast packets is to apply resequencing of the IPv4 ID
   header field or add options headers as needed (e.g.  IPv6).  In the
   case that resequencing is deemed necessary, it is RECOMMENDED that
   sequence numbering be applied such that a different sequence number
   space per <sourceAddress::destinationAddress> duple be used.  For
   initial SMF purposes where no distinct routing path decisions for
   different IP Multicast address destinations occur, it might appear to
   be sufficient to use sequence number spaces aggregated across all IP
   Multicast destinations (or across all IP destinations for a source as
   is the default implementation of the IPv4 ID field in many operating
   systems).  Future SMF extensions, beyond the present discussion, may
   contain dynamic forwarding state dependent on the multicast
   destination address.  The future possibility that different
   destinations may be routed differently suggests "per source/
   destination" numbering be used.  It should be noted that the default
   global IPv4 ID sequence space may be sufficient for some SMF
   deployments and interception of outbound packets may not be required
   if end systems have numbered the IPv4 ID field in an acceptable
   manner.  In other cases, such as when IPSec headers have been applied
   to packets, other sequence information (perhaps even "per flow") may
   be available for the SMF process to make use of in its duplicate
   table management.

   Inbound multicast packets will be received by the SMF implementation
   and processed for possible forwarding.  Well-known multicast groups
   for flooding to all nodes of an ad hoc network are specified for use
   with the network-layer flooding provided by SMF.  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 support
   transmissions to any directed broadcast address ranges.  Minimally
   SMF SHALL forward unique (non-duplicate) packets received for these

Macker, editor & SMF Design Team  Expires December 3, 2005      [Page 9]

Internet-Draft                SMF for MANET                    June 2005

   well-known group addresses when the TTL or hop count value in the IP
   header is greater than 1.  Optionally, SMF deployments may choose to
   forward packets for additional "global scope" multicast groups to
   support application needs or to distribute multicast packets that
   have ingressed the MANET area via border gateways.  Additional
   addresses will be specified by an a priori list or possible through a
   dynamic address management interface.  In all cases, the following
   rules SHALL be observed for SMF multicast forwarding:

   1.  Multicast packets with TTL <= 1 MUST NOT be forwarded*.

   2.  IPv6 Link Local multicast packets MUST NOT be forwarded
       regardless of TTL.

   3.  Multicast packets with an IP source address matching one of those
       of the local host interface(s) MUST NOT be forwarded.

   4.  Received packet frames with the MAC source address matching the
       local host interface(s) MUST NOT be forwarded.

      _(* An exception may be needed for rule #1 if IGMP or MLD proxy
      functions dictate flooding of such messages)_

   Note that rule #3 is important because in wireless networks, the
   local host may receive re-transmissions of its own packets when they
   are forwarded by neighboring nodes.  This rule avoids unnecessary
   retransmission of locally-generated packets even when other
   forwarding decision rules would apply.

   Once these criteria have been met, the implementation should
   reference a forwarding decision algorithm, possibly in concert with
   duplicate packet detection, to determine the next step in packet
   processing.  The forwarding decision may be implicit if the SMF
   implementation is configured to perform classic flooding (CF) of IP
   multicast packets.  Otherwise, the forwarding decision may be
   controlled by another process.  Neighborhood discovery protocols
   coupled with the source-based multi-point relay (S-MPR) or other CDS
   selection algorithms described below MAY be used to determine the
   local host's status with respect to forwarding.  For example, some
   algorithms may control forwarding based on a previous hop indentifier
   (e.g.  S-MPR forwarding), while others may designate the local host
   as a forwarder of all packets (or at least those generated by known
   neighbors) based on the neighborhood broadcast topology (e.g.
   Essential CDS (E-CDS)).

   DPD is the perhaps the most complex portion of the SMF forwarding
   process.  In general, detection of received duplicate packets is
   necessary to avoid forwarding the same packet multiple times.

Macker, editor & SMF Design Team  Expires December 3, 2005     [Page 10]

Internet-Draft                SMF for MANET                    June 2005

   However, in some cases (e.g., S-MPR), duplicate detection of some
   non-forwarded packets is also needed to maintain efficient
   forwarding.  Details on different duplicate packet detection and
   forwarding rules for the S-MPR, and E-CDS algorithms are given in
   Appendices of his document.  The details for these classes of
   algorithms may also apply to other similar algorithms.

Macker, editor & SMF Design Team  Expires December 3, 2005     [Page 11]

Internet-Draft                SMF for MANET                    June 2005

4.  SMF Duplicate Packet Detection

   One important design difference between routing for MANET interfaces
   and many wired network interfaces is that forwarding out the same
   physical interface a packet arrived upon is a normal operation.  This
   operation is often disallowed or discouraged in wired multicast
   routing designs to avoid possible looping.  Similarly, any Reverse
   Path Forwarding (RPF) logic also used needs to be softened when
   operating over a single MANET interface.  This MANET interface
   characteristic leads to DPD as a common requirement in MANET packet
   flooding.  While this requires increased per packet processing, it is
   necessary in MANET-specific multicasting because packets must be
   potentially be forwarded out the same physical interface they may
   arrive on and nodes can even receive copies of previously-transmitted
   packets from other forwarding neighbors.  This section describes a
   basic SMF DPD mechanism and some alternative operational options as

   SMF SHOULD implement explicit detection of duplicate multicast
   packets by a temporal packet identification scheme.  This is
   typically implemented by keeping a history of previous received and
   forwarded packet identifiers for comparison against recently
   forwarded multicast packets.  There are different possible approaches
   to packet identification that have been considered.  Possibilities
   include unique markings within packet header fields, such as packet
   sequence numbering, or application of hash algorithms or similar
   techniques to compactly and uniquely describe the history of recently
   received packets.  This document RECOMMENDS simple, sequence-based
   schemes that can be accomplished without additional (non-IP)
   encapsulation of packets and/or their content.  Encapsulation
   approaches are considered out-of-scope so that non-forwarding edge
   nodes within a MANET area may easily receive flooded content without
   any additional software beyond that of a typical IP stack.  Packet
   hashing approaches for DPD may be applicable in some cases, yet early
   examination of these approaches indicated the computation complexity
   may be prohibitive for per-packet processing on many candidate MANET
   platforms (e.g., PDAs).  Additionally, the unavoidable "cache-miss"
   rates, while possibly low for some algorithms, result in the severe
   penalty of false DPD (and thus packet loss) rather than the more
   benign penalty of additional computation cycles as associated with
   most applications of hashing.

   Implementations will need to age and/or timeout duplicate packet
   state as new packets are received and forwarded.  In the case that
   sequence-based packet identification is used, implementations SHOULD
   timeout stale histories for <sourceAddress::destinationAddress>
   entries where new, non-duplicate packets have not been recently
   received.  The proper duration of any timeout delay is a function of

Macker, editor & SMF Design Team  Expires December 3, 2005     [Page 12]

Internet-Draft                SMF for MANET                    June 2005

   expected possible network traversal time, roughly NET_DIAMETER (in
   hops) times NODE_TRAVERSAL_TIME.  NET_DIAMETER measures the maximum
   possible number of hops given any two nodes in the network.
   NODE_TRAVERSAL_TIME is a conservative estimate of the average one hop
   traversal time for packets and should include queueing delays,
   interrupt processing times, medium access delays, and propagation
   delays.  If the timeout is reset only upon reception of non-duplicate
   packets, it also limits the time that packets might be incorrectly
   dropped if a source node is stopped and restarted in the case of
   sequence-based packet identification.  The required size of the
   duplication detection cache is similarly governed and is also a
   function of the maximum expected packet rate.

   Of course, the duplicate packet detection mechanism SHOULD avoid
   keeping unnecessary state for packet flows such as those that are
   locally generated or link local destinations that would not be
   considered for forwarding.

4.1.  SMF IPv4 Duplicate Packet Detection

   IPv4 multicast packets from a particular source are assumed to be
   marked with a temporally unique identification number in the ID field
   of the IPv4 packet header [RFC0791] that can serve as a
   "packetIdentifier" for SMF purposes.  Unfortunately, in present
   operating system networking kernels, this IP header field value is
   not always generated or applied in a consistent manner with respect
   to SMF needs.  In order to build a working implementation without
   encapsulating packets, an SMF implementation SHOULD provide a
   sequence generation and marking module that can maintain and set a
   monotonically increasing IP ID field for locally-generated multicast
   packets with independent sequence number spaces applied on a
   <sourceAddress::destinationAddress> basis.  When needed this process
   will also recalculate and replace a proper IP header checksum for the
   formulated header.  For gateways injecting external IPv4 traffic into
   an SMF MANET area, the gateways SHOULD perform this same IP ID field
   re-sequencing.  Note the presence of IPSec may prevent such
   resequencing, but does provide its own organic means for duplicate
   packet detection.

   The use of IPSec for candidate packet flows presents the opportunity
   to make use of the additional, perhaps more reliable, sequencing
   information of the IPSec header for unique packet identification.
   The IPSec header provides a packet identifier field that can be used
   on a "per-security assocation" basis.  The IP addressing and IPSec
   Security Parameters Index (SPI) fields are used to identify security
   associations and, hence, packet flows.  So, if the packet is IPSec
   encapsulated, SMF will check the <sourceAddress::destinationAddress::
   SPI::packetIdentifier> where the <ESP_seq_number> or <AH_seq_number>

Macker, editor & SMF Design Team  Expires December 3, 2005     [Page 13]

Internet-Draft                SMF for MANET                    June 2005

   from the IPSec header serves as the "packetIdentifier" value.

   Although it would be possible to support IP layer fragmentation , SMF
   traffic sources or gateways SHOULD set the don't fragment bit for
   traffic intended to be carried by SMF.  This is recommended to avoid
   the additional complexity and inefficiencies arising from supporting
   IP layer fragmentation.

   To perform duplicate detection, SMF will check the <sourceAddress::
   destinationAddress::packetIdentifier> combination against a cache
   history of received packet identifiers.  Some forwarding algorithms
   may require that unique packets are only noted when received from
   certain neighbor nodes.  Multiple interface semantics may also add
   some additional considerations to the forwarding process depending
   upon the specific relay set selection forwarding rules.

   Although its use is demonstrated in working prototype code, the
   adoption of the IPv4 ID field for widespread packet duplication
   detection has some disadvantages that should be discussed.  The main
   disadvantage is that, as mentioned, the use and interpretation of the
   field is known to be non-consistent across operating systems.  The ID
   field is also limited and may provide less robust detection for high
   bandwidth applications since sequence wrap-around may occur
   relatively frequently if it is not possible to achieve "per source/
   destination" sequencing.  As an alternative, the use of a header
   option or encapsulation header in future implementations may provide
   more flexibility and consistency (see IPv6 DPD).  Another advantage
   of using a header option (or other encapsulation, if determined
   absolutely necessary) is that it would be possible for MANET gateway
   nodes to assess whether packets ingressing a MANET area have already
   been properly sequenced to avoid unnecessary re-injection of packets.
   We leave these design alternatives to be further defined and
   discussed in future work or later revisions of this ID.  A basic
   sequencing and marking design similar to the one we formulate here
   can be easily adapted to work with future approaches or can be
   bypassed when not needed.

4.2.  SMF IPv6 Duplicate Packet Detection

   The following section describes the mechanism and options for SMF
   IPv6 DPD.  The core IPv6 header does not provide an explicit
   identification header field that we can exploit for DPD.  SMF defines
   two methods for IPv6 use: a hop-by-hop DPD options header and the use
   of IPSec sequencing when an IPSec header is detected.  SMF MUST
   provide a DPD marking module that can insert the hop-by-hop IPv6
   header option defined for locally generated MANET multicast.  If the
   packet is _not_ IPSec encapsulated, SMF will use the IPv6 packet
   header and IPv6 DPD option to form <sourceAddress::

Macker, editor & SMF Design Team  Expires December 3, 2005     [Page 14]

Internet-Draft                SMF for MANET                    June 2005

   destinationAddress::packetIdentifier> that is checked against a cache
   history of received IPv6 packet identifiers.  Similarly to the case
   for IPv4, the presence of IPSec may prevent the intermediate addition
   of a hop-by-hop options header.  Fortunately, the IPSec header
   provides a packet identifier field that can be used on a "per-
   security assocation" basis.  The IP addressing fields and IPSec
   Security Parameters Index (SPI) fields are used to identify security
   associations and, hence, packet flows.  So, if the packet is IPSec
   encapsulated, SMF will check the <sourceAddress::destinationAddress::
   SPI::packetIdentifier> where the <ESP_seq_number> or <AH_seq_number>
   from the IPv6 IPSec header serves as a "packetIdentifier" value.

4.2.1.  IPv6 SMF-DPD Header Option Format

   Figure 2 illustrates the format of the IPv6 SMF Duplication Packet
   Detection (SMF-DPD) hop-by-hop header option.  (Discussion: Is there
   any value in specifying this as a "destination" option instead?).  If
   this is the only hop-by-hop option present, this will result in the
   addition of 8 bytes to the IPv6 packet header including the "Next
   Header", "Header Extension Length", SMF-DPD option fields, and

       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   | Opt. Data Len |
      |     DPD packet identifier     |              ...

                 Fig. 2 - IPv6 SMF-DPD Hop-by-hop Header Option
   Option Type = (TBD)

   Opt. Data Len = 2

   DPD packet identifier = monotonically increasing 16-bit sequence
   number assigned on a per <sourceAddress::destinationAddress> basis.

Macker, editor & SMF Design Team  Expires December 3, 2005     [Page 15]

Internet-Draft                SMF for MANET                    June 2005

5.  Relay Set Selection

   As mentioned SMF MUST support CF-based forwarding as a basic
   forwarding mechanism when optimized relay set information is not
   available or not selected.  In CF mode, each node transmits a locally
   generated or newly received packet exactly once.  The DPD technique
   mentioned in the previous section is critical to proper operation and
   avoids any duplicate packet retransmissions.

   In the requirements sections, it was stated that SMF MUST support the
   ability to modify forwarding rules based upon relay set information
   that is received dynamically during operation.  In this way, SMF can
   operate more efficiently within the MANET multicast area.  In the
   section we define the interface and processing semantics to allow SMF
   to support a variety of different relay set algorithms and

   Some recommended criteria for relay set selection algorithm

   1.  Robust with respect to mobility or other network dynamics

   2.  Require minimal signaling for neighbor discovery and/or control

   3.  Allow nodes to express preference for/against selection as relay

   Some relay set algorithms that meet this criteria are described in
   the Appendices of this document.  Different algorithms may be more
   suitable for different MANET routing types or deployments.
   Additional relay set selection algorithms may be specified in
   separate documents in the future.  The Appendices in this document
   can serve as a template for the content of such potential future

Macker, editor & SMF Design Team  Expires December 3, 2005     [Page 16]

Internet-Draft                SMF for MANET                    June 2005

6.  SMF Multicast Border Gateway Considerations

   Typically, it is expected that SMF will be used to distribute
   multicast traffic within a MANET area.  However, it is also
   envisioned to allow interconnection of SMF operation with networks
   using other multicast routing protocols if appropriate conditions are
   met.  Some primary considerations for further defintion (TBD)

   1.  Determining which multicast groups should transit the gateway
       whether entering or exiting the attached MANET area(s).

   2.  TTL threshold or other scoping policies.

   3.  Any marking or labeling to enable DPD on ingressing packets.

   4.  Interface with exterior multicast routing protocols.

   5.  Possible operation with multiple gateways.

   The behavior of gateway nodes is the same as that of non-gateway
   nodes when forwarding packets to interfaces within the MANET area.
   Packets that are passed to interfaces operating typical multicast
   routing protocols SHOULD be evaluated for duplicate packet status
   since standard multicast forwarding for wired interfaces do not
   usually perform this function.

6.1.  Forwarded Multicast Groups

   Determining which groups should be forwarded to or from a MANET SMF
   area presents challenges.  Ideally, only groups for which there is
   active group membership should be injected into the SMF domain.  This
   might be accomplished by providing an IPv4 Internet Group Membership
   Protocol (IGMP) or IPV6 Multicast Listener Discovery (MLD) proxy
   function so that MANET SMF nodes can inform attached gateways (and
   hence multicast networks) of their current group membership status.

6.2.  Multicast Group Scoping


6.3.  Duplicate Packet Detection Marking

   Packets sourced external to an SMF area may not have duplicate packet
   sequencing properly applied and the gateway may need to provide that
   sequencing information upon entry to the network.  In the case of
   IPv6, the gateway can apply the SMF DPD Hop-by-Hop options header to
   packets forwarded into the MANET area for those packets that do not

Macker, editor & SMF Design Team  Expires December 3, 2005     [Page 17]

Internet-Draft                SMF for MANET                    June 2005

   already have the option applied.  This header option provides the
   side benefit that the gateway can explicitly determine if the packet
   has already been marked and can use the packet identification field
   to determine that it is not re-injecting a duplicate packet.  For
   IPv4, it is RECOMMENDED that gateway nodes re-sequence the ID field
   of packets injected into the area.  However, the IPv4 ID field does
   not provide the gateway with explicit information on whether the
   field has been previously set for SMF purposes.  Thus, the potential
   exists that duplicate IPv4 packets may be re-injected by a gateway
   into an SMF area.  Further discussion and experimentation is
   recommended in this area.

   _(If multiple gateways are injecting packets, how do we make sure
   that dups are sequenced the same way? )_

6.4.  Interface with Exterior Multicast Routing Protocols


6.5.  Multiple Gateways


Macker, editor & SMF Design Team  Expires December 3, 2005     [Page 18]

Internet-Draft                SMF for MANET                    June 2005

7.  Security Considerations

   Gratuitous use of option headers can cause problems in routers.
   Routers outside of MANET routing areas should ignore SMF header
   options if encountered.

   Authentication mechanisms to identify the source of an option header
   should be considered to reduce vulnerability to a variety of attacks.

   Additional security consideration TBD.

Macker, editor & SMF Design Team  Expires December 3, 2005     [Page 19]

Internet-Draft                SMF for MANET                    June 2005

8.  IANA Considerations

   There are number of discussions within this SMF specificat that will
   be subject to IANA registration.  The IP Header Extensions being
   defined within this document MUST have an IANA registry established
   for them upon publication of the first RFC.  Additionally, the well-
   known multicast addresses intended for default use by the SMF
   forwarding process should be registered and defined by the first RFC

Macker, editor & SMF Design Team  Expires December 3, 2005     [Page 20]

Internet-Draft                SMF for MANET                    June 2005

9.  Acknowledgments

   Many of the concepts and mechanisms used and adopted by SMF resulted
   from many years of discussion of related work within the MANET WG.
   There are obviously many people that have contributed to past
   discussions and related draft documents within the WG that have
   influenced the development of SMF concepts that deserve
   acknowledgment.  In particular, the document is largely a direct
   product of the SMF design team within the IETF MANET WG and borrows
   text and implementation ideas from these individuals.

      SMF Design Team Contributors

      Thomas Clausen

      Charles Perkins

      Brian Adamson

      Justin Dean

      Brian Haberman

      Ian Chakeres

      Maoyu Wang

      Et al

   The RFC text was produced using Marshall Rose's xml2rfc tool.

Macker, editor & SMF Design Team  Expires December 3, 2005     [Page 21]

Internet-Draft                SMF for MANET                    June 2005

10.  References

10.1.  Normative References

   [RFC0791]  Postel, J., "Internet Protocol", STD 5, RFC 791,
              September 1981.

10.2.  Informative References

   [E-CDS]    Ogier, R., "MANET Extension of OSPF Using CDS Flooding",
              Proceedings of the 62nd IETF , March 2005.

   [GJ79]     Garey, M. and D. Johnson, "Computers and Intractability: A
              Guide to the Theory of NP-Completeness.", Freeman and
              Company , 1979.

   [JLMV02]   Jacquet, P., Laouiti, V., Minet, P., and L. Viennot,
              "Performance of multipoint relaying in ad hoc mobile
              routing protocols", Networking , 2002.

   [MDC04]    Macker, J., Dean, J., and W. Chao, "Simplified Multicast
              Forwarding in Mobile Ad hoc Networks", IEEE MILCOM 2004
              Proceedings , 2004.

   [NTSC99]   Ni, S., Tseng, Y., Chen, Y., and J. Sheu, "The Broadcast
              Storm Problem in Mobile Ad hoc Networks", Proceedings Of
              ACM Mobicom 99 , 1999.

   [RFC3626]  Clausen, T. and P. Jacquet, "Optimized Link State Routing
              Protocol", 2003.

   [RFC3684]  Ogier, R., Templin, F., and M. Lewis, "Topology
              Dissemination Based on Reverse-Path Forwarding", 2003.

   [WC02]     Williams, B. and T. Camp, "Comparison of Broadcasting
              Techniques for Mobile Ad hoc Networks", Proceedings of ACM
              Mobihoc 2002 , 2002.

Macker, editor & SMF Design Team  Expires December 3, 2005     [Page 22]

Internet-Draft                SMF for MANET                    June 2005

Appendix A.  Source-based Multipoint Relay (S-MPR)

   The source-based multipoint relay (S-MPR) set selection algorithm
   enables individual nodes, using two-hop topology information to
   select a minimum set of neighboring nodes that can provide relay to
   all nodes within a two-hop radius.  This distributed technique has
   been shown to approximate selection of a MCDS in [JLMV02].
   Individual nodes must collect two-hop neighborhood information from
   neighbors, determine an appropriate current relay set, and then
   inform the resultant selected neighbors of their relay status.  The
   Optimized Link State Routing (OLSR) protocol has used this algorithm
   and protocol for relay of link state updates and other control
   information[RFC3626] and has been shown to operate well even in
   dynamic network environments.

   Because a node's status as a relay is with respect to neighboring
   nodes who have selected it (i.e., its "selectors"), the relaying node
   must know the previous-hop transmitter of packets it receives in
   order to make an appropriate forwarding decision.  Additionally, it
   is important that relay nodes forward packets only for those nodes
   currently identified as symmetric, one-hop neighbors to maintain
   correctness.  Also, because the selection of relays does not result
   in a common set among neighboring nodes, relays MUST mark in their
   duplicate table any transmissions from non-selector, symmetric, one-
   hop neighbors (for a given interface) and not forward subsequent
   received copies of that packet even if received from a selector
   neighbor.  Deviation here may result in unecessary, even excessive,
   repeat transmission of packets throughout the network.  Or incorrect
   duplicate table recording of packets received from non-symmetric
   neighbors may result in incomplete flooding.  In these respects,
   flooding based on the S-MPR algorithm is more complex than that based
   upon some other relay set selection algorithms.

   When multiple interfaces are present, the S-MPR SMF forwarded must
   keep some independent state for each interface with regards to
   duplicate packets.  For example, when a packet is received from a
   non-selector, one-hop symmetric neighbor, an SMF forwarder using the
   S-MPR algorithm must update its duplicate packet state with respect
   to the interface on which the packet was received.  If the SMF
   forwarder receives that same packet from a selector neighbor on a
   different interface, it MUST still forward that packet on all
   interfaces it has not received that packet from a one-hop symmetric
   neighbor.  Once a packet has been forwarded in this fashion,
   subsequent duplicates received on any interface are ignored.

A.1.  S-MPR Relay Set Selection

   (TBD - Succinct description of the relay set selection algorithm.  In

Macker, editor & SMF Design Team  Expires December 3, 2005     [Page 23]

Internet-Draft                SMF for MANET                    June 2005

   this case, nodes collect two-hop neighbor information, then
   selctexplicitly designate (via messaging) certain neighbors as

A.2.  S-MPR Forwarding Rules

   (TBD - Enumerate rules for S-MPR duplicate marking and forwarding)

A.3.  Neighborhood Discovery Requirements

   (TBD - describe any extensions (i.e., TLV fields) to the neighborhood
   discovery protocol to support the S-MPR algorithm.  For example,
   S-MPR can possibly make use of relay "wilingness" factor.  Also will
   need to specify TLV for messages sent (or broadcast) designating
   multipoint relay choices)

Macker, editor & SMF Design Team  Expires December 3, 2005     [Page 24]

Internet-Draft                SMF for MANET                    June 2005

Appendix B.  Essential Connecting Dominating Set (E-CDS) Algorithm

   The "Essential connecting dominating set" (E-CDS) algorithm [E-CDS]
   allows nodes to use two-hop topology information to appropriately
   elect _themselves_ as relay nodes to form an efficient (for flooding)
   CDS.  While this algorithm does not tend to produce as small a set of
   relay nodes (per forwarded packet) as the previously-described S-MPR
   algorithm, it is not dependent upon previous-hop information to make
   a forwarding decision; it simply forwards any received non-duplicate
   packets.  This property also allows relay nodes using the E-CDS
   algorithm to be intermixed with nodes performing only classical
   flooding.  Additionally, the semantics for multiple interface support
   are simplified as compared to S-MPR and even packets that are
   received from non-symmetric neighbors may be forwarded without
   compromising flooding efficiency or correctness.

B.1.  E-CDS Relay Set Selection

   (TBD - Succinct description of the relay set selection algorithm.  In
   this case, nodes collect two-hop neighbor information and "self-
   elect" themselves as relays as needed)

B.2.  E-CDS Forwarding Rules

   (TBD - Enumerate rules for E-CDS duplicate marking and forwarding)

B.3.  Neighborhood Discovery Requirements

   (TBD - describe an extensions (i.e., TLV fields) to the neighborhood
   discovery protocol to support the E-CDS algorithm.  For example,
   E-CDS can make use of node "degree" and/or possibly a "wilingness" or
   "reluctance" factor)

Macker, editor & SMF Design Team  Expires December 3, 2005     [Page 25]

Internet-Draft                SMF for MANET                    June 2005

Appendix C.  Multipoint Relay Connected Dominating Set (MPR-CDS)

   (TBD - Overview of MPR-CDS algorithm)

C.1.  MPR-CDS Relay Set Selection

   (TBD - Succinct description of the relay set selection algorithm.  In
   this case, nodes collect two-hop neighbor information, MPR relay
   nodes are selected and designated, and finally, some selected MPRs
   "prune" themselves based on other information)

C.2.  MPR-CDS Forwarding Rules

   (TBD - Enumerate rules for MPR-CDS duplicate marking and forwarding)

C.3.  Neighborhood Discovery Requirements

   (TBD - describe an extensions (i.e., TLV fields) to the neighborhood
   discovery protocol to support the MPR-CDS algorithm.  For example,
   MPR-CDS may use extensions similar to those of S-MPR and/or E-CDS to
   meet its needs.)

Macker, editor & SMF Design Team  Expires December 3, 2005     [Page 26]

Internet-Draft                SMF for MANET                    June 2005

Authors' Addresses

   Joseph Macker
   Code 5522
   Washington, DC  20375

   Email: macker@itd.nrl.navy.mil

   SMF Design Team

   Email: manet@ietf.org

Macker, editor & SMF Design Team  Expires December 3, 2005     [Page 27]

Internet-Draft                SMF for MANET                    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

   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

Disclaimer of Validity

   This document and the information contained herein are provided on an

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.


   Funding for the RFC Editor function is currently provided by the
   Internet Society.

Macker, editor & SMF Design Team  Expires December 3, 2005     [Page 28]

Html markup produced by rfcmarkup 1.129d, available from https://tools.ietf.org/tools/rfcmarkup/