[Docs] [txt|pdf|xml|html] [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: Experimental                            SMF Design Team
Expires: May 7, 2009                                       IETF MANET WG
                                                        November 3, 2008


               Simplified Multicast Forwarding for MANET
                        draft-ietf-manet-smf-08

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

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

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

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

   This Internet-Draft will expire on May 7, 2009.

Abstract

   This document describes a Simplified Multicast Forwarding (SMF)
   mechanism that provides basic IP multicast forwarding suitable for
   wireless mesh and mobile ad hoc network (MANET) use.  SMF specifies
   techniques for multicast duplicate packet detection (DPD) to assist
   the forwarding process.  SMF also specifies DPD maintenance and
   checking operations for with both IPv4 and IPv6.  SMF also specifies
   the optional use of reduced relay sets for efficient MANET multicast
   data distribution within a mesh topology.  The document describes
   interactions with other protocols and multiple deployment approaches.
   Distributed algorithms for selecting reduced relay sets and related
   discussion are provided in the Appendices.  Basic issues relating to



Macker, editor & SMF Design Team  Expires May 7, 2009           [Page 1]


Internet-Draft                SMF for MANET                November 2008


   the operation of multicast MANET border routers are discussed but
   ongoing work remains in this area beyond the scope of this document.


Table of Contents

   1.  Requirements Notation  . . . . . . . . . . . . . . . . . . . .  4
   2.  Introduction and Scope . . . . . . . . . . . . . . . . . . . .  4
     2.1.  Abbreviations  . . . . . . . . . . . . . . . . . . . . . .  6
   3.  SMF Applicability  . . . . . . . . . . . . . . . . . . . . . .  6
   4.  SMF Packet Processing and Forwarding . . . . . . . . . . . . .  7
   5.  SMF Duplicate Packet Detection . . . . . . . . . . . . . . . .  9
     5.1.  IPv6 Duplicate Packet Detection  . . . . . . . . . . . . . 10
       5.1.1.  IPv6 SMF-DPD Header Option . . . . . . . . . . . . . . 11
       5.1.2.  IPv6 Identification-based DPD  . . . . . . . . . . . . 13
       5.1.3.  IPv6 Hash-based DPD  . . . . . . . . . . . . . . . . . 14
     5.2.  IPv4 Duplicate Packet Detection  . . . . . . . . . . . . . 15
       5.2.1.  IPv4 Identification-based DPD  . . . . . . . . . . . . 16
       5.2.2.  IPv4 Hash-based DPD  . . . . . . . . . . . . . . . . . 17
     5.3.  Internal Hash Computation Considerations . . . . . . . . . 18
   6.  Reduced Relay Set Forwarding and Relay Selection Capability  . 19
   7.  SMF Neighborhood Discovery Requirements  . . . . . . . . . . . 21
     7.1.  SMF Relay Algorithm TLV Types  . . . . . . . . . . . . . . 22
       7.1.1.  SMF Message TLV Type . . . . . . . . . . . . . . . . . 22
       7.1.2.  SMF Address Block TLV Type . . . . . . . . . . . . . . 23
   8.  SMF Border Gateway Considerations  . . . . . . . . . . . . . . 24
     8.1.  Forwarded Multicast Groups . . . . . . . . . . . . . . . . 24
     8.2.  Multicast Group Scoping  . . . . . . . . . . . . . . . . . 25
     8.3.  Interface with Exterior Multicast Routing Protocols  . . . 26
     8.4.  Multiple Border Routers  . . . . . . . . . . . . . . . . . 27
   9.  Non-SMF MANET Node Interaction . . . . . . . . . . . . . . . . 28
   10. Security Considerations  . . . . . . . . . . . . . . . . . . . 28
   11. IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 29
     11.1. IPv6 SMF_DPD Header Extension  . . . . . . . . . . . . . . 29
     11.2. SMF Type-Length-Value  . . . . . . . . . . . . . . . . . . 30
   12. Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . . 31
   13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 32
     13.1. Normative References . . . . . . . . . . . . . . . . . . . 32
     13.2. Informative References . . . . . . . . . . . . . . . . . . 33
   Appendix A.  Essential Connecting Dominating Set (E-CDS)
                Algorithm . . . . . . . . . . . . . . . . . . . . . . 34
     A.1.  E-CDS Relay Set Selection Overview . . . . . . . . . . . . 34
     A.2.  E-CDS Forwarding Rules . . . . . . . . . . . . . . . . . . 35
     A.3.  E-CDS Neighborhood Discovery Requirements  . . . . . . . . 35
     A.4.  E-CDS Selection Algorithm  . . . . . . . . . . . . . . . . 38
   Appendix B.  Source-based Multipoint Relay (S-MPR) . . . . . . . . 39
     B.1.  S-MPR Relay Set Selection Overview . . . . . . . . . . . . 40
     B.2.  S-MPR Forwarding Rules . . . . . . . . . . . . . . . . . . 41



Macker, editor & SMF Design Team  Expires May 7, 2009           [Page 2]


Internet-Draft                SMF for MANET                November 2008


     B.3.  S-MPR Neighborhood Discovery Requirements  . . . . . . . . 42
     B.4.  S-MPR Selection Algorithm  . . . . . . . . . . . . . . . . 44
   Appendix C.  Multipoint Relay Connected Dominating Set
                (MPR-CDS) Algorithm . . . . . . . . . . . . . . . . . 45
     C.1.  MPR-CDS Relay Set Selection Overview . . . . . . . . . . . 45
     C.2.  MPR-CDS Forwarding Rules . . . . . . . . . . . . . . . . . 46
     C.3.  MPR-CDS Neighborhood Discovery Requirements  . . . . . . . 47
     C.4.  MPR-CDS Selection Algorithm  . . . . . . . . . . . . . . . 47
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 48
   Intellectual Property and Copyright Statements . . . . . . . . . . 49









































Macker, editor & SMF Design Team  Expires May 7, 2009           [Page 3]


Internet-Draft                SMF for MANET                November 2008


1.  Requirements Notation

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].


2.  Introduction and Scope

   MANET unicast routing protocol designs have demonstrated effective
   and efficient mechanisms to flood routing control plane messages
   throughout a wireless routing area.  For example, algorithms
   specified within [RFC3626] and [RFC3684] provide distributed methods
   of dynamically electing reduced relay sets that attempt to optimize
   flooding of routing control messages amongst MANET routing peers.
   Simplified Multicast Forwarding (SMF) extends efficient flooding
   concept to the data forwarding plane.  In use cases where localized,
   efficient flooding is deemed an effective technique, SMF provides an
   appropriate multicast forwarding capability.  The SMF baseline design
   is intended to provide a basic, best effort multicast forwarding
   capability that is constrained to operate within a MANET or wireless
   mesh routing region.  The main design goals of this SMF specification
   are to adapt efficient relay sets in MANET environments [RFC2901] and
   to define the needed IPv4 and IPv6 multicast duplicate packet
   detection (DPD) mechanisms to support multi-hop, packet forwarding.
   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
   self-election) will occur based on input from a neighborhood
   discovery process, and the forwarding process will often be
   determined by dynamic relay set selection.  Note the neighborhood
   discovery and/or relay set selection information MAY be obtained from
   a coexistent process (e.g., MANET unicast routing protocol using
   relay sets).  In some cases, the forwarding decision for a packet can
   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 May 7, 2009           [Page 4]


Internet-Draft                SMF for MANET                November 2008


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

                      Figure 1: SMF Node Architecture

   Interoperable SMF implementations MUST use a common DPD approach and
   be able to process the header options defined in this document for
   IPv6 operation.  We define Classical Flooding (CF), as the simplest
   case of SMF multicast forwarding.  With CF, each SMF router forwards
   each received forwardable multicast packet once.  In this case, the
   need for any relay set selection or neighborhood topology information
   is eliminated but DPD functionality is still required.  While SMF
   supports a CF mode the use of more efficient relay set modes is
   RECOMMENDED to reduce contention and congestion caused by unnecessary
   packet retransmissions [NTSC99].  An efficient, reduced relay set is
   realized by selecting and maintaining a _subset_ of all possible SMF
   routers in a MANET routing region.  Known relay set selection
   algorithms have demonstrated the ability to provide and maintain a
   dynamic distribution mesh for forwarding user multicast data [MDC04].
   A few such relay set selection algorithms are described in the
   Appendices of this document and the basic designs borrow directly
   from previously documented IETF work.  SMF relay set configuration is
   extensible and an additional relay set algorithms or extensions can
   be accommodated for future use.

   Determining and maintaining an optimized set of relay (forwarding)
   nodes generally requires dynamic neighborhood topology information.
   Neighborhood topology discovery functions MAY be externally provided
   by a MANET unicast routing protocol or by using the MANET
   NeighborHood Discovery Protocol (NHDP) [NHDP] running in concurrence
   with SMF.  Additionally, this specification allows alternative
   processes that may be deemed more effective (e.g., lower layer
   wireless interface) to provide the necessary neighborhood information



Macker, editor & SMF Design Team  Expires May 7, 2009           [Page 5]


Internet-Draft                SMF for MANET                November 2008


   to support relay set election.  Fundamentally, an SMF implementation
   SHOULD provide the ability for multicast forwarding state to be
   dynamically managed per operating network interface.  Some of the
   relay state maintenance options and interactions are outlined later
   in Section 6.  This document states specific requirements for
   neighborhood discovery with respect to the forwarding process and the
   relay set selection algorithms described herein.  In the absence of a
   MANET unicast protocol or lower layer information interface, SMF
   relies on the MANET NHDP specification to assist in IP layer 2-hop
   neighborhood state discovery and maintenance for relay set election
   except in the case of CF operation.  A "SMF_RELAY_ALG" Message TLV
   type (per [PacketBB]) is defined for use with the NHDP protocol.  It
   is RECOMMENDED that all nodes performing SMF operation include this
   TLV type in their NHDP_HELLO messages when operating with NHDP.  This
   capability allows for nodes participating in SMF to be explicitly
   identified along with their respective dynamic relay set algorithm.

2.1.  Abbreviations

   The following abbreviations are used throughout this document:

            +--------------+---------------------------------+
            | Abbreviation | Definition                      |
            +--------------+---------------------------------+
            | MANET        | Mobile Ad hoc Network           |
            | SMF          | Simplified Multicast Forwarding |
            | CF           | Classical Flooding              |
            | CDS          | Connected Dominating Set        |
            | MPR          | Multi-Point Relay               |
            | S-MPR        | Source-based MPR                |
            | MPR-CDS      | MPR-based CDS                   |
            | E-CDS        | Essential CDS                   |
            | NHDP         | Neighborhood Discovery Protocol |
            | DPD          | Duplicate Packet Detection      |
            | I-DPD        | Identification-based DPD        |
            | H-DPD        | Hash-based DPD                  |
            | HAV          | Hash-assist Value               |
            | FIB          | Forwarding Information Base     |
            | TLV          | type-length-value encoding      |
            +--------------+---------------------------------+


3.  SMF Applicability

   Within dynamic, wireless routing topologies, maintaining traditional
   forwarding trees to support a multicast routing protocol is often not
   as effective as in wired networks due the reduced reliability and
   increased dynamics of mesh topologies [MGL04] [GM99].__A basic packet



Macker, editor & SMF Design Team  Expires May 7, 2009           [Page 6]


Internet-Draft                SMF for MANET                November 2008


   forwarding service reaching all connected MANET SMF routers
   participating within a localized routing region may provide a useful
   group communication paradigm for various classes of applications.
   Applications that could take advantage of a simple multicast
   forwarding service within a MANET routing region include multimedia
   streaming, interactive group-based messaging and applications, peer-
   to-peer middleware multicasting, and multi-hop mobile discovery or
   registration services.

   Note again 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 IP network
   layer semantics (e.g., special or unnecessary encapsulation of IP
   packets should be avoided in this case).  It is important that SMF
   deployed in a localized edge network setting be able to connect and
   interoperate with existing standard multicast protocols operating
   within more conventional Internet infrastructures.  A multicast
   border router or proxy mechanism MUST be used when deployed alongside
   more fixed-infrastructure IP multicast routing such Protocol
   Independent Multicast (PIM) variants [RFC3973] and [RFC4601].  With
   present experimental implementations, proxy methods have demonstrated
   gateway functionality at MANET border routers operating with existing
   external IP multicast routing protocols.  SMF may be extended or
   combined with other mechanisms to provide increased reliability and
   group specific filtering, but the details for this are not discussed
   here.


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
       interface(s).

   The purpose of intercepting outbound, locally-generated multicast
   packets is to apply any added packet marking needed to satisfy the
   DPD requirements described later so that proper forwarding may be
   conducted.  Note that for some system configurations interception of
   outbound packets for this purpose is not necessary.

   Inbound multicast packets are received by the SMF implementation and
   processed for possible forwarding.  This document does not presently
   support forwarding of directed broadcast addresses [RFC2644].  SMF
   implementations MUST be capable of forwarding "global scope"
   multicast packets to support generic multicast application needs or



Macker, editor & SMF Design Team  Expires May 7, 2009           [Page 7]


Internet-Draft                SMF for MANET                November 2008


   to distribute designated multicast traffic ingressing the MANET
   routing region via border routers.  The multicast addresses to be
   forwarded will be maintained by an _a priori_ list or a dynamic
   forwarding information base (FIB) that MAY interact with future MANET
   dynamic group membership extensions or management functions.  There
   will also be a well-known multicast group for flooding to all SMF
   forwarders.  This multicast group is specified to contain all MANET
   SMF routers of a connected MANET routing region, so that packets
   transmitted to the multicast address associated with the group will
   be delivered to all connected SMF routers.  For IPv6, the multicast
   address is specified to be "site-local".  The name of the multicast
   group is "SL-MANET-ROUTERS".  Minimally SMF SHALL forward, as
   instructed by the relay set selection algorithm, unique (non-
   duplicate) packets received for this well-known group address when
   the TTL or hop count value in the IP header is greater than 1.  SMF
   SHALL forward all additional global scope addresses specified within
   the dynamic FIB or configured list as well.  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 SMF router interface(s) MUST NOT be
       forwarded.
   4.  Received packet frames with the MAC source address matching the
       local SMF router interface(s) MUST NOT be forwarded.
   5.  Received packets for which SMF cannot reasonably ensure temporal
       DPD uniqueness MUST NOT be forwarded.
   6.  When packets are forwarded, TTL or hop limit SHALL be decremented
       by one.

   Note that rule #3 is important because in wireless networks, the
   local SMF router 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.

   An additional processing rule also needs to be considered based upon
   a potential security threat.  As discussed further in Section 10,
   there may be concern in some SMF deployments that malicious nodes may
   conduct a denial-of-service attack by remotely "previewing" (e.g.,
   via a directional receive antenna) packets that an SMF node would be
   forwarding and conduct a "pre-play" attack by transmitting the packet
   before the SMF node would otherwise receive it but with a reduced TTL
   (or Hop Limit) field value.  This form of attack could cause an SMF
   node to create a DPD entry that would block the proper forwarding of
   the valid packet (with correct TTL) through the SMF area.  A
   RECOMMENDED approach to prevent this attack, when it is a concern,



Macker, editor & SMF Design Team  Expires May 7, 2009           [Page 8]


Internet-Draft                SMF for MANET                November 2008


   would be to cache temporal packet TTL values along with the DPD state
   (hash value(s) and/or identifier).  Then, if a subsequent matching
   (with respect to DPD) packet arrives with a _larger_ TTL value than
   the packet that was previously forwarded, then SMF should forward the
   new packet _and_ update the TTL cached with corresponding DPD state
   to the new, larger TTL value.  There may be temporal cases where SMF
   may unnecessarily forward some duplicate packets using this approach,
   but those cases are expected to be minimal and acceptable when
   compared with the potential threat outcome of denied service.

   Once these criteria have been met, an SMF implementation MUST make a
   forwarding decision dependent upon the relay set selection algorithm
   in use.  If the SMF implementation is using Classical Flooding (CF),
   the forwarding decision is implicit once DPD uniqueness is
   determined.  Otherwise, a forwarding decision depends upon the
   current interface-specific relay set state.  The descriptions of the
   relay set selection algorithms in the Appendices to this document
   specify the respective heuristics for multicast packet forwarding and
   specific DPD or other processing required to achieve correct SMF
   behavior.  For example, one class of forwarding is based upon relay
   set election status _and_ the packet's previous hop (e.g.  S-MPR
   forwarding), while other classes designate the local SMF router as a
   forwarder of all neighbor packets (e.g.  E-CDS and MPR-CDS).


5.  SMF Duplicate Packet Detection

   Duplicate packet detection (DPD) is a common requirement in MANET
   packet forwarding because packets may be transmitted out the same
   physical interface upon which they arrived and nodes may also receive
   copies of previously-transmitted packets from other forwarding
   neighbors.  SMF implementations MUST detect and avoid forwarding
   duplicate multicast packets using temporal packet identification.  It
   is RECOMMENDED this be implemented by keeping a history of recently-
   processed multicast packets for comparison to incoming packets.  For
   both IPv4 and IPv6, this document describes two basic approaches to
   multicast duplicate packet detection: header content identification-
   based (I-DPD) and hash-based (H-DPD) duplicate detection.  The two
   approaches are described for experimental purposes.  Trade-offs of
   the two approaches to DPD merit different consideration dependent
   upon the specific SMF deployment scenario.  Because of the potential
   addition of a hop-by-hop option header with IPv6, SMF deployments
   MUST be configured to use a common mechanism and DPD algorithm.  The
   main difference between IPv4 and IPv6 SMF DPD specification is the
   avoidance of any additional header options in the IPv4 case.

   For each network interface, SMF implementations MUST maintain DPD
   packet state as needed to support the forwarding heuristics of the



Macker, editor & SMF Design Team  Expires May 7, 2009           [Page 9]


Internet-Draft                SMF for MANET                November 2008


   relay set algorithm used.  The specific requirements of several relay
   set selection algorithms and their forwarding rules are described in
   the Appendices of this document.  In general this involves keeping
   track of previously forwarded packets so that duplicates are not
   forwarded, but some relay techniques (e.g., S-MPR) have additional
   considerations.

   For I-DPD, packets are identified using explicit identifiers from the
   IP header.  The specific identifier to use depends upon the IP
   protocol version and the type of packet.  For example, IPv4 [RFC0791]
   provides an "Identification" field that may assist a DPD mechanism,
   and packets that contain IPSec protocol headers also provide suitable
   packet identifiers.  Fragmented packets also provide additional
   identifiers that need to be considered.  These identifier fields are
   unique within the context of source address, destination address,
   protocol type, and/or other header fields depending upon the type of
   identifier used for DPD.  Similarly, for H-DPD, it is expected that
   packet hash values will be kept with respect to at least the source
   address to help ensure hash collision avoidance.  SMF implementations
   MUST maintain DPD history per the applicable packet flow context
   (e.g., <protocol:srcAddr:dstAddr> for DPD based upon IPv4 ID).  The
   details for I-DPD and H-DPD for different types of packets are
   described in the sections below.  In either case, this history SHOULD
   be kept long enough to span the maximum network traversal lifetime,
   MAX_PACKET_LIFETIME, of multicast packets being forwarded within an
   SMF operating area.  The required size of the DPD cache is governed
   by this timeout value and is also a function of the packet forwarding
   rates.  The DPD 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.  IPv6 Duplicate Packet Detection

   This section describes the mechanisms and options for SMF IPv6 DPD.
   The core IPv6 packet header does not provide any explicit
   identification header field that can be exploited for I-DPD.  The
   following areas are described to support IPv6 DPD:
   1.  a hop-by-hop SMF-DPD option header (with supporting identifier or
       hash assistance value),
   2.  the use of IPv6 fragment header fields for I-DPD when they exist,
   3.  the use of IPSec sequencing for I-DPD when a non-fragmented,
       IPSec header is detected, and
   4.  an H-DPD approach assisted, as needed, by the SMF-DPD option
       header.
   SMF MUST provide a DPD marking module that can insert the hop-by-hop
   IPv6 header option defined in this section.  This process MUST come
   after any source-based fragmentation that may occur with IPv6.  As
   with IPv4, SMF IPv6 DPD is presently specified to allow either a



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 10]


Internet-Draft                SMF for MANET                November 2008


   packet hash or header identification method for DPD.  An SMF
   implementation MUST be configured to operate either in H-DPD or I-DPD
   mode and perform the appropriate routines outlined in the following
   sections.

5.1.1.  IPv6 SMF-DPD Header Option

   As previously mentioned, the base IPv6 packet header does not contain
   a unique identifier suitable for DPD.  This section defines an IPv6
   Hop-by-Hop Option to serve this purpose for IPv6 I-DPD.
   Additionally, the Option defined provides for a mechanism to
   guarantee non-collision of hash values for different packets when
   H-DPD is used.  The value of the IPv6 SMF_DPD Hop-by-Hop Option Type
   is TBD.

   The first bit of the data field of the SMF-DPD option is the "H-bit"
   that determines the format of the Option Data content.  Two different
   formats are supported.  When the "H-bit" is cleared (zero value), the
   SMF-DPD format to support I-DPD operation is specified as shown in
   Figure 2 and defines the extension header in accordance with
   [RFC2460].
        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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                      ...              |0|0|0| OptType | Opt. Data Len |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |0|TidTyp|TidLen|             TaggerId (optional) ...           |
       +-+-+-+-+-+-+-+-+               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                               |            Identifier  ...
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

            Figure 2: IPv6 SMF-DPD Header Option in I-DPD mode

   The "TidType" is a 3-bit field indicating the presence and type of
   the optional "TaggerId" field.  The optional "TaggerId" is used to
   differentiate multiple ingressing border gateways that may commonly
   apply the SMF-DPD option header to packets from a particular source.
   This is provided for experimental purposes.  The following table
   lists the valid TaggerId types:












Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 11]


Internet-Draft                SMF for MANET                November 2008


   +---------+-------+-------------------------------------------------+
   | Name    | Value | Purpose                                         |
   +---------+-------+-------------------------------------------------+
   | NULL    | 0     | Indicates no "taggerId" field is present.       |
   |         |       | "TidLen" MUST also be set to ZERO.              |
   | DEFAULT | 1     | A "TaggerId" of non-specific context is         |
   |         |       | present.  "TidLen + 1" defines the length of    |
   |         |       | the TaggerId field in bytes.                    |
   | IPv4    | 2     | A "TaggerId" representing an IPv4 address is    |
   |         |       | present.  The "TidLen" MUST be set to 3.        |
   | IPv6    | 3     | A "TaggerId" representing an IPv6 address is    |
   |         |       | present.  The "TidLen" MUST be set to 15.       |
   | ExtId   | 7     | RESERVED FOR FUTURE USE (possible extended ID)  |
   +---------+-------+-------------------------------------------------+

                          Table 1: TaggerId Types

   This format allows a quick check of the "TidType" field to determine
   if a "TaggerId" field is present.  If the <TidType> is NULL, then the
   length of the DPD packet <Identifier> field corresponds to the (<Opt.
   Data Len> - 1).  If the <TidType> is non-NULL, then the length of the
   "TaggerId" field is equal to (<TidLen> - 1) and the remainder of the
   option data comprises the DPD packet <Identifier> field.  When the
   "TaggerId" field is present, the <Identifier> field can be considered
   a unique packet identifier in the context of the <taggerId:srcAddr:
   dstAddr> tuple.  When the "TaggerId" field is not present, then it is
   assumed the source host applied the SMF-DPD option and the
   <Identifier> can be considered unique in the context of the IPv6
   packet header <srcAddr:dstAddr> tuple.  IPV6 I-DPD operation details
   are described in Section 5.1.2.

   When the "H-bit" in the SMF-DPD option data is set, the data content
   value is interpreted as a Hash-Assist Value (HAV) used to facilitate
   H-DPD operation.  In this case, source hosts or ingressing gateways
   apply the SMF-DPD with a HAV only when required to differentiate the
   hash value of a new packet with respect to older packets in the
   current DPD history cache.  This helps to guarantee the uniqueness of
   generated hash values when H-DPD is used.  Additionally, this also
   avoids the added overhead of applying the SMF-DPD option header to
   every packet.  For many hash algorithms, it is expected that only
   sparse use of the SMF-DPD option may be required.  The format of the
   SMF-DPD header option for H-DPD operation is given in Figure 3.









Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 12]


Internet-Draft                SMF for MANET                November 2008


       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     ...              |0|0|0| OptType | Opt. Data Len |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |0|    Hash Assist Value (HAV) ...
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

            Figure 3: IPv6 SMF_DPD Header Option in H-DPD Mode

   The SMF-DPD option should be applied with a HAV to produce a unique
   hash digest for packets within the context of the IPv6 packet header
   <srcAddr>.  The size of the HAV field is implied by the "Opt. Data
   Len".  The appropriate size of the field depends upon the collision
   properties of the specific hash algorithm used.  More details on IPv6
   H-DPD operation are provided in Section 5.1.3.

5.1.2.  IPv6 Identification-based DPD

   The following table summarizes the IPv6 I-DPD processing approach.
   Within the table '*' indicates a don't care condition.

   +-------------+-----------+-----------+-----------------------------+
   | IPv6        | IPv6      | IPv6      | SMF IPv6 I-DPD Mode Action  |
   | Fragment    | IPSec     | I-DPD     |                             |
   | Header      | Header    | Header    |                             |
   +-------------+-----------+-----------+-----------------------------+
   | Present     | *         | *         | Use Fragment Header I-DPD   |
   |             |           |           | Check and Process for       |
   |             |           |           | Forwarding                  |
   | Not Present | Present   | *         | Use IPSec Header I-DPD      |
   |             |           |           | Check and Process for       |
   |             |           |           | Forwarding                  |
   | Present     | *         | Present   | Invalid, do not Forward     |
   | Not Present | Present   | Present   | Invalid, do not Forward     |
   | Not Present | Not       | Not       | Add I-DPD Header,and        |
   |             | Present   | Present   | Process for Forwarding      |
   | Not Present | Not       | Present   | Use I-DPD Header Check and  |
   |             | Present   |           | Process for Forwarding      |
   +-------------+-----------+-----------+-----------------------------+

                   Table 2: IPv6 I-DPD Processing Rules

   If the IPv6 multicast packet is an IPv6 fragment, SMF MUST use the
   fragment extension header fields for packet identification.  This
   identifier can be considered unique in the context of the <srcAddr:
   dstAddr> of the IP packet.  If the packet is an unfragmented IPv6
   IPSec packet, SMF MUST use IPSec fields for packet identification.



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 13]


Internet-Draft                SMF for MANET                November 2008


   The IPSec header <sequence> field can be considered a unique
   identifier in the context of the <IPSecType:srcAddr:dstAddr:SPI>
   where the "IPSecType" is either AH or ESP.  For unfragmented, non-
   IPSec, IPv6 packets, the use of the SMF DPD header option is
   necessary to support I-DPD operation.  The SMF DPD header option is
   applied in the context of the <srcAddr> of the IP packet.  End
   systems or ingressing SMF gateways are responsible for applying this
   option to support DPD.  The following table summarizes these packet
   identification types:

   +-----------+---------------------------------+---------------------+
   | IPv6      | Packet DPD ID Context           | Packet DPD ID       |
   | Packet    |                                 |                     |
   | Type      |                                 |                     |
   +-----------+---------------------------------+---------------------+
   | Fragment  | <srcAddr:dstAddr>               | <fragmentOffset:id> |
   | IPSec     | <IPSecType:srcAddr:dstAddr:SPI> | <sequence>          |
   | Packet    |                                 |                     |
   | Regular   | <[taggerId:]srcAddr:dstAddr>    | <SMF-DPD option     |
   | Packet    |                                 | header id>          |
   +-----------+---------------------------------+---------------------+

              Table 3: IPv6 I-DPD Packet Identification Types

   "IPSecType" is either Authentication Header (AH) or Encapsulating
   Security Payload (ESP).

   The "taggerId" is an optional feature of the IPv6 SMF-DPD header
   option.

5.1.3.  IPv6 Hash-based DPD

   A default hash-based DPD approach (H-DPD) for use by SMF is specified
   as follows.  An MD5 [RFC1321] hash of the non-mutable header fields,
   options fields, and data content of the IPv6 multicast packet is used
   to produce a 128-bit digest.  The lower 64 bits of this digest
   (MD5_64) is used for SMF packet identification.  The approach for
   calculating this hash value SHOULD follow the same guidelines
   described for calculating the Integrity Check Value (ICV) described
   in [RFC4302] with respect to non-mutable fields.  This approach
   should have a reasonably low probability of digest collision when
   packet headers and content are varying.  MD5 is being applied in SMF
   only to provide a low probability of collision and is not being used
   for cryptographic or authentication purposes.  A history of the
   packet hash values SHOULD be maintained within the context of the
   IPv6 packet header <srcAddr>.  This history is used by forwarding SMF
   nodes (non-ingress points) to avoid forwarding duplicates.  SMF
   ingress points (i.e., source hosts or gateways) use this history to



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 14]


Internet-Draft                SMF for MANET                November 2008


   confirm that new packets are unique with respect to their hash value.
   The Hash-assist Value (HAV) field described in Section 5.1.1 is
   provided as a differentiating field when a digest collision would
   otherwise occur.  Note that the HAV is an immutable option field and
   SMF MUST use any included H-DPD hash assist value (HAV) option header
   (see Section 5.1.1) in its hash calculation.

   If a packet results in a digest collision (i.e., by checking the
   H-DPD digest history) within the limited history kept by SMF
   forwarders, the packet should be silently dropped.  If a digest
   collision is detected at an SMF ingress point (i.e., including SMF-
   aware sources), the H-DPD option header is applied with a HAV.  The
   packet is retested for collision and the HAV is re-applied as needed
   to produce a non-colliding hash value.  The multicast packet is then
   forwarded with the added IPv6 SMF-DPD header option.

   The MD5 indexing and IPv6 HAV approaches are specified at present for
   consistency and robustness to suit experimental uses.  Future
   approaches and experimentation may discover designs tradeoffs in hash
   robustness and efficiency worth considering.  This MAY include
   reducing the maximum payload length that is processed, determining
   shorter indexes, or applying more efficient hashing algorithms.  Use
   of the HAV functionality may allow for application of "lighter-
   weight" hashing techniques that might not have been initially
   considered due to poor collision properties otherwise.  Such
   techniques could reduce packet processing overhead and memory
   requirements.

5.2.  IPv4 Duplicate Packet Detection

   This section describes the mechanisms and options for IPv4 DPD.  The
   IPv4 packet header 16-bit "Identification" field MAY be used for DPD
   assistance, but practical limitations may require alternative
   approaches in some situations.  The following areas are described to
   support IPv4 DPD::
   1.  the use of IPv4 fragment header fields for I-DPD when they exist,
   2.  the use of IPSec sequencing for I-DPD when a non-fragmented IPv4
       IPSec packet is detected, and
   3.  a H-DPD approach.
   A specific SMF-DPD marking option is not specified for IPv4 since
   header options are not as tractable for end systems as for IPv6.
   IPv4 packets from a particular source are assumed to be marked with a
   temporally unique value in the "Identification" field of the packet
   header that can serve for SMF DPD purposes.  However, in present
   operating system networking kernels, the IPv4 header "Identification"
   value is not always generated properly, especially when the "don't
   fragment" (DF) bit is set.  The IPv4 I-DPD mode of this specification
   requires that IPv4 "Identification" fields are managed reasonably by



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 15]


Internet-Draft                SMF for MANET                November 2008


   source hosts and that temporally unique values are set within the
   context of the packet header <protocol:srcAddr:dstAddr> tuple.  If
   this is not expected during an SMF deployment, then it is RECOMMENDED
   that the H-DPD method be used as a more reliable approach.

   Since IPv4 SMF does not specify an options header, the
   interoperability constraints are looser than the IPv6 version and
   forwarders may be operate with mixed H-DPD and I-DPD modes as long as
   they consistently perform the appropriate DPD routines outlined in
   the following sections.  However, it is RECOMMENDED that a deployment
   be configured with a common mode for operational consistency.

5.2.1.  IPv4 Identification-based DPD

   The following table summarizes the IPv4 I-DPD processing approach
   once a packet has passed the basic forwardable criteria described in
   earlier SMF sections.  Within the table '*' indicates a don't care
   condition.

   +----+----+----------+---------+------------------------------------+
   | df | mf | fragment | IPSec   | IPv4 I-DPD Action                  |
   |    |    | offset   |         |                                    |
   +----+----+----------+---------+------------------------------------+
   | 1  | 1  | *        | *       | Invalid, Do Not Forward            |
   | 1  | 0  | nonzero  | *       | Invalid, Do Not Forward            |
   | *  | 0  | zero     | not     | Tuple I-DPD Check and Process for  |
   |    |    |          | Present | Forwarding                         |
   | *  | 0  | zero     | Present | IPSec enhanced Tuple I-DPD Check   |
   |    |    |          |         | and Process for Forwarding         |
   | 0  | 0  | nonzero  | *       | Extended Fragment Offset Tuple     |
   |    |    |          |         | I-DPD Check and Process for        |
   |    |    |          |         | Forwarding                         |
   | 0  | 1  | zero or  | *       | Extended Fragment Offset Tuple     |
   |    |    | nonzero  |         | I-DPD Check and Process for        |
   |    |    |          |         | Forwarding                         |
   +----+----+----------+---------+------------------------------------+

                   Table 4: IPv4 I-DPD Processing Rules

   For performance reasons, IPv4 network fragmentation and reassembly of
   multicast packets within wireless MANET networks should be minimized,
   yet SMF provides the forwarding of fragments when they occur.  If the
   IPv4 multicast packet is a fragment, SMF MUST use the fragmentation
   header fields for packet identification.  This identification can be
   considered temporally unique in the context of the <protocol:srcAddr:
   dstAddr> of the IPv4 packet.  If the packet is an unfragmented IPv4
   IPSec packet, SMF MUST use IPSec fields for packet identification.
   The IPSec header <sequence> field can be considered a unique



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 16]


Internet-Draft                SMF for MANET                November 2008


   identifier in the context of the <IPSecType:srcAddr:dstAddr:SPI>
   where the "IPSecType" is either AH or ESP.  Finally, for
   unfragmented, non-IPSec, IPv4 packets, the "Identification" field can
   be used for I-DPD purposes.  The "Identification" field can be
   considered unique in the context of the IPv4 <protocol:scrAddr:
   dstAddr> tuple.  The following table summarizes these packet
   identification types:

   +-----------+---------------------------------+---------------------+
   | IPv4      | Packet Identification Context   | Packet Identifier   |
   | Packet    |                                 |                     |
   | Type      |                                 |                     |
   +-----------+---------------------------------+---------------------+
   | Fragment  | <protocol:srcAddr:dstAddr>      | <fragmentOffset:id> |
   | IPSec     | <IPSecType:srcAddr:dstAddr:SPI> | <sequence>          |
   | Packet    |                                 |                     |
   | Regular   | <protocol:srcAddr:dstAddr>      | <id>                |
   | Packet    |                                 |                     |
   +-----------+---------------------------------+---------------------+

              Table 5: IPv4 I-DPD Packet Identification Types

   "IPSecType" is either Authentication Header (AH) or Encapsulating
   Security Payload (ESP).

   The limited size (16 bits) of the IPv4 header "Identification" field
   may result in more frequent value field wrapping, particularly if a
   common sequence space is used by a source for multiple destinations.
   If I-DPD operation is required, the use of the "internal hashing"
   technique described in Section 5.3 may mitigate this limitation of
   the IPv4 "Identification" field for SMF DPD.  In this case the
   "internal hash" value would be concatenated with the "Identification"
   value for I-DPD operation.

5.2.2.  IPv4 Hash-based DPD

   To ensure consistent IPv4 H-DPD operation among SMF nodes, a default
   hashing approach is specified.  This is similar to that specified for
   IPv6, but the H-DPD header option with HAV is not considered.  SMF
   MUST perform an MD5 [RFC1321] hash of the immutable header fields,
   option fields and data content of the IPv4 multicast packet resulting
   in a 128-bit digest.  The lower 64 bits of this digest (MD5_64) is
   used for SMF packet identification.  The approach for calculating the
   hash value SHOULD follow the same guidelines described for
   calculating the Integrity Check Value (ICV) described in [RFC4302]
   with respect to non-mutable fields.  A history of the packet hash
   values SHOULD be maintained in the context of <protocol:srcAddr:
   dstAddr>.  The context for IPv4 is more specific than that of IPv6



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 17]


Internet-Draft                SMF for MANET                November 2008


   since the SMF-DPD HAV cannot be employed to mitigate hash collisions.

   The MD5 hash is specified at present for consistency and robustness.
   Future approaches and experimentation may discover designs tradeoffs
   in hash robustness and efficiency worth considering for future
   versions of SMF.  This MAY include reducing the packet payload length
   that is processed, determining shorter indexes, or applying a more
   efficient hashing algorithm.

5.3.  Internal Hash Computation Considerations

   Forwarding protocols that use DPD techniques, such as SMF, may be
   vulnerable to denial-of-service (DoS) attacks based on spoofing
   packets with apparently valid packet identifier fields.  Such a
   consideration is pointed out in Section 10.  In wireless
   environments, where SMF will most likely be used, the opportunity for
   such attacks is more prevalent than in wired networks.  In the case
   of IPv4 packets, fragmented IP packets or packets with IPSec headers
   applied, the DPD "identifier" of potential future packets that might
   be forwarded is highly predictable and easily subject to denial-of-
   service attacks against forwarding.  A RECOMMENDED technique to
   counter this concern is for SMF implementations to generate an
   "internal" hash value that is concatenated with the explicit I-DPD
   packet identifier to form a unique identifier that is a function of
   the packet content as well as the visible identifier.  SMF
   implementations could seed their hash generation with a random value
   to make it unlikely that an external observer could guess how to
   spoof packets used in a denial-of-service attack against forwarding.
   Since the hash computation and state is kept completely internal to
   SMF nodes, the cryptographic properties of this hashing would not
   need to be extensive and thus possibly of low complexity.
   Experimental implementations may determine that a lightweight hash of
   even only portions of packets may suffice to serve this purpose.

   For IPv4 I-DPD based on the limited 16-bit IP header "Identification"
   field, it is possible that use of this "internal hash" technique may
   also enhance I-DPD performance in cases where the IPv4
   "Identification" field may frequently wrap due to sources supporting
   high data rate flows.

   While H-DPD is not as readily susceptible to this form of DoS attack,
   it is possible that a sophisticated adversary could use side
   information to construct spoofing packets to mislead forwarders using
   a well-known hash algorithm.  Thus, similarly, a separate "internal"
   hash value could be concatenated with the well-known hash value to
   alleviate this security concern.





Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 18]


Internet-Draft                SMF for MANET                November 2008


6.  Reduced Relay Set Forwarding and Relay Selection Capability

   SMF implementations MUST support CF as a basic forwarding mechanism
   when reduced relay set information is not available or not selected
   for operation.  In CF mode, each node transmits a locally generated
   or newly received forwardable packet exactly once.  The DPD
   techniques described in Section 5 are critical to proper operation
   and prevent duplicate packet retransmissions by the same forwarding
   node.

   A goal of SMF is to apply reduced relay sets for more efficient
   multicast dissemination within dynamic topologies.  To accomplish
   this SMF MUST support the ability to modify its multicast packet
   forwarding rules based upon relay set state received dynamically
   during operation.  In this way, SMF forwarding operates effectively
   as neighbor adjacencies or multicast forwarding policies within the
   topology change.

   In early SMF experimental deployments, the relay set information has
   been derived from coexistent unicast MANET protocol coexistent
   control plane traffic flooding processes.  From this experience,
   extra pruning considerations were sometimes required when utilizing a
   relay set from a separate routing protocol process.  As an example,
   relay sets formed for the unicast control plane flooding MAY include
   additional redundancy that may not be desired for multicast
   forwarding use (e.g., biconnected CDS mesh for control plane
   purposes).

   Here is a recommended criteria list for SMF relay set selection
   algorithm candidates:

   1.  Robustness to topological dynamics and mobility
   2.  Localized election or coordination of any relay sets
   3.  Reasonable minimization of relay set size to achieve CDS given
       above constraints
   4.  Heuristic support for preference or election metrics (Better
       enables scenario-specific management of relay set)

   Some relay set algorithms meeting these 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 specifications in the future.  The Appendices in this
   document can serve as a template for the content of such potential
   future specifications.

   Figure 4 depicts a state information diagram of possible relay set
   control options.



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 19]


Internet-Draft                SMF for MANET                November 2008


                       Possible L2 Trigger/Information
                                      |
                                      |
    ______________              ______v_____         __________________
   |    MANET     |            |            |       |                  |
   | Neighborhood |            | Relay Set  |       | Other Heuristics |
   |  Discovery   |----------->| Selection  |<------| (Preference,etc) |
   |   Protocol   | neighbor   | Algorithm  |       |                  |
   |______________|   info     |____________|       |__________________|
          \                              /
           \                            /
    neighbor\                          / Dynamic Relay
      info*  \      ____________      /    Set Status
              \    |    SMF     |    / (State, {neighbor info})
               `-->| Relay Set  |<--'
                   |   State    |
                -->|____________|
               /
              /
    ______________
   |  Coexistent  |
   |    MANET     |
   |   Unicast    |
   |   Process    |
   |______________|


                  Figure 4: SMF Relay Set Control Options

   There are basically three styles of SMF operation with reduced relay
   sets:

   1.  Independent operation: SMF performs its own relay set selection
       using information from an associated MANET NHDP process.  In this
       case, NHDP messaging SHOULD be appended with additional
       [PacketBB] type-length-value (TLV) content to support SMF-
       specific requirements as discussed in Section 7 and for the
       applicable relay set algorithm described in the Appendices of
       this document or future specifications.
   2.  Operation with CDS-aware unicast routing protocol: Coexistent
       unicast routing protocol provides dynamic relay set state based
       upon its own control plane CDS or neighborhood discovery
       information.  If it is desired that the SMF data plane forwarding
       use a different relay set selection algorithm than used for the
       routing protocol control plane, then the routing protocol NHDP
       instance (if applicable) SHOULD append its messages with the
       appropriate SMF-specific TLV content (see Section 7 and the relay
       set algorithm Appendices).



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 20]


Internet-Draft                SMF for MANET                November 2008


   3.  Cross-layer Operation: SMF operates using neighborhood status and
       triggers from a cross-layer information base for dynamic relay
       set selection and maintenance (e.g., lower link layer) .


7.  SMF Neighborhood Discovery Requirements

   This section defines the requirements for use of the MANET
   Neighborhood Discovery Protocol (NHDP) [NHDP] to support SMF
   operation.  Note that basic CF forwarding requires no neighborhood
   topology knowledge since every SMF node relays all traffic while
   supporting more efficient SMF relay set operation requires the
   discovery and maintenance of dynamic neighborhood topology
   information.  The MANET NHDP protocol can provide this necessary
   information, but in some circumstances there are SMF-specific
   requirements for related NHDP use.  This can be the case for both
   "independent" SMF operation where NHDP is being used specifically to
   support SMF or when one NHDP instance is used for both for SMF and a
   coexistent MANET unicast routing protocol.

   Core NHDP messages and the resultant neighborhood information base
   are described separately within the NHDP specification.  To
   summarize, the NHDP protocol provides the following basic functions:
   1.  1-hop neighbor link sensing and bidirectionality checks of
       neighbor links,
   2.  2-hop neighborhood discovery including collection of 2-hop
       neighbors and connectivity information,
   3.  Collection and maintenance of the above information across
       multiple interfaces, and
   4.  A method for signaling SMF information throughout the 2-hop
       neighborhood such as the existence of an SMF instance and any
       related relay set selection information.

   The Appendices of this document describe a set of CDS-based relay set
   selection algorithms that can be used to achieve efficient SMF
   operation, even in dynamic, mobile networks[MDDA07].  For some of
   these algorithms, the core NHDP specification can provide all the
   necessary information to conduct relay set selection.  For others,
   NHDP messaging needs to be extended to support SMF discovery, relay
   set selection, and maintenance.  For example, the [OLSRv2]
   specification specifies TLV constructs for NHDP messages to support
   its use of the S-MPR algorithm.

   The following sub-sections specify some SMF-specific TLV types to
   support general SMF operation or to support the algorithms described
   in the Appendices to this document.  The Appendices describing each
   of the relay set algorithms also specify any additional requirements
   for NHDP to support their operation and reference the applicable TLV



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 21]


Internet-Draft                SMF for MANET                November 2008


   types as needed.

7.1.  SMF Relay Algorithm TLV Types

   This section specifies TLV types to be used within NHDP messages to
   identify the CDS relay set selection algorithm(s) in use.  Two TLV
   types are defined, one message TLV type and one address TLV type.

7.1.1.  SMF Message TLV Type

   The SMF message TLV type denoted SMF_TYPE is used to identify the
   existence of an SMF instance operating in conjunction with NHDP.
   This message type makes use of the extended type field as defined by
   [PacketBB] to convey the CDS relay set selection algorithm currently
   in use by the SMF message originator.  When NHDP is used to support
   SMF operation, the SMF_TYPE TLV, containing the extended type field
   with the appropriate value, SHOULD be included in NHDP_HELLO messages
   generated.  This allows SMF nodes to learn when neighbors are
   configured to use NHDP for information exchange including algorithm
   type and related algorithm information.  This information can be used
   to take action, such as ignoring neighbor information using
   incompatible algorithms.  It is possible that SMF neighbors MAY be
   configured differently and still operate cooperatively, but these
   cases will vary dependent upon the algorithm types designated.

   This document defines the following Message TLV typeTable 6
   conforming to [PacketBB].  Extended type field values communicate
   "Relay Algorithm Type" to other 1-hop SMF neighbors and value fields
   may contain algorithm specific information.

       +---------------+---------------------+--------------------+
       |               | packetBB TLV syntax | Field Values       |
       +---------------+---------------------+--------------------+
       | type          | <tlv-type>          | SMF_TYPE           |
       | extended type | <tlv-type-ext>      | <relayAlgorithmid> |
       | length        | <length>            | variable           |
       | value         | <value>             | variable           |
       +---------------+---------------------+--------------------+

                       Table 6: SMF Type Message TLV

   In Table 6 <relayAlgorithmId> is an 8-bit field containing a number
   0-255 representing the "Relay Algorithm Type" of the originator
   address of the corresponding NHDP message.

   Possible values for the <relayAlgorithmId> are defined in Table 7.
   The table provides value assignments, future IANA assignment spaces,
   and an experimental space.  The experimental space use MUST NOT



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 22]


Internet-Draft                SMF for MANET                November 2008


   assume uniqueness and thus should not be used for general
   interoperable deployment prior to official IANA assignment.

     +---------------------+----------------------------------------+
     | Extended Type Value |                Algorithm               |
     +---------------------+----------------------------------------+
     |          0          |                   CF                   |
     |          1          |                  S-MPR                 |
     |          2          |                  E-CDS                 |
     |          3          |                 MPR-CDS                |
     |        4-127        |    Future Assignment with STD action   |
     |       128-239       |         No STD action required         |
     |       240-255       |           Experimental Space           |
     +---------------------+----------------------------------------+

                 Table 7: SMF Relay Algorithm Type Values

   Acceptable <length> and <value> fields of an SMF_TYPE TLV are
   extended type dependent.  The appropriate algorithm type, as conveyed
   in the <tlv-type-ext> field, defines the meaning and format of its
   TLV <value> field.  For algorithms defined by this document see the
   appropriate appendix for the <value> field format.

7.1.2.  SMF Address Block TLV Type

   An address block TLV type, denoted SMF_NBR_TYPE (i.e., SMF neighbor
   relay algorithm) Table 8, is specified so that CDS relay algorithm
   operation and configuration can be shared among 2-hop neighborhoods
   This is useful for the case when mixed relay algorithm operation is
   possible.

   The message SMF_TYPE TLV and address block SMF_NBR_TYPE TLV types
   share a common format.

       +---------------+---------------------+--------------------+
       |               | packetBB TLV syntax | Field Values       |
       +---------------+---------------------+--------------------+
       | type          | <tlv-type>          | SMF_NBR_RELAY_ALG  |
       | extended type | <tlv-type-ext>      | <relayAlgorithmid> |
       | length        | <length>            | variable           |
       | value         | <value>             | variable           |
       +---------------+---------------------+--------------------+

                    Table 8: SMF Type Address Block TLV

   <relayAlgorithmId> in Table 7 is an 8-bit field containing a number
   0-255 representing the "Relay Algorithm Type" value that corresponds
   to any indicated address in the address block.  Note that "Relay



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 23]


Internet-Draft                SMF for MANET                November 2008


   Algorithm Type" values for 2-hop neighbors can be conveyed in a
   single TLV or multiple value TLVs as described in [PacketBB].  It is
   expected that SMF nodes using NHDP construct address blocks with
   SMF_NBR_TYPE TLVs to advertise "Relay Algorithm Type" and to
   advertise neighbor algorithm values received in SMF_TYPE TLVs from
   those neighbors.

   Again values for the <relayAlgorithmId> are defined in Table 7.

   Value length and value content of an SMF_NBR_TYPE TLV is defined by
   the appropriate algorithm type contained in the extended type field.
   See appropriate the appendix for definitions of value fields for
   algorithms defined by this document.


8.  SMF Border Gateway Considerations

   It is expected that SMF will be used to provide simple forwarding of
   multicast trafficwithin a MANET mesh routing topology.  A border
   router approach should be used to allow interconnection of SMF areas
   with networks using other multicast routing protocols (e.g., PIM).
   It is important to note that there are many scenario-specific issues
   that should be addressed when discussing border routers.  At the
   present time, experimental deployments of SMF and PIM border router
   approaches have been demonstrated.  Some of the functionality border
   routers may need to address include the following:

   1.  Determining which multicast groups should transit the border
       router whether entering or exiting the attached MANET routing
       region(s).
   2.  Enforcement of 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 border routers (presently beyond
       scope of this document).
   6.  Provisions for participating non-SMF nodes.

   Note the behavior of border router SMF nodes is the same as that of
   non-border SMF nodes when forwarding packets on interfaces within the
   MANET routing region.  Packets that are passed outbound to interfaces
   operating fixed-infrastructure 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

   Mechanisms for dynamically determining groups for forwarding into a
   MANET SMF routing region is an evolving technology area.  Ideally,



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 24]


Internet-Draft                SMF for MANET                November 2008


   only groups for which there is active group membership should be
   injected into the SMF domain.  This can 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 border routers (and hence multicast networks) of
   their current group membership status.  For specific systems and
   services it may be possible to statically configure group membership
   joins in border routers, 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 border routers can perform
   duplicate packet detection and forward non-duplicate traffic that
   meets TTL/hop limit and scoping criteria to other interfaces.
   Appropriate IP multicast routing (PIM, etc) on those interfaces can
   then make further forwarding decisions with respect to the given
   traffic destination and potentially its source addresses.  Note that
   the presence of multiple border routers associated with a MANET
   routing region raises additional issues.  This is further discussed
   in Section 8.4 but further work is expected to be needed here.

8.2.  Multicast Group Scoping

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

   1.  TTL scoping.
   2.  Administrative scoping.

   For IPv4, network administrators can configure border routers 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 SHOULD be taken into
   account that the packet could traverse multiple hops within the MANET
   SMF routing region before reaching the border router.  Thus, TTL
   thresholds SHOULD be selected carefully.

   For IPv6, multicast address spaces include information about the
   scope of the group.  Thus, border routers of an SMF routing region
   know if they must forward a packet based on the IPv6 multicast group
   address.  For the case of IPv6, it is RECOMMENDED that a MANET SMF
   routing region be designated a site.  Thus, all IPv6 multicast



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 25]


Internet-Draft                SMF for MANET                November 2008


   packets in the range FF05::/16 SHOULD be kept within the MANET SMF
   routing region by border routers.  IPv6 packets in any other wider
   range scopes (i.e.  FF08::/16, FF0B::/16 and FF0E::16) MAY traverse
   border routers unless other restrictions different from the scope
   applies.

   Given that scoping of multicast packets is performed at the border
   routers, and given that existing scoping mechanisms are not designed
   to work with mobile routers, it is assumed that non-border SMF
   routers will not stop forwarding multicast data packets of the
   appropriate site scoping.  That is, it is assumed that the entire
   MANET SMF routing region is a site scoped area.

8.3.  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, border
   routers can be considered leaf routers.  Mechanisms for multicast
   sources and receivers to interoperate with border routers over the
   multihop MANET SMF routing region as if they were directly connected
   to the router need to be defined.  The following issues need to be
   addressed:

   1.  Mechanism by which border routers gather membership information.
   2.  Mechanism by which multicast sources are known by the border
       router.
   3.  Exchange of exterior routing protocol messages across the MANET
       routing region if the MANET routing region is to provide transit
       connectivity for multicast traffic.

   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 routing region.  But, because MANET routing
   regions 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 operation.

   The need for the border router to receive traffic from recognized
   multicast sources within the MANET SMF routing region is important to
   achieve a smooth interworking with existing routing protocols.  For
   instance, PIM-S requires routers with locally attached multicast



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 26]


Internet-Draft                SMF for MANET                November 2008


   sources to register them to the Rendezvous Point (RP) so that nodes
   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.4.  Multiple Border Routers

   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 routing region can be beneficial since it can increase
   reliability, and provide better service.  For example, if the MANET
   routing region were to fragment with different MANET nodes
   maintaining connectivity to different border routers, multicast
   service could still continue successfully.  But, the case of multiple
   border routers connecting a MANET routing region to external networks
   presents several challenges for SMF:

   1.  Detection/hash collision/sequencing of duplicate unmarked IPv4 or
       IPv6 (without IPSec encapsulation or DPD option) packets possibly
       injected by multiple border routers.
   2.  Source-based relay algorithms handling of duplicate traffic
       injected by multiple border routers.
   3.  Determination of which border router(s) will forward outbound
       multicast traffic.
   4.  Additional challenges with interfaces to exterior multicast
       routing protocols.
   One of the most obvious issues is when multiple border routers are
   present and may be alternatively (due to route changes) or
   simultaneously injecting common traffic into the MANET routing region
   that has not been previously marked for SMF DPD.  Different border
   routers would not be able to implicitly synchronize sequencing of
   injected traffic since they may not receive exactly the same messages
   due to packet losses.  For IPv6 I-DPD operation, the optional
   "TaggerId" field described for the SMF-DPD header option can be used
   to mitigate this issue.  When multiple border routers are injecting a
   flow into a MANET routing region, there are two forwarding policies
   that SMF I-DPD nodes may implement:

   1.  Redundantly forward the multicast flows (identified by
       <sourceAddress:destinationAddress>) from each border router,
       performing DPD processing on a <taggerID:destinationAddress> or
       <taggerID:sourceAddress:destinationAddress> basis, or
   2.  Use some basis to select the flow of one tagger (border router)
       over the others and forward packets for applicable flows
       (identified by <sourceAddress:destinationAddress>) only for that
       "Tagger ID" until timeout or some other criteria to favor another



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 27]


Internet-Draft                SMF for MANET                November 2008


       tagger occurs.
   It is RECOMMENDED that the first approach be used in the case of
   I-DPD operation unless the SMF system is specifically designed to
   implement the second option.  Additional specification may be
   required to describe an interoperable forwarding policy based on this
   second option.  Note that the implementation of the second option
   requires that per-flow (i.e., <sourceAddress::destinationAddress>)
   state be maintained for the selected "Tagger ID".

   The deployment of a H-DPD operational mode may alleviate DPD
   resolution when ingressing traffic comes from multiple border
   routers.  Non-colliding hash indexes (those not requiring the H-DPD
   options header in IPv6) should be resolved effectively.


9.  Non-SMF MANET Node Interaction

   There may be scenarios in which some neighboring wireless MANET node
   are not running SMF and/or not forwarding, but 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, NHDP, and/or SMF forwarding operation.
   These devices include:

   1.  Devices that opportunistically receive multicast traffic due to
       proximity with SMF relays (possibly with asymmetric IP
       connectivity e.g., sensor network device).
   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,
   but the election heuristics shown in Figure 4 MAY be adjusted via
   management to better support such devices.  However, 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 routing regions 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 routers or intermediate systems
   providing IP Multicast routing functions.


10.  Security Considerations

   Gratuitous use of option headers can cause problems in routers.
   Routers outside of MANET routing regions should ignore SMF-specific



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 28]


Internet-Draft                SMF for MANET                November 2008


   header options if encountered.  The header options types are encoded
   appropriately for this behavior.

   Sequence-based packet identifiers are predictable and thus provide an
   opportunity for a denial-of-service attack against forwarding.  The
   use of the "internal hashing" as described in Section 5.3 for the
   I-DPD operation helps to mitigate denial-of-service attacks on
   predictable packet identifiers.  In this case, spoofed packets MAY be
   forwarded but the additional internal history identifier will protect
   against false collision events that may result from a predictive
   denial-of-service attack.

   Another potential denial-of-service attack against SMF forwarding is
   possible when a bad-behaving node has a form of "wormhole" access
   (via a directional antenna, etc) to preview packets before a
   particular SMF node would receive them.  The bad-behaving node could
   reduce the TTL or Hop Limit of the packet and transmit it to the SMF
   node causing it to forward the packet with a limited TTL (or even
   drop it) and make a DPD entry that would block forwarding of the
   subsequently-arriving valid packet with appropriate TTL value.  This
   would be a relatively low-cost, high-payoff attack that would be hard
   to detect and thus attractive to potential attackers.  An approach of
   caching TTL information with DPD state and taking appropriate
   forwarding actions is identified in Section 4 to mitigate this form
   of attack.

   The support of forwarding IPSec datagrams without further
   modification for both IPv4 and IPv6 is supported by this
   specification.

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


11.  IANA Considerations

   This document raises multiple IANA Considerations.  These include the
   IPv6 SMF_DPD hop-by-hop Header Extension defined and multiple Type-
   Length-Value (TLV) constructs (see [PacketBB]) used to extend NHDP
   operation as needed to support different forms of SMF operation.

11.1.  IPv6 SMF_DPD Header Extension

   This document requests IANA assignment of the "SMF_DPD" hop-by-hop
   option type from the IANA "IPv6 Hop-by-Hop Options Option Type"
   registry (see Section 5.5 of [RFC2780]).




Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 29]


Internet-Draft                SMF for MANET                November 2008


   The format of this new option type is described in Section 5.1.1.  A
   portion of the option data content is the "taggerIdType" that
   provides a context for the "taggerId" that is optionally included to
   identify the intermediate system that added the SMF_DPD option to the
   packet.  This document defines a name-space for IPv6 SMF_DPD Tagger
   Identifier Types:
                        ietf:manet:smf:taggerIdTypes

   The values that can be assigned within the "ietf:manet:smf:
   taggerIdTypes" name-space are numeric indexes in the range [0, 7],
   boundaries included.  All assignment requests are granted on a "IETF
   Consensus" basis as defined in [RFC2434].

   This specification registers Tagger Identification Type values from
   Table 9 in the registry "ietf:manet:smf:taggerIdTypes":

                   +----------+-------+---------------+
                   | Mnemonic | Value | Reference     |
                   +----------+-------+---------------+
                   |   NULL   |   0   | This document |
                   |  DEFAULT |   1   | This document |
                   |   IPv4   |   2   | This document |
                   |   IPv6   |   3   | This document |
                   |   ExtId  |   7   | This document |
                   +----------+-------+---------------+

                          Table 9: TaggerId Types

11.2.  SMF Type-Length-Value

   This document requests an IANA assignment one message "SMF_TYPE" TLV
   value and one address block "SMF_NBR_TYPE" TLV value from the [NHDP]
   specific registry space.

   The format of this new TLV type is described in Table 6 and Table 8.
   Furthermore this document defines a namespace for algorithm ID types
   using the extended type TLV value field defined by [PacketBB].  Both
   SMF_TYPE and SMF_NBR_TYPE TLVs use this namespace.
               ietf:manet:packetbb:nhdp:smf:relayAlgorithmID

   The values that can be assigned within the "ietf:manet:packetbb:nhdp:
   smf:relayAlgorithmID" name-space are numeric indexes in the range [0,
   239], boundaries included.  Assignment requests for the [0-127] are
   granted on a "IETF Consensus" basis as defined in [RFC2434].
   Standards action is not required for assignment requests of the range
   [128-239].  Documents requesting relayAlgorithmId values SHOULD
   define value field uses contained by the SMF_TYPE:<relayAlgorithmID>
   and SMF_NBR_TYPE:<relayAlgorithmID> full type TLVs.



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 30]


Internet-Draft                SMF for MANET                November 2008


   This specification registers the following Relay Algorithm ID Type
   values shown in Table 10 in the registry "ietf:manet:packetbb:nhdp:
   smf:relayAlgorithmID

                   +----------+-------+---------------+
                   | Mnemonic | Value | Reference     |
                   +----------+-------+---------------+
                   | CF       | 0     | This document |
                   | S-MPR    | 1     | Appendix B    |
                   | E-CDS    | 2     | Appendix A    |
                   | MPR-CDS  | 3     | Appendix C    |
                   +----------+-------+---------------+

                 Table 10: Relay Set Algorithm Type Values


12.  Acknowledgments

   Many of the concepts and mechanisms used and adopted by SMF resulted
   from many years of discussion and related work within the MANET WG
   since the late 1990s.  There are obviously many contributors 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 earlier 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 design, content
   editing, prototype implementation, and core discussions are listed
   below in alphabetical order.  We appreciate input from many others we
   may have missed in this list as well.
      Design contributors in alphabetical order:
      Brian Adamson
      Teco Boot
      Ian Chakeres
      Thomas Clausen
      Justin Dean
      Brian Haberman
      Charles Perkins
      Pedro Ruiz
      Fred Templin
      Maoyu Wang

   The RFC text was produced using Marshall Rose's xml2rfc tool and Bill
   Fenner's XMLmind add-ons.


13.  References




Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 31]


Internet-Draft                SMF for MANET                November 2008


13.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-nhdp-05, Work in progress ,
              December 2007.

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

   [PacketBB]
              Clausen, T. and et al, "Generalized MANET Packet/Message
              Format", draft-ietf-manet-packetbb-11, Work in progress ,
              November 2007.

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

   [RFC1321]  Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321,
              April 1992.

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

   [RFC2434]  Narten, T. and H. Alvestrand, "Guidelines for Writing an
              IANA Considerations Section in RFCs", BCP 26, RFC 2434,
              October 1998.

   [RFC2460]  Deering, S. and R. Hinden, "Internet Protocol, Version 6
              (IPv6) Specification", RFC 2460, December 1998.

   [RFC2644]  Senie, D., "Changing the Default for Directed Broadcasts
              in Routers", BCP 34, RFC 2644, August 1999.

   [RFC2780]  Bradner, S., "IANA Allocation Guidelines For Values In the
              Internet Protocol and Related Headers", March 2000.

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

   [RFC4302]  Kent, S., "IP Authentication Header", December 2005.



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 32]


Internet-Draft                SMF for MANET                November 2008


13.2.  Informative References

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

   [GM99]     Garcia-Luna-Aceves, JJ. and E. Madruga, "The core-assisted
              mesh protocol", Selected Areas in Communications, IEEE
              Journal on  Volume 17, Issue 8, August 1999.

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

   [MDDA07]   Macker, J., Downard, I., Dean, J., and R. Adamson,
              "Evaluation of distributed cover set algorithms in mobile
              ad hoc network for simplified multicast forwarding", ACM
              SIGMOBILE Mobile Computing and Communications Review
               Volume 11 ,  Issue 3  (July 2007), July 2007.

   [MGL04]    Mohapatra, P., Gui, C., and J. Li, "Group Communications
              in Mobile Ad hoc Networks", IEEE Computer Vol. 37, No. 2,
              February 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.

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

   [RFC3973]  Adams, A., Nicholas, J., and W. Siadak, "Protocol
              Independent Multicast - Dense Mode (PIM-DM): Protocol
              Specification (Revised)", RFC 3973, January 2005.

   [RFC4601]  Fenner, B., Handley, M., Holbrook, H., and I. Kouvelas,
              "Protocol Independent Multicast - Sparse Mode (PIM-SM):
              Protocol Specification (Revised)", RFC 4601, August 2006.

   [WC02]     Williams, B. and T. Camp, "Comparison of Broadcasting



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 33]


Internet-Draft                SMF for MANET                November 2008


              Techniques for Mobile Ad hoc Networks", Proceedings of ACM
              Mobihoc 2002 , 2002.


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

   The "Essential Connected Dominating Set" (E-CDS) algorithm [E-CDS]
   allows nodes to use 2-hop neighborhood topology information to
   dynamically perform relay self election to form a CDS.  Its packet
   forwarding rules are not dependent upon previous hop knowledge.
   Additionally, E-CDS SMF forwarders can be easily mixed without
   problems with CF SMF forwarders, even those not participating in
   NHDP.  Another benefit is that packets opportunistically received
   from non-symmetric neighbors may be forwarded without compromising
   flooding efficiency or correctness.  Furthermore, multicast sources
   not participating in NHDP may freely inject their traffic and any
   neighboring E-CDS relays will properly forward the traffic.  The
   E-CDS based relay set selection algorithm is based upon the summary
   within [E-CDS].  E-CDS was originally discussed in the context of
   forming partial adjacencies and efficient flooding for MANET OSPF
   extensions work and the core algorithm is applied here for SMF.

   It is RECOMMENDED that the SMF_TYPE:E-CDS message TLV be included in
   NHDP_HELLO messages that are generated by nodes conducting E-CDS SMF
   operation.  It is also RECOMMENDED that the SMF_NBR_TYPE:E-CDS
   address block TLV be used to advertise neighbor nodes that are also
   conducting E-CDS SMF operation.

A.1.  E-CDS Relay Set Selection Overview

   The E-CDS relay set selection requires 2-hop neighborhood information
   collected through NHDP or another process.  Relay nodes, in E-CDS SMF
   selection, are "self-elected" using a router identifier (Router ID)
   and an optional nodal metric, referred to here as "Router Priority"
   for all 1-hop and 2-hop neighbors.  To ensure proper relay set self-
   election, the Router ID and Router Priority MUST be consistent among
   nodes participating and it is RECOMMENDED that NHDP be used to share
   this information.  The Router ID is a logical identification that
   MUST be consistent across interoperating SMF neighborhoods and it is
   RECOMMENDED to be chosen as the largest interface address advertised
   by NHDP.  The E-CDS self-election process can be summarized as
   follows:

   1.  If an SMF node has a higher ordinal (Router Priority, Router ID)
       than all of its symmetric neighbors, it elects itself to act as a
       forwarder for all received multicast packets,





Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 34]


Internet-Draft                SMF for MANET                November 2008


   2.  Else, if there does not exist a path from neighbor "j" with
       largest (Router Priority, Router ID) to any 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 provide for redundant relay set election
   (e.g., bi-connected) but such capability is supported by the basic
   E-CDS design.

A.2.  E-CDS Forwarding Rules

   With E-CDS, any SMF node that has selected itself as a relay performs
   DPD and forwards all non-duplicative multicast traffic allowed by the
   present forwarding policy.  Packet previous hop knowledge is not
   needed for forwarding decisions when using E-CDS.

   1.  Upon packet reception, DPD is performed.  Note E-CDS requires a
       single duplicate table for the set of interfaces associated with
       the relay set selection.
   2.  If the packet is a duplicate, no further action is taken.
   3.  If the packet is non-duplicative:
       A.  A DPD entry is made for the packet identifier
       B.  The packet is forwarded out all interfaces associated with
           the relay set selection
   As previously mentioned, even packets sourced (or relayed) by nodes
   not participating in NHDP and/or the E-CDS relay set selection may be
   forwarded by E-CDS forwarders without problem.  A particular
   deployment MAY choose to not forward packets from sources or relays
   that have been not explicitly identified via NHDP or other means as
   operating as part of a different relay set algorithm (e.g.  S-MPR) to
   allow coexistent deployments to operate correctly.  Also, E-CDS relay
   set selection may be configured to be influenced by statically-
   configured CF relays that are identified via NHDP or other means.

A.3.  E-CDS Neighborhood Discovery Requirements

   It is possible to perform E-CDS relay set selection without
   modification of NHDP, basing the self-election process exclusively on
   the Router IDs (interface addresses) of participating SMF nodes.
   However steps MUST be taken to insure that all NHDP instances not
   using SMF_TYPE:E-CDS full type message TLVs are in fact running SMF
   E-CDS, otherwise incorrect forwarding may occur.  Furthermore, it has
   been shown that use of a "Router Priority" metric as part of the
   selection process can result in improved performance in certain
   cases.  Note that SMF nodes with higher "Router Priority" values will
   tend to be favored as relays over other nodes.  Thus, preferred
   relays MAY be administratively configured to be selected when



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 35]


Internet-Draft                SMF for MANET                November 2008


   possible.  Additionally, other metrics (e.g. nodal degree, energy
   capacity, etc) may also be taken into account in constructing a
   "Router Priority" value.  When using "Router Priority" with multiple
   interfaces all interfaces on a node MUST use and advertise a common
   "Router Priority" value.

   To share a node's "Router Priority" with its 1-hop neighbors the
   SMF_TYPE:E-CDS message TLV's <value> field is defined as shown in
   Table 11.

               +---------------+---------+-----------------+
               | Length(bytes) | Value   | Router Priority |
               +---------------+---------+-----------------+
               | 0             | N/A     | 64              |
               | 1             | <value> | 0-127           |
               +---------------+---------+-----------------+

                    Table 11: E-CDS Message TLV Values

   Where <value> is a one byte bit field which is defined as:

   bit 0: is reserved and SHOULD be set to 0.

   bit 1-7: contain the priority value, 0-127, which is associated with
   the originator address.

   Combinations of value field lengths and values other than specified
   here are NOT permitted and SHOULD be ignored.  Below is an example
   SMF_TYPE:E-CDS message TLV

       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     ...              |   SMF_TYPE    |1|0|0|1|0|0|   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |     E-CDS     |0|0|0|0|0|0|0|1|R|  priority   |     ...       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                    Figure 5: E-CDS Message TLV Example

   To convey "Router Priority" values among 2-hop neighborhoods the
   SMF_NBR_TYPE:E-CDS address block TLV's <value> field is defined thus:









Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 36]


Internet-Draft                SMF for MANET                November 2008


   +---------------+--------+----------+-------------------------------+
   | Length(bytes) | # Addr | Value    | Router Priority               |
   +---------------+--------+----------+-------------------------------+
   | 0             | Any    | N/A      | 64                            |
   | 1             | Any    | <value>  | <value> is for all addresses  |
   | N             | N      | <value>* | Each address gets its own     |
   |               |        |          | <value>                       |
   +---------------+--------+----------+-------------------------------+

                 Table 12: E-CDS Address Block TLV Values

   Where <value> is a one byte bit field which is defined as:

   bit 0: is reserved and SHOULD be set to 0.

   bit 1-7: contain a priority value, 0-127, which is associated with
   the appropriate address.

   Combinations of value field lengths and # of addresses other than
   specified here are NOT permitted and SHOULD be ignored.  A default
   technique of using nodal degree (i.e. count of 1-hop neighbors) is
   RECOMMENDED for the value field of these TLV types.  Below are two
   example SMF_NBR_TYPE:E-CDS address block TLVs.

       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     ...              | SMF_NBR_TYPE  |1|0|0|1|0|0|   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |     E-CDS     |0|0|0|0|0|0|0|1|R|  priority   |     ...       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                Figure 6: E-CDS Address Block TLV Example 1

   This single value example TLV specifies that all address(es)
   contained in the address block are running SMF using the E-CDS
   algorithm and all address(es) share the value field and therefore the
   same priority value.













Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 37]


Internet-Draft                SMF for MANET                November 2008


       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     ...              | SMF_NBR_TYPE  |1|0|1|1|0|1|   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |     E-CDS     |  index-start  |   index-end   |    length     |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |R|  priority0  |R|  priority1  |      ...      |R|  priorityn  |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                Figure 7: E-CDS Address Block TLV Example 2

   This example multivalue TLV specifies that address(es) contained in
   the address block from index-start to index-end inclusive are running
   SMF using the E-CDS algorithm.  Each address is associated with its
   own value byte and therefore their own priority value.

A.4.  E-CDS Selection Algorithm

   This section describes an algorithm for E-CDS relay selection (self-
   election).  The algorithm described uses 2-hop information.  Note it
   is possible to extend this algorithm to use k-hop information with
   added computational complexity and mechanisms for sharing k-hop
   topology information that are not described in this document or
   wihtin the NHDP specification.  It should also be noted that this
   algorithm does not impose the "hop limit" bound described in [E-CDS]
   when performing the path search that is used for relay selection.
   However, the algorithm below could be easily augmented to accommodate
   this additional criteria.  In normal operation, it is not expected
   that the "hop limit" bound will provide significant benefit.

   The tuple of "Router Priority" and "Router ID" is used in E-CDS relay
   set selection.  Precedence is given to the "Router Priority" portion
   and the "Router ID" value is used as a tie-breaker.  The evaluation
   of this tuple is referred to as "RtrPri(n)" in the description below
   where "n" references a specific node.  Note it is possible that the
   "Router Priority" portion may be optional and the evaluation of
   "RtrPri()" be solely based upon the unique "Router ID".  Since there
   MUST NOT be any duplicate "Router ID" values among SMF nodes, a
   comparison of RtrPri(n) between any two nodes will always be an
   inequality.  The use of nodal degree for calculating "Router
   Priority" is RECOMMENDED as default and the largest IP address
   associated across interfaces advertised by NHDP MUST be used as the
   "Router ID".  NHDP provides all interface address throughout the
   2-hop neighborhood so explicity conveying a "Router ID" is not
   necessary.  The following steps describe a basic algorithm for
   conducting E-CDS relay selection for a node "n0":




Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 38]


Internet-Draft                SMF for MANET                November 2008


   1.  Initialize the set "N1" to include all 1-hop neighbors of "n0".
   2.  If "N1" has less than 2 members, then "n0" does not elect itself
       as a relay and no further steps are taken.
   3.  Initialize the set "N2" to include all 2-hop neighbors, excluding
       "n0" and any nodes in "N1".
   4.  If "RtrPri(n0)" is greater than that of all nodes in the union of
       "N1" and "N2", then "n0" selects itself as a relay and no further
       steps are taken.
   5.  Initialize all nodes in the union of "N1" and "N2" as
       "unvisited".
   6.  Find the node "n1_Max" that has the largest "RtrPri()" of all
       nodes in "N1"
   7.  Initialize queue "Q" to contain "n1_Max", marking "n1_Max" as
       "visited"
   8.  While node queue "Q" is not empty, remove node "x" from the head
       of "Q", and for each 1-hop neighbor "n" of node "x" (excluding
       "n0") that is not marked "visited"
       A.  Mark node "n" as "visited"
       B.  If "RtrPri(n)" is greater than "RtrPri(n0), append "n" to "Q"
   9.  If any node in "N1" remains "unvisited", then "n0" selects itself
       as a relay.  Otherwise "n0" does not act as an relay.
   Note these steps are re-evaluated upon neighborhood status changes.
   Steps 5 through 8 of this procedure describe an approach to a path
   search.  The purpose of this path search is to determine if paths
   exist from the 1-hop neighbor with maximum "RtrPri()" to all other
   1-hop neighbors without traversing an intermediate node with a
   ""RtrPri()" value less than "RtrPri(n0)".  These steps comprise a
   breadth-first traversal that evaluates only paths that meet that
   criteria.  If all 1-hop neighbors of "n0" are "visited" during this
   traversal, then the path search has succeeded and node "n0" does not
   need to provide relay.  It can be assumed that other nodes will
   provide relay operation to ensure SMF connectivity.

   It is possible to extend this algorithm to consider neighboring SMF
   nodes that are known to be statically configured for CF (always
   relaying).  The modification to the above algorithm is to process
   such nodes as having a maximum possible "Router Priority" value.  It
   is expected that nodes configured for CF and participating in NHDP
   would indicate this with use of the SMF_TYPE:CF and SMF_NBR_TYPE:CF
   TLV types in their NHDP_HELLO message and address blocks,
   respectively.


Appendix B.  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 relays from their set of neighboring nodes.  Relays are



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 39]


Internet-Draft                SMF for MANET                November 2008


   selected so that forwarding to the node's complete two-hop neighbor
   set is covered.  This distributed relay set selection technique has
   been shown to approximate a minimal connected dominating set (MCDS)
   in [JLMV02].  Individual nodes must collect two-hop neighborhood
   information from neighbors, determine an appropriate current relay
   set, and inform selected neighbors of their relay status.  Note that
   since each node picks its neighboring relays independently, S-MPR
   forwarders depend upon previous hop information (e.g, source MAC
   address) to operate correctly.  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 it has
   been demonstrated operationally in dynamic network environments.

   It is RECOMMENDED that the SMF_TYPE:S-MPR message TLV be included in
   NHDP_HELLO messages that are generated by nodes conducting S-MPR SMF
   operation.  It is also RECOMMENDED that the SMF_NBR_TYPE:S-MPR
   address block TLV be used to specifiy which neighbor nodes are
   conducting S-MPR SMF operation.

B.1.  S-MPR Relay Set Selection Overview

   A RECOMMENDED algorithm for S-MPR set selection is described in the
   [OLSRv2] specification.  As this algorithm has had considerable use
   to support the OLSR control plane, it is expected to perform
   adequately to support data plane multicast traffic.  To summarize,
   the S-MPR algorithm uses bi-directional 1-hop and 2-hop neighborhood
   information collected via NHDP to select, from a node's 1-hop
   neighbors, a set of relays that will cover the node's entire 2-hop
   neighbor set upon forwarding.  The algorithm described uses a
   "greedy" heuristic of first picking the 1-hop neighbor who will cover
   the most 2-hop neighbors.  Then, excluding those 2-hop neighbors that
   have been covered, additional relays from its 1-hop neighbor set are
   iteratively selected until the entire 2-hop neighborhood is covered.
   Note that 1-hop neighbors also identified as 2-hop neighbors are
   considered as 1-hop neighbors only.  This is only a partial
   description of the S-MPR algorithm.  The [RFC3626] specification
   provides a complete description including the use of a "WILLINGNESS"
   metric, termed here "Router Priority", that can be used to influence
   S-MPR forwarder selection.

   NHDP_HELLO messages supporting S-MPR forwarding operation SHOULD use
   the TLVs defined in Section 7.1 using the S-MPR extended type.  The
   value field of an address block TLV which has a full type value of
   SMF_NBR_TYPE:S-MPR is defined in Table 14 such that signaling of
   multi point relay (MPR) selections to 1-hop neighbors is possible.
   The value field of a message block TLV which has a full type value of
   SMF_TYPE:S-MPR is defined in Table 13 such that signaling of "Router
   Priority" (described as "WILLINGNESS" in [OLSRv2]) to 1-hop neighbors



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 40]


Internet-Draft                SMF for MANET                November 2008


   is possible.  In some cases "MPR" address block TLV specified in
   [RFC3626] MAY be used in place of the SMF_NBR_TYPE:SMPR TLV to mark
   the addresses of selected neighbor relays in the NHDP_HELLO message
   address block(s), however in this case steps must be taken to insure
   SMF operation of neighbor nodes otherwise improper forwarding
   selection can occur.  It is important to note that S-MPR forwarding
   is dependent upon the previous hop of an incoming packet.  A S-MPR
   node MUST forward packets only for neighbors which have explicitly
   selected it as a relay (i.e., its "selectors").  There are also some
   additional requirements for duplicate packet detection to support
   S-MPR SMF operation that are described below.

   For multiple interface operation, MPR selection SHOULD be conducted
   on a per-interface basis.  However, it is possible to economize MPR
   selection among multiple interfaces by selecting common MPRs to the
   extent possible.  It is important to note that the S-MPR forwarding
   rules described in [OLSRv2] assume per-interface MPR selection (i.e.
   MPRs are _not_ selected in the context of all interfaces).  This is
   consistent with the MPR selection heuristics described in [RFC3626].
   Other source-based approaches may be possible, but would require
   alternative selection and forwarding rules to be specified.

B.2.  S-MPR Forwarding Rules

   An S-MPR relay MUST only forward packets for neighbors that have
   explicitly selected it as a forwarder.  The source-based forwarding
   technique also stipulates some additional duplicate packet detection
   operations.  For multiple network interfaces, independent DPD state
   MUST be maintained for each separate interface.  The following table
   provides the procedure for S-MPR packet forwarding given the arrival
   of a packet on a given interface, denoted <srcIface>.  There are
   three possible actions, depending upon the previous-hop transmitter:
   1.  If the previous-hop transmitter has selected the current node as
       a relay,
       A.  The packet identifier is checked against the DPD state for
           each possible outbound interface, including the <srcIface>.
       B.  If the packet is not a duplicate for an outbound interface,
           the packet is forwarded via that interface and a DPD entry is
           made for the given packet identifier for the interface.
       C.  If the packet is a duplicate, no action is taken for that
           interface.
   2.  Else, if the previous-hop transmitter is a 1-hop symmetric
       neighbor,
       A.  A DPD entry is made for that packet for the <srcIface>, but
           the packet is not forwarded.
   3.  Otherwise, no action is taken.

   Case number two in the above table is non-intuitive, but important to



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 41]


Internet-Draft                SMF for MANET                November 2008


   ensure correctness of S-MPR SMF operation.  The selection of source-
   based relays does not result in a common set among neighboring nodes,
   so relays MUST mark in their DPD state, packets received from non-
   selector, symmetric, one-hop neighbors (for a given interface) and
   not forward subsequent duplicates of that packet if received on that
   interface.  Deviation here can result in unnecessary, repeated packet
   forwarding throughout the network, or incomplete flooding.

   Nodes not participating in neighborhood discovery and relay set
   selection will not be able to source multicast packets into the area
   and have SMF forward them, unlike E-CDS or MPR-CDS where forwarding
   may occur dependent on topology.  Correct S-MPR relay behavior will
   occur with the introduction of repeaters (non-NHDP/SMF participants
   that relay multicast packets using duplicate detection and CF) but
   the repeaters will not efficiently contribute to S-MPR forwarding as
   these nodes will not be identified as neighbors (symmetric or
   otherwise) in the S-MPR forwarding process.  NHDP/SMF participants
   MUST NOT provide extra forwarding, forwarding packets which are not
   selected by the algorithm, as this can disrupt network-wide S-MPR
   flooding, resulting in incomplete or inefficient flooding.

B.3.  S-MPR Neighborhood Discovery Requirements

   Nodes may optionally signal "Router Priority" or "WILLINGNESS" to
   become MPR nodes for their one hop neighbors by using the SMF_TYPE:S-
   MPR message block TLV value field defined as such:

               +---------------+---------+-----------------+
               | Length(bytes) | Value   | Router Priority |
               +---------------+---------+-----------------+
               | 0             | N/A     | 64              |
               | 1             | <value> | 0-127           |
               +---------------+---------+-----------------+

                    Table 13: S-MPR Message TLV Values

   Where <value> is a one byte bit field which is defined as:

   bit 0: is reserved and SHOULD be set to 0.

   bit 1-7: contain the priority value, 0-127, which is associated with
   the originator address.

   Router priority values for S-MPR work similarly to "WILLINGNESS"
   values as described in [OLSRv2] with value 0 indicating a node will
   NEVER forward and value 127 indicating a node will ALWAYS forward.
   Combinations of value field lengths and values other than specified
   here are NOT permitted and SHOULD be ignored.  Below is an example



Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 42]


Internet-Draft                SMF for MANET                November 2008


   SMF_TYPE:S-MPR message TLV.

       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     ...              | SMF_NBR_TYPE  |1|0|0|1|0|0|   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |     S-MPR     |0|0|0|0|0|0|0|1|R|  priority   |     ...       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                    Figure 8: S-MPR Message TLV Example

   S-MPR election operation requires 2-hop neighbor knowledge as
   provided by the NHDP protocol [NHDP] or from external sources.  MPRs
   are dynamically selected by each node and selections MUST be
   advertised and dynamically updated within NHDP or an equivalent
   protocol or mechanism.  For NHDP use, the SMF_NBR_TYPE:S-MPR address
   block TLV value field is defined as such:

   +---------------+--------+----------+-------------------------------+
   | Length(bytes) | # Addr | Value    | Meaning                       |
   +---------------+--------+----------+-------------------------------+
   | 0             | Any    | N/A      | Addresses are NOT MPRs        |
   | 1             | Any    | <value>  | <value> is for all addresses  |
   | N             | N      | <value>* | Each address gets its own     |
   |               |        |          | <value>                       |
   +---------------+--------+----------+-------------------------------+

                 Table 14: E-CDS Address Block TLV Values

   Where <value> is a one byte field whcih is defined as:

   bit 0: Is the M bit which when set indicates MPR selection of
   associated address(es) by the originator node of the NHDP HELLO
   message.  When unset indicates the originator of the NHDP HELLO
   message has not selected the relevant address as an MPR.

   bit 1-7: are reserved and SHOULD be set to 0.

   Combinations of value field lengths and # of addresses other than
   specified here are NOT permitted and SHOULD be ignored.  All bits,
   excepting the leftmost bit, are RESERVED and SHOULD be set to 0.









Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 43]


Internet-Draft                SMF for MANET                November 2008


       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     ...              | SMF_NBR_TYPE  |1|1|0|1|0|0|   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |     S-MPR     |  start-index  |0|0|0|0|0|0|0|1|M|  reserved   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                Figure 9: S-MPR Address Block TLV Example 1

   This single index example TLV indicates that the address specified by
   the <start-index> field is running SMF using S-MPR and has been
   selected by the originator of the NHDP HELLO message as an MPR
   forwarder if the M bit is set.  Multivalue TLVs may also be used to
   specify MPR selection status of multiple addresses using only one
   TLV.  See Figure 7 for an example on how this may be done.

B.4.  S-MPR Selection Algorithm

   This section describes a basic algorithm for the S-MPR selection
   process.  Note that the selection is with respect to a specific
   interface of the node performing selection and other node interfaces
   referenced are reachable from this reference node interface.  This is
   consistent with the S-MPR forwarding rules described above.  When
   multiple interfaces per node are used, it is possible to enhance the
   overall selection process across multiple interfaces such that common
   nodes are selected as MPRs for each interface to avoid unnecessary
   inefficiencies in flooding.  This is described further in [OLSRv2].
   The following steps describe a basic algorithm for conducting S-MPR
   selection for a node interface "n0":
   1.  Initialize the set "MPR" to empty.
   2.  Initialize the set "N1" to include all 1-hop neighbors of "n0".
   3.  Initialize the set "N2" to include all 2-hop neighbors, excluding
       "n0" and any nodes in "N1".  Nodes which are only reachable via
       "N1" nodes with router priority values of NEVER are also
       excluded.
   4.  For each interface "y" in "N1", initialize a set "N2(y)" to
       include any interfaces in "N2" that are 1-hop neighbors of "y".
   5.  For each interface "x" in "N1" with a router priority value of
       "ALWAYS" (or using CF relay algorithm), select "x" as a MPR:
       A.  Add "x" to the set "MPR" and remove "x" from "N1".
       B.  For each interface "z" in "N2(x)", remove "z" from "N2"
       C.  For each interface "y" in "N1", remove any interfaces in
           "N2(x)" from "N2(y)"
   6.  For each interface "z" in "N2", initialize the set "N1(z)" to
       include any interfaces in "N1" that are 1-hop neighbors of "z".





Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 44]


Internet-Draft                SMF for MANET                November 2008


   7.  For each interface "x" in "N2" where "N1(x)" has only one member,
       select "x" as a MPR:
       A.  Add "x" to the set "MPR" and remove "x" from "N1".
       B.  For each interface "z" in "N2(x)", remove "z" from "N2" and
           delete "N1(z)"
       C.  For each interface "y" in "N1", remove any interfaces in
           "N2(x)" from "N2(y)"
   8.  While "N2" is not empty, select the interface "x" in "N1" with
       the largest router priority which has the number of members in
       "N_2(x)" as a MPR:
       A.  Add "x" to the set "MPR" and remove "x" from "N1".
       B.  For each interface "z" in "N2(x)", remove "z" from "N2"
       C.  For each interface "y" in "N1", remove any interfaces in
           "N2(x)" from "N2(y)"
   After the set of nodes "MPR" is selected, node "n_0" must signal its
   selections to its neighbors.  With NHDP, this is done by using the
   MPR address block TLV to mark selected neighbor addresses in
   NHDP_HELLO messages.  Neighbors MUST record their MPR selection
   status and the previous hop address (e.g., link or MAC layer) of the
   selector.  Note these steps are re-evaluated upon neighborhood status
   changes.


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

   The MPR-CDS algorithm is an extension to the basic S-MPR election
   algorithm that results in a shared (non source-specific) SMF CDS.
   Thus its forwarding rules are not dependent upon previous hop
   information similar to E-CDS.  An overview of the MPR-CDS selection
   algorithm is provided in [MPR-CDS].

   It is RECOMMENDED that the SMF_RELAY_ALG message TLV be included in
   NHDP_HELLO messages that are generated by nodes conducting MPR-CDS
   SMF operation.

C.1.  MPR-CDS Relay Set Selection Overview

   The MPR-CDS relay set selection process is based upon the MPR
   selection process of the S-MPR algorithm with the added refinement of
   a distributed technique for subsequently down-selecting to a common
   reduced, shared relay set.  A node ordering (or "prioritization")
   metric is used as part of this down-selection process Like the E-CDS
   algorithm, this metric can be based upon node address or some other
   unique router identifier ("Router ID") as well as an additional
   "Router Priority" measure, if desired.  The process for MPR-CDS relay
   selection is as follows:




Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 45]


Internet-Draft                SMF for MANET                November 2008


   1.  First, MPR selection per the S-MPR algorithm is conducted, with
       selectors informing their MPRs (via NHDP) of their selection.
   2.  Then, the following rules are used on a distributed basis by
       selected nodes to possibly unselect themselves and thus jointly
       establish a common set of shared SMF relays:
       A.  If a selected node has a larger "RtrPri()" than all of its
           1-hop symmetric neighbors, then it acts as a relay for all
           multicast traffic, regardless of the previous hop
       B.  Else, if the 1-hop symmetric neighbor with the largest
           "RtrPri()" value has selected the node, then it also acts as
           a relay for all multicast traffic, regardless of the previous
           hop.
       C.  Otherwise, it unselects itself as a relay and does not
           forward any traffic unless changes occur that require re-
           evaluation of the above steps.
   This technique shares many of the desirable properties of the E-CDS
   technique with regards to compatibility with multicast sources not
   participating in NHDP and the opportunity for statically-configure CF
   nodes to be present, regardless of their participation in NHDP.

C.2.  MPR-CDS Forwarding Rules

   The forwarding rules for MPR-CDS are common with those of E-CDS.  Any
   SMF node that has selected itself as a relay performs DPD and forward
   all non-duplicative multicast traffic allowed by the present
   forwarding policy.  Packet previous hop knowledge is not needed for
   forwarding decisions when using MPR-CDS.

   1.  Upon packet reception, DPD is performed.  Note MPR-CDS require
       one duplicate table for the set of interfaces associated with the
       relay set selection.
   2.  If the packet is a duplicate, no further action is taken.
   3.  If the packet is non-duplicative:
       A.  A DPD entry is made for the packet identifier
       B.  The packet is forwarded out all interfaces associated with
           the relay set selection
   As previously mentioned, even packets sourced (or relayed) by nodes
   not participating in NHDP and/or the MPR-CDS relay set selection may
   be forwarded by E-CDS forwarders without problem.  A particular
   deployment MAY choose to not forward packets from sources or relays
   that have been explicitly identified via NHDP or other means as
   operating as part of a different relay set algorithm (e.g.  S-MPR) to
   allow coexistent deployments to operate correctly.  Also, MPR-CDS
   relay set selection may be configured to be influenced by statically-
   configured CF relays that are identified via NHDP or other means.






Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 46]


Internet-Draft                SMF for MANET                November 2008


C.3.  MPR-CDS Neighborhood Discovery Requirements

   The neighborhood discovery requirements for MPR-CDS have commonality
   with both the S-MPR and E-CDS algorithms.  MPR-CDS selection
   operation requires 2-hop neighbor knowledge as provided by the NHDP
   protocol [NHDP] or from external sources.  Unlike S-MPR operation,
   there is no need for associating link-layer address information with
   1-hop neighbors since MPR-CDS forwarding is independent of the
   previous hop similar to E-CDS forwarding.

   To advertise an optional "Router Priority" value or "WILLINGNESS" an
   originating node may use the message TLV of type SMF_TYPE:MPR-CDS
   which shares a common <value> format with both SMF_TYPE:E-CDS
   Table 11 and SMF_TYPE:S-MPR Table 13.

   MPR-CDS only requires 1-hop knowledge of "Router Priority" for
   correct operation.  In the S-MPR phase of MPR-CDS selection, MPRs are
   dynamically determined by each node and selections MUST be advertised
   and dynamically updated using NHDP or an equivalent protocol or
   mechanism.  Therefore the <value> field of the SMF_NBR_TYPE:MPR-CDS
   type TLV shares a common format with SMF_NBR_TYPE:S-MPR Table 14 to
   convey MPR selection.

C.4.  MPR-CDS Selection Algorithm

   This section describes an algorithm for the MPR-CDS selection
   process.  Note that the selection described is with respect to a
   specific interface of the node performing selection and other node
   interfaces referenced are reachable from this reference node
   interface.  An ordered tuple of "Router Priority" and "Router ID" is
   used in MPR-CDS relay set selection.  The "Router ID" value should be
   set to the largest advertised address of a given node, this
   information is provided to one hop neighbors via NHDP by default.
   Precedence is given to the "Router Priority" portion and the "Router
   ID" value is used as a tie-breaker.  The evaluation of this tuple is
   referred to as "RtrPri(n)" in the description below where "n"
   references a specific node.  Note it is possible that the "Router
   Priority" portion may be optional and the evaluation of "RtrPri()" be
   solely based upon the unique "Router ID".  Since there MUST NOT be
   any duplicate address values among SMF nodes, a comparison of
   RtrPri(n) between any two nodes will always be an inequality.  The
   following steps, repeated upon any changes detected within the 1-hop
   and 2-hop neighborhood, describe a basic algorithm for conducting
   MPR-CDS selection for a node interface "n0":
   1.  Perform steps 1-8 of Appendix B.4 to select MPRs from the set of
       1-hop neighbors of "n0" and notify/update neighbors of
       selections.




Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 47]


Internet-Draft                SMF for MANET                November 2008


   2.  Upon being selected as an MPR (or any change in the set of nodes
       selecting "n0" as an MPR):
       A.  If no neighbors have selected "n0" as an MPR, "n0" does not
           act as a relay and no further steps are taken until a change
           in neighborhood topology or selection status occurs.
       B.  Determine the node "n1_max" that has the maximum "RtrPri()"
           of all 1-hop neighbors.
       C.  If "RtrPri(n0)" is greater than "RtrPri(n1_max)", then "n0"
           selects itself as a relay for all multicast packets,
       D.  Else, if "n1_max" has selected "n0" as an MPR, then "0"
           selects itself as a relay for all multicast packets.
       E.  Otherwise, "n0" does not act as a relay.
   It is possible to extend this algorithm to consider neighboring SMF
   nodes that are known to be statically configured for CF (always
   relaying).  The modification to the above algorithm is to process
   such nodes as having a maximum possible "Router Priority" value.
   This is the same as the case for participating nodes that have been
   configured with a S-MPR "WILLINGNESS" value of "WILL_ALWAYS".  It is
   expected that nodes configured for CF and participating in NHDP would
   indicate their status with use of the SMF_RELAY_ALG TLV type in their
   NHDP_HELLO message TLV block.  It is important to note however that
   CF nodes will not select MPR nodes and therefore cannot guarantee
   connectedness.


Authors' Addresses

   Joseph Macker
   NRL
   Washington, DC  20375
   USA

   Email: macker@itd.nrl.navy.mil


   SMF Design Team
   IETF MANET WG

   Email: manet@ietf.org












Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 48]


Internet-Draft                SMF for MANET                November 2008


Full Copyright Statement

   Copyright (C) The IETF Trust (2008).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

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


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
   http://www.ietf.org/ipr.

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











Macker, editor & SMF Design Team  Expires May 7, 2009          [Page 49]


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