idnits 2.17.1 draft-ietf-manet-smf-06.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 1838. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1849. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1856. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1862. 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 == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: Values are defined in Table 6. The table provides present value assignments, future IANA reserved space, and an experimental space. Experimental space use MUST not assume uniqueness properties and should be used only for experimentation prior to any IANA assignment.. -- 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 (November 17, 2007) is 6006 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Unused Reference: 'PacketBB' is defined on line 1399, but no explicit reference was found in the text == Unused Reference: 'RFC0791' is defined on line 1404, but no explicit reference was found in the text == Unused Reference: 'GJ79' is defined on line 1426, but no explicit reference was found in the text == Unused Reference: 'MDDA07' is defined on line 1438, but no explicit reference was found in the text == Unused Reference: 'NTSC99' is defined on line 1444, but no explicit reference was found in the text == Unused Reference: 'WC02' is defined on line 1463, but no explicit reference was found in the text -- No information found for draft-ietf-manet-ndp - is the name correct? == Outdated reference: A later version (-19) exists of draft-ietf-manet-olsrv2-00 == Outdated reference: A later version (-17) exists of draft-ietf-manet-packetbb-00 ** Obsolete normative reference: RFC 2460 (Obsoleted by RFC 8200) -- Obsolete informational reference (is this intentional?): RFC 4601 (Obsoleted by RFC 7761) Summary: 2 errors (**), 0 flaws (~~), 10 warnings (==), 9 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: May 20, 2008 IETF MANET WG 6 November 17, 2007 8 Simplified Multicast Forwarding for MANET 9 draft-ietf-manet-smf-06 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 May 20, 2008. 36 Copyright Notice 38 Copyright (C) The IETF Trust (2007). 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 consistent with both IPv4 and IPv6. SMF takes 48 advantage of reduced relay sets for efficient MANET multicast 49 forwarding within a mesh topology and the document describes protocol 50 interaction with a number of approaches. Candidate algorithms for 51 selecting reduced relay sets and related discussion is 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 . . . . . . . . . . . . . . . . . . . . . . . . 8 62 4. SMF Packet Processing and Forwarding . . . . . . . . . . . . . 9 63 5. SMF Duplicate Packet Detection . . . . . . . . . . . . . . . . 11 64 5.1. IPv6 Duplicate Packet Detection . . . . . . . . . . . . . 12 65 5.1.1. IPv6 SMF-DPD Header Option . . . . . . . . . . . . . . 12 66 5.1.2. IPv6 Identification-based DPD Operation . . . . . . . 14 67 5.1.3. IPv6 Hash-based DPD Operation . . . . . . . . . . . . 16 68 5.2. IPv4 Duplicate Packet Detection . . . . . . . . . . . . . 17 69 5.2.1. IPv4 Identification-based DPD Operation . . . . . . . 18 70 5.2.2. IPv4 Hash-based DPD Operation . . . . . . . . . . . . 19 71 5.3. Internal Hash Computation . . . . . . . . . . . . . . . . 20 72 6. Reduced Relay Set Forwarding and Relay Selection Capability . 21 73 7. SMF Neighborhood Discovery Requirements . . . . . . . . . . . 23 74 7.1. SMF Relay Set Algorithm ID Message TLV . . . . . . . . . . 24 75 7.2. Router Priority Message TLV . . . . . . . . . . . . . . . 24 76 7.3. Router Priority Address Block TLV . . . . . . . . . . . . 25 77 8. SMF Border Gateway Considerations . . . . . . . . . . . . . . 26 78 8.1. Forwarded Multicast Groups . . . . . . . . . . . . . . . . 26 79 8.2. Multicast Group Scoping . . . . . . . . . . . . . . . . . 27 80 8.3. Interface with Exterior Multicast Routing Protocols . . . 28 81 8.4. Multiple Border Routers . . . . . . . . . . . . . . . . . 29 82 9. Non-SMF MANET Node Interaction . . . . . . . . . . . . . . . . 31 83 10. Security Considerations . . . . . . . . . . . . . . . . . . . 32 84 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 33 85 12. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 34 86 13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 35 87 13.1. Normative References . . . . . . . . . . . . . . . . . . . 35 88 13.2. Informative References . . . . . . . . . . . . . . . . . . 35 89 Appendix A. Reduced Relay Set Forwarding Algorithms and 90 Considerations . . . . . . . . . . . . . . . . . . . 37 91 Appendix B. Source-based Multipoint Relay (S-MPR) . . . . . . . . 38 92 B.1. S-MPR Relay Set Selection . . . . . . . . . . . . . . . . 38 93 B.2. S-MPR Forwarding Rules . . . . . . . . . . . . . . . . . . 38 94 B.3. S-MPR Neighborhood Discovery Requirements . . . . . . . . 39 95 B.4. S-MPR Selection Algorithm . . . . . . . . . . . . . . . . 39 96 B.4.1. MPR Node Selection Procedure . . . . . . . . . . . . . 40 97 Appendix C. Essential Connecting Dominating Set (E-CDS) 98 Algorithm . . . . . . . . . . . . . . . . . . . . . . 41 99 C.1. E-CDS Relay Set Selection . . . . . . . . . . . . . . . . 41 100 C.2. E-CDS Forwarding Rules . . . . . . . . . . . . . . . . . . 41 101 C.3. E-CDS Neighborhood Discovery Requirements . . . . . . . . 42 102 C.4. E-CDS Selection Algorithm (2-Hop) . . . . . . . . . . . . 43 103 Appendix D. Multipoint Relay Connected Dominating Set 104 (MPR-CDS) Algorithm . . . . . . . . . . . . . . . . . 44 105 D.1. MPR-CDS Relay Set Selection . . . . . . . . . . . . . . . 44 106 D.2. MPR-CDS Forwarding Rules . . . . . . . . . . . . . . . . . 44 107 D.3. MPR-CDS Neighborhood Discovery Requirements . . . . . . . 45 108 D.4. MPR-CDS Selection Algorithm . . . . . . . . . . . . . . . 45 109 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 46 110 Intellectual Property and Copyright Statements . . . . . . . . . . 47 112 1. Requirements Notation 114 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 115 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 116 document are to be interpreted as described in [RFC2119]. 118 2. Introduction and Scope 120 MANET unicast routing protocol designs have demonstrated effective 121 and efficient mechanisms to flood routing control plane packets 122 throughout a wireless routing region. For example, algorithms 123 specified within [RFC3626]and [RFC3684] provide distributed methods 124 of dynamically electing reduced relay sets that attempt to optimize 125 control packet flooding of routing control packets amongst MANET 126 routing peers. Simplified Multicast Forwarding (SMF) extends the 127 efficient flooding concept to the forwarding plane for IP multicast 128 packets. When localized, efficient flooding is deemed an effective 129 technique, SMF provides an appropriate multicast forwarding 130 capability. The SMF baseline design limits the scope to basic, best 131 effort multicast forwarding intended to be constrained within a MANET 132 or wireless mesh routing region. The main design goals of this SMF 133 specification are to adapt efficient relay sets in MANET environments 134 [RFC2901] and define the needed IPv4 and IPv6 multicast duplicate 135 packet detection (DPD) mechanisms to support multi-hop, packet 136 forwarding. Figure 1 provides an overview of the logical SMF node 137 architecture, consisting of "Neighborhood Discovery", "Relay Set 138 Selection" and "Forwarding Process" components. Typically, relay set 139 selection (or self-election) will occur based on input from a 140 neighborhood discovery process, and the forwarding process will be 141 controlled by status based upon relay set selection. Note the 142 neighborhood discovery and/or relay set selection information MAY be 143 obtained from a coexistent process (e.g., MANET unicast routing 144 protocol using relay sets). In some cases, the forwarding decision 145 for a packet can also depend on previous hop or incoming interface 146 information. The asterisks (*) in Figure 1 mark the primitives and 147 relationships needed by relay set algorithms requiring previous-hop 148 packet forwarding knowledge. 150 ______________ _____________ 151 | | | | 152 | Neighborhood | | Relay Set | 153 | Discovery |------------->| Selection | 154 | Protocol | neighbor | Algorithm | 155 |______________| info |_____________| 156 \ / 157 \ / 158 neighbor\ /forwarding 159 info* \ ____________ / status 160 \ | | / 161 `-->| Forwarding |<--' 162 | Process | 163 ~~~~~~~~~~~~~~~~~>|____________|~~~~~~~~~~~~~~~~~> 164 incoming packet, forwarded packets 165 interface id, and 166 previous hop* 168 Fig. 1 - SMF Node Architecture 170 Interoperable SMF implementations MUST use a common DPD approach and 171 be able to process the header options defined in this document for 172 IPv6 operation. We define Classical Flooding (CF), as the simplest 173 case of SMF multicast forwarding. With CF, each SMF router forwards 174 each received packet once. In this case, the need for any relay set 175 selection or neighborhood topology information is eliminated but DPD 176 is still required. While CF may be used, in general practice, a form 177 of efficient relay set selection is RECOMMENDED. An efficient, 178 reduced relay set is realized by selecting a _subset_ of all possible 179 SMF routers in a MANET routing region as the forwarding relay set. 180 Known relay set selection algorithms have demonstrated the ability to 181 provide and maintain a dynamic distribution mesh for forwarding user 182 multicast data [MDC04]. A few such relay set selection algorithms 183 are described in the Appendices of this document and the basic 184 designs borrow directly from previous work. Additional relay set 185 algorithms or extensions may be specified in the future for use with 186 SMF. 188 Dynamic neighborhood topology information is needed to determine and 189 maintain an optimized set of relay (forwarding) nodes. Neighborhood 190 topology discovery functions MAY be externally provided by a MANET 191 unicast routing protocol or by using the MANET NeighborHood Discovery 192 Protocol (NHDP) [NHDP] running in concurrence with SMF. 193 Additionally, this specification does not preclude a lower protocol 194 layer from providing necessary neighborhood information. 195 Fundamentally, an SMF implementation SHOULD provide the ability for 196 multicast forwarding state to be dynamically managed per operating 197 network interface. Some of the relay state maintenance options and 198 interactions are outlined later in Section 6. This document states 199 specific requirements for neighborhood discovery with respect to the 200 forwarding process and relay set selection algorithms described 201 herein. In the absence of a MANET unicast protocol or lower layer 202 information interface, SMF relies on the MANET NHDP specification to 203 assist in 2-hop neighborhood state discovery and maintenance for 204 relay set election when not operating in a CF mode. 206 2.1. Abbreviations 208 MANET : Mobile Ad hoc Network 210 SMF : Simplified Multicast Forwarding 212 CF : Classical Flooding 214 CDS : Connected Dominating Set 216 MCDS : Minimum Connected Domination Set 218 MPR : Multi-point Relay 220 S-MPR: Source-based MPR 222 CDS-MPR: CDS-based MPR 224 E-CDS: Essential Connected Dominating Set 226 DPD: Duplicate Packet Detection 228 NHDP: Neighborhood Discovery Protocol 230 I-DPD: Identification-based Duplicate Packet Detection 232 H-DPD: Hash-based Duplicate Packet Detection 234 HAV: Hash Assist Value 236 FIB: Forwarding Information Base 238 3. Applicability 240 Within dynamic, mobile routing topologies, maintaining traditional 241 forwarding trees to support a multicast routing protocol MAY not be 242 sensible or needed. A basic packet forwarding service that reaches 243 all MANET SMF routers participating within a localized MANET routing 244 region MAY provide a useful group communication mechanism for various 245 classes of applications. Applications that could take advantage of a 246 simple multicast forwarding service within a MANET routing region 247 include multimedia streaming, interactive group-based messaging and 248 applications, peer-to-peer middleware multicasting, and multi-hop 249 mobile discovery or registration services. 251 Note again that Figure 1 provides a notional architecture for 252 _typical_ MANET SMF-capable nodes. However, a goal is that simple 253 end-system (non-forwarding) wireless nodes may also participate in 254 multicast traffic transmission and reception with standard IP network 255 layer semantics (e.g., special or unnecessary encapsulation of IP 256 packets should be avoided in this case). A multicast border router 257 or proxy mechanism MUST be used when deployed alongside more fixed- 258 infrastructure IP multicast routing such Protocol Independent 259 Multicast (PIM) variants [RFC3973] and [RFC4601]. With present 260 experimental implementations, proxy methods have demonstrated gateway 261 functionality at MANET border routers operating with external IP 262 multicast routing protocols. SMF may be extended or combined with 263 other mechanisms to provide increased reliability and group specific 264 filtering, but the details for this are not discussed here. 266 4. SMF Packet Processing and Forwarding 268 The SMF Packet Processing and Forwarding actions are conducted with 269 the following packet handling activities: 271 1. Processing of outbound, locally-generated multicast packets. 273 2. Reception and processing of inbound packets on a specific network 274 interface(s). 276 The purpose of intercepting outbound, locally-generated multicast 277 packets is to enforce any of the DPD requirements described later so 278 that proper forwarding may be conducted. 280 Inbound multicast packets will be received by the SMF implementation 281 and processed for possible forwarding. This document does not 282 presently support forwarding of directed broadcast addresses 283 [RFC2644]. SMF implementations MUST be capable of forwarding packets 284 for "global scope" multicast groups to support generic multicast 285 application needs or to distribute designated multicast traffic that 286 ingresses the MANET routing region via border routers. The set of 287 destination addresses to be forwarded will be maintained by an _a 288 priori_ list or a dynamic forwarding information base (FIB) that may 289 interact with future MANET dynamic group membership extensions. 290 There will be a well-known multicast group for flooding to all SMF 291 forwarders. This multicast group is specified to contain all MANET 292 SMF routers of a connected MANET routing region, so that packets 293 transmitted to the multicast address associated with the group will 294 be delivered to all connected SMF routers. For IPv6, the multicast 295 address is specified to be "site-local". The name of the multicast 296 group is "SL-MANET-ROUTERS". Minimally SMF SHALL forward, as 297 instructed by the relay set selection algorithm, unique (non- 298 duplicate) packets received for this well-known group address when 299 the TTL or hop count value in the IP header is greater than 1. SMF 300 SHALL forward all additional global scope addresses specified within 301 the FIB as well. In all cases, the following rules SHALL be observed 302 for SMF multicast forwarding: 304 1. Multicast packets with TTL <= 1 MUST NOT be forwarded*. 306 2. Link local multicast packets MUST NOT be forwarded. 308 3. Incoming multicast packets with an IP source address matching one 309 of those of the local SMF router interface(s) MUST NOT be 310 forwarded. 312 4. Received packet frames with the MAC source address matching the 313 local SMF router interface(s) MUST NOT be forwarded. 315 5. Received packets for which SMF cannot reasonably ensure temporal 316 DPD uniqueness MUST NOT be forwarded. 318 6. When packets are forwarded, TTL or hop limit SHALL be decremented 319 by one. 321 Note that rule #3 is important because in wireless networks, the 322 local SMF router may receive re-transmissions of its own packets when 323 they are forwarded by neighboring nodes. This rule avoids 324 unnecessary retransmission of locally-generated packets even when 325 other forwarding decision rules would apply. 327 As mentioned in Section 10, there may be concern in some SMF 328 deployments that bad-behaving nodes could conduct a denial-of-service 329 attack by remotely "previewing" (e.g., via a directional receive 330 antenna) packets that an SMF node would be forwarding and conduct a 331 "pre-play" attack by transmitting the packet before the SMF node 332 would otherwise receive it but with a reduced TTL (or Hop Limit) 333 field value. This form of attack could cause an SMF node to create a 334 DPD entry that would block the proper forwarding of the valid packet 335 (with correct TTL) through the SMF area. A RECOMMENDED approach to 336 prevent this attack, when it is a concern, would be to cache temporal 337 packet TTL values along with the DPD state (hash value(s) and/or 338 identifier). Then, if a subsequent matching (with respect to DPD) 339 packet arrives with a _larger_ TTL value than the packet that was 340 previously forwarded, then SMF should forward the new packet _and_ 341 update the TTL cached with corresponding DPD state to the new, larger 342 TTL value. There may be some isolated, temporary cases where SMF may 343 unnecessarily forward some duplicate packets using this approach, but 344 those case are expected to be exceptional. 346 Once these criteria have been met, an SMF implementation MUST examine 347 a forwarding decision algorithm to determine the next steps in packet 348 processing. If the SMF implementation is operating in a classical 349 flooding (CF) mode the forwarding decision is implicit after DPD 350 uniqueness is determined. Otherwise, a forwarding decision requires 351 additional information, including interface specific relay set state. 352 Relay set selection algorithms described later MAY be used to 353 determine the local SMF router's status with respect to forwarding. 354 Some algorithms control forwarding based on a relay set election and 355 previous hop identifier (e.g. S-MPR forwarding), while others 356 designate the local SMF router as a forwarder of all neighbor packets 357 based on the neighborhood topology (e.g. Essential CDS (E-CDS) and 358 MPR-CDS). A specific SMF node within a deployment may perform 359 redundant forwarding, but each forwarder MUST at a minimum support a 360 distributed election process that ensures a consistent dynamic CDS. 362 5. SMF Duplicate Packet Detection 364 Duplicate packet detection (DPD) is a common requirement in MANET 365 packet flooding because packets may be forwarded out the same 366 physical interface upon which they arrived and nodes may also receive 367 copies of previously-transmitted packets from other forwarding 368 neighbors. SMF implementations MUST detect and avoid forwarding 369 duplicate multicast packets using a temporal packet identification 370 scheme. It is RECOMMENDED this be implemented by keeping a history 371 of recently-processed multicast packets for comparison to incoming 372 packets. For both IPv4 and IPv6, this document describes two basic 373 approaches to multicast duplicate packet detection: header content 374 identification-based (I-DPD) and hash-based (H-DPD) duplicate 375 detection. The two approaches are described for experimental 376 purposes. Trade-offs of the two approaches to DPD may merit 377 different consideration depending upon specific SMF deployment 378 scenarios. Because of the potential addition of a hop-by-hop option 379 header with IPv6, SMF deployments MUST be configured to use a common 380 mechanism and DPD algorithm. The main difference between IPv4 and 381 IPv6 SMF DPD specification is the avoidance of any additional header 382 options or encapsulation in the IPv4 case. 384 For each network interface, SMF implementations MUST maintain DPD 385 packet state as needed to support the forwarding heuristics of the 386 relay set algorithm used. The specific requirements of several relay 387 set selection algorithms and their forwarding rules are described in 388 the Appendices of this document. In general this involves keeping 389 track of previously forwarded packets so that duplicates are not 390 forwarded, but some relay techniques (e.g., S-MPR) may have 391 additional considerations. 393 For I-DPD, packets are identified using explicit identifiers from the 394 IP header. The specific identifier to use depends upon the IP 395 protocol version and the type of packet. For example, IPv4 provides 396 an "Identification" field that may be used for DPD purposes, and 397 packets that contain IPSec protocol headers also provide a suitable 398 packet identifier. These identifier fields are unique within the 399 context of source address, destination address, protocol type, and/or 400 other header fields depending upon the type of identifier used for 401 DPD. Similarly, for H-DPD, it is expected that packet hash values 402 will be kept with respect to at least the source address to help 403 ensure hash collision avoidance. SMF implementations MUST maintain 404 DPD history per the applicable packet flow context (e.g., for DPD based upon IPv4 ID). The details for I-DPD 406 and H-DPD for different types of packets are described in the 407 sections below. In either case, this history SHOULD be kept long 408 enough to span the maximum network traversal lifetime, 409 MAX_PACKET_LIFETIME, of multicast packets being forwarded within an 410 SMF operating area. The required size of the DPD cache is governed 411 by this timeout value and is also a function of the packet forwarding 412 rates. The DPD mechanism SHOULD avoid keeping unnecessary state for 413 packet flows such as those that are locally-generated or link local 414 destinations that would not be considered for forwarding. 416 5.1. IPv6 Duplicate Packet Detection 418 This section describes the mechanisms and options for SMF IPv6 DPD. 419 The core IPv6 packet header does not provide any explicit 420 identification header field that can be exploited for I-DPD. The 421 following areas are described to support IPv6 DPD: 423 1. a hop-by-hop SMF-DPD option header (with supporting identifier or 424 hash assistance value), 426 2. the use of IPv6 fragment header fields for I-DPD when they exist, 428 3. the use of IPSec sequencing for I-DPD when a non-fragmented, 429 IPSec header is detected, and 431 4. an H-DPD approach assisted, as needed, by the SMF-DPD option 432 header. 434 SMF MUST provide a DPD marking module that can insert the hop-by-hop 435 IPv6 header option defined in this section. This process MUST come 436 after any source-based fragmentation that may occur with IPv6. As 437 with IPv4, SMF IPv6 DPD is presently specified to allow either a 438 packet hash or header identification method for DPD. An SMF 439 implementation MUST be configured to operate either in H-DPD or I-DPD 440 mode and perform the appropriate routines outlined in the following 441 sections. 443 5.1.1. IPv6 SMF-DPD Header Option 445 As previously mentioned, the base IPv6 packet header does not contain 446 a unique identifier suitable for DPD. This section defines an IPv6 447 hop-by-hop header option to serve this purpose for IPv6 I-DPD. 448 Additionally, the header option provides an opportunity to help 449 guarantee non-collision of hash values for different packets when 450 H-DPD is used. This header option format supports both of these 451 purposes. 453 The first bit of the data field of the SMF-DPD option is the "H-bit" 454 that determines the format of the data field. Two different formats 455 are supported. When the "H-bit" is cleared (zero value), the SMF-DPD 456 format to support I-DPD operation is specified as shown in Figure 5 457 and defines the extension header in accordance with [RFC2460]. 459 0 1 2 3 460 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 461 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 462 ... |0|0|0| OptType | Opt. Data Len | 463 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 464 |0|TidTyp|TidLen| TaggerId (optional) ... | 465 +-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 466 | | Identifier ... 467 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 469 Fig. 5 - IPv6 SMF-DPD Header Option in I-DPD mode 470 The "TidType" is a 3-bit field indicating the presence and type of 471 the optional "TaggerId" field. The optional "TaggerId" is used to 472 differentiate multiple ingressing border gateways that may commonly 473 apply the SMF-DPD option header to packets from a particular source. 474 This is provided for experimental purposes. The following table 475 lists the valid TaggerId types: 477 +---------+-------+-------------------------------------------------+ 478 | Name | Value | Purpose | 479 +---------+-------+-------------------------------------------------+ 480 | NULL | 0 | Indicates no "taggerId" field is present. | 481 | | | "TidLen" MUST also be set to ZERO. | 482 | | | | 483 | DEFAULT | 1 | A "TaggerId" of non-specific context is | 484 | | | present. "TidLen + 1" defines the length of | 485 | | | the TaggerId field in bytes. | 486 | | | | 487 | IPv4 | 2 | A "TaggerId" representing an IPv4 address is | 488 | | | present. The "TidLen" MUST be set to 3. | 489 | | | | 490 | IPv6 | 3 | A "TaggerId" representing an IPv6 address is | 491 | | | present. The "TidLen" MUST be set to 15. | 492 | | | | 493 | ExtId | 7 | RESERVED FOR FUTURE USE (possible extended ID) | 494 +---------+-------+-------------------------------------------------+ 496 This format allows a quick check of the "TidType" field to determine 497 if a "TaggerId" field is present. If the is NULL, then the 498 length of the DPD packet field corresponds to the ( - 1). If the is non-NULL, then the length of the 500 "TaggerId" field is equal to ( - 1) and the remainder of the 501 option data comprises the DPD packet field. When the 502 "TaggerId" field is present, the field can be considered 503 a unique packet identifier in the context of the tuple. When the "TaggerId" field is not present, then it is 505 assumed the source host applied the SMF-DPD option and the 506 can be considered unique in the context of the IPv6 507 packet header tuple. Details on IPV6 I-DPD 508 operation are described in Section 5.1.2. 510 When the "H-bit" in the SMF-DPD option data is set, the data content 511 value is interpreted as a Hash-Assist Value (HAV) used to facilitate 512 H-DPD operation. In this case, source hosts or ingressing gateways 513 apply the SMF-DPD with a HAV only when required to differentiate the 514 hash value of a new packet with respect to older packets in the 515 current DPD history cache. This helps to guarantee the uniqueness of 516 generated hash values when H-DPD is used. Additionally, this also 517 avoids the added overhead of applying the SMF-DPD option header to 518 every packet. For many hash algorithms, it is expected that only 519 sparse use of the SMF-DPD option may be required. The following 520 table illustrates the format of the SMF-DPD header option for H-DPD 521 operation: 523 0 1 2 3 524 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 525 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 526 ... |0|0|0| OptType | Opt. Data Len | 527 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 528 |0| Hash Assist Value (HAV) ... 529 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 531 Fig. 6 - IPv6 SMF-DPD Header Option in H-DPD mode 532 The SMF-DPD option should be applied with a HAV to produce a unique 533 hash digest for packets within the context of the IPv6 packet header 534 . The size of the HAV field is implied by the "Opt. Data 535 Len". The appropriate size of the field depends upon the collision 536 properties of the specific hash algorithm used. More details on IPv6 537 H-DPD operation are provided in Section 5.1.3. 539 5.1.2. IPv6 Identification-based DPD Operation 541 The following table summarizes the IPv6 I-DPD processing approach. 542 Within the table '*' indicates a don't care condition. 544 IPv6 I-DPD Processing Rules 546 +-------------+-----------+-----------+-----------------------------+ 547 | IPv6 | IPv6 | IPv6 | SMF IPv6 I-DPD Mode Action | 548 | Fragment | IPSEC | I-DPD | | 549 | Header | Header | Header | | 550 +-------------+-----------+-----------+-----------------------------+ 551 | Present | * | * | Use Fragment Header I-DPD | 552 | | | | Check and Process for | 553 | | | | Forwarding | 554 | | | | | 555 | Not Present | Present | * | Use IPSEC Header I-DPD | 556 | | | | Check and Process for | 557 | | | | Forwarding | 558 | | | | | 559 | Present | * | Present | Invalid, do not Forward | 560 | | | | | 561 | Not Present | Present | Present | Invalid, do not Forward | 562 | | | | | 563 | Not Present | Not | Not | Add I-DPD Header,and | 564 | | Present | Present | Process for Forwarding | 565 | | | | | 566 | Not Present | Not | Present | Use I-DPD Header Check and | 567 | | Present | | Process for Forwarding | 568 +-------------+-----------+-----------+-----------------------------+ 570 If the IPv6 multicast packet is an IPv6 fragment, SMF MUST use the 571 fragment extension header fields for packet identification. This 572 identifier can be considered unique in the context of the of the IP packet. If the packet is an unfragmented IPv6 574 IPSEC packet, SMF MUST use IPSec fields for packet identification. 575 The IPSec header field can be considered a unique 576 identifier in the context of the 577 where the "IPSecType" is either AH or ESP. For unfragmented, non- 578 IPSec, IPv6 packets, the use of the SMF DPD header option is 579 necessary to support I-DPD operation. The SMF DPD header option is 580 applied in the context of the of the IP packet. End 581 systems or ingressing SMF gateways are responsible for applying this 582 option to support DPD. The following table summarizes these packet 583 identification types: 585 *IPv6 I-DPD Packet Identification Types* 587 +-----------+---------------------------------+---------------------+ 588 | IPv6 | Packet DPD ID Context | Packet DPD ID | 589 | Packet | | | 590 | Type | | | 591 +-----------+---------------------------------+---------------------+ 592 | Fragment | | | 593 | | | | 594 | IPSec | | | 595 | Packet | | | 596 | | | | 597 | Regular | <[taggerId:]srcAddr:dstAddr> | | 599 +-----------+---------------------------------+---------------------+ 601 "IPSecType" is either Authentication Header (AH) or Encapsulating 602 Security Payload (ESP). 604 The "taggerId" is an optional feature of the IPv6 SMF-DPD header 605 option. 607 5.1.3. IPv6 Hash-based DPD Operation 609 A default hash-based DPD approach (H-DPD) for use by SMF is specified 610 as follows. An MD5 [RFC1321] hash of the non-mutable header fields, 611 options fields, and data content of the IPv6 multicast packet is used 612 to produce a 128-bit digest. The lower 64 bits of this digest 613 (MD5_64) is used for SMF packet identification. The approach for 614 calculating this hash value SHOULD follow the same guidelines 615 described for calculating the Integrity Check Value (ICV) described 616 in [RFC4302] with respect to non-mutable fields. This approach 617 should have a reasonably low probability of digest collision when 618 packet headers and content are varying. MD5 is being applied in SMF 619 only to provide a low probability of collision and is not being used 620 for cryptographic or authentication purposes. A history of the 621 packet hash values SHOULD be maintained within the context of the 622 IPv6 packet header . This history is used by forwarding SMF 623 nodes (non-ingress points) to avoid forwarding duplicates. SMF 624 ingress points (i.e., source hosts or gateways) use this history to 625 confirm that new packets are unique with respect to their hash value. 626 The Hash-assist Value (HAV) field described in Section 5.1.1 is 627 provided as a differentiating field when a digest collision would 628 otherwise occur. Note that the HAV is an immutable option field and 629 SMF MUST use any included H-DPD hash assist value (HAV) option header 630 (see Section 5.1.1) in its hash calculation. 632 If a packet results in a digest collision (i.e., by checking the 633 H-DPD digest history) within the limited history kept by SMF 634 forwarders, the packet should be silently dropped. If a digest 635 collision is detected at an SMF ingress point (i.e., including SMF- 636 aware sources), the H-DPD option header is applied with a HAV. The 637 packet is retested for collision and the HAV is re-applied as needed 638 to produce a non-colliding hash value. The multicast packet is then 639 forwarded with the added IPv6 SMF-DPD header option. 641 The MD5 indexing and IPv6 HAV approaches are specified at present for 642 consistency and robustness to suit experimental application. Future 643 approaches and experimentation may discover designs tradeoffs in hash 644 robustness and efficiency worth considering. This MAY include 645 reducing the maximum payload length that is processed, determining 646 shorter indexes, or applying more efficient hashing algorithms. Use 647 of the HAV may allow for application of "lighter-weight" hashing 648 techniques that might have been not considered due to poor collision 649 properties otherwise. 651 5.2. IPv4 Duplicate Packet Detection 653 This section describes the mechanisms and options for IPv4 DPD. The 654 IPv4 packet header 16-bit "Identification" field MAY be used for DPD, 655 but its limitations may require alternative approaches in some 656 situations. The following areas are described to support IPv4 DPD:: 658 1. the use of IPv4 fragment header fields for I-DPD when they exist, 660 2. the use of IPSec sequencing for I-DPD when a non-fragmented IPv4 661 IPSec packet is detected, and 663 3. a H-DPD approach. 665 A specific SMF-DPD marking option is not specified for IPv4 since 666 header options are not as tractable for end systems as for IPv6. 667 IPv4 packets from a particular source are assumed to be marked with a 668 temporally unique value in the "Identification" field of the packet 669 header that can serve for SMF DPD purposes. However, in present 670 operating system networking kernels, the IPv4 header "Identification" 671 value is not always generated properly, especially when the "don't 672 fragment" (DF) bit is set. The IPv4 I-DPD mode of this specification 673 requires that IPv4 "Identification" fields are managed reasonably by 674 source hosts and that temporally unique values are set within the 675 context of the packet header tuple. If 676 this is not expected during an SMF deployment, then it is RECOMMENDED 677 that the H-DPD method be used as a more reliable approach. 679 Since IPv4 SMF does not specify an options header, the 680 interoperability constraints are looser than the IPv6 version and 681 forwarders may be operate with mixed H-DPD and I-DPD modes as long as 682 they consistently perform the appropriate DPD routines outlined in 683 the following sections. However, it is RECOMMENDED that a deployment 684 be configured with a common mode for operational consistency. 686 5.2.1. IPv4 Identification-based DPD Operation 688 The following table summarizes the IPv4 I-DPD processing approach 689 once a packet has passed the basic forwardable criteria described in 690 earlier SMF sections. Within the table '*' indicates a don't care 691 condition. 693 +----+----+----------+---------+------------------------------------+ 694 | df | mf | fragment | IPSEC | IPv4 I-DPD Action | 695 | | | offset | | | 696 +----+----+----------+---------+------------------------------------+ 697 | 1 | 1 | * | * | Invalid, Do Not Forward | 698 | | | | | | 699 | 1 | 0 | nonzero | * | Invalid, Do Not Forward | 700 | | | | | | 701 | * | 0 | zero | not | Tuple I-DPD Check and Process for | 702 | | | | Present | Forwarding | 703 | | | | | | 704 | * | 0 | zero | Present | IPSEC enhanced Tuple I-DPD Check | 705 | | | | | and Process for Forwarding | 706 | | | | | | 707 | 0 | 0 | nonzero | * | Extended Fragment Offset Tuple | 708 | | | | | I-DPD Check and Process for | 709 | | | | | Forwarding | 710 | | | | | | 711 | 0 | 1 | zero or | * | Extended Fragment Offset Tuple | 712 | | | nonzero | | I-DPD Check and Process for | 713 | | | | | Forwarding | 714 +----+----+----------+---------+------------------------------------+ 716 For performance reasons, IPv4 network fragmentation and reassembly of 717 multicast packets within wireless MANET networks should be minimized, 718 yet SMF provides the forwarding of fragments when they occur. If the 719 IPv4 multicast packet is a fragment, SMF MUST use the fragmentation 720 header fields for packet identification. This identification can be 721 considered temporally unique in the context of the of the IPv4 packet. If the packet is an unfragmented IPv4 723 IPSEC packet, SMF MUST use IPSec fields for packet identification. 724 The IPSec header field can be considered a unique 725 identifier in the context of the 726 where the "IPSecType" is either AH or ESP. Finally, for 727 unfragmented, non-IPSec, IPv4 packets, the "Identification" field can 728 be used for I-DPD purposes. The "Identification" field can be 729 considered unique in the context of the IPv4 tuple. The following table summarizes these packet 731 identification types: 733 *IPv4 I-DPD Packet Identification Types* 735 +-----------+---------------------------------+---------------------+ 736 | IPv4 | Packet Identification Context | Packet Identifier | 737 | Packet | | | 738 | Type | | | 739 +-----------+---------------------------------+---------------------+ 740 | Fragment | | | 741 | | | | 742 | IPSec | | | 743 | Packet | | | 744 | | | | 745 | Regular | | | 746 | Packet | | | 747 +-----------+---------------------------------+---------------------+ 749 "IPSecType" is either Authentication Header (AH) or Encapsulating 750 Security Payload (ESP). 752 The limited size (16 bits) of the IPv4 header "Identification" field 753 may result in the value rapidly wrapping, particularly if a common 754 sequence space is used by a source for multiple destinations. If 755 I-DPD operation is required, the use of the "internal hashing" 756 technique described in Section 5.3 may mitigate this limitation of 757 the IPv4 "Identification" field for SMF DPD. In this case the 758 "internal hash" value would be concatenated with the "Identification" 759 value for I-DPD operation. 761 5.2.2. IPv4 Hash-based DPD Operation 763 To ensure consistent IPv4 H-DPD operation among SMF nodes, a default 764 hashing approach is specified. This is similar to that specified for 765 IPv6, but the H-DPD header option with HAV is not considered. SMF 766 MUST perform an MD5 [RFC1321] hash of the immutable header fields, 767 option fields and data content of the IPv4 multicast packet resulting 768 in a 128-bit digest. The lower 64 bits of this digest (MD5_64) is 769 used for SMF packet identification. The approach for calculating the 770 hash value SHOULD follow the same guidelines described for 771 calculating the Integrity Check Value (ICV) described in [RFC4302] 772 with respect to non-mutable fields. A history of the packet hash 773 values SHOULD be maintained in the context of . The context for IPv4 is more specific than that of IPv6 775 since the SMF-DPD HAV cannot be employed to mitigate hash collisions. 777 The MD5 hash is specified at present for consistency and robustness. 778 Future approaches and experimentation may discover designs tradeoffs 779 in hash robustness and efficiency worth considering for future 780 versions of SMF. This MAY include reducing the packet payload length 781 that is processed, determining shorter indexes, or applying a more 782 efficient hashing algorithm. 784 5.3. Internal Hash Computation 786 Forwarding protocols that use DPD techniques, such as SMF, may be 787 vulnerable to denial-of-service (DoS) attacks based on spoofing 788 packets with apparently valid packet identifier fields. Such a 789 consideration is pointed out in Section 10. In wireless environments 790 where SMF will most likely be used, the opportunity for badly- 791 behaving nodes to conduct such attacks is more prevalent than in 792 wired networks. In the case of IPv4 packets, fragmented IP packets 793 or packets with IPSec headers applied, the DPD "identifier" of 794 potential future packets that might be forwarded is very predictable 795 and easily subject to denial-of-service attacks against forwarding. 796 A RECOMMENDED technique to counter this concern is for SMF 797 implementations to generate an "internal" hash value that is 798 concatenated with the explicit I-DPD packet identifier to form a 799 unique identifier that is a function of the packet content as well as 800 the visible identifier. SMF implementations could seed their hash 801 generation with a random value to make it unlikely that an external 802 observer could guess how to spoof packets used in a denial-of-service 803 attack against forwarding. Since the hash computation and state is 804 kept completely internal to SMF nodes, the cryptographic properties 805 of this hashing would not need to be extensive and thus possibly of 806 low complexity. Experimental implementations may determine that a 807 lightweight hash of even only portions of packets may suffice to 808 serve this purpose. 810 For IPv4 I-DPD based on the limited 16-bit "Identification" field, it 811 is possible that use of this "internal hash" technique may also 812 enhance I-DPD performance in cases where the IPv4 "Identification" 813 field may wrap quickly due to the source supporting high data rate 814 flows. 816 While H-DPD is not as readily susceptible to this form of DoS attack, 817 it is possible that a sophisticated adversary could use side 818 information to construct spoofing packets to mislead forwarders using 819 a well-known hash algorithm. Thus, similarly, a separate "internal" 820 hash value could be concatenated with the well-known hash value to 821 alleviate this security concern. 823 6. Reduced Relay Set Forwarding and Relay Selection Capability 825 SMF MUST support CF-based forwarding as a basic forwarding mechanism 826 when reduced relay set information is not available or not selected 827 for operation. In CF mode, each node transmits a locally generated 828 or newly received packet exactly once. The DPD techniques described 829 in Section 5 are critical to proper operation and prevent duplicate 830 packet retransmissions by the same forwarding node. 832 A goal of SMF is to apply reduced relay sets for more efficient 833 multicast dissemination within dynamic topologies. To accomplish 834 this SMF MUST support the ability to modify its multicast packet 835 forwarding rules based upon relay set state received dynamically 836 during operation. In this way, SMF forwarding can continue to 837 operate effectively as neighbor adjacencies or multicast forwarding 838 policies within the topology change. 840 In early SMF experimental deployments, the relay set information has 841 been derived from a coexistent unicast MANET protocol calculation of 842 a reduced relay set for control plane traffic. From this experience, 843 extra pruning considerations are sometimes required when utilizing a 844 relay set from a independent routing protocol process, since a relay 845 set formed for the unicast control plane flooding MAY include a more 846 redundant set of nodes than desired for multicast forwarding use 847 (e.g., biconnected control plane CDS meshes). 849 Here is a recommended criteria list for relay set selection algorithm 850 candidates: 852 1. Robustness to topological dynamics and mobility 854 2. Localized election or coordination of any relay sets 856 3. Heuristic support for preference or election metrics (Better 857 enables scenario-specific management of relay set) 859 Some relay set algorithms meeting these criteria are described in the 860 Appendices of this document. Different algorithms may be more 861 suitable for different MANET routing types or deployments. 862 Additional relay set selection algorithms may be specified in 863 separate specifications in the future. The Appendices in this 864 document can serve as a template for the content of such potential 865 future specifications. 867 Figure 7 depicts a state information diagram of possible relay set 868 control options. There are basically three style of SMF operation 869 with reduced relay sets as follows. 871 1. Unicast dependent operation with a coexisting MANET unicast 872 routing protocol in which the relay set state is derived from the 873 unicast control plane CDS information. 875 2. Unicast independent operation in which SMF performs its own Relay 876 Set Selection and derives dynamic neighborhood information from a 877 MANET NHDP process. In this case, additional TLV definitions for 878 related CDS collection SHOULD be used as discussed in Section 7. 880 3. Possible crosslayer implementation that uses L2 neighborhood 881 information and possible triggers to assist the dynamic relay set 882 selection and maintenance process. 884 Possible L2 Trigger/Information 885 | 886 | 887 ______________ _______v_____ __________________ 888 | MANET | | | | | 889 | Neighborhood | | Relay Set | | Other Heuristics | 890 | Discovery |------------->| Selection |<------| (Preference,etc) | 891 | Protocol | neighbor | Algorithm | | | 892 |______________| info |_____________| |__________________| 893 \ / 894 \ / 895 neighbor\ / Dynamic Relay 896 info* \ ____________ / Set Status 897 \ | SMF | / (State, {neighbor info}) 898 `-->| Relay Set |<--' 899 | State | 900 -->|____________| 901 / 902 / 903 ______________ 904 | Coexistent | 905 | MANET | 906 | Unicast | 907 | Process | 908 |______________| 910 Fig. 7 - SMF Relay Set Control Options 912 7. SMF Neighborhood Discovery Requirements 914 In absence of a compatible, coexisting unicast routing protocol or 915 lower layer protocol providing neighborhood topology information 916 sufficient for relay set selection, this section defines the issues 917 and additional requirements for a MANET Neighborhood Discovery 918 Protocol (NHDP) that MAY be used by SMF nodes. 920 With respect to neighborhood topology knowledge and/or discovery, 921 there are three basic modes of SMF operation: 923 1. Classical Flooding (CF) mode: with no requirements for discovery 924 or knowledge of neighborhood topology, 926 2. External CDS control mode: an external process dynamically 927 determines the local SMF relay status (e.g., SMF prototypes have 928 leveraged neighborhood topology information collected by MANET 929 unicast routing protocol instantiations), and 931 3. Independent CDS control mode: SMF uses the MANET Neighborhood 932 Discovery Protocol (NHDP) [NHDP] to collect localized link 933 information required for the various CDS algorithm modes 934 discussed in the Appendices. 936 Core NHDP messages and the neighborhood information base are 937 described separately within the NHDP specification (IETF work in 938 progress). In this mode, SMF uses and relies upon an implementation 939 of NHDP. The NHDP protocol provides the following basic functions: 941 1. 1-hop Neighbor link sensing: maintaining neighbor lists and 942 performing bidirectionality checks of neighbor links 944 2. 2-hop Neighborhood Discovery: collecting 2-hop bidirectional 945 neighborhood information and any information relevant to relay 946 set election 948 3. The collection and maintenance of the above information across 949 multiple interfaces. 951 4. Relay Set Signaling: signal relay set selection to neighbor nodes 952 if the relay set algorithm requires such information 954 The Appendices discuss a set of implemented SMF CDS approaches that 955 may be needed by an NHDP implementation to support each approach. 956 The following subsections define TLVs consistent with [PacketBB]that 957 SHOULD be used when deploying SMF in Independent CDS control mode. 959 7.1. SMF Relay Set Algorithm ID Message TLV 961 The following TLV, SMF_RELAYALG_ID, is used within NHDP messages to 962 provide an indicator of the operating relay set selection algorithm. 963 When NHDP messages are used by SMF for independent CDS control mode a 964 SMF_RELAYALG_ID TLV SHOULD be included. Nodes receiving a NHDP 965 message with a SMF_RELAYALG_ID value differing from its own type the 966 entire message SHOULD NOT be used for relay set processing. 968 type=SMF_RELAYALG_ID, length=1 byte, value = 970 is an 8 bit value identifying the present relay algorithm of the 971 SMF node represented by the originator address of the NHDP message. 973 Values are defined in Table 6. The table provides present value 974 assignments, future IANA reserved space, and an experimental space. 975 Experimental space use MUST not assume uniqueness properties and 976 should be used only for experimentation prior to any IANA 977 assignment.. 979 +---------------------+----------------------------------------+ 980 | Value | Algorithm | 981 +---------------------+----------------------------------------+ 982 | 0 | S-MPR | 983 | | | 984 | 1 | E-CDS | 985 | | | 986 | 2 | MPR-CDS | 987 | | | 988 | 3-127 | Reserved for Future Assignment | 989 | | | 990 | 128-255 | Experimental Space | 991 +---------------------+----------------------------------------+ 993 Table 6 995 7.2. Router Priority Message TLV 997 For some relay set election operations, a value of Router Priority 998 (RtrPri) must be given or assumed for each address with the two-hop 999 neighborhood which is consistent for all nodes. More specific 1000 discussions are provided in the Appendices. 1002 The following TLV communicates router priority values among 1-hop 1003 router neighbors. 1005 type=SMF_RTR_PRI, length=1 byte, value = 1006 is an 8 bit field which contains a number 0-255 which 1007 represents RtrPri value of the node represented by the originator 1008 address of the NHDP message. 1010 Message TLVs of type SMF_RTR_PRI SHOULD only be used within NHDP 1011 messages. 1013 7.3. Router Priority Address Block TLV 1015 For some relay set election operations, a value of Router Priority 1016 (RtrPri) must be given or assumed for each address with the two-hop 1017 neighborhood that is consistent for all nodes. More specific 1018 discussions are provided in the Appendices. 1020 The following TLV is defined to support the communication of router 1021 priority values between 2-hop router neighbors. When generating 1022 address block TLV router priority messages the RtrPri values included 1023 MUST be consistent with advertised values contained within previously 1024 received router priority message TLVs. 1026 type=SMF_RTR_PRI, length= bytes, value = 1028 is the number of addresses which the TLV applies to. 1029 This value MUST be consistent with the TLV semantics, length, and 1030 index fields. 1032 is a single or multivalue field containing a 1033 value field for each node represented by the address(es) the TLV 1034 applies to. 1036 +---------------------+-------+-------------------------------------+ 1037 | Mnemonic | Value | Description | 1038 +---------------------+-------+-------------------------------------+ 1039 | SMF_ALGORITHM_ID | TBD | A message TLV which contains the an | 1040 | | | id value representing the algorithm | 1041 | | | being used by the originator | 1042 | | | address in the NHDP message | 1043 | | | | 1044 | SMF_ROUTER_PRIORITY | TBD | A message TLV or address block TLV | 1045 | | | which contains a router priority | 1046 | | | value for each node represented by | 1047 | | | the associated address(es). | 1048 +---------------------+-------+-------------------------------------+ 1050 Table 7 1052 8. SMF Border Gateway Considerations 1054 It is expected that SMF will be used to provide simple forwarding of 1055 multicast traffic _within_ a MANET mesh routing topology. A border 1056 router approach should be used to allow interconnection of SMF areas 1057 with networks using other multicast routing protocols (e.g., PIM). 1058 It is important to note that there are many scenario-specific issues 1059 that should be addressed when discussing border routers. At the 1060 present time, experimental deployments of SMF and PIM border router 1061 approaches are being used. 1063 Some of the functionality border routers may need to address include 1064 the following: 1066 1. Determining which multicast groups should transit the border 1067 router whether entering or exiting the attached MANET routing 1068 region(s). 1070 2. Enforcement of TTL threshold or other scoping policies. 1072 3. Any marking or labeling to enable DPD on ingressing packets. 1074 4. Interface with exterior multicast routing protocols. 1076 5. Possible operation with multiple border routers (presently beyond 1077 scope of this document). 1079 6. Provisions for participating non-SMF nodes. 1081 Note the behavior of border router SMF nodes is the same as that of 1082 non-border SMF nodes when forwarding packets on interfaces within the 1083 MANET routing region. Packets that are passed outbound to interfaces 1084 operating fixed-infrastructure multicast routing protocols SHOULD be 1085 evaluated for duplicate packet status since present standard 1086 multicast forwarding mechanisms do not usually perform this function. 1088 8.1. Forwarded Multicast Groups 1090 Determining which groups should be forwarded into a MANET SMF routing 1091 region is an evolving technology area. Ideally, only groups for 1092 which there is active group membership should be injected into the 1093 SMF domain. This might be accomplished by providing an IPv4 Internet 1094 Group Membership Protocol (IGMP) or IPV6 Multicast Listener Discovery 1095 (MLD) proxy protocol so that MANET SMF nodes can inform attached 1096 border routers (and hence multicast networks) of their current group 1097 membership status. For specific systems and services it may be 1098 possible to statically configure group membership joins in border 1099 routers, but it is RECOMMENDED that some form of IGMP/MLD proxy or 1100 other explicit, dynamic control of membership be provided. 1101 Specification of such an IGMP/MLD proxy protocol is beyond the scope 1102 of this document. 1104 Outbound traffic is less problematic. SMF border routers can perform 1105 duplicate packet detection and forward non-duplicate traffic that 1106 meets TTL/hop limit and scoping criteria to other interfaces. 1107 Appropriate IP multicast routing (PIM, etc) on those interfaces can 1108 then make further forwarding decisions with respect to the given 1109 traffic and its MANET source address. Note that the presence of 1110 multiple border routers associated with a MANET routing region may 1111 create some additional issues. This is further discussed in 1112 Section 8.4. 1114 8.2. Multicast Group Scoping 1116 Multicast scoping is used by network administrators to control the 1117 network routing regions which are reached by multicast packets. This 1118 is usually done by configuring external interfaces of border routers 1119 in the border of an routing region to not forward multicast packets 1120 which must be kept within the routing region. This is commonly done 1121 based on TTL of messages or the basis of group addresses. These 1122 schemes are known respectively as: 1124 1. TTL scoping. 1126 2. Administrative scoping. 1128 For IPv4, network administrators can configure border routers with 1129 the appropriate TTL thresholds or administratively scoped multicast 1130 groups in the router's interfaces as with any traditional multicast 1131 router. However, for the case of TTL scoping it must be taken into 1132 account that the packet could traverse multiple hops within the MANET 1133 SMF routing region before reaching the border router. Thus, TTL 1134 thresholds must be selected carefully. 1136 For IPv6, multicast address spaces include information about the 1137 scope of the group. Thus, border routers of an SMF routing region 1138 know if they must forward a packet based on the IPv6 multicast group 1139 address. For the case of IPv6, it is RECOMMENDED that a MANET SMF 1140 routing region be designated a site. Thus, all IPv6 multicast 1141 packets in the range FF05::/16 SHOULD be kept within the MANET SMF 1142 routing region by border routers. IPv6 packets in any other wider 1143 range scopes (i.e. FF08::/16, FF0B::/16 and FF0E::16) MAY traverse 1144 border routers unless other restrictions different from the scope 1145 applies. 1147 Given that scoping of multicast packets is performed at the border 1148 routers, and given that existing scoping mechanisms are not designed 1149 to work with mobile routers, it is assumed that non-border SMF 1150 routers will not stop forwarding multicast data packets because of 1151 their scope. That is, it is assumed that the entire MANET SMF 1152 routing region is a non-divisible scoping area except in the case of 1153 link-local addresses that are not forwarded by SMF. 1155 8.3. Interface with Exterior Multicast Routing Protocols 1157 The traditional operation of multicast routing protocols is tightly 1158 integrated with the group membership function. Leaf routers are 1159 configured to periodically gather group membership information, while 1160 intermediate routers conspire to create multicast trees connecting 1161 routers with directly-connected multicast sources and routers with 1162 active multicast receivers. In the concrete case of SMF, border 1163 routers can be considered leaf routers. Mechanisms for multicast 1164 sources and receivers to interoperate with border routers over the 1165 multihop MANET SMF routing region as if they were directly connected 1166 to the router need to be defined. The following issues need to be 1167 addressed: 1169 1. Mechanism by which border routers gather membership information. 1171 2. Mechanism by which multicast sources are known by the border 1172 router. 1174 3. Exchange of exterior routing protocol messages across the MANET 1175 routing region if the MANET routing region is to provide transit 1176 connectivity for multicast traffic. 1178 It is beyond the scope of this document to address implementation 1179 solutions to these issues. As described in Section 8.1, IGMP/MLD 1180 proxy mechanisms can be deployed to address some of these issues. 1181 Similarly, exterior routing protocol messages could be tunneled or 1182 conveyed across the MANET routing region. But, because MANET routing 1183 regions are multi-hop and potentially unreliable, as opposed to the 1184 single-hop LAN interconnection that neighboring IP Multicast routers 1185 might typically enjoy, additional provisions may be required to 1186 achieve successful operation. 1188 The need for the border router to receive traffic from recognized 1189 multicast sources within the MANET SMF routing region is important to 1190 achieve a smooth interworking with existing routing protocols. For 1191 instance, PIM-S requires routers with locally attached multicast 1192 sources to register them to the Rendezvous Point (RP) so that other 1193 people can join the multicast tree. In addition, if those sources 1194 are not advertised to other autonomous systems (AS) using MSDP, 1195 receivers in those external networks are not able to join the 1196 multicast tree for that source. 1198 8.4. Multiple Border Routers 1200 A MANET might be deployed with multiple participating nodes having 1201 connectivity to external (to the MANET), fixed-infrastructure 1202 networks. Allowing multiple nodes to forward multicast traffic to/ 1203 from the MANET routing region can be beneficial since it can increase 1204 reliability, and provide better service. For example, if the MANET 1205 routing region were to fragment with different MANET nodes 1206 maintaining connectivity to different border routers, multicast 1207 service could still continue successfully. But, the case of multiple 1208 border routers connecting a MANET routing region to external networks 1209 presents several challenges for SMF: 1211 1. Detection/hash collision/sequencing of duplicate unmarked IPv4 or 1212 IPv6 (without IPSec encapsulation or DPD option) packets possibly 1213 injected by multiple border routers. 1215 2. Source-based relay algorithms handling of duplicate traffic 1216 injected by multiple border routers. 1218 3. Determination of which border router(s) will forward outbound 1219 multicast traffic. 1221 4. Additional challenges with interfaces to exterior multicast 1222 routing protocols. 1224 One of the most obvious issues is when multiple border routers are 1225 present and may be alternatively (due to route changes) or 1226 simultaneously injecting common traffic into the MANET routing region 1227 that has not been previously marked for SMF DPD. Different border 1228 routers would not be able to implicitly synchronize sequencing of 1229 injected traffic since they may not receive exactly the same messages 1230 due to packet losses. For IPv6 I-DPD operation, the optional 1231 "TaggerId" field described for the SMF-DPD header option can be used 1232 to mitigate this issue. When multiple border routers are injecting a 1233 flow into a MANET routing region, there are two forwarding policies 1234 that SMF DPD-S nodes may implement: 1236 1. Redundantly forward the multicast flows (identified by 1237 ) from each border router, 1238 performing DPD processing on a or 1239 basis, or 1241 2. Use some basis to select the flow of one tagger (border router) 1242 over the others and forward packets for applicable flows 1243 (identified by ) only for that 1244 "Tagger ID" until timeout or some other criteria to favor another 1245 tagger occurs. 1247 It is RECOMMENDED that the first approach be used in the case of 1248 I-DPD operation unless the SMF system is specifically designed to 1249 implement the second option. Additional specification may be 1250 required to describe an interoperable forwarding policy based on this 1251 second option. Note that the implementation of the second option 1252 requires that per-flow (i.e., ) 1253 state be maintained for the selected "Tagger ID". 1255 The deployment of a H-DPD operational mode may alleviate DPD 1256 resolution when ingressing traffic comes from multiple border 1257 routers. Non-colliding hash indexes (those not requiring the H-DPD 1258 options header in IPv6) should be resolved effectively. 1260 9. Non-SMF MANET Node Interaction 1262 There may be scenarios in which some neighboring wireless MANET node 1263 is not running SMF and/or conduct forwarding, but is interested in 1264 receiving multicast data. For example, a MANET service might be 1265 deployed that is accessible to wireless edge devices that does not 1266 participate in MANET routing and/or SMF forwarding operation. These 1267 devices include: 1269 1. Devices that opportunistically receive multicast traffic due to 1270 proximity with SMF relays (possibly with asymmetric IP 1271 connectivity e.g., sensor network device). 1273 2. Devices that participate in NHDP (directly or via routing 1274 protocol signaling) but do not forward traffic. 1276 Note there is no guarantee of traffic delivery with category 1 above, 1277 but the election heuristics shown in Figure 2 may be adjusted via 1278 management to better support such devices. It is RECOMMENDED that 1279 nodes participate in NHDP when possible. Such devices may also 1280 transmit multicast traffic, but it is important to note that SMF 1281 routing regions using source-specific relay set algorithms such as 1282 (S-MPR) may not forward such traffic. These devices SHOULD also 1283 listen for any IGMP/MLD Queries that are provided and transmit IGMP/ 1284 MLD Reports for groups they have joined per usual IP Multicast 1285 operation. While it is not in the scope of this document, IGMP/MLD 1286 proxy mechanisms may be in place to convey group membership 1287 information to any border routers or intermediate systems providing 1288 IP Multicast routing functions. 1290 10. Security Considerations 1292 Gratuitous use of option headers can cause problems in routers. 1293 Routers outside of MANET routing regions should ignore SMF-specific 1294 header options if encountered. The header options types are encoded 1295 appropriately for this behavior. 1297 Sequence-based packet identifiers are predictable and thus provide an 1298 opportunity for a denial-of-service attack against forwarding. The 1299 use of the "internal hashing" as described in Section 5.3 for the 1300 I-DPD operation helps to mitigate denial-of-service attacks on 1301 predictable packet identifiers. In this case, spoofed packets MAY be 1302 forwarded but the additional internal history identifier will protect 1303 against false collision events that may result from a predictive 1304 denial-of-service attack. 1306 Another potential denial-of-service attack against SMF forwarding is 1307 possible when a bad-behaving node has a form of "wormhole" access 1308 (via a directional antenna, etc) to preview packets before a 1309 particular SMF node would receive them. The bad-behaving node could 1310 reduce the TTL or Hop Limit of the packet and transmit it to the SMF 1311 node causing it to forward the packet with a limited TTL (or even 1312 drop it) and make a DPD entry that would block forwarding of the 1313 subsequently-arriving valid packet with appropriate TTL value. This 1314 would be a relatively low-cost, high-payoff attack that would be hard 1315 to detect and thus attractive to potential attackers. An approach of 1316 caching TTL information with DPD state and taking appropriate 1317 forwarding actions is identified in Section 4 to mitigate this form 1318 of attack. 1320 The support of forwarding non-fragmented IPSEC datagrams without 1321 further modification for both IPv4 and IPv6 is supported by this 1322 specification. 1324 Authentication mechanisms to identify the source of IPv6 option 1325 headers should be considered to reduce vulnerability to a variety of 1326 attacks. 1328 11. IANA Considerations 1330 There are number of discussions within this SMF specification that 1331 will be subject to IANA registration and consideration. The IPv6 1332 SMF-DPD hop-by-hop Header Extension being defined within this 1333 document MUST have an IANA registry established upon publication of 1334 the first RFC. Additionally, well-known site-scoped multicast 1335 addresses intended as default forwardable addresses by the SMF 1336 forwarding process for both IPv4 and IPv6 should be registered and 1337 defined by the first RFC published. Also, SMF specific TLV types and 1338 definitions MUST be registered in the context of packetbb and NHDP 1339 use. 1341 12. Acknowledgments 1343 Many of the concepts and mechanisms used and adopted by SMF resulted 1344 from many years of discussion and related work within the MANET WG 1345 since the late 1990s. There are obviously many contributors to past 1346 discussions and related draft documents within the WG that have 1347 influenced the development of SMF concepts that deserve 1348 acknowledgment. In particular, the document is largely a direct 1349 product of the earlier SMF design team within the IETF MANET WG and 1350 borrows text and implementation ideas from the related individuals. 1351 Some of the contributors who have been involved in design, content 1352 editing, prototype implementation, and core discussions are listed 1353 below in alphabetical order. We appreciate input from many others we 1354 may have missed in this list as well. 1356 Design contributors in alphabetical order: 1358 Brian Adamson 1360 Teco Boot 1362 Ian Chakeres 1364 Thomas Clausen 1366 Justin Dean 1368 Brian Haberman 1370 Charles Perkins 1372 Pedro Ruiz 1374 Fred Templin 1376 Maoyu Wang 1378 The RFC text was produced using Marshall Rose's xml2rfc tool and Bill 1379 Fenner's XMLmind add-ons. 1381 13. References 1383 13.1. Normative References 1385 [E-CDS] Ogier, R., "MANET Extension of OSPF Using CDS Flooding", 1386 Proceedings of the 62nd IETF , March 2005. 1388 [MPR-CDS] Adjih, C., Jacquet, P., and L. Viennot, "Computing 1389 Connected Dominating Sets with Multipoint Relays", Ad Hoc 1390 and Sensor Wireless Networks , January 2005. 1392 [NHDP] Clausen, T. and et al, "Neighborhood Discovery Protocol", 1393 draft-ietf-manet-ndp-00, Work in progress , July 2006. 1395 [OLSRv2] Clausen, T. and et al, "Optimized Link State Routing 1396 Protocol version 2", draft-ietf-manet-olsrv2-00, Work in 1397 progress , March 2006. 1399 [PacketBB] 1400 Clausen, T. and et al, "Generalized MANET Packet/Message 1401 Format", draft-ietf-manet-packetbb-00, Work in progress , 1402 March 2006. 1404 [RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791, 1405 September 1981. 1407 [RFC1321] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, 1408 April 1992. 1410 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1411 Requirement Levels", BCP 14, RFC 2119, March 1997. 1413 [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 1414 (IPv6) Specification", RFC 2460, December 1998. 1416 [RFC2644] Senie, D., "Changing the Default for Directed Broadcasts 1417 in Routers", BCP 34, RFC 2644, August 1999. 1419 [RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing 1420 Protocol", 2003. 1422 [RFC4302] Kent, S., "IP Authentication Header", December 2005. 1424 13.2. Informative References 1426 [GJ79] Garey, M. and D. Johnson, "Computers and Intractability: A 1427 Guide to the Theory of NP-Completeness.", Freeman and 1428 Company , 1979. 1430 [JLMV02] Jacquet, P., Laouiti, V., Minet, P., and L. Viennot, 1431 "Performance of multipoint relaying in ad hoc mobile 1432 routing protocols", Networking , 2002. 1434 [MDC04] Macker, J., Dean, J., and W. Chao, "Simplified Multicast 1435 Forwarding in Mobile Ad hoc Networks", IEEE MILCOM 2004 1436 Proceedings , 2004. 1438 [MDDA07] Macker, J., Downard, I., Dean, J., and R. Adamson, 1439 "Evaluation of distributed cover set algorithms in mobile 1440 ad hoc network for simplified multicast forwarding", ACM 1441 SIGMOBILE Mobile Computing and Communications Review 1442 Volume 11 , Issue 3 (July 2007), July 2007. 1444 [NTSC99] Ni, S., Tseng, Y., Chen, Y., and J. Sheu, "The Broadcast 1445 Storm Problem in Mobile Ad hoc Networks", Proceedings Of 1446 ACM Mobicom 99 , 1999. 1448 [RFC2901] Macker, JP. and MS. Corson, "Mobile Ad hoc Networking 1449 (MANET): Routing Protocol Performance Issues and 1450 Evaluation Considerations", 1999. 1452 [RFC3684] Ogier, R., Templin, F., and M. Lewis, "Topology 1453 Dissemination Based on Reverse-Path Forwarding", 2003. 1455 [RFC3973] Adams, A., Nicholas, J., and W. Siadak, "Protocol 1456 Independent Multicast - Dense Mode (PIM-DM): Protocol 1457 Specification (Revised)", RFC 3973, January 2005. 1459 [RFC4601] Fenner, B., Handley, M., Holbrook, H., and I. Kouvelas, 1460 "Protocol Independent Multicast - Sparse Mode (PIM-SM): 1461 Protocol Specification (Revised)", RFC 4601, August 2006. 1463 [WC02] Williams, B. and T. Camp, "Comparison of Broadcasting 1464 Techniques for Mobile Ad hoc Networks", Proceedings of ACM 1465 Mobihoc 2002 , 2002. 1467 Appendix A. Reduced Relay Set Forwarding Algorithms and Considerations 1469 This Appendix discusses candidate SMF reduced relay set algorithms 1470 that have been used in practice. Basic algorithm operation is 1471 described along with related issues (e.g., TLV use). 1473 The following definitions are used to describe algorithm operation 1474 within sections to follow. 1476 node : A MANET router operating SMF. 1478 n_0 : The node performing the SMF algorithm computation. 1480 N_1 : A set of 1-hop neighbors of n_0. Initially set to all 1-hop 1481 neighbors. 1483 N_2 : A set of 2-hop neighbors reachable by n_0, excluding n_0 and 1484 all nodes in N_1. Initially set to all 2-hop neighbors excluding 1485 n_0 and all nodes in N_1. 1487 N_2(y) : The subset of N_2 nodes which are 1-hop neighbors of node 1488 y, where node y is in N_1. 1490 N_1(z) : The subset of N_1 nodes which are 1-hop neighbors of node 1491 z, where z is in N_2. 1493 RtrPri : an expression of router priority. In the case of a 1494 RtrPri value tie, higher address values are equivalent to a higher 1495 priority value result. 1497 rp_max_1 : The node with the largest RtrPri of N_1. 1499 MPRs : The subset of N_1 which have been selected by n_0 to 1500 forward packets from n_0. 1502 MPR-Selectors : The subset of N_1 for whom n_0 has been selected 1503 to forward packets. 1505 Appendix B. Source-based Multipoint Relay (S-MPR) 1507 The source-based multipoint relay (S-MPR) set selection algorithm 1508 enables individual nodes, using two-hop topology information, to 1509 select relays from their set of neighboring nodes. Relays are 1510 selected so that a nodes two-hop neighbor set is covered. This 1511 distributed technique has been shown to approximate selection of a 1512 minimal connected dominating set (MCDS) in [JLMV02]. Individual 1513 nodes must collect two-hop neighborhood information from neighbors, 1514 determine an appropriate current relay set, and inform selected 1515 neighbors of their relay status. The Optimized Link State Routing 1516 (OLSR) protocol has used this algorithm and protocol for relay of 1517 link state updates and other control information [RFC3626] and it has 1518 been demonstrated operationally in dynamic network environments. 1520 B.1. S-MPR Relay Set Selection 1522 If SMF is operating S-MPR relay set election is operating with 1523 independent CDS control, the election algorithm and TLVs defined 1524 within [OLSRv2] SHOULD be used. In this case, NHDP messages SHOULD 1525 also include a message TLV of type SMF_RELAYALG_ID specifying S-MPR 1526 relay election. 1528 With S-MPR, a node's status as a relay is with respect to neighboring 1529 nodes who have selected it (i.e., its "selectors".) This requires 1530 nodes to inform neighbors of who they have selected as forwarders. 1531 These relaying nodes must have previous-hop knowledge of packets 1532 received to make forwarding decisions. Additionally, it is important 1533 that relay nodes forward packets for only those nodes identified as 1534 symmetric, one-hop neighbors to maintain correctness. The selection 1535 of relays does not result in a common set among neighboring nodes, so 1536 relays MUST mark in their duplicate table packets from non-selector, 1537 symmetric, one-hop neighbors (for a given interface) and not forward 1538 subsequent duplicates of that packet if received on that interface. 1539 Deviation here can result in unnecessary, repeated packet forwarding 1540 throughout the network, or incomplete flooding. When multiple 1541 interfaces are present, the S-MPR SMF forwarder must keep independent 1542 state for each interface with regards to duplicate packets. In these 1543 respects, flooding for SMF based on the S-MPR algorithm is more 1544 complex than previous hop independent relay set selection algorithms, 1545 yet S-MPR is a known technique that has significant experimental and 1546 operational experience and may have other performance advantages. 1548 B.2. S-MPR Forwarding Rules 1550 1. Upon reception of a packet, it is checked against the incoming 1551 interfaces duplicate table. If a duplicate exists no further 1552 action is taken. 1554 2. Once uniqueness is verified and if the previous-hop transmitter 1555 is a one-hop symmetric neighbor, the packet is added to the 1556 duplicate table of the incoming interface. If the previous-hop 1557 transmitter is not a one-hop symmetric neighbor the packet SHOULD 1558 NOT be forwarded and SHOULD NOT be added to the duplicat table. 1560 3. If the previous-hop transmitter has selected the current node, on 1561 the incoming interface, as an MPR, the packet is forwarded out 1562 all interfaces. If the node is not an MPR for the previous-hop, 1563 on the incoming interface, no further action is taken. 1565 4. Any packet sourced or forwarded through a node is added to the 1566 duplicate tables of all of the nodes interfaces. 1568 Basic S-MPR relay forwarding will not forward packets in which the 1569 previous hop is not known through the neighbor discovery mechanism, 1570 therefore nodes not participating in neighbor discovery and relay set 1571 selection will not be able to source multicast packets into the MANET 1572 and have SMF forward them. Correct S-MPR relay behavior will occur 1573 with the introduction of repeaters (non SMF participant nodes that 1574 relay multicast packets using duplicate detection and CF) but the 1575 repeaters will be dead ends with regards to S-MPR SMF forwarding. 1576 SMF participant nodes may not provide extra forwarding, forwarding 1577 packets which are not selected by the algorithm, as this can break 1578 network wide S-MPR flooding. 1580 B.3. S-MPR Neighborhood Discovery Requirements 1582 S-MPR election operation requires 2-hop neighbor knowledge as 1583 provided by the NHDP protocol [NHDP] or as available from external 1584 sources. MPRs are dynamically selected by each node and selections 1585 MUST be advertised and dynamically updated within NHDP or equivalent 1586 protocol. In this mode, the MPR specific TLVs defined in OLSRv2 1587 [OLSRv2] are also required to be implemented by NHDP. 1589 B.4. S-MPR Selection Algorithm 1591 1. 1. Calculate N_1(z) for all nodes z in N_2. 1593 2. 2. Calculate N_2(y) for all nodes y in N_1. 1595 3. 3. For each z in N_2 where |N_1(z)| is equal to 1, select the 1596 node in N_1(z) as an MPR by using Appendix B.4.1. 1598 4. 4. While N_2 is not empty select the node y, with the largest 1599 |N_2(y)|, as MPR by using Appendix B.4.1. 1601 5. 5. Restore N_1 and N_2. 1603 6. 6. Node n_0 shares its MPRs with N_1. 1605 7. 7. Each node in n_0's MPRs set add n_0 to their MPR-Selectors 1606 set. 1608 8. 8. Nodes forward all unique multicast packets which are first 1609 received from a node in their MPR-Selectors set. 1611 B.4.1. MPR Node Selection Procedure 1613 1. Add n to the MPRs set. 1615 2. Remove node n from N_1. 1617 3. For each y in N_2(n), remove y from N_2. 1619 4. Calculate N_1(z) for all nodes z in N_2 1621 5. Calculate N_2(y) for all nodes y in N_1. 1623 Appendix C. Essential Connecting Dominating Set (E-CDS) Algorithm 1625 The "Essential Connected Dominating Set" (E-CDS) algorithm [E-CDS] 1626 allows nodes to use two-hop topology information to dynamically elect 1627 _themselves_ as relay nodes to form an efficient (for flooding) CDS. 1628 Its forwarding rules within SMF are non-dependent upon previous hop 1629 information. Semantics for multiple interface support are simplified 1630 as compared to S-MPR as only one duplicate table is required. 1631 Packets which are received from non-symmetric neighbors may be 1632 forwarded without compromising flooding efficiency or algorithm 1633 correctness. The E-CDS based relay set selection algorithm is based 1634 upon Richard Ogier's original summary within [E-CDS]. E-CDS was 1635 originally discussed in the context of forming partial adjacencies 1636 and efficient flooding for MANET OSPF extensions work but its core 1637 algorithm is applied here. 1639 If SMF is operating E-CDS relay set election with independent CDS 1640 control, NHDP messages SHOULD also include a message TLV of type 1641 SMF_RELAYALG_ID specifying E-CDS relay election. 1643 C.1. E-CDS Relay Set Selection 1645 E-CDS requires two-hop neighbor information collected through NHDP or 1646 other process. Each router has a Router Identifier (that may be 1647 represented by an interface address) and Router Priority 1648 value(RtrPri). The Router Priority value may be dynamic and may 1649 represent such metrics as node degree. The fundamental election 1650 steps are as follows: 1652 1. If an SMF node has a higher (Router Priority, Router ID) than all 1653 of its symmetric neighbors, it elects itself to the relay set. 1655 2. Else, if there does not exist a path from neighbor j with largest 1656 (Router Priority, Router ID) to some other neighbor, via 1657 neighbors with larger values of (Router Priority, Router ID), 1658 then it elects itself to the relay set. 1660 The basic form of E-CDS described and applied within this 1661 specification does not at present define redundant relay set election 1662 but such capability is supported by the basic E-CDS design. 1664 C.2. E-CDS Forwarding Rules 1666 Upon electing itself as an E-CDS relay set forwarder, SMF nodes 1667 perform DPD functions and forward all ranges of non-duplicative 1668 multicast traffic allowed by the present forwarding policy. 1669 Knowledge of a packets previous hop is not needed for forwarding 1670 decisions when using E-CDS. 1672 1. Upon reception of a packet, it is checked against the duplicate 1673 table. If a duplicate exists no further action is taken. E-CDS 1674 and all other shared relay selection algorithms only require one 1675 duplicate table for all interfaces of which the algorithm covers. 1677 2. Once uniqueness is verified, the packet is added to the duplicate 1678 table. 1680 3. A unique packet is forwarded out all interfaces if the local node 1681 has selected itself as a relay node according to the E-CDS 1682 algorithm. 1684 4. Any packet sourced or forwarded through a node is added to the 1685 duplicate table. 1687 Using E-CDS relay forwarding, nodes which are not participating in 1688 neighbor discovery and relay set selection will have directly 1689 injected multicast packets forwarded by SMF if they are received at a 1690 relay node. Correct E-CDS relay behavior will occur with the 1691 introduction of repeaters (non SMF participant nodes which relay 1692 multicast packets using duplicate detection) and these repeaters can 1693 be used to connect otherwise separate SMF relay sets. SMF 1694 participant nodes may provide extra forwarding, becoming a relay node 1695 when not selected by the E-CDS algorithm, without breaking correct 1696 flooding throughout the network. 1698 C.3. E-CDS Neighborhood Discovery Requirements 1700 Two-hop knowledge is needed during the election process, but unlike 1701 the MPR method, E-CDS is a self-electing algorithm. For E-CDS 1702 operation, some value of RtrPri must be given or assumed for each 1703 address with the two-hop neighborhood which is consistent for all 1704 nodes. If RtrPri is a non-default value it MUST be shared with all 1705 immediate neighbor and 2-hop neighbor nodes. To support this the 1706 SMF_RTR_PRI TLVs MAY be used to transmit RtrPri for each address 1707 within a NHDP message. If a NHDP message originator does not provide 1708 a RtrPri value for given address(es) using the SMF_RTR_PRI TLVs, a 1709 default value RTRPRI_DEFAULT = 128 should be assumed. 1711 Local determination of a node RtrPri value can be done in multiple 1712 ways as described in the [E-CDS]. An early experimental deployment 1713 of an SMF prototype and E-CDS has used node degree as the default 1714 priority value computed during neighbor discovery, yet it is still 1715 unclear if this is the best method. Nonetheless, this is recommended 1716 as the default mode on all SMF nodes to enable interoperability. 1718 C.4. E-CDS Selection Algorithm (2-Hop) 1720 1. If |N_1| < 2 than n_0 does not select itself as a forwarder and 1721 no further steps need to be taken 1723 2. If n_0 has a larger value of RtrPri than all nodes in N_1 and 1724 N_2, then n_0 selects itself as a forwarder for all nodes. 1725 Unless otherwise set, n_0 should assume a default RtrPri of 128. 1726 RtrPri ties should be broken by comparing addresses. 1728 3. If there does not exist a path from r_max_1 to every other node 1729 in N_1 and N_2 using only N_1 and N_2 nodes that have RtrPri 1730 larger than n_0's, then n_0 selects itself as a forwarder for all 1731 nodes. 1733 Appendix D. Multipoint Relay Connected Dominating Set (MPR-CDS) 1734 Algorithm 1736 The MPR-CDS algorithm is an extension to the basic MPR election 1737 algorithm and results in a shared relay set that forms a CDS. Its 1738 forwarding rules within SMF are non-dependent upon previous hop 1739 information similar to E-CDS. An overview of the MPR-CDS selection 1740 algorithm is provided in [MPR-CDS]. 1742 If SMF is operating MPR-CDS relay set election with independent CDS 1743 control, NHDP messages SHOULD also include a message TLV of type 1744 SMF_RELAYALG_ID specifying MPR-CDS relay election. 1746 D.1. MPR-CDS Relay Set Selection 1748 The basic requirements for election are similar to the basic MPR 1749 algorithm with the addition that some node ordering knowledge is 1750 required. This is similar to the E-CDS requirement and can be based 1751 upon node IP address or some other unique router identifier. The 1752 rules for election are as follows: 1754 A node decides it is in the relay set if: 1756 1. n_0 has a larger RtrPri than all of N_1 (Rule 1) 1758 2. or n_0 is an MPR of rp_max_1 (Rule 2) 1760 D.2. MPR-CDS Forwarding Rules 1762 MPR-CDS forms a shared relay set so the forwarding rules do not 1763 require previous previous hop information for making forwarding 1764 decisions. Upon election as a MPR-CDS relay set forwarder, SMF nodes 1765 perform DPD functions and forward all ranges of multicast traffic 1766 allowed. 1768 1. Upon reception of a packet, it is checked against the duplicate 1769 table. If a duplicate exists no further action is taken. E-CDS 1770 and all other shared relay selection algorithms only require one 1771 duplicate table for all interfaces. 1773 2. Once uniqueness is verified, the packet is added to the duplicate 1774 table. 1776 3. A unique packet is forwarded out all interfaces if the local node 1777 has selected itself as a relay node according to the MPR-CDS 1778 algorithm. 1780 4. Any packet sourced or forwarded through a node is added to the 1781 duplicate table. 1783 Correct MPR-CDS relay behavior will occur with the introduction of 1784 repeaters (non SMF participant nodes which relay multicast packets 1785 using duplicate detection) and these repeaters can be used to connect 1786 otherwise separate SMF relay sets. SMF participant nodes may provide 1787 extra forwarding, becoming a relay node when not selected by the MPR- 1788 CDS algorithm, without breaking correct flooding throughout the 1789 network. 1791 D.3. MPR-CDS Neighborhood Discovery Requirements 1793 MPR-CDS election operation requires 2-hop neighbor knowledge as 1794 provided by the NHDP protocol [NHDP] or as available from external 1795 sources. MPR-CDS require the MPR specific TLVs defined in OLSRv2 1796 [OLSRv2] and MAY use SMF_RTR_PRI message TLVs to convey router 1797 priority values. 1799 D.4. MPR-CDS Selection Algorithm 1801 1. Perform steps 1-7 of Appendix B.4. 1803 2. If n_0 RtrPri value is greater than rp_max_1's RtrPri value, and 1804 |MPR-Selectors| > 0, then n_0 selects itself as a forwarder for 1805 all nodes. 1807 3. If rp_max_1 is in the MPR-Selectors set, then n_0 selects itself 1808 as a forwarder for all nodes. 1810 Authors' Addresses 1812 Joseph Macker 1813 NRL 1814 Washington, DC 20375 1815 USA 1817 Email: macker@itd.nrl.navy.mil 1819 SMF Design Team 1820 IETF MANET WG 1822 Email: manet@ietf.org 1824 Full Copyright Statement 1826 Copyright (C) The IETF Trust (2007). 1828 This document is subject to the rights, licenses and restrictions 1829 contained in BCP 78, and except as set forth therein, the authors 1830 retain all their rights. 1832 This document and the information contained herein are provided on an 1833 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1834 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 1835 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 1836 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 1837 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1838 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1840 Intellectual Property 1842 The IETF takes no position regarding the validity or scope of any 1843 Intellectual Property Rights or other rights that might be claimed to 1844 pertain to the implementation or use of the technology described in 1845 this document or the extent to which any license under such rights 1846 might or might not be available; nor does it represent that it has 1847 made any independent effort to identify any such rights. Information 1848 on the procedures with respect to rights in RFC documents can be 1849 found in BCP 78 and BCP 79. 1851 Copies of IPR disclosures made to the IETF Secretariat and any 1852 assurances of licenses to be made available, or the result of an 1853 attempt made to obtain a general license or permission for the use of 1854 such proprietary rights by implementers or users of this 1855 specification can be obtained from the IETF on-line IPR repository at 1856 http://www.ietf.org/ipr. 1858 The IETF invites any interested party to bring to its attention any 1859 copyrights, patents or patent applications, or other proprietary 1860 rights that may cover technology that may be required to implement 1861 this standard. Please address the information to the IETF at 1862 ietf-ipr@ietf.org. 1864 Acknowledgment 1866 Funding for the RFC Editor function is provided by the IETF 1867 Administrative Support Activity (IASA).