RFC 6621
Simplified Multicast Forwarding
RFC 6621: Simplified Multicast Forwarding 💖
(part 1 of 13 ✨)
okay bestie, let's get into RFC 6621 🦋 It's an Experimental doc about Simplified Multicast Forwarding (SMF), and it's giving "flooding, but make it efficient" 💅
Here's the title block, the facts you need up top:
- Number: RFC 6621
- Title: Simplified Multicast Forwarding
- Authors: J. Macker, Ed., NRL
- Category: Experimental
- Date: May 2012
- Stream: IETF
- ISSN: 2070-1721
- Obsoletes / Updates: neither is listed in the header, so this doc doesn't obsolete or update anything 🌸
Abstract 🌸
okay so this doc describes an SMF mechanism that gives you basic IP multicast forwarding, and it's built for limited wireless mesh and MANET (mobile ad hoc network) use 📡 It's mainly for setups where efficient flooding is an okay engineering trade-off, fr. It defines duplicate packet detection (DPD) techniques that get applied while forwarding, for both IPv4 and IPv6 ✨
It also has optional mechanisms that use reduced relay sets to distribute multicast data more efficiently across a mesh than Classic Flooding does 🦋 It talks about how SMF interacts with other protocols, like using info from unicast routing protocols running alongside it, or working with other multicast protocols. Multiple deployment approaches get covered too 💖
The distributed algorithms for picking reduced relay sets, plus related discussion, live in the appendices 🧚 Last thing: basic stuff about multicast MANET border routers is covered, but the ongoing work there is out of scope for this doc 👑
Status of This Memo 🎀
this doc is not an Internet Standards Track spec 💅 It's published for examination, experimental implementation, and evaluation, so it's giving "try it out and tell us" energy 🧪
It defines an Experimental Protocol for the Internet community. It's a product of the IETF and represents IETF community consensus. It got public review and was approved for publication by the Internet Engineering Steering Group (IESG). Not every IESG-approved doc is a candidate for any level of Internet Standard, so check Section 2 of RFC 5741 if you want the details 🌈
For the current status, any errata, and how to give feedback, go to http://www.rfc-editor.org/info/rfc6621 🔥
Copyright Notice 🌈
Copyright (c) 2012 IETF Trust and the persons identified as the document authors. All rights reserved. 🫶
This doc is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) as in effect on the date of publication. Please read these carefully, since they spell out your rights and restrictions for this doc. Code Components pulled from this doc must include Simplified BSD License text, as described in Section 4.e of the Trust Legal Provisions, and they come with no warranty, as described in the Simplified BSD License 📜
This doc may contain material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. The people controlling the copyright in some of that material may not have granted the IETF Trust the right to allow modifications outside the IETF Standards Process. Unless you get an adequate license from those copyright holders, this doc may not be modified outside the IETF Standards Process, and derivative works of it may not be created outside the IETF Standards Process. The exceptions are formatting it for publication as an RFC or translating it into languages other than English 🌸
Table of Contents 🧚
1. Introduction and Scope ..........................................4
2. Terminology .....................................................4
3. Applicability Statement .........................................5
4. Overview and Functioning ........................................6
5. SMF Packet Processing and Forwarding ............................8
6. SMF Duplicate Packet Detection .................................10
6.1. IPv6 Duplicate Packet Detection ...........................11
6.1.1. IPv6 SMF_DPD Option Header .........................12
6.1.2. IPv6 Identification-Based DPD ......................14
6.1.3. IPv6 Hash-Based DPD ................................16
6.2. IPv4 Duplicate Packet Detection ...........................17
6.2.1. IPv4 Identification-Based DPD ......................18
6.2.2. IPv4 Hash-Based DPD ................................19
7. Relay Set Selection ............................................20
7.1. Non-Reduced Relay Set Forwarding ..........................20
7.2. Reduced Relay Set Forwarding ..............................20
8. SMF Neighborhood Discovery Requirements ........................23
8.1. SMF Relay Algorithm TLV Types .............................24
8.1.1. SMF Message TLV Type ...............................24
8.1.2. SMF Address Block TLV Type .........................25
9. SMF Border Gateway Considerations ..............................26
9.1. Forwarded Multicast Groups ................................27
9.2. Multicast Group Scoping ...................................28
9.3. Interface with Exterior Multicast Routing Protocols .......29
9.4. Multiple Border Routers ...................................29
10. Security Considerations .......................................31
11. IANA Considerations ...........................................32
11.1. IPv6 SMF_DPD Header Extension Option Type ................33
11.2. TaggerId Types (TidTy) ...................................33
11.3. Well-Known Multicast Address .............................34
11.4. SMF TLVs .................................................34
11.4.1. Expert Review for Created Type Extension
Registries ........................................34
11.4.2. SMF Message TLV Type (SMF_TYPE) ...................34
11.4.3. SMF Address Block TLV Type (SMF_NBR_TYPE) .........35
11.4.4. SMF Relay Algorithm ID Registry ...................35
12. Acknowledgments ...............................................36
13. References ....................................................37
13.1. Normative References .....................................37
13.2. Informative References ...................................38
Appendix A. Essential Connecting Dominating Set (E-CDS)
Algorithm ............................................40
A.1. E-CDS Relay Set Selection Overview ........................40
A.2. E-CDS Forwarding Rules ....................................41
A.3. E-CDS Neighborhood Discovery Requirements .................41
A.4. E-CDS Selection Algorithm .................................44
Appendix B. Source-Based Multipoint Relay (S-MPR) Algorithm ......46
B.1. S-MPR Relay Set Selection Overview ........................46
B.2. S-MPR Forwarding Rules ....................................47
B.3. S-MPR Neighborhood Discovery Requirements .................48
B.4. S-MPR Selection Algorithm .................................50
Appendix C. Multipoint Relay Connected Dominating Set
(MPR-CDS) Algorithm ..................................52
C.1. MPR-CDS Relay Set Selection Overview ......................52
C.2. MPR-CDS Forwarding Rules ..................................53
C.3. MPR-CDS Neighborhood Discovery Requirements ...............53
C.4. MPR-CDS Selection Algorithm ...............................541. Introduction and Scope 🌟
okay so unicast routing protocols built for MANET and wireless mesh use often run distributed algorithms to flood routing control plane messages across a MANET routing domain 🕸️ Like, the algorithms in [RFC3626] and [RFC3684] are distributed ways of dynamically electing reduced relay sets. They try to flood control messages efficiently while keeping the set connected, even when the topology keeps changing 🔄
SMF takes that efficient flooding idea and applies it to the data forwarding plane 💖 The result is a multicast forwarding capability for cases where localized, efficient flooding is a solid design choice. The baseline design is a basic, best-effort multicast forwarding capability, and it's limited to one MANET routing domain 🫶
An SMF routing domain is an instance of an SMF routing protocol with common policies, under a single network administration authority 👑 The main design goals of this doc are:
- adapt efficient relay sets in MANET environments [RFC2501], and
- define the needed IPv4 and IPv6 multicast duplicate packet detection (DPD) mechanisms to support multi-hop packet forwarding.
2. Terminology 📚
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119] 🎀
The terms introduced in [RFC5444], including "packet", "message", "TLV Block", "TLV", and "address", are to be interpreted as described there ✨
These abbreviations are used throughout the doc 💅
+--------------+----------------------------------------------------+
| Abbreviation | Definition |
+--------------+----------------------------------------------------+
| MANET | Mobile Ad Hoc Network |
| SMF | Simplified Multicast Forwarding |
| CF | Classic Flooding |
| CDS | Connected Dominating Set |
| MPR | Multipoint 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 |
| DoS | Denial of Service |
| SMF Router | A MANET Router implementing the protocol specified |
| | in this document |
| SMF Routing | A MANET Routing Domain wherein the protocol |
| Domain | specified in this document is operating |
+--------------+----------------------------------------------------+3. Applicability Statement 🎀
okay so bestie, wireless mesh networks are kinda chaotic 🌀. Maintaining the usual forwarding trees to support a multicast routing protocol just isn't as effective as it is on wired networks, because mesh topologies are less reliable and way more dynamic [MGL04][GM99]. 😭 A basic packet forwarding service that reaches every connected router running the SMF protocol inside a MANET routing domain can be a super useful group communication vibe for stuff like multimedia streaming, interactive group messaging and apps, peer-to-peer middleware multicasting, and multi-hop mobile discovery or registration services 💖. SMF is likely only appropriate for limited, dynamic MANET routing domains (further defined as administratively scoped multicast forwarding domains in Section 9.2) so that the flooding can be contained 🧚.
The design goal is giving hosts the ability to send and receive multicast traffic with standard IP network-layer semantics too 🫶. Special or unnecessary encapsulation of IP packets should be avoided in this case, so nobody gets weird extra wrapping 💅. SMF deployments are also able to connect and interoperate with existing standard multicast protocols running in more conventional Internet infrastructures ✨. To make that work, a multicast border router or proxy mechanism MUST be used whenever SMF is deployed alongside fixed-infrastructure IP multicast routing, such as the Protocol Independent Multicast (PIM) variants [RFC3973][RFC4601] 🔥. Experimental SMF implementations and deployments have already shown gateway functionality at MANET border routers working with existing external IP multicast routing protocols [CDHM07][DHS08][DHG09] 🌈. SMF may be extended or combined with other mechanisms for extra reliability and group-specific filtering too, but those details are out of the scope of this document 🦋.
This document does not presently support forwarding of packets with directed broadcast addresses as a destination [RFC2644]. 🙈
4. Overview and Functioning 💜
Figure 1 is the big-picture tour of the logical SMF router architecture 🗺️. It has three components: "Neighborhood Discovery", "Relay Set Selection", and "Forwarding Process" ✨.
______________ _____________
| | | |
| Neighborhood | | Relay Set |
| Discovery |------------->| Selection |
| | neighbor | |
|______________| info |_____________|
\ /
\ /
neighbor\ /forwarding
info* \ ____________ / status
\ | | /
`-->| Forwarding |<--'
| Process |
~~~~~~~~~~~~~~~~~>|____________|~~~~~~~~~~~~~~~~~>
incoming packet, forwarded packets
interface id*, and
previous hop*
Figure 1: SMF Router ArchitectureTypically, relay set selection (or self-election) happens based on dynamic input from a neighborhood discovery process 🔍. SMF also supports the case where neighborhood discovery and/or relay set selection info comes from a coexistent process, like a lower-layer mechanism or a unicast routing protocol using relay sets 🤝. In some algorithm designs, 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 that relay set algorithms need if they rely on previous-hop packet-forwarding knowledge ⭐.
Certain IP multicast packets, defined in Sections 9.2 and 5, are "non-forwardable" 🚫. These multicast packets MUST be ignored by the SMF forwarding engine 💀. The SMF forwarding engine MAY also work with policies and management interfaces to add extra filtering control over which multicast packets get considered for potential SMF forwarding 🎀. That interface would allow more refined dynamic forwarding control once those techniques are mature for MANET operation 🌸. For now, further discussion of dynamic control is left to future work 🔮.
Interoperable SMF implementations MUST use compatible DPD approaches and be able to process the header options defined in this document for IPv6 operation 🫶.
Classic Flooding (CF) is defined as the simplest case of SMF multicast forwarding 🌊. With CF, all SMF routers forward each received multicast packet exactly once 🍓. The need for any relay set selection or neighborhood topology information is gone in this case, but the trade-off is extra network overhead from unnecessary packet retransmissions 😅. With CF, the SMF DPD functionality is still required. While SMF supports CF as a mode of operation, 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 built by selecting and updating, as needed, a subset of all possible routers in a MANET routing domain to act as SMF forwarders 👑. Known distributed relay set selection algorithms have shown they can provide and maintain a dynamic connected set for forwarding multicast IP packets [MDC04] ✨. A few of these algorithms are described in the appendices of this document, and their basic designs borrow directly from previously documented IETF work 📚. SMF relay set configuration is extensible, so additional relay set algorithms beyond the ones specified here can be added in future work 🧚♀️.
Figuring out and maintaining an optimized set of relays usually requires dynamic neighborhood topology information 🗺️. Neighborhood topology discovery functions MAY be provided by a MANET unicast routing protocol or by the MANET Neighborhood Discovery Protocol (NHDP) [RFC6130], running concurrently with SMF 🌈. This specification also allows alternative lower-layer interfaces (for example, radio router interfaces) to provide the neighborhood information needed for more effective relay set selection 📡. An SMF implementation SHOULD provide the ability for multicast forwarding state to be dynamically managed per operating network interface 🦋. The relay state maintenance options and interactions are outlined in Section 7 💅. This document states specific requirements for neighborhood discovery with respect to the forwarding process and the relay set selection algorithms described here ✨. For determining dynamic relay sets when no other control protocols are around, SMF relies on NHDP to help with IP-layer 2-hop neighborhood discovery and maintenance for relay set selection 🥹. The "SMF_TYPE" and "SMF_NBR_TYPE" Message and Address Block TLV structures (per [RFC5444]) are defined by this document for use with NHDP to carry SMF-specific information 🎀. It is RECOMMENDED that all routers performing SMF operation together with NHDP include these TLV types in any NHDP HELLO messages they generate 💖. This lets routers participating in SMF be explicitly identified, along with their respective dynamic relay set algorithm configuration 👑.
5. SMF Packet Processing and Forwarding ✨
okay so SMF has two main packet handling jobs, bestie 💅
- Processing of outbound, locally generated multicast packets.
- Reception and processing of inbound packets on specific network interfaces.
The whole point of catching outbound, locally generated multicast packets is to slap on any extra packet marking needed to meet the DPD requirements, so proper forwarding can happen 🎀. Lowkey, for some system setups, intercepting outbound packets for this isn't even necessary ✨.
Inbound multicast packets get received by the SMF implementation and checked for possible forwarding. SMF implementations MUST be capable of forwarding IP multicast packets with destination addresses that are not router-local and link-local for IPv6, as defined in [RFC4291], and that are not within the local network control block as defined by [RFC5771] 🌸.
This supports generic multi-hop multicast application needs, or distributes designated multicast traffic that enters the SMF routing domain through border routers 🧚. The multicast addresses to be forwarded should 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 💜.
The SL-MANET-ROUTERS multicast group is defined to contain all routers within an SMF routing domain, so packets sent to the multicast address for that group will be attempted to be delivered to every connected router running SMF 🦋. Because a MANET is mobile, routers running SMF may not be topologically connected at certain times 🙈. For IPv6, SL-MANET-ROUTERS is specified to be "site-local" ✨. Minimally, SMF MUST forward, as instructed by the relay set selection algorithm, unique (non-duplicate) packets received for SL-MANET-ROUTERS when the Time to Live (TTL) / hop limit or hop limit value in the IP header is greater than 1. SMF MUST forward all additional global-scope multicast addresses specified within the dynamic FIB or configured list as well 🔥. In all cases, the following rules MUST be observed for SMF multicast forwarding 👑:
- Any IP packets not addressed to an IP multicast address MUST NOT be forwarded by the SMF forwarding engine.
- IP multicast packets with
TTL/hop limit <= 1MUST NOT be forwarded. - Link local IP multicast packets MUST NOT be forwarded.
- Incoming IP multicast packets with an IP source address matching one of those of the local SMF router interface(s) MUST NOT be forwarded.
- Received frames with the Media Access Control (MAC) source address matching any MAC address of the router's interfaces MUST NOT be forwarded.
- Received packets for which SMF cannot reasonably ensure temporal DPD uniqueness MUST NOT be forwarded.
- Prior to being forwarded, the TTL/hop limit of the forwarded packet MUST be decremented by one.
Rule #4 is very important 😭. Over some types of wireless interfaces, the originating SMF router may receive retransmissions of its own packets when they are forwarded by adjacent routers. This rule avoids unnecessary retransmission of locally generated packets, even when other forwarding decision rules would apply 🙈.
There's also an extra processing rule to think about because of a possible security threat 💀. As discussed in Section 10, someone can conduct a DoS attack by remotely "previewing" packets that an SMF router would forward (for example, with a directional receive antenna). They then do a "pre-play" attack by transmitting the packet before the SMF router would otherwise receive it, but with a reduced TTL/hop limit field value 😱. This can make an SMF router create a DPD entry that blocks the proper forwarding of the valid packet (with the correct TTL/hop limit) through the SMF routing domain. A RECOMMENDED approach to prevent this attack, when it is a concern, is to cache temporal packet TTL/hop limit values along with the per-packet DPD state (hash value(s) and/or identifier, as described in Section 6). Then, if a subsequent matching (with respect to DPD) packet arrives with a larger TTL/hop limit value than the packet that was previously forwarded, SMF should forward the new packet and update the TTL/hop limit value cached with the corresponding DPD state to the new, larger value 🧁. There may be temporal cases where SMF would unnecessarily forward some duplicate packets using this approach, but those cases are expected to be minimal and acceptable compared with the potential threat of denied service 💖.
Once the SMF multicast forwarding rules have been applied, an SMF implementation MUST make a forwarding decision that depends on the relay set selection algorithm in use 🦋. If the SMF implementation is using Classic Flooding (CF), the forwarding decision is implicit once DPD uniqueness is determined ✨. Otherwise, the forwarding decision depends on the current interface-specific relay set state. The descriptions of the relay set selection algorithms in this document's appendices specify the respective heuristics for multicast packet forwarding, plus the specific DPD or other processing needed for correct SMF behavior in each case 🌈. For example, one class of forwarding is based on relay set selection status and the packet's previous hop, while other classes designate the local SMF router as a forwarder for all neighboring routers 🫶.
6. SMF Duplicate Packet Detection 🦋
Duplicate packet detection (DPD) is often a requirement in MANET or wireless mesh packet forwarding mechanisms, because packets may be transmitted out via the same physical interface they were received on 🌀. Routers may also receive multiple copies of the same packets from different neighbors or interfaces 😵. SMF operation requires DPD, and implementations MUST provide mechanisms to detect and reduce the likelihood of forwarding duplicate multicast packets using temporal packet identification 💅. It is RECOMMENDED that this be implemented by keeping a history of recently processed multicast packets to compare with incoming packets 📜. A DPD packet cache history SHOULD be kept long enough to span the maximum network traversal lifetime, MAX_PACKET_LIFETIME, of multicast packets being forwarded within an SMF routing domain ⏳. The DPD mechanism SHOULD avoid keeping unnecessary state for packet flows, such as those that are locally generated or have link-local destinations that would not be considered for forwarding, as presented in Section 5 🙅♀️.
For both IPv4 and IPv6, this document describes two basic multicast duplicate packet detection mechanisms: header content identification-based (I-DPD) and hash-based (H-DPD) duplicate packet detection 🎀.
I-DPD uses specific packet headers (and option headers, in the case of IPv6) in combination with flow state to estimate the temporal uniqueness of a packet 🧠. H-DPD uses hashing over header fields and the payload of a multicast packet to estimate temporal uniqueness 🔍.
The two approaches to DPD have trade-offs that deserve different considerations depending on the specific SMF deployment scenario ⚖️.
Because a hop-by-hop option header might be added with IPv6, all SMF routers in the same SMF deployment MUST be configured to use a common mechanism and DPD algorithm 🫶. The main difference between the IPv4 and IPv6 SMF DPD specifications is that IPv4 avoids any additional header options ✨.
For each network interface, SMF implementations MUST maintain DPD packet state as needed to support the forwarding heuristics of the relay set algorithm in use 💜. In general, this means keeping track of previously forwarded packets so duplicates are not forwarded, but some relay techniques have additional considerations, such as those discussed in Appendix B.2 🌸.
Additional details of I-DPD and H-DPD processing and maintenance for different classes of packets are described in the following subsections 📚.
6.1. IPv6 Duplicate Packet Detection 💅
This section describes the mechanisms and options for SMF IPv6 DPD 🧚. The base IPv6 packet header doesn't have an explicit packet identification header field that can be exploited for I-DPD, so the following options are described to support IPv6 DPD 😤:
- a hop-by-hop SMF_DPD option header, defined in this document (Section 6.1.1),
- the use of IPv6 fragment header fields for I-DPD, if one is present (Section 6.1.2),
- the use of IPsec sequencing for I-DPD when a non-fragmented IPsec header is detected (Section 6.1.2), and
- an H-DPD approach assisted, as needed, by the SMF_DPD option header (Section 6.1.3).
SMF MUST provide a DPD marking module that can insert the hop-by-hop IPv6 header option, defined in Section 6.1.1 🎀. This module MUST be invoked after any source-based fragmentation that may occur with IPv6, so that all fragments are suitably marked 🧩. SMF IPv6 DPD is presently specified to allow either a packet hash or a header identification method for DPD 🔑. An SMF implementation MUST be configured to operate in either I-DPD or H-DPD mode, and to perform the corresponding tasks outlined in Sections 6.1.2 and 6.1.3 🌈.
6.1.1. IPv6 SMF_DPD Option Header ✨
Okay bestie, this section defines an IPv6 Hop-by-Hop Option [RFC2460] called SMF_DPD 🎀. It has two jobs. It gives IPv6 I-DPD a unique packet identifier, and when H-DPD is in use, it makes sure different packets don't end up with colliding hash values 💅.
If this is the only hop-by-hop option present, the optional TaggerId field is left out, and the DPD packet identifier (sequence number) or hash token is 24 bits or less, the whole thing adds 8 bytes to the IPv6 packet header 🍓. Those 8 bytes cover the "Next Header", "Header Extension Length", the SMF_DPD option fields, and padding 🧚.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
... |0|0|0| 01000 | Opt. Data Len |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|H| DPD Identifier Option Fields or Hash Assist Value ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Figure 2: IPv6 SMF_DPD Hop-by-Hop Option Header
"Option Type" = 00001000. The highest order three bits are 000 because this specification requires that routers not recognizing this option type skip over this option and continue processing the header, and that the option must not change en route [RFC2460]. 🙈
"Opt. Data Len" = Length of option content (i.e., 1 + (<IdType> ? (<IdLen> + 1): 0) + Length(DPD ID)). 🌸
"H-bit" = a hash indicator bit value identifying DPD marking type. 0 means a sequence-based approach with optional TaggerId and a tuple-based sequence number. 1 means a hash assist value (HAV) field follows to help avoid hash-based DPD collisions. 🦋
When the "H-bit" is cleared (zero value), the SMF_DPD format that supports I-DPD operation looks like Figure 3, and it defines the extension header in line 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| 01000 | Opt. Data Len |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|TidTy| TidLen| TaggerId (optional) ... |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | Identifier ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Figure 3: IPv6 SMF_DPD Option Header in I-DPD mode
"TidTy" = a 3-bit field indicating the presence and type of the optional TaggerId field. 🎀
"TidLen" = a 4-bit field indicating the length (in octets) of the following TaggerId field. 🫶
"TaggerId" = a field used to tell apart multiple ingressing border gateways that may commonly apply the SMF_DPD option header to packets from a particular source. Table 1 lists the TaggerId types used in this document: 👑
+---------+---------------------------------------------------------+
| Name | Purpose |
+---------+---------------------------------------------------------+
| NULL | Indicates no TaggerId field is present. "TidLen" MUST |
| | also be set to ZERO. |
| DEFAULT | A TaggerId of non-specific context is present. "TidLen |
| | + 1" defines the length of the TaggerId field in bytes. |
| IPv4 | A TaggerId representing an IPv4 address is present. The |
| | "TidLen" MUST be set to 3. |
| IPv6 | A TaggerId representing an IPv6 address is present. The |
| | "TidLen" MUST be set to 15. |
+---------+---------------------------------------------------------+Table 1: TaggerId Types
This format lets you do a quick check of the "TidTy" field to see if a TaggerId field is there 👀. If "TidTy" is NULL, the length of the DPD packet <Identifier> field is (<Opt. Data Len> - 1). If <TidTy> is non-NULL, the TaggerId field length is (<TidLen> - 1), and whatever is left of the option data is the DPD packet <Identifier> field 🌈. When the TaggerId field is present, the <Identifier> can be treated as a unique packet identifier within the <TaggerId:srcAddr:dstAddr> tuple 💖. When it isn't present, it's assumed the source applied the SMF_DPD option, and the <Identifier> can be treated as unique within the IPv6 packet header <srcAddr:dstAddr> tuple ✨. IPv6 I-DPD operation details are in Section 6.1.2.
When the "H-bit" in the SMF_DPD option data is set, the data content is read as a hash assist value (HAV) that helps with H-DPD operation 🔥. In this case, the source or ingressing gateways only apply the SMF_DPD with an HAV when it's needed to tell a new packet's hash value apart from the hash values already in the DPD cache 🙌. A router can detect this locally by running the hash algorithm and checking the DPD cache, before ingressing a previously unmarked packet or a locally sourced packet. This helps guarantee the uniqueness of generated hash values when H-DPD is used. It also avoids the extra overhead of applying the SMF_DPD option header to every single packet 💅. For many hash algorithms, it's expected that only sparse use of the SMF_DPD option may be required. The format of the SMF_DPD option header for H-DPD operation is in Figure 4.
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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|1| Hash Assist Value (HAV) ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Figure 4: IPv6 SMF_DPD Option Header in H-DPD Mode
The SMF_DPD option should be applied with an 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 "Opt. Data Len". The right size depends on the collision properties of the specific hash algorithm being used. More details on IPv6 H-DPD operation are in Section 6.1.3. 🦋
6.1.2. IPv6 Identification-Based DPD 🌷
Table 2 sums up the IPv6 I-DPD processing and forwarding decision approach. In the table, * means an ignore field condition 🧁.
+-------------+-----------+-----------+-----------------------------+
| IPv6 | IPv6 | IPv6 | SMF IPv6 I-DPD Mode Action |
| Fragment | IPsec | I-DPD | |
| Header | Header | Header | |
+-------------+-----------+-----------+-----------------------------+
| Present | * | Not | Use Fragment Header I-DPD |
| | | Present | Check and Process for |
| | | | Forwarding |
| Not Present | Present | Not | Use IPsec Header I-DPD |
| | | Present | 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 a received 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. The IPsec header
<sequence>field can be considered a unique identifier in the context of the<IPsecType:srcAddr:dstAddr:SPI>where "IPsecType" is either Authentication Header (AH) or Encapsulating Security Payload (ESP) [RFC4302]. 🔐 - For unfragmented, non-IPsec IPv6 packets, the use of the SMF_DPD option header is necessary to support I-DPD operation. The SMF_DPD option header is applied in the context of the
<srcAddr>of the IP packet. Hosts or ingressing SMF gateways are responsible for applying this option to support DPD. Table 3 sums up 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 field of the IPv6 SMF_DPD option header. 🎀
6.1.3. IPv6 Hash-Based DPD ✨
okay so here's the default hash-based DPD approach (H-DPD) that SMF uses 💖 It takes a SHA-1 [RFC3174] hash of the non-mutable header fields, options fields, and data content of the IPv6 multicast packet and spits out a 160-bit digest 🔥 The way that hash gets calculated SHOULD follow the same guidelines as the Integrity Check Value (ICV) in [RFC4302] when it comes to non-mutable fields. It should have a reasonably low probability of digest collision even when the headers and content keep changing 🦋 SHA-1 is only in SMF to keep the collision chances low. It 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>. SMF ingress points (aka source hosts or gateways) use that history to check that new packets are unique by their hash value 👀 The hash assist value (HAV) field from Section 6.1.1 is the differentiating field that shows up when a digest collision would otherwise happen. The HAV is an immutable option field, and SMF MUST process any included HAV values (see Section 6.1.1) in its hash calculation 🧚
If a packet causes a digest collision (checked against the H-DPD digest history) inside the DPD cache that SMF forwarders keep, the packet SHOULD be silently dropped 💀 If a digest collision is detected at an SMF ingress point, the H-DPD option header gets built with a randomly generated HAV. The HAV is recalculated as needed to get a non-colliding hash value before forwarding 🎀
The multicast packet then gets forwarded with the added IPv6 SMF_DPD option header. A common hash approach MUST be used by SMF routers for the applied HAV, so they consistently avoid hash collisions and the inadvertent packet drops that come with them 🫶
The SHA-1 indexing and IPv6 HAV approaches are specified for now for consistency and robustness, and they're meant for experimental uses 🧪 Future approaches and experimentation may find design trade-offs in hash robustness and efficiency that are worth looking at. Enhancements MAY include reducing the maximum payload length that gets processed, finding shorter indexes, or using more efficient hashing algorithms. Using the HAV functionality may allow "lighter-weight" hashing techniques that might not have looked good before because of poor collision properties. Those techniques could cut down on packet-processing overhead and memory requirements ✨
6.2. IPv4 Duplicate Packet Detection 🌸
this section covers the mechanisms and options for IPv4 DPD. Three areas support IPv4 DPD:
- the use of IPv4 fragment header fields for I-DPD when they exist (Section 6.2.1),
- the use of IPsec sequencing for I-DPD when a non-fragmented IPv4 IPsec packet is detected (Section 6.2.1), and
- an H-DPD approach (Section 6.2.2) when neither of the above cases can be applied.
Even though the IPv4 datagram has a 16-bit Identification (ID) field as specified in [RFC0791], you can't rely on it for DPD purposes 🙅♀️ That's because of common computer operating system implementation practices and the reasons in the updated specification of the IPv4 ID Field [IPV4-ID-UPDATE]. An SMF IPv4 DPD marking option, like the IPv6 SMF_DPD option header, is not specified, since IPv4 header options aren't as easy for hosts to work with as they are for IPv6. When IPsec is applied or IPv4 packets have been fragmented, though, the I-DPD approach can be applied reliably using the matching packet identifier fields from Section 6.2.1. For the general IPv4 case (non-IPsec and non-fragmented packets), the H-DPD approach of Section 6.2.2 is RECOMMENDED 🍓
Since IPv4 SMF doesn't specify an option header, the interoperability constraints are looser than in the IPv6 version. Forwarders may run mixed H-DPD and I-DPD modes, as long as they consistently perform the right DPD routines from the sections below 🦋 Still, it is RECOMMENDED that a deployment be configured with a common mode for operational consistency 💅
6.2.1. IPv4 Identification-Based DPD 🔍
Table 4 sums up the IPv4 I-DPD processing approach once a packet has passed the basic forwardable criteria from Section 5. Basically, for IPv4, I-DPD only applies to packets that have been fragmented or have IPsec applied. In Table 4, * means an ignore field condition. DF, MF, and Fragment offset line up with the related fields and flags defined in [RFC0791].
+------+------+----------+---------+--------------------------------+
| DF | MF | Fragment | IPsec | IPv4 I-DPD Action |
| flag | flag | offset | | |
+------+------+----------+---------+--------------------------------+
| 1 | 1 | * | * | Invalid; do not forward. |
| 1 | 0 | nonzero | * | Invalid; do not forward. |
| * | 0 | zero | not | Use H-DPD check instead |
| | | | Present | |
| * | 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 RulesFor performance reasons, IPv4 network fragmentation and reassembly of multicast packets within wireless MANET networks should be minimized, but SMF still forwards fragments when they happen 🌈 If the IPv4 multicast packet is a fragment, SMF MUST use the fragmentation header fields for packet identification. That identification can be treated as temporally unique within the context of <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 treated as a unique identifier within the context of <IPsecType:srcAddr:dstAddr:SPI>, where "IPsecType" is either AH or ESP [RFC4302]. Table 5 sums up 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 | | |
+-----------+---------------------------------+---------------------+
Table 5: IPv4 I-DPD Packet Identification Types"IPsecType" is either Authentication Header (AH) or Encapsulating Security Payload (ESP) 🎀
6.2.2. IPv4 Hash-Based DPD 💜
The hashing technique here is similar to the one for IPv6 in Section 6.1.3, but the H-DPD header option with HAV isn't considered 🙈 To keep IPv4 H-DPD working consistently across SMF routers, a default hashing approach is specified. A common DPD hashing algorithm for an SMF routing area is RECOMMENDED, because colliding hash values for different packets lead to "false positive" duplicate packet detection, and there's a small chance that valid packets get dropped because of the hashing technique used. The "hash assist value" approach isn't available for IPv4, so using a common hashing approach keeps the chance of hash-collision packet drops low over multiple hops of forwarding 🧚
SMF MUST perform a SHA-1 [RFC3174] hash of the immutable header fields, option fields, and data content of the IPv4 multicast packet, which gives a 160-bit digest. The way that hash value gets calculated SHOULD follow the same guidelines as the Integrity Check Value (ICV) in [RFC4302] when it comes 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 for IPv6, because the SMF_DPD HAV can't be used to mitigate hash collisions 🔥 A RECOMMENDED implementation detail for IPv4 H-DPD is to concatenate the 16-bit IPv4 ID value with the computed hash value as an extended DPD hash value. That may reduce hash collisions when the IPv4 ID field is being set by host operating systems or gateways 💖
When this approach is taken, using the supplemental "internal hash" technique described in Section 10 is RECOMMENDED as a security measure 🛡️
The SHA-1 hash is specified for now for consistency and robustness. Future approaches and experimentation may find design trade-offs in hash robustness and efficiency worth considering for future revisions of SMF. This MAY include reducing the packet payload length that gets processed, finding shorter indexes, or using a more efficient hashing algorithm 🦋
7. Relay Set Selection 👑
SMF is flexible about supporting different reduced relay set mechanisms for efficient flooding, and the constraints for those are detailed in this section 🌸
7.1. Non-Reduced Relay Set Forwarding 🧁
SMF implementations MUST support CF as a basic forwarding mechanism when reduced relay set information isn't available or isn't selected for operation. In CF mode, each router transmits a packet once it has passed the SMF forwarding rules. The DPD techniques from Section 6 are critical to proper operation and to preventing duplicate packet retransmissions by the same relays 💅
7.2. Reduced Relay Set Forwarding ✨
okay so MANET reduced relay sets are usually built by distributed algorithms that dynamically work out a topological connected dominating set (CDS) 🧚
A big goal of SMF is using reduced relay sets so multicast gets spread around more efficiently in topologies that keep changing 💖 To make that happen, an SMF implementation MUST support modifying its multicast packet forwarding rules based on relay set state it receives dynamically while it's running. That's how SMF acts like neighbor adjacencies or multicast forwarding policies even when the topology shifts 🌊
In early SMF experimental prototyping, the relay set info came from coexistent unicast routing control plane traffic flooding processes [MDC04]. From that experience, extra pruning considerations sometimes had to be handled when a relay set came from a separate routing protocol process 🙈 For example, relay sets formed for unicast control plane flooding MAY include extra redundancy that isn't wanted for multicast forwarding use (e.g., biconnected relay set). Not ideal, bestie 💀
Here's a recommended criteria list for SMF relay set selection algorithm candidates:
- Robustness to topological dynamics and mobility
- Localized election or coordination of any relay sets
- Reasonable minimization of CDS relay set size given the above constraints
- Heuristic support for preference or election metrics
Some relay set algorithms that meet these criteria are described in the appendices of this document 📚 More relay set selection algorithms may be specified in separate specifications later on. Each appendix subsection in this document can act as a template for specifying additional relay algorithms 🎀
Figure 5 shows an information flow diagram of possible relay set control options 👑 The SMF Relay Set State is the information base SMF uses in the forwarding decision process. The diagram shows that the SMF Relay Set State can be determined by three fundamentally different methods:
- Independent operation with NHDP [RFC6130] input providing dynamic network neighborhood adjacency information, used by a particular relay set selection algorithm.
- Slave operation with an existing unicast MANET routing protocol, capable of providing CDS election information for use by SMF.
- Cross-layer operation that may involve L2 triggers or information describing neighbors or links.
Other heuristics that influence and control election can come from network management or other interfaces, as shown on the right of Figure 5. CF mode keeps things simple and doesn't need other input, since it relies solely on DPD 🫶
Possible L2 Trigger/Information
|
|
______________ ______v_____ __________________
| MANET | | | | |
| Neighborhood | | Relay Set | | Other Heuristics |
| Discovery |----------->| Selection |<------|(Preference, etc.)|
| Protocol | neighbor | Algorithm | | Net Management |
|______________| info |____________| |__________________|
\ /
\ /
neighbor\ / Dynamic Relay
info* \ ____________ / Set Status
\ | SMF | / (State, {neighbor info})
`-->| Relay Set |<--'
| State |
-->|____________|
/
/
______________
| Coexistent |
| MANET |
| Unicast |
| Process |
|______________|
Figure 5: SMF Reduced Relay Set Information FlowHere's more on the three styles of SMF operation with reduced relay sets shown in Figure 5 ✨
- Independent operation: In this case, SMF operates independently from any unicast routing protocols. To support reduced relay sets, SMF MUST perform its own relay set selection using information gathered from signaling. It is RECOMMENDED that an associated NHDP process be used for this signaling. NHDP messaging SHOULD be appended with additional [RFC5444] type-length-value (TLV) content to support SMF-specific requirements, as discussed in [RFC6130], and to support specific relay set operation as described in the appendices of this document or future specifications. Unicast routing protocols may coexist, even using the same NHDP process, but signaling that supports reduced relay set selection for SMF is independent of these protocols 💅
- Operation with CDS-aware unicast routing protocol: In this case, a coexistent unicast routing protocol provides dynamic relay set state based on its own control plane CDS or neighborhood discovery information 🦋
- Cross-layer operation: In this case, 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) 🌈
8. SMF Neighborhood Discovery Requirements ✨
This section defines the requirements for using the MANET Neighborhood Discovery Protocol (NHDP) [RFC6130] to support SMF operation. Basic CF forwarding needs no neighborhood topology knowledge, since in this configured mode every SMF router relays all traffic 🍓 Supporting more reduced SMF relay set operation requires discovering and maintaining dynamic neighborhood topology information. NHDP can provide this necessary information, but there are SMF-specific requirements for NHDP use. This applies both to "independent" SMF operation, where NHDP is used specifically to support SMF, and to when one NHDP instance is used for both SMF and a coexistent MANET unicast routing protocol 🫶
NHDP HELLO messages and the resulting neighborhood information base are described separately within the NHDP specification. To sum up, NHDP provides these basic functions:
- 1-hop neighbor link sensing and bidirectionality checks of neighbor links,
- 2-hop neighborhood discovery, including collection of 2-hop neighbors and connectivity information,
- Collection and maintenance of the above information across multiple interfaces, and
- A method for signaling SMF information throughout the 2-hop neighborhood through the use of TLV extensions.
Appendices A-C of this document describe CDS-based relay set selection algorithms that can achieve efficient SMF operation, even in dynamic, mobile networks. Each of these algorithms has been initially experimented with in a working SMF prototype [MDDA07] 🧚 When these algorithms are used in conjunction with NHDP, a method verifying neighbor SMF operation is required in order to ensure correct relay set selection. NHDP, along with SMF operation verification, provides the necessary information these algorithms need to do relay set selection. Verification of SMF operation may be done administratively or through the use of the SMF relay algorithm TLVs defined in the following subsections. Use of the SMF relay algorithm TLVs is RECOMMENDED when using NHDP for SMF neighborhood discovery 💜
Section 8.1 specifies SMF-specific TLV types, supporting general SMF operation or supporting the algorithms described in the appendices. The appendices that describe several relay set algorithms also specify any additional requirements for use with NHDP and reference the applicable TLV types as needed 👑
8.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 Block TLV type 🌸
8.1.1. SMF Message TLV Type 💖
okay so the Message TLV type called SMF_TYPE is how you spot an SMF instance that's working alongside NHDP 🫶 it uses the extended type field from [RFC5444] to carry the CDS relay set selection algorithm the SMF message originator is currently running. 🧚 when NHDP is powering SMF, the SMF_TYPE TLV (with the right extended type value in it) SHOULD be included in NHDP_HELLO messages (HELLO messages as defined in [RFC6130]). this lets SMF routers see when their neighbors are using NHDP to swap info, including which algorithm type they're on and the algorithm details that go with it. 👀 that intel can be used to act on it, like ignoring neighbor info from incompatible algorithms. it's possible that SMF neighbors MAY be configured differently and still work together just fine 🌈 but how that goes really depends on which algorithm types are involved.
this document defines a Message TLV type as specified in Table 6, following [RFC5444]. the TLV extended type field holds the sender's "Relay Algorithm Type" 💅 and what the <value> content means is defined separately for each "Relay Algorithm Type." it may also carry algorithm-specific info.
+---------------+----------------+--------------------+
| | 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 TLVin Table 6, <relayAlgorithmId> is an 8-bit field holding a number from 0-255 that represents the "Relay Algorithm Type" of the originator address of the matching NHDP message. 🦋
the values for <relayAlgorithmId> are listed in Table 7. the table covers the assigned values, future IANA assignment spaces, and an experimental space. ⚠️ the experimental space use MUST NOT assume uniqueness, so it SHOULD NOT be used for general interoperable deployment before official IANA assignment. no cap, that's a big one 💀
+-------------+--------------------+--------------------------------+
| Type Value | Extended Type | Algorithm |
| | Value | |
+-------------+--------------------+--------------------------------+
| SMF_TYPE | 0 | CF |
| SMF_TYPE | 1 | S-MPR |
| SMF_TYPE | 2 | E-CDS |
| SMF_TYPE | 3 | MPR-CDS |
| SMF_TYPE | 4-127 | Future Assignment STD action |
| SMF_TYPE | 128-239 | No STD action required |
| SMF_TYPE | 240-255 | Experimental Space |
+-------------+--------------------+--------------------------------+
Table 7: SMF Relay Algorithm Type Valuesthe acceptable <length> and <value> fields of an SMF_TYPE TLV depend on the extended type value (aka the relay algorithm type) ✨ the algorithm type, carried in the <tlv-type-ext> field, decides what the TLV <value> field means and how it's formatted. for the algorithms this document defines, check the matching appendix for the <value> format 🎀
8.1.2. SMF Address Block TLV Type 🌸
the Address Block TLV type called SMF_NBR_TYPE (short for SMF neighbor relay algorithm) is set out in Table 8. this TLV lets CDS relay algorithm operation and configuration get shared across 2-hop neighborhoods 🍓 some relay algorithms need 2-hop neighbor config to pick their relay sets properly, and it's also handy when mixed relay algorithm operation is possible. the appendices have some mixed-use examples.
the SMF_TYPE message TLV and the Address Block SMF_NBR_TYPE TLV share the same format.
+---------------+----------------+--------------------+
| | TLV syntax | Field Values |
+---------------+----------------+--------------------+
| type | <tlv-type> | SMF_NBR_TYPE |
| extended type | <tlv-type-ext> | <relayAlgorithmId> |
| length | <length> | variable |
| value | <value> | variable |
+---------------+----------------+--------------------+
Table 8: SMF Type Address Block TLV<relayAlgorithmId> in Table 8 is an 8-bit unsigned integer field holding a number from 0-255, which represents the "Relay Algorithm Type" value linked to any associated address in the address block. 🧚♀️ quick note: "Relay Algorithm Type" values for 2-hop neighbors can be sent in one TLV or in multiple value TLVs, as described in [RFC5444]. SMF routers using NHDP are expected to build address blocks with SMF_NBR_TYPE TLVs, so they can advertise their own "Relay Algorithm Type" and pass along the neighbor algorithm values they got in SMF_TYPE TLVs from those neighbors. 💜
again, the values for <relayAlgorithmId> are defined in Table 7.
the "value" field of SMF_NBR_TYPE TLVs is interpreted per "Relay Algorithm Type" and may hold algorithm-specific info 🔥 check the appropriate appendix for the value field definitions of the algorithms this document defines.
9. SMF Border Gateway Considerations 🌈
it's expected that SMF will be used to give simple forwarding of multicast traffic inside a MANET or mesh routing topology 🫶 a border router gateway approach should be used to connect SMF routing domains with networks running other multicast routing protocols, like PIM. 👑 there are a lot of scenario-specific issues to think about with border multicast routers. right now, experimental SMF and PIM border router approaches have been demonstrated [DHS08]. some of the stuff border routers may need to handle includes the following:
- Determination of which multicast group traffic transits the border router, whether it's entering or exiting the attached SMF routing domain.
- Enforcement of TTL/hop limit threshold or other scoping policies.
- Any marking or labeling to enable DPD on ingressing packets.
- Interface with exterior multicast routing protocols.
- Possible operation with multiple border routers (presently beyond the scope of this document).
- Provisions for participating non-SMF devices (routers or hosts).
each of these areas gets a closer look in the subsections below. 🦋 note that SMF border routers behave the same as non-border SMF routers when they forward packets on interfaces inside the SMF routing domain. packets passed outbound to interfaces running fixed-infrastructure multicast routing protocols SHOULD be checked for duplicate packet status, since current standard multicast forwarding mechanisms don't usually do this job 💅
9.1. Forwarded Multicast Groups ✨
mechanisms for dynamically figuring out which groups to forward into a MANET SMF routing domain are still an evolving area 🧚 ideally, only traffic with active group membership should get injected into the SMF domain. that can be done by offering an IPv4 Internet Group Membership Protocol (IGMP) or IPv6 Multicast Listener Discovery (MLD) proxy protocol, so MANET SMF routers can tell attached border routers (and by extension the multicast networks) about their current group membership status. 🍓 for some specific systems and services, you might be able to statically configure group membership joins in border routers, but it is RECOMMENDED that some form of IGMP/MLD proxy or other explicit, dynamic membership control be provided. 🙈 specifying such an IGMP/MLD proxy protocol is beyond the scope of this document.
for outbound traffic, SMF border routers do duplicate packet detection and forward non-duplicate traffic that meets the TTL/hop limit and scoping criteria to interfaces outside the SMF routing domain 🌸 appropriate IP multicast routing (e.g., PIM-based solutions) on those interfaces can make further forwarding decisions about the multicast packet. note that having multiple border routers attached to a MANET routing domain raises extra issues. this is discussed further in Section 9.4, but more work is expected to be needed here. 🔥
9.2. Multicast Group Scoping 💜
multicast scoping is how network admins control which network routing domains multicast packets can reach 💅 usually this is done by setting up external interfaces of border routers at the edge of a routing domain so they don't forward multicast packets that have to stay inside the SMF routing domain. it's commonly based on the TTL/hop limit of messages, or on using administratively scoped group addresses. these schemes are known as:
- TTL scoping.
- Administrative scoping.
for IPv4, network admins can configure border routers with the right TTL/hop limit thresholds or administratively scoped multicast groups for the router interfaces, same as with any traditional multicast router. ⚠️ however, for TTL/hop limit scoping, it SHOULD be taken into account that the packet could traverse multiple hops inside the MANET SMF routing domain before it reaches the border router. so TTL thresholds SHOULD be selected carefully 🥺
for IPv6, multicast address spaces include info about the scope of the group 🎀 so border routers in an SMF routing domain know whether they must forward a packet based on the IPv6 multicast group address. for IPv6, it is RECOMMENDED that a MANET SMF routing domain be designated a site-scoped multicast domain. that means all IPv6 site-scoped multicast packets in the range FF05::/16 SHOULD be kept inside the MANET SMF routing domain by border routers. IPv6 packets in any other, wider scopes (i.e., FF08::/16, FF0B::/16, and FF0E::16) MAY traverse border routers, unless other restrictions different from the scope apply. 🌈
given that scoping of multicast packets happens at the border routers, and given that existing scoping mechanisms aren't designed to work with mobile routers, it's assumed that non-border routers running SMF will not stop forwarding multicast data packets of an appropriate site scope. so basically, it's assumed that an SMF routing domain is a site-scoped multicast area ✨
9.3. Interface with Exterior Multicast Routing Protocols 🌐
okay so, bestie, traditional multicast routing is basically joined at the hip with group membership 💜 Leaf routers are set up to periodically gather group membership info, and intermediate routers team up to build multicast trees that connect routers with directly attached multicast sources to routers with active receivers. In the SMF case, border routers count as leaf routers 🧚 We still need mechanisms so multicast sources and receivers can talk to border routers across the multi-hop MANET SMF routing domain as if they were plugged right into the router. Three issues need sorting out:
- A mechanism by which border routers gather membership information
- A mechanism by which multicast sources are known by the border router
- A mechanism for exchange of exterior routing protocol messages across the SMF routing domain if the SMF routing domain is to provide transit connectivity for multicast traffic.
It's out of scope for this document to pick implementation solutions for these 🙈 As described in Section 9.1, IGMP/MLD proxy mechanisms can help with some of them ✨ Exterior routing protocol messages could also be tunneled or carried across an SMF routing domain, but doing that robustly in a distributed wireless environment probably needs extra considerations that live outside this document 💅
The border router needs to receive traffic from recognized multicast sources inside the SMF routing domain, and this is a big deal for interoperating with some existing routing protocols 🔥 For example, PIM-S requires routers with locally attached multicast sources to register them with the Rendezvous Point (RP) so that other routers can join the multicast tree. And if those sources aren't advertised to other autonomous systems (ASes) using Multicast Source Discovery Protocol (MSDP), receivers in those external networks can't join the multicast tree for that source 😭
9.4. Multiple Border Routers 🦋
An SMF routing domain might be deployed with multiple participating routers that have connectivity to external, fixed-infrastructure networks. Letting several routers forward multicast traffic to and from the SMF routing domain can be super beneficial, since it can boost reliability and give better service ✨ For example, if the SMF routing domain splits up, with different SMF routers staying connected to different border routers, multicast service can still keep going successfully 🫶 But having multiple border routers connecting an SMF routing domain to external networks brings some real challenges for SMF:
- Handling duplicate unmarked IPv4 or IPv6 (without IPsec encapsulation or DPD option) packets possibly injected by multiple border routers.
- Handling of duplicate traffic injected by multiple border routers by source-based relay algorithms.
- Determining which border router(s) will forward outbound multicast traffic.
- Additional challenges with interfaces to exterior multicast routing protocols.
When there are multiple border routers, they may be injecting common traffic into the SMF routing domain either alternately (because of route changes) or at the same time, and that traffic hasn't been previously marked for IPv6 SMF_DPD 🌸 Different border routers can't implicitly sync up their sequencing of injected traffic, since they might not receive exactly the same messages because of packet losses. For IPv6 I-DPD operation, the optional TaggerId field described for the SMF_DPD option header can help with this issue 💖 When multiple border routers are injecting a flow into an SMF routing domain, SMF routers running I-DPD can implement one of two forwarding policies:
- Redundantly forward the multicast flows (identified by
<srcAddr: dstAddr>) from each border router, performing DPD processing on a<TaggerID:dstAddr>or<TaggerID:srcAddr:dstAddr>basis, or - Use some basis to select the flow of one tagger (border router) over the others and forward packets for applicable flows (identified by
<sourceAddress:dstAddr>) only for the selected TaggerId until timeout or some other criteria to favor another tagger occurs.
It is RECOMMENDED that the first approach be used in the case of I-DPD operation. 👑 Additional specification may be required to describe an interoperable forwarding policy based on this second option. Heads up: implementing the second option means per-flow state (i.e., <srcAddr::dstAddr>) has to be maintained for the selected TaggerId 👀
H-DPD operation might help take the pressure off 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 ✨
10. Security Considerations 🛡️
Gratuitous use of option headers can cause problems in routers 💀 Other IP routers outside an SMF routing domain that might receive forwarded multicast SHOULD ignore SMF-specific IPv6 header options when they run into them. The header option types are encoded appropriately to allow for this behavior 🫶
This section briefly talks about several SMF denial-of-service (DoS) attack scenarios and offers some initial recommended mitigation strategies. Let's get into it 😤
A potential denial-of-service attack against SMF forwarding is possible when a malicious router has a form of wormhole access to non-adjacent parts of a network topology. In the wireless ad hoc case, a directional antenna is one way to provide such a wormhole physically. If such a router can preview forwarded packets in a non-adjacent part of the network and forward modified versions to another part of the network, it can perform the following attack. The malicious router could reduce the TTL/hop limit or hop limit of the packet and transmit it to the SMF router, causing it to forward the packet with a limited TTL/hop limit (or even drop it) and make a DPD entry that could block or limit the subsequent forwarding of later-arriving valid packets with correct TTL/hop limit values. This would be a relatively low-cost, high-payoff attack that would be hard to detect, which makes it super attractive to potential attackers 😱 An approach of caching TTL/hop limit information with DPD state and taking appropriate forwarding actions is identified in Section 5 to mitigate this form of attack 🔥
Sequence-based packet identifiers are predictable, so they give attackers an opening for a DoS attack against forwarding ✨ Forwarding protocols that use DPD techniques, such as SMF, may be vulnerable to DoS attacks based on spoofing packets with apparently valid packet identifier fields. In wireless environments, which is where SMF will most likely be used, the opportunity for these attacks may be more prevalent than in wired networks. For IPv4 packets, fragmented IP packets, or packets with IPsec headers applied, the DPD "identifier portions" of potential future packets that might be forwarded are highly predictable and easily subject to DoS 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 are kept completely internal to SMF routers, the cryptographic properties of this hashing would not need to be extensive and thus could possibly be of low complexity. Experimental implementations may determine that even a lightweight hash of only portions of packets may suffice to serve this purpose 🧪
H-DPD isn't as readily susceptible to this form of DoS attack, but it's still possible that a sophisticated adversary could use side information to construct spoofing packets that mislead forwarders using a well-known hash algorithm 🕵️♀️ So, similarly, a separate "internal" hash value could be concatenated with the well-known hash value to ease this security concern.
The support of forwarding IPsec packets 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 🔑
Furthermore, when the MANET Neighborhood Discovery Protocol [RFC6130] is used, the security considerations described in [RFC6130] also apply 💜
11. IANA Considerations 🎀
This document defines one IPv6 Hop-by-Hop Option, a type for which has been allocated from the IPv6 "Destination Options and Hop-by-Hop Options" registry of [RFC2780].
This document creates one registry called "TaggerId Types" for recording TaggerId types, (TidTy), as a sub-registry in the "IPv6 Parameters" registry.
This document registers one well-known multicast address from each of the IPv4 and IPv6 multicast address spaces.
This document defines one Message TLV, a type for which has been allocated from the "Message TLV Types" registry of [RFC5444].
Finally, this document defines one Address Block TLV, a type for which has been allocated from the "Address Block TLV Types" registry of [RFC5444] 🌈
11.1. IPv6 SMF_DPD Header Extension Option Type 🦋
IANA has allocated an IPv6 Option Type from the IPv6 "Destination Options and Hop-by-Hop Options" registry of [RFC2780], as specified in Table 9 ✨
+-----------+-------------------------+-------------+---------------+
| Hex Value | Binary Value | Description | Reference |
| | act | chg | rest | | |
+-----------+-------------------------+-------------+---------------+
| 8 | 00 | 0 | 01000 | SMF_DPD | This Document |
+-----------+-------------------------+-------------+---------------+
Table 9: IPv6 Option Type Allocation11.2. TaggerId Types (TidTy) 🎀
okay so the SMF_DPD option data has this bit called the Tagger Identifier Type (TidTy), and its whole job is to give context to the optionally included TaggerId 💅
IANA made a registry for recording TaggerId Types (TidTy) 🌸 The starting values and the allocation rules are all in Table 10, so check it out:
+------+----------+------------------------------------+------------+
| Type | Mnemonic | Description | Reference |
+------+----------+------------------------------------+------------+
| 0 | NULL | No TaggerId field is present | This |
| | | | document |
| 1 | DEFAULT | A TaggerId of non-specific context | This |
| | | is present | document |
| 2 | IPv4 | A TaggerId representing an IPv4 | This |
| | | address is present | document |
| 3 | IPv6 | A TaggerId representing an IPv6 | This |
| | | address is present | document |
| 4-7 | | Unassigned | |
+------+----------+------------------------------------+------------+
Table 10: TaggerId TypesFor allocating the unassigned values 4-7, IETF Review [RFC5226] is required 🦋
11.3. Well-Known Multicast Address 🌈
okay this one is iconic 👑 IANA gave the IPv4 multicast address 224.0.1.186 the name "SL-MANET-ROUTERS". It came out of the "Internetwork Control Block (224.0.1.0-224.0.1.255 (224.0.1/24))" sub-registry of the "IPv4 Multicast Address" registry ✨
IANA also gave an IPv6 multicast address the same name, "SL-MANET-ROUTERS" 🧚 That one came from the "Site-Local Scope Multicast Addresses" sub-sub-registry, which lives under the "Fixed Scope Multicast Addresses" sub-registry of the "INTERNET PROTOCOL VERSION 6 MULTICAST ADDRESSES" registry. so many layers, bestie 😭
11.4. SMF TLVs 💜
11.4.1. Expert Review for Created Type Extension Registries 🔥
so when Address Block TLV Types and Message TLV Types get created in the registries of [RFC5444], and therefore in the HELLO-message-specific registries of [RFC6130], you also end up creating a matching Type Extension registry for each one of those types 🍓 For those Type Extension registries that need an Expert Review, the designated expert SHOULD keep in mind the same general recommendations that [RFC5444] lays out. honestly that's just good manners 🫶
11.4.2. SMF Message TLV Type (SMF_TYPE) 🎀
this document defines one Message TLV Type, "SMF_TYPE" ✨ It was allocated from the "HELLO Message-Type-specific Message TLV Types" registry, which is defined in [RFC6130].
That created a brand new Type Extension registry, and its starting assignments are in Table 11 💖
+----------+------+-----------+--------------------+----------------+
| Name | Type | Type | Description | Allocation |
| | | Extension | | Policy |
+----------+------+-----------+--------------------+----------------+
| SMF_TYPE | 128 | 0-255 | Specifies relay | Section 11.4.4 |
| | | | algorithm | |
| | | | supported by the | |
| | | | SMF router, | |
| | | | originating the | |
| | | | HELLO message, | |
| | | | according to | |
| | | | Section 11.4.4. | |
+----------+------+-----------+--------------------+----------------+
Table 11: SMF_TYPE Message TLV Type Extension Registry11.4.3. SMF Address Block TLV Type (SMF_NBR_TYPE) 🌸
this document defines one Address Block TLV Type, "SMF_NBR_TYPE" 🦋 It was allocated from the "HELLO Message-Type-specific Address Block TLV Types" registry, which is defined in [RFC6130].
This created a new Type Extension registry too, and the starting assignments are in Table 12 🧚
+--------------+--------+-----------+-----------------+-------------+
| Name | Type | Type | Description | Allocation |
| | | Extension | | Policy |
+--------------+--------+-----------+-----------------+-------------+
| SMF_NBR_TYPE | 128 | 0-255 | Specifies relay | Section |
| | | | algorithm | 11.4.4 |
| | | | supported by | |
| | | | the SMF router | |
| | | | corresponding | |
| | | | to the | |
| | | | advertised | |
| | | | address, | |
| | | | according to | |
| | | | Section 11.4.4. | |
+--------------+--------+-----------+-----------------+-------------+
Table 12: SMF_NBR_TYPE Address Block TLV Type Extension Registry11.4.4. SMF Relay Algorithm ID Registry 👑
okay the Type Extension registries for the SMF_TYPE Message TLV and the SMF_NBR_TYPE Address Block TLV get merged into one single registry, the SMF Relay Algorithm ID Registry, and that's what this section is about ✨ The whole vibe is unity 🫶
IANA created a registry for recording Relay Algorithm Identifiers 💅 The starting assignments and allocation policies are in Table 13:
+---------+---------+-------------+-------------------+
| Value | Name | Description | Allocation Policy |
+---------+---------+-------------+-------------------+
| 0 | CF | Section 4 | |
| 1 | S-MPR | Appendix B | |
| 2 | E-CDS | Appendix A | |
| 3 | MPR-CDS | Appendix C | |
| 4-127 | | Unassigned | Expert Review |
| 128-255 | | Unassigned | Experimental Use |
+---------+---------+-------------+-------------------+
Table 13: Relay Set Algorithm Type ValuesNow the important bit 🔥 A specification that asks for an allocation from the 4-127 range of the SMF Relay Algorithm ID Registry MUST specify the interpretation of the <value> field (if any). no skipping that one, periodt 💀
Heads up: that MUST is non-negotiable. If you're requesting a value in the 4-127 range, you have to spell out what <value> means.
12. Acknowledgments 🫶
lots of the SMF concepts came together over several years of discussion and related work in the MANET working group, going all the way back to the late 1990s 🦋 There are obviously tons of people who contributed to past discussions and related drafts in the working group and shaped how SMF came to be, and they deserve a shoutout. In particular, this document is largely a direct product of the earlier SMF design team in the IETF MANET working group, and it borrows text and implementation ideas from those folks and their activities 🌈
These are some of the direct contributors who helped with design, content editing, prototype implementation, major commenting, and core discussions, listed alphabetically 💖
- Brian Adamson
- Teco Boot
- Ian Chakeres
- Thomas Clausen
- Justin Dean
- Brian Haberman
- Ulrich Herberg
- Charles Perkins
- Pedro Ruiz
- Fred Templin
- Maoyu Wang
And to everyone else in the community and the early implementation users who gave input and feedback but aren't on this list, we appreciate you so much 🌸✨
13. References 📚
13.1. Normative References 🎀
- [MPR-CDS] Adjih, C., Jacquet, P., and L. Viennot, "Computing Connected Dominating Sets with Multipoint Relays", Ad Hoc and Sensor Wireless Networks, January 2005.
- [RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791, September 1981.
- [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
- [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. and V. Paxson, "IANA Allocation Guidelines For Values In the Internet Protocol and Related Headers", BCP 37, RFC 2780, March 2000.
- [RFC3174] Eastlake, D. and P. Jones, "US Secure Hash Algorithm 1 (SHA1)", RFC 3174, September 2001.
- [RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing Protocol (OLSR)", RFC 3626, October 2003.
- [RFC4291] Hinden, R. and S. Deering, "IP Version 6 Addressing Architecture", RFC 4291, February 2006.
- [RFC4302] Kent, S., "IP Authentication Header", RFC 4302, December 2005.
- [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 5226, May 2008.
- [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, "Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format", RFC 5444, February 2009.
- [RFC5614] Ogier, R. and P. Spagnolo, "Mobile Ad Hoc Network (MANET) Extension of OSPF Using Connected Dominating Set (CDS) Flooding", RFC 5614, August 2009.
- [RFC5771] Cotton, M., Vegoda, L., and D. Meyer, "IANA Guidelines for IPv4 Multicast Address Assignments", BCP 51, RFC 5771, March 2010.
- [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)", RFC 6130, April 2011.
13.2. Informative References 📚
Okay bestie, this is the extra-credit reading list 🤓 These are the references that are good to know, but you don't need them to get the spec working.
- [CDHM07] Chakeres, I., Danilov, C., Henderson, T., and J. Macker, "Connecting MANET Multicast", IEEE MILCOM 2007 Proceedings, 2007.
- [DHG09] Danilov, C., Henderson, T., Goff, T., Kim, J., Macker, J., Weston, J., Neogi, N., Ortiz, A., and D. Uhlig, "Experiment and field demonstration of a 802.11-based ground-UAV mobile ad-hoc network", Proceedings of the 28th IEEE conference on Military Communications, 2009.
- [DHS08] Danilov, C., Henderson, T., Spagnolo, T., Goff, T., and J. Kim, "MANET Multicast with Multiple Gateways", IEEE MILCOM 2008 Proceedings, 2008.
- [GM99] Garcia-Luna-Aceves, JJ. and E. Madruga, "The Core-Assisted Mesh Protocol", Selected Areas in Communications, IEEE Journal, Volume 17, Issue 8, August 1999.
- [IPV4-ID-UPDATE] Touch, J., "Updated Specification of the IPv4 ID Field", Work in Progress, September 2011.
- [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.
- [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 a Mobile Ad Hoc Network", Proceedings of ACM Mobicom 99, 1999.
- [RFC2501] Corson, M. and J. Macker, "Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations", RFC 2501, January 1999.
- [RFC3684] Ogier, R., Templin, F., and M. Lewis, "Topology Dissemination Based on Reverse-Path Forwarding (TBRPF)", RFC 3684, February 2004.
- [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.
Appendix A. Essential Connecting Dominating Set (E-CDS) Algorithm 🧚
Okay this part is so iconic 😭 The "Essential Connected Dominating Set" (E-CDS) algorithm [RFC5614] builds a single CDS mesh for the SMF operating region. Routers look at their 2-hop neighborhood topology info and dynamically self-elect as relays to form the CDS. The packet-forwarding rules don't depend on previous hop knowledge, which is so clean 💅 E-CDS SMF forwarders also mix easily with CF SMF forwarders, even ones that aren't in NHDP. Packets opportunistically received from non-symmetric neighbors can be forwarded without hurting flooding efficiency or correctness. And multicast sources that aren't in NHDP can inject their traffic freely, and any neighboring E-CDS relays will forward it properly 🦋 The E-CDS relay set selection is based on [RFC5614]. E-CDS was first discussed for forming partial adjacencies and efficient flooding in the MANET OSPF extensions work, and this appendix applies the core algorithm to SMF 🌸
It is RECOMMENDED that the SMF_TYPE:E-CDS Message TLV be included in NHDP_HELLO messages generated by routers running 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 running E-CDS SMF operation 💜
A.1. E-CDS Relay Set Selection Overview
The E-CDS relay set selection needs 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 called Router Priority, for all 1-hop and 2-hop neighbors. For 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 the Router ID and Router Priority through 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. 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 goes like this ✨
- 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.
- 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 in this specification does not provide for redundant relay set selection (e.g., bi-connected). The basic E-CDS design can support that capability, though 🙈
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 💖
- Upon packet reception, DPD is performed. Note that E-CDS requires a single duplicate table for the set of interfaces associated with the relay set selection.
- If the packet is a duplicate, no further action is taken.
- 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 mentioned before, even packets sourced or relayed by routers that aren't in NHDP and/or the E-CDS relay set selection can be forwarded by E-CDS forwarders without problems 🍓 A particular deployment MAY choose to not forward packets from previous hop routers that haven't been explicitly identified via NHDP or other means as running a different relay set algorithm (e.g., S-MPR). This keeps coexistent deployments working 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 🦋
okay so you can absolutely do E-CDS relay set selection without modifying NHDP 💅 you just base the whole self-election thing on the "Neighbor Address List" of the participating SMF routers. like, set the Router Priority to a default value and pick the numerically largest address in that list as your Router ID ✨ BUT (big but 🙈) steps MUST be taken to make sure that every NHDP-enabled router not using SMF_TYPE:E-CDS full type Message TLVs is actually running SMF E-CDS with the same methods for picking Router Priority and Router ID. otherwise, incorrect forwarding may occur 💀 also, SMF routers with higher Router Priority values get favored as relays over the lower ones, so preferred relays MAY be administratively configured to get picked when possible 👑 other metrics (like nodal degree or energy capacity) can also count when you build a Router Priority value 🌈 and when a router has multiple interfaces, all of them MUST use and advertise the same Router Priority value 🫶 a router's Router Priority can be set administratively or algorithmically, and different routers don't have to use the same method 🧚
E-CDS relay set selection can also be influenced by statically configured CF relays that are found through NHDP or some other way. nodes that advertise CF through NHDP can be treated as 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 gets defined like this 🍓
+----------------+---------+-----------------+
| Length (bytes) | Value | Router Priority |
+----------------+---------+-----------------+
| 0 | N/A | 64 |
| 1 | <value> | 0-127 |
+----------------+---------+-----------------+
Table 14: E-CDS Message TLV Valueswhere <value> is a one-octet-long bit field, and it breaks down like this:
- 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 the ones listed here are NOT permitted and SHOULD be ignored 🙅♀️ here's an example SMF_TYPE:E-CDS Message TLV, aka Figure 6 🎀
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 Exampleto pass Router Priority values around the 2-hop neighborhoods, the SMF_NBR_TYPE:E-CDS Address Block TLV's <value> field comes in clutch 🧚✨ multi-index and multivalue TLV layouts as defined in [RFC5444] are supported. the SMF_NBR_TYPE:E-CDS value fields are defined like so:
+---------------+--------+----------+-------------------------------+
| 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 Valueswhere <value> is a one-byte bit field, and here's the breakdown 🌸
- 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 the ones specified here are NOT permitted and SHOULD be ignored. a default technique of using nodal degree (aka the count of 1-hop neighbors) is RECOMMENDED for the value field of these TLV types 💖 two example SMF_NBR_TYPE:E-CDS Address Block TLVs are shown below.
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 1the single value example TLV (Figure 7) says that all the address(es) in the address block are running SMF using the E-CDS algorithm, and they all share the value field, so they all have 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 2and the multivalued example TLV (Figure 8) says that the address(es) from index-start to index-end (inclusive) are running SMF using the E-CDS algorithm. each address gets its own value byte, so each one also gets its own Router Priority 🌈
A.4. E-CDS Selection Algorithm 👑
this section describes an algorithm for E-CDS relay selection (self-election) 🔥 it uses 2-hop information. it's possible to extend this algorithm to use k-hop information, but that comes with added computational complexity and mechanisms for sharing k-hop topology information, and neither of those are described in this document or in the NHDP specification 🙈 it should also be noted that this algorithm does not impose the hop limit bound described in [RFC5614] when doing the path search used for relay selection. the algorithm below could be easily augmented to accommodate that extra criterion, though. it's 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. Router Priority gets precedence, and the Router ID is the tiebreaker 🎀 the evaluation of this tuple is called "RtrPri(n)" below, where "n" points to a specific router. it's possible that the Router Priority portion is optional, and then the evaluation of "RtrPri()" is based solely on the unique Router ID. since there MUST NOT be any duplicate Router ID values among SMF routers, comparing "RtrPri(n)" between any two routers will always be an inequality ✨ using nodal degree to calculate Router Priority is RECOMMENDED as the default, and the largest IP address in the "Neighbor Address List" as advertised by NHDP MUST be used as the Router ID. NHDP already gives all the interface addresses throughout the 2-hop neighborhood through HELLO messages, so explicitly conveying a Router ID isn't necessary 🧚 here's the basic algorithm for running E-CDS relay selection for a router "n0":
- Initialize the set "N1" with tuples ("Router Priority", "Router ID", "Neighbor Address List") for each 1-hop neighbor of "n0".
- If "N1" has less than 2 tuples, then "n0" does not elect itself as a relay, and no further steps are taken.
- 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.
- 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.
- Initialize all tuples in the union of "N1" and "N2" as "unvisited".
- Find the tuple "n1_Max" that has the largest "RtrPri()" of all tuples in "N1".
- Initialize queue "Q" to contain "n1_Max", marking "n1_Max" as "visited".
- 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".
- 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 get re-evaluated whenever the neighborhood status changes 🌸 steps 5 through 8 describe a path search approach. the point of this path search is to figure out whether paths exist from the 1-hop neighbor with the maximum "RtrPri()" to all the other 1-hop neighbors, without going through any intermediate router whose "RtrPri()" is less than "RtrPri(n0)" 💜 these steps are a breadth-first traversal that only checks paths meeting that condition. if every 1-hop neighbor of "n0" gets "visited" during this traversal, the path search has succeeded, and router "n0" doesn't need to provide relay. it can be assumed that other routers will provide relay operation to keep SMF connectivity going 🫶
it's possible to extend this algorithm to consider neighboring SMF routers that are statically configured for CF (always relaying) 🍓 the change is to treat those routers as having a maximum possible Router Priority value. routers configured for CF that participate in NHDP are expected to indicate this with 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 ✨
okay so the source-based multipoint relay (S-MPR) set selection algorithm is lowkey the most iconic thing 💅 It lets individual routers, using 2-hop topology info, pick their relays out of their neighboring routers. The relays get chosen so that forwarding covers the router's complete 2-hop neighbor set, so no one gets left out 🦋 This distributed relay selection technique has been shown to approximate a minimal connected dominating set (MCDS) in [JLMV02]. Each router has to collect 2-hop neighborhood info from its neighbors, figure out its current relay set, and let the selected neighbors know they got picked 🫶 Since each router picks its neighboring relays independently, S-MPR forwarders depend on previous hop info (e.g., source MAC address) to work correctly. The Optimized Link State Routing (OLSR) protocol has used this algorithm and protocol to relay 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
okay so S-MPR uses bi-directional 1-hop and 2-hop neighborhood info collected via NHDP to pick, from a router's 1-hop neighbors, a set of relays that will cover the router's entire 2-hop neighbor set once they forward 🌸 The algorithm uses a "greedy" heuristic, which is giving first pick to the 1-hop neighbor who covers the most 2-hop neighbors ✨ Then, after excluding the 2-hop neighbors that are already covered, more relays get picked from the 1-hop neighbor set again and again until the whole 2-hop neighborhood is covered 🍓 Fun detail: any 1-hop neighbor that is also identified as a 2-hop neighbor is only treated as a 1-hop neighbor 🙈
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 with a full type value of SMF_NBR_TYPE:S-MPR is defined in Table 17, so signaling MPR selections to 1-hop neighbors is possible 🫶 The value field of a message block TLV with a full type value of SMF_TYPE:S-MPR is defined in Table 16, so signaling Router Priority (called "WILLINGNESS" in [RFC3626]) to 1-hop neighbors is possible 🌈 Okay, this next part is so important 😭 S-MPR forwarding depends on 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 extra requirements for duplicate packet detection to support S-MPR SMF operation, which we'll go through below 🎀
For multiple interface operation, MPR selection SHOULD be conducted on a per-interface basis 🦋 It is possible to economize MPR selection among multiple interfaces by selecting common MPRs to the extent possible ✨
B.2. S-MPR Forwarding Rules
bestie, 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 comes with some extra duplicate packet detection operations 💜 For multiple network interfaces, independent DPD state MUST be maintained for each separate interface 🔥 Here's the procedure for S-MPR packet forwarding when a packet arrives on a given interface, denoted <srcIface>. There are three possible actions, depending on the previous-hop transmitter 🧚
- 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.
- 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 🙈
- Otherwise, no action is taken.
Action number two is kinda non-intuitive, but it's SO important for S-MPR SMF operation to be correct 😭 Source-based relays don't end up as 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 🫶 If you deviate here, you can get unnecessary, repeated packet forwarding all over the network, or incomplete flooding 💀
Nodes that aren't taking part in neighborhood discovery and relay set selection won't be able to source multicast packets into the area and have SMF forward them 🥺 That's different from E-CDS or MPR-CDS, where forwarding may depend on topology. Correct S-MPR relay behavior comes with the introduction of repeaters (non-NHDP/SMF participants that relay multicast packets using duplicate detection and CF) 🌸 But repeaters won't contribute efficiently to S-MPR forwarding, since these routers won't be identified as neighbors (symmetric or otherwise) in the S-MPR forwarding process 🍓 NHDP/SMF participants MUST NOT forward packets that the algorithm didn't select, because that can disrupt network-wide S-MPR flooding and cause incomplete or inefficient flooding 👑 The bottom line is that non-S-MPR SMF routers won't be able to source multicast packets and have other S-MPR SMF routers forward them 💅
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. Here's the summary 🎀
+---------------+---------+-----------------+
| Length(bytes) | Value | Router Priority |
+---------------+---------+-----------------+
| 0 | N/A | 64 |
| 1 | <value> | 0-127 |
+---------------+---------+-----------------+
Table 16: S-MPR Message TLV ValuesWhere <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 read the same way as "WILLINGNESS" ([RFC3626]), so the value 0 means a router will NEVER forward, and the value 127 means a router will ALWAYS forward 😭 Values 1-126 show how likely an S-MPR SMF router is to be selected as an MPR by a neighboring SMF router, and higher values make that more likely 🦋 Combinations of value field lengths and values other than those specified here are NOT permitted and SHOULD be ignored 🙈 Here's 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 ExampleS-MPR election operation needs 2-hop neighbor knowledge, which NHDP [RFC6130] provides or which comes from external sources ✨ MPRs get selected dynamically 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 like this 🍓
+---------------+--------+----------+-------------------------------+
| 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 ValuesWhere <value>, if present, is a one-octet bit field defined as:
bit 0: The leftmost bit is the M bit. When it's set, it indicates MPR selection of the relevant interface, represented by the associated address(es), by the originator router of the NHDP HELLO message. When it's 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, except 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 ExampleThe single index TLV example in Figure 10 shows that the address given by the <start-index> field is running SMF using S-MPR, and it has been selected by the originator of the NHDP HELLO message as an MPR forwarder if the M bit is set 🦋 Multivalued TLVs can also be used to specify the MPR selection status of multiple addresses using only one TLV. See Figure 8 for a similar example of how this can be done 🌈
B.4. S-MPR Selection Algorithm 🎀
okay so this section is the basic recipe for picking S-MPRs 🧁 the selection happens for one specific interface of the router doing the picking, and any other router interfaces mentioned are reachable from that reference interface 🫶 that matches the S-MPR forwarding rules we just went through. if a router has multiple interfaces, you can level up the whole process so the same routers get picked as MPRs on each interface and you don't waste flooding effort 💜 but here's the basic version for a router interface "n0":
- Initialize the set "MPR" to empty.
- Initialize the set "N1" to include all 1-hop neighbors of "n0".
- 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.
- For each interface "y" in "N1", initialize a set "N2(y)" to include any interfaces in "N2" that are 1-hop neighbors of "y".
- 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)".
- For each interface "z" in "N2", initialize the set "N1(z)" to include any interfaces in "N1" that are 1-hop neighbors of "z".
- 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)".
- 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)".
once the set of routers "MPR" is picked, router "n_0" must signal its selections to its neighbors ✨ with NHDP, that happens by using the MPR Address Block TLV to mark the 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 💅 and these steps get re-evaluated whenever neighborhood status changes, so stay alert 👀
Appendix C. Multipoint Relay Connected Dominating Set (MPR-CDS) Algorithm 👑
okay this one is giving main character energy 🌈 the MPR-CDS algorithm is an extension of the basic S-MPR election that ends up with a shared, non-source-specific SMF CDS 🦋 so its forwarding rules don't depend on previous hop information, just like E-CDS 🫶 there's an overview of the MPR-CDS selection algorithm in [MPR-CDS] if you want to go deeper.
It is RECOMMENDED that the SMF_TYPE Message TLV be included in NHDP_HELLO messages generated by routers running MPR-CDS SMF operation 🎀
C.1. MPR-CDS Relay Set Selection Overview 🧚
the MPR-CDS relay set selection is built on the S-MPR MPR selection, with an extra distributed step that down-selects to a common, reduced, shared relay set 💖 there's a router ordering (or "prioritization") metric in play here, and like the E-CDS algorithm, it can be based on router address(es) or some other unique router identifier (for example, a Router ID based on the largest address in the "Neighbor Address List"), plus an extra Router Priority measure if you want one 🍓 the MPR-CDS relay selection goes like this:
- First, MPR selection per the S-MPR algorithm is run, with selectors telling their MPRs (via NHDP) about their selection 🌸
- Then, these rules get used on a distributed basis by selected routers, so they can possibly deselect themselves and together set up 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.
- 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 a lot of the good stuff E-CDS has, like working with multicast sources that aren't in NHDP and letting statically configured CF routers be present no matter whether they take part in NHDP 🔥
C.2. MPR-CDS Forwarding Rules 💅
the MPR-CDS forwarding rules are pretty similar to E-CDS 🦋 any SMF router that has picked itself as a relay runs DPD and forwards all non-duplicative multicast traffic that the current forwarding policy allows ✨ packet previous hop knowledge isn't needed for forwarding decisions with MPR-CDS, which is so relatable 🙈
- 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.
- If the packet is a duplicate, no further action is taken.
- 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 we already mentioned, even packets sourced (or relayed) by routers that aren't in NHDP and/or the MPR-CDS relay set selection may be forwarded by MPR-CDS forwarders without problem 🌈 a particular deployment MAY choose not to forward packets from sources or relays that NHDP or other means have explicitly identified as running a different relay set algorithm (e.g., S-MPR), so coexisting deployments can keep working correctly 🧁
C.3. MPR-CDS Neighborhood Discovery Requirements 🎀
the neighborhood discovery requirements for MPR-CDS have stuff in common with both S-MPR and E-CDS ✨ MPR-CDS selection needs 2-hop neighbor knowledge, which comes from NHDP [RFC6130] or from external sources 🫶 unlike S-MPR operation, there's no need to link layer address info with 1-hop neighbors, because MPR-CDS forwarding doesn't depend on the previous hop, just like 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 needs 1-hop knowledge of Router Priority to work right 🦋 during the S-MPR phase of MPR-CDS selection, each router dynamically figures out its MPRs, 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 🧚 the selection described is with respect to one specific interface of the router doing the selecting, and other router interfaces referenced are reachable from that reference router interface ✨ MPR-CDS relay set selection uses an ordered tuple of Router Priority and Router ID 💅 the Router ID value should be set to the largest advertised address of a given router, and NHDP gives this info to 1-hop neighbors by default 🫶 Router Priority gets precedence, and the Router ID value is the tiebreaker 🌸 evaluating this tuple is called "RtrPri(n)" below, where "n" refers to a specific router. it's possible the Router Priority portion is optional, in which case "RtrPri()" is based only on the unique Router ID 🎀 since there MUST NOT be any duplicate address values among SMF routers, comparing "RtrPri(n)" between any two routers will always give an inequality 💀 the following steps, repeated whenever changes are detected within the 1-hop and 2-hop neighborhood, describe a basic algorithm for MPR-CDS selection on a router interface "n0":
- 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.
- Upon being selected as an MPR (or any change in the set of routers 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 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's possible to extend this algorithm to take neighboring SMF routers into account when they're known to be statically configured for CF (always relaying) 🌈 the change is to treat those routers as having a maximum possible Router Priority value, which is the same as participating routers configured with an S-MPR "WILLINGNESS" value of WILL_ALWAYS ✨ routers configured for CF that take part in NHDP are expected to show their status with the SMF_TYPE TLV type in their NHDP_HELLO message TLV block 🧁 but heads up: CF routers won't select MPR routers, so they can't guarantee connectedness 💀
Author's Address 🦋
Joseph Macker (editor)
NRL
Washington, DC 20375
USA
EMail: macker@itd.nrl.navy.mil📦 where this page comes from
- ietf: rfc6621 2012-05
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms