[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
Intended status: Standards Track                         SMF Design Team
Expires: April 8, 2007                                     IETF MANET WG
                                                         October 5, 2006

               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 April 8, 2007.

Copyright Notice

   Copyright (C) The Internet Society (2006).

Macker, editor & SMF Design Team  Expires April 8, 2007         [Page 1]

Internet-Draft                SMF for MANET                 October 2006


   This document describes the Simplified Multicast Forwarding (SMF)
   protocol that provides a basic IP multicast forwarding capability
   suitable for 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 fixed-infrastructure
   networks.  SMF uses a simplified forwarding mechanism that delivers
   multicast packets to all MANET multicast receivers within a MANET
   routing area.  The core design does not use receiver specific group
   information in favor of reduced complexity and state maintenance
   within the mobile topology.  Group-specific extensions may follow in
   later specifications.  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 describes the SMF forwarding mechanisms
   in detail, its use with the MANET Neighborhood Discovery Protocol
   (NHDP), and several efficient relay set algorithms specified for use
   in conjunction with SMF.

Macker, editor & SMF Design Team  Expires April 8, 2007         [Page 2]

Internet-Draft                SMF for MANET                 October 2006

Table of Contents

   1.  Requirements Notation  . . . . . . . . . . . . . . . . . . . .  4
   2.  Introduction and Scope . . . . . . . . . . . . . . . . . . . .  5
     2.1.  Terminology  . . . . . . . . . . . . . . . . . . . . . . .  7
     2.2.  Applicability and Scope  . . . . . . . . . . . . . . . . .  7
   3.  SMF Core Design Issues . . . . . . . . . . . . . . . . . . . .  9
     3.1.  Previous Related Work  . . . . . . . . . . . . . . . . . . 10
   4.  SMF Packet Processing and Forwarding . . . . . . . . . . . . . 11
   5.  SMF Duplicate Packet Detection . . . . . . . . . . . . . . . . 14
     5.1.  SMF IPv4 Packet Identification . . . . . . . . . . . . . . 15
     5.2.  SMF IPv6 Packet Identification . . . . . . . . . . . . . . 16
       5.2.1.  IPv6 SMF-DPD Header Option Format  . . . . . . . . . . 17
   6.  Relay Set Selection  . . . . . . . . . . . . . . . . . . . . . 18
   7.  SMF Neighborhood Discovery  Requirements . . . . . . . . . . . 19
     7.1.  NHDP Description and SMF Requirements  . . . . . . . . . . 19
   8.  SMF Multicast Border Gateway Considerations  . . . . . . . . . 21
     8.1.  Forwarded Multicast Groups . . . . . . . . . . . . . . . . 21
     8.2.  Multicast Group Scoping  . . . . . . . . . . . . . . . . . 22
     8.3.  Duplicate Packet Detection Marking . . . . . . . . . . . . 23
     8.4.  Interface with Exterior Multicast Routing Protocols  . . . 23
     8.5.  Multiple Gateways  . . . . . . . . . . . . . . . . . . . . 24
     8.6.  Non-SMF MANET Nodes  . . . . . . . . . . . . . . . . . . . 25
   9.  Security Considerations  . . . . . . . . . . . . . . . . . . . 26
   10. IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 27
   11. Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . . 28
   12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 29
     12.1. Normative References . . . . . . . . . . . . . . . . . . . 29
     12.2. Informative References . . . . . . . . . . . . . . . . . . 29
   Appendix A.  Source-based Multipoint Relay (S-MPR) . . . . . . . . 31
     A.1.  S-MPR Relay Set Selection  . . . . . . . . . . . . . . . . 32
     A.2.  Neighborhood Discovery Requirements  . . . . . . . . . . . 32
   Appendix B.  Essential Connecting Dominating Set (E-CDS)
                Algorithm . . . . . . . . . . . . . . . . . . . . . . 33
     B.1.  E-CDS Relay Set Selection  . . . . . . . . . . . . . . . . 33
     B.2.  E-CDS Forwarding Rules . . . . . . . . . . . . . . . . . . 33
     B.3.  Neighborhood Discovery Requirements  . . . . . . . . . . . 34
   Appendix C.  Multipoint Relay Connected Dominating Set
                (MPR-CDS) Algorithm . . . . . . . . . . . . . . . . . 35
     C.1.  MPR-CDS Relay Set Selection  . . . . . . . . . . . . . . . 35
     C.2.  MPR-CDS Forwarding Rules . . . . . . . . . . . . . . . . . 35
     C.3.  Neighborhood Discovery Requirements  . . . . . . . . . . . 35
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 36
   Intellectual Property and Copyright Statements . . . . . . . . . . 37

Macker, editor & SMF Design Team  Expires April 8, 2007         [Page 3]

Internet-Draft                SMF for MANET                 October 2006

1.  Requirements Notation

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

Macker, editor & SMF Design Team  Expires April 8, 2007         [Page 4]

Internet-Draft                SMF for MANET                 October 2006

2.  Introduction and Scope

   Design and implementation progress has been made in demonstrating
   effective ways to flood control packets within dynamic wireless
   routing protocols.  For example, algorithms within MANET RFC 3626
   [RFC3626]and RFC 3684 [RFC3684] specify distributed methods of
   dynamically electing reduced relay sets that efficiently optimize the
   flooding of routing control packets amongst MANET routing nodes.  In
   this document, we specify the Simplified Multicast Forwarding (SMF)
   framework.  The main purpose of SMF is to adapt known efficient
   flooding designs in MANET environments and apply these mechanisms to
   IP multicast packet forwarding.  When localized efficient flooding is
   a sufficient technique, SMF can provide simplified multicast
   forwarding 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 April 8, 2007         [Page 5]

Internet-Draft                SMF for MANET                 October 2006

       ______________                _____________
      |              |              |             |
      | 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

   SMF is 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) is
   supported, eliminating the need for any relay set algorithm or
   neighborhood topology information.  However, more efficient flooding
   techniques will typically 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 and running code exist that makes 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 additional relay set
   algorithms or extensions may be specified in the future for use with

   Dynamic neighborhood topology information is often needed by
   distributed relay set algorithms to determine and maintain an
   optimized set of forwarding nodes.  It is generally expected that
   neighborhood topology discovery functions will be provided by a MANET
   unicast routing protocol or a MANET NeighborHood Discovery Protocol
   (NHDP) implementation running in concurrence with SMF.  This
   specification does not preclude a lower link layer from providing the
   necessary neighborhood information through an enhanced interface.

Macker, editor & SMF Design Team  Expires April 8, 2007         [Page 6]

Internet-Draft                SMF for MANET                 October 2006

   Different distributed relay set algorithms and associated forwarding
   decision logic can have differing neighborhood discovery and
   signaling demands.  This document states specific requirements for
   neighborhood discovery with respect to the forwarding process and
   relay set selection algorithms described herein and relies on the
   MANET NHDP specification to support operation independent of any
   MANET unicast protocol and any lower layer information.  As
   mentioned, the CF mode can be supported with or without neighborhood
   information or related discovery.

2.1.  Terminology

      MANET : Mobile Ad hoc Network

      SMF : Simplified Multicast Forwarding

      CF : Classical Flooding

      CDS : Connected Dominating Set

      MCDS : Minimum Connected Domination Set

      MPR : Multi-point Relay

      DPD: Duplicate Packet Detection

      NHDP: Neighborhood Discovery Protocol

2.2.  Applicability and Scope

   A basic packet forwarding service that reaches all destinations
   participating within a MANET area can provide a useful group
   communication mechanism for an application layer.  While the design
   requirements for this are similar to those needed by the control
   plane of many MANET unicast routing protocol layers, it is desirable
   to provide a more general IP multicast forwarding function for use by
   a variety of applications.  This can be useful for some multicast
   application flows that are global in scope but also is useful for
   site-scoped multicast applications and data flows within a MANET
   routing area.  There are a number of application areas that could
   take advantage of a simple site-scoped multicast forwarding service
   within a MANET routing region (e.g., multimedia streaming, peer-to-
   peer middleware multicasting, auto-configuration, and multi-hop
   discovery services).

   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

Macker, editor & SMF Design Team  Expires April 8, 2007         [Page 7]

Internet-Draft                SMF for MANET                 October 2006

   traffic transmission and reception with standard network layer
   semantics.  Also, a multicast border gateway or proxying mechanism
   MUST be used when interoperating with other IP multicast routing such
   as that for fixed-infrastructure networks (e.g., PIM).  In present
   experiments, proxying methods have been used to enable some gateway
   functionality at MANET border gateways operating with external IP
   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.

Macker, editor & SMF Design Team  Expires April 8, 2007         [Page 8]

Internet-Draft                SMF for MANET                 October 2006

3.  SMF Core Design Issues

   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 a 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
   networks, direct contention and interference is often correlated
   beyond a one-hop neighbor link interface.  Reducing unnecessary
   channel contention within a MANET can 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 can also results in decreased robustness of packet
   delivery within a mobile topology.  The scenario and system dependent
   design tradeoff between relay efficiency and delivery robustness
   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 specification 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 should be
   transparently supported by SMF's best effort delivery mechanism.  The
   core design scope of SMF is to define a DPD mechanism, support simple
   CF-based forwarding, and define the use of reduced relay set
   algorithms for increased efficiency.

   At a theoretic level, work in the area of minimizing packet
   forwarders, or relay node sets, is sometimes 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 MANET relay set selection must
   also consider distributed and dynamic operation.  To better explain
   the design requirements, we formulated the following characteristics
   desired of an effective MANET flooding algorithm for use in SMF:

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

Macker, editor & SMF Design Team  Expires April 8, 2007         [Page 9]

Internet-Draft                SMF for MANET                 October 2006

   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.

3.1.  Previous Related Work

   Previous 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.  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:

   1.  protocol state maintenance

   2.  duplicate packet detection mechanisms

   3.  packet processing requirements and overhead

   4.  expected traffic distribution patterns

   5.  protocol signaling requirements

   6.  delivery robustness requirements

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 10]

Internet-Draft                SMF for MANET                 October 2006

4.  SMF Packet Processing and Forwarding

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

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

   2.  Reception and processing of inbound packets on a specific network

   In the case that sequence-based DPD as described in Section 5 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).  However, 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 that "per source/
   destination" identification 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 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 routers 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 MANET routers of a contiguous
   MANET area, 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_ROUTERS"
   (TBD) and "ALL_IPv6_MANET_ROUTERS" (TBD).  This document does not
   support transmissions to any directed broadcast address ranges.
   Minimally SMF SHALL forward, as instructed by the the relay set
   selection algorithm, unique (non-duplicate) packets received for
   these well-known group addresses when the TTL or hop count value in

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 11]

Internet-Draft                SMF for MANET                 October 2006

   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
   possibly through a implementation of 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.  Link Local multicast packets MUST NOT be forwarded

   3.  Incoming 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.

   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, dependent upon
   DPD results, only if the SMF implementation is configured to perform
   classical flooding (CF) of IP multicast packets.  Otherwise, the
   forwarding decision may be controlled using additional information.
   Neighborhood discovery protocols coupled with the Source-based Multi-
   Point Relay (S-MPR) or other CDS selection algorithms described later
   MAY be used to determine the local host's status with respect to
   forwarding.  For example, algorithms may control forwarding based on
   a relay set election and previous hop indentifier (e.g.  S-MPR
   forwarding), while others may designate the local host as a forwarder
   of all neighbor packets based on the neighborhood broadcast topology
   (e.g.  Essential CDS (E-CDS)).

   DPD is a fundamental and critical portion of the SMF forwarding
   process.  In general, detection of received duplicate packets is
   necessary to avoid forwarding the same packet multiple times.
   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

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 12]

Internet-Draft                SMF for MANET                 October 2006

   Appendices of his document.  The details for these classes of
   algorithms may also apply to other similar algorithms.

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 13]

Internet-Draft                SMF for MANET                 October 2006

5.  SMF Duplicate Packet Detection

   One important design difference between routing for MANET interfaces
   and classical infrastructure network interfaces is that forwarding a
   packet via the same physical interface that it arrived upon is a
   normal operation.  This operation is often disallowed or discouraged
   in many multicast routing designs to avoid possible looping.
   Similarly, any Reverse Path Forwarding (RPF) logic used may need 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 may be forwarded out the same physical interface upon which
   they arrived and nodes can 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 computational
   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 minimum duration of any timeout delay is a

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 14]

Internet-Draft                SMF for MANET                 October 2006

   function of expected possible network traversal time, roughly
   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 DPD cache is similarly governed and is also a function of the
   maximum expected packet rate.  It should be noted that less stateful
   bitmask approaches to marking packet status can be used by using a
   contiguous space of sequence numbers rather than explicit lists of
   arbitrary packet identifiers.

   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.

5.1.  SMF IPv4 Packet Identification

   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 that can serve as a "packetIdentifier" for
   SMF purposes.  Unfortunately, in present operating system networking
   kernels, the IP ID 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.  This process will also need to
   recalculate and replace a proper IP header checksum for the modified
   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 fortunately, IPSec 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

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 15]

Internet-Draft                SMF for MANET                 October 2006

   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 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::[SPI::]packetIdentifier> combination against a
   history of received packet identifiers.  Note some forwarding
   algorithms may require that unique packets are noted when received
   from certain neighbor nodes regardless of whether the packets are
   forwarded.  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 has been demonstrated in running 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 the use and interpretation of the field is known to
   be inconsistent across operating systems.  The IPv4 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.  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.

5.2.  SMF IPv6 Packet Identification

   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 can be exploited for DPD.  SMF
   defines two methods for IPv6 use:

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 16]

Internet-Draft                SMF for MANET                 October 2006

   1.  a hop-by-hop DPD options header, and

   2.  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 multicast packets.
   If the packet is _not_ IPSec encapsulated, SMF will use the IPv6
   packet header and IPv6 DPD option to form the <sourceAddress::
   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.  Again, 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.

5.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.  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 padding.

       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 April 8, 2007        [Page 17]

Internet-Draft                SMF for MANET                 October 2006

6.  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 by the same forwarding

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

   Here is a recommended criteria list for relay set selection algorithm

   1.  Robust with respect to mobility or other network dynamics

   2.  Minimal signaling requirements for neighborhood discovery and/or

   3.  Support for preference levels 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 April 8, 2007        [Page 18]

Internet-Draft                SMF for MANET                 October 2006

7.  SMF Neighborhood Discovery  Requirements

   In absence of a compatible, coexisting unicast routing protocol or
   MAC layer protocol that provides neighborhood toplogy information
   sufficient for relay set selection, this section defines the issues
   and additional requirements for a MANET Neighborhood Discovery
   Protocol (NHDP) that MAY be operational between SMF nodes.

   With respect to neighborhood topology knowledge and/or discovery,
   there are three basic modes of SMF operation:

   1.  Classical Flooding (CF) mode: with no requirements for discovery
       or knowledge of neighborhood topology,

   2.  External CDS control mode: an external process dynamically
       determines the local SMF relay status (e.g., SMF prototypes have
       leveraged neighborhood toplogy information collected by MANET
       unicast routing protocols such as OLSRv2 or Manet-OSPF ), and

   3.  Independent CDS control mode: SMF uses the MANET Neighborhood
       Discovery Protocol (NHDP) [NHDP] to collect localized link
       information required for the various CDS algorithm modes
       discussed in the Appendices.

   We have previously discussed modes 1 and 2.  This section will
   describe mode 3, using NHDP to support CDS relay set capability
   independent of any MANET unicast routing protocol process.  This
   design uses and is consistent with the Generalized MANET Packet/
   Message Format [PacketBB] and NHDP protocol work in progress within
   the MANET WG.

7.1.  NHDP Description and SMF Requirements

   Core NHDP messages and the neighborhood information base are
   described separately within the NHDP specification (ref).  In this
   mode, SMF uses and relies upon an implementation of NHDP.  The NHDP
   protocol provides the following basic functions:

   1.  1-hop neighbor link sensing: maintaining neighbor lists and
       performing a basic bidirectionality check of neighbor links

   2.  2-hop Neighborhood Discovery: collecting 2-hop bidirectional
       neighborhood information and any information relevant to relay
       set election

   3.  The collection and maintenance of the above information across
       multiple interfaces.

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 19]

Internet-Draft                SMF for MANET                 October 2006

   4.  Relay Set Signaling: signal relay set selection to neighbor nodes
       if the relay set algorithm requires such information

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 20]

Internet-Draft                SMF for MANET                 October 2006

8.  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.  It is important to note that there are many issues that need to
   be resolved for this type of interconnection to successfully occur:

   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 (presently beyond scope
       of this document).

   6.  Provision for participating non-SMF nodes.

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

8.1.  Forwarded Multicast Groups

   Determining which groups should be forwarded into a MANET SMF area is
   problematic.  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 protocol so
   that MANET SMF nodes can inform attached gateways (and hence
   multicast networks) of their current group membership status.  For
   specific systems and services it may be possible to statically
   configure group membership in border gateways, but it is RECOMMENDED
   that some form of IGMP/MLD proxy or other explicit, dynamic control
   of membership be provided.  Specification of such an IGMP/MLD proxy
   protocol is beyond the scope of this document.

   Outbound traffic is less problematic.  SMF gateways can perform
   duplicate packet detection and forward non-duplicate traffic that
   meets TTL/hop limit and scoping criteria to other interfaces.

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 21]

Internet-Draft                SMF for MANET                 October 2006

   Appropriate IP multicast routing (PIM, etc) on those interfaces can
   then make further forwarding decisions with respect to the given
   traffic and its MANET source address.  Note that the presence of
   multiple gateways associated with a MANET area may create some
   additional issues.  This is further discussed in Section 8.5.

8.2.  Multicast Group Scoping

   Multicast scoping is used by network administrators to control the
   network areas which are reached by multicast packets.  This is
   usually done by configuring external interfaces of gateways in the
   border of an area to not forward multicast packets which must be kept
   within the area.  This is commonly done based on TTL of messages or
   group addresses.  These schemes are known respectively as:

   1.  TTL scoping.

   2.  Administrative scoping.

   For IPv4, network adminstrators can configure gateways with the
   appropriate TTL thresholds or administratively scoped multicast
   groups in the router's interfaces as with any traditional multicast
   router.  However, for the case of TTL scoping it must be taken into
   account that the packet could traverse multiple hops within the MANET
   SMF area before reaching the gateway.  Thus, TTL thresholds must be
   selected carefully.

   For IPv6, multicast addresses themselves include information about
   the scope of the group.  Thus, gateways in the border of an area know
   if they must forward a packet based on the IPv6 multicast group
   address.  For the case of IPv6, we recommend a MANET SMF routing area
   be designated a site.  Thus, all multicast packets in the range
   FF05::/16 will be kept within the MANET SMF area by gateways.
   Packets in any other wider range (i.e.  FF08::/16, FF0B::/16 and
   FF0E::16) will traverse gateways unless any other restrictions
   different from the scope applies.

   Given that scoping of multicast packets is performed at the area
   gateways, and given that existing scoping mechanisms are not designed
   to work with mobile routers, we assume that non-gateway SMF nodes,
   will not stop forwarding multicast data packets because of their
   scope.  That is, we assume that the whole MANET SMF area is an non-
   divisible scoping area except in the case of link-local addresses
   that are not forwarded by SMF.

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 22]

Internet-Draft                SMF for MANET                 October 2006

8.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 into the MANET area.  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 already have the option applied.  If this option has been
   applied, this indicates the packet has already been marked for
   potential handling by SMF relays.  Similarly, IP packets that have
   been encapsulated with IPSec may also be treated as appropriately
   marked for DPD and may be forwarded without modification.  Both of
   these indicators (the IPv6 SMF DPD option and IPSec encapsulation)
   provide the side benefit for the gateway to explicitly determine if
   the packet has already been marked.  In this case, the gateway can
   use the packet identification field to ensure it is not re-injecting
   a duplicate packet into the MANET area.  For IPv4 packets that are
   not IPSec encapsulated, 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 if a multicast routing
   loop has occurred.  If multiple multicast gateways are envisioned,
   additional considerations must be taken into account and solutions
   are considered out of scope for this document.  See Section 8.5 for
   more discussion of related issues.

8.4.  Interface with Exterior Multicast Routing Protocols

   The traditional operation of multicast routing protocols is tightly
   integrated with the group membership function.  Leaf routers are
   configured to periodically gather group membership information, while
   intermediate routers conspire to create multicast trees connecting
   routers with directly-connected multicast sources and routers with
   active multicast receivers.  In the concrete case of SMF, we can
   consider gateways as leaf routers.  Mechanisms for multicast sources
   and receivers to interoperate with gateways over the multihop MANET
   SMF area as if they were directly connected to the router need to be
   defined.  The following issues need to be addressed:

   1.  Mechanism by which gateways gather membership information.

   2.  Mechanism by which multicast sources are known by the gateway.

   3.  Exchange of exterior routing protocol messages across the MANET
       area if the MANET area is to provide transit connectivity for
       multicast traffic.

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 23]

Internet-Draft                SMF for MANET                 October 2006

   It is beyond the scope of this document to address implementation
   solutions to these issues.  As described in Section 8.1, IGMP/MLD
   proxy mechanisms can be deployed to address some of these issues.
   Similarly, exterior routing protocol messages could be tunneled or
   conveyed across the MANET area.  But, because MANET areas are multi-
   hop and potentially unreliable, as opposed to the single-hop LAN
   interconnection that neighboring IP Multicast routers might typically
   enjoy, additional provisions may be required to achieve successful

   The need for the gateway to receive traffic from recognized multicast
   sources within the MANET SMF area is important to achieve a smooth
   interworking with existing routing protocols.  For instance,
   protocols like PIM-SM, a commonly used multicast protocol, require
   routers with locally attached multicast sources to register them to
   the Rendezvous Point (RP) so that other people can join the multicast
   tree.  In addition, if those sources are not advertised to other
   autonomous systems (AS) using MSDP, receivers in those external
   networks are not able to join the multicast tree for that source.

8.5.  Multiple Gateways

   A MANET might be deployed with multiple participating nodes having
   connectivity to external (to the MANET), fixed-infrastructure
   networks.  Allowing multiple nodes to forward multicast traffic to/
   from the MANET area can be benefitial since it can increase
   reliability, and provide better service.  For example, if the MANET
   area were to fragment with different MANET nodes maintaining
   connectivity to different gateways, multicast service could still
   continue successfully.  But, the case of multiple gateways connecting
   a MANET area to external networks presents several challenges for

   1.  Detection/sequencing of duplicate unmarked IPv4 or IPv6 (without
       IPSec encapsulation or DPD option) packets possibly injected by
       multiple gateways.

   2.  Source-based relay algorithms handling of duplicate traffic
       injected by multiple gateways.

   3.  Determination of which gateway(s) will forward outbound multicast

   4.  Additional challenges with interfaces to exterior multicast
       routing protocols.

   One of the most obvious issues is when multiple gateways are present
   and may be alternatively (due to route changes) or simultaneously

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 24]

Internet-Draft                SMF for MANET                 October 2006

   injecting traffic into the MANET area that has not been previously
   marked for SMF DPD.  Different gateways would not be able to
   implicitly synchronize sequencing of injected traffic since they may
   not receive exactly the same messages due to packet losses.  While
   not covered in this document, an approach needs to be identified to
   allow multiple gateways to properly mark traffic that is being
   injected or carefully control that only one gateway is exclusively
   injecting a given "flow" of multicast traffic into the MANET area.
   Related to this, when source-based relay algorithms such as S-MPR are
   used, the efficiency or correctness of the algorithm may be
   compromised when multiple sources inject the same traffic into a
   MANET area.  Multiple solutions to these gateway issues are possible
   and detailed solution proposals are considered out of scope of the
   present document.

8.6.  Non-SMF MANET Nodes

   There may be scenarios in which some MANET nodes may not wish to run
   the SMF protocol and/or conduct forwarding, but they are interested
   in receiving multicast data.  For example, a MANET service might be
   deployed that is accessible to wireless edge devices that do not
   participate in MANET routing and/or SMF forwarding operation.  These
   devices include:

   1.  Devices that opportunistically receive multicast traffic due to
       proximity with SMF relays.

   2.  Devices that participate in NHDP (directly or via routing
       protocol signaling) but do not forward traffic.

   Note there is no guarantee of traffic delivery with category 1 above,
   so it is RECOMMENDED that nodes participate in NHDP when possible.
   Such devices may also transmit multicast traffic, but it is important
   to note that SMF areas using source-specific relay set algorithms
   such as (S-MPR) may not forward such traffic.  These devices SHOULD
   also listen for any IGMP/MLD Queries that are provided and transmit
   IGMP/MLD Reports for groups they have joined per usual IP Multicast
   operation.  While it is not in the scope of this document, IGMP/MLD
   proxy mechanisms may be in place to convey group membership
   information to any border gateways or intermediate systems providing
   IP Multicast routing functions.

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 25]

Internet-Draft                SMF for MANET                 October 2006

9.  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 April 8, 2007        [Page 26]

Internet-Draft                SMF for MANET                 October 2006

10.  IANA Considerations

   There are number of discussions within this SMF specification 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
   published.  These IANA considerations may in common or may be handed
   in comjunction with other MANET protocol efforts including the
   General Message Format specification and potentially common
   neighborhood discovery protocol considerations.

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 27]

Internet-Draft                SMF for MANET                 October 2006

11.  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 the related individuals.  Some of
   the contributors who have been involved in document content editing
   or discussions are listed below.  We appreciate input from others we
   may have missed in this list as well.

      SMF Design Team Contributors:

      Brian Adamson

      Ian Chakeres

      Thomas Clausen

      Justin Dean

      Brian Haberman

      Charles Perkins

      Pedro Ruiz

      Maoyu Wang

      Et al

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

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 28]

Internet-Draft                SMF for MANET                 October 2006

12.  References

12.1.  Normative References

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

   [MPR-CDS]  Adjih, C., Jacquet, P., and L. Viennot, "Computing
              Connected Dominating Sets with Multipoint Relays", Ad Hoc
              and Sensor Wireless Networks , January 2005.

   [NHDP]     Clausen, T. and et al, "Neighborhood Discovery Protocol",
              draft-ietf-manet-ndp-00, Work in progress , July 2006.

   [OLSRv2]   Clausen, T. and et al, "Optimized Link State Routing
              Protocol version 2", draft-ietf-manet-olsrv2-00, Work in
              progress , March 2006.

              Clausen, T. and et al, "Generalized MANET Packet/Message
              Format", draft-ietf-manet-packetbb-00, Work in progress ,
              March 2006.

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

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

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

12.2.  Informative References

   [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

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 29]

Internet-Draft                SMF for MANET                 October 2006

              ACM Mobicom 99 , 1999.

   [RFC2901]  Macker, JP. and MS. Corson, "Mobile Ad hoc Networking
              (MANET): Routing Protocol Performance Issues and
              Evaluation Considerations", 1999.

   [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 April 8, 2007        [Page 30]

Internet-Draft                SMF for MANET                 October 2006

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.

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 31]

Internet-Draft                SMF for MANET                 October 2006

A.1.  S-MPR Relay Set Selection

   If SMF is operating S-MPR relay set election independent of
   coexistent OLSR operation, based upon NHDP mechanisms, the election
   algorithm defined within RFC3626 [RFC3626] should be used.

A.2.  Neighborhood Discovery Requirements

   S-MPR election operation requires 2-hop neighbor knowledge as
   provided by the NHDP protocol[NHDP] or as available from external
   sources.  MPRs are dynamically selected by each node and selections
   MUST be advertised and dynamically updated within the SMF NDP or
   equivalent protocol.  In this mode, the MPR specific TLVs defined in
   OLSRv2 [OLSRv2]are also required to be implemented by NHDP.

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 32]

Internet-Draft                SMF for MANET                 October 2006

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

   The "Essential Connected 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

   This section provides a short description of the E-CDS based relay
   set selection algorithm and is based upon Richard Ogier's original
   summary within [E-CDS].  This was originally discussed in the context
   of forming partial adjacencies and efficient flooding for MANET-OSPF
   work but its core algorithm is applied here.

   E-CDS requires two-hop neighbor information collected through the
   SMF-NDP or other process.  Each router has a Router Identifier (may
   be represented by an interface address) and Router Priority value.
   The Router Priority value may be dynamic and represent such metrics
   as node degree.  The fundamental election steps are as follows:

   1.  If an SMF node has a higher (Router Priority, Router ID) than all
       of its symmetric neighbors, it elects itself to the relay set.

   2.  Else, if there does not exist a path from neighbor j with largest
       (Router Priority, Router ID) to some other neighbor, via
       neighbors with larger values of (Router Priority, Router ID),
       then it elects itself to the relay set.

   The basic form of E-CDS described and applied within this
   specification does not at present define redundant relay set election
   but such capability is supported by the E-CDS design.

B.2.  E-CDS Forwarding Rules

   E-CDS forwarding is quite simple and straightforward.  As mentioned,
   there is no need to check previous hop information during forwarding.
   Upon electing itself as an E-CDS relay set forwarder, SMF nodes
   perform DPD functions and forward all ranges of non-duplicative

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 33]

Internet-Draft                SMF for MANET                 October 2006

   multicast traffic allowed by the present forwarding policy.

B.3.  Neighborhood Discovery Requirements

   To support functions required by the core E_CDS relay set algorithm
   the following TLV is required to be transmitted by each node within a
   NHDP HELLO message:

   *Router Priority*: type=SMF_ROUTER_PRIORITY, length=1, value =

   For E-CDS operation, some value of SMF_ROUTER_PRIORITY must be given
   or assumed for each address in the <address-block> portion of the
   SMF_HELLO message.  If a SMF_HELLO message originator does not
   provide a SMF_ROUTER_PRIORITY value for given address(es), a default
   value SMF_RPRI_DEFAULT=(TBD) should be assumed.  Local determination
   of a node SMF_ROUTER_PRIORITY value can be done in multiple ways as
   described in the [E-CDS].  An early implementation of SMF and E-CDS
   has used node degree computed during neighbor discovery, yet it is
   still unclear if this is the best method.  Unlike the MPR method, the
   E-CDS is a self-electing algorithm.  SMF_ROUTER_PRIORITY needs to be
   shared with all immediate neighbor nodes and 2-hop neighbor knowledge
   is needed during the self election process.  Further algorithm
   examples and details are covered in the Appendices.

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 34]

Internet-Draft                SMF for MANET                 October 2006

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

   The MPR-CDS algorithm is an extension to the basic MPR election
   algorithm and results in a shared relay set that forms a CDS.  Its
   forwarding rules within SMF are non-dependent upon previous hop
   information similar to E-CDS.

C.1.  MPR-CDS Relay Set Selection

   An overview of the the MPR-CDS selection algorithm is provided in
   [MPR-CDS].  The basic requirements for election are similar to the
   basic MPR algorithm with the addtion that some node ordering
   knowledge is required.  This is similar to the E-CDS requirement and
   can be based upon node IP address or some other unique router
   identifier.  The rules for election are as follows:

      A node decides it is in the relay set if:

   1.  the node is smaller than all its neighbors (Rule 1)

   2.  or the node is an MPR of its smallest neighbor (Rule 2)

C.2.  MPR-CDS Forwarding Rules

   MPR-CDS forwarding are quite simple and straightforward.  As with
   E-CDS, there is no need to check previous hop information during
   forwarding.  Upon electing itself as a MPR-CDS relay set forwarder,
   SMF nodes perform DPD functions and forward all ranges of multicast
   traffic allowed.

C.3.  Neighborhood Discovery Requirements

   No additional discovery requirements are needed beyond the basic MPR-
   related TLVs already discussed.

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 35]

Internet-Draft                SMF for MANET                 October 2006

Authors' Addresses

   Joseph Macker
   Washington, DC  20375

   Email: macker@itd.nrl.navy.mil

   SMF Design Team

   Email: manet@ietf.org

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 36]

Internet-Draft                SMF for MANET                 October 2006

Full Copyright Statement

   Copyright (C) The Internet Society (2006).

   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

Intellectual Property

   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


   Funding for the RFC Editor function is provided by the IETF
   Administrative Support Activity (IASA).

Macker, editor & SMF Design Team  Expires April 8, 2007        [Page 37]

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