Network Working Group J. Macker, editor Internet-Draft NRL Intended status: Standards Track SMF Design Team Expires: September 6, 2007 IETF MANET WG March 5, 2007 Simplified Multicast Forwarding for MANET draft-ietf-manet-smf-04 Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on September 6, 2007. Copyright Notice Copyright (C) The IETF Trust (2007). Macker, editor & SMF Design Team Expires September 6, 2007 [Page 1] Internet-Draft SMF for MANET March 2007 Abstract This document describes the Simplified Multicast Forwarding (SMF) protocol that provides a basic IP multicast forwarding capability suitable for mobile ad-hoc networks (MANET). SMF is designed to have limited applicability as a forwarding mechanism for multicast packets within MANET routing areas. In addition, it provides mechanisms to support interoperability with a connected fixed-infrastructure networks. SMF uses a simplified forwarding mechanism that delivers multicast packets to all MANET multicast receivers within a MANET routing area. The core design does not use receiver specific group information in favor of reduced complexity and state maintenance within the mobile topology. Group-specific forwarding can be supported through appropriate forwarding filters and related extensions may follow in later specifications. The design accounts for the unique nature and behavior of MANET interfaces and takes advantage of efficient relay set algorithms previously designed and applied in the MANET routing control plane. This document describes the SMF forwarding mechanisms in detail, its use with the MANET Neighborhood Discovery Protocol (NHDP), and several efficient relay set algorithms specified for use in conjunction with SMF. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 2] Internet-Draft SMF for MANET March 2007 Table of Contents 1. Requirements Notation . . . . . . . . . . . . . . . . . . . . 4 2. Introduction and Scope . . . . . . . . . . . . . . . . . . . . 5 2.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 7 2.2. Applicability and Scope . . . . . . . . . . . . . . . . . 7 3. SMF Core Design Issues . . . . . . . . . . . . . . . . . . . . 9 3.1. Previous Related Work . . . . . . . . . . . . . . . . . . 10 4. SMF Packet Processing and Forwarding . . . . . . . . . . . . . 11 5. SMF Duplicate Packet Detection . . . . . . . . . . . . . . . . 14 5.1. SMF IPv4 Packet Identification . . . . . . . . . . . . . . 15 5.2. SMF IPv6 Packet Identification . . . . . . . . . . . . . . 16 5.2.1. IPv6 SMF-DPD Header Option Format . . . . . . . . . . 17 6. Relay Set Selection . . . . . . . . . . . . . . . . . . . . . 21 7. SMF Neighborhood Discovery Requirements . . . . . . . . . . . 22 7.1. NHDP Description and SMF Requirements . . . . . . . . . . 22 8. SMF Multicast Border Gateway Considerations . . . . . . . . . 24 8.1. Forwarded Multicast Groups . . . . . . . . . . . . . . . . 24 8.2. Multicast Group Scoping . . . . . . . . . . . . . . . . . 25 8.3. Duplicate Packet Detection Marking . . . . . . . . . . . . 26 8.4. Interface with Exterior Multicast Routing Protocols . . . 26 8.5. Multiple Gateways . . . . . . . . . . . . . . . . . . . . 27 8.6. Non-SMF MANET Nodes . . . . . . . . . . . . . . . . . . . 28 9. Security Considerations . . . . . . . . . . . . . . . . . . . 30 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 31 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 32 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 33 12.1. Normative References . . . . . . . . . . . . . . . . . . . 33 12.2. Informative References . . . . . . . . . . . . . . . . . . 33 Appendix A. Source-based Multipoint Relay (S-MPR) . . . . . . . . 35 A.1. S-MPR Relay Set Selection . . . . . . . . . . . . . . . . 36 A.2. Neighborhood Discovery Requirements . . . . . . . . . . . 36 Appendix B. Essential Connecting Dominating Set (E-CDS) Algorithm . . . . . . . . . . . . . . . . . . . . . . 37 B.1. E-CDS Relay Set Selection . . . . . . . . . . . . . . . . 37 B.2. E-CDS Forwarding Rules . . . . . . . . . . . . . . . . . . 37 B.3. Neighborhood Discovery Requirements . . . . . . . . . . . 38 Appendix C. Multipoint Relay Connected Dominating Set (MPR-CDS) Algorithm . . . . . . . . . . . . . . . . . 39 C.1. MPR-CDS Relay Set Selection . . . . . . . . . . . . . . . 39 C.2. MPR-CDS Forwarding Rules . . . . . . . . . . . . . . . . . 39 C.3. Neighborhood Discovery Requirements . . . . . . . . . . . 39 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 40 Intellectual Property and Copyright Statements . . . . . . . . . . 41 Macker, editor & SMF Design Team Expires September 6, 2007 [Page 3] Internet-Draft SMF for MANET March 2007 1. Requirements Notation The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 4] Internet-Draft SMF for MANET March 2007 2. Introduction and Scope Design and implementation progress has been made in demonstrating effective ways to flood control packets within dynamic wireless routing protocols. For example, algorithms within MANET RFC 3626 [RFC3626]and RFC 3684 [RFC3684] specify distributed methods of dynamically electing reduced relay sets that efficiently optimize the flooding of routing control packets amongst MANET routing nodes. In this document, we specify the Simplified Multicast Forwarding (SMF) framework. The main purpose of SMF is to adapt known efficient flooding designs in MANET environments and apply these mechanisms to IP multicast packet forwarding. When localized efficient flooding is a sufficient technique, SMF can provide simplified multicast forwarding to data flows within a MANET routing area. The SMF baseline design limits the scope to basic, best effort multicast forwarding and its applicability is intended to be constrained within a MANET routing area. Figure 1 provides an overview of the logical SMF node architecture, consisting of "Neighborhood Discovery", "Relay Set Selection" and "Forwarding Process" components. Typically, relay set selection (or even self-election) will occur based on input from a neighborhood discovery process, and the forwarding process will be controlled by status based upon relay set selection. In some cases, the forwarding decision for a packet may also depend on previous hop or incoming interface information. The asterisks (*) in Figure 1 mark the primitives and relationships needed by relay set algorithms requiring previous-hop packet forwarding knowledge. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 5] Internet-Draft SMF for MANET March 2007 ______________ _____________ | | | | | Neighborhood | | Relay Set | | Discovery |------------->| Selection | | Protocol | neighbor | Algorithm | |______________| info |_____________| \ / \ / neighbor\ /fowarding info* \ ____________ / status \ | | / `-->| Forwarding |<--' | Process | ~~~~~~~~~~~~~~~~~>|____________|~~~~~~~~~~~~~~~~~> incoming packet, forwarded packets interface id, and previous hop* Fig. 1 - SMF Node Architecture SMF is a network layer multicast forwarding process compatible with different neighborhood discovery protocols and relay set selection algorithms. Different discovery mechanisms or relay set algorithms may be applicable for different MANET routing protocols and deployments. In the simplest case, Classical Flooding (CF) is supported, eliminating the need for any relay set algorithm or neighborhood topology information. However, more efficient flooding techniques will typically be preferred due to expected gains in network efficiency and reductions in wireless congestion and contention. Efficient flooding is realized by selecting a _subset_ of all possible nodes in a MANET area as the forwarding relay set. Algorithms and running code exist that makes use of local network neighborhood topology information to determine an appropriate relay set in a distributed, dynamic fashion. These relay set selection algorithms can be used to provide and maintain a dynamic distribution tree or mesh for forwarding user multicast data[MDC04]. A few such relay set selection algorithms are described in Appendices of this document, but additional relay set algorithms or extensions may be specified in the future for use with SMF. Dynamic neighborhood topology information is often needed by distributed relay set algorithms to determine and maintain an optimized set of forwarding nodes. It is generally expected that neighborhood topology discovery functions will be provided by a MANET unicast routing protocol or a MANET NeighborHood Discovery Protocol (NHDP) implementation running in concurrence with SMF. This specification does not preclude a lower link layer from providing the necessary neighborhood information through an enhanced interface when Macker, editor & SMF Design Team Expires September 6, 2007 [Page 6] Internet-Draft SMF for MANET March 2007 available. Different distributed relay set algorithms and associated forwarding decision logic can have differing neighborhood discovery and signaling demands. This document states specific requirements for neighborhood discovery with respect to the forwarding process and relay set selection algorithms described herein and relies on the MANET NHDP specification to support operation independent of any MANET unicast protocol and any lower layer information interface. As already mentioned, the exception is that the CF mode can be supported with or without neighborhood information or related discovery. 2.1. Terminology MANET : Mobile Ad hoc Network SMF : Simplified Multicast Forwarding CF : Classical Flooding CDS : Connected Dominating Set MCDS : Minimum Connected Domination Set MPR : Multi-point Relay DPD: Duplicate Packet Detection NHDP: Neighborhood Discovery Protocol 2.2. Applicability and Scope A basic packet forwarding service that reaches all destinations participating within a MANET area can provide a useful group communication mechanism for various classes of applications. While the design requirements for this are similar to those needed by the control plane of many MANET unicast routing protocol layers, it is desirable to provide a more general IP multicast forwarding function for use by a variety of applications. This can be useful for forwarding multicast application flows that are global in scope within the MANET but is also useful for site-scoped multicast applications and data flows intended to be contained within a MANET routing area. There are a number of application areas that could take advantage of a simple site-scoped multicast forwarding service within a MANET routing region (e.g., multimedia streaming, peer-to- peer middleware multicasting, auto-configuration, and multi-hop discovery services). Note that Figure 1 provides a notional architecture for _typical_ MANET SMF-capable nodes. However, a goal is that simple end-system Macker, editor & SMF Design Team Expires September 6, 2007 [Page 7] Internet-Draft SMF for MANET March 2007 (non-forwarding) wireless nodes may also participate in multicast traffic transmission and reception with standard network layer semantics. Also, a multicast border gateway or proxying mechanism MUST be used when interoperating with other IP multicast routing such as that for fixed-infrastructure networks (e.g., Protocol Independent Multicast (PIM)). In present experiments, proxying methods have been used to enable some gateway functionality at MANET border gateways operating with external IP multicast routing protocol interfaces. Although SMF may be extended or combined with other protocols to provide increased reliability and group specific forwarding state, the details of those methods will be discussed in other documents. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 8] Internet-Draft SMF for MANET March 2007 3. SMF Core Design Issues In CF, each participating forwarder node is required to rebroadcast packets intended for dissemination once and only once. This approach is extremely simple and only requires a means of duplicate packet detection (DPD) and a basic forwarding mechanism. However, it is well known that using CF, especially within dense networks, results in a significant number of redundant transmissions often referred to as the broadcast storm problem [NTSC99]. Within wireless multi-hop networks, direct contention and interference is often correlated beyond a one-hop neighbor link interface. Reducing unnecessary channel contention within a MANET can significantly improve network performance. Therefore, minimizing the number of required relay nodes is a heightened design goal in this environment. Unfortunately, reducing the number of relay nodes in a MANET environment can also contribute to decreased robustness of packet delivery within a mobile topology. The scenario and system dependent design tradeoff between relay efficiency and delivery robustness should be considered carefully. If needed, additional reliability mechanisms MAY be considered for use with reduced relay sets (e.g., backup and redundant relay set) but the specification of limited hop- by-hop retransmission schemes at the network layer are considered out of scope for this document. If needed by an application, the use of IETF reliable multicast transport layer protocols should be transparently supported by SMF's best effort delivery mechanism. The core design scope of SMF is to define a DPD mechanism, support simple CF-based forwarding, and define the use of reduced relay set algorithms for increased efficiency. At a theoretic level, work in the area of minimizing packet forwarders, or relay node sets, can be related to basic static graph theory problems. In graph theory, a Dominating Set (DS) for a graph is a set of vertices that, along with their neighbors, constitute all the vertices in the graph. A Connected DS (CDS) is a DS where the subgraph induced is connected. A Minimum CDS (MCDS) is a set such that the number of vertices is the minimum required to form a CDS. Finding a small dominating set is one of the most fundamental problems of traditional graph theory and is often related to the problem of optimizing flooding algorithms in MANET routing protocols. Finding an MCDS in a given graph is known to be NP-hard [GJ79]. These basic static graph theoretic issues are important to apply in developing efficient relay sets, but MANET relay set selection must also support distributed and dynamic operation. To better explain the design requirements, we formulated the following characteristics desired of an effective MANET flooding algorithm for use in SMF: 1. A resultant cover set that is small compared to the total number of nodes as the network scales in size and density. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 9] Internet-Draft SMF for MANET March 2007 2. A robust approach somewhat resilient to network mobility and link dynamics. 3. A cover set election/maintenance mechanism that is lightweight, distributed, and adaptive in nature. 3.1. Previous Related Work Previous work on MANET flooding and reduced relay set mechanisms has been done and this document borrows from and builds off previous work accomplished. In [WC02], a taxonomy of flooding algorithms for use in MANET environments was presented and the work examined performance issues related to various approaches. Other important work has developed distributed mechanisms that select and maintain reduced relay node sets. The design tradeoffs are further complicated by wireless contention, topological classes, and the robustness of packet delivery and set election under mobility scenarios. In addition, the actual protocol implementation for IP multicast forwarding based upon these flooding algorithms raises additional design tradeoffs and issues. This includes: 1. protocol state maintenance 2. duplicate packet detection mechanisms 3. packet processing requirements and overhead 4. expected traffic distribution patterns 5. protocol signaling requirements 6. delivery robustness requirements Macker, editor & SMF Design Team Expires September 6, 2007 [Page 10] Internet-Draft SMF for MANET March 2007 4. SMF Packet Processing and Forwarding The SMF Packet Processing and Forwarding actions are conducted with the following packet handling activities: 1. Processing of outbound, locally-generated multicast packets. 2. Reception and processing of inbound packets on a specific network interface(s). In the case that sequence-based DPD as described in Section 5 is used, the purpose of intercepting outbound, locally-generated multicast packets is to apply resequencing of the IPv4 ID header field or add options headers as needed (e.g. IPv6). In the case that resequencing is deemed necessary, it is RECOMMENDED that sequence numbering be applied such that a different sequence number space per duple be used. For initial SMF purposes where no distinct routing path decisions for different IP Multicast address destinations occur, it might appear to be sufficient to use sequence number spaces aggregated across all IP Multicast destinations (or across all IP destinations for a source as is the default implementation of the IPv4 ID field in many operating systems). However, future SMF extensions, beyond the present discussion, may contain dynamic forwarding state dependent on the multicast destination address. The future possibility that different destinations may be routed differently suggests that "per source/ destination" identification be used. It should be noted that the default global IPv4 ID sequence space may be sufficient for some SMF deployments and interception of outbound packets may not be required if end systems have numbered the IPv4 ID field in an acceptable manner. In other cases, such as when IPSec headers have been applied to packets, other sequence information may be available for the SMF process to make use of in its duplicate table management. Inbound multicast packets will be received by the SMF implementation and processed for possible forwarding. Well-known multicast groups for flooding to all routers of an ad hoc network are specified for use with the network-layer flooding provided by SMF. These multicast groups are specified to contain all MANET routers of a contiguous MANET area, so that packets transmitted to the multicast address associated with the group will be delivered to all nodes as desired. For IPv6, the multicast address is specified to be "site-local". The names of the multicast groups are given as "ALL_IPv4_MANET_ROUTERS" (TBD) and "ALL_IPv6_MANET_ROUTERS" (TBD). This document does not support transmissions to any directed broadcast address ranges. Minimally SMF SHALL forward, as instructed by the relay set selection algorithm, unique (non-duplicate) packets received for these well- known group addresses when the TTL or hop count value in the IP Macker, editor & SMF Design Team Expires September 6, 2007 [Page 11] Internet-Draft SMF for MANET March 2007 header is greater than 1. Optionally, SMF deployments may choose to forward packets for additional "global scope" multicast groups to support application needs or to distribute multicast packets that ingress the MANET area via border gateways. Additional addresses will be specified by an _a priori_ list or possibly through a implementation of a dynamic address management interface. In all cases, the following rules SHALL be observed for SMF multicast forwarding: 1. Multicast packets with TTL <= 1 MUST NOT be forwarded*. 2. Link Local multicast packets MUST NOT be forwarded 3. Incoming multicast packets with an IP source address matching one of those of the local host interface(s) MUST NOT be forwarded. 4. Received packet frames with the MAC source address matching the local host interface(s) MUST NOT be forwarded. Note that rule #3 is important because in wireless networks, the local host may receive re-transmissions of its own packets when they are forwarded by neighboring nodes. This rule avoids unnecessary retransmission of locally-generated packets even when other forwarding decision rules would apply. Once these criteria have been met, the implementation should reference a forwarding decision algorithm, possibly in concert with duplicate packet detection, to determine the next step in packet processing. The forwarding decision may be implicit, dependent upon DPD results, only if the SMF implementation is configured to perform classical flooding (CF) of IP multicast packets. Otherwise, the forwarding decision may be controlled using additional information. Neighborhood discovery protocols coupled with the Source-based Multi- Point Relay (S-MPR) or other CDS selection algorithms described later MAY be used to determine the local host's status with respect to forwarding. For example, algorithms may control forwarding based on a relay set election and previous hop identifier (e.g. S-MPR forwarding), while others may designate the local host as a forwarder of all neighbor packets based on the neighborhood broadcast topology (e.g. Essential CDS (E-CDS)). DPD is a fundamental and critical portion of the SMF forwarding process. In general, detection of received duplicate packets is necessary to avoid forwarding the same packet multiple times. However, in some cases (e.g., S-MPR), duplicate detection of some non-forwarded packets is also needed to maintain efficient forwarding. Details on different duplicate packet detection and forwarding rules for the S-MPR, and E-CDS algorithms are given in Macker, editor & SMF Design Team Expires September 6, 2007 [Page 12] Internet-Draft SMF for MANET March 2007 Appendices of his document. The details for these classes of algorithms may also apply to other similar algorithms. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 13] Internet-Draft SMF for MANET March 2007 5. SMF Duplicate Packet Detection One important design difference between routing for MANET interfaces and classical infrastructure network interfaces is that forwarding a packet via the same physical interface that it arrived upon is a normal operation. This operation is often disallowed or discouraged in many multicast routing designs to avoid possible looping. Similarly, any Reverse Path Forwarding (RPF) logic used may need to be softened when operating over a single MANET interface. This MANET interface characteristic leads to DPD as a common requirement in MANET packet flooding. While this requires increased per-packet processing, it is necessary in MANET-specific multicasting because packets may be forwarded out the same physical interface upon which they arrived and nodes can receive copies of previously-transmitted packets from other forwarding neighbors. This section describes a basic SMF DPD mechanism and some alternative operational options as considerations. SMF SHOULD implement explicit detection of duplicate multicast packets by a temporal packet identification scheme. This is typically implemented by keeping a history of previous received and forwarded packet identifiers for comparison against recently forwarded multicast packets. There are different possible approaches to packet identification that have been considered. Possibilities include unique markings within packet header fields, such as packet sequence numbering, or application of hash algorithms or similar techniques to compactly and uniquely describe the history of recently received packets. This document RECOMMENDS simple, sequence-based schemes that can be accomplished without additional (non-IP) encapsulation of packets and/or their content. Encapsulation approaches are considered out-of-scope so that non-forwarding edge nodes within a MANET area may easily receive flooded content without any additional software beyond that of a typical IP stack. Packet hashing approaches for DPD may be applicable in some cases, yet early examination of these approaches indicated the computational complexity may be prohibitive for per-packet processing on many candidate MANET platforms (e.g., PDAs). Additionally, the unavoidable "cache-miss" rates, while possibly low for some algorithms, result in the severe penalty of false DPD (and thus packet loss) rather than the more benign penalty of additional computation cycles as associated with most applications of hashing. Implementations will need to age and/or timeout duplicate packet state as new packets are received and forwarded. In the case that sequence-based packet identification is used, implementations SHOULD timeout stale histories for entries where new, _non-duplicate_ packets have not been recently received. The proper minimum duration of any timeout delay is a Macker, editor & SMF Design Team Expires September 6, 2007 [Page 14] Internet-Draft SMF for MANET March 2007 function of expected possible network traversal time, roughly NET_DIAMETER (in hops) times NODE_TRAVERSAL_TIME. NET_DIAMETER measures the maximum possible number of hops given any two nodes in the network. NODE_TRAVERSAL_TIME is a conservative estimate of the average one hop traversal time for packets and should include queueing delays, interrupt processing times, medium access delays, and propagation delays. If the timeout is reset only upon reception of non-duplicate packets, it also limits the time that packets might be incorrectly dropped if a source node is stopped and restarted in the case of sequence-based packet identification. The required size of the DPD cache is similarly governed and is also a function of the maximum expected packet rate. It should be noted that less stateful bitmask approaches to marking packet status can be used by using a contiguous space of sequence numbers rather than explicit lists of arbitrary packet identifiers. Of course, the duplicate packet detection mechanism SHOULD avoid keeping unnecessary state for packet flows such as those that are locally generated or link local destinations that would not be considered for forwarding. 5.1. SMF IPv4 Packet Identification IPv4 multicast packets from a particular source are assumed to be marked with a temporally unique identification number in the ID field of the IPv4 packet header that can serve as a "packetIdentifier" for SMF purposes. Unfortunately, in present operating system networking kernels, the IP ID header field value is not always generated or applied in a consistent manner with respect to SMF needs. In order to build a working implementation without encapsulating packets, an SMF implementation SHOULD provide a sequence generation and marking module that can maintain and set a monotonically increasing IP ID field for locally-generated multicast packets with independent sequence number spaces applied on a basis. This process will also need to recalculate and replace a proper IP header checksum for the modified header. For gateways injecting external IPv4 traffic into an SMF MANET area, the gateways SHOULD perform this same IP ID field re- sequencing. Note the presence of IPSec may prevent such resequencing, but fortunately, IPSec does provide its own organic means for duplicate packet detection. The use of IPSec for candidate packet flows presents the opportunity to make use of the additional, perhaps more reliable, sequencing information of the IPSec header for unique packet identification. The IPSec header provides a packet identifier field that can be used on a "per-security association" basis. The IP addressing and IPSec Security Parameters Index (SPI) fields are used to identify security Macker, editor & SMF Design Team Expires September 6, 2007 [Page 15] Internet-Draft SMF for MANET March 2007 associations and, hence, packet flows. So, if the packet is IPSec encapsulated, SMF will check the where the or from the IPSec header serves as the "packetIdentifier" value. Although it would be possible to support IP layer fragmentation , SMF traffic sources or gateways SHOULD set the don't fragment bit for traffic intended to be carried by SMF. This is recommended to avoid the additional complexity and inefficiencies arising from supporting IP layer fragmentation. To perform duplicate detection, SMF will check the combination against a history of received packet identifiers. Note some forwarding algorithms may require that unique packets are noted when received from certain neighbor nodes regardless of whether the packets are forwarded. Multiple interface semantics may also add some additional considerations to the forwarding process depending upon the specific relay set selection forwarding rules. Although its use has been demonstrated in running prototype code, the adoption of the IPv4 ID field for widespread packet duplication detection has some disadvantages that should be discussed. The main disadvantage is the use and interpretation of the field is known to be inconsistent across operating systems. The IPv4 ID field is also limited and may provide less robust detection for high bandwidth applications since sequence wrap-around may occur relatively frequently if it is not possible to achieve "per source/destination" sequencing. As an alternative, the use of a header option or encapsulation header in future implementations may provide more flexibility and consistency (see IPv6 DPD). Another advantage of using a header option (or other encapsulation, if determined absolutely necessary) is that it would be possible for MANET gateway nodes to assess whether packets ingressing a MANET area have already been properly sequenced to avoid unnecessary re-injection of packets. We leave these design alternatives to be further defined and discussed in future work. A basic sequencing and marking design similar to the one we formulate here can be easily adapted to work with future approaches or can be bypassed when not needed. 5.2. SMF IPv6 Packet Identification The following section describes the mechanism and options for SMF IPv6 DPD. The core IPv6 header does not provide an explicit identification header field that can be exploited for DPD. SMF defines two methods for IPv6 use: Macker, editor & SMF Design Team Expires September 6, 2007 [Page 16] Internet-Draft SMF for MANET March 2007 1. a hop-by-hop DPD options header, and 2. the use of IPSec sequencing when an IPSec header is detected. SMF MUST provide a DPD marking module that can insert the hop-by-hop IPv6 header option defined for locally generated multicast packets. If the packet is _not_ IPSec encapsulated, SMF will use the IPv6 packet header and IPv6 DPD option to form the tuple that is checked against a cache history of received IPv6 packet identifiers. In some systems, it may be necessary for an intermediate system (gateway) that is injecting the packet into a MANET area to apply the DPD marking when the original source has not. In this document, such an intermediate system is referred to as a "tagger" (i.e., "tagging" the packet with DPD information) and a "Tagger ID" field is provided in the DPD marking mechanism described below. In the case that a packet is tagged, SMF may perform DPD processing on a or depending upon the policy handling the case of multiple gateways injecting and tagging multiple copies of the same packet flow. The usage of the "Tagger ID" is described in further detail in Section 8. Similarly to the case for IPv4, the presence of IPSec may prevent the intermediate addition of a hop-by-hop options header. Again, the IPSec header provides a packet identifier field that can be used on a "per-security association" basis. The IP addressing fields and IPSec Security Parameters Index (SPI) fields are used to identify security associations and, hence, packet flows. So, if the packet is IPSec encapsulated, SMF will check the where the or from the IPv6 IPSec header serves as a "packetIdentifier" value. 5.2.1. IPv6 SMF-DPD Header Option Format Figure 2 illustrates the format of the IPv6 SMF Duplication Packet Detection (SMF-DPD) hop-by-hop header option. If this is the only hop-by-hop option present, the optional "Tagger ID" field is not included, and the size of the DPD packet identifier (sequence number) is 24 bits or less, this will result in the addition of 8 bytes to the IPv6 packet header including the "Next Header", "Header Extension Length", SMF-DPD option fields, and padding. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 17] Internet-Draft SMF for MANET March 2007 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... | Option Type | Opt. Data Len | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |IdType | IdLen | Tagger ID (optional) ... | +-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | DPD packet identifier ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Fig. 2 - IPv6 SMF-DPD Hop-by-hop Header Option "Option Type" = (TBD pending IANA assignment) "Opt. Data Len" = Length of option content (I.e., 1 + ( ? ( + 1): 0) + Length(DPD ID)). "IdType" = 4-bit type of optional "Tagger ID" field. An enumeration of initial type values is given below. "IdLen" = 4-bit length of optional "Tagger ID" field in bytes minus one iff non-zero IdType (I.e., if IdType is non-zero and IdLen==0, then the length of the "Tagger ID" field is one byte). The "IdLen" field MUST be set to ZERO if "IdType" is ZERO. Tagger ID = identifies an intermediate node that has applied the SMF- DPD option to the packet (instead of the source). DPD packet identifier = monotonically increasing n-bit sequence number assigned on a per or basis. If "IdType" is non-zero, the length of this field is ( - - 2). Otherwise, the length of this field is ( - 1). The following list of Tagger ID type values are defined below. Additional Tagger "IdType" values may be assigned in subsequent specifications. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 18] Internet-Draft SMF for MANET March 2007 +---------+-------+-------------------------------------------------+ | Name | Value | Purpose | +---------+-------+-------------------------------------------------+ | NULL | 0 | Indicates no "Tagger ID" field is present. | | | | IdLen MUST be also set to ZERO. | | | | | | DEFAULT | 1 | The "Tagger ID" field of unknown context is | | | | present. "IdLen + 1" defines field length in | | | | bytes. | | | | | | IPv4 | 2 | The "Tagger ID" represents an IPv4 address. | | | | The "IdLen" MUST be set to 3. | | | | | | IPv6 | 3 | The "Tagger ID" represents an IPv4 address. | | | | The "IdLen" MUST be set to 15 | +---------+-------+-------------------------------------------------+ This format allows a quick check of the "IdType" field to detect whether a "Tagger ID" is present. If "IdType" is NULL, then the length of the "DPD packet identifier" (sequence number) corresponds to ( - 1). If the "IdType" is not NULL, then the length of the "Tagger ID" field is equal to ( + 1) and the remainder of the option content comprises the "DPD packet identifier" field. When the "Tagger ID" field is present, duplicate packet detection SHALL be conducted using the tuple from the packet to identify the applicable sequence space. When the "Tagger ID" field is not present, then it is assumed that the source host applied the DPD option and the packet's SHALL be used to identify the sequence space for duplicate packet detection. Thus "Tagger ID" fields sized up to 16 bytes may be applied and the size of the DPD packet identifier is configurable to meet the needs of different network environments. In fact, if an 8-bit "Tagger ID" and a 16-bit "DPD packet identifier" are used, the size of the SMF-DPD hop-by-hop header extension would still be the minimum possible IPv6 size if no other options are present. The rationale for providing "Tagger ID" context (i.e., the "IdType" field) is that the tagger identifier may correspond to some commonly- available identifier such as an IP address so that management of a specific identifier space for gateways possibly applying the SMF-DPD may not be necessary. While the context of the "Tagger ID" (what the "Tagger ID" actually represents) is not necessary for SMF DPDprocessing, it is possible that this context may be useful as part of additional network management or policies that might be operate in concert with SMF. Figure 3 illustrates a specific example of the SMF-DPD option format Macker, editor & SMF Design Team Expires September 6, 2007 [Page 19] Internet-Draft SMF for MANET March 2007 when the "Tagger ID" is _not_ applied and a 16-bit "DPD packet identifier" is used. It is RECOMMENDED that a 16-bit "DPD packet identifier" be used for most purposes. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... | Option Type |OptDataLen = 3 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |IdType&IdLen=0 | DPD packet identifier | ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Fig. 3 - Example SMF-DPD Option w/ no "Tagger ID" and 16-bit DPD ID Macker, editor & SMF Design Team Expires September 6, 2007 [Page 20] Internet-Draft SMF for MANET March 2007 6. Relay Set Selection As mentioned SMF MUST support CF-based forwarding as a basic forwarding mechanism when optimized relay set information is not available or not selected. In CF mode, each node transmits a locally generated or newly received packet exactly once. The DPD technique mentioned in the previous section is critical to proper operation and avoids any duplicate packet retransmissions by the same forwarding node. In the requirements sections, it was stated that SMF MUST support the ability to modify forwarding rules based upon relay set information received dynamically during operation. In this way, SMF can operate more efficiently within the MANET multicast area as neighborhoods change. In the section we define the interface and processing semantics to allow SMF to support a variety of different relay set algorithms and approaches. Here is a recommended criteria list for relay set selection algorithm candidates: 1. Robust with respect to mobility or other network dynamics 2. Minimal signaling requirements for neighborhood discovery and/or control 3. Support for preference levels for/against selection as relay Some relay set algorithms that meet this criteria are described in the Appendices of this document. Different algorithms may be more suitable for different MANET routing types or deployments. Additional relay set selection algorithms may be specified in separate documents in the future. The Appendices in this document can serve as a template for the content of such potential future specifications. In present SMF implementations the relay set information is often derived from a coexistent unicast MANET protocol's calculation of an optimized relay set. From current experience, extra pruning may be required when utilizing a relay set from a independent routing protocol process, since a CDS relay set formed for the unicast control plane flooding MAY include a larger set of nodes than desired for the purposes of SMF. The election and maintienance heuristics should also be considered to optimize the use in forwarding multicast application data. Certain heuristics and pruning strategies may lead to poor performance in even in small MANET multicast networks. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 21] Internet-Draft SMF for MANET March 2007 7. SMF Neighborhood Discovery Requirements In absence of a compatible, coexisting unicast routing protocol or lower layer protocol providing neighborhood topology information sufficient for relay set selection, this section defines the issues and additional requirements for a MANET Neighborhood Discovery Protocol (NHDP) that MAY be operational between SMF nodes. With respect to neighborhood topology knowledge and/or discovery, there are three basic modes of SMF operation: 1. Classical Flooding (CF) mode: with no requirements for discovery or knowledge of neighborhood topology, 2. External CDS control mode: an external process dynamically determines the local SMF relay status (e.g., SMF prototypes have leveraged neighborhood topology information collected by MANET unicast routing protocols such as OLSRv2 or Manet-OSPF ), and 3. Independent CDS control mode: SMF uses the MANET Neighborhood Discovery Protocol (NHDP) [NHDP] to collect localized link information required for the various CDS algorithm modes discussed in the Appendices. We have previously discussed modes 1 and 2. This section will describe mode 3, using NHDP to support CDS relay set capability independent of any MANET unicast routing protocol process. This design uses and is consistent with the Generalized MANET Packet/ Message Format [PacketBB] and NHDP protocol work in progress within the MANET WG. 7.1. NHDP Description and SMF Requirements Core NHDP messages and the neighborhood information base are described separately within the NHDP specification (ref). In this mode, SMF uses and relies upon an implementation of NHDP. The NHDP protocol provides the following basic functions: 1. 1-hop neighbor link sensing: maintaining neighbor lists and performing a basic bidirectionality check of neighbor links 2. 2-hop Neighborhood Discovery: collecting 2-hop bidirectional neighborhood information and any information relevant to relay set election 3. The collection and maintenance of the above information across multiple interfaces. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 22] Internet-Draft SMF for MANET March 2007 4. Relay Set Signaling: signal relay set selection to neighbor nodes if the relay set algorithm requires such information Macker, editor & SMF Design Team Expires September 6, 2007 [Page 23] Internet-Draft SMF for MANET March 2007 8. SMF Multicast Border Gateway Considerations Typically, it is expected that SMF will be used to distribute multicast traffic within a MANET area. However, it is also envisioned to allow interconnection of SMF operation with networks using other multicast routing protocols if appropriate conditions are met. It is important to note that there are many issues that need to be resolved for this type of interconnection to successfully occur: 1. Determining which multicast groups should transit the gateway whether entering or exiting the attached MANET area(s). 2. TTL threshold or other scoping policies. 3. Any marking or labeling to enable DPD on ingressing packets. 4. Interface with exterior multicast routing protocols. 5. Possible operation with multiple gateways (presently beyond scope of this document). 6. Provision for participating non-SMF nodes. Note the behavior of gateway nodes is the same as that of non-gateway nodes when forwarding packets on interfaces within the MANET area. And packets that are passed outbound to interfaces operating typical multicast routing protocols SHOULD be evaluated for duplicate packet status since present standard multicast forwarding mechanisms do not usually perform this function. 8.1. Forwarded Multicast Groups Determining which groups should be forwarded into a MANET SMF area is problematic. Ideally, only groups for which there is active group membership should be injected into the SMF domain. This might be accomplished by providing an IPv4 Internet Group Membership Protocol (IGMP) or IPV6 Multicast Listener Discovery (MLD) proxy protocol so that MANET SMF nodes can inform attached gateways (and hence multicast networks) of their current group membership status. For specific systems and services it may be possible to statically configure group membership in border gateways, but it is RECOMMENDED that some form of IGMP/MLD proxy or other explicit, dynamic control of membership be provided. Specification of such an IGMP/MLD proxy protocol is beyond the scope of this document. Outbound traffic is less problematic. SMF gateways can perform duplicate packet detection and forward non-duplicate traffic that meets TTL/hop limit and scoping criteria to other interfaces. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 24] Internet-Draft SMF for MANET March 2007 Appropriate IP multicast routing (PIM, etc) on those interfaces can then make further forwarding decisions with respect to the given traffic and its MANET source address. Note that the presence of multiple gateways associated with a MANET area may create some additional issues. This is further discussed in Section 8.5. 8.2. Multicast Group Scoping Multicast scoping is used by network administrators to control the network areas which are reached by multicast packets. This is usually done by configuring external interfaces of gateways in the border of an area to not forward multicast packets which must be kept within the area. This is commonly done based on TTL of messages or group addresses. These schemes are known respectively as: 1. TTL scoping. 2. Administrative scoping. For IPv4, network administrators can configure gateways with the appropriate TTL thresholds or administratively scoped multicast groups in the router's interfaces as with any traditional multicast router. However, for the case of TTL scoping it must be taken into account that the packet could traverse multiple hops within the MANET SMF area before reaching the gateway. Thus, TTL thresholds must be selected carefully. For IPv6, multicast addresses themselves include information about the scope of the group. Thus, gateways in the border of an area know if they must forward a packet based on the IPv6 multicast group address. For the case of IPv6, we recommend a MANET SMF routing area be designated a site. Thus, all multicast packets in the range FF05::/16 will be kept within the MANET SMF area by gateways. Packets in any other wider range (i.e. FF08::/16, FF0B::/16 and FF0E::16) will traverse gateways unless any other restrictions different from the scope applies. Given that scoping of multicast packets is performed at the area gateways, and given that existing scoping mechanisms are not designed to work with mobile routers, we assume that non-gateway SMF nodes, will not stop forwarding multicast data packets because of their scope. That is, we assume that the whole MANET SMF area is an non- divisible scoping area except in the case of link-local addresses that are not forwarded by SMF. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 25] Internet-Draft SMF for MANET March 2007 8.3. Duplicate Packet Detection Marking Packets sourced external to an SMF area may not have duplicate packet sequencing properly applied and the gateway may need to provide that sequencing information upon entry into the MANET area. In the case of IPv6, the gateway can apply the SMF DPD Hop-by-Hop options header to packets forwarded into the MANET area for those packets that do not already have the option applied. If this option has been applied, this indicates the packet has already been marked for potential handling by SMF relays. Similarly, IP packets that have been encapsulated with IPSec may also be treated as appropriately marked for DPD and may be forwarded without modification. Both of these indicators (the IPv6 SMF DPD option and IPSec encapsulation) provide the side benefit for the gateway to explicitly determine if the packet has already been marked. In this case, the gateway can use the packet identification field to ensure it is not re-injecting a duplicate packet into the MANET area. For IPv4 packets that are not IPSec encapsulated, it is RECOMMENDED that gateway nodes re- sequence the ID field of packets injected into the area. However, the IPv4 ID field does not provide the gateway with explicit information on whether the field has been previously set for SMF purposes. Thus, the potential exists that duplicate IPv4 packets may be re-injected by a gateway into an SMF area if a multicast routing loop has occurred. If multiple multicast gateways are envisioned, additional considerations must be taken into account and solutions are considered out of scope for this document. See Section 8.5 for more discussion of related issues. 8.4. Interface with Exterior Multicast Routing Protocols The traditional operation of multicast routing protocols is tightly integrated with the group membership function. Leaf routers are configured to periodically gather group membership information, while intermediate routers conspire to create multicast trees connecting routers with directly-connected multicast sources and routers with active multicast receivers. In the concrete case of SMF, we can consider gateways as leaf routers. Mechanisms for multicast sources and receivers to interoperate with gateways over the multihop MANET SMF area as if they were directly connected to the router need to be defined. The following issues need to be addressed: 1. Mechanism by which gateways gather membership information. 2. Mechanism by which multicast sources are known by the gateway. 3. Exchange of exterior routing protocol messages across the MANET area if the MANET area is to provide transit connectivity for multicast traffic. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 26] Internet-Draft SMF for MANET March 2007 It is beyond the scope of this document to address implementation solutions to these issues. As described in Section 8.1, IGMP/MLD proxy mechanisms can be deployed to address some of these issues. Similarly, exterior routing protocol messages could be tunneled or conveyed across the MANET area. But, because MANET areas are multi- hop and potentially unreliable, as opposed to the single-hop LAN interconnection that neighboring IP Multicast routers might typically enjoy, additional provisions may be required to achieve successful operation. The need for the gateway to receive traffic from recognized multicast sources within the MANET SMF area is important to achieve a smooth interworking with existing routing protocols. For instance, protocols like PIM-SM, a commonly used multicast protocol, require routers with locally attached multicast sources to register them to the Rendezvous Point (RP) so that other people can join the multicast tree. In addition, if those sources are not advertised to other autonomous systems (AS) using MSDP, receivers in those external networks are not able to join the multicast tree for that source. 8.5. Multiple Gateways A MANET might be deployed with multiple participating nodes having connectivity to external (to the MANET), fixed-infrastructure networks. Allowing multiple nodes to forward multicast traffic to/ from the MANET area can be beneficial since it can increase reliability, and provide better service. For example, if the MANET area were to fragment with different MANET nodes maintaining connectivity to different gateways, multicast service could still continue successfully. But, the case of multiple gateways connecting a MANET area to external networks presents several challenges for SMF: 1. Detection/sequencing of duplicate unmarked IPv4 or IPv6 (without IPSec encapsulation or DPD option) packets possibly injected by multiple gateways. 2. Source-based relay algorithms handling of duplicate traffic injected by multiple gateways. 3. Determination of which gateway(s) will forward outbound multicast traffic. 4. Additional challenges with interfaces to exterior multicast routing protocols. One of the most obvious issues is when multiple gateways are present and may be alternatively (due to route changes) or simultaneously Macker, editor & SMF Design Team Expires September 6, 2007 [Page 27] Internet-Draft SMF for MANET March 2007 injecting common traffic into the MANET area that has not been previously marked for SMF DPD. Different gateways would not be able to implicitly synchronize sequencing of injected traffic since they may not receive exactly the same messages due to packet losses. For IPv6 operation, the "Tagger ID" optional field described for the SMF- DPD header option can be used to mitigate this issue. When multiple gateways are injecting a flow into a MANET area, there are two forwarding policies that SMF nodes may implement: 1. Redundantly forward the multicast flows (identified by ) from each gateway, performing DPD processing on a or basis, or 2. Use some basis to select the flow of one tagger (gateway) over the others and forward packets for applicable flows (identified by ) only for that "Tagger ID" until timeout or some other criteria to favor another tagger occurs. It is RECOMMENDED that the first approach be used unless the SMF system is specifically designed to implement the second option. Additional specification may be required to describe an interoperable forwarding policy based on this second option. Note that the implementation of the second option requires that per-flow (i.e., ) state be maintained for the selected "Tagger ID". 8.6. Non-SMF MANET Nodes There may be scenarios in which some MANET nodes may not wish to run the SMF protocol and/or conduct forwarding, but they are interested in receiving multicast data. For example, a MANET service might be deployed that is accessible to wireless edge devices that do not participate in MANET routing and/or SMF forwarding operation. These devices include: 1. Devices that opportunistically receive multicast traffic due to proximity with SMF relays. 2. Devices that participate in NHDP (directly or via routing protocol signaling) but do not forward traffic. Note there is no guarantee of traffic delivery with category 1 above, so it is RECOMMENDED that nodes participate in NHDP when possible. Such devices may also transmit multicast traffic, but it is important to note that SMF areas using source-specific relay set algorithms such as (S-MPR) may not forward such traffic. These devices SHOULD Macker, editor & SMF Design Team Expires September 6, 2007 [Page 28] Internet-Draft SMF for MANET March 2007 also listen for any IGMP/MLD Queries that are provided and transmit IGMP/MLD Reports for groups they have joined per usual IP Multicast operation. While it is not in the scope of this document, IGMP/MLD proxy mechanisms may be in place to convey group membership information to any border gateways or intermediate systems providing IP Multicast routing functions. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 29] Internet-Draft SMF for MANET March 2007 9. Security Considerations Gratuitous use of option headers can cause problems in routers. Routers outside of MANET routing areas should ignore SMF header options if encountered. Authentication mechanisms to identify the source of an option header should be considered to reduce vulnerability to a variety of attacks. Additional security consideration TBD. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 30] Internet-Draft SMF for MANET March 2007 10. IANA Considerations There are number of discussions within this SMF specification that will be subject to IANA registration. The IP Header Extensions being defined within this document MUST have an IANA registry established for them upon publication of the first RFC. Additionally, the well- known multicast addresses intended for default use by the SMF forwarding process should be registered and defined by the first RFC published. These IANA considerations may in common or may be handed in conjunction with other MANET protocol efforts including the General Message Format specification and potentially common neighborhood discovery protocol considerations. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 31] Internet-Draft SMF for MANET March 2007 11. Acknowledgments Many of the concepts and mechanisms used and adopted by SMF resulted from many years of discussion of related work within the MANET WG. There are obviously many people that have contributed to past discussions and related draft documents within the WG that have influenced the development of SMF concepts that deserve acknowledgment. In particular, the document is largely a direct product of the SMF design team within the IETF MANET WG and borrows text and implementation ideas from the related individuals. Some of the contributors who have been involved in document content editing or discussions are listed below. We appreciate input from others we may have missed in this list as well. SMF Core Design Team Contributors: Brian Adamson Ian Chakeres Thomas Clausen Justin Dean Brian Haberman Charles Perkins Pedro Ruiz Maoyu Wang The RFC text was produced using Marshall Rose's xml2rfc tool. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 32] Internet-Draft SMF for MANET March 2007 12. References 12.1. Normative References [E-CDS] Ogier, R., "MANET Extension of OSPF Using CDS Flooding", Proceedings of the 62nd IETF , March 2005. [MPR-CDS] Adjih, C., Jacquet, P., and L. Viennot, "Computing Connected Dominating Sets with Multipoint Relays", Ad Hoc and Sensor Wireless Networks , January 2005. [NHDP] Clausen, T. and et al, "Neighborhood Discovery Protocol", draft-ietf-manet-ndp-00, Work in progress , July 2006. [OLSRv2] Clausen, T. and et al, "Optimized Link State Routing Protocol version 2", draft-ietf-manet-olsrv2-00, Work in progress , March 2006. [PacketBB] Clausen, T. and et al, "Generalized MANET Packet/Message Format", draft-ietf-manet-packetbb-00, Work in progress , March 2006. [RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791, September 1981. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing Protocol", 2003. 12.2. Informative References [GJ79] Garey, M. and D. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness.", Freeman and Company , 1979. [JLMV02] Jacquet, P., Laouiti, V., Minet, P., and L. Viennot, "Performance of multipoint relaying in ad hoc mobile routing protocols", Networking , 2002. [MDC04] Macker, J., Dean, J., and W. Chao, "Simplified Multicast Forwarding in Mobile Ad hoc Networks", IEEE MILCOM 2004 Proceedings , 2004. [NTSC99] Ni, S., Tseng, Y., Chen, Y., and J. Sheu, "The Broadcast Storm Problem in Mobile Ad hoc Networks", Proceedings Of Macker, editor & SMF Design Team Expires September 6, 2007 [Page 33] Internet-Draft SMF for MANET March 2007 ACM Mobicom 99 , 1999. [RFC2901] Macker, JP. and MS. Corson, "Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations", 1999. [RFC3684] Ogier, R., Templin, F., and M. Lewis, "Topology Dissemination Based on Reverse-Path Forwarding", 2003. [WC02] Williams, B. and T. Camp, "Comparison of Broadcasting Techniques for Mobile Ad hoc Networks", Proceedings of ACM Mobihoc 2002 , 2002. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 34] Internet-Draft SMF for MANET March 2007 Appendix A. Source-based Multipoint Relay (S-MPR) The source-based multipoint relay (S-MPR) set selection algorithm enables individual nodes, using two-hop topology information to select a minimum set of neighboring nodes that can provide relay to all nodes within a two-hop radius. This distributed technique has been shown to approximate selection of a MCDS in [JLMV02]. Individual nodes must collect two-hop neighborhood information from neighbors, determine an appropriate current relay set, and then inform the resultant selected neighbors of their relay status. The Optimized Link State Routing (OLSR) protocol has used this algorithm and protocol for relay of link state updates and other control information[RFC3626] and has been shown to operate well even in dynamic network environments. Because a node's status as a relay is with respect to neighboring nodes who have selected it (i.e., its "selectors"), the relaying node must know the previous-hop transmitter of packets it receives in order to make an appropriate forwarding decision. Additionally, it is important that relay nodes forward packets only for those nodes currently identified as symmetric, one-hop neighbors to maintain correctness. Also, because the selection of relays does not result in a common set among neighboring nodes, relays MUST mark in their duplicate table any transmissions from non-selector, symmetric, one- hop neighbors (for a given interface) and not forward subsequent received copies of that packet even if received from a selector neighbor. Deviation here may result in unnecessary, even excessive, repeat transmission of packets throughout the network. Or incorrect duplicate table recording of packets received from non-symmetric neighbors may result in incomplete flooding. In these respects, flooding based on the S-MPR algorithm is more complex than that based upon some other relay set selection algorithms. When multiple interfaces are present, the S-MPR SMF forwarded must keep some independent state for each interface with regards to duplicate packets. For example, when a packet is received from a non-selector, one-hop symmetric neighbor, an SMF forwarder using the S-MPR algorithm must update its duplicate packet state with respect to the interface on which the packet was received. If the SMF forwarder receives that same packet from a selector neighbor on a different interface, it MUST still forward that packet on all interfaces it has not received that packet from a one-hop symmetric neighbor. Once a packet has been forwarded in this fashion, subsequent duplicates received on any interface are ignored. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 35] Internet-Draft SMF for MANET March 2007 A.1. S-MPR Relay Set Selection If SMF is operating S-MPR relay set election independent of coexistent OLSR operation, based upon NHDP mechanisms, the election algorithm defined within RFC3626 [RFC3626] should be used. A.2. Neighborhood Discovery Requirements S-MPR election operation requires 2-hop neighbor knowledge as provided by the NHDP protocol[NHDP] or as available from external sources. MPRs are dynamically selected by each node and selections MUST be advertised and dynamically updated within the SMF NDP or equivalent protocol. In this mode, the MPR specific TLVs defined in OLSRv2 [OLSRv2]are also required to be implemented by NHDP. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 36] Internet-Draft SMF for MANET March 2007 Appendix B. Essential Connecting Dominating Set (E-CDS) Algorithm The "Essential Connected Dominating Set" (E-CDS) algorithm [E-CDS] allows nodes to use two-hop topology information to appropriately elect _themselves_ as relay nodes to form an efficient (for flooding) CDS. While this algorithm does not tend to produce as small a set of relay nodes (per forwarded packet) as the previously-described S-MPR algorithm, it is not dependent upon previous-hop information to make a forwarding decision; it simply forwards any received non-duplicate packets. This property also allows relay nodes using the E-CDS algorithm to be intermixed with nodes performing only classical flooding. Additionally, the semantics for multiple interface support are simplified as compared to S-MPR and even packets that are received from non-symmetric neighbors may be forwarded without compromising flooding efficiency or correctness. B.1. E-CDS Relay Set Selection This section provides a short description of the E-CDS based relay set selection algorithm and is based upon Richard Ogier's original summary within [E-CDS]. This was originally discussed in the context of forming partial adjacencies and efficient flooding for MANET-OSPF work but its core algorithm is applied here. E-CDS requires two-hop neighbor information collected through the SMF-NDP or other process. Each router has a Router Identifier (may be represented by an interface address) and Router Priority value. The Router Priority value may be dynamic and represent such metrics as node degree. The fundamental election steps are as follows: 1. If an SMF node has a higher (Router Priority, Router ID) than all of its symmetric neighbors, it elects itself to the relay set. 2. Else, if there does not exist a path from neighbor j with largest (Router Priority, Router ID) to some other neighbor, via neighbors with larger values of (Router Priority, Router ID), then it elects itself to the relay set. The basic form of E-CDS described and applied within this specification does not at present define redundant relay set election but such capability is supported by the E-CDS design. B.2. E-CDS Forwarding Rules E-CDS forwarding is quite simple and straightforward. As mentioned, there is no need to check previous hop information during forwarding. Upon electing itself as an E-CDS relay set forwarder, SMF nodes perform DPD functions and forward all ranges of non-duplicative Macker, editor & SMF Design Team Expires September 6, 2007 [Page 37] Internet-Draft SMF for MANET March 2007 multicast traffic allowed by the present forwarding policy. B.3. Neighborhood Discovery Requirements To support functions required by the core E_CDS relay set algorithm the following TLV is required to be transmitted by each node within a NHDP HELLO message: *Router Priority*: type=SMF_ROUTER_PRIORITY, length=1, value = priority* For E-CDS operation, some value of SMF_ROUTER_PRIORITY must be given or assumed for each address in the portion of the SMF_HELLO message. If a SMF_HELLO message originator does not provide a SMF_ROUTER_PRIORITY value for given address(es), a default value SMF_RPRI_DEFAULT=(TBD) should be assumed. Local determination of a node SMF_ROUTER_PRIORITY value can be done in multiple ways as described in the [E-CDS]. An early implementation of SMF and E-CDS has used node degree computed during neighbor discovery, yet it is still unclear if this is the best method. Unlike the MPR method, the E-CDS is a self-electing algorithm. SMF_ROUTER_PRIORITY needs to be shared with all immediate neighbor nodes and 2-hop neighbor knowledge is needed during the self election process. Further algorithm examples and details are covered in the Appendices. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 38] Internet-Draft SMF for MANET March 2007 Appendix C. Multipoint Relay Connected Dominating Set (MPR-CDS) Algorithm The MPR-CDS algorithm is an extension to the basic MPR election algorithm and results in a shared relay set that forms a CDS. Its forwarding rules within SMF are non-dependent upon previous hop information similar to E-CDS. C.1. MPR-CDS Relay Set Selection An overview of the MPR-CDS selection algorithm is provided in [MPR-CDS]. The basic requirements for election are similar to the basic MPR algorithm with the addtion that some node ordering knowledge is required. This is similar to the E-CDS requirement and can be based upon node IP address or some other unique router identifier. The rules for election are as follows: A node decides it is in the relay set if: 1. the node is smaller than all its neighbors (Rule 1) 2. or the node is an MPR of its smallest neighbor (Rule 2) C.2. MPR-CDS Forwarding Rules MPR-CDS forwarding are quite simple and straightforward. As with E-CDS, there is no need to check previous hop information during forwarding. Upon electing itself as a MPR-CDS relay set forwarder, SMF nodes perform DPD functions and forward all ranges of multicast traffic allowed. C.3. Neighborhood Discovery Requirements No additional discovery requirements are needed beyond the basic MPR- related TLVs already discussed. Macker, editor & SMF Design Team Expires September 6, 2007 [Page 39] Internet-Draft SMF for MANET March 2007 Authors' Addresses Joseph Macker NRL Washington, DC 20375 USA Email: macker@itd.nrl.navy.mil SMF Design Team IETF MANET WG Email: manet@ietf.org Macker, editor & SMF Design Team Expires September 6, 2007 [Page 40] Internet-Draft SMF for MANET March 2007 Full Copyright Statement Copyright (C) The IETF Trust (2007). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Intellectual Property The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Acknowledgment Funding for the RFC Editor function is provided by the IETF Administrative Support Activity (IASA). Macker, editor & SMF Design Team Expires September 6, 2007 [Page 41]