idnits 2.17.1 draft-ietf-manet-smf-14.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document seems to contain a disclaimer for pre-RFC5378 work, and may have content which was first submitted before 10 November 2008. The disclaimer is necessary when there are original authors that you have been unable to contact, or if some do not wish to grant the BCP78 rights to the IETF Trust. If you are able to get all authors (current and original) to grant those rights, you can and should remove the disclaimer; otherwise, the disclaimer is needed and you can ignore this comment. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (March 6, 2012) is 4428 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Unused Reference: 'RFC5226' is defined on line 1652, but no explicit reference was found in the text ** Obsolete normative reference: RFC 2460 (Obsoleted by RFC 8200) ** Obsolete normative reference: RFC 5226 (Obsoleted by RFC 8126) == Outdated reference: A later version (-07) exists of draft-ietf-intarea-ipv4-id-update-04 -- Obsolete informational reference (is this intentional?): RFC 4601 (Obsoleted by RFC 7761) Summary: 2 errors (**), 0 flaws (~~), 3 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group J. Macker, editor 3 Internet-Draft NRL 4 Intended status: Experimental March 6, 2012 5 Expires: September 7, 2012 7 Simplified Multicast Forwarding 8 draft-ietf-manet-smf-14 10 Abstract 12 This document describes a Simplified Multicast Forwarding (SMF) 13 mechanism that provides basic Internet Protocol (IP) multicast 14 forwarding suitable for limited wireless mesh and mobile ad hoc 15 network (MANET) use. It is mainly applicable in situations where 16 efficient flooding represents an acceptable engineering design trade- 17 off. It defines techniques for multicast duplicate packet detection 18 (DPD), to be applied in the forwarding process, for both IPv4 and 19 IPv6 protocol use. This document also specifies optional mechanisms 20 for using reduced relay sets to achieve more efficient multicast data 21 distribution within a mesh topology as compared to classic flooding. 22 Interactions with other protocols, such as use of information 23 provided by concurrently running unicast routing protocols, or 24 interaction with other multicast protocols, as well as multiple 25 deployment approaches are also described. Distributed algorithms for 26 selecting reduced relay sets and related discussion are provided in 27 the appendices. Basic issues relating to the operation of multicast 28 MANET border routers are discussed, but ongoing work remains in this 29 area, and is beyond the scope of this document. 31 Status of this Memo 33 This Internet-Draft is submitted in full conformance with the 34 provisions of BCP 78 and BCP 79. 36 Internet-Drafts are working documents of the Internet Engineering 37 Task Force (IETF). Note that other groups may also distribute 38 working documents as Internet-Drafts. The list of current Internet- 39 Drafts is at http://datatracker.ietf.org/drafts/current/. 41 Internet-Drafts are draft documents valid for a maximum of six months 42 and may be updated, replaced, or obsoleted by other documents at any 43 time. It is inappropriate to use Internet-Drafts as reference 44 material or to cite them other than as "work in progress." 46 This Internet-Draft will expire on September 7, 2012. 48 Copyright Notice 49 Copyright (c) 2012 IETF Trust and the persons identified as the 50 document authors. All rights reserved. 52 This document is subject to BCP 78 and the IETF Trust's Legal 53 Provisions Relating to IETF Documents 54 (http://trustee.ietf.org/license-info) in effect on the date of 55 publication of this document. Please review these documents 56 carefully, as they describe your rights and restrictions with respect 57 to this document. Code Components extracted from this document must 58 include Simplified BSD License text as described in Section 4.e of 59 the Trust Legal Provisions and are provided without warranty as 60 described in the Simplified BSD License. 62 This document may contain material from IETF Documents or IETF 63 Contributions published or made publicly available before November 64 10, 2008. The person(s) controlling the copyright in some of this 65 material may not have granted the IETF Trust the right to allow 66 modifications of such material outside the IETF Standards Process. 67 Without obtaining an adequate license from the person(s) controlling 68 the copyright in such materials, this document may not be modified 69 outside the IETF Standards Process, and derivative works of it may 70 not be created outside the IETF Standards Process, except to format 71 it for publication as an RFC or to translate it into languages other 72 than English. 74 Table of Contents 76 1. Introduction and Scope . . . . . . . . . . . . . . . . . . . . 5 77 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 78 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 6 79 4. Overview and Functioning . . . . . . . . . . . . . . . . . . . 7 80 5. SMF Packet Processing and Forwarding . . . . . . . . . . . . . 9 81 6. SMF Duplicate Packet Detection . . . . . . . . . . . . . . . . 11 82 6.1. IPv6 Duplicate Packet Detection . . . . . . . . . . . . . 12 83 6.1.1. IPv6 SMF_DPD Header Option . . . . . . . . . . . . . . 12 84 6.1.2. IPv6 Identification-based DPD . . . . . . . . . . . . 15 85 6.1.3. IPv6 Hash-based DPD . . . . . . . . . . . . . . . . . 17 86 6.2. IPv4 Duplicate Packet Detection . . . . . . . . . . . . . 18 87 6.2.1. IPv4 Identification-based DPD . . . . . . . . . . . . 18 88 6.2.2. IPv4 Hash-based DPD . . . . . . . . . . . . . . . . . 20 89 7. Relay Set Selection . . . . . . . . . . . . . . . . . . . . . 20 90 7.1. Non-Reduced Relay Set Forwarding . . . . . . . . . . . . . 21 91 7.2. Reduced Relay Set Forwarding . . . . . . . . . . . . . . . 21 92 8. SMF Neighborhood Discovery Requirements . . . . . . . . . . . 23 93 8.1. SMF Relay Algorithm TLV Types . . . . . . . . . . . . . . 24 94 8.1.1. SMF Message TLV Type . . . . . . . . . . . . . . . . . 24 95 8.1.2. SMF Address Block TLV Type . . . . . . . . . . . . . . 26 96 9. SMF Border Gateway Considerations . . . . . . . . . . . . . . 26 97 9.1. Forwarded Multicast Groups . . . . . . . . . . . . . . . . 27 98 9.2. Multicast Group Scoping . . . . . . . . . . . . . . . . . 28 99 9.3. Interface with Exterior Multicast Routing Protocols . . . 28 100 9.4. Multiple Border Routers . . . . . . . . . . . . . . . . . 29 101 10. Security Considerations . . . . . . . . . . . . . . . . . . . 30 102 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 32 103 11.1. IPv6 SMF_DPD Header Extension Option Type . . . . . . . . 32 104 11.2. TaggerId Types (TidTy) . . . . . . . . . . . . . . . . . . 33 105 11.3. Well-known Multicast Address . . . . . . . . . . . . . . . 34 106 11.4. SMF Type-Length-Values . . . . . . . . . . . . . . . . . . 34 107 11.4.1. Expert Review for created Type Extension Registries . 34 108 11.4.2. SMF Message TLV Type (SMF_TYPE) . . . . . . . . . . . 34 109 11.4.3. SMF Address Block TLV Type (SMF_NBR_TYPE) . . . . . . 35 110 11.4.4. SMF Relay Algorithm ID Registry . . . . . . . . . . . 35 111 12. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 36 112 13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 36 113 13.1. Normative References . . . . . . . . . . . . . . . . . . . 36 114 13.2. Informative References . . . . . . . . . . . . . . . . . . 38 115 Appendix A. Essential Connecting Dominating Set (E-CDS) 116 Algorithm . . . . . . . . . . . . . . . . . . . . . . 39 117 A.1. E-CDS Relay Set Selection Overview . . . . . . . . . . . . 39 118 A.2. E-CDS Forwarding Rules . . . . . . . . . . . . . . . . . . 40 119 A.3. E-CDS Neighborhood Discovery Requirements . . . . . . . . 41 120 A.4. E-CDS Selection Algorithm . . . . . . . . . . . . . . . . 43 121 Appendix B. Source-based Multipoint Relay (S-MPR) . . . . . . . . 45 122 B.1. S-MPR Relay Set Selection Overview . . . . . . . . . . . . 45 123 B.2. S-MPR Forwarding Rules . . . . . . . . . . . . . . . . . . 46 124 B.3. S-MPR Neighborhood Discovery Requirements . . . . . . . . 47 125 B.4. S-MPR Selection Algorithm . . . . . . . . . . . . . . . . 49 126 Appendix C. Multipoint Relay Connected Dominating Set 127 (MPR-CDS) Algorithm . . . . . . . . . . . . . . . . . 50 128 C.1. MPR-CDS Relay Set Selection Overview . . . . . . . . . . . 50 129 C.2. MPR-CDS Forwarding Rules . . . . . . . . . . . . . . . . . 51 130 C.3. MPR-CDS Neighborhood Discovery Requirements . . . . . . . 52 131 C.4. MPR-CDS Selection Algorithm . . . . . . . . . . . . . . . 52 132 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 53 134 1. Introduction and Scope 136 Unicast routing protocols, designed for MANET and wireless mesh use, 137 often apply distributed algorithms to flood routing control plane 138 messages within a MANET routing domain. For example, algorithms 139 specified within [RFC3626] and [RFC3684] provide distributed methods 140 of dynamically electing reduced relay sets that attempt to 141 efficiently flood routing control messages while maintaining a 142 connected set under dynamic topological conditions. 144 Simplified Multicast Forwarding (SMF) extends the efficient flooding 145 concept to the data forwarding plane, providing an appropriate 146 multicast forwarding capability for use cases where localized, 147 efficient flooding is considered an effective design approach. The 148 baseline design is intended to provide a basic, best effort multicast 149 forwarding capability that is constrained to operate within a single 150 MANET routing domain. 152 An SMF routing domain is an instance of an SMF routing protocol with 153 common policies, under a single network administration authority. 154 The main design goals of this document are to: 156 o adapt efficient relay sets in MANET environments [RFC2501]; 157 o define the needed IPv4 and IPv6 multicast duplicate packet 158 detection (DPD) mechanisms to support multi-hop, packet 159 forwarding. 161 2. Terminology 163 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 164 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 165 "OPTIONAL" in this document are to be interpreted as described in 166 [RFC2119]. 168 The terms introduced in [RFC5444], including "packet", "message", 169 "TLV Block", "TLV", and "address" are to be interpreted as described 170 therein. 172 The following abbreviations are used throughout this document: 174 +--------------+----------------------------------------------------+ 175 | Abbreviation | Definition | 176 +--------------+----------------------------------------------------+ 177 | MANET | Mobile Ad hoc Network | 178 | SMF | Simplified Multicast Forwarding | 179 | CF | Classic Flooding | 180 | CDS | Connected Dominating Set | 181 | MPR | Multi-Point Relay | 182 | S-MPR | Source-based MPR | 183 | MPR-CDS | MPR-based CDS | 184 | E-CDS | Essential CDS | 185 | NHDP | Neighborhood Discovery Protocol | 186 | DPD | Duplicate Packet Detection | 187 | I-DPD | Identification-based DPD | 188 | H-DPD | Hash-based DPD | 189 | HAV | Hash-assist Value | 190 | FIB | Forwarding Information Base | 191 | TLV | type-length-value encoding | 192 | DoS | Denial of Service | 193 | SMF Router | A MANET Router, implementing the protocol | 194 | | specified in this document | 195 | SMF Routing | A MANET Routing Domain wherein the protocol, | 196 | Domain | specified in this document, is operating | 197 +--------------+----------------------------------------------------+ 199 3. Applicability Statement 201 Within dynamic wireless routing topologies, maintaining traditional 202 forwarding trees to support a multicast routing protocol is often not 203 as effective as in wired networks due to the reduced reliability and 204 increased dynamics of mesh topologies [MGL04] [GM99]. A basic packet 205 forwarding service reaching all connected routers running the SMF 206 protocol within a MANET routing domain may provide a useful group 207 communication paradigm for various classes of applications, for 208 example multimedia streaming, interactive group-based messaging and 209 applications, peer-to-peer middleware multicasting, and multi-hop 210 mobile discovery or registration services. SMF is likely only 211 appropriate for deployment in limited dynamic MANET routing domains 212 so that the flooding process can be contained, further defined as 213 administratively scoped multicast forwarding domains in Section 9.2. 215 A design goal is that hosts may also participate in multicast traffic 216 transmission and reception with standard IP network layer semantics 217 (e.g., special or unnecessary encapsulation of IP packets should be 218 avoided in this case). SMF deployments are able to connect and 219 interoperate with existing standard multicast protocols operating 220 within more conventional Internet infrastructures. To this end, a 221 multicast border router or proxy mechanism MUST be used when deployed 222 alongside more fixed-infrastructure IP multicast routing such 223 Protocol Independent Multicast (PIM) variants [RFC3973] and 224 [RFC4601]. Experimental SMF implementations and deployments have 225 demonstrated gateway functionality at MANET border routers operating 226 with existing external IP multicast routing protocols [CDHM07], 227 [DHS08],and [DHG09]. SMF may be extended or combined with other 228 mechanisms to provide increased reliability and group specific 229 filtering; the details for this are out of scope for this document. 231 This document does not presently support forwarding of packets with 232 directed broadcast addresses as a destination [RFC2644]. 234 4. Overview and Functioning 236 Figure 1 provides an overview of the logical SMF router architecture, 237 consisting of "Neighborhood Discovery", "Relay Set Selection" and 238 "Forwarding Process" components. Typically, relay set selection (or 239 self-election) occurs based on dynamic input from a neighborhood 240 discovery process. SMF supports the case where neighborhood 241 discovery and/or relay set selection information is obtained from a 242 coexistent process (e.g., a lower layer mechanism or a unicast 243 routing protocol using relay sets). In some algorithm designs, the 244 forwarding decision for a packet can also depend on previous hop or 245 incoming interface information. The asterisks (*) in Figure 1 mark 246 the primitives and relationships, needed by relay set algorithms 247 requiring previous-hop packet forwarding knowledge. 248 ______________ _____________ 249 | | | | 250 | Neighborhood | | Relay Set | 251 | Discovery |------------->| Selection | 252 | | neighbor | Algorithm | 253 |______________| info |_____________| 254 \ / 255 \ / 256 neighbor\ /forwarding 257 info* \ ____________ / status 258 \ | | / 259 `-->| Forwarding |<--' 260 | Process | 261 ~~~~~~~~~~~~~~~~~>|____________|~~~~~~~~~~~~~~~~~> 262 incoming packet, forwarded packets 263 interface id*, and 264 previous hop* 266 Figure 1: SMF router Architecture 268 Certain IP multicast packets, defined in Section 9.2 and Section 5, 269 are "non-forwardable". These multicast packets MUST be ignored by 270 the SMF forwarding engine. The SMF forwarding engine MAY also work 271 with policies and management interfaces to allow additional filtering 272 control over which multicast packets are considered for potential SMF 273 forwarding. This interface would allow more refined dynamic 274 forwarding control once such techniques are matured for MANET 275 operation. At present, further discussion of dynamic control is left 276 to future work. 278 Interoperable SMF implementations MUST use compatible DPD approaches 279 and be able to process the header options defined in this document 280 for IPv6 operation. 282 Classic Flooding (CF) is defined as the simplest case of SMF 283 multicast forwarding. With CF, all SMF routers forward each received 284 multicast packet exactly once. In this case, the need for any relay 285 set selection or neighborhood topology information is eliminated, at 286 the expense of additional network overhead incurring from unnecessary 287 packet retransmissions. With CF, the SMF DPD functionality is still 288 required. While SMF supports CF as a mode of operation, the use of 289 more efficient relay set modes is RECOMMENDED in order to reduce 290 contention and congestion caused by unnecessary packet 291 retransmissions [NTSC99]. 293 An efficient, reduced relay set is constructed by selecting and 294 updating, as needed, a subset of all possible routers in a MANET 295 routing domain to act as SMF forwarders. Known distributed relay set 296 selection algorithms have demonstrated the ability to provide and 297 maintain a dynamic connected set for forwarding multicast IP packets 298 [MDC04]. A few such relay set selection algorithms are described in 299 the Appendices of this document and the basic designs borrow directly 300 from previously documented IETF work. SMF relay set configuration is 301 extensible and additional relay set algorithms beyond those specified 302 here can be accommodated in future work. 304 Determining and maintaining an optimized set of relays generally 305 requires dynamic neighborhood topology information. Neighborhood 306 topology discovery functions MAY be provided by a MANET unicast 307 routing protocol or by using the MANET NeighborHood Discovery 308 Protocol (NHDP) [RFC6130], operating concurrently with SMF. This 309 specification also allows alternative lower layer interfaces (e.g., 310 radio router interface) to provide the necessary neighborhood 311 information to aid in supporting more effective relay set election. 312 An SMF implementation SHOULD provide the ability for multicast 313 forwarding state to be dynamically managed per operating network 314 interface. The relay state maintenance options and interactions are 315 outlined in Section 7. This document states specific requirements 316 for neighborhood discovery with respect to the forwarding process and 317 the relay set selection algorithms described herein. For determining 318 dynamic relay sets in the absence of other control protocols, SMF 319 relies on NHDP to assist in IP layer 2-hop neighborhood discovery and 320 maintenance for relay set election. "SMF_TYPE" and "SMF_NBR_TYPE" 321 Message and Address Block TLV structures (per [RFC5444]) are defined 322 by this document for use with NHDP to carry SMF-specific information. 323 It is RECOMMENDED that all routers performing SMF operation in 324 conjunction with NHDP include these TLV types in any NHDP HELLO 325 messages generated. This capability allows for routers participating 326 in SMF to be explicitly identified along with their respective 327 dynamic relay set algorithm configuration. 329 5. SMF Packet Processing and Forwarding 331 The SMF Packet Processing and Forwarding actions are conducted with 332 the following packet handling activities: 334 1. Processing of outbound, locally-generated multicast packets. 335 2. Reception and processing of inbound packets on specific network 336 interfaces. 338 The purpose of intercepting outbound, locally-generated multicast 339 packets is to apply any added packet marking needed to satisfy the 340 DPD requirements so that proper forwarding may be conducted. Note 341 that for some system configurations the interception of outbound 342 packets for this purpose is not necessary. 344 Inbound multicast packets are received by the SMF implementation and 345 processed for possible forwarding. SMF implementations MUST be 346 capable of forwarding IP multicast packets with destination addresses 347 that are not router-local and link-local for IPv6, as defined in 348 [RFC4291], and that are not within the local network control block as 349 defined by [RFC5771]. 351 This will support generic multi-hop multicast application needs or 352 distribute designated multicast traffic ingressing the SMF routing 353 domain via border routers. The multicast addresses to be forwarded 354 should be maintained by an a priori list or a dynamic forwarding 355 information base (FIB) that MAY interact with future MANET dynamic 356 group membership extensions or management functions. 358 The SL-MANET-ROUTERS multicast group is defined to contain all 359 routers within an SMF routing domain, so that packets transmitted to 360 the multicast address associated with the group will be attempted 361 delivered to all connected routers running SMF. Due to the mobile 362 nature of a MANET, routers running SMF may not be topologically 363 connected at particular times. For IPv6, SL-MANET-ROUTERS is 364 specified to be "site-local". Minimally, SMF MUST forward, as 365 instructed by the relay set selection algorithm, unique (non- 366 duplicate) packets received for SL-MANET-ROUTERS when the TTL/ 367 hop-limit or hop limit value in the IP header is greater than 1. SMF 368 MUST forward all additional global scope multicast addresses 369 specified within the dynamic FIB or configured list as well. In all 370 cases, the following rules MUST be observed for SMF multicast 371 forwarding: 373 1. Any IP packets not addressed to an IP multicast address MUST NOT 374 be forwarded by the SMF forwarding engine 375 2. IP multicast packets with TTL/hop-limit <= 1 MUST NOT be 376 forwarded. 377 3. Link local IP multicast packets MUST NOT be forwarded. 378 4. Incoming IP multicast packets with an IP source address matching 379 one of those of the local SMF router interface(s) MUST NOT be 380 forwarded. 381 5. Received frames with the MAC source address matching any MAC 382 address of the router's interfaces MUST NOT be forwarded. 383 6. Received packets for which SMF cannot reasonably ensure temporal 384 DPD uniqueness MUST NOT be forwarded. 385 7. Prior to being forwarded, the TTL/hop-limit of the forwarded 386 packet MUST be decremented by one. 388 Note that rule #4 is important because over some types of wireless 389 interfaces, the originating SMF router may receive re-transmissions 390 of its own packets when they are forwarded by adjacent routers. This 391 rule avoids unnecessary retransmission of locally-generated packets 392 even when other forwarding decision rules would apply. 394 An additional processing rule also needs to be considered based upon 395 a potential security threat. As discussed in Section 10, there is a 396 potential DoS attack that can be conducted by remotely "previewing" 397 (e.g., via a directional receive antenna) packets that an SMF router 398 would be forwarding and conduct a "pre-play" attack by transmitting 399 the packet before the SMF router would otherwise receive it but with 400 a reduced TTL/hop-limit field value. This form of attack can cause 401 an SMF router to create a DPD entry that would block the proper 402 forwarding of the valid packet (with correct TTL/hop-limit) through 403 the SMF routing domain. A RECOMMENDED approach to prevent this 404 attack, when it is a concern, would be to cache temporal packet TTL/ 405 hop-limit values along with the per-packet DPD state (hash value(s) 406 and/or identifier as described in Section 6). Then, if a subsequent 407 matching (with respect to DPD) packet arrives with a larger TTL/ 408 hop-limit value than the packet that was previously forwarded, SMF 409 should forward the new packet and update the TTL/hop-limit value 410 cached with corresponding DPD state to the new, larger TTL/hop-limit 411 value. There may be temporal cases where SMF would unnecessarily 412 forward some duplicate packets using this approach, but those cases 413 are expected to be minimal and acceptable when compared with the 414 potential threat of denied service. 416 Once the SMF multicast forwarding rules have been applied, an SMF 417 implementation MUST make a forwarding decision dependent upon the 418 relay set selection algorithm in use. If the SMF implementation is 419 using Classic Flooding (CF), the forwarding decision is implicit once 420 DPD uniqueness is determined. Otherwise, a forwarding decision 421 depends upon the current interface-specific relay set state. The 422 descriptions of the relay set selection algorithms in the Appendices 423 to this document specify the respective heuristics for multicast 424 packet forwarding and specific DPD or other processing required to 425 achieve correct SMF behavior in each case. For example, one class of 426 forwarding is based upon relay set election status and the packet's 427 previous hop, while other classes designate the local SMF router as a 428 forwarder for all neighboring routers. 430 6. SMF Duplicate Packet Detection 432 Duplicate packet detection (DPD) is often a requirement in MANET or 433 wireless mesh packet forwarding mechanisms because packets may be 434 transmitted out via the same physical interface as the one over which 435 they were received. Routers may also receive multiple copies of the 436 same packets from different neighbors or interfaces. SMF operation 437 requires DPD and implementations MUST provide mechanisms to detect 438 and reduce the likelihood of forwarding duplicate multicast packets 439 using temporal packet identification. It is RECOMMENDED this be 440 implemented by keeping a history of recently-processed multicast 441 packets for comparison with incoming packets. A DPD packet cache 442 history SHOULD be kept long enough so as to span the maximum network 443 traversal lifetime, MAX_PACKET_LIFETIME, of multicast packets being 444 forwarded within an SMF routing domain. The DPD mechanism SHOULD 445 avoid keeping unnecessary state for packet flows such as those that 446 are locally-generated or link-local destinations that would not be 447 considered for forwarding, as presented in Section 5. 449 For IPv4 and IPv6, both, this document describes two basic multicast 450 duplicate packet detection mechanisms: header content identification- 451 based (I-DPD) and hash-based (H-DPD) duplicate detection. I-DPD is a 452 mechanism using specific packet headers, and option headers in the 453 case of IPv6, in combination with flow state to estimate the temporal 454 uniqueness of a packet. H-DPD uses hashing over header fields and 455 payload of a multicast packet, in order to provide an estimation of 456 temporal uniqueness. 458 Trade-offs of the two approaches to DPD merit different 459 considerations dependent upon the specific SMF deployment scenario. 461 Because of the potential addition of a hop-by-hop option header with 462 IPv6, all SMF routers in the same SMF deployments MUST be configured 463 so as to use a common mechanism and DPD algorithm. The main 464 difference between IPv4 and IPv6 SMF DPD specification is the 465 avoidance of any additional header options for IPv4. 467 For each network interface, SMF implementations MUST maintain DPD 468 packet state as needed to support the forwarding heuristics of the 469 relay set algorithm used. In general, this involves keeping track of 470 previously forwarded packets so that duplicates are not forwarded, 471 but some relay techniques have additional considerations, such as 472 discussed in Appendix B.2. 474 Additional details of I-DPD and H-DPD processing and maintenance for 475 different classes of packets are described in the following. 477 6.1. IPv6 Duplicate Packet Detection 479 This section describes the mechanisms and options for SMF IPv6 DPD. 480 The base IPv6 packet header does not provide any explicit packet 481 identification header field that can be exploited for I-DPD. The 482 following options are therefore described, to support IPv6 DPD: 483 1. a hop-by-hop SMF_DPD option header, defined in this document 484 (Section 6.1.1), 485 2. the use of IPv6 fragment header fields for I-DPD, if one is 486 present (Section 6.1.2), 487 3. the use of IPsec sequencing for I-DPD when a non-fragmented, 488 IPsec header is detected (Section 6.1.2), and 489 4. an H-DPD approach assisted, as needed, by the SMF_DPD option 490 header (Section 6.1.3). 492 SMF MUST provide a DPD marking module that can insert the hop-by-hop 493 IPv6 header option, defined Section 6.1.1. This module MUST be 494 invoked after any source-based fragmentation that may occur with 495 IPv6, so as to ensure that all fragments are suitably marked. SMF 496 IPv6 DPD is presently specified to allow either a packet hash or 497 header identification method for DPD. An SMF implementation MUST be 498 configured to operate either in H-DPD or I-DPD mode, and perform the 499 corresponding tasks, outlined in Section 6.1.1 and Section 6.1.3. 501 6.1.1. IPv6 SMF_DPD Header Option 503 This section defines an IPv6 Hop-by-Hop Option [RFC2460], SMF_DPD, to 504 serve the purpose of unique packet identification for IPv6 I-DPD. 505 Additionally, the SMF_DPD header option provides a mechanism to 506 guarantee non-collision of hash values for different packets when 507 H-DPD is used. 509 If this is the only hop-by-hop option present, the optional 510 "TaggerId" field (see below) is not included, and the size of the DPD 511 packet identifier (sequence number) or hash token is 24 bits or less, 512 this will result in the addition of 8 bytes to the IPv6 packet header 513 including the "Next Header", "Header Extension Length", SMF_DPD 514 option fields, and padding. 516 0 1 2 3 517 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 518 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 519 ... |0|0|0| SMF_DPD | Opt. Data Len | 520 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 521 |H| DPD Identifier Option Fields or Hash Assist Value ... 522 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 524 IPv6 SMF_DPD Hop-by-Hop Header Option 526 "Option Type" = (Lower 5 bits pending IANA assignment, highest order 527 MUST be 000). By having these three bits be zero, this specification 528 requires that routers not recognizing this option type should skip 529 over this option and continue processing the header and that the 530 option must not change en route [RFC2460]. 532 "Opt. Data Len" = Length of option content (I.e., 1 + ( ? 533 ( + 1): 0) + Length(DPD ID)). 535 "H-bit" = a hash indicator bit value identifying DPD marking type. 0 536 == sequence-based approach with optional TaggerId and a tuple-based 537 sequence number. 1 == indicates a hash assist value (HAV) field 538 follows to aid in avoiding hash-based DPD collisions. 540 When the "H-bit" is cleared (zero value), the SMF_DPD format to 541 support I-DPD operation is specified as shown in Figure 2 and defines 542 the extension header in accordance with [RFC2460]. 544 0 1 2 3 545 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 546 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 547 ... |0|0|0| OptType | Opt. Data Len | 548 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 549 |0|TidTy| TidLen| TaggerId (optional) ... | 550 +-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 551 | | Identifier ... 552 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 554 Figure 2: IPv6 SMF_DPD Header Option in I-DPD mode 556 "TidTy" = a 3-bit field indicating the presence and type of the 557 optional "TaggerId" field. "TidLen" = a 4-bit field indicating the 558 length (in octets) of the following TaggerId field. "TaggerId" = a 559 field, is used to differentiate multiple ingressing border gateways 560 that may commonly apply the SMF_DPD option header to packets from a 561 particular source. Table 1 lists the TaggerId types, used in this 562 document: 564 +---------+---------------------------------------------------------+ 565 | Name | Purpose | 566 +---------+---------------------------------------------------------+ 567 | NULL | Indicates no "TaggerId" field is present. "TidLen" | 568 | | MUST also be set to ZERO. | 569 | DEFAULT | A "TaggerId" of non-specific context is present. | 570 | | "TidLen + 1" defines the length of the TaggerId field | 571 | | in bytes. | 572 | IPv4 | A "TaggerId" representing an IPv4 address is present. | 573 | | The "TidLen" MUST be set to 3. | 574 | IPv6 | A "TaggerId" representing an IPv6 address is present. | 575 | | The "TidLen" MUST be set to 15. | 576 +---------+---------------------------------------------------------+ 578 Table 1: TaggerId Types 580 This format allows a quick check of the "TidTy" field to determine if 581 a "TaggerId" field is present. If "TidTy" is NULL, then the length 582 of the DPD packet field corresponds to ( 583 - 1). If the is non-NULL, then the length of the "TaggerId" 584 field is equal to ( - 1) and the remainder of the option data 585 comprises the DPD packet field. When the "TaggerId" 586 field is present, the field can be considered a unique 587 packet identifier in the context of the 588 tuple. When the "TaggerId" field is not present, then it is assumed 589 the source applied the SMF_DPD option and the can be 590 considered unique in the context of the IPv6 packet header tuple. IPv6 I-DPD operation details are described in 592 Section 6.1.2. 594 When the "H-bit" in the SMF_DPD option data is set, the data content 595 value is interpreted as a Hash-Assist Value (HAV) used to facilitate 596 H-DPD operation. In this case, the source or ingressing gateways 597 apply the SMF_DPD with an HAV only when required to differentiate the 598 hash value of a new packet with respect to hash values in the DPD 599 cache. This situation can be detected locally on the router by 600 running the hash algorithm and checking the DPD cache, prior to 601 ingressing a previously unmarked packet or a locally sourced packet. 602 This helps to guarantee the uniqueness of generated hash values when 603 H-DPD is used. Additionally, this also avoids the added overhead of 604 applying the SMF_DPD option header to every packet. For many hash 605 algorithms, it is expected that only sparse use of the SMF_DPD option 606 may be required. The format of the SMF_DPD header option for H-DPD 607 operation is given in Figure 3. 609 0 1 2 3 610 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 611 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 612 ... |0|0|0| OptType | Opt. Data Len | 613 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 614 |1| Hash Assist Value (HAV) ... 615 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 617 Figure 3: IPv6 SMF_DPD Header Option in H-DPD Mode 619 The SMF_DPD option should be applied with an HAV to produce a unique 620 hash digest for packets within the context of the IPv6 packet header 621 . The size of the HAV field is implied by the "Opt. Data 622 Len". The appropriate size of the field depends upon the collision 623 properties of the specific hash algorithm used. More details on IPv6 624 H-DPD operation are provided in Section 6.1.3. 626 6.1.2. IPv6 Identification-based DPD 628 Table 2 summarizes the IPv6 I-DPD processing and forwarding decision 629 approach. Within the table '*' indicates an ignore field condition. 631 +-------------+-----------+-----------+-----------------------------+ 632 | IPv6 | IPv6 | IPv6 | SMF IPv6 I-DPD Mode Action | 633 | Fragment | IPsec | I-DPD | | 634 | Header | Header | Header | | 635 +-------------+-----------+-----------+-----------------------------+ 636 | Present | * | Not | Use Fragment Header I-DPD | 637 | | | Present | Check and Process for | 638 | | | | Forwarding | 639 | Not Present | Present | Not | Use IPsec Header I-DPD | 640 | | | Present | Check and Process for | 641 | | | | Forwarding | 642 | Present | * | Present | Invalid, do not Forward | 643 | Not Present | Present | Present | Invalid, do not Forward | 644 | Not Present | Not | Not | Add I-DPD Header,and | 645 | | Present | Present | Process for Forwarding | 646 | Not Present | Not | Present | Use I-DPD Header Check and | 647 | | Present | | Process for Forwarding | 648 +-------------+-----------+-----------+-----------------------------+ 650 Table 2: IPv6 I-DPD Processing Rules 652 1. If a received IPv6 multicast packet is an IPv6 fragment, SMF MUST 653 use the fragment extension header fields for packet 654 identification. This identifier can be considered unique in the 655 context of the of the IP packet. 656 2. If the packet is an unfragmented IPv6 IPsec packet, SMF MUST use 657 IPsec fields for packet identification. The IPsec header 658 field can be considered a unique identifier in the 659 context of the where the 660 "IPsecType" is either AH or ESP [RFC4302]. 661 3. For unfragmented, non-IPsec, IPv6 packets, the use of the SMF_DPD 662 header option is necessary to support I-DPD operation. The 663 SMF_DPD header option is applied in the context of the 664 of the IP packet. hosts or ingressing SMF gateways are 665 responsible for applying this option to support DPD. Table 3 666 summarizes these packet identification types: 668 +-----------+---------------------------------+---------------------+ 669 | IPv6 | Packet DPD ID Context | Packet DPD ID | 670 | Packet | | | 671 | Type | | | 672 +-----------+---------------------------------+---------------------+ 673 | Fragment | | | 674 | IPsec | | | 675 | Packet | | | 676 | Regular | <[TaggerId:]srcAddr:dstAddr> | | 678 +-----------+---------------------------------+---------------------+ 679 Table 3: IPv6 I-DPD Packet Identification Types 681 "IPsecType" is either Authentication Header (AH) or Encapsulating 682 Security Payload (ESP). 684 The "TaggerId" is an optional field of the IPv6 SMF_DPD header 685 option. 687 6.1.3. IPv6 Hash-based DPD 689 A default hash-based DPD approach (H-DPD) for use by SMF is specified 690 as follows. An SHA-1 [RFC3174] hash of the non-mutable header 691 fields, options fields, and data content of the IPv6 multicast packet 692 is used to produce a 160-bit digest. The approach for calculating 693 this hash value SHOULD follow the same guidelines described for 694 calculating the Integrity Check Value (ICV) described in [RFC4302] 695 with respect to non-mutable fields. This approach should have a 696 reasonably low probability of digest collision when packet headers 697 and content are varying. SHA-1 is being applied in SMF only to 698 provide a low probability of collision and is not being used for 699 cryptographic or authentication purposes. A history of the packet 700 hash values SHOULD be maintained within the context of the IPv6 701 packet header . SMF ingress points (i.e., source hosts or 702 gateways) use this history to confirm that new packets are unique 703 with respect to their hash value. The Hash-assist Value (HAV) field 704 described in Section 6.1.1 is provided as a differentiating field 705 when a digest collision would otherwise occur. Note that the HAV is 706 an immutable option field and SMF MUST process any included HAV 707 values (see Section 6.1.1) in its hash calculation. 709 If a packet results in a digest collision (i.e., by checking the 710 H-DPD digest history) within the DPD cache kept by SMF forwarders, 711 the packet SHOULD be silently dropped. If a digest collision is 712 detected at an SMF ingress point the H-DPD option header is 713 constructed with a randomly generated HAV. A HAV is recalculated as 714 needed to produce a non-colliding hash value prior to forwarding. 715 The multicast packet is then forwarded with the added IPv6 SMF_DPD 716 header option. A common hash approach MUST be used by SMF routers 717 for the applied HAV to consistently avoid hash collision and thus 718 inadvertent packet drops. 720 The SHA-1 indexing and IPv6 HAV approaches are specified at present 721 for consistency and robustness to suit experimental uses. Future 722 approaches and experimentation may discover design tradeoffs in hash 723 robustness and efficiency worth considering. Enhancements MAY 724 include reducing the maximum payload length that is processed, 725 determining shorter indexes, or applying more efficient hashing 726 algorithms. Use of the HAV functionality may allow for application 727 of "lighter-weight" hashing techniques that might not have been 728 initially considered due to poor collision properties otherwise. 729 Such techniques could reduce packet processing overhead and memory 730 requirements. 732 6.2. IPv4 Duplicate Packet Detection 734 This section describes the mechanisms and options for IPv4 DPD. The 735 following areas are described to support IPv4 DPD: 737 1. the use of IPv4 fragment header fields for I-DPD when they exist 738 (Section 6.2.1), 739 2. the use of IPsec sequencing for I-DPD when a non-fragmented IPv4 740 IPsec packet is detected (Section 6.2.1), and 741 3. an H-DPD approach(Section 6.2.2) when neither of the above cases 742 can be applied. 744 Although the IPv4 datagram has a 16-bit Identification (ID) field as 745 specified in [RFC0791], it cannot be relied upon for DPD purposes due 746 to common computer operating system implementation practices and the 747 reasons described in the updated specification of the IPv4 ID Field 748 [I-D.ietf-intarea-ipv4-id-update]. An SMF IPv4 DPD marking option 749 like the IPv6 SMF_DPD option header is not specified since IPv4 750 header options are not as tractable for hosts as they are for IPv6. 751 However, when IPsec is applied or IPv4 packets have been fragmented, 752 the I-DPD approach can be applied reliably using the corresponding 753 packet identifier fields described in Section 6.2.1 below. For the 754 general IPv4 case (non-IPsec and non-fragmented packets), the H-DPD 755 approach of Section 6.2.2 is RECOMMENDED. 757 Since IPv4 SMF does not specify an option header, the 758 interoperability constraints are looser than the IPv6 version and 759 forwarders may be operate with mixed H-DPD and I-DPD modes as long as 760 they consistently perform the appropriate DPD routines outlined in 761 the following sections. However, it is RECOMMENDED that a deployment 762 be configured with a common mode for operational consistency. 764 6.2.1. IPv4 Identification-based DPD 766 Table 4 summarizes the IPv4 I-DPD processing approach once a packet 767 has passed the basic forwardable criteria described in Section 5. To 768 summarize, for IPv4, I-DPD is applicable only for packets which have 769 been fragmented or have IPsec applied. Within the table '*' 770 indicates an ignore field condition. DF, MF, Fragment offset 771 correspond to related fields and flags defined in [RFC0791]. 773 +------+------+----------+---------+--------------------------------+ 774 | DF | MF | Fragment | IPsec | IPv4 I-DPD Action | 775 | flag | flag | offset | | | 776 +------+------+----------+---------+--------------------------------+ 777 | 1 | 1 | * | * | Invalid, Do Not Forward | 778 | 1 | 0 | nonzero | * | Invalid, Do Not Forward | 779 | * | 0 | zero | not | Use H-DPD check instead | 780 | | | | Present | | 781 | * | 0 | zero | Present | IPsec enhanced Tuple I-DPD | 782 | | | | | Check and Process for | 783 | | | | | Forwarding | 784 | 0 | 0 | nonzero | * | Extended Fragment Offset Tuple | 785 | | | | | I-DPD Check and Process for | 786 | | | | | Forwarding | 787 | 0 | 1 | zero or | * | Extended Fragment Offset Tuple | 788 | | | nonzero | | I-DPD Check and Process for | 789 | | | | | Forwarding | 790 +------+------+----------+---------+--------------------------------+ 792 Table 4: IPv4 I-DPD Processing Rules 794 For performance reasons, IPv4 network fragmentation and reassembly of 795 multicast packets within wireless MANET networks should be minimized, 796 yet SMF provides the forwarding of fragments when they occur. If the 797 IPv4 multicast packet is a fragment, SMF MUST use the fragmentation 798 header fields for packet identification. This identification can be 799 considered temporally unique in the context of the of the IPv4 packet. If the packet is an unfragmented IPv4 801 IPsec packet, SMF MUST use IPsec fields for packet identification. 802 The IPsec header field can be considered a unique 803 identifier in the context of the 804 where the "IPsecType" is either AH or ESP [RFC4302]. Table 5 805 summarizes these packet identification types: 807 +-----------+---------------------------------+---------------------+ 808 | IPv4 | Packet Identification Context | Packet Identifier | 809 | Packet | | | 810 | Type | | | 811 +-----------+---------------------------------+---------------------+ 812 | Fragment | | | 813 | IPsec | | | 814 | Packet | | | 815 +-----------+---------------------------------+---------------------+ 817 Table 5: IPv4 I-DPD Packet Identification Types 819 "IPsecType" is either Authentication Header (AH) or Encapsulating 820 Security Payload (ESP). 822 6.2.2. IPv4 Hash-based DPD 824 The hashing technique here is similar to that specified for IPv6 in 825 Section 6.1.3, but the H-DPD header option with HAV is not 826 considered. To ensure consistent IPv4 H-DPD operation among SMF 827 routers, a default hashing approach is specified. A common DPD 828 hashing algorithm for an SMF routing area is RECOMMENDED because 829 colliding hash values for different packets result in a "false 830 positive" duplicate packet detection and valid packets may be dropped 831 with a small probability based on the hashing technique used. Since 832 the "hash assist value" approach is not available for IPv4, use of a 833 common hashing approach minimizes the hash collision packet drop 834 probability over multiple hops of forwarding. 836 SMF MUST perform an SHA-1 [RFC3174] hash of the immutable header 837 fields, option fields and data content of the IPv4 multicast packet 838 resulting in a 160-bit digest. The approach for calculating the hash 839 value SHOULD follow the same guidelines described for calculating the 840 Integrity Check Value (ICV) described in [RFC4302] with respect to 841 non-mutable fields. A history of the packet hash values SHOULD be 842 maintained in the context of . The context 843 for IPv4 is more specific than that of IPv6 since the SMF_DPD HAV 844 cannot be employed to mitigate hash collisions. A RECOMMENDED 845 implementation detail for IPv4 H-DPD is to concatenate the 16-bit 846 IPv4 ID value with the computed hash value as an extended DPD hash 847 value that may provide reduced hash collisions in the cases where the 848 IPv4 ID field is being set by host operating systems or gateways. 849 When this approach is taken, the use of the supplemental "internal 850 hash" technique as described in Section 10 is RECOMMENDED as a 851 security measure. 853 The SHA-1 hash is specified at present for consistency and 854 robustness. Future approaches and experimentation may discover 855 design tradeoffs in hash robustness and efficiency worth considering 856 for future revisions of SMF. This MAY include reducing the packet 857 payload length that is processed, determining shorter indexes, or 858 applying a more efficient hashing algorithm. 860 7. Relay Set Selection 862 SMF is flexible in its support of different reduced relay set 863 mechanism for efficient flooding, the constraints imposed hereon 864 being detailed in this section. 866 7.1. Non-Reduced Relay Set Forwarding 868 SMF implementations MUST support CF as a basic forwarding mechanism 869 when reduced relay set information is not available or not selected 870 for operation. In CF mode, each router transmits a packet once that 871 has passed the SMF forwarding rules. The DPD techniques described in 872 Section 6 are critical to proper operation and prevent duplicate 873 packet retransmissions by the same relays. 875 7.2. Reduced Relay Set Forwarding 877 MANET reduced relay sets are often achieved by distributed algorithms 878 that can dynamically calculate a topological connected dominating set 879 (CDS). 881 A goal of SMF is to apply reduced relay sets for more efficient 882 multicast dissemination within dynamic topologies. To accomplish 883 this an SMF implementation MUST support the ability to modify its 884 multicast packet forwarding rules based upon relay set state received 885 dynamically during operation. In this way, SMF operates effectively 886 as neighbor adjacencies or multicast forwarding policies within the 887 topology change. 889 In early SMF experimental prototyping, the relay set information has 890 been derived from coexistent unicast routing control plane traffic 891 flooding processes [MDC04]. From this experience, extra pruning 892 considerations were sometimes required when utilizing a relay set 893 from a separate routing protocol process. As an example, relay sets 894 formed for the unicast control plane flooding MAY include additional 895 redundancy that may not be desired for multicast forwarding use 896 (e.g., biconnected relay set). 898 Here is a recommended criteria list for SMF relay set selection 899 algorithm candidates: 901 1. Robustness to topological dynamics and mobility 902 2. Localized election or coordination of any relay sets 903 3. Reasonable minimization of CDS relay set size given above 904 constraints 905 4. Heuristic support for preference or election metrics 907 Some relay set algorithms meeting these criteria are described in the 908 Appendices of this document. Additional relay set selection 909 algorithms may be specified in separate specifications in the future. 910 Each Appendix subsection in this document can serve as a template for 911 specifying additional relay algorithms. 913 Figure 4 depicts an information flow diagram of possible relay set 914 control options. The SMF Relay Set State represents the information 915 base that is used by SMF in the forwarding decision process. The 916 relay set control option diagram demonstrates that the SMF relay set 917 state may be determined by fundamentally three different methods: 919 o Independent operation with NHDP [RFC6130] input providing dynamic 920 network neighborhood adjacency information, used by a particular 921 relay set selection algorithm. 922 o Slave operation with an existing unicast MANET routing protocol, 923 capable of providing CDS election information for use by SMF. 924 o Cross layer operation that may involve L2 triggers / Information 925 describing neighbors or links. 927 Other heuristics to influence and control election can come from 928 network management or other interfaces as shown on the right of 929 Figure 4. CF mode simplifies the control and does not require other 930 input but relies solely on DPD. 932 Possible L2 Trigger/Information 933 | 934 | 935 ______________ ______v_____ __________________ 936 | MANET | | | | | 937 | Neighborhood | | Relay Set | | Other Heuristics | 938 | Discovery |----------->| Selection |<------| (Preference,etc) | 939 | Protocol | neighbor | Algorithm | | Net Management | 940 |______________| info |____________| |__________________| 941 \ / 942 \ / 943 neighbor\ / Dynamic Relay 944 info* \ ____________ / Set Status 945 \ | SMF | / (State, {neighbor info}) 946 `-->| Relay Set |<--' 947 | State | 948 -->|____________| 949 / 950 / 951 ______________ 952 | Coexistent | 953 | MANET | 954 | Unicast | 955 | Process | 956 |______________| 958 Figure 4: SMF Reduced Relay Set Information Flow 960 More discussion is provided on the three styles of SMF operation with 961 reduced relay sets as illustrated in Figure 4: 963 1. Independent operation: In this case, SMF operates independently 964 from any unicast routing protocols. To support reduced relay 965 sets SMF MUST perform its own relay set selection using 966 information gathered from signaling. It is RECOMMENDED that an 967 associated NHDP process be used for this signaling. NHDP 968 messaging SHOULD be appended with additional [RFC5444] type- 969 length-value (TLV) content to support SMF-specific requirements 970 as discussed in [RFC6130] and for the applicable relay set 971 algorithm described in the Appendices of this document or future 972 specifications. Unicast routing protocols may co-exist, even 973 using the same NHDP process, but signaling that supports reduced 974 relay set selection for SMF is independent of these protocols. 975 2. Operation with CDS-aware unicast routing protocol: In this case, 976 a coexistent unicast routing protocol provides dynamic relay set 977 state based upon its own control plane CDS or neighborhood 978 discovery information. 979 3. Cross-layer Operation: In this case, SMF operates using 980 neighborhood status and triggers from a cross-layer information 981 base for dynamic relay set selection and maintenance (e.g., lower 982 link layer). 984 8. SMF Neighborhood Discovery Requirements 986 This section defines the requirements for use of the MANET 987 Neighborhood Discovery Protocol (NHDP) [RFC6130] to support SMF 988 operation. Note that basic CF forwarding requires no neighborhood 989 topology knowledge since in this configured mode every SMF router 990 relays all traffic. Supporting more reduced SMF relay set operation 991 requires the discovery and maintenance of dynamic neighborhood 992 topology information. NHDP can be used to provide this necessary 993 information, however there are SMF-specific requirements for NHDP 994 use. This is the case for both "independent" SMF operation where 995 NHDP is being used specifically to support SMF or when one NHDP 996 instance is used, both, for SMF and a coexistent MANET unicast 997 routing protocol. 999 NHDP HELLO messages and the resultant neighborhood information base 1000 are described separately within the NHDP specification. To 1001 summarize, NHDP provides the following basic functions: 1003 1. 1-hop neighbor link sensing and bidirectionality checks of 1004 neighbor links, 1005 2. 2-hop neighborhood discovery including collection of 2-hop 1006 neighbors and connectivity information, 1007 3. Collection and maintenance of the above information across 1008 multiple interfaces, and 1010 4. A method for signaling SMF information throughout the 2-hop 1011 neighborhood through the use of TLV extensions. 1013 Appendices (A-C) of this document describe CDS-based relay set 1014 selection algorithms that can achieve efficient SMF operation, even 1015 in dynamic, mobile networks and each of the algorithms has been 1016 initially experimented within a working SMF prototype [MDDA07]. When 1017 using these algorithms in conjunction with NHDP, a method verifying 1018 neighbor SMF operation is required in order to insure correct relay 1019 set selection. NHDP along with SMF operation verification provides 1020 the necessary information required by these algorithms to conduct 1021 relay set selection. Verification of SMF operation may be done 1022 administratively or through the use of the SMF relay algorithms TLVs 1023 defined in the following subsections. Use of the SMF relay algorithm 1024 TLVs is RECOMMENDED when using NHDP for SMF neighborhood discovery. 1026 Section 8.1 specifies SMF-specific TLV types, supporting general SMF 1027 operation or supporting the algorithms described in the Appendices. 1028 The Appendices describing several relay set algorithms also specify 1029 any additional requirements for use with NHDP and reference the 1030 applicable TLV types as needed. 1032 8.1. SMF Relay Algorithm TLV Types 1034 This section specifies TLV types to be used within NHDP messages to 1035 identify the CDS relay set selection algorithm(s) in use. Two TLV 1036 types are defined, one Message TLV type and one Address Block TLV 1037 type. 1039 8.1.1. SMF Message TLV Type 1041 The Message TLV type denoted SMF_TYPE is used to identify the 1042 existence of an SMF instance operating in conjunction with NHDP. 1043 This Message TLV type makes use of the extended type field as defined 1044 by [RFC5444] to convey the CDS relay set selection algorithm 1045 currently in use by the SMF message originator. When NHDP is used to 1046 support SMF operation, the SMF_TYPE TLV, containing the extended type 1047 field with the appropriate value, SHOULD be included in NHDP_HELLO 1048 messages (HELLO messages as defined in [RFC6130]). This allows SMF 1049 routers to learn when neighbors are configured to use NHDP for 1050 information exchange including algorithm type and related algorithm 1051 information. This information can be used to take action, such as 1052 ignoring neighbor information using incompatible algorithms. It is 1053 possible that SMF neighbors MAY be configured differently and still 1054 operate cooperatively, but these cases will vary dependent upon the 1055 algorithm types designated. 1057 This document defines a Message TLV type as specified in Table 6 1058 conforming to [RFC5444]. The TLV extended type field is used to 1059 contain the sender's "Relay Algorithm Type". The interpretation of 1060 the "value" content of these TLVs is defined per "Relay Algorithm 1061 Type" and may contain algorithm specific information. 1063 +---------------+----------------+--------------------+ 1064 | | TLV Syntax | Field Values | 1065 +---------------+----------------+--------------------+ 1066 | type | | SMF_TYPE | 1067 | extended type | | | 1068 | length | | variable | 1069 | value | | variable | 1070 +---------------+----------------+--------------------+ 1072 Table 6: SMF Type Message TLV 1074 In Table 6 is an 8-bit field containing a number 1075 0-255 representing the "Relay Algorithm Type" of the originator 1076 address of the corresponding NHDP message. 1078 Values for the are defined in Table 7. The table 1079 provides value assignments, future IANA assignment spaces, and an 1080 experimental space. The experimental space use MUST NOT assume 1081 uniqueness and thus SHOULD NOT be used for general interoperable 1082 deployment prior to official IANA assignment. 1084 +-------------+--------------------+--------------------------------+ 1085 | Type Value | Extended Type | Algorithm | 1086 | | Value | | 1087 +-------------+--------------------+--------------------------------+ 1088 | SMF_TYPE | 0 | CF | 1089 | SMF_TYPE | 1 | S-MPR | 1090 | SMF_TYPE | 2 | E-CDS | 1091 | SMF_TYPE | 3 | MPR-CDS | 1092 | SMF_TYPE | 4-127 | Future Assignment STD action | 1093 | SMF_TYPE | 128-239 | No STD action required | 1094 | SMF_TYPE | 240-255 | Experimental Space | 1095 +-------------+--------------------+--------------------------------+ 1097 Table 7: SMF Relay Algorithm Type Values 1099 Acceptable and fields of an SMF_TYPE TLV are 1100 dependent on the extended type value (i.e. relay algorithm type). 1101 The appropriate algorithm type, as conveyed in the 1102 field, defines the meaning and format of its TLV field. For 1103 the algorithms defined by this document, see the appropriate appendix 1104 for the field format. 1106 8.1.2. SMF Address Block TLV Type 1108 An address block TLV type, denoted SMF_NBR_TYPE (i.e., SMF neighbor 1109 relay algorithm) is specified in Table 8. This TLV enables CDS relay 1110 algorithm operation and configuration to be shared among 2-hop 1111 neighborhoods. Some relay algorithms require two hop neighbor 1112 configuration in order to correctly select relay sets. It is also 1113 useful when mixed relay algorithm operation is possible, some 1114 examples of mixed use are outlined in the Appendices. 1116 The message SMF_TYPE TLV and address block SMF_NBR_TYPE TLV types 1117 share a common format. 1119 +---------------+----------------+--------------------+ 1120 | | TLV syntax | Field Values | 1121 +---------------+----------------+--------------------+ 1122 | type | | SMF_NBR_TYPE | 1123 | extended type | | | 1124 | length | | variable | 1125 | value | | variable | 1126 +---------------+----------------+--------------------+ 1128 Table 8: SMF Type Address Block TLV 1130 in Table 8 is an 8-bit unsigned integer field 1131 containing a number 0-255 representing the "Relay Algorithm Type" 1132 value that corresponds to any associated address in the address 1133 block. Note that "Relay Algorithm Type" values for 2-hop neighbors 1134 can be conveyed in a single TLV or multiple value TLVs as described 1135 in [RFC5444]. It is expected that SMF routers using NHDP construct 1136 address blocks with SMF_NBR_TYPE TLVs to advertise "Relay Algorithm 1137 Type" and to advertise neighbor algorithm values received in SMF_TYPE 1138 TLVs from those neighbors. 1140 Again values for the are defined in Table 7. 1142 The interpretation of the "value" field of SMF_NBR_TYPE TLVs is 1143 defined per "Relay Algorithm Type" and may contain algorithm specific 1144 information. See the appropriate appendix for definitions of value 1145 fields for the algorithms defined by this document. 1147 9. SMF Border Gateway Considerations 1149 It is expected that SMF will be used to provide simple forwarding of 1150 multicast traffic within a MANET or mesh routing topology. A border 1151 router gateway approach should be used to allow interconnection of 1152 SMF routing domains with networks using other multicast routing 1153 protocols, such as PIM. It is important to note that there are many 1154 scenario-specific issues that should be addressed when discussing 1155 border multicast routers. At the present time, experimental 1156 deployments of SMF and PIM border router approaches have been 1157 demonstrated [DHS08]. Some of the functionality border routers may 1158 need to address includes the following: 1160 1. Determining which multicast group traffic transits the border 1161 router whether entering or exiting the attached SMF routing 1162 domain. 1163 2. Enforcement of TTL/hop-limit threshold or other scoping policies. 1164 3. Any marking or labeling to enable DPD on ingressing packets. 1165 4. Interface with exterior multicast routing protocols. 1166 5. Possible operation with multiple border routers (presently beyond 1167 scope of this document). 1168 6. Provisions for participating non-SMF devices (routers or hosts). 1170 Each of these areas is discussed in more detail in the following 1171 subsections. Note the behavior of SMF border routers is the same as 1172 that of non-border SMF routers when forwarding packets on interfaces 1173 within the SMF routing domain. Packets that are passed outbound to 1174 interfaces operating fixed-infrastructure multicast routing protocols 1175 SHOULD be evaluated for duplicate packet status since present 1176 standard multicast forwarding mechanisms do not usually perform this 1177 function. 1179 9.1. Forwarded Multicast Groups 1181 Mechanisms for dynamically determining groups for forwarding into a 1182 MANET SMF routing domain is an evolving technology area. Ideally, 1183 only traffic for which there is active group membership should be 1184 injected into the SMF domain. This can be accomplished by providing 1185 an IPv4 Internet Group Membership Protocol (IGMP) or IPv6 Multicast 1186 Listener Discovery (MLD) proxy protocol so that MANET SMF routers can 1187 inform attached border routers (and hence multicast networks) of 1188 their current group membership status. For specific systems and 1189 services it may be possible to statically configure group membership 1190 joins in border routers, but it is RECOMMENDED that some form of 1191 IGMP/MLD proxy or other explicit, dynamic control of membership be 1192 provided. Specification of such an IGMP/MLD proxy protocol is beyond 1193 the scope of this document. 1195 For outbound traffic, SMF border routers perform duplicate packet 1196 detection and forward non-duplicate traffic that meets TTL/hop limit 1197 and scoping criteria to interfaces external to the SMF routing 1198 domain. Appropriate IP multicast routing (e.g., PIM-based solutions) 1199 on those interfaces can make further forwarding decisions with 1200 respect to the multicast packet. Note that the presence of multiple 1201 border routers associated with a MANET routing domain raises 1202 additional issues. This is further discussed in Section 9.4 but 1203 further work is expected to be needed here. 1205 9.2. Multicast Group Scoping 1207 Multicast scoping is used by network administrators to control the 1208 network routing domains reachable by multicast packets. This is 1209 usually done by configuring external interfaces of border routers in 1210 the border of a routing domain to not forward multicast packets which 1211 must be kept within the SMF routing domain. This is commonly done 1212 based on TTL/hop-limit of messages or by using adminstratively scoped 1213 group addresses. These schemes are known respectively as: 1215 1. TTL scoping. 1216 2. Administrative scoping. 1218 For IPv4, network administrators can configure border routers with 1219 the appropriate TTL/hop-limit thresholds or administratively scoped 1220 multicast groups for the router interfaces as with any traditional 1221 multicast router. However, for the case of TTL/hop-limit scoping it 1222 SHOULD be taken into account that the packet could traverse multiple 1223 hops within the MANET SMF routing domain before reaching the border 1224 router. Thus, TTL thresholds SHOULD be selected carefully. 1226 For IPv6, multicast address spaces include information about the 1227 scope of the group. Thus, border routers of an SMF routing domain 1228 know if they must forward a packet based on the IPv6 multicast group 1229 address. For the case of IPv6, it is RECOMMENDED that a MANET SMF 1230 routing domain be designated a site-scoped multicast domain. Thus, 1231 all IPv6 site-scoped multicast packets in the range FF05::/16 SHOULD 1232 be kept within the MANET SMF routing domain by border routers. IPv6 1233 packets in any other wider range scopes (i.e. FF08::/16, FF0B::/16 1234 and FF0E::16) MAY traverse border routers unless other restrictions 1235 different from the scope applies. 1237 Given that scoping of multicast packets is performed at the border 1238 routers, and given that existing scoping mechanisms are not designed 1239 to work with mobile routers, it is assumed that non-border routers 1240 running SMF will not stop forwarding multicast data packets of an 1241 appropriate site scoping. That is, it is assumed that an SMF routing 1242 domain is a site-scoped multicast area. 1244 9.3. Interface with Exterior Multicast Routing Protocols 1246 The traditional operation of multicast routing protocols is tightly 1247 integrated with the group membership function. Leaf routers are 1248 configured to periodically gather group membership information, while 1249 intermediate routers conspire to create multicast trees connecting 1250 routers with directly-connected multicast sources and routers with 1251 active multicast receivers. In the concrete case of SMF, border 1252 routers can be considered leaf routers. Mechanisms for multicast 1253 sources and receivers to interoperate with border routers over the 1254 multihop MANET SMF routing domain as if they were directly connected 1255 to the router need to be defined. The following issues need to be 1256 addressed: 1258 1. A mechanism by which border routers gather membership information 1259 2. A mechanism by which multicast sources are known by the border 1260 router 1261 3. A mechanism for exchange of exterior routing protocol messages 1262 across the SMF routing domain if the SMF routing domain is to 1263 provide transit connectivity for multicast traffic. 1265 It is beyond the scope of this document to address implementation 1266 solutions to these issues. As described in Section 9.1, IGMP/MLD 1267 proxy mechanisms can address some of these issues. Similarly, 1268 exterior routing protocol messages could be tunneled or conveyed 1269 across an SMF routing domain but doing this robustly in a distributed 1270 wireless environment likely requires additional considerations 1271 outside the scope of this document. 1273 The need for the border router to receive traffic from recognized 1274 multicast sources within the SMF routing domain is important to 1275 achieve interoperability with some existing routing protocols. For 1276 instance, PIM-S requires routers with locally attached multicast 1277 sources to register them to the Rendezvous Point (RP) so that routers 1278 can join the multicast tree. In addition, if those sources are not 1279 advertised to other autonomous systems (AS) using Multicast Source 1280 Discovery Protocol (MSDP), receivers in those external networks are 1281 not able to join the multicast tree for that source. 1283 9.4. Multiple Border Routers 1285 An SMF routing domain might be deployed with multiple participating 1286 routers having connectivity to external, fixed-infrastructure 1287 networks. Allowing multiple routers to forward multicast traffic to/ 1288 from the SMF routing domain can be beneficial since it can increase 1289 reliability, and provide better service. For example, if the SMF 1290 routing domain were to fragment with different SMF routers 1291 maintaining connectivity to different border routers, multicast 1292 service could still continue successfully. But, the case of multiple 1293 border routers connecting an SMF routing domain to external networks 1294 presents several challenges for SMF: 1296 1. Handling duplicate unmarked IPv4 or IPv6 (without IPsec 1297 encapsulation or DPD option) packets possibly injected by 1298 multiple border routers. 1299 2. Source-based relay algorithms handling of duplicate traffic 1300 injected by multiple border routers. 1301 3. Determination of which border router(s) will forward outbound 1302 multicast traffic. 1303 4. Additional challenges with interfaces to exterior multicast 1304 routing protocols. 1306 When multiple border routers are present they may be alternatively 1307 (due to route changes) or simultaneously injecting common traffic 1308 into the SMF routing domain that has not been previously marked for 1309 IPv6 SMF_DPD. Different border routers would not be able to 1310 implicitly synchronize sequencing of injected traffic since they may 1311 not receive exactly the same messages due to packet losses. For IPv6 1312 I-DPD operation, the optional "TaggerId" field described for the 1313 SMF_DPD header option can be used to mitigate this issue. When 1314 multiple border routers are injecting a flow into an SMF routing 1315 domain, there are two forwarding policies that SMF routers running 1316 I-DPD may implement: 1318 1. Redundantly forward the multicast flows (identified by ) from each border router, performing DPD processing on a 1320 or basis, or 1321 2. Use some basis to select the flow of one tagger (border router) 1322 over the others and forward packets for applicable flows 1323 (identified by ) only for the selected 1324 "Tagger ID" until timeout or some other criteria to favor another 1325 tagger occurs. 1327 It is RECOMMENDED that the first approach be used in the case of 1328 I-DPD operation. Additional specification may be required to 1329 describe an interoperable forwarding policy based on this second 1330 option. Note that the implementation of the second option requires 1331 that per-flow (i.e., ) state be maintained for the 1332 selected "Tagger ID". 1334 The deployment of H-DPD operation may alleviate DPD resolution when 1335 ingressing traffic comes from multiple border routers. Non-colliding 1336 hash indexes (those not requiring the H-DPD options header in IPv6) 1337 should be resolved effectively. 1339 10. Security Considerations 1341 Gratuitous use of option headers can cause problems in routers. 1342 Other IP routers external to an SMF routing domain that might receive 1343 forwarded multicast SHOULD ignore SMF-specific IPv6 header options 1344 when encountered. The header options types are encoded appropriately 1345 to allow for this behavior. 1347 This section briefly discusses several SMF denial-of-service (DoS) 1348 attack scenarios and we provide some initial recommended mitigation 1349 strategies. 1351 A potential denial-of-service attack against SMF forwarding is 1352 possible when a malicious router has a form of wormhole access to 1353 non-adjacent parts of a network topology. In the wireless ad hoc 1354 case, a directional antenna is one way to provide such a wormhole 1355 physically. If such a router can preview forwarded packets in a non- 1356 adjacent part of the network and forward modified versions to another 1357 part of the network it can perform the following attack. The 1358 malicious router could reduce the TTL/hop-limit or Hop Limit of the 1359 packet and transmit it to the SMF router causing it to forward the 1360 packet with a limited TTL/hop-limit (or even drop it) and make a DPD 1361 entry that could block or limit the subsequent forwarding of later- 1362 arriving valid packets with correct TTL/hop-limit values. This would 1363 be a relatively low-cost, high-payoff attack that would be hard to 1364 detect and thus attractive to potential attackers. An approach of 1365 caching TTL/hop-limit information with DPD state and taking 1366 appropriate forwarding actions is identified in Section 5 to mitigate 1367 this form of attack. 1369 Sequence-based packet identifiers are predictable and thus provide an 1370 opportunity for a DoS attack against forwarding. Forwarding 1371 protocols that use DPD techniques, such as SMF, may be vulnerable to 1372 DoS attacks based on spoofing packets with apparently valid packet 1373 identifier fields. In wireless environments, where SMF will most 1374 likely be used, the opportunity for such attacks may be more 1375 prevalent than in wired networks. In the case of IPv4 packets, 1376 fragmented IP packets or packets with IPsec headers applied, the DPD 1377 "identifier portions" of potential future packets that might be 1378 forwarded is highly predictable and easily subject to DoS attacks 1379 against forwarding. A RECOMMENDED technique to counter this concern 1380 is for SMF implementations to generate an "internal" hash value that 1381 is concatenated with the explicit I-DPD packet identifier to form a 1382 unique identifier that is a function of the packet content as well as 1383 the visible identifier. SMF implementations could seed their hash 1384 generation with a random value to make it unlikely that an external 1385 observer could guess how to spoof packets used in a denial-of-service 1386 attack against forwarding. Since the hash computation and state is 1387 kept completely internal to SMF routers, the cryptographic properties 1388 of this hashing would not need to be extensive and thus possibly of 1389 low complexity. Experimental implementations may determine that a 1390 lightweight hash of even only portions of packets may suffice to 1391 serve this purpose. 1393 While H-DPD is not as readily susceptible to this form of DoS attack, 1394 it is possible that a sophisticated adversary could use side 1395 information to construct spoofing packets to mislead forwarders using 1396 a well-known hash algorithm. Thus, similarly, a separate "internal" 1397 hash value could be concatenated with the well-known hash value to 1398 alleviate this security concern. 1400 The support of forwarding IPsec packets without further modification 1401 for both IPv4 and IPv6 is supported by this specification. 1403 Authentication mechanisms to identify the source of IPv6 option 1404 headers should be considered to reduce vulnerability to a variety of 1405 attacks. 1407 Furthermore, when the MANET Neighborhood Discovery Protocol [RFC6130] 1408 is used, the security considerations described there also applies. 1410 11. IANA Considerations 1412 This document defines one IPv6 Hop-by-Hop Option, a type for which 1413 which must be allocated from the IPv6 "Destination Options and Hop- 1414 by-Hop Options" registry of [RFC2780]. 1416 This document creates one registry for recording TaggerId types, 1417 (TidTy). 1419 This document requests registration of one well-known multicast 1420 address from each of the IPv4 and IPv6 multicast address spaces. 1422 This document defines one Message TLV, a type for which must be 1423 allocated from the "Message TLV Types" registry of [RFC5444]. 1425 Finally, this document defines one Address Block TLV, a type for 1426 which must be allocated from the "Address Block TLV Types" registry 1427 of [RFC5444]. 1429 11.1. IPv6 SMF_DPD Header Extension Option Type 1431 IANA is requested to allocate an IPv6 Option Type from the IPv6 1432 "Destination Options and Hop-by-Hop Options" registry of [RFC2780], 1433 as specified in Table 9. 1435 +----------+-----+-----+------+-------------------------+-----------+ 1436 | Mnemonic | act | chg | rest | Description | Reference | 1437 +----------+-----+-----+------+-------------------------+-----------+ 1438 | SMF_DPD | 00 | 0 | TBD | Multicast Duplicate | This | 1439 | | | | | Packet Detection (DPD) | Document | 1440 +----------+-----+-----+------+-------------------------+-----------+ 1442 Table 9: IPv6 Option Type Allocation 1444 11.2. TaggerId Types (TidTy) 1446 A portion of the option data content in the SMF_DPD is the Taggger 1447 Identifier Type (TidTy), that provides a context for the optionally 1448 included "TaggerId". 1450 IANA is requested to create a registry for recording TaggerId Types 1451 (TidTy), with initial assignments and allocation policies, as 1452 specified in Table 10. 1454 +----------+------+-------------------------------+-----------------+ 1455 | Mnemonic | Type | Description | Reference | 1456 +----------+------+-------------------------------+-----------------+ 1457 | NULL | 0 | No "TaggerId" field is | This document | 1458 | | | present | | 1459 | DEFAULT | 1 | A "TaggerId" of non-specific | This document | 1460 | | | context is present | | 1461 | IPv4 | 2 | A "TaggerId" representing an | This document | 1462 | | | IPv4 address is present | | 1463 | IPv6 | 3 | A "TaggerId" representing an | This document | 1464 | | | IPv6 address is present | | 1465 | | 4-6 | | Unassigned | 1466 | | | | (IETF Review) | 1467 | ExtId | 7 | | Unassigned | 1468 | | | | (Expert Review) | 1469 +----------+------+-------------------------------+-----------------+ 1471 Table 10: TaggerId Types 1473 For allocation of unassigned values 4-6, IETF Review is required. 1475 For allocation of unassigned value 7, Expert Review is required, with 1476 the following specific guidelines to the Expert: this value is 1477 intended for use in case a future development of this specification 1478 requires extending the type space (e.g. by way of providing a pointer 1479 to a subsequent field). 1481 11.3. Well-known Multicast Address 1483 IANA is requested to allocate an IPv4 multicast address "SL-MANET- 1484 ROUTERS" from the "Internetwork Control Block (224.0.1/24)" sub- 1485 registry of the "IPv4 Multicast Address" registry. 1487 IANA is requested to allocate an IPv6 multicast address "SL-MANET- 1488 ROUTERS" from the "Site-Local Scope Multicast Addresses" sub-sub- 1489 registry of the "Fixed Scope Multicast Addresses" sub-registry of the 1490 "INTERNET PROTOCOL VERSION 6 MULTICAST ADDRESSES" registry. 1492 11.4. SMF Type-Length-Values 1494 11.4.1. Expert Review for created Type Extension Registries 1496 Creation of Address Block TLV Types and Message TLV Types in 1497 registries of [RFC5444], and hence in the HELLO message specific 1498 registries of [RFC6130], entails creation of corresponding Type 1499 Extension registries for each such type. For such Type Extension 1500 registries, where an Expert Review is required, the designated expert 1501 SHOULD take the same general recommendations into consideration as 1502 are specified by [RFC5444]. 1504 11.4.2. SMF Message TLV Type (SMF_TYPE) 1506 This document defines one Message TLV Type, "SMF_TYPE", which must be 1507 allocated from the "HELLO Message-Type-specific Message TLV Types" 1508 registry, defined in [RFC6130]. 1510 This will create a new Type Extension registry, with initial 1511 assignments as specified in Table 11. 1513 +----------+------+-----------+--------------------+----------------+ 1514 | Name | Type | Type | Description | Allocation | 1515 | | | Extension | | Policy | 1516 +----------+------+-----------+--------------------+----------------+ 1517 | SMF_TYPE | TBD2 | 0-255 | Specifies relay | Section 11.4.4 | 1518 | | | | algorithm | | 1519 | | | | supported by the | | 1520 | | | | SMF router, | | 1521 | | | | originating the | | 1522 | | | | HELLO message, | | 1523 | | | | according to | | 1524 | | | | Section 11.4.4. | | 1525 +----------+------+-----------+--------------------+----------------+ 1527 Table 11: SMF_TYPE Message TLV Type Extension Registry 1529 11.4.3. SMF Address Block TLV Type (SMF_NBR_TYPE) 1531 This document defines one Address Block TLV Type, "SMF_NBR_TYPE", 1532 which must be allocated from the "HELLO Message-Type-specific Address 1533 Block TLV Types" registry, defined in [RFC6130]. 1535 This will create a new Type Extension registry, with initial 1536 assignments as specified in Table 12. 1538 +-------------+------+-----------+-----------------+----------------+ 1539 | Name | Type | Type | Description | Allocation | 1540 | | | Extension | | Policy | 1541 +-------------+------+-----------+-----------------+----------------+ 1542 | SMF_NBR_TYP | TBD2 | 0-255 | Specifies relay | Section 11.4.4 | 1543 | E | | | algorithm | | 1544 | | | | supported by | | 1545 | | | | the SMF router | | 1546 | | | | corresponding | | 1547 | | | | to the | | 1548 | | | | advertised | | 1549 | | | | address, | | 1550 | | | | according to | | 1551 | | | | Section 11.4.4. | | 1552 +-------------+------+-----------+-----------------+----------------+ 1554 Table 12: SMF_NBR_TYPE Address Block TLV Type Extension Registry 1556 11.4.4. SMF Relay Algorithm ID Registry 1558 Types for the Type Extension Registries for the SMF_TYPE Message TLV 1559 and the SMF_NBR_TYPE Address Block TLV are unified in this single SMF 1560 Relay Algorithm ID Registry, defined in this section. 1562 IANA is requested to create a registry for recording Relay Algorithm 1563 Identifiers, with initial assignments and allocation policies as 1564 specified in Table 13. 1566 +---------+---------+-------------+-------------------+ 1567 | Name | Value | Description | Allocation Policy | 1568 +---------+---------+-------------+-------------------+ 1569 | CF | 0 | Section 4 | | 1570 | S-MPR | 1 | Appendix B | | 1571 | E-CDS | 2 | Appendix A | | 1572 | MPR-CDS | 3 | Appendix C | | 1573 | | 4-127 | Unassigned | Expert Review | 1574 | | 128-255 | Unassigned | Experimental Use | 1575 +---------+---------+-------------+-------------------+ 1576 Table 13: Relay Set Algorithm Type Values 1578 A specification requesting an allocation from the 4-127 range from 1579 the SMF Relay Algorithm ID Registry MUST specify the interpretation 1580 of the field (if any). 1582 12. Acknowledgments 1584 Many of the concepts and mechanisms used and adopted by SMF resulted 1585 over several years of discussion and related work within the MANET 1586 working group since the late 1990s. There are obviously many 1587 contributors to past discussions and related draft documents within 1588 the working group that have influenced the development of SMF 1589 concepts and they deserve acknowledgment. In particular, the 1590 document is largely a direct product of the earlier SMF design team 1591 within the IETF MANET working group and borrows text and 1592 implementation ideas from the related individuals and activities. 1593 Some of the direct contributors who have been involved in design, 1594 content editing, prototype implementation, major commenting, and core 1595 discussions are listed below in alphabetical order. We appreciate 1596 all the input and feedback from the many community members and early 1597 implementation users we have heard from that are not on this list as 1598 well. 1600 Some core contributors/authors in alphabetical order: 1601 Brian Adamson 1602 Teco Boot 1603 Ian Chakeres 1604 Thomas Clausen 1605 Justin Dean 1606 Brian Haberman 1607 Ulrich Herberg 1608 Charles Perkins 1609 Pedro Ruiz 1610 Fred Templin 1611 Maoyu Wang 1613 The RFC text was produced using Marshall Rose's xml2rfc tool and Bill 1614 Fenner's XMLmind add-ons. 1616 13. References 1618 13.1. Normative References 1620 [MPR-CDS] Adjih, C., Jacquet, P., and L. Viennot, "Computing 1621 Connected Dominating Sets with Multipoint Relays", Ad Hoc 1622 and Sensor Wireless Networks , January 2005. 1624 [RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791, 1625 September 1981. 1627 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1628 Requirement Levels", BCP 14, RFC 2119, March 1997. 1630 [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 1631 (IPv6) Specification", RFC 2460, December 1998. 1633 [RFC2644] Senie, D., "Changing the Default for Directed Broadcasts 1634 in Routers", BCP 34, RFC 2644, August 1999. 1636 [RFC2780] Bradner, S. and V. Paxson, "IANA Allocation Guidelines For 1637 Values In the Internet Protocol and Related Headers", 1638 BCP 37, RFC 2780, March 2000. 1640 [RFC3174] Eastlake, D. and P. Jones, "US Secure Hash Algorithm 1 1641 (SHA1)", RFC 3174, September 2001. 1643 [RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing 1644 Protocol (OLSR)", RFC 3626, October 2003. 1646 [RFC4291] Hinden, R. and S. Deering, "IP Version 6 Addressing 1647 Architecture", RFC 4291, February 2006. 1649 [RFC4302] Kent, S., "IP Authentication Header", RFC 4302, 1650 December 2005. 1652 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 1653 IANA Considerations Section in RFCs", BCP 26, RFC 5226, 1654 May 2008. 1656 [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 1657 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 1658 Format", RFC 5444, February 2009. 1660 [RFC5614] Ogier, R. and P. Spagnolo, "Mobile Ad Hoc Network (MANET) 1661 Extension of OSPF Using Connected Dominating Set (CDS) 1662 Flooding", RFC 5614, August 2009. 1664 [RFC5771] Cotton, M., Vegoda, L., and D. Meyer, "IANA Guidelines for 1665 IPv4 Multicast Address Assignments", BCP 51, RFC 5771, 1666 March 2010. 1668 [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc 1669 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 1670 RFC 6130, April 2011. 1672 13.2. Informative References 1674 [CDHM07] Chakeres, I., Danilov, C., and T. Henderson, "Connecting 1675 MANET Multicast", IEEE MILCOM 2007 Proceedings , 2007. 1677 [DHG09] Danilov, C., Henderson, T., and T. Goff, "Experiment and 1678 field demonstration of a 802.11-based ground-UAV mobile 1679 ad-hoc network", Proceedings of the 28th IEEE conference 1680 on Military Communications , 2009. 1682 [DHS08] Danilov, C., Henderson, T., and T. Spagnolo, "MANET 1683 Multicast with Multiple Gateways", IEEE MILCOM 2008 1684 Proceedings , 2008. 1686 [GM99] Garcia-Luna-Aceves, JJ. and E. Madruga, "The core-assisted 1687 mesh protocol", Selected Areas in Communications, IEEE 1688 Journal on Volume 17, Issue 8, August 1999. 1690 [I-D.ietf-intarea-ipv4-id-update] 1691 Touch, J., "Updated Specification of the IPv4 ID Field", 1692 draft-ietf-intarea-ipv4-id-update-04 (work in progress), 1693 September 2011. 1695 [JLMV02] Jacquet, P., Laouiti, V., Minet, P., and L. Viennot, 1696 "Performance of multipoint relaying in ad hoc mobile 1697 routing protocols", Networking , 2002. 1699 [MDC04] Macker, J., Dean, J., and W. Chao, "Simplified Multicast 1700 Forwarding in Mobile Ad hoc Networks", IEEE MILCOM 2004 1701 Proceedings , 2004. 1703 [MDDA07] Macker, J., Downard, I., Dean, J., and R. Adamson, 1704 "Evaluation of distributed cover set algorithms in mobile 1705 ad hoc network for simplified multicast forwarding", ACM 1706 SIGMOBILE Mobile Computing and Communications Review 1707 Volume 11 , Issue 3, July 2007. 1709 [MGL04] Mohapatra, P., Gui, C., and J. Li, "Group Communications 1710 in Mobile Ad hoc Networks", IEEE Computer Vol. 37, No. 2, 1711 February 2004. 1713 [NTSC99] Ni, S., Tseng, Y., Chen, Y., and J. Sheu, "The Broadcast 1714 Storm Problem in Mobile Ad hoc Networks", Proceedings Of 1715 ACM Mobicom 99 , 1999. 1717 [RFC2501] Corson, M. and J. Macker, "Mobile Ad hoc Networking 1718 (MANET): Routing Protocol Performance Issues and 1719 Evaluation Considerations", RFC 2501, January 1999. 1721 [RFC3684] Ogier, R., Templin, F., and M. Lewis, "Topology 1722 Dissemination Based on Reverse-Path Forwarding (TBRPF)", 1723 RFC 3684, February 2004. 1725 [RFC3973] Adams, A., Nicholas, J., and W. Siadak, "Protocol 1726 Independent Multicast - Dense Mode (PIM-DM): Protocol 1727 Specification (Revised)", RFC 3973, January 2005. 1729 [RFC4601] Fenner, B., Handley, M., Holbrook, H., and I. Kouvelas, 1730 "Protocol Independent Multicast - Sparse Mode (PIM-SM): 1731 Protocol Specification (Revised)", RFC 4601, August 2006. 1733 Appendix A. Essential Connecting Dominating Set (E-CDS) Algorithm 1735 The "Essential Connected Dominating Set" (E-CDS) algorithm [RFC5614] 1736 forms a single CDS mesh for the SMF operating region. It allows 1737 routers to use 2-hop neighborhood topology information to dynamically 1738 perform relay self election to form a CDS. Its packet forwarding 1739 rules are not dependent upon previous hop knowledge. Additionally, 1740 E-CDS SMF forwarders can be easily mixed without problems with CF SMF 1741 forwarders, even those not participating in NHDP. Another benefit is 1742 that packets opportunistically received from non-symmetric neighbors 1743 may be forwarded without compromising flooding efficiency or 1744 correctness. Furthermore, multicast sources not participating in 1745 NHDP may freely inject their traffic and any neighboring E-CDS relays 1746 will properly forward the traffic. The E-CDS based relay set 1747 selection algorithm is based upon [RFC5614]. E-CDS was originally 1748 discussed in the context of forming partial adjacencies and efficient 1749 flooding for MANET OSPF extensions work and the core algorithm is 1750 applied here for SMF. 1752 It is RECOMMENDED that the SMF_TYPE:E-CDS Message TLV be included in 1753 NHDP_HELLO messages that are generated by routers conducting E-CDS 1754 SMF operation. It is also RECOMMENDED that the SMF_NBR_TYPE:E-CDS 1755 address block TLV be used to advertise neighbor routers that are also 1756 conducting E-CDS SMF operation. 1758 A.1. E-CDS Relay Set Selection Overview 1760 The E-CDS relay set selection requires 2-hop neighborhood information 1761 collected through NHDP or another process. Relay routers, in E-CDS 1762 SMF selection, are "self-elected" using a router identifier (Router 1763 ID) and an optional nodal metric, referred to here as "Router 1764 Priority" for all 1-hop and 2-hop neighbors. To ensure proper relay 1765 set self-election, the Router ID and Router Priority MUST be 1766 consistent among participating routers. It is RECOMMENDED that NHDP 1767 be used to share Router ID and Router Priority through the use of 1768 SMF_TYPE:E-CDS TLVs as described in this appendix. The Router ID is 1769 a logical identification that MUST be consistent across 1770 interoperating SMF neighborhoods and it is RECOMMENDED to be chosen 1771 as the numerically largest address contained in a routers "Neighbor 1772 Address List" as defined in NHDP. The E-CDS self-election process 1773 can be summarized as follows: 1775 1. If an SMF router has a higher ordinal (Router Priority, Router 1776 ID) than all of its symmetric neighbors, it elects itself to act 1777 as a forwarder for all received multicast packets, 1778 2. Else, if there does not exist a path from the neighbor with 1779 largest (Router Priority, Router ID) to any other neighbor, via 1780 neighbors with larger values of (Router Priority, Router ID), 1781 then it elects itself to the relay set. 1783 The basic form of E-CDS described and applied within this 1784 specification does not provide for redundant relay set election 1785 (e.g., bi-connected) but such capability is supported by the basic 1786 E-CDS design. 1788 A.2. E-CDS Forwarding Rules 1790 With E-CDS, any SMF router that has selected itself as a relay 1791 performs DPD and forwards all non-duplicative multicast traffic 1792 allowed by the present forwarding policy. Packet previous hop 1793 knowledge is not needed for forwarding decisions when using E-CDS. 1795 1. Upon packet reception, DPD is performed. Note E-CDS requires a 1796 single duplicate table for the set of interfaces associated with 1797 the relay set selection. 1798 2. If the packet is a duplicate, no further action is taken. 1799 3. If the packet is non-duplicative: 1800 A. A DPD entry is made for the packet identifier 1801 B. The packet is forwarded out all interfaces associated with 1802 the relay set selection 1804 As previously mentioned, even packets sourced (or relayed) by routers 1805 not participating in NHDP and/or the E-CDS relay set selection may be 1806 forwarded by E-CDS forwarders without problem. A particular 1807 deployment MAY choose to not forward packets from previous hop 1808 routers that have been not explicitly identified via NHDP or other 1809 means as operating as part of a different relay set algorithm (e.g. 1810 S-MPR) to allow coexistent deployments to operate correctly. Also, 1811 E-CDS relay set selection may be configured to be influenced by 1812 statically-configured CF relays that are identified via NHDP or other 1813 means. 1815 A.3. E-CDS Neighborhood Discovery Requirements 1817 It is possible to perform E-CDS relay set selection without 1818 modification of NHDP, basing the self-election process exclusively on 1819 the "Neighbor Address List" of participating SMF routers. For 1820 example by setting the "Router Priority" to a default value and 1821 selecting the "Router ID" as the numerically largest address 1822 contained in the "Neighbor Address List". However steps MUST be 1823 taken to insure that all NHDP enabled routers not using SMF_TYPE:E- 1824 CDS full type Message TLVs are in fact running SMF E-CDS with the 1825 same methods for selecting "Router Priority" and "Router ID", 1826 otherwise incorrect forwarding may occur. Note that SMF routers with 1827 higher "Router Priority" values will be favored as relays over 1828 routers with lower "Router Priority". Thus, preferred relays MAY be 1829 administratively configured to be selected when possible. 1830 Additionally, other metrics (e.g. nodal degree, energy capacity, etc) 1831 may also be taken into account in constructing a "Router Priority" 1832 value. When using "Router Priority" with multiple interfaces all 1833 interfaces on a router MUST use and advertise a common "Router 1834 Priority" value. A routers "Router Priority" value may be 1835 administratively or algorithmically selected. The method of 1836 selection does not need to be the same among different routers. 1838 E-CDS relay set selection may be configured to be influenced by 1839 statically configured CF relays that are identified via NHDP or other 1840 means. Nodes advertising CF through NHDP may be considered E-CDS SMF 1841 routers with maximal "Router Priority". 1843 To share a router's "Router Priority" with its 1-hop neighbors the 1844 SMF_TYPE:E-CDS Message TLV's field is defined as shown in 1845 Table 14. 1847 +---------------+---------+-----------------+ 1848 | Length(bytes) | Value | Router Priority | 1849 +---------------+---------+-----------------+ 1850 | 0 | N/A | 64 | 1851 | 1 | | 0-127 | 1852 +---------------+---------+-----------------+ 1854 Table 14: E-CDS Message TLV Values 1856 Where is a one octet long bit field which is defined as: 1858 bit 0: the leftmost bit is reserved and SHOULD be set to 0. 1860 bit 1-7: contain the unsigned "Router Priority" value, 0-127, which 1861 is associated with the "Neighbor Address List". 1863 Combinations of value field lengths and values other than specified 1864 here are NOT permitted and SHOULD be ignored. Figure 5 shows an 1865 example SMF_TYPE:E-CDS Message TLV 1867 0 1 2 3 1868 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 1869 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1870 ... | SMF_TYPE |1|0|0|1|0|0| | 1871 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1872 | E-CDS |0|0|0|0|0|0|0|1|R| priority | ... | 1873 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1875 Figure 5: E-CDS Message TLV Example 1877 To convey "Router Priority" values among 2-hop neighborhoods the 1878 SMF_NBR_TYPE:E-CDS address block TLV's field is used. Multi- 1879 index and multi-value TLV layouts as defined in [RFC5444] are 1880 supported. SMF_NBR_TYPE:E-CDS value fields are defined thus: 1882 +---------------+--------+----------+-------------------------------+ 1883 | Length(bytes) | # Addr | Value | Router Priority | 1884 +---------------+--------+----------+-------------------------------+ 1885 | 0 | Any | N/A | 64 | 1886 | 1 | Any | | is for all addresses | 1887 | N | N | * | Each address gets its own | 1888 | | | | | 1889 +---------------+--------+----------+-------------------------------+ 1891 Table 15: E-CDS Address Block TLV Values 1893 Where is a one byte bit field which is defined as: 1895 bit 0: the leftmost bit is reserved and SHOULD be set to 0. 1897 bit 1-7: contain the unsigned "Router Priority" value, 0-127, which 1898 is associated with the appropriate address(es). 1900 Combinations of value field lengths and # of addresses other than 1901 specified here are NOT permitted and SHOULD be ignored. A default 1902 technique of using nodal degree (i.e. count of 1-hop neighbors) is 1903 RECOMMENDED for the value field of these TLV types. Below are two 1904 example SMF_NBR_TYPE:E-CDS address block TLVs. 1906 0 1 2 3 1907 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 1908 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1909 ... | SMF_NBR_TYPE |1|0|0|1|0|0| | 1910 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1911 | E-CDS |0|0|0|0|0|0|0|1|R| priority | ... | 1912 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1914 Figure 6: E-CDS Address Block TLV Example 1 1916 The single value example TLV, depicted in Figure 6 , specifies that 1917 all address(es) contained in the address block are running SMF using 1918 the E-CDS algorithm and all address(es) share the value field and 1919 therefore the same "Router Priority". 1920 0 1 2 3 1921 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 1922 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1923 ... | SMF_NBR_TYPE |1|0|1|1|0|1| | 1924 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1925 | E-CDS | index-start | index-end | length | 1926 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1927 |R| priority0 |R| priority1 | ... |R| priorityN | 1928 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1930 Figure 7: E-CDS Address Block TLV Example 2 1932 The example multivalued TLV, depicted in Figure 7, specifies that 1933 address(es) contained in the address block from index-start to index- 1934 end inclusive are running SMF using the E-CDS algorithm. Each 1935 address is associated with its own value byte and therefore its own 1936 "Router Priority". 1938 A.4. E-CDS Selection Algorithm 1940 This section describes an algorithm for E-CDS relay selection (self- 1941 election). The algorithm described uses 2-hop information. Note it 1942 is possible to extend this algorithm to use k-hop information with 1943 added computational complexity and mechanisms for sharing k-hop 1944 topology information that are not described in this document or 1945 within the NHDP specification. It should also be noted that this 1946 algorithm does not impose the "hop limit" bound described in 1947 [RFC5614] when performing the path search that is used for relay 1948 selection. However, the algorithm below could be easily augmented to 1949 accommodate this additional criterion. It is not expected that the 1950 "hop limit" bound will provide significant benefit to the algorithm 1951 defined in this appendix. 1953 The tuple of "Router Priority" and "Router ID" is used in E-CDS relay 1954 set selection. Precedence is given to the "Router Priority" portion 1955 and the "Router ID" value is used as a tie-breaker. The evaluation 1956 of this tuple is referred to as "RtrPri(n)" in the description below 1957 where "n" references a specific router. Note it is possible that the 1958 "Router Priority" portion may be optional and the evaluation of 1959 "RtrPri()" be solely based upon the unique "Router ID". Since there 1960 MUST NOT be any duplicate "Router ID" values among SMF routers, a 1961 comparison of RtrPri(n) between any two routers will always be an 1962 inequality. The use of nodal degree for calculating "Router 1963 Priority" is RECOMMENDED as default and the largest IP address in the 1964 "Neighbor Address List" as advertised by NHDP MUST be used as the 1965 "Router ID". NHDP provides all interface address throughout the 1966 2-hop neighborhood through HELLO messages, so explicitly conveying a 1967 "Router ID" is not necessary. The following steps describe a basic 1968 algorithm for conducting E-CDS relay selection for a router "n0": 1969 1. Initialize the set "N1" with tuples ("Router Priority", "Router 1970 ID", "Neighbor Address List") for each 1-hop neighbor of "n0". 1971 2. If "N1" has less than 2 tuples, then "n0" does not elect itself 1972 as a relay and no further steps are taken. 1973 3. Initialize the set "N2" with tuples ("Router Priority", "Router 1974 ID", "2-hop address") for each "2-hop address" of "n0", where 1975 "2-hop address" is defined in NHDP. 1976 4. If "RtrPri(n0)" is greater than that of all tuples in the union 1977 of "N1" and "N2", then "n0" selects itself as a relay and no 1978 further steps are taken. 1979 5. Initialize all tuples in the union of "N1" and "N2" as 1980 "unvisited". 1981 6. Find the tuple "n1_Max" that has the largest "RtrPri()" of all 1982 tuples in "N1" 1983 7. Initialize queue "Q" to contain "n1_Max", marking "n1_Max" as 1984 "visited" 1985 8. While router queue "Q" is not empty, remove router "x" from the 1986 head of "Q", and for each 1-hop neighbor "n" of router "x" 1987 (excluding "n0") that is not marked "visited" 1988 A. Mark router "n" as "visited" 1989 B. If "RtrPri(n)" is greater than "RtrPri(n0), append "n" to "Q" 1990 9. If any tuple in "N1" remains "unvisited", then "n0" selects 1991 itself as a relay. Otherwise "n0" does not act as a relay. 1992 Note these steps are re-evaluated upon neighborhood status changes. 1993 Steps 5 through 8 of this procedure describe an approach to a path 1994 search. The purpose of this path search is to determine if paths 1995 exist from the 1-hop neighbor with maximum "RtrPri()" to all other 1996 1-hop neighbors without traversing an intermediate router with a 1997 "RtrPri()" value less than "RtrPri(n0)". These steps comprise a 1998 breadth-first traversal that evaluates only paths that meet that 1999 criteria. If all 1-hop neighbors of "n0" are "visited" during this 2000 traversal, then the path search has succeeded and router "n0" does 2001 not need to provide relay. It can be assumed that other routers will 2002 provide relay operation to ensure SMF connectivity. 2004 It is possible to extend this algorithm to consider neighboring SMF 2005 routers that are known to be statically configured for CF (always 2006 relaying). The modification to the above algorithm is to process 2007 such routers as having a maximum possible "Router Priority" value. 2008 It is expected that routers configured for CF and participating in 2009 NHDP would indicate this with use of the SMF_TYPE:CF and 2010 SMF_NBR_TYPE:CF TLV types in their NHDP_HELLO message and address 2011 blocks, respectively. 2013 Appendix B. Source-based Multipoint Relay (S-MPR) 2015 The source-based multipoint relay (S-MPR) set selection algorithm 2016 enables individual routers, using two-hop topology information, to 2017 select relays from their set of neighboring routers. Relays are 2018 selected so that forwarding to the router's complete two-hop neighbor 2019 set is covered. This distributed relay set selection technique has 2020 been shown to approximate a minimal connected dominating set (MCDS) 2021 in [JLMV02]. Individual routers must collect two-hop neighborhood 2022 information from neighbors, determine an appropriate current relay 2023 set, and inform selected neighbors of their relay status. Note that 2024 since each router picks its neighboring relays independently, S-MPR 2025 forwarders depend upon previous hop information (e.g, source MAC 2026 address) to operate correctly. The Optimized Link State Routing 2027 (OLSR) protocol has used this algorithm and protocol for relay of 2028 link state updates and other control information [RFC3626] and it has 2029 been demonstrated operationally in dynamic network environments. 2031 It is RECOMMENDED that the SMF_TYPE:S-MPR Message TLV be included in 2032 NHDP_HELLO messages that are generated by routers conducting S-MPR 2033 SMF operation. It is also RECOMMENDED that the SMF_NBR_TYPE:S-MPR 2034 address block TLV be used to specify which neighbor routers are 2035 conducting S-MPR SMF operation. 2037 B.1. S-MPR Relay Set Selection Overview 2039 The S-MPR algorithm uses bi-directional 1-hop and 2-hop neighborhood 2040 information collected via NHDP to select, from a router's 1-hop 2041 neighbors, a set of relays that will cover the router's entire 2-hop 2042 neighbor set upon forwarding. The algorithm described uses a 2043 "greedy" heuristic of first picking the 1-hop neighbor who will cover 2044 the most 2-hop neighbors. Then, excluding those 2-hop neighbors that 2045 have been covered, additional relays from its 1-hop neighbor set are 2046 iteratively selected until the entire 2-hop neighborhood is covered. 2047 Note that 1-hop neighbors also identified as 2-hop neighbors are 2048 considered as 1-hop neighbors only. 2050 NHDP HELLO messages supporting S-MPR forwarding operation SHOULD use 2051 the TLVs defined in Section 8.1 using the S-MPR extended type. The 2052 value field of an address block TLV which has a full type value of 2053 SMF_NBR_TYPE:S-MPR is defined in Table 17 such that signaling of MPR 2054 selections to 1-hop neighbors is possible. The value field of a 2055 message block TLV which has a full type value of SMF_TYPE:S-MPR is 2056 defined in Table 16 such that signaling of "Router Priority" 2057 (described as "WILLINGNESS" in [RFC3626]) to 1-hop neighbors is 2058 possible. It is important to note that S-MPR forwarding is dependent 2059 upon the previous hop of an incoming packet. An S-MPR router MUST 2060 forward packets only for neighbors which have explicitly selected it 2061 as a multi-point relay (i.e., its "selectors"). There are also some 2062 additional requirements for duplicate packet detection to support 2063 S-MPR SMF operation that are described below. 2065 For multiple interface operation, MPR selection SHOULD be conducted 2066 on a per-interface basis. However, it is possible to economize MPR 2067 selection among multiple interfaces by selecting common MPRs to the 2068 extent possible. 2070 B.2. S-MPR Forwarding Rules 2072 An S-MPR SMF router MUST only forward packets for neighbors that have 2073 explicitly selected it as an MPR. The source-based forwarding 2074 technique also stipulates some additional duplicate packet detection 2075 operations. For multiple network interfaces, independent DPD state 2076 MUST be maintained for each separate interface. The following 2077 provides the procedure for S-MPR packet forwarding given the arrival 2078 of a packet on a given interface, denoted . There are 2079 three possible actions, depending upon the previous-hop transmitter: 2081 1. If the previous-hop transmitter has selected the current router 2082 as an MPR, 2083 A. The packet identifier is checked against the DPD state for 2084 each possible outbound interface, including the . 2085 B. If the packet is not a duplicate for an outbound interface, 2086 the packet is forwarded on that interface and a DPD entry is 2087 made for the given packet identifier for the interface. 2088 C. If the packet is a duplicate, no action is taken for that 2089 interface. 2090 2. Else, if the previous-hop transmitter is a 1-hop symmetric 2091 neighbor, 2092 A. A DPD entry is added for that packet for the , but 2093 the packet is not forwarded. 2094 3. Otherwise, no action is taken. 2096 Case number two in the above table is non-intuitive, but important to 2097 ensure correctness of S-MPR SMF operation. The selection of source- 2098 based relays does not result in a common set among neighboring 2099 routers, so relays MUST mark in their DPD state, packets received 2100 from non-selector, symmetric, one-hop neighbors (for a given 2101 interface) and not forward subsequent duplicates of that packet if 2102 received on that interface. Deviation here can result in 2103 unnecessary, repeated packet forwarding throughout the network, or 2104 incomplete flooding. 2106 Nodes not participating in neighborhood discovery and relay set 2107 selection will not be able to source multicast packets into the area 2108 and have SMF forward them, unlike E-CDS or MPR-CDS where forwarding 2109 may occur dependent on topology. Correct S-MPR relay behavior will 2110 occur with the introduction of repeaters (non-NHDP/SMF participants 2111 that relay multicast packets using duplicate detection and CF) but 2112 the repeaters will not efficiently contribute to S-MPR forwarding as 2113 these routers will not be identified as neighbors (symmetric or 2114 otherwise) in the S-MPR forwarding process. NHDP/SMF participants 2115 MUST NOT provide extra forwarding, forwarding packets which are not 2116 selected by the algorithm, as this can disrupt network-wide S-MPR 2117 flooding, resulting in incomplete or inefficient flooding. The 2118 result is that non S-MPR SMF routers will be unable to source 2119 multicast packets and have them forwarded by other S-MPR SMF routers. 2121 B.3. S-MPR Neighborhood Discovery Requirements 2123 Nodes may optionally signal a "Router Priority" value to their one 2124 hop neighbors by using the SMF_TYPE:S-MPR message block TLV value 2125 field. If the value field is omitted, a default "Router Priority" 2126 value of 64 is to be assumed. This is summarized here: 2128 +---------------+---------+-----------------+ 2129 | Length(bytes) | Value | Router Priority | 2130 +---------------+---------+-----------------+ 2131 | 0 | N/A | 64 | 2132 | 1 | | 0-127 | 2133 +---------------+---------+-----------------+ 2135 Table 16: S-MPR Message TLV Values 2137 Where is a one octet long bit field defined as: 2139 bit 0: the leftmost bit is reserved and SHOULD be set to 0. 2141 bit 1-7: contain the "Router Priority" value, 0-127, which is 2142 associated with the "Neighbor Address List". 2144 "Router Priority" values for S-MPR are interpreted in the same 2145 fashion as "WILLINGNESS" ([RFC3626])with value 0 indicating a router 2146 will NEVER forward and value 127 indicating a router will ALWAYS 2147 forward. Values 1-126 indicate how likely a S-MPR SMF router will be 2148 selected as an MPR by a neighboring SMF router, with higher values 2149 increasing the likelihood. Combinations of value field lengths and 2150 values other than specified here are NOT permitted and SHOULD be 2151 ignored. Below is an example SMF_TYPE:S-MPR Message TLV. 2153 0 1 2 3 2154 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 2155 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2156 ... | SMF_TYPE |1|0|0|1|0|0| | 2157 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2158 | S-MPR |0|0|0|0|0|0|0|1|R| priority | ... | 2159 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2161 Figure 8: S-MPR Message TLV Example 2163 S-MPR election operation requires 2-hop neighbor knowledge as 2164 provided by NHDP [RFC6130] or from external sources. MPRs are 2165 dynamically selected by each router and selections MUST be advertised 2166 and dynamically updated within NHDP or an equivalent protocol or 2167 mechanism. For NHDP use, the SMF_NBR_TYPE:S-MPR address block TLV 2168 value field is defined as such: 2170 +---------------+--------+----------+-------------------------------+ 2171 | Length(bytes) | # Addr | Value | Meaning | 2172 +---------------+--------+----------+-------------------------------+ 2173 | 0 | Any | N/A | NOT MPRs | 2174 | 1 | Any | | is for all addresses | 2175 | N | N | * | Each address gets its own | 2176 | | | | | 2177 +---------------+--------+----------+-------------------------------+ 2179 Table 17: S-MPR Address Block TLV Values 2181 Where , if present, is a one octet bit field defined as: 2183 bit 0: The leftmost bit is the M bit. When set indicates MPR 2184 selection of the relevant interface, represented by the associated 2185 address(es), by the originator router of the NHDP HELLO message. 2186 When unset, indicates the originator router of the NHDP HELLO message 2187 has not selected the relevant interfaces, represented by the 2188 associated address(es), as its MPR. 2190 bit 1-7: are reserved and SHOULD be set to 0. 2192 Combinations of value field lengths and number of addresses other 2193 than specified here are NOT permitted and SHOULD be ignored. All 2194 bits, excepting the leftmost bit, are RESERVED and SHOULD be set to 2195 0. 2196 0 1 2 3 2197 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 2198 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2199 ... | SMF_NBR_TYPE |1|1|0|1|0|0| | 2200 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2201 | S-MPR | start-index |0|0|0|0|0|0|0|1|M| reserved | 2202 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2204 Figure 9: S-MPR Address Block TLV Example 2206 The single index TLV example, depicted in Figure 9, indicates that 2207 the address specified by the field is running SMF using 2208 S-MPR and has been selected by the originator of the NHDP HELLO 2209 message as an MPR forwarder if the M bit is set. Multivalued TLVs 2210 may also be used to specify MPR selection status of multiple 2211 addresses using only one TLV. See Figure 7 for a similar example on 2212 how this may be done. 2214 B.4. S-MPR Selection Algorithm 2216 This section describes a basic algorithm for the S-MPR selection 2217 process. Note that the selection is with respect to a specific 2218 interface of the router performing selection and other router 2219 interfaces referenced are reachable from this reference router 2220 interface. This is consistent with the S-MPR forwarding rules 2221 described above. When multiple interfaces per router are used, it is 2222 possible to enhance the overall selection process across multiple 2223 interfaces such that common routers are selected as MPRs for each 2224 interface to avoid unnecessary inefficiencies in flooding. The 2225 following steps describe a basic algorithm for conducting S-MPR 2226 selection for a router interface "n0": 2228 1. Initialize the set "MPR" to empty. 2229 2. Initialize the set "N1" to include all 1-hop neighbors of "n0". 2230 3. Initialize the set "N2" to include all 2-hop neighbors, excluding 2231 "n0" and any routers in "N1". Nodes which are only reachable via 2232 "N1" routers with router priority values of NEVER are also 2233 excluded. 2234 4. For each interface "y" in "N1", initialize a set "N2(y)" to 2235 include any interfaces in "N2" that are 1-hop neighbors of "y". 2236 5. For each interface "x" in "N1" with a router priority value of 2237 "ALWAYS" (or using CF relay algorithm), select "x" as a MPR: 2238 A. Add "x" to the set "MPR" and remove "x" from "N1". 2239 B. For each interface "z" in "N2(x)", remove "z" from "N2" 2240 C. For each interface "y" in "N1", remove any interfaces in 2241 "N2(x)" from "N2(y)" 2242 6. For each interface "z" in "N2", initialize the set "N1(z)" to 2243 include any interfaces in "N1" that are 1-hop neighbors of "z". 2244 7. For each interface "x" in "N2" where "N1(x)" has only one member, 2245 select "x" as a MPR: 2246 A. Add "x" to the set "MPR" and remove "x" from "N1". 2247 B. For each interface "z" in "N2(x)", remove "z" from "N2" and 2248 delete "N1(z)" 2249 C. For each interface "y" in "N1", remove any interfaces in 2250 "N2(x)" from "N2(y)" 2251 8. While "N2" is not empty, select the interface "x" in "N1" with 2252 the largest router priority which has the number of members in 2253 "N_2(x)" as a MPR: 2254 A. Add "x" to the set "MPR" and remove "x" from "N1". 2255 B. For each interface "z" in "N2(x)", remove "z" from "N2" 2256 C. For each interface "y" in "N1", remove any interfaces in 2257 "N2(x)" from "N2(y)" 2259 After the set of routers "MPR" is selected, router "n_0" must signal 2260 its selections to its neighbors. With NHDP, this is done by using 2261 the MPR address block TLV to mark selected neighbor addresses in 2262 NHDP_HELLO messages. Neighbors MUST record their MPR selection 2263 status and the previous hop address (e.g., link or MAC layer) of the 2264 selector. Note these steps are re-evaluated upon neighborhood status 2265 changes. 2267 Appendix C. Multipoint Relay Connected Dominating Set (MPR-CDS) 2268 Algorithm 2270 The MPR-CDS algorithm is an extension to the basic S-MPR election 2271 algorithm that results in a shared (non source-specific) SMF CDS. 2272 Thus its forwarding rules are not dependent upon previous hop 2273 information similar to E-CDS. An overview of the MPR-CDS selection 2274 algorithm is provided in [MPR-CDS]. 2276 It is RECOMMENDED that the SMF_TYPE Message TLV be included in 2277 NHDP_HELLO messages that are generated by routers conducting MPR-CDS 2278 SMF operation. 2280 C.1. MPR-CDS Relay Set Selection Overview 2282 The MPR-CDS relay set selection process is based upon the MPR 2283 selection process of the S-MPR algorithm with the added refinement of 2284 a distributed technique for subsequently down-selecting to a common 2285 reduced, shared relay set. A router ordering (or "prioritization") 2286 metric is used as part of this down-selection process like the E-CDS 2287 algorithm, this metric can be based upon router address(es) or some 2288 other unique router identifier (e.g. "Router ID" based on largest 2289 address contained within the "Neighbor Address List") as well as an 2290 additional "Router Priority" measure, if desired. The process for 2291 MPR-CDS relay selection is as follows: 2292 1. First, MPR selection per the S-MPR algorithm is conducted, with 2293 selectors informing their MPRs (via NHDP) of their selection. 2294 2. Then, the following rules are used on a distributed basis by 2295 selected routers to possibly deselect themselves and thus jointly 2296 establish a common set of shared SMF relays: 2297 A. If a selected router has a larger "RtrPri()" than all of its 2298 1-hop symmetric neighbors, then it acts as a relay for all 2299 multicast traffic, regardless of the previous hop 2300 B. Else, if the 1-hop symmetric neighbor with the largest 2301 "RtrPri()" value has selected the router, then it also acts 2302 as a relay for all multicast traffic, regardless of the 2303 previous hop. 2304 C. Otherwise, it deselects itself as a relay and does not 2305 forward any traffic unless changes occur that require re- 2306 evaluation of the above steps. 2308 This technique shares many of the desirable properties of the E-CDS 2309 technique with regards to compatibility with multicast sources not 2310 participating in NHDP and the opportunity for statically-configure CF 2311 routers to be present, regardless of their participation in NHDP. 2313 C.2. MPR-CDS Forwarding Rules 2315 The forwarding rules for MPR-CDS are common with those of E-CDS. Any 2316 SMF router that has selected itself as a relay performs DPD and 2317 forwards all non-duplicative multicast traffic allowed by the present 2318 forwarding policy. Packet previous hop knowledge is not needed for 2319 forwarding decisions when using MPR-CDS. 2321 1. Upon packet reception, DPD is performed. Note MPR-CDS require 2322 one duplicate table for the set of interfaces associated with the 2323 relay set selection. 2324 2. If the packet is a duplicate, no further action is taken. 2325 3. If the packet is non-duplicative: 2326 A. A DPD entry is added for the packet identifier 2327 B. The packet is forwarded out all interfaces associated with 2328 the relay set selection 2330 As previously mentioned, even packets sourced (or relayed) by routers 2331 not participating in NHDP and/or the MPR-CDS relay set selection may 2332 be forwarded by MPR-CDS forwarders without problem. A particular 2333 deployment MAY choose to not forward packets from sources or relays 2334 that have been explicitly identified via NHDP or other means as 2335 operating as part of a different relay set algorithm (e.g. S-MPR) to 2336 allow coexistent deployments to operate correctly. 2338 C.3. MPR-CDS Neighborhood Discovery Requirements 2340 The neighborhood discovery requirements for MPR-CDS have commonality 2341 with both the S-MPR and E-CDS algorithms. MPR-CDS selection 2342 operation requires 2-hop neighbor knowledge as provided by NHDP 2343 [RFC6130] or from external sources. Unlike S-MPR operation, there is 2344 no need for associating link-layer address information with 1-hop 2345 neighbors since MPR-CDS forwarding is independent of the previous hop 2346 similar to E-CDS forwarding. 2348 To advertise an optional "Router Priority" value or "WILLINGNESS" an 2349 originating router may use the Message TLV of type SMF_TYPE:MPR-CDS 2350 which shares a common format with both SMF_TYPE:E-CDS 2351 Table 14 and SMF_TYPE:S-MPR Table 16. 2353 MPR-CDS only requires 1-hop knowledge of "Router Priority" for 2354 correct operation. In the S-MPR phase of MPR-CDS selection, MPRs are 2355 dynamically determined by each router and selections MUST be 2356 advertised and dynamically updated using NHDP or an equivalent 2357 protocol or mechanism. The field of the SMF_NBR_TYPE:MPR-CDS 2358 type TLV shares a common format with SMF_NBR_TYPE:S-MPR Table 17 to 2359 convey MPR selection. 2361 C.4. MPR-CDS Selection Algorithm 2363 This section describes an algorithm for the MPR-CDS selection 2364 process. Note that the selection described is with respect to a 2365 specific interface of the router performing selection and other 2366 router interfaces referenced are reachable from this reference router 2367 interface. An ordered tuple of "Router Priority" and "Router ID" is 2368 used in MPR-CDS relay set selection. The "Router ID" value should be 2369 set to the largest advertised address of a given router, this 2370 information is provided to one hop neighbors via NHDP by default. 2371 Precedence is given to the "Router Priority" portion and the "Router 2372 ID" value is used as a tie-breaker. The evaluation of this tuple is 2373 referred to as "RtrPri(n)" in the description below where "n" 2374 references a specific router. Note it is possible that the "Router 2375 Priority" portion may be optional and the evaluation of "RtrPri()" be 2376 solely based upon the unique "Router ID". Since there MUST NOT be 2377 any duplicate address values among SMF routers, a comparison of 2378 RtrPri(n) between any two routers will always be an inequality. The 2379 following steps, repeated upon any changes detected within the 1-hop 2380 and 2-hop neighborhood, describe a basic algorithm for conducting 2381 MPR-CDS selection for a router interface "n0": 2383 1. Perform steps 1-8 of Appendix B.4 to select MPRs from the set of 2384 1-hop neighbors of "n0" and notify/update neighbors of 2385 selections. 2386 2. Upon being selected as an MPR (or any change in the set of 2387 routers selecting "n0" as an MPR): 2388 A. If no neighbors have selected "n0" as an MPR, "n0" does not 2389 act as a relay and no further steps are taken until a change 2390 in neighborhood topology or selection status occurs. 2391 B. Determine the router "n1_max" that has the maximum "RtrPri()" 2392 of all 1-hop neighbors. 2393 C. If "RtrPri(n0)" is greater than "RtrPri(n1_max)", then "n0" 2394 selects itself as a relay for all multicast packets, 2395 D. Else, if "n1_max" has selected "n0" as an MPR, then "0" 2396 selects itself as a relay for all multicast packets. 2397 E. Otherwise, "n0" does not act as a relay. 2399 It is possible to extend this algorithm to consider neighboring SMF 2400 routers that are known to be statically configured for CF (always 2401 relaying). The modification to the above algorithm is to process 2402 such routers as having a maximum possible "Router Priority" value. 2403 This is the same as the case for participating routers that have been 2404 configured with a S-MPR "WILLINGNESS" value of "WILL_ALWAYS". It is 2405 expected that routers configured for CF and participating in NHDP 2406 would indicate their status with use of the SMF_TYPE TLV type in 2407 their NHDP_HELLO message TLV block. It is important to note however 2408 that CF routers will not select MPR routers and therefore cannot 2409 guarantee connectedness. 2411 Author's Address 2413 Joseph Macker 2414 NRL 2415 Washington, DC 20375 2416 USA 2418 Email: macker@itd.nrl.navy.mil