tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Glossaries     Architecture     IMS     UICC    |    search     info

RFC 6621

 
 
 

Simplified Multicast Forwarding

Part 3 of 3, p. 40 to 55
Prev RFC Part

 


prevText      Top      Up      ToC       Page 40 
Appendix A.  Essential Connecting Dominating Set (E-CDS) Algorithm

   The "Essential Connected Dominating Set" (E-CDS) algorithm [RFC5614]
   forms a single CDS mesh for the SMF operating region.  It allows
   routers 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 [RFC5614].  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 routers conducting E-CDS
   SMF operation.  It is also RECOMMENDED that the SMF_NBR_TYPE:E-CDS
   Address Block TLV be used to advertise neighbor routers 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 routers, 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
   participating routers.  It is RECOMMENDED that NHDP be used to share
   Router ID and Router Priority through the use of SMF_TYPE:E-CDS TLVs
   as described in this appendix.  The Router ID is a logical
   identification that MUST be consistent across interoperating SMF
   neighborhoods, and it is RECOMMENDED to be chosen as the numerically
   largest address contained in a router's "Neighbor Address List" as
   defined in NHDP.  The E-CDS self-election process can be summarized
   as follows:

   1.  If an SMF router 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.

Top      Up      ToC       Page 41 
   2.  Else, if there does not exist a path from the neighbor 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 selection
   (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 router 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 to all interfaces associated with
           the relay set selection.

   As previously mentioned, even packets sourced (or relayed) by routers
   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 previous hop
   routers 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 "Neighbor Address List" of participating SMF routers, for
   example, by setting the Router Priority to a default value and
   selecting the Router ID as the numerically largest address contained

Top      Up      ToC       Page 42 
   in the "Neighbor Address List".  However, steps MUST be taken to
   ensure that all NHDP-enabled routers not using SMF_TYPE:E-CDS full
   type Message TLVs are, in fact, running SMF E-CDS with the same
   methods for selecting Router Priority and Router ID; otherwise,
   incorrect forwarding may occur.  Note that SMF routers with higher
   Router Priority values will be favored as relays over routers with
   lower Router Priority.  Thus, preferred relays MAY be
   administratively configured to be selected when 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 router MUST use and advertise a common Router
   Priority value.  A router's Router Priority value may be
   administratively or algorithmically selected.  The method of
   selection does not need to be the same among different routers.

   E-CDS relay set selection may be configured to be influenced by
   statically configured CF relays that are identified via NHDP or other
   means.  Nodes advertising CF through NHDP may be considered E-CDS SMF
   routers with maximal Router Priority.

   To share a router's Router Priority with its 1-hop neighbors, the
   SMF_TYPE:E-CDS Message TLV's <value> field is defined as shown in
   Table 14.

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

                    Table 14: E-CDS Message TLV Values

   Where <value> is a one-octet-long bit field that is defined as:

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

   bits 1-7: contain the unsigned Router Priority value, 0-127, which is
   associated with the "Neighbor Address List".

   Combinations of value field lengths and values other than specified
   here are NOT permitted and SHOULD be ignored.  Figure 6 shows an
   example SMF_TYPE:E-CDS Message TLV.

Top      Up      ToC       Page 43 
       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 6: 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 used.  Multi-
   index and multivalue TLV layouts as defined in [RFC5444] are
   supported.  SMF_NBR_TYPE:E-CDS value fields are defined thus:

   +---------------+--------+----------+-------------------------------+
   | 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 15: E-CDS Address Block TLV Values

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

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

   bits 1-7: contain the unsigned Router Priority value, 0-127, which is
   associated with the appropriate address(es).

   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 7: E-CDS Address Block TLV Example 1

Top      Up      ToC       Page 44 
   The single value example TLV, depicted in Figure 7, 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 Router Priority.
       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 8: E-CDS Address Block TLV Example 2

   The example multivalued TLV, depicted in Figure 8, 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 its own
   Router Priority.

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
   that 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
   within the NHDP specification.  It should also be noted that this
   algorithm does not impose the hop limit bound described in [RFC5614]
   when performing the path search that is used for relay selection.
   However, the algorithm below could be easily augmented to accommodate
   this additional criterion.  It is not expected that the hop limit
   bound will provide significant benefit to the algorithm defined in
   this appendix.

   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 tiebreaker.  The evaluation of this
   tuple is referred to as "RtrPri(n)" in the description below where
   "n" references a specific router.  Note that 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 routers, a
   comparison of "RtrPri(n)" between any two routers will always be an
   inequality.  The use of nodal degree for calculating Router Priority
   is RECOMMENDED as default, and the largest IP address in the

Top      Up      ToC       Page 45 
   "Neighbor Address List" as advertised by NHDP MUST be used as the
   Router ID.  NHDP provides all interface addresses throughout the
   2-hop neighborhood through HELLO messages, so explicitly conveying a
   Router ID is not necessary.  The following steps describe a basic
   algorithm for conducting E-CDS relay selection for a router "n0":

   1.  Initialize the set "N1" with tuples ("Router Priority", "Router
       ID", "Neighbor Address List") for each 1-hop neighbor of "n0".

   2.  If "N1" has less than 2 tuples, then "n0" does not elect itself
       as a relay, and no further steps are taken.

   3.  Initialize the set "N2" with tuples ("Router Priority", "Router
       ID", "2-hop address") for each "2-hop address" of "n0", where
       "2-hop address" is defined in NHDP.

   4.  If "RtrPri(n0)" is greater than that of all tuples in the union
       of "N1" and "N2", then "n0" selects itself as a relay, and no
       further steps are taken.

   5.  Initialize all tuples in the union of "N1" and "N2" as
       "unvisited".

   6.  Find the tuple "n1_Max" that has the largest "RtrPri()" of all
       tuples in "N1".

   7.  Initialize queue "Q" to contain "n1_Max", marking "n1_Max" as
       "visited".

   8.  While router queue "Q" is not empty, remove router "x" from the
       head of "Q", and for each 1-hop neighbor "n" of router "x"
       (excluding "n0") that is not marked "visited".

       A.  Mark router "n" as "visited".

       B.  If "RtrPri(n)" is greater than "RtrPri(n0)", append "n" to
           "Q".

   9.  If any tuple in "N1" remains "unvisited", then "n0" selects
       itself as a relay.  Otherwise, "n0" does not act as a 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 router with a
   "RtrPri()" value less than "RtrPri(n0)".  These steps comprise a
   breadth-first traversal that evaluates only paths that meet that

Top      Up      ToC       Page 46 
   criteria.  If all 1-hop neighbors of "n0" are "visited" during this
   traversal, then the path search has succeeded, and router "n0" does
   not need to provide relay.  It can be assumed that other routers will
   provide relay operation to ensure SMF connectivity.

   It is possible to extend this algorithm to consider neighboring SMF
   routers that are known to be statically configured for CF (always
   relaying).  The modification to the above algorithm is to process
   such routers as having a maximum possible Router Priority value.  It
   is expected that routers 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) Algorithm

   The source-based multipoint relay (S-MPR) set selection algorithm
   enables individual routers, using 2-hop topology information, to
   select relays from their set of neighboring routers.  Relays are
   selected so that forwarding to the router's complete 2-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 routers must collect 2-hop neighborhood
   information from neighbors, determine an appropriate current relay
   set, and inform selected neighbors of their relay status.  Note that
   since each router 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 routers conducting S-MPR
   SMF operation.  It is also RECOMMENDED that the SMF_NBR_TYPE:S-MPR
   Address Block TLV be used to specify which neighbor routers are
   conducting S-MPR SMF operation.

B.1.  S-MPR Relay Set Selection Overview

   The S-MPR algorithm uses bi-directional 1-hop and 2-hop neighborhood
   information collected via NHDP to select, from a router's 1-hop
   neighbors, a set of relays that will cover the router'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

Top      Up      ToC       Page 47 
   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.

   NHDP HELLO messages supporting S-MPR forwarding operation SHOULD use
   the TLVs defined in Section 8.1 using the S-MPR extended type.  The
   value field of an Address Block TLV that has a full type value of
   SMF_NBR_TYPE:S-MPR is defined in Table 17 such that signaling of MPR
   selections to 1-hop neighbors is possible.  The value field of a
   message block TLV that has a full type value of SMF_TYPE:S-MPR is
   defined in Table 16 such that signaling of Router Priority (described
   as "WILLINGNESS" in [RFC3626]) to 1-hop neighbors is possible.  It is
   important to note that S-MPR forwarding is dependent upon the
   previous hop of an incoming packet.  An S-MPR router MUST forward
   packets only for neighbors that have explicitly selected it as a
   multipoint 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.

B.2.  S-MPR Forwarding Rules

   An S-MPR SMF router MUST only forward packets for neighbors that have
   explicitly selected it as an MPR.  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
   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 router
       as an MPR,

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

Top      Up      ToC       Page 48 
   2.  Else, if the previous-hop transmitter is a 1-hop symmetric
       neighbor, a DPD entry is added for that packet for the
       <srcIface>, but the packet is not forwarded.

   3.  Otherwise, no action is taken.

   Action number two in the list above is non-intuitive but important to
   ensure correctness of S-MPR SMF operation.  The selection of source-
   based relays does not result in a common set among neighboring
   routers, so relays MUST mark, in their DPD state, packets received
   from non-selector, symmetric, 1-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 routers will not be identified as neighbors (symmetric or
   otherwise) in the S-MPR forwarding process.  NHDP/SMF participants
   MUST NOT forward packets that are not selected by the algorithm, as
   this can disrupt network-wide S-MPR flooding, resulting in incomplete
   or inefficient flooding.  The result is that non-S-MPR SMF routers
   will be unable to source multicast packets and have them forwarded by
   other S-MPR SMF routers.

B.3.  S-MPR Neighborhood Discovery Requirements

   Nodes may optionally signal a Router Priority value to their 1-hop
   neighbors by using the SMF_TYPE:S-MPR message block TLV value field.
   If the value field is omitted, a default Router Priority value of 64
   is to be assumed.  This is summarized here:

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

                    Table 16: S-MPR Message TLV Values

Top      Up      ToC       Page 49 
   Where <value> is a one-octet-long bit field defined as:

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

   bits 1-7: contain the Router Priority value, 0-127, which is
   associated with the "Neighbor Address List".

   Router Priority values for S-MPR are interpreted in the same fashion
   as "WILLINGNESS" ([RFC3626]), with the value 0 indicating a router
   will NEVER forward and value 127 indicating a router will ALWAYS
   forward.  Values 1-126 indicate how likely a S-MPR SMF router will be
   selected as an MPR by a neighboring SMF router, with higher values
   increasing the likelihood.  Combinations of value field lengths and
   values other than those specified here are NOT permitted and SHOULD
   be ignored.  Below is an example 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_TYPE    |1|0|0|1|0|0|   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |     S-MPR     |0|0|0|0|0|0|0|1|R|  priority   |     ...       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                    Figure 9: S-MPR Message TLV Example

   S-MPR election operation requires 2-hop neighbor knowledge as
   provided by NHDP [RFC6130] or from external sources.  MPRs are
   dynamically selected by each router, 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      | NOT MPRs                      |
   | 1             | Any    | <value>  | <value> is for all addresses  |
   | N             | N      | <value>* | Each address gets its own     |
   |               |        |          | <value>                       |
   +---------------+--------+----------+-------------------------------+

                 Table 17: S-MPR Address Block TLV Values

Top      Up      ToC       Page 50 
   Where <value>, if present, is a one-octet bit field defined as:

   bit 0: The leftmost bit is the M bit that, when set, indicates MPR
   selection of the relevant interface, represented by the associated
   address(es), by the originator router of the NHDP HELLO message.
   When unset, it indicates the originator router of the NHDP HELLO
   message has not selected the relevant interfaces, represented by the
   associated address(es), as its MPR.

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

   Combinations of value field lengths and number 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.

       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 10: S-MPR Address Block TLV Example

   The single index TLV example, depicted in Figure 10, 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.  Multivalued TLVs
   may also be used to specify MPR selection status of multiple
   addresses using only one TLV.  See Figure 8 for a similar 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 router performing selection, and other router
   interfaces referenced are reachable from this reference router
   interface.  This is consistent with the S-MPR forwarding rules
   described above.  When multiple interfaces per router are used, it is
   possible to enhance the overall selection process across multiple
   interfaces such that common routers are selected as MPRs for each
   interface to avoid unnecessary inefficiencies in flooding.  The
   following steps describe a basic algorithm for conducting S-MPR
   selection for a router interface "n0":

Top      Up      ToC       Page 51 
   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 routers in "N1".  Nodes that are only reachable via
       "N1" routers 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 the CF relay algorithm), select "x" as an 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".

   7.  For each interface "x" in "N2" where "N1(x)" has only one member,
       select "x" as an 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 that has the number of members in
       "N_2(x)" as an 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)".

Top      Up      ToC       Page 52 
   After the set of routers "MPR" is selected, router "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_TYPE Message TLV be included in
   NHDP_HELLO messages that are generated by routers 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 router ordering (or "prioritization")
   metric is used as part of this down-selection process; like the E-CDS
   algorithm, this metric can be based upon router address(es) or some
   other unique router identifier (e.g., Router ID based on largest
   address contained within the "Neighbor Address List") as well as an
   additional Router Priority measure, if desired.  The process for MPR-
   CDS relay selection is as follows:

   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 routers to possibly deselect themselves and thus jointly
       establish a common set of shared SMF relays:

       A.  If a selected router 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.

Top      Up      ToC       Page 53 
       B.  Else, if the 1-hop symmetric neighbor with the largest
           "RtrPri()" value has selected the router, then it also acts
           as a relay for all multicast traffic, regardless of the
           previous hop.

       C.  Otherwise, it deselects 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 configured
   CF routers to be present, regardless of their participation in NHDP.

C.2.  MPR-CDS Forwarding Rules

   The forwarding rules for MPR-CDS are similar to those for E-CDS.  Any
   SMF router 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 MPR-CDS.

   1.  Upon packet reception, DPD is performed.  Note that MPR-CDS
       requires 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 added for the packet identifier

       B.  The packet is forwarded out to all interfaces associated with
           the relay set selection.

   As previously mentioned, even packets sourced (or relayed) by routers
   not participating in NHDP and/or the MPR-CDS relay set selection may
   be forwarded by MPR-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.

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 NHDP

Top      Up      ToC       Page 54 
   [RFC6130] 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 router may use the Message TLV of type SMF_TYPE:MPR-CDS,
   which shares a common <value> format with both SMF_TYPE:E-CDS
   (Table 14) and SMF_TYPE:S-MPR (Table 16).

   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 router, and selections MUST be
   advertised and dynamically updated using NHDP or an equivalent
   protocol or mechanism.  The <value> field of the SMF_NBR_TYPE:MPR-CDS
   type TLV shares a common format with SMF_NBR_TYPE:S-MPR (Table 17) 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 router performing selection, and other
   router interfaces referenced are reachable from this reference router
   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 router; 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 tiebreaker.  The evaluation of this tuple is referred to as
   "RtrPri(n)" in the description below where "n" references a specific
   router.  Note that 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 routers, a comparison of "RtrPri(n)" between any two
   routers 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
   router 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.

   2.  Upon being selected as an MPR (or any change in the set of
       routers selecting "n0" as an MPR):

Top      Up      ToC       Page 55 
       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 router "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
   routers that are known to be statically configured for CF (always
   relaying).  The modification to the above algorithm is to process
   such routers as having a maximum possible Router Priority value.
   This is the same as the case for participating routers that have been
   configured with a S-MPR "WILLINGNESS" value of "WILL_ALWAYS".  It is
   expected that routers configured for CF and participating in NHDP
   would indicate their status with use of the SMF_TYPE TLV type in
   their NHDP_HELLO message TLV block.  It is important to note,
   however, that CF routers will not select MPR routers and therefore
   cannot guarantee connectedness.

Author's Address

   Joseph Macker (editor)
   NRL
   Washington, DC  20375
   USA

   EMail: macker@itd.nrl.navy.mil