idnits 2.17.1 draft-ietf-manet-smf-07.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 16. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 2271. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 2282. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 2289. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 2295. 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 Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (February 25, 2008) is 5905 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 1528 -- Looks like a reference, but probably isn't: '7' on line 1459 -- Looks like a reference, but probably isn't: '127' on line 1528 -- Looks like a reference, but probably isn't: '128' on line 1530 -- Looks like a reference, but probably isn't: '239' on line 1530 -- Looks like a reference, but probably isn't: '240' on line 1532 -- Looks like a reference, but probably isn't: '255' on line 1532 == Unused Reference: 'GJ79' is defined on line 1647, but no explicit reference was found in the text == Unused Reference: 'WC02' is defined on line 1692, but no explicit reference was found in the text == Outdated reference: A later version (-15) exists of draft-ietf-manet-nhdp-05 == Outdated reference: A later version (-19) exists of draft-ietf-manet-olsrv2-04 == Outdated reference: A later version (-17) exists of draft-ietf-manet-packetbb-11 ** Obsolete normative reference: RFC 2434 (Obsoleted by RFC 5226) ** Obsolete normative reference: RFC 2460 (Obsoleted by RFC 8200) -- Obsolete informational reference (is this intentional?): RFC 4601 (Obsoleted by RFC 7761) Summary: 3 errors (**), 0 flaws (~~), 6 warnings (==), 15 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 SMF Design Team 5 Expires: August 28, 2008 IETF MANET WG 6 February 25, 2008 8 Simplified Multicast Forwarding for MANET 9 draft-ietf-manet-smf-07 11 Status of this Memo 13 By submitting this Internet-Draft, each author represents that any 14 applicable patent or other IPR claims of which he or she is aware 15 have been or will be disclosed, and any of which he or she becomes 16 aware will be disclosed, in accordance with Section 6 of BCP 79. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet-Drafts as reference 26 material or to cite them other than as "work in progress." 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt. 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 This Internet-Draft will expire on August 28, 2008. 36 Copyright Notice 38 Copyright (C) The IETF Trust (2008). 40 Abstract 42 This document describes a Simplified Multicast Forwarding (SMF) 43 mechanism that provides basic IP multicast forwarding suitable for 44 wireless mesh and mobile ad hoc network (MANET) use. SMF specifies 45 techniques for multicast duplicate packet detection (DPD) to assist 46 the forwarding process. SMF also specifies DPD maintenance and 47 checking operations for with both IPv4 and IPv6. SMF takes advantage 48 of reduced relay sets for efficient MANET multicast data distribution 49 within a mesh topology. The document describes interactions with 50 other protocols and multiple deployment approaches. Algorithms for 51 selecting reduced relay sets and related discussion are provided in 52 the Appendices. Basic issues relating to the operation of multicast 53 MANET border routers are discussed but ongoing work remains in this 54 area beyond the scope of this document. 56 Table of Contents 58 1. Requirements Notation . . . . . . . . . . . . . . . . . . . . 4 59 2. Introduction and Scope . . . . . . . . . . . . . . . . . . . . 5 60 2.1. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 7 61 3. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 9 62 4. SMF Packet Processing and Forwarding . . . . . . . . . . . . . 10 63 5. SMF Duplicate Packet Detection . . . . . . . . . . . . . . . . 13 64 5.1. IPv6 Duplicate Packet Detection . . . . . . . . . . . . . 14 65 5.1.1. IPv6 SMF-DPD Header Option . . . . . . . . . . . . . . 14 66 5.1.2. IPv6 Identification-based DPD . . . . . . . . . . . . 16 67 5.1.3. IPv6 Hash-based DPD . . . . . . . . . . . . . . . . . 18 68 5.2. IPv4 Duplicate Packet Detection . . . . . . . . . . . . . 19 69 5.2.1. IPv4 Identification-based DPD . . . . . . . . . . . . 20 70 5.2.2. IPv4 Hash-based DPD . . . . . . . . . . . . . . . . . 21 71 5.3. Internal Hash Computation Considerations . . . . . . . . . 22 72 6. Reduced Relay Set Forwarding and Relay Selection Capability . 23 73 7. SMF Neighborhood Discovery Requirements . . . . . . . . . . . 26 74 7.1. SMF Relay Algorithm TLV Types . . . . . . . . . . . . . . 27 75 7.1.1. Relay Algorithm Message TLV Type . . . . . . . . . . . 27 76 7.1.2. Relay Algorithm Address Block TLV Type . . . . . . . . 28 77 7.2. SMF Router Priority TLV Types . . . . . . . . . . . . . . 29 78 7.2.1. Router Priority Message TLV Type . . . . . . . . . . . 29 79 7.2.2. Router Priority Address Block TLV Type . . . . . . . . 29 80 8. SMF Border Gateway Considerations . . . . . . . . . . . . . . 31 81 8.1. Forwarded Multicast Groups . . . . . . . . . . . . . . . . 31 82 8.2. Multicast Group Scoping . . . . . . . . . . . . . . . . . 32 83 8.3. Interface with Exterior Multicast Routing Protocols . . . 33 84 8.4. Multiple Border Routers . . . . . . . . . . . . . . . . . 34 85 9. Non-SMF MANET Node Interaction . . . . . . . . . . . . . . . . 36 86 10. Security Considerations . . . . . . . . . . . . . . . . . . . 37 87 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 38 88 11.1. IPv6 SMF_DPD Header Extension . . . . . . . . . . . . . . 38 89 11.2. SMF NHDP TLV Types . . . . . . . . . . . . . . . . . . . . 38 90 12. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 41 91 13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 42 92 13.1. Normative References . . . . . . . . . . . . . . . . . . . 42 93 13.2. Informative References . . . . . . . . . . . . . . . . . . 43 94 Appendix A. Source-based Multipoint Relay (S-MPR) . . . . . . . . 45 95 A.1. S-MPR Relay Set Selection Overview . . . . . . . . . . . . 45 96 A.2. S-MPR Forwarding Rules . . . . . . . . . . . . . . . . . . 46 97 A.3. S-MPR Neighborhood Discovery Requirements . . . . . . . . 47 98 A.4. S-MPR Selection Algorithm . . . . . . . . . . . . . . . . 47 99 Appendix B. Essential Connecting Dominating Set (E-CDS) 100 Algorithm . . . . . . . . . . . . . . . . . . . . . . 50 101 B.1. E-CDS Relay Set Selection Overview . . . . . . . . . . . . 50 102 B.2. E-CDS Forwarding Rules . . . . . . . . . . . . . . . . . . 51 103 B.3. E-CDS Neighborhood Discovery Requirements . . . . . . . . 51 104 B.4. E-CDS Selection Algorithm . . . . . . . . . . . . . . . . 52 105 Appendix C. Multipoint Relay Connected Dominating Set 106 (MPR-CDS) Algorithm . . . . . . . . . . . . . . . . . 54 107 C.1. MPR-CDS Relay Set Selection Overview . . . . . . . . . . . 54 108 C.2. MPR-CDS Forwarding Rules . . . . . . . . . . . . . . . . . 55 109 C.3. MPR-CDS Neighborhood Discovery Requirements . . . . . . . 55 110 C.4. MPR-CDS Selection Algorithm . . . . . . . . . . . . . . . 56 111 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 58 112 Intellectual Property and Copyright Statements . . . . . . . . . . 59 114 1. Requirements Notation 116 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 117 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 118 document are to be interpreted as described in [RFC2119]. 120 2. Introduction and Scope 122 MANET unicast routing protocol designs have demonstrated effective 123 and efficient mechanisms to flood routing control plane messages 124 throughout a wireless routing area. For example, algorithms 125 specified within [RFC3626] and [RFC3684] provide distributed methods 126 of dynamically electing reduced relay sets that attempt to optimize 127 flooding of routing control messages amongst MANET routing peers. 128 Simplified Multicast Forwarding (SMF) extends this efficient flooding 129 concept to the data forwarding plane for IP multicast packets. When 130 localized, efficient flooding is deemed an effective technique, SMF 131 provides an appropriate multicast forwarding capability. The SMF 132 baseline design is intended to provide a basic, best effort multicast 133 forwarding capability that is constrained to operate within a MANET 134 or wireless mesh routing region. The main design goals of this SMF 135 specification are to adapt efficient relay sets in MANET environments 136 [RFC2901] and define the needed IPv4 and IPv6 multicast duplicate 137 packet detection (DPD) mechanisms to support multi-hop, packet 138 forwarding. Figure 1 provides an overview of the logical SMF node 139 architecture, consisting of "Neighborhood Discovery", "Relay Set 140 Selection" and "Forwarding Process" components. Typically, relay set 141 selection (or self-election) will occur based on input from a 142 neighborhood discovery process, and the forwarding process will often 143 be determined by dynamic relay set selection. Note the neighborhood 144 discovery and/or relay set selection information MAY be obtained from 145 a coexistent process (e.g., MANET unicast routing protocol using 146 relay sets). In some cases, the forwarding decision for a packet can 147 also depend on previous hop or incoming interface information. The 148 asterisks (*) in Figure 1 mark the primitives and relationships 149 needed by relay set algorithms requiring previous-hop packet 150 forwarding knowledge. 152 ______________ _____________ 153 | | | | 154 | Neighborhood | | Relay Set | 155 | Discovery |------------->| Selection | 156 | Protocol | neighbor | Algorithm | 157 |______________| info |_____________| 158 \ / 159 \ / 160 neighbor\ /forwarding 161 info* \ ____________ / status 162 \ | | / 163 `-->| Forwarding |<--' 164 | Process | 165 ~~~~~~~~~~~~~~~~~>|____________|~~~~~~~~~~~~~~~~~> 166 incoming packet, forwarded packets 167 interface id, and 168 previous hop* 170 Figure 1: SMF Node Architecture 172 Interoperable SMF implementations MUST use a common DPD approach and 173 be able to process the header options defined in this document for 174 IPv6 operation. We define Classical Flooding (CF), as the simplest 175 case of SMF multicast forwarding. With CF, each SMF router forwards 176 each received forwardable multicast packet once. In this case, the 177 need for any relay set selection or neighborhood topology information 178 is eliminated but DPD is still required. While SMF supports a CF 179 mode the use of more efficient relay set modes is RECOMMENDED to 180 reduce contention and congestion caused by unnecessary packet 181 retransmissions [NTSC99]. An efficient, reduced relay set is 182 realized by selecting and maintaining a _subset_ of all possible SMF 183 routers in a MANET routing region. Known relay set selection 184 algorithms have demonstrated the ability to provide and maintain a 185 dynamic distribution mesh for forwarding user multicast data [MDC04]. 186 A few such relay set selection algorithms are described in the 187 Appendices of this document and the basic designs borrow directly 188 from previous work. Additional relay set algorithms or extensions 189 may be specified for future used with SMF. 191 Dynamic neighborhood topology information is often needed to 192 determine and maintain an optimized set of relay (forwarding) nodes. 193 Neighborhood topology discovery functions MAY be externally provided 194 by a MANET unicast routing protocol or by using the MANET 195 NeighborHood Discovery Protocol (NHDP) [NHDP] running in concurrence 196 with SMF. Additionally, this specification does not preclude a lower 197 protocol layer from providing necessary neighborhood information. 198 Fundamentally, an SMF implementation SHOULD provide the ability for 199 multicast forwarding state to be dynamically managed per operating 200 network interface. Some of the relay state maintenance options and 201 interactions are outlined later in Section 6. This document states 202 specific requirements for neighborhood discovery with respect to the 203 forwarding process and the relay set selection algorithms described 204 herein. In the absence of a MANET unicast protocol or lower layer 205 information interface, SMF relies on the MANET NHDP specification to 206 assist in IP layer 2-hop neighborhood state discovery and maintenance 207 for relay set election in non-CF optimized modes. A "SMF_RELAY_ALG" 208 Message TLV type (per [PacketBB]) is defined for use with the NHDP 209 protocol. It is RECOMMENDED that all nodes performing SMF operation 210 include this TLV type in their NHDP_HELLO messages when operating 211 with NHDP. This capability allows for nodes participating in SMF to 212 be explicitly identified along with their respective CDS algorithm. 214 2.1. Abbreviations 216 The following abbreviations are used throughout this document: 218 +--------------+------------------------------------+ 219 | Abbreviation | : Definition | 220 +--------------+------------------------------------+ 221 | MANET | : Mobile Ad hoc Network | 222 | | | 223 | SMF | : Simplified Multicast Forwarding | 224 | | | 225 | CF | : Classical Flooding | 226 | | | 227 | CDS | : Connected Dominating Set | 228 | | | 229 | MCDS | : Minimum Connected Dominating Set | 230 | | | 231 | MPR | : Multi-Point Relay | 232 | | | 233 | S-MPR | : Source-based MPR | 234 | | | 235 | MPR-CDS | : MPR-based CDS | 236 | | | 237 | E-CDS | : Essential CDS | 238 | | | 239 | NHDP | : Neighborhood Discovery Protocol | 240 | | | 241 | DPD | : Duplicate Packet Detection | 242 | | | 243 | I-DPD | : Identification-based DPD | 244 | | | 245 | H-DPD | : Hash-based DPD | 246 | | | 247 | HAV | : Hash-assist Value | 248 | | | 249 | FIB | Forwarding Information Base | 250 | | | 251 | TLV | : type-length-value encoding | 252 +--------------+------------------------------------+ 254 3. Applicability 256 Within dynamic, wireless routing topologies, maintaining traditional 257 forwarding trees to support a multicast routing protocol is often not 258 as effective as in wired networks due the reduced reliability and 259 increased dynamics of the mesh topology [MGL04] and [GM99].__ A basic 260 packet forwarding service that reaches all MANET SMF routers 261 participating within a localized routing region may provide a useful 262 group communication paradigm for various classes of applications. 263 Applications that could take advantage of a simple multicast 264 forwarding service within a MANET routing region include multimedia 265 streaming, interactive group-based messaging and applications, peer- 266 to-peer middleware multicasting, and multi-hop mobile discovery or 267 registration services. 269 Note again that Figure 1 provides a notional architecture for 270 _typical_ MANET SMF-capable nodes. However, a goal is that simple 271 end-system (non-forwarding) wireless nodes may also participate in 272 multicast traffic transmission and reception with standard IP network 273 layer semantics (e.g., special or unnecessary encapsulation of IP 274 packets should be avoided in this case). A multicast border router 275 or proxy mechanism MUST be used when deployed alongside more fixed- 276 infrastructure IP multicast routing such Protocol Independent 277 Multicast (PIM) variants [RFC3973] and [RFC4601]. With present 278 experimental implementations, proxy methods have demonstrated gateway 279 functionality at MANET border routers operating with external IP 280 multicast routing protocols. SMF may be extended or combined with 281 other mechanisms to provide increased reliability and group specific 282 filtering, but the details for this are not discussed here. 284 4. SMF Packet Processing and Forwarding 286 The SMF Packet Processing and Forwarding actions are conducted with 287 the following packet handling activities: 289 1. Processing of outbound, locally-generated multicast packets. 291 2. Reception and processing of inbound packets on a specific network 292 interface(s). 294 The purpose of intercepting outbound, locally-generated multicast 295 packets is to apply any added packet marking needed to satisfy the 296 DPD requirements described later so that proper forwarding may be 297 conducted. Note that for some system configurations interception of 298 outbound packets for this purpose is not necessary. 300 Inbound multicast packets will be received by the SMF implementation 301 and processed for possible forwarding. This document does not 302 presently support forwarding of directed broadcast addresses 303 [RFC2644]. SMF implementations MUST be capable of forwarding "global 304 scope" multicast packets to support generic multicast application 305 needs or to distribute designated multicast traffic that ingresses 306 the MANET routing region via border routers. The multicast addresses 307 to be forwarded will be maintained by an _a priori_ list or a dynamic 308 forwarding information base (FIB) that MAY interact with future MANET 309 dynamic group membership extensions. There will also be well-known 310 multicast group for flooding to all SMF forwarders. This multicast 311 group is specified to contain all MANET SMF routers of a connected 312 MANET routing region, so that packets transmitted to the multicast 313 address associated with the group will be delivered to all connected 314 SMF routers. For IPv6, the multicast address is specified to be 315 "site-local". The name of the multicast group is "SL-MANET-ROUTERS". 316 Minimally SMF SHALL forward, as instructed by the relay set selection 317 algorithm, unique (non-duplicate) packets received for this well- 318 known group address when the TTL or hop count value in the IP header 319 is greater than 1. SMF SHALL forward all additional global scope 320 addresses specified within the FIB as well. In all cases, the 321 following rules SHALL be observed for SMF multicast forwarding: 323 1. Multicast packets with TTL <= 1 MUST NOT be forwarded. 325 2. Link local multicast packets MUST NOT be forwarded. 327 3. Incoming multicast packets with an IP source address matching one 328 of those of the local SMF router interface(s) MUST NOT be 329 forwarded. 331 4. Received packet frames with the MAC source address matching the 332 local SMF router interface(s) MUST NOT be forwarded. 334 5. Received packets for which SMF cannot reasonably ensure temporal 335 DPD uniqueness MUST NOT be forwarded. 337 6. When packets are forwarded, TTL or hop limit SHALL be decremented 338 by one. 340 Note that rule #3 is important because in wireless networks, the 341 local SMF router may receive re-transmissions of its own packets when 342 they are forwarded by neighboring nodes. This rule avoids 343 unnecessary retransmission of locally-generated packets even when 344 other forwarding decision rules would apply. 346 An additional processing rule also needs to be considered based upon 347 a potential security threat. As discussed further in Section 10, 348 there may be concern in some SMF deployments that malicious nodes may 349 conduct a denial-of-service attack by remotely "previewing" (e.g., 350 via a directional receive antenna) packets that an SMF node would be 351 forwarding and conduct a "pre-play" attack by transmitting the packet 352 before the SMF node would otherwise receive it but with a reduced TTL 353 (or Hop Limit) field value. This form of attack could cause an SMF 354 node to create a DPD entry that would block the proper forwarding of 355 the valid packet (with correct TTL) through the SMF area. A 356 RECOMMENDED approach to prevent this attack, when it is a concern, 357 would be to cache temporal packet TTL values along with the DPD state 358 (hash value(s) and/or identifier). Then, if a subsequent matching 359 (with respect to DPD) packet arrives with a _larger_ TTL value than 360 the packet that was previously forwarded, then SMF should forward the 361 new packet _and_ update the TTL cached with corresponding DPD state 362 to the new, larger TTL value. There may be temporal cases where SMF 363 may unnecessarily forward some duplicate packets using this approach, 364 but those cases are expected to be minimal and acceptable when 365 compared with the potential threat outcome of denied service. 367 Once these criteria have been met, an SMF implementation MUST make a 368 forwarding decision dependent upon the relay set selection algorithm 369 in use. If the SMF implementation is using Classical Flooding (CF), 370 the forwarding decision is implicit once DPD uniqueness is 371 determined. Otherwise, a forwarding decision depends upon the 372 current interface-specific relay set state. The descriptions of the 373 relay set selection algorithms in the Appendices to this document 374 specify the respective heuristics for multicast packet forwarding and 375 specific DPD or other processing required to achieve correct SMF 376 behavior. For example, one class of forwarding is based upon relay 377 set election status _and_ the packet's previous hop (e.g. S-MPR 378 forwarding), while other classes designate the local SMF router as a 379 forwarder of all neighbor packets based on the neighborhood topology 380 (e.g. E-CDS and MPR-CDS). 382 5. SMF Duplicate Packet Detection 384 Duplicate packet detection (DPD) is a common requirement in MANET 385 packet forwarding because packets may be transmitted out the same 386 physical interface upon which they arrived and nodes may also receive 387 copies of previously-transmitted packets from other forwarding 388 neighbors. SMF implementations MUST detect and avoid forwarding 389 duplicate multicast packets using temporal packet identification. It 390 is RECOMMENDED this be implemented by keeping a history of recently- 391 processed multicast packets for comparison to incoming packets. For 392 both IPv4 and IPv6, this document describes two basic approaches to 393 multicast duplicate packet detection: header content identification- 394 based (I-DPD) and hash-based (H-DPD) duplicate detection. The two 395 approaches are described for experimental purposes. Trade-offs of 396 the two approaches to DPD may merit different consideration depending 397 upon specific SMF deployment scenarios. Because of the potential 398 addition of a hop-by-hop option header with IPv6, SMF deployments 399 MUST be configured to use a common mechanism and DPD algorithm. The 400 main difference between IPv4 and IPv6 SMF DPD specification is the 401 avoidance of any additional header options in the IPv4 case. 403 For each network interface, SMF implementations MUST maintain DPD 404 packet state as needed to support the forwarding heuristics of the 405 relay set algorithm used. The specific requirements of several relay 406 set selection algorithms and their forwarding rules are described in 407 the Appendices of this document. In general this involves keeping 408 track of previously forwarded packets so that duplicates are not 409 forwarded, but some relay techniques (e.g., S-MPR) have additional 410 considerations. 412 For I-DPD, packets are identified using explicit identifiers from the 413 IP header. The specific identifier to use depends upon the IP 414 protocol version and the type of packet. For example, IPv4 [RFC0791] 415 provides an "Identification" field that can assist a DPD mechanism, 416 and packets that contain IPSec protocol headers also provide suitable 417 packet identifiers. Fragmented packets also provide additional 418 identifiers that need to be considered. These identifier fields are 419 unique within the context of source address, destination address, 420 protocol type, and/or other header fields depending upon the type of 421 identifier used for DPD. Similarly, for H-DPD, it is expected that 422 packet hash values will be kept with respect to at least the source 423 address to help ensure hash collision avoidance. SMF implementations 424 MUST maintain DPD history per the applicable packet flow context 425 (e.g., for DPD based upon IPv4 ID). The 426 details for I-DPD and H-DPD for different types of packets are 427 described in the sections below. In either case, this history SHOULD 428 be kept long enough to span the maximum network traversal lifetime, 429 MAX_PACKET_LIFETIME, of multicast packets being forwarded within an 430 SMF operating area. The required size of the DPD cache is governed 431 by this timeout value and is also a function of the packet forwarding 432 rates. The DPD mechanism SHOULD avoid keeping unnecessary state for 433 packet flows such as those that are locally-generated or link-local 434 destinations that would not be considered for forwarding. 436 5.1. IPv6 Duplicate Packet Detection 438 This section describes the mechanisms and options for SMF IPv6 DPD. 439 The core IPv6 packet header does not provide any explicit 440 identification header field that can be exploited for I-DPD. The 441 following areas are described to support IPv6 DPD: 443 1. a hop-by-hop SMF-DPD option header (with supporting identifier or 444 hash assistance value), 446 2. the use of IPv6 fragment header fields for I-DPD when they exist, 448 3. the use of IPSec sequencing for I-DPD when a non-fragmented, 449 IPSec header is detected, and 451 4. an H-DPD approach assisted, as needed, by the SMF-DPD option 452 header. 454 SMF MUST provide a DPD marking module that can insert the hop-by-hop 455 IPv6 header option defined in this section. This process MUST come 456 after any source-based fragmentation that may occur with IPv6. As 457 with IPv4, SMF IPv6 DPD is presently specified to allow either a 458 packet hash or header identification method for DPD. An SMF 459 implementation MUST be configured to operate either in H-DPD or I-DPD 460 mode and perform the appropriate routines outlined in the following 461 sections. 463 5.1.1. IPv6 SMF-DPD Header Option 465 As previously mentioned, the base IPv6 packet header does not contain 466 a unique identifier suitable for DPD. This section defines an IPv6 467 Hop-by-Hop Option to serve this purpose for IPv6 I-DPD. 468 Additionally, the Option defined provides for a mechanism to 469 guarantee non-collision of hash values for different packets when 470 H-DPD is used. The value of the IPv6 SMF_DPD Hop-by-Hop Option Type 471 is TBD. 473 The first bit of the data field of the SMF-DPD option is the "H-bit" 474 that determines the format of the Option Data content. Two different 475 formats are supported. When the "H-bit" is cleared (zero value), the 476 SMF-DPD format to support I-DPD operation is specified as shown in 477 Figure 2 and defines the extension header in accordance with 479 [RFC2460]. 480 0 1 2 3 481 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 482 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 483 ... |0|0|0| OptType | Opt. Data Len | 484 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 485 |0|TidTyp|TidLen| TaggerId (optional) ... | 486 +-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 487 | | Identifier ... 488 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 490 Figure 2: IPv6 SMF-DPD Header Option in I-DPD mode 492 The "TidType" is a 3-bit field indicating the presence and type of 493 the optional "TaggerId" field. The optional "TaggerId" is used to 494 differentiate multiple ingressing border gateways that may commonly 495 apply the SMF-DPD option header to packets from a particular source. 496 This is provided for experimental purposes. The following table 497 lists the valid TaggerId types: 499 +---------+-------+-------------------------------------------------+ 500 | Name | Value | Purpose | 501 +---------+-------+-------------------------------------------------+ 502 | NULL | 0 | Indicates no "taggerId" field is present. | 503 | | | "TidLen" MUST also be set to ZERO. | 504 | | | | 505 | DEFAULT | 1 | A "TaggerId" of non-specific context is | 506 | | | present. "TidLen + 1" defines the length of | 507 | | | the TaggerId field in bytes. | 508 | | | | 509 | IPv4 | 2 | A "TaggerId" representing an IPv4 address is | 510 | | | present. The "TidLen" MUST be set to 3. | 511 | | | | 512 | IPv6 | 3 | A "TaggerId" representing an IPv6 address is | 513 | | | present. The "TidLen" MUST be set to 15. | 514 | | | | 515 | ExtId | 7 | RESERVED FOR FUTURE USE (possible extended ID) | 516 +---------+-------+-------------------------------------------------+ 518 This format allows a quick check of the "TidType" field to determine 519 if a "TaggerId" field is present. If the is NULL, then the 520 length of the DPD packet field corresponds to the ( - 1). If the is non-NULL, then the length of the 522 "TaggerId" field is equal to ( - 1) and the remainder of the 523 option data comprises the DPD packet field. When the 524 "TaggerId" field is present, the field can be considered 525 a unique packet identifier in the context of the tuple. When the "TaggerId" field is not present, then it is 527 assumed the source host applied the SMF-DPD option and the 528 can be considered unique in the context of the IPv6 529 packet header tuple. IPV6 I-DPD operation details 530 are described in Section 5.1.2. 532 When the "H-bit" in the SMF-DPD option data is set, the data content 533 value is interpreted as a Hash-Assist Value (HAV) used to facilitate 534 H-DPD operation. In this case, source hosts or ingressing gateways 535 apply the SMF-DPD with a HAV only when required to differentiate the 536 hash value of a new packet with respect to older packets in the 537 current DPD history cache. This helps to guarantee the uniqueness of 538 generated hash values when H-DPD is used. Additionally, this also 539 avoids the added overhead of applying the SMF-DPD option header to 540 every packet. For many hash algorithms, it is expected that only 541 sparse use of the SMF-DPD option may be required. The format of the 542 SMF-DPD header option for H-DPD operation is given in Figure 3. 543 0 1 2 3 544 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 545 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 546 ... |0|0|0| OptType | Opt. Data Len | 547 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 548 |0| Hash Assist Value (HAV) ... 549 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 551 Figure 3: IPv6 SMF_DPD Header Option in H-DPD Mode 553 The SMF-DPD option should be applied with a HAV to produce a unique 554 hash digest for packets within the context of the IPv6 packet header 555 . The size of the HAV field is implied by the "Opt. Data 556 Len". The appropriate size of the field depends upon the collision 557 properties of the specific hash algorithm used. More details on IPv6 558 H-DPD operation are provided in Section 5.1.3. 560 5.1.2. IPv6 Identification-based DPD 562 The following table summarizes the IPv6 I-DPD processing approach. 563 Within the table '*' indicates a don't care condition. 565 IPv6 I-DPD Processing Rules 567 +-------------+-----------+-----------+-----------------------------+ 568 | IPv6 | IPv6 | IPv6 | SMF IPv6 I-DPD Mode Action | 569 | Fragment | IPSec | I-DPD | | 570 | Header | Header | Header | | 571 +-------------+-----------+-----------+-----------------------------+ 572 | Present | * | * | Use Fragment Header I-DPD | 573 | | | | Check and Process for | 574 | | | | Forwarding | 575 | | | | | 576 | Not Present | Present | * | Use IPSec Header I-DPD | 577 | | | | Check and Process for | 578 | | | | Forwarding | 579 | | | | | 580 | Present | * | Present | Invalid, do not Forward | 581 | | | | | 582 | Not Present | Present | Present | Invalid, do not Forward | 583 | | | | | 584 | Not Present | Not | Not | Add I-DPD Header,and | 585 | | Present | Present | Process for Forwarding | 586 | | | | | 587 | Not Present | Not | Present | Use I-DPD Header Check and | 588 | | Present | | Process for Forwarding | 589 +-------------+-----------+-----------+-----------------------------+ 591 If the IPv6 multicast packet is an IPv6 fragment, SMF MUST use the 592 fragment extension header fields for packet identification. This 593 identifier can be considered unique in the context of the of the IP packet. If the packet is an unfragmented IPv6 595 IPSec packet, SMF MUST use IPSec fields for packet identification. 596 The IPSec header field can be considered a unique 597 identifier in the context of the 598 where the "IPSecType" is either AH or ESP. For unfragmented, non- 599 IPSec, IPv6 packets, the use of the SMF DPD header option is 600 necessary to support I-DPD operation. The SMF DPD header option is 601 applied in the context of the of the IP packet. End 602 systems or ingressing SMF gateways are responsible for applying this 603 option to support DPD. The following table summarizes these packet 604 identification types: 606 *IPv6 I-DPD Packet Identification Types* 608 +-----------+---------------------------------+---------------------+ 609 | IPv6 | Packet DPD ID Context | Packet DPD ID | 610 | Packet | | | 611 | Type | | | 612 +-----------+---------------------------------+---------------------+ 613 | Fragment | | | 614 | | | | 615 | IPSec | | | 616 | Packet | | | 617 | | | | 618 | Regular | <[taggerId:]srcAddr:dstAddr> | | 620 +-----------+---------------------------------+---------------------+ 622 "IPSecType" is either Authentication Header (AH) or Encapsulating 623 Security Payload (ESP). 625 The "taggerId" is an optional feature of the IPv6 SMF-DPD header 626 option. 628 5.1.3. IPv6 Hash-based DPD 630 A default hash-based DPD approach (H-DPD) for use by SMF is specified 631 as follows. An MD5 [RFC1321] hash of the non-mutable header fields, 632 options fields, and data content of the IPv6 multicast packet is used 633 to produce a 128-bit digest. The lower 64 bits of this digest 634 (MD5_64) is used for SMF packet identification. The approach for 635 calculating this hash value SHOULD follow the same guidelines 636 described for calculating the Integrity Check Value (ICV) described 637 in [RFC4302] with respect to non-mutable fields. This approach 638 should have a reasonably low probability of digest collision when 639 packet headers and content are varying. MD5 is being applied in SMF 640 only to provide a low probability of collision and is not being used 641 for cryptographic or authentication purposes. A history of the 642 packet hash values SHOULD be maintained within the context of the 643 IPv6 packet header . This history is used by forwarding SMF 644 nodes (non-ingress points) to avoid forwarding duplicates. SMF 645 ingress points (i.e., source hosts or gateways) use this history to 646 confirm that new packets are unique with respect to their hash value. 647 The Hash-assist Value (HAV) field described in Section 5.1.1 is 648 provided as a differentiating field when a digest collision would 649 otherwise occur. Note that the HAV is an immutable option field and 650 SMF MUST use any included H-DPD hash assist value (HAV) option header 651 (see Section 5.1.1) in its hash calculation. 653 If a packet results in a digest collision (i.e., by checking the 654 H-DPD digest history) within the limited history kept by SMF 655 forwarders, the packet should be silently dropped. If a digest 656 collision is detected at an SMF ingress point (i.e., including SMF- 657 aware sources), the H-DPD option header is applied with a HAV. The 658 packet is retested for collision and the HAV is re-applied as needed 659 to produce a non-colliding hash value. The multicast packet is then 660 forwarded with the added IPv6 SMF-DPD header option. 662 The MD5 indexing and IPv6 HAV approaches are specified at present for 663 consistency and robustness to suit experimental uses. Future 664 approaches and experimentation may discover designs tradeoffs in hash 665 robustness and efficiency worth considering. This MAY include 666 reducing the maximum payload length that is processed, determining 667 shorter indexes, or applying more efficient hashing algorithms. Use 668 of the HAV functionality may allow for application of "lighter- 669 weight" hashing techniques that might not have been initially 670 considered due to poor collision properties otherwise. Such 671 techniques could reduce packet processing overhead and memory 672 requirements. 674 5.2. IPv4 Duplicate Packet Detection 676 This section describes the mechanisms and options for IPv4 DPD. The 677 IPv4 packet header 16-bit "Identification" field MAY be used for DPD 678 assistance, but practical limitations may require alternative 679 approaches in some situations. The following areas are described to 680 support IPv4 DPD:: 682 1. the use of IPv4 fragment header fields for I-DPD when they exist, 684 2. the use of IPSec sequencing for I-DPD when a non-fragmented IPv4 685 IPSec packet is detected, and 687 3. a H-DPD approach. 689 A specific SMF-DPD marking option is not specified for IPv4 since 690 header options are not as tractable for end systems as for IPv6. 691 IPv4 packets from a particular source are assumed to be marked with a 692 temporally unique value in the "Identification" field of the packet 693 header that can serve for SMF DPD purposes. However, in present 694 operating system networking kernels, the IPv4 header "Identification" 695 value is not always generated properly, especially when the "don't 696 fragment" (DF) bit is set. The IPv4 I-DPD mode of this specification 697 requires that IPv4 "Identification" fields are managed reasonably by 698 source hosts and that temporally unique values are set within the 699 context of the packet header tuple. If 700 this is not expected during an SMF deployment, then it is RECOMMENDED 701 that the H-DPD method be used as a more reliable approach. 703 Since IPv4 SMF does not specify an options header, the 704 interoperability constraints are looser than the IPv6 version and 705 forwarders may be operate with mixed H-DPD and I-DPD modes as long as 706 they consistently perform the appropriate DPD routines outlined in 707 the following sections. However, it is RECOMMENDED that a deployment 708 be configured with a common mode for operational consistency. 710 5.2.1. IPv4 Identification-based DPD 712 The following table summarizes the IPv4 I-DPD processing approach 713 once a packet has passed the basic forwardable criteria described in 714 earlier SMF sections. Within the table '*' indicates a don't care 715 condition. 717 +----+----+----------+---------+------------------------------------+ 718 | df | mf | fragment | IPSec | IPv4 I-DPD Action | 719 | | | offset | | | 720 +----+----+----------+---------+------------------------------------+ 721 | 1 | 1 | * | * | Invalid, Do Not Forward | 722 | | | | | | 723 | 1 | 0 | nonzero | * | Invalid, Do Not Forward | 724 | | | | | | 725 | * | 0 | zero | not | Tuple I-DPD Check and Process for | 726 | | | | Present | Forwarding | 727 | | | | | | 728 | * | 0 | zero | Present | IPSec enhanced Tuple I-DPD Check | 729 | | | | | and Process for Forwarding | 730 | | | | | | 731 | 0 | 0 | nonzero | * | Extended Fragment Offset Tuple | 732 | | | | | I-DPD Check and Process for | 733 | | | | | Forwarding | 734 | | | | | | 735 | 0 | 1 | zero or | * | Extended Fragment Offset Tuple | 736 | | | nonzero | | I-DPD Check and Process for | 737 | | | | | Forwarding | 738 +----+----+----------+---------+------------------------------------+ 740 For performance reasons, IPv4 network fragmentation and reassembly of 741 multicast packets within wireless MANET networks should be minimized, 742 yet SMF provides the forwarding of fragments when they occur. If the 743 IPv4 multicast packet is a fragment, SMF MUST use the fragmentation 744 header fields for packet identification. This identification can be 745 considered temporally unique in the context of the of the IPv4 packet. If the packet is an unfragmented IPv4 747 IPSec packet, SMF MUST use IPSec fields for packet identification. 748 The IPSec header field can be considered a unique 749 identifier in the context of the 750 where the "IPSecType" is either AH or ESP. Finally, for 751 unfragmented, non-IPSec, IPv4 packets, the "Identification" field can 752 be used for I-DPD purposes. The "Identification" field can be 753 considered unique in the context of the IPv4 tuple. The following table summarizes these packet 755 identification types: 757 *IPv4 I-DPD Packet Identification Types* 759 +-----------+---------------------------------+---------------------+ 760 | IPv4 | Packet Identification Context | Packet Identifier | 761 | Packet | | | 762 | Type | | | 763 +-----------+---------------------------------+---------------------+ 764 | Fragment | | | 765 | | | | 766 | IPSec | | | 767 | Packet | | | 768 | | | | 769 | Regular | | | 770 | Packet | | | 771 +-----------+---------------------------------+---------------------+ 773 "IPSecType" is either Authentication Header (AH) or Encapsulating 774 Security Payload (ESP). 776 The limited size (16 bits) of the IPv4 header "Identification" field 777 may result in the value rapidly wrapping, particularly if a common 778 sequence space is used by a source for multiple destinations. If 779 I-DPD operation is required, the use of the "internal hashing" 780 technique described in Section 5.3 may mitigate this limitation of 781 the IPv4 "Identification" field for SMF DPD. In this case the 782 "internal hash" value would be concatenated with the "Identification" 783 value for I-DPD operation. 785 5.2.2. IPv4 Hash-based DPD 787 To ensure consistent IPv4 H-DPD operation among SMF nodes, a default 788 hashing approach is specified. This is similar to that specified for 789 IPv6, but the H-DPD header option with HAV is not considered. SMF 790 MUST perform an MD5 [RFC1321] hash of the immutable header fields, 791 option fields and data content of the IPv4 multicast packet resulting 792 in a 128-bit digest. The lower 64 bits of this digest (MD5_64) is 793 used for SMF packet identification. The approach for calculating the 794 hash value SHOULD follow the same guidelines described for 795 calculating the Integrity Check Value (ICV) described in [RFC4302] 796 with respect to non-mutable fields. A history of the packet hash 797 values SHOULD be maintained in the context of . The context for IPv4 is more specific than that of IPv6 799 since the SMF-DPD HAV cannot be employed to mitigate hash collisions. 801 The MD5 hash is specified at present for consistency and robustness. 802 Future approaches and experimentation may discover designs tradeoffs 803 in hash robustness and efficiency worth considering for future 804 versions of SMF. This MAY include reducing the packet payload length 805 that is processed, determining shorter indexes, or applying a more 806 efficient hashing algorithm. 808 5.3. Internal Hash Computation Considerations 810 Forwarding protocols that use DPD techniques, such as SMF, may be 811 vulnerable to denial-of-service (DoS) attacks based on spoofing 812 packets with apparently valid packet identifier fields. Such a 813 consideration is pointed out in Section 10. In wireless environments 814 where SMF will most likely be used, the opportunity for badly- 815 behaving nodes to conduct such attacks is more prevalent than in 816 wired networks. In the case of IPv4 packets, fragmented IP packets 817 or packets with IPSec headers applied, the DPD "identifier" of 818 potential future packets that might be forwarded is very predictable 819 and easily subject to denial-of-service attacks against forwarding. 820 A RECOMMENDED technique to counter this concern is for SMF 821 implementations to generate an "internal" hash value that is 822 concatenated with the explicit I-DPD packet identifier to form a 823 unique identifier that is a function of the packet content as well as 824 the visible identifier. SMF implementations could seed their hash 825 generation with a random value to make it unlikely that an external 826 observer could guess how to spoof packets used in a denial-of-service 827 attack against forwarding. Since the hash computation and state is 828 kept completely internal to SMF nodes, the cryptographic properties 829 of this hashing would not need to be extensive and thus possibly of 830 low complexity. Experimental implementations may determine that a 831 lightweight hash of even only portions of packets may suffice to 832 serve this purpose. 834 For IPv4 I-DPD based on the limited 16-bit IP header "Identification" 835 field, it is possible that use of this "internal hash" technique may 836 also enhance I-DPD performance in cases where the IPv4 837 "Identification" field may wrap quickly due to the source supporting 838 high data rate flows. 840 While H-DPD is not as readily susceptible to this form of DoS attack, 841 it is possible that a sophisticated adversary could use side 842 information to construct spoofing packets to mislead forwarders using 843 a well-known hash algorithm. Thus, similarly, a separate "internal" 844 hash value could be concatenated with the well-known hash value to 845 alleviate this security concern. 847 6. Reduced Relay Set Forwarding and Relay Selection Capability 849 SMF implementations MUST support CF as a basic forwarding mechanism 850 when reduced relay set information is not available or not selected 851 for operation. In CF mode, each node transmits a locally generated 852 or newly received packet exactly once. The DPD techniques described 853 in Section 5 are critical to proper operation and prevent duplicate 854 packet retransmissions by the same forwarding node. 856 A goal of SMF is to apply reduced relay sets for more efficient 857 multicast dissemination within dynamic topologies. To accomplish 858 this SMF MUST support the ability to modify its multicast packet 859 forwarding rules based upon relay set state received dynamically 860 during operation. In this way, SMF forwarding can continue to 861 operate effectively as neighbor adjacencies or multicast forwarding 862 policies within the topology change. 864 In early SMF experimental deployments, the relay set information has 865 been derived from a coexistent unicast MANET protocol that selected a 866 reduced relay set for control plane traffic. From this experience, 867 extra pruning considerations where sometimes required when utilizing 868 a relay set from a separate routing protocol process, since a relay 869 set formed for the unicast control plane flooding MAY include a more 870 redundant set of nodes than desired for multicast forwarding use 871 (e.g., biconnected control plane CDS meshes). 873 Here is a recommended criteria list for SMF relay set selection 874 algorithm candidates: 876 1. Robustness to topological dynamics and mobility 878 2. Localized election or coordination of any relay sets 880 3. Reasonable minimization of relay set size to achieve CDS given 881 above constraints 883 4. Heuristic support for preference or election metrics (Better 884 enables scenario-specific management of relay set) 886 Some relay set algorithms meeting these criteria are described in the 887 Appendices of this document. Different algorithms may be more 888 suitable for different MANET routing types or deployments. 889 Additional relay set selection algorithms may be specified in 890 separate specifications in the future. The Appendices in this 891 document can serve as a template for the content of such potential 892 future specifications. 894 Figure 4 depicts a state information diagram of possible relay set 895 control options. 897 Possible L2 Trigger/Information 898 | 899 | 900 ______________ ______v_____ __________________ 901 | MANET | | | | | 902 | Neighborhood | | Relay Set | | Other Heuristics | 903 | Discovery |----------->| Selection |<------| (Preference,etc) | 904 | Protocol | neighbor | Algorithm | | | 905 |______________| info |____________| |__________________| 906 \ / 907 \ / 908 neighbor\ / Dynamic Relay 909 info* \ ____________ / Set Status 910 \ | SMF | / (State, {neighbor info}) 911 `-->| Relay Set |<--' 912 | State | 913 -->|____________| 914 / 915 / 916 ______________ 917 | Coexistent | 918 | MANET | 919 | Unicast | 920 | Process | 921 |______________| 923 Figure 4: Smf Relay Set Control Options 925 There are basically three styles of SMF operation with reduced relay 926 sets: 928 1. Independent operation: SMF performs its own relay set selection 929 using information from an associated MANET NHDP process. In this 930 case, NHDP messaging SHOULD be appended with additional 931 [PacketBB] type-length-value (TLV) content to support SMF- 932 specific requirements as discussed in Section 7 and for the 933 applicable relay set algorithm described in the Appendices of 934 this document or future specifications. 936 2. Operation with CDS-aware unicast routing protocol: Coexistent 937 unicast routing protocol provides dynamic relay set state based 938 upon its own control plane CDS or neighborhood discovery 939 information. If it is desired that the SMF data plane forwarding 940 use a different relay set selection algorithm than used for the 941 routing protocol control plane, then the routing protocol NHDP 942 instance (if applicable) SHOULD append its messages with the 943 appropriate SMF-specific TLV content (see Section 7 and the relay 944 set algorithm Appendices). 946 3. Cross-layer Operation: SMF operates using neighborhood status and 947 triggers from a cross-layer (e.g., layer 2 MAC or link layer) 948 information base for dynamic relay set selection and maintenance. 950 7. SMF Neighborhood Discovery Requirements 952 This section defines the requirements for use of the MANET 953 Neighborhood Discovery Protocol (NHDP) [NHDP] to support SMF 954 operation. Note that basic CF forwarding requires no neighborhood 955 topology knowledge since every SMF node relays all traffic while 956 supporting more efficient SMF relay set operation requires the 957 discovery and maintenance of dynamic neighborhood (1- and 2-hop 958 knowledge) topology information. The MANET NHDP protocol can provide 959 this necessary information, but in some circumstances there are a few 960 SMF-specific requirements for related NHDP use. This can be the case 961 for both "independent" SMF operation where NHDP is being used 962 specifically to support SMF or when one NHDP instance is used for 963 both for SMF and a coexistent MANET unicast routing protocol. 965 Core NHDP messages and the resultant neighborhood information base 966 are described separately within the NHDP specification. To 967 summarize, the NHDP protocol provides the following basic functions: 969 1. 1-hop neighbor link sensing and bidirectionality checks of 970 neighbor links, 972 2. 2-hop neighborhood discovery including collection of 2-hop 973 neighbors and connectivity information, 975 3. Collection and maintenance of the above information across 976 multiple interfaces, and 978 4. Signaling relay set selection to neighbor nodes if the relay set 979 algorithm requires such information (e.g. S-MPR ). 981 The Appendices of this document describe a set of CDS-based relay set 982 selection algorithms that can be used to achieve efficient SMF 983 operation, even in dynamic, mobile networks[MDDA07]. For some of 984 these algorithms, the core NHDP specification provides all the 985 necessary information to conduct relay set selection. For others, 986 NHDP messaging needs to be extended to support relay set selection 987 and maintenance. For example, the [OLSRv2] specification specifies 988 TLV constructs for NHDP messages to support its use of the S-MPR 989 algorithm for control plane messaging. An independent SMF 990 implementation using S-MPR can also use these same OLSRv2 TLV types 991 to support its operation. 993 The following sub-sections specify some SMF-specific TLV types to 994 support general SMF operation or to support the algorithms described 995 in the Appendices to this document. The Appendices describing each 996 of the relay set algorithms also specify any additional requirements 997 for NHDP to support their operation and reference the applicable TLV 998 types as needed. 1000 7.1. SMF Relay Algorithm TLV Types 1002 This section specifies TLV types to be used within NHDP messages to 1003 identify the CDS relay set selection algorithm(s) in use. Two TLV 1004 types are defined, one message TLV type and one address TLV type. 1006 7.1.1. Relay Algorithm Message TLV Type 1008 The message TLV type denoted SMF_RELAY_ALG is used to identify the 1009 CDS relay set selection algorithm currently in use by the NHDP 1010 message originator. When NHDP is used to support SMF operation, the 1011 SMF_RELAY_ALG TLV SHOULD be included in NHDP_HELLO messages 1012 generated. This allows SMF nodes to learn when neighbors are 1013 configured to use different relay set algorithms. This information 1014 can be used to take action, such as ignoring neighbor information 1015 using incompatible algorithms. It is possible that SMF neighbors MAY 1016 be configured differently and still operate cooperatively, but these 1017 cases will vary dependent upon the algorithm types designated. 1019 This document defines the following Message TLV typeTable 7 1020 conforming to [PacketBB] to communicate "Relay Algorithm Type" to 1021 other 1-hop SMF neighbors. 1023 +--------+---------------------+--------------------+ 1024 | | packetBB TLV syntax | Field Values | 1025 +--------+---------------------+--------------------+ 1026 | type | | SMF_RELAY_ALG | 1027 | | | | 1028 | length | | 1 byte | 1029 | | | | 1030 | value | | | 1031 +--------+---------------------+--------------------+ 1033 Table 7: SMF Relay Algorithm Type Message TLV 1035 In Table 7 is an 8-bit field containing a number 1036 0-255 representing the "Relay Algorithm Type" of the originator 1037 address of the corresponding NHDP message. 1039 Possible values for the are defined in Table 8. 1040 The table provides value assignments, future IANA assignment spaces, 1041 and an experimental space. The experimental space use MUST NOT 1042 assume uniqueness and thus should not be used for general 1043 interoperable deployment prior to official IANA assignment. 1045 +---------------------+----------------------------------------+ 1046 | Value | Algorithm | 1047 +---------------------+----------------------------------------+ 1048 | 0 | CF | 1049 | | | 1050 | 1 | S-MPR | 1051 | | | 1052 | 2 | E-CDS | 1053 | | | 1054 | 3 | MPR-CDS | 1055 | | | 1056 | 4-127 | Future Assignment with STD action | 1057 | | | 1058 | 128-239 | No STD action required | 1059 | | | 1060 | 240-255 | Experimental Space | 1061 +---------------------+----------------------------------------+ 1063 Table 8: SMF Relay Algorithm Type Values 1065 7.1.2. Relay Algorithm Address Block TLV Type 1067 An address block TLV type, denoted SMF_NBR_RELAY_ALG (i.e., SMF 1068 neighbor relay algorithm) Table 9, is specified so that CDS relay 1069 algorithm configuration can be shared among 2-hop neighborhoods This 1070 is useful for the case when mixed relay algorithm operation is 1071 possible. 1073 The message SMF_RELAY_ALG TLV and address block SMF_NBR_RELAY_ALG TLV 1074 types share a common format. 1076 +--------+---------------------+---------------------+ 1077 | | packetBB TLV syntax | Field Values | 1078 +--------+---------------------+---------------------+ 1079 | type | | SMF_NBR_RELAY_ALG | 1080 | | | | 1081 | length | | variable | 1082 | | | | 1083 | value | | * | 1084 +--------+---------------------+---------------------+ 1086 Table 9: SMF Relay Algorithm Type Address Block TLV 1088 Each in Table 9 is an 8-bit field containing a 1089 number 0-255 representing the "Relay Algorithm Type" value that 1090 corresponds to the indicated address in the address block. Note that 1091 "Relay Algorithm Type" values for 2-hop neighbors may be conveyed as 1092 single value or multiple value TLVs as described in [PacketBB]. It 1093 is expected that SMF nodes using NHDP shall construct address blocks 1094 using the SMF_NBR_RELAY_ALG TLV type to share the "Relay Algorithm 1095 Type" values of 1-hop neighbors received in SMF_RELAY_ALG TLV content 1096 from those neighbors. 1098 Again values for the are defined in Table 8. 1100 7.2. SMF Router Priority TLV Types 1102 This section specifies TLV types to be used within NHDP messages to 1103 identify SMF Router Priority values. Two TLV types are defined, one 1104 message TLV type and one address TLV type. 1106 For some relay set selection techniques, a value of Router Priority 1107 must be given or assumed for each address within the 1-hop and 1108 possibly 2-hop neighborhood. This value for a specific originator 1109 must be consistent among neighborhood nodes. The Appendices of this 1110 document discuss specific algorithm cases that require the use of 1111 this TLV. 1113 7.2.1. Router Priority Message TLV Type 1115 This document defines the following Message TLV type Table 10 to 1116 share "Router Priority" values among 1-hop SMF neighbors. 1118 +--------+---------------------+------------------+ 1119 | | packetBB TLV syntax | Field Values | 1120 +--------+---------------------+------------------+ 1121 | type | | SMF_RTR_PRIORITY | 1122 | | | | 1123 | length | | 1 byte | 1124 | | | | 1125 | value | | | 1126 +--------+---------------------+------------------+ 1128 Table 10: SMF Router Priority Message TLV 1130 in Table 9 is an 8-bit field containing a number 0-255 1131 representing the "Router Priority" value of the originator 1132 corresponding NHDP message. 1134 7.2.2. Router Priority Address Block TLV Type 1136 Some relay set selection algorithms require that the "Router 1137 Priority" for 2-hop neighbors also be communicated and this can be 1138 accomplished by including the values within address block 1139 advertisements. An Address Block TLV type is defined with the format 1140 in Table 11 to support this purpose. 1142 +--------+---------------------+----------------------+ 1143 | | packetBB TLV syntax | Field Values | 1144 +--------+---------------------+----------------------+ 1145 | type | | SMF_NBR_RTR_PRIORITY | 1146 | | | | 1147 | length | | variable | 1148 | | | | 1149 | value | | * | 1150 +--------+---------------------+----------------------+ 1152 Table 11: SMF Router Priority Address Block TLV 1154 Each in Table 11 is an 8-bit field containing a number 1155 0-255 representing the "Router Priority" value that corresponds to 1156 the indicated address in the address block. Note that "Router 1157 Priority" values for 2-hop neighbors may be conveyed as single value 1158 or multiple value TLVs as described in [PacketBB]. It is expected 1159 that SMF nodes using NHDP shall construct address blocks using the 1160 SMF_NBR_RTR_PRIORITY TLV type to share the "Router Priority" values 1161 of 1-hop neighbors received in SMF_RTR_PRIORITY TLV content from 1162 those neighbors. 1164 8. SMF Border Gateway Considerations 1166 It is expected that SMF will be used to provide simple forwarding of 1167 multicast traffic _within_ a MANET mesh routing topology. A border 1168 router approach should be used to allow interconnection of SMF areas 1169 with networks using other multicast routing protocols (e.g., PIM). 1170 It is important to note that there are many scenario-specific issues 1171 that should be addressed when discussing border routers. At the 1172 present time, experimental deployments of SMF and PIM border router 1173 approaches are being used. Some of the functionality border routers 1174 may need to address include the following: 1176 1. Determining which multicast groups should transit the border 1177 router whether entering or exiting the attached MANET routing 1178 region(s). 1180 2. Enforcement of TTL threshold or other scoping policies. 1182 3. Any marking or labeling to enable DPD on ingressing packets. 1184 4. Interface with exterior multicast routing protocols. 1186 5. Possible operation with multiple border routers (presently beyond 1187 scope of this document). 1189 6. Provisions for participating non-SMF nodes. 1191 Note the behavior of border router SMF nodes is the same as that of 1192 non-border SMF nodes when forwarding packets on interfaces within the 1193 MANET routing region. Packets that are passed outbound to interfaces 1194 operating fixed-infrastructure multicast routing protocols SHOULD be 1195 evaluated for duplicate packet status since present standard 1196 multicast forwarding mechanisms do not usually perform this function. 1198 8.1. Forwarded Multicast Groups 1200 Mechanisms for determining which groups should be forwarded into a 1201 MANET SMF routing region is an evolving technology area. Ideally, 1202 only groups for which there is active group membership should be 1203 injected into the SMF domain. This might be accomplished by 1204 providing an IPv4 Internet Group Membership Protocol (IGMP) or IPV6 1205 Multicast Listener Discovery (MLD) proxy protocol so that MANET SMF 1206 nodes can inform attached border routers (and hence multicast 1207 networks) of their current group membership status. For specific 1208 systems and services it may be possible to statically configure group 1209 membership joins in border routers, but it is RECOMMENDED that some 1210 form of IGMP/MLD proxy or other explicit, dynamic control of 1211 membership be provided. Specification of such an IGMP/MLD proxy 1212 protocol is beyond the scope of this document. 1214 Outbound traffic is less problematic. SMF border routers can perform 1215 duplicate packet detection and forward non-duplicate traffic that 1216 meets TTL/hop limit and scoping criteria to other interfaces. 1217 Appropriate IP multicast routing (PIM, etc) on those interfaces can 1218 then make further forwarding decisions with respect to the given 1219 traffic and its MANET source address. Note that the presence of 1220 multiple border routers associated with a MANET routing region may 1221 create some additional issues. This is further discussed in 1222 Section 8.4. 1224 8.2. Multicast Group Scoping 1226 Multicast scoping is used by network administrators to control the 1227 network routing regions which are reached by multicast packets. This 1228 is usually done by configuring external interfaces of border routers 1229 in the border of an routing region to not forward multicast packets 1230 which must be kept within the routing region. This is commonly done 1231 based on TTL of messages or the basis of group addresses. These 1232 schemes are known respectively as: 1234 1. TTL scoping. 1236 2. Administrative scoping. 1238 For IPv4, network administrators can configure border routers with 1239 the appropriate TTL thresholds or administratively scoped multicast 1240 groups in the router's interfaces as with any traditional multicast 1241 router. However, for the case of TTL scoping it SHOULD be taken into 1242 account that the packet could traverse multiple hops within the MANET 1243 SMF routing region before reaching the border router. Thus, TTL 1244 thresholds SHOULD be selected carefully. 1246 For IPv6, multicast address spaces include information about the 1247 scope of the group. Thus, border routers of an SMF routing region 1248 know if they must forward a packet based on the IPv6 multicast group 1249 address. For the case of IPv6, it is RECOMMENDED that a MANET SMF 1250 routing region be designated a site. Thus, all IPv6 multicast 1251 packets in the range FF05::/16 SHOULD be kept within the MANET SMF 1252 routing region by border routers. IPv6 packets in any other wider 1253 range scopes (i.e. FF08::/16, FF0B::/16 and FF0E::16) MAY traverse 1254 border routers unless other restrictions different from the scope 1255 applies. 1257 Given that scoping of multicast packets is performed at the border 1258 routers, and given that existing scoping mechanisms are not designed 1259 to work with mobile routers, it is assumed that non-border SMF 1260 routers will not stop forwarding multicast data packets of the 1261 appropriate site scoping. That is, it is assumed that the entire 1262 MANET SMF routing region is a site scoped area. 1264 8.3. Interface with Exterior Multicast Routing Protocols 1266 The traditional operation of multicast routing protocols is tightly 1267 integrated with the group membership function. Leaf routers are 1268 configured to periodically gather group membership information, while 1269 intermediate routers conspire to create multicast trees connecting 1270 routers with directly-connected multicast sources and routers with 1271 active multicast receivers. In the concrete case of SMF, border 1272 routers can be considered leaf routers. Mechanisms for multicast 1273 sources and receivers to interoperate with border routers over the 1274 multihop MANET SMF routing region as if they were directly connected 1275 to the router need to be defined. The following issues need to be 1276 addressed: 1278 1. Mechanism by which border routers gather membership information. 1280 2. Mechanism by which multicast sources are known by the border 1281 router. 1283 3. Exchange of exterior routing protocol messages across the MANET 1284 routing region if the MANET routing region is to provide transit 1285 connectivity for multicast traffic. 1287 It is beyond the scope of this document to address implementation 1288 solutions to these issues. As described in Section 8.1, IGMP/MLD 1289 proxy mechanisms can be deployed to address some of these issues. 1290 Similarly, exterior routing protocol messages could be tunneled or 1291 conveyed across the MANET routing region. But, because MANET routing 1292 regions are multi-hop and potentially unreliable, as opposed to the 1293 single-hop LAN interconnection that neighboring IP Multicast routers 1294 might typically enjoy, additional provisions may be required to 1295 achieve successful operation. 1297 The need for the border router to receive traffic from recognized 1298 multicast sources within the MANET SMF routing region is important to 1299 achieve a smooth interworking with existing routing protocols. For 1300 instance, PIM-S requires routers with locally attached multicast 1301 sources to register them to the Rendezvous Point (RP) so that other 1302 people can join the multicast tree. In addition, if those sources 1303 are not advertised to other autonomous systems (AS) using MSDP, 1304 receivers in those external networks are not able to join the 1305 multicast tree for that source. 1307 8.4. Multiple Border Routers 1309 A MANET might be deployed with multiple participating nodes having 1310 connectivity to external (to the MANET), fixed-infrastructure 1311 networks. Allowing multiple nodes to forward multicast traffic to/ 1312 from the MANET routing region can be beneficial since it can increase 1313 reliability, and provide better service. For example, if the MANET 1314 routing region were to fragment with different MANET nodes 1315 maintaining connectivity to different border routers, multicast 1316 service could still continue successfully. But, the case of multiple 1317 border routers connecting a MANET routing region to external networks 1318 presents several challenges for SMF: 1320 1. Detection/hash collision/sequencing of duplicate unmarked IPv4 or 1321 IPv6 (without IPSec encapsulation or DPD option) packets possibly 1322 injected by multiple border routers. 1324 2. Source-based relay algorithms handling of duplicate traffic 1325 injected by multiple border routers. 1327 3. Determination of which border router(s) will forward outbound 1328 multicast traffic. 1330 4. Additional challenges with interfaces to exterior multicast 1331 routing protocols. 1333 One of the most obvious issues is when multiple border routers are 1334 present and may be alternatively (due to route changes) or 1335 simultaneously injecting common traffic into the MANET routing region 1336 that has not been previously marked for SMF DPD. Different border 1337 routers would not be able to implicitly synchronize sequencing of 1338 injected traffic since they may not receive exactly the same messages 1339 due to packet losses. For IPv6 I-DPD operation, the optional 1340 "TaggerId" field described for the SMF-DPD header option can be used 1341 to mitigate this issue. When multiple border routers are injecting a 1342 flow into a MANET routing region, there are two forwarding policies 1343 that SMF DPD-S nodes may implement: 1345 1. Redundantly forward the multicast flows (identified by 1346 ) from each border router, 1347 performing DPD processing on a or 1348 basis, or 1350 2. Use some basis to select the flow of one tagger (border router) 1351 over the others and forward packets for applicable flows 1352 (identified by ) only for that 1353 "Tagger ID" until timeout or some other criteria to favor another 1354 tagger occurs. 1356 It is RECOMMENDED that the first approach be used in the case of 1357 I-DPD operation unless the SMF system is specifically designed to 1358 implement the second option. Additional specification may be 1359 required to describe an interoperable forwarding policy based on this 1360 second option. Note that the implementation of the second option 1361 requires that per-flow (i.e., ) 1362 state be maintained for the selected "Tagger ID". 1364 The deployment of a H-DPD operational mode may alleviate DPD 1365 resolution when ingressing traffic comes from multiple border 1366 routers. Non-colliding hash indexes (those not requiring the H-DPD 1367 options header in IPv6) should be resolved effectively. 1369 9. Non-SMF MANET Node Interaction 1371 There may be scenarios in which some neighboring wireless MANET node 1372 are not running SMF and/or not forwarding, but are interested in 1373 receiving multicast data. For example, a MANET service might be 1374 deployed that is accessible to wireless edge devices that do not 1375 participate in MANET routing, NDHDP, and/or SMF forwarding operation. 1376 These devices include: 1378 1. Devices that opportunistically receive multicast traffic due to 1379 proximity with SMF relays (possibly with asymmetric IP 1380 connectivity e.g., sensor network device). 1382 2. Devices that participate in NHDP (directly or via routing 1383 protocol signaling) but do not forward traffic. 1385 Note there is no guarantee of traffic delivery with category 1 above, 1386 but the election heuristics shown in Figure 2 MAY be adjusted via 1387 management to better support such devices. However, it is 1388 RECOMMENDED that nodes participate in NHDP when possible. Such 1389 devices may also transmit multicast traffic, but it is important to 1390 note that SMF routing regions using source-specific relay set 1391 algorithms such as (S-MPR) may not forward such traffic. These 1392 devices SHOULD also listen for any IGMP/MLD Queries that are provided 1393 and transmit IGMP/MLD Reports for groups they have joined per usual 1394 IP Multicast operation. While it is not in the scope of this 1395 document, IGMP/MLD proxy mechanisms may be in place to convey group 1396 membership information to any border routers or intermediate systems 1397 providing IP Multicast routing functions. 1399 10. Security Considerations 1401 Gratuitous use of option headers can cause problems in routers. 1402 Routers outside of MANET routing regions should ignore SMF-specific 1403 header options if encountered. The header options types are encoded 1404 appropriately for this behavior. 1406 Sequence-based packet identifiers are predictable and thus provide an 1407 opportunity for a denial-of-service attack against forwarding. The 1408 use of the "internal hashing" as described in Section 5.3 for the 1409 I-DPD operation helps to mitigate denial-of-service attacks on 1410 predictable packet identifiers. In this case, spoofed packets MAY be 1411 forwarded but the additional internal history identifier will protect 1412 against false collision events that may result from a predictive 1413 denial-of-service attack. 1415 Another potential denial-of-service attack against SMF forwarding is 1416 possible when a bad-behaving node has a form of "wormhole" access 1417 (via a directional antenna, etc) to preview packets before a 1418 particular SMF node would receive them. The bad-behaving node could 1419 reduce the TTL or Hop Limit of the packet and transmit it to the SMF 1420 node causing it to forward the packet with a limited TTL (or even 1421 drop it) and make a DPD entry that would block forwarding of the 1422 subsequently-arriving valid packet with appropriate TTL value. This 1423 would be a relatively low-cost, high-payoff attack that would be hard 1424 to detect and thus attractive to potential attackers. An approach of 1425 caching TTL information with DPD state and taking appropriate 1426 forwarding actions is identified in Section 4 to mitigate this form 1427 of attack. 1429 The support of forwarding IPSec datagrams without further 1430 modification for both IPv4 and IPv6 is supported by this 1431 specification. 1433 Authentication mechanisms to identify the source of IPv6 option 1434 headers should be considered to reduce vulnerability to a variety of 1435 attacks. 1437 11. IANA Considerations 1439 This document raises multiple IANA Considerations. These include the 1440 IPv6 SMF_DPD hop-by-hop Header Extension defined and multiple Type- 1441 Length-Value (TLV) constructs (see [PacketBB]) used to extend NHDP 1442 operation as needed to support different forms of SMF operation. 1444 11.1. IPv6 SMF_DPD Header Extension 1446 This document requests IANA assignment of the "SMF_DPD" hop-by-hop 1447 option type from the IANA "IPv6 Hop-by-Hop Options Option Type" 1448 registry (see Section 5.5 of [RFC2780]). 1450 The format of this new option type is described in Section 5.1.1. A 1451 portion of the option data content is the "taggerIdType" that 1452 provides a context for the "taggerId" that is optionally included to 1453 identify the intermediate system that added the SMF_DPD option to the 1454 packet. This document defines a name-space for IPv6 SMF_DPD Tagger 1455 Identifier Types: 1456 ietf:manet:smf:taggerIdTypes 1458 The values that can be assigned within the "ietf:manet:smf: 1459 taggerIdTypes" name-space are numeric indexes in the range [0, 7], 1460 boundaries included. All assignment requests are granted on a "IETF 1461 Consensus" basis as defined in [RFC2434]. 1463 This specification registers the following Tagger Identification Type 1464 values in the registry "ietf:manet:smf:taggerIdTypes": 1466 +----------+-------+---------------+ 1467 | Mnemonic | Value | Reference | 1468 +----------+-------+---------------+ 1469 | NULL | 0 | This document | 1470 | | | | 1471 | DEFAULT | 1 | This document | 1472 | | | | 1473 | IPv4 | 2 | This document | 1474 | | | | 1475 | IPv6 | 3 | This document | 1476 | | | | 1477 | ExtId | 7 | This document | 1478 +----------+-------+---------------+ 1480 11.2. SMF NHDP TLV Types 1482 SMF defines two Message TLV types that must be allocated from the 1483 "Assigned Message TLV Types" registry of [PacketBB]. The following 1484 table lists the Message TLV types that must be allocated: 1486 +------------------+-------+----------------------------------------+ 1487 | Mnemonic | Value | Description | 1488 +------------------+-------+----------------------------------------+ 1489 | SMF_RELAY_ALG | TBD | The value field of this TLV conveys | 1490 | | | the SMF relay set selection algorithm | 1491 | | | of the message originator. | 1492 | | | | 1493 | SMF_RTR_PRIORITY | TBD | The value field of this TLV conveys | 1494 | | | the "Router Priority" of the SMF node | 1495 | | | originating the message. | 1496 +------------------+-------+----------------------------------------+ 1498 Additionally, SMF also defines two corresponding Address Block TLV 1499 types that must be allocated from the "Assigned Address Block TLV 1500 Types" repository of [PacketBB]. The following table lists the 1501 Address Block TLV types that must be allocated: 1503 +----------------------+-------+------------------------------------+ 1504 | Mnemonic | Value | Description | 1505 +----------------------+-------+------------------------------------+ 1506 | SMF_NBR_RELAY_ALG | TBD | The value field of this TLV | 1507 | | | conveys the SMF relay set | 1508 | | | selection algorithm of the node | 1509 | | | associated with the corresponding | 1510 | | | address in the address block. | 1511 | | | | 1512 | SMF_NBR_RTR_PRIORITY | TBD | The value field of this TLV | 1513 | | | conveys the "Router Priority" of | 1514 | | | the SMF ode associated with the | 1515 | | | corresponding address in the | 1516 | | | address block. | 1517 +----------------------+-------+------------------------------------+ 1519 The SMF_RELAY_ALG and SMF_NBR_RELAY_ALGORITHM TLV types share a 1520 common format with an 8-bit value field that identifies the SMF relay 1521 selection algorithm type. This specification defines the following 1522 name-space for SMF relay set selection algorithm types: 1523 ietf:manet:smf:relayAlgorithms 1525 The values that can be assigned within the "ietf:manet:smf: 1526 relayAlgorithms" name-space are numeric indexes in the range [0, 1527 255], boundaries included. As shown in Table 8 assignment requests 1528 in the range [0, 127] are granted on a "IETF Consensus" basis as 1529 defined in [RFC2434]. Assignment requests within the "ietf:manet: 1530 smf:relayAlgorithms" namespace for the range [128,239] are granted on 1531 a "First Come First Served" basis as defined in [RFC2434]. The 1532 experimental space in the range [240, 255] should be reserved and not 1533 assigned. 1535 This specification registers the following Tagger Identification Type 1536 values in the registry "ietf:manet:smf:relayAlgorithms": 1538 +----------+-------+-----------------------------+ 1539 | Mnemonic | Value | Reference | 1540 +----------+-------+-----------------------------+ 1541 | CF | 0 | This document | 1542 | | | | 1543 | S-MPR | 1 | Appendix A of this document | 1544 | | | | 1545 | E-CDS | 2 | Appendix B of this document | 1546 | | | | 1547 | MPR-CDS | 3 | Appendix C of this document | 1548 +----------+-------+-----------------------------+ 1550 It is RECOMMENDED that the SMF_RELAY_ALG Message TLV type be included 1551 in NHDP messages generated by nodes configured for any form of SMF 1552 operation. 1554 12. Acknowledgments 1556 Many of the concepts and mechanisms used and adopted by SMF resulted 1557 from many years of discussion and related work within the MANET WG 1558 since the late 1990s. There are obviously many contributors to past 1559 discussions and related draft documents within the WG that have 1560 influenced the development of SMF concepts that deserve 1561 acknowledgment. In particular, the document is largely a direct 1562 product of the earlier SMF design team within the IETF MANET WG and 1563 borrows text and implementation ideas from the related individuals. 1564 Some of the contributors who have been involved in design, content 1565 editing, prototype implementation, and core discussions are listed 1566 below in alphabetical order. We appreciate input from many others we 1567 may have missed in this list as well. 1569 Design contributors in alphabetical order: 1571 Brian Adamson 1573 Teco Boot 1575 Ian Chakeres 1577 Thomas Clausen 1579 Justin Dean 1581 Brian Haberman 1583 Charles Perkins 1585 Pedro Ruiz 1587 Fred Templin 1589 Maoyu Wang 1591 The RFC text was produced using Marshall Rose's xml2rfc tool and Bill 1592 Fenner's XMLmind add-ons. 1594 13. References 1596 13.1. Normative References 1598 [E-CDS] Ogier, R., "MANET Extension of OSPF Using CDS Flooding", 1599 Proceedings of the 62nd IETF , March 2005. 1601 [MPR-CDS] Adjih, C., Jacquet, P., and L. Viennot, "Computing 1602 Connected Dominating Sets with Multipoint Relays", Ad Hoc 1603 and Sensor Wireless Networks , January 2005. 1605 [NHDP] Clausen, T. and et al, "Neighborhood Discovery Protocol", 1606 draft-ietf-manet-nhdp-05, Work in progress , 1607 December 2007. 1609 [OLSRv2] Clausen, T. and et al, "Optimized Link State Routing 1610 Protocol version 2", draft-ietf-manet-olsrv2-04, Work in 1611 progress , July 2007. 1613 [PacketBB] 1614 Clausen, T. and et al, "Generalized MANET Packet/Message 1615 Format", draft-ietf-manet-packetbb-11, Work in progress , 1616 November 2007. 1618 [RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791, 1619 September 1981. 1621 [RFC1321] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, 1622 April 1992. 1624 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1625 Requirement Levels", BCP 14, RFC 2119, March 1997. 1627 [RFC2434] Narten, T. and H. Alvestrand, "Guidelines for Writing an 1628 IANA Considerations Section in RFCs", BCP 26, RFC 2434, 1629 October 1998. 1631 [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 1632 (IPv6) Specification", RFC 2460, December 1998. 1634 [RFC2644] Senie, D., "Changing the Default for Directed Broadcasts 1635 in Routers", BCP 34, RFC 2644, August 1999. 1637 [RFC2780] Bradner, S., "IANA Allocation Guidelines For Values In the 1638 Internet Protocol and Related Headers", March 2000. 1640 [RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing 1641 Protocol", 2003. 1643 [RFC4302] Kent, S., "IP Authentication Header", December 2005. 1645 13.2. Informative References 1647 [GJ79] Garey, M. and D. Johnson, "Computers and Intractability: A 1648 Guide to the Theory of NP-Completeness.", Freeman and 1649 Company , 1979. 1651 [GM99] Garcia-Luna-Aceves, JJ. and E. Madruga, "The core-assisted 1652 mesh protocol", Selected Areas in Communications, IEEE 1653 Journal on Volume 17, Issue 8, August 1999. 1655 [JLMV02] Jacquet, P., Laouiti, V., Minet, P., and L. Viennot, 1656 "Performance of multipoint relaying in ad hoc mobile 1657 routing protocols", Networking , 2002. 1659 [MDC04] Macker, J., Dean, J., and W. Chao, "Simplified Multicast 1660 Forwarding in Mobile Ad hoc Networks", IEEE MILCOM 2004 1661 Proceedings , 2004. 1663 [MDDA07] Macker, J., Downard, I., Dean, J., and R. Adamson, 1664 "Evaluation of distributed cover set algorithms in mobile 1665 ad hoc network for simplified multicast forwarding", ACM 1666 SIGMOBILE Mobile Computing and Communications Review 1667 Volume 11 , Issue 3 (July 2007), July 2007. 1669 [MGL04] Mohapatra, P., Gui, C., and J. Li, "Group Communications 1670 in Mobile Ad hoc Networks", IEEE Computer Vol. 37, No. 2, 1671 February 2004. 1673 [NTSC99] Ni, S., Tseng, Y., Chen, Y., and J. Sheu, "The Broadcast 1674 Storm Problem in Mobile Ad hoc Networks", Proceedings Of 1675 ACM Mobicom 99 , 1999. 1677 [RFC2901] Macker, JP. and MS. Corson, "Mobile Ad hoc Networking 1678 (MANET): Routing Protocol Performance Issues and 1679 Evaluation Considerations", 1999. 1681 [RFC3684] Ogier, R., Templin, F., and M. Lewis, "Topology 1682 Dissemination Based on Reverse-Path Forwarding", 2003. 1684 [RFC3973] Adams, A., Nicholas, J., and W. Siadak, "Protocol 1685 Independent Multicast - Dense Mode (PIM-DM): Protocol 1686 Specification (Revised)", RFC 3973, January 2005. 1688 [RFC4601] Fenner, B., Handley, M., Holbrook, H., and I. Kouvelas, 1689 "Protocol Independent Multicast - Sparse Mode (PIM-SM): 1690 Protocol Specification (Revised)", RFC 4601, August 2006. 1692 [WC02] Williams, B. and T. Camp, "Comparison of Broadcasting 1693 Techniques for Mobile Ad hoc Networks", Proceedings of ACM 1694 Mobihoc 2002 , 2002. 1696 Appendix A. Source-based Multipoint Relay (S-MPR) 1698 The source-based multipoint relay (S-MPR) set selection algorithm 1699 enables individual nodes, using two-hop topology information, to 1700 select relays from their set of neighboring nodes. Relays are 1701 selected so that forwarding to the node's complete two-hop neighbor 1702 set is covered. This distributed relay set selection technique has 1703 been shown to approximate a minimal connected dominating set (MCDS) 1704 in [JLMV02]. Individual nodes must collect two-hop neighborhood 1705 information from neighbors, determine an appropriate current relay 1706 set, and inform selected neighbors of their relay status. Note that 1707 since each node picks its neighboring relays independently, S-MPR 1708 forwarders depend upon previous hop information (e.g, source MAC 1709 address) to operate correctly. The Optimized Link State Routing 1710 (OLSR) protocol has used this algorithm and protocol for relay of 1711 link state updates and other control information [RFC3626] and it has 1712 been demonstrated operationally in dynamic network environments. 1714 It is RECOMMENDED that the SMF_RELAY_ALG message TLV be included in 1715 NHDP_HELLO messages that are generated by nodes conducting S-MPR SMF 1716 operation. 1718 A.1. S-MPR Relay Set Selection Overview 1720 A RECOMMENDED algorithm for S-MPR set selection is described in the 1721 [OLSRv2] specification. As this algorithm has had considerable use 1722 to support the OLSR control plane, it is expected to perform 1723 adequately to support data plane multicast traffic. To summarize, 1724 the S-MPR algorithm uses bi-directional 1-hop and 2-hop neighborhood 1725 information collected via NHDP to select, from a node's 1-hop 1726 neighbors, a set of relays that will cover the node's entire 2-hop 1727 neighbor set upon forwarding. The algorithm described uses a 1728 "greedy" heuristic of first picking the 1-hop neighbor who will cover 1729 the most 2-hop neighbors. Then, excluding those 2-hop neighbors that 1730 have been covered, additional relays from its 1-hop neighbor set are 1731 iteratively selected until the entire 2-hop neighborhood is covered. 1732 Note that 1-hop neighbors also identified as 2-hop neighbors are 1733 considered as 1-hop neighbors only. This is only a partial 1734 description of the S-MPR algorithm. The [RFC3626] specification 1735 provides a complete description including the use of a "willingness" 1736 metric that can be used to influence S-MPR forwarder selection. That 1737 specification also describes a "WILLINGNESS" message TLV that can be 1738 used in NHDP by nodes to advertise their "willingness" metric value 1739 to their neighbors. 1741 NHDP_HELLO messages are used to signal relay selections to 1-hop 1742 neighbors. The "MPR" address block TLV specified in [RFC3626] MUST 1743 be used to mark the addresses of selected neighbor relays in the 1744 NHDP_HELLO message address block(s). It is important to note that 1745 S-MPR forwarding is dependent upon the previous hop of an incoming 1746 packet. A S-MPR node MUST forward packets only for neighbors which 1747 have explicitly selected it as a relay (i.e., its "selectors"). 1748 There are also some additional requirements for duplicate packet 1749 detection to support S-MPR SMF operation that are described below. 1751 For multiple interface operation, MPR selection SHOULD be conducted 1752 on a per-interface basis. However, it is possible to economize MPR 1753 selection among multiple interfaces by selecting common MPRs to the 1754 extent possible. It is important to note that the S-MPR forwarding 1755 rules described in assume per-interface MPR selection (i.e. MPRs are 1756 _not_ selected in the context of all interfaces). This is consistent 1757 with the MPR selection heuristics described in [RFC3626]. Other 1758 source-based approaches may be possible, but would require 1759 alternative selection and forwarding rules be specified. 1761 A.2. S-MPR Forwarding Rules 1763 An S-MPR relay MUST only forward packets for neighbors that have 1764 explicitly selected it as a forwarder. The source-based forwarding 1765 technique also stipulates some additional duplicate packet detection 1766 operations. For multiple network interfaces, independent DPD state 1767 MUST be maintained for each separate interface. The following table 1768 provides the procedure for S-MPR packet forwarding given the arrival 1769 of a packet on a given interface, denoted . There are 1770 three possible actions, depending upon the previous-hop transmitter: 1772 1. If the previous-hop transmitter has selected the current node as 1773 a relay, 1775 A. The packet identifier is checked against the DPD state for 1776 each possible outbound interface, including the . 1778 B. If the packet is not a duplicate for an outbound interface, 1779 the packet is forwarded via that interface and a DPD entry is 1780 made for the given packet identifier for the interface. 1782 C. If the packet is a duplicate, no action is taken for that 1783 interface. 1785 2. Else, if the previous-hop transmitter is a 1-hop symmetric 1786 neighbor, 1788 A. A DPD entry is made for that packet for the , but 1789 the packet is not forwarded. 1791 3. Otherwise, no action is taken. 1793 Case number two in the above table is non-intuitive, but important to 1794 ensure correctness of S-MPR SMF operation. The selection of source- 1795 based relays does not result in a common set among neighboring nodes, 1796 so relays MUST mark in their DPD state, packets received from non- 1797 selector, symmetric, one-hop neighbors (for a given interface) and 1798 not forward subsequent duplicates of that packet if received on that 1799 interface. Deviation here can result in unnecessary, repeated packet 1800 forwarding throughout the network, or incomplete flooding. 1802 Nodes not participating in neighborhood discovery and relay set 1803 selection will not be able to source multicast packets into the area 1804 and have SMF forward them. Correct S-MPR relay behavior will occur 1805 with the introduction of repeaters (non-NHDP/SMF participants that 1806 relay multicast packets using duplicate detection and CF) but the 1807 repeaters will not efficiently contribute to S-MPR forwarding as 1808 these nodes will not be identified as neighbors (symmetric or 1809 otherwise) in the S-MPR forwarding process. NHDP/SMF participants 1810 MUST NOT provide extra forwarding, forwarding packets which are not 1811 selected by the algorithm, as this can disrupt network-wide S-MPR 1812 flooding, resulting in incomplete or inefficient flooding. 1814 A.3. S-MPR Neighborhood Discovery Requirements 1816 S-MPR election operation requires 2-hop neighbor knowledge as 1817 provided by the NHDP protocol [NHDP] or from external sources. MPRs 1818 are dynamically selected by each node and selections MUST be 1819 advertised and dynamically updated within NHDP or an equivalent 1820 protocol or mechanism. For NHDP use, the MPR-specific TLVs defined 1821 in OLSRv2 [OLSRv2] are also required to be implemented by NHDP. This 1822 includes the "MPR" address block TLV type for designating selected 1823 1-hop neighbors and the optional "WILLINGNESS" TLV described in that 1824 specification. The NHDP or external process must also provide link- 1825 layer (MAC) addresses of 1-hop neighbor nodes and MPR selectors so 1826 that S-MPR forwarding can be conducted properly. 1828 A.4. S-MPR Selection Algorithm 1830 This section describes a basic algorithm for the S-MPR selection 1831 process. Note that the selection is with respect to a specific 1832 interface of the node performing selection and other node interfaces 1833 referenced are reachable from this reference node interface. This is 1834 consistent with the S-MPR forwarding rules described above. When 1835 multiple interfaces per node are used, it is possible to enhance the 1836 overall selection process across multiple interfaces such that common 1837 nodes are selected as MPRs for each interface to avoid unnecessary 1838 inefficiencies in flooding. This is described further in [OLSRv2]. 1840 The following steps describe a basic algorithm for conducting S-MPR 1841 selection for a node interface "n0": 1843 1. Initialize the set "MPR" to empty. 1845 2. Initialize the set "N1" to include all 1-hop neighbors of "n0". 1847 3. Initialize the set "N2" to include all 2-hop neighbors, excluding 1848 "n0" and any nodes in "N1". 1850 4. For each interface "y" in "N1", initialize a set "N2(y)" to 1851 include any interfaces in "N2" that are 1-hop neighbors of "y". 1853 5. For each interface "x" in "N1" with a willingness value of 1854 "WILL_ALWAYS" (or using CF relay algorithm), select "x" as a MPR: 1856 A. Add "x" to the set "MPR" and remove "x" from "N1". 1858 B. For each interface "z" in "N2(x)", remove "z" from "N2" 1860 C. For each interface "y" in "N1", remove any interfaces in 1861 "N2(x)" from "N2(y)" 1863 6. For each interface "z" in "N2", initialize the set "N1(z)" to 1864 include any interfaces in "N1" that are 1-hop neighbors of "z". 1866 7. For each interface "x" in "N2" where "N1(x)" has only one member, 1867 select "x" as a MPR: 1869 A. Add "x" to the set "MPR" and remove "x" from "N1". 1871 B. For each interface "z" in "N2(x)", remove "z" from "N2" and 1872 delete "N1(z)" 1874 C. For each interface "y" in "N1", remove any interfaces in 1875 "N2(x)" from "N2(y)" 1877 8. While "N2" is not empty, select the interface "x" in "N1" with 1878 the largest number of members in "N_2(x)" as a MPR: 1880 A. Add "x" to the set "MPR" and remove "x" from "N1". 1882 B. For each interface "z" in "N2(x)", remove "z" from "N2" 1884 C. For each interface "y" in "N1", remove any interfaces in 1885 "N2(x)" from "N2(y)" 1887 After the set of nodes "MPR" is selected, node "n_0" must signal its 1888 selections to its neighbors. With NHDP, this is done by using the 1889 MPR address block TLV to mark selected neighbor addresses in 1890 NHDP_HELLO messages. Neighbors MUST record their MPR selection 1891 status and the previous hop address (e.g., link or MAC layer) of the 1892 selector. Note these steps are re-evaluated upon neighborhood status 1893 changes. 1895 Appendix B. Essential Connecting Dominating Set (E-CDS) Algorithm 1897 The "Essential Connected Dominating Set" (E-CDS) algorithm [E-CDS] 1898 allows nodes to use 2-hop neighborhood topology information to 1899 dynamically elect _themselves_ as relay nodes to form a CDS. Its 1900 packet forwarding rules are not dependent upon previous hop 1901 knowledge. Additionally, E-CDS SMF forwarders can be easily mixed 1902 without problem with CF SMF forwarders, even those not participating 1903 in NHDP. Another benefit is that packets opportunistically received 1904 from non-symmetric neighbors may be forwarded without compromising 1905 flooding efficiency or correctness. Furthermore, multicast sources 1906 not participating in NHDP may freely inject their traffic and 1907 neighboring E-CDS relays will properly forward the traffic. The 1908 E-CDS based relay set selection algorithm is based upon the summary 1909 within [E-CDS]. E-CDS was originally discussed in the context of 1910 forming partial adjacencies and efficient flooding for MANET OSPF 1911 extensions work and the core algorithm is applied here for SMF. 1913 It is RECOMMENDED that the SMF_RELAY_ALG message TLV be included in 1914 NHDP_HELLO messages that are generated by nodes conducting E-CDS SMF 1915 operation. 1917 B.1. E-CDS Relay Set Selection Overview 1919 The E-CDS relay set selection requires 2-hop neighborhood information 1920 collected through NHDP or another process. Relay nodes, in E-CDS SMF 1921 selection, are "self-elected" using a Router ID (identifier, that may 1922 be represented by an interface address) and an optional nodal metric, 1923 referred to here as "Router Priority" for all 1-hop and 2-hop 1924 neighbors. To ensure proper relay set self-election, the Router ID 1925 and Router Priority MUST be consistent among nodes participating and 1926 it is RECOMMENDED that NHDP be used to share this information. The 1927 E-CDS self-election process can be summarized as follows: 1929 1. If an SMF node has a higher ordinal (Router Priority, Router ID) 1930 than all of its symmetric neighbors, it elects itself to act as a 1931 forwarder for all received multicast packets, 1933 2. Else, if there does not exist a path from neighbor "j" with 1934 largest (Router Priority, Router ID) to any other neighbor, _via_ 1935 neighbors with larger values of (Router Priority, Router ID), 1936 then it elects itself to the relay set. 1938 The basic form of E-CDS described and applied within this 1939 specification does not provide for redundant relay set election 1940 (e.g., bi-connected) but such capability is supported by the basic 1941 E-CDS design. 1943 B.2. E-CDS Forwarding Rules 1945 With E-CDS, any SMF node that has selected itself as a relay performs 1946 DPD and forward all non-duplicative multicast traffic allowed by the 1947 present forwarding policy. Packet previous hop knowledge is not 1948 needed for forwarding decisions when using E-CDS. 1950 1. Upon packet reception, DPD is performed. Note E-CDS require one 1951 duplicate table for the set of interfaces associated with the 1952 relay set selection. 1954 2. If the packet is a duplicate, no further action is taken. 1956 3. If the packet is non-duplicative: 1958 A. A DPD entry is made for the packet identifier 1960 B. The packet is forwarded out all interfaces associated with 1961 the relay set selection 1963 As previously mentioned, even packets sourced (or relayed) by nodes 1964 not participating in NHDP and/or the E-CDS relay set selection may be 1965 forwarded by E-CDS forwarders without problem. A particular 1966 deployment MAY choose to not forward packets from sources or relays 1967 that have been explicitly identified via NHDP or other means as 1968 operating as part of a different relay set algorithm (e.g. S-MPR) to 1969 allow coexistent deployments to operate correctly. Also, E-CDS relay 1970 set selection may be configured to be influenced by statically- 1971 configured CF relays that are identified via NHDP or other means. 1973 B.3. E-CDS Neighborhood Discovery Requirements 1975 It is possible to perform E-CDS relay set selection without 1976 modification of NHDP, basing the self-election process exclusively on 1977 the Router IDs (interface addresses) of participating SMF nodes. 1978 However, it has been shown that use of the "Router Priority" metric 1979 as part of the selection process can result in improved performance 1980 in certain cases. Note that SMF nodes with higher "Router Priority" 1981 values will tend to be favored as relays over other nodes. Thus, 1982 preferred relays MAY be administratively configured to be selected 1983 when possible. Additionally, other metrics (e.g. nodal degree, 1984 energy capacity, etc) for "Router Priority" may be used to produce 1985 desired network performance. In either case it is required that SMF 1986 nodes MUST have been assigned unique "Router ID" values. For 1987 multiple interface operation, it is necessary that a consistent 1988 "Router ID" be advertised in NHDP messages for the originator and its 1989 1-hop symmetric neighbors (_TBD - Does NHDP provide for this? If so, 1990 how? Or do we need to define an SMF_RTR_ID TLV?_). 1992 The SMF_PRIORITY message TLV and SMF_NBR_PRIORITY address block TLV 1993 described in Section 7.2 are RECOMMENDED for use with SMF E-CDS 1994 operation. The SMF_PRIORITY message TLV is used to share a node's 1995 "Router Priority" with its 1-hop neighbors and the SMF_NBR_PRIORITY 1996 address block TLV is used to convey "Router Priority" values among 1997 2-hop neighborhoods. A default technique of using nodal degree (i.e. 1998 count of 1-hop neighbors) is RECOMMENDED for the value field of these 1999 TLV types. 2001 B.4. E-CDS Selection Algorithm 2003 This section describes an algorithm for E-CDS relay selection (self- 2004 election). The algorithm described uses 2-hop information. Note it 2005 is possible to extend this algorithm to use k-hop information with 2006 added computational complexity and mechanisms for sharing k-hop 2007 topology information that are not described in this document or the 2008 NHDP specification. It should also be noted that this algorithm does 2009 not impose the "hop limit" bound described in [E-CDS] when performing 2010 the path search that is used for relay selection. However, the 2011 algorithm below could be easily augmented to accommodate this 2012 additional criteria. In normal operation, it is not expected that 2013 the "hop limit" bound will provide significant benefit. 2015 The tuple of "Router Priority" and "Router ID" is used in E-CDS relay 2016 set selection. Precedence is given to the "Router Priority" portion 2017 and the "Router ID" value is used as a tie-breaker. The evaluation 2018 of this tuple is referred to as "RtrPri(n)" in the description below 2019 where "n" references a specific node. Note it is possible that the 2020 "Router Priority" portion may be optional and the evaluation of 2021 "RtrPri()" be solely based upon the unique "Router ID". Since there 2022 MUST NOT be any duplicate "Router ID" values among SMF nodes, a 2023 comparison of RtrPri(n) between any two nodes will always be an 2024 inequality. The following steps describe a basic algorithm for 2025 conducting E-CDS relay selection for a node "n0": 2027 1. Initialize the set "N1" to include all 1-hop neighbors of "n0". 2029 2. If "N1" has less than 2 members, then "n0" does _not_ select 2030 itself as a relay and no further steps are taken. 2032 3. Initialize the set "N2" to include all 2-hop neighbors, excluding 2033 "n0" and any nodes in "N1". 2035 4. If "RtrPri(n0)" is greater than that of all nodes in the union of 2036 "N1" and "N2", then "n0" selects itself as a relay and no further 2037 steps are taken. 2039 5. Initialize all nodes in the union of "N1" and "N2" as 2040 "unvisited". 2042 6. Find the node "n1_Max" that has the largest "RtrPri()" of all 2043 nodes in "N1" 2045 7. Initialize queue "Q" to contain "n1_Max", marking "n1_Max" as 2046 "visited" 2048 8. While node queue "Q" is not empty, remove node "x" from the head 2049 of "Q", and for each 1-hop neighbor "n" of node "x" (excluding 2050 "n0") that is _not_ marked "visited" 2052 A. Mark node "n" as "visited" 2054 B. If "RtrPri(n)" is greater than "RtrPri(n0), append "n" to "Q" 2056 9. If any node in "N1" remains "unvisited", then "n0" selects itself 2057 as a relay. Otherwise "n0" does not act as an relay. 2059 Note these steps are re-evaluated upon neighborhood status changes. 2060 Steps 5 through 8 of this procedure describe an approach to a path 2061 search. The purpose of this path search is to determine if paths 2062 exist from the 1-hop neighbor with maximum "RtrPri()" to all other 2063 1-hop neighbors without traversing an intermediate node with a 2064 ""RtrPri()" value less than "RtrPri(n0)". These steps comprise a 2065 breadth-first traversal that evaluates only paths that meet that 2066 criteria. If all 1-hop neighbors of "n0" are "visited" during this 2067 traversal, then the path search has succeeded and node "n0" does not 2068 need to provide relay. It can be assumed that other nodes will 2069 provide relay operation to ensure SMF connectivity. 2071 It is possible to extend this algorithm to consider neighboring SMF 2072 nodes that are known to be statically configured for CF (always 2073 relaying). The modification to the above algorithm is to process 2074 such nodes as having a maximum possible "Router Priority" value. It 2075 is expected that nodes configured for CF and participating in NHDP 2076 would indicate this with use of the SMF_RELAY_ALG and 2077 SMF_NBR_RELAY_ALG TLV types in their NHDP_HELLO message and address 2078 blocks, respectively. 2080 Appendix C. Multipoint Relay Connected Dominating Set (MPR-CDS) 2081 Algorithm 2083 The MPR-CDS algorithm is an extension to the basic S-MPR election 2084 algorithm that results in a shared (non source-specific) SMF CDS. 2085 Thus its forwarding rules are not dependent upon previous hop 2086 information similar to E-CDS. An overview of the MPR-CDS selection 2087 algorithm is provided in [MPR-CDS]. 2089 It is RECOMMENDED that the SMF_RELAY_ALG message TLV be included in 2090 NHDP_HELLO messages that are generated by nodes conducting MPR-CDS 2091 SMF operation. 2093 C.1. MPR-CDS Relay Set Selection Overview 2095 The MPR-CDS relay set selection process is based upon the MPR 2096 selection process of the S-MPR algorithm with the added refinement of 2097 a distributed technique for subsequently down-selecting to a common 2098 reduced, shared relay set. A node ordering (or "prioritization") 2099 metric is used as part of this down-selection process Like the E-CDS 2100 algorithm, this metric can be based upon node address or some other 2101 unique router identifier ("Router ID") as well as an additional 2102 "Router Priority" measure, if desired. The process for MPR-CDS relay 2103 selection is as follows: 2105 1. First, MPR selection per the S-MPR algorithm is conducted, with 2106 selectors informing their MPRs (via NHDP) of their selection. 2108 2. Then, the following rules are used on a distributed basis by 2109 selected nodes to possibly unselect themselves and thus jointly 2110 establish a common set of shared SMF relays: 2112 A. If a selected node has a larger "RtrPri()" than all of its 2113 1-hop symmetric neighbors, then it acts as a relay for all 2114 multicast traffic, regardless of the previous hop 2116 B. Else, if the 1-hop symmetric neighbor with the largest 2117 "RtrPri()" value has selected the node, then it also acts as 2118 a relay for all multicast traffic, regardless of the previous 2119 hop. 2121 C. Otherwise, it unselects itself as a relay and does not 2122 forward any traffic unless changes occur that require re- 2123 evaluation of the above steps. 2125 This technique shares many of the desirable properties of the E-CDS 2126 technique with regards to compatibility with multicast sources not 2127 participating in NHDP and the opportunity for statically-configure CF 2128 nodes to be present, regardless of their participation in NHDP. 2130 C.2. MPR-CDS Forwarding Rules 2132 The forwarding rules for MPR-CDS are common with those of E-CDS. Any 2133 SMF node that has selected itself as a relay performs DPD and forward 2134 all non-duplicative multicast traffic allowed by the present 2135 forwarding policy. Packet previous hop knowledge is not needed for 2136 forwarding decisions when using MPR-CDS. 2138 1. Upon packet reception, DPD is performed. Note MPR-CDS require 2139 one duplicate table for the set of interfaces associated with the 2140 relay set selection. 2142 2. If the packet is a duplicate, no further action is taken. 2144 3. If the packet is non-duplicative: 2146 A. A DPD entry is made for the packet identifier 2148 B. The packet is forwarded out all interfaces associated with 2149 the relay set selection 2151 As previously mentioned, even packets sourced (or relayed) by nodes 2152 not participating in NHDP and/or the MPR-CDS relay set selection may 2153 be forwarded by E-CDS forwarders without problem. A particular 2154 deployment MAY choose to not forward packets from sources or relays 2155 that have been explicitly identified via NHDP or other means as 2156 operating as part of a different relay set algorithm (e.g. S-MPR) to 2157 allow coexistent deployments to operate correctly. Also, MPR-CDS 2158 relay set selection may be configured to be influenced by statically- 2159 configured CF relays that are identified via NHDP or other means. 2161 C.3. MPR-CDS Neighborhood Discovery Requirements 2163 The neighborhood discovery requirements for MPR-CDS have commonality 2164 with both the S-MPR and E-CDS algorithms. MPR-CDS selection 2165 operation requires 2-hop neighbor knowledge as provided by the NHDP 2166 protocol [NHDP] or from external sources. In the S-MPR phase of MPR- 2167 CDS selection, MPRs are dynamically determined by each node and 2168 selections MUST be advertised and dynamically updated using NHDP or 2169 an equivalent protocol or mechanism. For NHDP use, the TLVs defined 2170 in OLSRv2 [OLSRv2] to support MPR selection and notification are also 2171 required. This includes the "MPR" address block TLV type for 2172 designating selected 1-hop neighbors and the optional "WILLINGNESS" 2173 TLV described in that specification. Unlike S-MPR operation, there 2174 is no need for associating link-layer address information with 1-hop 2175 neighbors since MPR-CDS forwarding is independent of the previous 2176 hop. In common with E-CDS, the SMF_RTR_PRIORITY TLV MAY be used to 2177 advertise an optional "Router Priority" value associated with a node. 2178 However, in MPR-CDS, only the message TLV for "Router Priority" needs 2179 to be used since only 1-hop knowledge of "Router Priority" is 2180 required. 2182 The NHDP or external process must also provide link-layer (MAC) 2183 addresses of 1-hop neighbor nodes and MPR selectors so that S-MPR 2184 forwarding can be conducted properly. 2186 C.4. MPR-CDS Selection Algorithm 2188 This section describes an algorithm for the MPR-CDS selection 2189 process. Note that the selection described is with respect to a 2190 specific interface of the node performing selection and other node 2191 interfaces referenced are reachable from this reference node 2192 interface. An ordered tuple of "Router Priority" and "Router ID" is 2193 used in MPR-CDS relay set selection. Precedence is given to the 2194 "Router Priority" portion and the "Router ID" value is used as a tie- 2195 breaker. The evaluation of this tuple is referred to as "RtrPri(n)" 2196 in the description below where "n" references a specific node. Note 2197 it is possible that the "Router Priority" portion may be optional and 2198 the evaluation of "RtrPri()" be solely based upon the unique "Router 2199 ID". Since there MUST NOT be any duplicate "Router ID" values among 2200 SMF nodes, a comparison of RtrPri(n) between any two nodes will 2201 always be an inequality. Additionally, since this process includes 2202 S-MPR selection as part of its execution, the S-MPR "WILLINGNESS" 2203 value that nodes MAY use is also taken into consideration. Note 2204 that, if a node is configured with a "WILLINGNESS" value of 2205 "WILL_ALWAYS", then that node's "RtrPtr()" should be evaluated 2206 assuming the maximum possible "Router Priority". The following 2207 steps, repeated upon any changes detected within the 1-hop and 2-hop 2208 neighborhood, describe a basic algorithm for conducting MPR-CDS 2209 selection for a node interface "n0": 2211 1. Perform steps 1-8 of Appendix A.4 to select MPRs from the set of 2212 1-hop neighbors of "n0" and notify/update neighbors of 2213 selections. 2215 2. Upon being selected as an MPR (or any change in the set of nodes 2216 selecting "n0" as an MPR): 2218 A. If no neighbors have selected "n0" as an MPR, "n0" does not 2219 act as a relay and no further steps are taken until a change 2220 in neighborhood topology or selection status occurs. 2222 B. Determine the node "n1_max" that has the maximum "RtrPri()" 2223 of all 1-hop neighbors. 2225 C. If "RtrPri(n0)" is greater than "RtrPri(n1_max)", then "n0" 2226 selects itself as a relay for all multicast packets, 2228 D. Else, if "n1_max" has selected "n0" as an MPR, then "0" 2229 selects itself as a relay for all multicast packets. 2231 E. Otherwise, "n0" does not act as a relay. 2233 It is possible to extend this algorithm to consider neighboring SMF 2234 nodes that are known to be statically configured for CF (always 2235 relaying). The modification to the above algorithm is to process 2236 such nodes as having a maximum possible "Router Priority" value. 2237 This is the same as the case for participating nodes that have been 2238 configured with a S-MPR "WILLINGNESS" value of "WILL_ALWAYS". It is 2239 expected that nodes configured for CF and participating in NHDP would 2240 indicate their status with use of the SMF_RELAY_ALG TLV type in their 2241 NHDP_HELLO message TLV block. 2243 Authors' Addresses 2245 Joseph Macker 2246 NRL 2247 Washington, DC 20375 2248 USA 2250 Email: macker@itd.nrl.navy.mil 2252 SMF Design Team 2253 IETF MANET WG 2255 Email: manet@ietf.org 2257 Full Copyright Statement 2259 Copyright (C) The IETF Trust (2008). 2261 This document is subject to the rights, licenses and restrictions 2262 contained in BCP 78, and except as set forth therein, the authors 2263 retain all their rights. 2265 This document and the information contained herein are provided on an 2266 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 2267 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 2268 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 2269 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 2270 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 2271 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 2273 Intellectual Property 2275 The IETF takes no position regarding the validity or scope of any 2276 Intellectual Property Rights or other rights that might be claimed to 2277 pertain to the implementation or use of the technology described in 2278 this document or the extent to which any license under such rights 2279 might or might not be available; nor does it represent that it has 2280 made any independent effort to identify any such rights. Information 2281 on the procedures with respect to rights in RFC documents can be 2282 found in BCP 78 and BCP 79. 2284 Copies of IPR disclosures made to the IETF Secretariat and any 2285 assurances of licenses to be made available, or the result of an 2286 attempt made to obtain a general license or permission for the use of 2287 such proprietary rights by implementers or users of this 2288 specification can be obtained from the IETF on-line IPR repository at 2289 http://www.ietf.org/ipr. 2291 The IETF invites any interested party to bring to its attention any 2292 copyrights, patents or patent applications, or other proprietary 2293 rights that may cover technology that may be required to implement 2294 this standard. Please address the information to the IETF at 2295 ietf-ipr@ietf.org. 2297 Acknowledgment 2299 Funding for the RFC Editor function is provided by the IETF 2300 Administrative Support Activity (IASA).