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