Network Working Group J. Macker, editor
Internet-Draft NRL
Intended status: Experimental SMF Design Team
Expires: August 28, 2008 IETF MANET WG
February 25, 2008
Simplified Multicast Forwarding for MANET
draft-ietf-manet-smf-07
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 August 28, 2008.
Copyright Notice
Copyright (C) The IETF Trust (2008).
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 1]
Internet-Draft SMF for MANET February 2008
Abstract
This document describes a Simplified Multicast Forwarding (SMF)
mechanism that provides basic IP multicast forwarding suitable for
wireless mesh and mobile ad hoc network (MANET) use. SMF specifies
techniques for multicast duplicate packet detection (DPD) to assist
the forwarding process. SMF also specifies DPD maintenance and
checking operations for with both IPv4 and IPv6. SMF takes advantage
of reduced relay sets for efficient MANET multicast data distribution
within a mesh topology. The document describes interactions with
other protocols and multiple deployment approaches. Algorithms for
selecting reduced relay sets and related discussion are provided in
the Appendices. Basic issues relating to the operation of multicast
MANET border routers are discussed but ongoing work remains in this
area beyond the scope of this document.
Table of Contents
1. Requirements Notation . . . . . . . . . . . . . . . . . . . . 4
2. Introduction and Scope . . . . . . . . . . . . . . . . . . . . 5
2.1. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 7
3. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 9
4. SMF Packet Processing and Forwarding . . . . . . . . . . . . . 10
5. SMF Duplicate Packet Detection . . . . . . . . . . . . . . . . 13
5.1. IPv6 Duplicate Packet Detection . . . . . . . . . . . . . 14
5.1.1. IPv6 SMF-DPD Header Option . . . . . . . . . . . . . . 14
5.1.2. IPv6 Identification-based DPD . . . . . . . . . . . . 16
5.1.3. IPv6 Hash-based DPD . . . . . . . . . . . . . . . . . 18
5.2. IPv4 Duplicate Packet Detection . . . . . . . . . . . . . 19
5.2.1. IPv4 Identification-based DPD . . . . . . . . . . . . 20
5.2.2. IPv4 Hash-based DPD . . . . . . . . . . . . . . . . . 21
5.3. Internal Hash Computation Considerations . . . . . . . . . 22
6. Reduced Relay Set Forwarding and Relay Selection Capability . 23
7. SMF Neighborhood Discovery Requirements . . . . . . . . . . . 26
7.1. SMF Relay Algorithm TLV Types . . . . . . . . . . . . . . 27
7.1.1. Relay Algorithm Message TLV Type . . . . . . . . . . . 27
7.1.2. Relay Algorithm Address Block TLV Type . . . . . . . . 28
7.2. SMF Router Priority TLV Types . . . . . . . . . . . . . . 29
7.2.1. Router Priority Message TLV Type . . . . . . . . . . . 29
7.2.2. Router Priority Address Block TLV Type . . . . . . . . 29
8. SMF Border Gateway Considerations . . . . . . . . . . . . . . 31
8.1. Forwarded Multicast Groups . . . . . . . . . . . . . . . . 31
8.2. Multicast Group Scoping . . . . . . . . . . . . . . . . . 32
8.3. Interface with Exterior Multicast Routing Protocols . . . 33
8.4. Multiple Border Routers . . . . . . . . . . . . . . . . . 34
9. Non-SMF MANET Node Interaction . . . . . . . . . . . . . . . . 36
10. Security Considerations . . . . . . . . . . . . . . . . . . . 37
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 2]
Internet-Draft SMF for MANET February 2008
11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 38
11.1. IPv6 SMF_DPD Header Extension . . . . . . . . . . . . . . 38
11.2. SMF NHDP TLV Types . . . . . . . . . . . . . . . . . . . . 38
12. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 41
13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 42
13.1. Normative References . . . . . . . . . . . . . . . . . . . 42
13.2. Informative References . . . . . . . . . . . . . . . . . . 43
Appendix A. Source-based Multipoint Relay (S-MPR) . . . . . . . . 45
A.1. S-MPR Relay Set Selection Overview . . . . . . . . . . . . 45
A.2. S-MPR Forwarding Rules . . . . . . . . . . . . . . . . . . 46
A.3. S-MPR Neighborhood Discovery Requirements . . . . . . . . 47
A.4. S-MPR Selection Algorithm . . . . . . . . . . . . . . . . 47
Appendix B. Essential Connecting Dominating Set (E-CDS)
Algorithm . . . . . . . . . . . . . . . . . . . . . . 50
B.1. E-CDS Relay Set Selection Overview . . . . . . . . . . . . 50
B.2. E-CDS Forwarding Rules . . . . . . . . . . . . . . . . . . 51
B.3. E-CDS Neighborhood Discovery Requirements . . . . . . . . 51
B.4. E-CDS Selection Algorithm . . . . . . . . . . . . . . . . 52
Appendix C. Multipoint Relay Connected Dominating Set
(MPR-CDS) Algorithm . . . . . . . . . . . . . . . . . 54
C.1. MPR-CDS Relay Set Selection Overview . . . . . . . . . . . 54
C.2. MPR-CDS Forwarding Rules . . . . . . . . . . . . . . . . . 55
C.3. MPR-CDS Neighborhood Discovery Requirements . . . . . . . 55
C.4. MPR-CDS Selection Algorithm . . . . . . . . . . . . . . . 56
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 58
Intellectual Property and Copyright Statements . . . . . . . . . . 59
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 3]
Internet-Draft SMF for MANET February 2008
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 August 28, 2008 [Page 4]
Internet-Draft SMF for MANET February 2008
2. Introduction and Scope
MANET unicast routing protocol designs have demonstrated effective
and efficient mechanisms to flood routing control plane messages
throughout a wireless routing area. For example, algorithms
specified within [RFC3626] and [RFC3684] provide distributed methods
of dynamically electing reduced relay sets that attempt to optimize
flooding of routing control messages amongst MANET routing peers.
Simplified Multicast Forwarding (SMF) extends this efficient flooding
concept to the data forwarding plane for IP multicast packets. When
localized, efficient flooding is deemed an effective technique, SMF
provides an appropriate multicast forwarding capability. The SMF
baseline design is intended to provide a basic, best effort multicast
forwarding capability that is constrained to operate within a MANET
or wireless mesh routing region. The main design goals of this SMF
specification are to adapt efficient relay sets in MANET environments
[RFC2901] and define the needed IPv4 and IPv6 multicast duplicate
packet detection (DPD) mechanisms to support multi-hop, packet
forwarding. 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 self-election) will occur based on input from a
neighborhood discovery process, and the forwarding process will often
be determined by dynamic relay set selection. Note the neighborhood
discovery and/or relay set selection information MAY be obtained from
a coexistent process (e.g., MANET unicast routing protocol using
relay sets). In some cases, the forwarding decision for a packet can
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 August 28, 2008 [Page 5]
Internet-Draft SMF for MANET February 2008
______________ _____________
| | | |
| Neighborhood | | Relay Set |
| Discovery |------------->| Selection |
| Protocol | neighbor | Algorithm |
|______________| info |_____________|
\ /
\ /
neighbor\ /forwarding
info* \ ____________ / status
\ | | /
`-->| Forwarding |<--'
| Process |
~~~~~~~~~~~~~~~~~>|____________|~~~~~~~~~~~~~~~~~>
incoming packet, forwarded packets
interface id, and
previous hop*
Figure 1: SMF Node Architecture
Interoperable SMF implementations MUST use a common DPD approach and
be able to process the header options defined in this document for
IPv6 operation. We define Classical Flooding (CF), as the simplest
case of SMF multicast forwarding. With CF, each SMF router forwards
each received forwardable multicast packet once. In this case, the
need for any relay set selection or neighborhood topology information
is eliminated but DPD is still required. While SMF supports a CF
mode the use of more efficient relay set modes is RECOMMENDED to
reduce contention and congestion caused by unnecessary packet
retransmissions [NTSC99]. An efficient, reduced relay set is
realized by selecting and maintaining a _subset_ of all possible SMF
routers in a MANET routing region. Known relay set selection
algorithms have demonstrated the ability to provide and maintain a
dynamic distribution mesh for forwarding user multicast data [MDC04].
A few such relay set selection algorithms are described in the
Appendices of this document and the basic designs borrow directly
from previous work. Additional relay set algorithms or extensions
may be specified for future used with SMF.
Dynamic neighborhood topology information is often needed to
determine and maintain an optimized set of relay (forwarding) nodes.
Neighborhood topology discovery functions MAY be externally provided
by a MANET unicast routing protocol or by using the MANET
NeighborHood Discovery Protocol (NHDP) [NHDP] running in concurrence
with SMF. Additionally, this specification does not preclude a lower
protocol layer from providing necessary neighborhood information.
Fundamentally, an SMF implementation SHOULD provide the ability for
multicast forwarding state to be dynamically managed per operating
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 6]
Internet-Draft SMF for MANET February 2008
network interface. Some of the relay state maintenance options and
interactions are outlined later in Section 6. This document states
specific requirements for neighborhood discovery with respect to the
forwarding process and the relay set selection algorithms described
herein. In the absence of a MANET unicast protocol or lower layer
information interface, SMF relies on the MANET NHDP specification to
assist in IP layer 2-hop neighborhood state discovery and maintenance
for relay set election in non-CF optimized modes. A "SMF_RELAY_ALG"
Message TLV type (per [PacketBB]) is defined for use with the NHDP
protocol. It is RECOMMENDED that all nodes performing SMF operation
include this TLV type in their NHDP_HELLO messages when operating
with NHDP. This capability allows for nodes participating in SMF to
be explicitly identified along with their respective CDS algorithm.
2.1. Abbreviations
The following abbreviations are used throughout this document:
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 7]
Internet-Draft SMF for MANET February 2008
+--------------+------------------------------------+
| Abbreviation | : Definition |
+--------------+------------------------------------+
| MANET | : Mobile Ad hoc Network |
| | |
| SMF | : Simplified Multicast Forwarding |
| | |
| CF | : Classical Flooding |
| | |
| CDS | : Connected Dominating Set |
| | |
| MCDS | : Minimum Connected Dominating Set |
| | |
| MPR | : Multi-Point Relay |
| | |
| S-MPR | : Source-based MPR |
| | |
| MPR-CDS | : MPR-based CDS |
| | |
| E-CDS | : Essential CDS |
| | |
| NHDP | : Neighborhood Discovery Protocol |
| | |
| DPD | : Duplicate Packet Detection |
| | |
| I-DPD | : Identification-based DPD |
| | |
| H-DPD | : Hash-based DPD |
| | |
| HAV | : Hash-assist Value |
| | |
| FIB | Forwarding Information Base |
| | |
| TLV | : type-length-value encoding |
+--------------+------------------------------------+
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 8]
Internet-Draft SMF for MANET February 2008
3. Applicability
Within dynamic, wireless routing topologies, maintaining traditional
forwarding trees to support a multicast routing protocol is often not
as effective as in wired networks due the reduced reliability and
increased dynamics of the mesh topology [MGL04] and [GM99].__ A basic
packet forwarding service that reaches all MANET SMF routers
participating within a localized routing region may provide a useful
group communication paradigm for various classes of applications.
Applications that could take advantage of a simple multicast
forwarding service within a MANET routing region include multimedia
streaming, interactive group-based messaging and applications, peer-
to-peer middleware multicasting, and multi-hop mobile discovery or
registration services.
Note again that Figure 1 provides a notional architecture for
_typical_ MANET SMF-capable nodes. However, a goal is that simple
end-system (non-forwarding) wireless nodes may also participate in
multicast traffic transmission and reception with standard IP network
layer semantics (e.g., special or unnecessary encapsulation of IP
packets should be avoided in this case). A multicast border router
or proxy mechanism MUST be used when deployed alongside more fixed-
infrastructure IP multicast routing such Protocol Independent
Multicast (PIM) variants [RFC3973] and [RFC4601]. With present
experimental implementations, proxy methods have demonstrated gateway
functionality at MANET border routers operating with external IP
multicast routing protocols. SMF may be extended or combined with
other mechanisms to provide increased reliability and group specific
filtering, but the details for this are not discussed here.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 9]
Internet-Draft SMF for MANET February 2008
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).
The purpose of intercepting outbound, locally-generated multicast
packets is to apply any added packet marking needed to satisfy the
DPD requirements described later so that proper forwarding may be
conducted. Note that for some system configurations interception of
outbound packets for this purpose is not necessary.
Inbound multicast packets will be received by the SMF implementation
and processed for possible forwarding. This document does not
presently support forwarding of directed broadcast addresses
[RFC2644]. SMF implementations MUST be capable of forwarding "global
scope" multicast packets to support generic multicast application
needs or to distribute designated multicast traffic that ingresses
the MANET routing region via border routers. The multicast addresses
to be forwarded will be maintained by an _a priori_ list or a dynamic
forwarding information base (FIB) that MAY interact with future MANET
dynamic group membership extensions. There will also be well-known
multicast group for flooding to all SMF forwarders. This multicast
group is specified to contain all MANET SMF routers of a connected
MANET routing region, so that packets transmitted to the multicast
address associated with the group will be delivered to all connected
SMF routers. For IPv6, the multicast address is specified to be
"site-local". The name of the multicast group is "SL-MANET-ROUTERS".
Minimally SMF SHALL forward, as instructed by the relay set selection
algorithm, unique (non-duplicate) packets received for this well-
known group address when the TTL or hop count value in the IP header
is greater than 1. SMF SHALL forward all additional global scope
addresses specified within the FIB as well. 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 SMF router interface(s) MUST NOT be
forwarded.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 10]
Internet-Draft SMF for MANET February 2008
4. Received packet frames with the MAC source address matching the
local SMF router interface(s) MUST NOT be forwarded.
5. Received packets for which SMF cannot reasonably ensure temporal
DPD uniqueness MUST NOT be forwarded.
6. When packets are forwarded, TTL or hop limit SHALL be decremented
by one.
Note that rule #3 is important because in wireless networks, the
local SMF router 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.
An additional processing rule also needs to be considered based upon
a potential security threat. As discussed further in Section 10,
there may be concern in some SMF deployments that malicious nodes may
conduct a denial-of-service attack by remotely "previewing" (e.g.,
via a directional receive antenna) packets that an SMF node would be
forwarding and conduct a "pre-play" attack by transmitting the packet
before the SMF node would otherwise receive it but with a reduced TTL
(or Hop Limit) field value. This form of attack could cause an SMF
node to create a DPD entry that would block the proper forwarding of
the valid packet (with correct TTL) through the SMF area. A
RECOMMENDED approach to prevent this attack, when it is a concern,
would be to cache temporal packet TTL values along with the DPD state
(hash value(s) and/or identifier). Then, if a subsequent matching
(with respect to DPD) packet arrives with a _larger_ TTL value than
the packet that was previously forwarded, then SMF should forward the
new packet _and_ update the TTL cached with corresponding DPD state
to the new, larger TTL value. There may be temporal cases where SMF
may unnecessarily forward some duplicate packets using this approach,
but those cases are expected to be minimal and acceptable when
compared with the potential threat outcome of denied service.
Once these criteria have been met, an SMF implementation MUST make a
forwarding decision dependent upon the relay set selection algorithm
in use. If the SMF implementation is using Classical Flooding (CF),
the forwarding decision is implicit once DPD uniqueness is
determined. Otherwise, a forwarding decision depends upon the
current interface-specific relay set state. The descriptions of the
relay set selection algorithms in the Appendices to this document
specify the respective heuristics for multicast packet forwarding and
specific DPD or other processing required to achieve correct SMF
behavior. For example, one class of forwarding is based upon relay
set election status _and_ the packet's previous hop (e.g. S-MPR
forwarding), while other classes designate the local SMF router as a
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 11]
Internet-Draft SMF for MANET February 2008
forwarder of all neighbor packets based on the neighborhood topology
(e.g. E-CDS and MPR-CDS).
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 12]
Internet-Draft SMF for MANET February 2008
5. SMF Duplicate Packet Detection
Duplicate packet detection (DPD) is a common requirement in MANET
packet forwarding because packets may be transmitted out the same
physical interface upon which they arrived and nodes may also receive
copies of previously-transmitted packets from other forwarding
neighbors. SMF implementations MUST detect and avoid forwarding
duplicate multicast packets using temporal packet identification. It
is RECOMMENDED this be implemented by keeping a history of recently-
processed multicast packets for comparison to incoming packets. For
both IPv4 and IPv6, this document describes two basic approaches to
multicast duplicate packet detection: header content identification-
based (I-DPD) and hash-based (H-DPD) duplicate detection. The two
approaches are described for experimental purposes. Trade-offs of
the two approaches to DPD may merit different consideration depending
upon specific SMF deployment scenarios. Because of the potential
addition of a hop-by-hop option header with IPv6, SMF deployments
MUST be configured to use a common mechanism and DPD algorithm. The
main difference between IPv4 and IPv6 SMF DPD specification is the
avoidance of any additional header options in the IPv4 case.
For each network interface, SMF implementations MUST maintain DPD
packet state as needed to support the forwarding heuristics of the
relay set algorithm used. The specific requirements of several relay
set selection algorithms and their forwarding rules are described in
the Appendices of this document. In general this involves keeping
track of previously forwarded packets so that duplicates are not
forwarded, but some relay techniques (e.g., S-MPR) have additional
considerations.
For I-DPD, packets are identified using explicit identifiers from the
IP header. The specific identifier to use depends upon the IP
protocol version and the type of packet. For example, IPv4 [RFC0791]
provides an "Identification" field that can assist a DPD mechanism,
and packets that contain IPSec protocol headers also provide suitable
packet identifiers. Fragmented packets also provide additional
identifiers that need to be considered. These identifier fields are
unique within the context of source address, destination address,
protocol type, and/or other header fields depending upon the type of
identifier used for DPD. Similarly, for H-DPD, it is expected that
packet hash values will be kept with respect to at least the source
address to help ensure hash collision avoidance. SMF implementations
MUST maintain DPD history per the applicable packet flow context
(e.g., <protocol:srcAddr:dstAddr> for DPD based upon IPv4 ID). The
details for I-DPD and H-DPD for different types of packets are
described in the sections below. In either case, this history SHOULD
be kept long enough to span the maximum network traversal lifetime,
MAX_PACKET_LIFETIME, of multicast packets being forwarded within an
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 13]
Internet-Draft SMF for MANET February 2008
SMF operating area. The required size of the DPD cache is governed
by this timeout value and is also a function of the packet forwarding
rates. The DPD 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. IPv6 Duplicate Packet Detection
This section describes the mechanisms and options for SMF IPv6 DPD.
The core IPv6 packet header does not provide any explicit
identification header field that can be exploited for I-DPD. The
following areas are described to support IPv6 DPD:
1. a hop-by-hop SMF-DPD option header (with supporting identifier or
hash assistance value),
2. the use of IPv6 fragment header fields for I-DPD when they exist,
3. the use of IPSec sequencing for I-DPD when a non-fragmented,
IPSec header is detected, and
4. an H-DPD approach assisted, as needed, by the SMF-DPD option
header.
SMF MUST provide a DPD marking module that can insert the hop-by-hop
IPv6 header option defined in this section. This process MUST come
after any source-based fragmentation that may occur with IPv6. As
with IPv4, SMF IPv6 DPD is presently specified to allow either a
packet hash or header identification method for DPD. An SMF
implementation MUST be configured to operate either in H-DPD or I-DPD
mode and perform the appropriate routines outlined in the following
sections.
5.1.1. IPv6 SMF-DPD Header Option
As previously mentioned, the base IPv6 packet header does not contain
a unique identifier suitable for DPD. This section defines an IPv6
Hop-by-Hop Option to serve this purpose for IPv6 I-DPD.
Additionally, the Option defined provides for a mechanism to
guarantee non-collision of hash values for different packets when
H-DPD is used. The value of the IPv6 SMF_DPD Hop-by-Hop Option Type
is TBD.
The first bit of the data field of the SMF-DPD option is the "H-bit"
that determines the format of the Option Data content. Two different
formats are supported. When the "H-bit" is cleared (zero value), the
SMF-DPD format to support I-DPD operation is specified as shown in
Figure 2 and defines the extension header in accordance with
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 14]
Internet-Draft SMF for MANET February 2008
[RFC2460].
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
... |0|0|0| OptType | Opt. Data Len |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|TidTyp|TidLen| TaggerId (optional) ... |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | Identifier ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 2: IPv6 SMF-DPD Header Option in I-DPD mode
The "TidType" is a 3-bit field indicating the presence and type of
the optional "TaggerId" field. The optional "TaggerId" is used to
differentiate multiple ingressing border gateways that may commonly
apply the SMF-DPD option header to packets from a particular source.
This is provided for experimental purposes. The following table
lists the valid TaggerId types:
+---------+-------+-------------------------------------------------+
| Name | Value | Purpose |
+---------+-------+-------------------------------------------------+
| NULL | 0 | Indicates no "taggerId" field is present. |
| | | "TidLen" MUST also be set to ZERO. |
| | | |
| DEFAULT | 1 | A "TaggerId" of non-specific context is |
| | | present. "TidLen + 1" defines the length of |
| | | the TaggerId field in bytes. |
| | | |
| IPv4 | 2 | A "TaggerId" representing an IPv4 address is |
| | | present. The "TidLen" MUST be set to 3. |
| | | |
| IPv6 | 3 | A "TaggerId" representing an IPv6 address is |
| | | present. The "TidLen" MUST be set to 15. |
| | | |
| ExtId | 7 | RESERVED FOR FUTURE USE (possible extended ID) |
+---------+-------+-------------------------------------------------+
This format allows a quick check of the "TidType" field to determine
if a "TaggerId" field is present. If the <TidType> is NULL, then the
length of the DPD packet <Identifier> field corresponds to the (<Opt.
Data Len> - 1). If the <TidType> is non-NULL, then the length of the
"TaggerId" field is equal to (<TidLen> - 1) and the remainder of the
option data comprises the DPD packet <Identifier> field. When the
"TaggerId" field is present, the <Identifier> field can be considered
a unique packet identifier in the context of the <taggerId:srcAddr:
dstAddr> tuple. When the "TaggerId" field is not present, then it is
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 15]
Internet-Draft SMF for MANET February 2008
assumed the source host applied the SMF-DPD option and the
<Identifier> can be considered unique in the context of the IPv6
packet header <srcAddr:dstAddr> tuple. IPV6 I-DPD operation details
are described in Section 5.1.2.
When the "H-bit" in the SMF-DPD option data is set, the data content
value is interpreted as a Hash-Assist Value (HAV) used to facilitate
H-DPD operation. In this case, source hosts or ingressing gateways
apply the SMF-DPD with a HAV only when required to differentiate the
hash value of a new packet with respect to older packets in the
current DPD history cache. This helps to guarantee the uniqueness of
generated hash values when H-DPD is used. Additionally, this also
avoids the added overhead of applying the SMF-DPD option header to
every packet. For many hash algorithms, it is expected that only
sparse use of the SMF-DPD option may be required. The format of the
SMF-DPD header option for H-DPD operation is given in Figure 3.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
... |0|0|0| OptType | Opt. Data Len |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0| Hash Assist Value (HAV) ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 3: IPv6 SMF_DPD Header Option in H-DPD Mode
The SMF-DPD option should be applied with a HAV to produce a unique
hash digest for packets within the context of the IPv6 packet header
<srcAddr>. The size of the HAV field is implied by the "Opt. Data
Len". The appropriate size of the field depends upon the collision
properties of the specific hash algorithm used. More details on IPv6
H-DPD operation are provided in Section 5.1.3.
5.1.2. IPv6 Identification-based DPD
The following table summarizes the IPv6 I-DPD processing approach.
Within the table '*' indicates a don't care condition.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 16]
Internet-Draft SMF for MANET February 2008
IPv6 I-DPD Processing Rules
+-------------+-----------+-----------+-----------------------------+
| IPv6 | IPv6 | IPv6 | SMF IPv6 I-DPD Mode Action |
| Fragment | IPSec | I-DPD | |
| Header | Header | Header | |
+-------------+-----------+-----------+-----------------------------+
| Present | * | * | Use Fragment Header I-DPD |
| | | | Check and Process for |
| | | | Forwarding |
| | | | |
| Not Present | Present | * | Use IPSec Header I-DPD |
| | | | Check and Process for |
| | | | Forwarding |
| | | | |
| Present | * | Present | Invalid, do not Forward |
| | | | |
| Not Present | Present | Present | Invalid, do not Forward |
| | | | |
| Not Present | Not | Not | Add I-DPD Header,and |
| | Present | Present | Process for Forwarding |
| | | | |
| Not Present | Not | Present | Use I-DPD Header Check and |
| | Present | | Process for Forwarding |
+-------------+-----------+-----------+-----------------------------+
If the IPv6 multicast packet is an IPv6 fragment, SMF MUST use the
fragment extension header fields for packet identification. This
identifier can be considered unique in the context of the <srcAddr:
dstAddr> of the IP packet. If the packet is an unfragmented IPv6
IPSec packet, SMF MUST use IPSec fields for packet identification.
The IPSec header <sequence> field can be considered a unique
identifier in the context of the <IPSecType:srcAddr:dstAddr:SPI>
where the "IPSecType" is either AH or ESP. For unfragmented, non-
IPSec, IPv6 packets, the use of the SMF DPD header option is
necessary to support I-DPD operation. The SMF DPD header option is
applied in the context of the <srcAddr> of the IP packet. End
systems or ingressing SMF gateways are responsible for applying this
option to support DPD. The following table summarizes these packet
identification types:
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 17]
Internet-Draft SMF for MANET February 2008
*IPv6 I-DPD Packet Identification Types*
+-----------+---------------------------------+---------------------+
| IPv6 | Packet DPD ID Context | Packet DPD ID |
| Packet | | |
| Type | | |
+-----------+---------------------------------+---------------------+
| Fragment | <srcAddr:dstAddr> | <fragmentOffset:id> |
| | | |
| IPSec | <IPSecType:srcAddr:dstAddr:SPI> | <sequence> |
| Packet | | |
| | | |
| Regular | <[taggerId:]srcAddr:dstAddr> | <SMF-DPD option |
| Packet | | header id> |
+-----------+---------------------------------+---------------------+
"IPSecType" is either Authentication Header (AH) or Encapsulating
Security Payload (ESP).
The "taggerId" is an optional feature of the IPv6 SMF-DPD header
option.
5.1.3. IPv6 Hash-based DPD
A default hash-based DPD approach (H-DPD) for use by SMF is specified
as follows. An MD5 [RFC1321] hash of the non-mutable header fields,
options fields, and data content of the IPv6 multicast packet is used
to produce a 128-bit digest. The lower 64 bits of this digest
(MD5_64) is used for SMF packet identification. The approach for
calculating this hash value SHOULD follow the same guidelines
described for calculating the Integrity Check Value (ICV) described
in [RFC4302] with respect to non-mutable fields. This approach
should have a reasonably low probability of digest collision when
packet headers and content are varying. MD5 is being applied in SMF
only to provide a low probability of collision and is not being used
for cryptographic or authentication purposes. A history of the
packet hash values SHOULD be maintained within the context of the
IPv6 packet header <srcAddr>. This history is used by forwarding SMF
nodes (non-ingress points) to avoid forwarding duplicates. SMF
ingress points (i.e., source hosts or gateways) use this history to
confirm that new packets are unique with respect to their hash value.
The Hash-assist Value (HAV) field described in Section 5.1.1 is
provided as a differentiating field when a digest collision would
otherwise occur. Note that the HAV is an immutable option field and
SMF MUST use any included H-DPD hash assist value (HAV) option header
(see Section 5.1.1) in its hash calculation.
If a packet results in a digest collision (i.e., by checking the
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 18]
Internet-Draft SMF for MANET February 2008
H-DPD digest history) within the limited history kept by SMF
forwarders, the packet should be silently dropped. If a digest
collision is detected at an SMF ingress point (i.e., including SMF-
aware sources), the H-DPD option header is applied with a HAV. The
packet is retested for collision and the HAV is re-applied as needed
to produce a non-colliding hash value. The multicast packet is then
forwarded with the added IPv6 SMF-DPD header option.
The MD5 indexing and IPv6 HAV approaches are specified at present for
consistency and robustness to suit experimental uses. Future
approaches and experimentation may discover designs tradeoffs in hash
robustness and efficiency worth considering. This MAY include
reducing the maximum payload length that is processed, determining
shorter indexes, or applying more efficient hashing algorithms. Use
of the HAV functionality may allow for application of "lighter-
weight" hashing techniques that might not have been initially
considered due to poor collision properties otherwise. Such
techniques could reduce packet processing overhead and memory
requirements.
5.2. IPv4 Duplicate Packet Detection
This section describes the mechanisms and options for IPv4 DPD. The
IPv4 packet header 16-bit "Identification" field MAY be used for DPD
assistance, but practical limitations may require alternative
approaches in some situations. The following areas are described to
support IPv4 DPD::
1. the use of IPv4 fragment header fields for I-DPD when they exist,
2. the use of IPSec sequencing for I-DPD when a non-fragmented IPv4
IPSec packet is detected, and
3. a H-DPD approach.
A specific SMF-DPD marking option is not specified for IPv4 since
header options are not as tractable for end systems as for IPv6.
IPv4 packets from a particular source are assumed to be marked with a
temporally unique value in the "Identification" field of the packet
header that can serve for SMF DPD purposes. However, in present
operating system networking kernels, the IPv4 header "Identification"
value is not always generated properly, especially when the "don't
fragment" (DF) bit is set. The IPv4 I-DPD mode of this specification
requires that IPv4 "Identification" fields are managed reasonably by
source hosts and that temporally unique values are set within the
context of the packet header <protocol:srcAddr:dstAddr> tuple. If
this is not expected during an SMF deployment, then it is RECOMMENDED
that the H-DPD method be used as a more reliable approach.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 19]
Internet-Draft SMF for MANET February 2008
Since IPv4 SMF does not specify an options header, the
interoperability constraints are looser than the IPv6 version and
forwarders may be operate with mixed H-DPD and I-DPD modes as long as
they consistently perform the appropriate DPD routines outlined in
the following sections. However, it is RECOMMENDED that a deployment
be configured with a common mode for operational consistency.
5.2.1. IPv4 Identification-based DPD
The following table summarizes the IPv4 I-DPD processing approach
once a packet has passed the basic forwardable criteria described in
earlier SMF sections. Within the table '*' indicates a don't care
condition.
+----+----+----------+---------+------------------------------------+
| df | mf | fragment | IPSec | IPv4 I-DPD Action |
| | | offset | | |
+----+----+----------+---------+------------------------------------+
| 1 | 1 | * | * | Invalid, Do Not Forward |
| | | | | |
| 1 | 0 | nonzero | * | Invalid, Do Not Forward |
| | | | | |
| * | 0 | zero | not | Tuple I-DPD Check and Process for |
| | | | Present | Forwarding |
| | | | | |
| * | 0 | zero | Present | IPSec enhanced Tuple I-DPD Check |
| | | | | and Process for Forwarding |
| | | | | |
| 0 | 0 | nonzero | * | Extended Fragment Offset Tuple |
| | | | | I-DPD Check and Process for |
| | | | | Forwarding |
| | | | | |
| 0 | 1 | zero or | * | Extended Fragment Offset Tuple |
| | | nonzero | | I-DPD Check and Process for |
| | | | | Forwarding |
+----+----+----------+---------+------------------------------------+
For performance reasons, IPv4 network fragmentation and reassembly of
multicast packets within wireless MANET networks should be minimized,
yet SMF provides the forwarding of fragments when they occur. If the
IPv4 multicast packet is a fragment, SMF MUST use the fragmentation
header fields for packet identification. This identification can be
considered temporally unique in the context of the <protocol:srcAddr:
dstAddr> of the IPv4 packet. If the packet is an unfragmented IPv4
IPSec packet, SMF MUST use IPSec fields for packet identification.
The IPSec header <sequence> field can be considered a unique
identifier in the context of the <IPSecType:srcAddr:dstAddr:SPI>
where the "IPSecType" is either AH or ESP. Finally, for
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 20]
Internet-Draft SMF for MANET February 2008
unfragmented, non-IPSec, IPv4 packets, the "Identification" field can
be used for I-DPD purposes. The "Identification" field can be
considered unique in the context of the IPv4 <protocol:scrAddr:
dstAddr> tuple. The following table summarizes these packet
identification types:
*IPv4 I-DPD Packet Identification Types*
+-----------+---------------------------------+---------------------+
| IPv4 | Packet Identification Context | Packet Identifier |
| Packet | | |
| Type | | |
+-----------+---------------------------------+---------------------+
| Fragment | <protocol:srcAddr:dstAddr> | <fragmentOffset:id> |
| | | |
| IPSec | <IPSecType:srcAddr:dstAddr:SPI> | <sequence> |
| Packet | | |
| | | |
| Regular | <protocol:srcAddr:dstAddr> | <id> |
| Packet | | |
+-----------+---------------------------------+---------------------+
"IPSecType" is either Authentication Header (AH) or Encapsulating
Security Payload (ESP).
The limited size (16 bits) of the IPv4 header "Identification" field
may result in the value rapidly wrapping, particularly if a common
sequence space is used by a source for multiple destinations. If
I-DPD operation is required, the use of the "internal hashing"
technique described in Section 5.3 may mitigate this limitation of
the IPv4 "Identification" field for SMF DPD. In this case the
"internal hash" value would be concatenated with the "Identification"
value for I-DPD operation.
5.2.2. IPv4 Hash-based DPD
To ensure consistent IPv4 H-DPD operation among SMF nodes, a default
hashing approach is specified. This is similar to that specified for
IPv6, but the H-DPD header option with HAV is not considered. SMF
MUST perform an MD5 [RFC1321] hash of the immutable header fields,
option fields and data content of the IPv4 multicast packet resulting
in a 128-bit digest. The lower 64 bits of this digest (MD5_64) is
used for SMF packet identification. The approach for calculating the
hash value SHOULD follow the same guidelines described for
calculating the Integrity Check Value (ICV) described in [RFC4302]
with respect to non-mutable fields. A history of the packet hash
values SHOULD be maintained in the context of <protocol:srcAddr:
dstAddr>. The context for IPv4 is more specific than that of IPv6
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 21]
Internet-Draft SMF for MANET February 2008
since the SMF-DPD HAV cannot be employed to mitigate hash collisions.
The MD5 hash is specified at present for consistency and robustness.
Future approaches and experimentation may discover designs tradeoffs
in hash robustness and efficiency worth considering for future
versions of SMF. This MAY include reducing the packet payload length
that is processed, determining shorter indexes, or applying a more
efficient hashing algorithm.
5.3. Internal Hash Computation Considerations
Forwarding protocols that use DPD techniques, such as SMF, may be
vulnerable to denial-of-service (DoS) attacks based on spoofing
packets with apparently valid packet identifier fields. Such a
consideration is pointed out in Section 10. In wireless environments
where SMF will most likely be used, the opportunity for badly-
behaving nodes to conduct such attacks is more prevalent than in
wired networks. In the case of IPv4 packets, fragmented IP packets
or packets with IPSec headers applied, the DPD "identifier" of
potential future packets that might be forwarded is very predictable
and easily subject to denial-of-service attacks against forwarding.
A RECOMMENDED technique to counter this concern is for SMF
implementations to generate an "internal" hash value that is
concatenated with the explicit I-DPD packet identifier to form a
unique identifier that is a function of the packet content as well as
the visible identifier. SMF implementations could seed their hash
generation with a random value to make it unlikely that an external
observer could guess how to spoof packets used in a denial-of-service
attack against forwarding. Since the hash computation and state is
kept completely internal to SMF nodes, the cryptographic properties
of this hashing would not need to be extensive and thus possibly of
low complexity. Experimental implementations may determine that a
lightweight hash of even only portions of packets may suffice to
serve this purpose.
For IPv4 I-DPD based on the limited 16-bit IP header "Identification"
field, it is possible that use of this "internal hash" technique may
also enhance I-DPD performance in cases where the IPv4
"Identification" field may wrap quickly due to the source supporting
high data rate flows.
While H-DPD is not as readily susceptible to this form of DoS attack,
it is possible that a sophisticated adversary could use side
information to construct spoofing packets to mislead forwarders using
a well-known hash algorithm. Thus, similarly, a separate "internal"
hash value could be concatenated with the well-known hash value to
alleviate this security concern.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 22]
Internet-Draft SMF for MANET February 2008
6. Reduced Relay Set Forwarding and Relay Selection Capability
SMF implementations MUST support CF as a basic forwarding mechanism
when reduced relay set information is not available or not selected
for operation. In CF mode, each node transmits a locally generated
or newly received packet exactly once. The DPD techniques described
in Section 5 are critical to proper operation and prevent duplicate
packet retransmissions by the same forwarding node.
A goal of SMF is to apply reduced relay sets for more efficient
multicast dissemination within dynamic topologies. To accomplish
this SMF MUST support the ability to modify its multicast packet
forwarding rules based upon relay set state received dynamically
during operation. In this way, SMF forwarding can continue to
operate effectively as neighbor adjacencies or multicast forwarding
policies within the topology change.
In early SMF experimental deployments, the relay set information has
been derived from a coexistent unicast MANET protocol that selected a
reduced relay set for control plane traffic. From this experience,
extra pruning considerations where sometimes required when utilizing
a relay set from a separate routing protocol process, since a relay
set formed for the unicast control plane flooding MAY include a more
redundant set of nodes than desired for multicast forwarding use
(e.g., biconnected control plane CDS meshes).
Here is a recommended criteria list for SMF relay set selection
algorithm candidates:
1. Robustness to topological dynamics and mobility
2. Localized election or coordination of any relay sets
3. Reasonable minimization of relay set size to achieve CDS given
above constraints
4. Heuristic support for preference or election metrics (Better
enables scenario-specific management of relay set)
Some relay set algorithms meeting these 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 specifications in the future. The Appendices in this
document can serve as a template for the content of such potential
future specifications.
Figure 4 depicts a state information diagram of possible relay set
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 23]
Internet-Draft SMF for MANET February 2008
control options.
Possible L2 Trigger/Information
|
|
______________ ______v_____ __________________
| MANET | | | | |
| Neighborhood | | Relay Set | | Other Heuristics |
| Discovery |----------->| Selection |<------| (Preference,etc) |
| Protocol | neighbor | Algorithm | | |
|______________| info |____________| |__________________|
\ /
\ /
neighbor\ / Dynamic Relay
info* \ ____________ / Set Status
\ | SMF | / (State, {neighbor info})
`-->| Relay Set |<--'
| State |
-->|____________|
/
/
______________
| Coexistent |
| MANET |
| Unicast |
| Process |
|______________|
Figure 4: Smf Relay Set Control Options
There are basically three styles of SMF operation with reduced relay
sets:
1. Independent operation: SMF performs its own relay set selection
using information from an associated MANET NHDP process. In this
case, NHDP messaging SHOULD be appended with additional
[PacketBB] type-length-value (TLV) content to support SMF-
specific requirements as discussed in Section 7 and for the
applicable relay set algorithm described in the Appendices of
this document or future specifications.
2. Operation with CDS-aware unicast routing protocol: Coexistent
unicast routing protocol provides dynamic relay set state based
upon its own control plane CDS or neighborhood discovery
information. If it is desired that the SMF data plane forwarding
use a different relay set selection algorithm than used for the
routing protocol control plane, then the routing protocol NHDP
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 24]
Internet-Draft SMF for MANET February 2008
instance (if applicable) SHOULD append its messages with the
appropriate SMF-specific TLV content (see Section 7 and the relay
set algorithm Appendices).
3. Cross-layer Operation: SMF operates using neighborhood status and
triggers from a cross-layer (e.g., layer 2 MAC or link layer)
information base for dynamic relay set selection and maintenance.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 25]
Internet-Draft SMF for MANET February 2008
7. SMF Neighborhood Discovery Requirements
This section defines the requirements for use of the MANET
Neighborhood Discovery Protocol (NHDP) [NHDP] to support SMF
operation. Note that basic CF forwarding requires no neighborhood
topology knowledge since every SMF node relays all traffic while
supporting more efficient SMF relay set operation requires the
discovery and maintenance of dynamic neighborhood (1- and 2-hop
knowledge) topology information. The MANET NHDP protocol can provide
this necessary information, but in some circumstances there are a few
SMF-specific requirements for related NHDP use. This can be the case
for both "independent" SMF operation where NHDP is being used
specifically to support SMF or when one NHDP instance is used for
both for SMF and a coexistent MANET unicast routing protocol.
Core NHDP messages and the resultant neighborhood information base
are described separately within the NHDP specification. To
summarize, the NHDP protocol provides the following basic functions:
1. 1-hop neighbor link sensing and bidirectionality checks of
neighbor links,
2. 2-hop neighborhood discovery including collection of 2-hop
neighbors and connectivity information,
3. Collection and maintenance of the above information across
multiple interfaces, and
4. Signaling relay set selection to neighbor nodes if the relay set
algorithm requires such information (e.g. S-MPR ).
The Appendices of this document describe a set of CDS-based relay set
selection algorithms that can be used to achieve efficient SMF
operation, even in dynamic, mobile networks[MDDA07]. For some of
these algorithms, the core NHDP specification provides all the
necessary information to conduct relay set selection. For others,
NHDP messaging needs to be extended to support relay set selection
and maintenance. For example, the [OLSRv2] specification specifies
TLV constructs for NHDP messages to support its use of the S-MPR
algorithm for control plane messaging. An independent SMF
implementation using S-MPR can also use these same OLSRv2 TLV types
to support its operation.
The following sub-sections specify some SMF-specific TLV types to
support general SMF operation or to support the algorithms described
in the Appendices to this document. The Appendices describing each
of the relay set algorithms also specify any additional requirements
for NHDP to support their operation and reference the applicable TLV
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 26]
Internet-Draft SMF for MANET February 2008
types as needed.
7.1. SMF Relay Algorithm TLV Types
This section specifies TLV types to be used within NHDP messages to
identify the CDS relay set selection algorithm(s) in use. Two TLV
types are defined, one message TLV type and one address TLV type.
7.1.1. Relay Algorithm Message TLV Type
The message TLV type denoted SMF_RELAY_ALG is used to identify the
CDS relay set selection algorithm currently in use by the NHDP
message originator. When NHDP is used to support SMF operation, the
SMF_RELAY_ALG TLV SHOULD be included in NHDP_HELLO messages
generated. This allows SMF nodes to learn when neighbors are
configured to use different relay set algorithms. This information
can be used to take action, such as ignoring neighbor information
using incompatible algorithms. It is possible that SMF neighbors MAY
be configured differently and still operate cooperatively, but these
cases will vary dependent upon the algorithm types designated.
This document defines the following Message TLV typeTable 7
conforming to [PacketBB] to communicate "Relay Algorithm Type" to
other 1-hop SMF neighbors.
+--------+---------------------+--------------------+
| | packetBB TLV syntax | Field Values |
+--------+---------------------+--------------------+
| type | <tlvType> | SMF_RELAY_ALG |
| | | |
| length | <length> | 1 byte |
| | | |
| value | <value> | <relayAlgorithmId> |
+--------+---------------------+--------------------+
Table 7: SMF Relay Algorithm Type Message TLV
In Table 7 <relayAlgorithmId> is an 8-bit field containing a number
0-255 representing the "Relay Algorithm Type" of the originator
address of the corresponding NHDP message.
Possible values for the <relayAlgorithmId> are defined in Table 8.
The table provides value assignments, future IANA assignment spaces,
and an experimental space. The experimental space use MUST NOT
assume uniqueness and thus should not be used for general
interoperable deployment prior to official IANA assignment.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 27]
Internet-Draft SMF for MANET February 2008
+---------------------+----------------------------------------+
| Value | Algorithm |
+---------------------+----------------------------------------+
| 0 | CF |
| | |
| 1 | S-MPR |
| | |
| 2 | E-CDS |
| | |
| 3 | MPR-CDS |
| | |
| 4-127 | Future Assignment with STD action |
| | |
| 128-239 | No STD action required |
| | |
| 240-255 | Experimental Space |
+---------------------+----------------------------------------+
Table 8: SMF Relay Algorithm Type Values
7.1.2. Relay Algorithm Address Block TLV Type
An address block TLV type, denoted SMF_NBR_RELAY_ALG (i.e., SMF
neighbor relay algorithm) Table 9, is specified so that CDS relay
algorithm configuration can be shared among 2-hop neighborhoods This
is useful for the case when mixed relay algorithm operation is
possible.
The message SMF_RELAY_ALG TLV and address block SMF_NBR_RELAY_ALG TLV
types share a common format.
+--------+---------------------+---------------------+
| | packetBB TLV syntax | Field Values |
+--------+---------------------+---------------------+
| type | <tlvType> | SMF_NBR_RELAY_ALG |
| | | |
| length | <length> | variable |
| | | |
| value | <value> | <relayAlgorithmId>* |
+--------+---------------------+---------------------+
Table 9: SMF Relay Algorithm Type Address Block TLV
Each <relayAlgorithmId> in Table 9 is an 8-bit field containing a
number 0-255 representing the "Relay Algorithm Type" value that
corresponds to the indicated address in the address block. Note that
"Relay Algorithm Type" values for 2-hop neighbors may be conveyed as
single value or multiple value TLVs as described in [PacketBB]. It
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 28]
Internet-Draft SMF for MANET February 2008
is expected that SMF nodes using NHDP shall construct address blocks
using the SMF_NBR_RELAY_ALG TLV type to share the "Relay Algorithm
Type" values of 1-hop neighbors received in SMF_RELAY_ALG TLV content
from those neighbors.
Again values for the <relayAlgorithmId> are defined in Table 8.
7.2. SMF Router Priority TLV Types
This section specifies TLV types to be used within NHDP messages to
identify SMF Router Priority values. Two TLV types are defined, one
message TLV type and one address TLV type.
For some relay set selection techniques, a value of Router Priority
must be given or assumed for each address within the 1-hop and
possibly 2-hop neighborhood. This value for a specific originator
must be consistent among neighborhood nodes. The Appendices of this
document discuss specific algorithm cases that require the use of
this TLV.
7.2.1. Router Priority Message TLV Type
This document defines the following Message TLV type Table 10 to
share "Router Priority" values among 1-hop SMF neighbors.
+--------+---------------------+------------------+
| | packetBB TLV syntax | Field Values |
+--------+---------------------+------------------+
| type | <tlvType> | SMF_RTR_PRIORITY |
| | | |
| length | <length> | 1 byte |
| | | |
| value | <value> | <priority> |
+--------+---------------------+------------------+
Table 10: SMF Router Priority Message TLV
<priority> in Table 9 is an 8-bit field containing a number 0-255
representing the "Router Priority" value of the originator
corresponding NHDP message.
7.2.2. Router Priority Address Block TLV Type
Some relay set selection algorithms require that the "Router
Priority" for 2-hop neighbors also be communicated and this can be
accomplished by including the values within address block
advertisements. An Address Block TLV type is defined with the format
in Table 11 to support this purpose.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 29]
Internet-Draft SMF for MANET February 2008
+--------+---------------------+----------------------+
| | packetBB TLV syntax | Field Values |
+--------+---------------------+----------------------+
| type | <tlvType> | SMF_NBR_RTR_PRIORITY |
| | | |
| length | <length> | variable |
| | | |
| value | <value> | <priority>* |
+--------+---------------------+----------------------+
Table 11: SMF Router Priority Address Block TLV
Each <priority> in Table 11 is an 8-bit field containing a number
0-255 representing the "Router Priority" value that corresponds to
the indicated address in the address block. Note that "Router
Priority" values for 2-hop neighbors may be conveyed as single value
or multiple value TLVs as described in [PacketBB]. It is expected
that SMF nodes using NHDP shall construct address blocks using the
SMF_NBR_RTR_PRIORITY TLV type to share the "Router Priority" values
of 1-hop neighbors received in SMF_RTR_PRIORITY TLV content from
those neighbors.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 30]
Internet-Draft SMF for MANET February 2008
8. SMF Border Gateway Considerations
It is expected that SMF will be used to provide simple forwarding of
multicast traffic _within_ a MANET mesh routing topology. A border
router approach should be used to allow interconnection of SMF areas
with networks using other multicast routing protocols (e.g., PIM).
It is important to note that there are many scenario-specific issues
that should be addressed when discussing border routers. At the
present time, experimental deployments of SMF and PIM border router
approaches are being used. Some of the functionality border routers
may need to address include the following:
1. Determining which multicast groups should transit the border
router whether entering or exiting the attached MANET routing
region(s).
2. Enforcement of 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 border routers (presently beyond
scope of this document).
6. Provisions for participating non-SMF nodes.
Note the behavior of border router SMF nodes is the same as that of
non-border SMF nodes when forwarding packets on interfaces within the
MANET routing region. Packets that are passed outbound to interfaces
operating fixed-infrastructure 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
Mechanisms for determining which groups should be forwarded into a
MANET SMF routing region is an evolving technology area. 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 border routers (and hence multicast
networks) of their current group membership status. For specific
systems and services it may be possible to statically configure group
membership joins in border routers, 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
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 31]
Internet-Draft SMF for MANET February 2008
protocol is beyond the scope of this document.
Outbound traffic is less problematic. SMF border routers can perform
duplicate packet detection and forward non-duplicate traffic that
meets TTL/hop limit and scoping criteria to other interfaces.
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 border routers associated with a MANET routing region may
create some additional issues. This is further discussed in
Section 8.4.
8.2. Multicast Group Scoping
Multicast scoping is used by network administrators to control the
network routing regions which are reached by multicast packets. This
is usually done by configuring external interfaces of border routers
in the border of an routing region to not forward multicast packets
which must be kept within the routing region. This is commonly done
based on TTL of messages or the basis of group addresses. These
schemes are known respectively as:
1. TTL scoping.
2. Administrative scoping.
For IPv4, network administrators can configure border routers 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 SHOULD be taken into
account that the packet could traverse multiple hops within the MANET
SMF routing region before reaching the border router. Thus, TTL
thresholds SHOULD be selected carefully.
For IPv6, multicast address spaces include information about the
scope of the group. Thus, border routers of an SMF routing region
know if they must forward a packet based on the IPv6 multicast group
address. For the case of IPv6, it is RECOMMENDED that a MANET SMF
routing region be designated a site. Thus, all IPv6 multicast
packets in the range FF05::/16 SHOULD be kept within the MANET SMF
routing region by border routers. IPv6 packets in any other wider
range scopes (i.e. FF08::/16, FF0B::/16 and FF0E::16) MAY traverse
border routers unless other restrictions different from the scope
applies.
Given that scoping of multicast packets is performed at the border
routers, and given that existing scoping mechanisms are not designed
to work with mobile routers, it is assumed that non-border SMF
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 32]
Internet-Draft SMF for MANET February 2008
routers will not stop forwarding multicast data packets of the
appropriate site scoping. That is, it is assumed that the entire
MANET SMF routing region is a site scoped area.
8.3. 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, border
routers can be considered leaf routers. Mechanisms for multicast
sources and receivers to interoperate with border routers over the
multihop MANET SMF routing region as if they were directly connected
to the router need to be defined. The following issues need to be
addressed:
1. Mechanism by which border routers gather membership information.
2. Mechanism by which multicast sources are known by the border
router.
3. Exchange of exterior routing protocol messages across the MANET
routing region if the MANET routing region is to provide transit
connectivity for multicast traffic.
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 routing region. But, because MANET routing
regions 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 border router to receive traffic from recognized
multicast sources within the MANET SMF routing region is important to
achieve a smooth interworking with existing routing protocols. For
instance, PIM-S requires 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.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 33]
Internet-Draft SMF for MANET February 2008
8.4. Multiple Border Routers
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 routing region can be beneficial since it can increase
reliability, and provide better service. For example, if the MANET
routing region were to fragment with different MANET nodes
maintaining connectivity to different border routers, multicast
service could still continue successfully. But, the case of multiple
border routers connecting a MANET routing region to external networks
presents several challenges for SMF:
1. Detection/hash collision/sequencing of duplicate unmarked IPv4 or
IPv6 (without IPSec encapsulation or DPD option) packets possibly
injected by multiple border routers.
2. Source-based relay algorithms handling of duplicate traffic
injected by multiple border routers.
3. Determination of which border router(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 border routers are
present and may be alternatively (due to route changes) or
simultaneously injecting common traffic into the MANET routing region
that has not been previously marked for SMF DPD. Different border
routers 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 I-DPD operation, the optional
"TaggerId" field described for the SMF-DPD header option can be used
to mitigate this issue. When multiple border routers are injecting a
flow into a MANET routing region, there are two forwarding policies
that SMF DPD-S nodes may implement:
1. Redundantly forward the multicast flows (identified by
<sourceAddress:destinationAddress>) from each border router,
performing DPD processing on a <taggerID:destinationAddress> or
<taggerID:sourceAddress:destinationAddress> basis, or
2. Use some basis to select the flow of one tagger (border router)
over the others and forward packets for applicable flows
(identified by <sourceAddress:destinationAddress>) only for that
"Tagger ID" until timeout or some other criteria to favor another
tagger occurs.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 34]
Internet-Draft SMF for MANET February 2008
It is RECOMMENDED that the first approach be used in the case of
I-DPD operation 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., <sourceAddress::destinationAddress>)
state be maintained for the selected "Tagger ID".
The deployment of a H-DPD operational mode may alleviate DPD
resolution when ingressing traffic comes from multiple border
routers. Non-colliding hash indexes (those not requiring the H-DPD
options header in IPv6) should be resolved effectively.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 35]
Internet-Draft SMF for MANET February 2008
9. Non-SMF MANET Node Interaction
There may be scenarios in which some neighboring wireless MANET node
are not running SMF and/or not forwarding, but 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, NDHDP, and/or SMF forwarding operation.
These devices include:
1. Devices that opportunistically receive multicast traffic due to
proximity with SMF relays (possibly with asymmetric IP
connectivity e.g., sensor network device).
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,
but the election heuristics shown in Figure 2 MAY be adjusted via
management to better support such devices. However, 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 routing regions using source-specific relay set
algorithms such as (S-MPR) may not forward such traffic. These
devices SHOULD 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 routers or intermediate systems
providing IP Multicast routing functions.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 36]
Internet-Draft SMF for MANET February 2008
10. Security Considerations
Gratuitous use of option headers can cause problems in routers.
Routers outside of MANET routing regions should ignore SMF-specific
header options if encountered. The header options types are encoded
appropriately for this behavior.
Sequence-based packet identifiers are predictable and thus provide an
opportunity for a denial-of-service attack against forwarding. The
use of the "internal hashing" as described in Section 5.3 for the
I-DPD operation helps to mitigate denial-of-service attacks on
predictable packet identifiers. In this case, spoofed packets MAY be
forwarded but the additional internal history identifier will protect
against false collision events that may result from a predictive
denial-of-service attack.
Another potential denial-of-service attack against SMF forwarding is
possible when a bad-behaving node has a form of "wormhole" access
(via a directional antenna, etc) to preview packets before a
particular SMF node would receive them. The bad-behaving node could
reduce the TTL or Hop Limit of the packet and transmit it to the SMF
node causing it to forward the packet with a limited TTL (or even
drop it) and make a DPD entry that would block forwarding of the
subsequently-arriving valid packet with appropriate TTL value. This
would be a relatively low-cost, high-payoff attack that would be hard
to detect and thus attractive to potential attackers. An approach of
caching TTL information with DPD state and taking appropriate
forwarding actions is identified in Section 4 to mitigate this form
of attack.
The support of forwarding IPSec datagrams without further
modification for both IPv4 and IPv6 is supported by this
specification.
Authentication mechanisms to identify the source of IPv6 option
headers should be considered to reduce vulnerability to a variety of
attacks.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 37]
Internet-Draft SMF for MANET February 2008
11. IANA Considerations
This document raises multiple IANA Considerations. These include the
IPv6 SMF_DPD hop-by-hop Header Extension defined and multiple Type-
Length-Value (TLV) constructs (see [PacketBB]) used to extend NHDP
operation as needed to support different forms of SMF operation.
11.1. IPv6 SMF_DPD Header Extension
This document requests IANA assignment of the "SMF_DPD" hop-by-hop
option type from the IANA "IPv6 Hop-by-Hop Options Option Type"
registry (see Section 5.5 of [RFC2780]).
The format of this new option type is described in Section 5.1.1. A
portion of the option data content is the "taggerIdType" that
provides a context for the "taggerId" that is optionally included to
identify the intermediate system that added the SMF_DPD option to the
packet. This document defines a name-space for IPv6 SMF_DPD Tagger
Identifier Types:
ietf:manet:smf:taggerIdTypes
The values that can be assigned within the "ietf:manet:smf:
taggerIdTypes" name-space are numeric indexes in the range [0, 7],
boundaries included. All assignment requests are granted on a "IETF
Consensus" basis as defined in [RFC2434].
This specification registers the following Tagger Identification Type
values in the registry "ietf:manet:smf:taggerIdTypes":
+----------+-------+---------------+
| Mnemonic | Value | Reference |
+----------+-------+---------------+
| NULL | 0 | This document |
| | | |
| DEFAULT | 1 | This document |
| | | |
| IPv4 | 2 | This document |
| | | |
| IPv6 | 3 | This document |
| | | |
| ExtId | 7 | This document |
+----------+-------+---------------+
11.2. SMF NHDP TLV Types
SMF defines two Message TLV types that must be allocated from the
"Assigned Message TLV Types" registry of [PacketBB]. The following
table lists the Message TLV types that must be allocated:
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 38]
Internet-Draft SMF for MANET February 2008
+------------------+-------+----------------------------------------+
| Mnemonic | Value | Description |
+------------------+-------+----------------------------------------+
| SMF_RELAY_ALG | TBD | The value field of this TLV conveys |
| | | the SMF relay set selection algorithm |
| | | of the message originator. |
| | | |
| SMF_RTR_PRIORITY | TBD | The value field of this TLV conveys |
| | | the "Router Priority" of the SMF node |
| | | originating the message. |
+------------------+-------+----------------------------------------+
Additionally, SMF also defines two corresponding Address Block TLV
types that must be allocated from the "Assigned Address Block TLV
Types" repository of [PacketBB]. The following table lists the
Address Block TLV types that must be allocated:
+----------------------+-------+------------------------------------+
| Mnemonic | Value | Description |
+----------------------+-------+------------------------------------+
| SMF_NBR_RELAY_ALG | TBD | The value field of this TLV |
| | | conveys the SMF relay set |
| | | selection algorithm of the node |
| | | associated with the corresponding |
| | | address in the address block. |
| | | |
| SMF_NBR_RTR_PRIORITY | TBD | The value field of this TLV |
| | | conveys the "Router Priority" of |
| | | the SMF ode associated with the |
| | | corresponding address in the |
| | | address block. |
+----------------------+-------+------------------------------------+
The SMF_RELAY_ALG and SMF_NBR_RELAY_ALGORITHM TLV types share a
common format with an 8-bit value field that identifies the SMF relay
selection algorithm type. This specification defines the following
name-space for SMF relay set selection algorithm types:
ietf:manet:smf:relayAlgorithms
The values that can be assigned within the "ietf:manet:smf:
relayAlgorithms" name-space are numeric indexes in the range [0,
255], boundaries included. As shown in Table 8 assignment requests
in the range [0, 127] are granted on a "IETF Consensus" basis as
defined in [RFC2434]. Assignment requests within the "ietf:manet:
smf:relayAlgorithms" namespace for the range [128,239] are granted on
a "First Come First Served" basis as defined in [RFC2434]. The
experimental space in the range [240, 255] should be reserved and not
assigned.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 39]
Internet-Draft SMF for MANET February 2008
This specification registers the following Tagger Identification Type
values in the registry "ietf:manet:smf:relayAlgorithms":
+----------+-------+-----------------------------+
| Mnemonic | Value | Reference |
+----------+-------+-----------------------------+
| CF | 0 | This document |
| | | |
| S-MPR | 1 | Appendix A of this document |
| | | |
| E-CDS | 2 | Appendix B of this document |
| | | |
| MPR-CDS | 3 | Appendix C of this document |
+----------+-------+-----------------------------+
It is RECOMMENDED that the SMF_RELAY_ALG Message TLV type be included
in NHDP messages generated by nodes configured for any form of SMF
operation.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 40]
Internet-Draft SMF for MANET February 2008
12. Acknowledgments
Many of the concepts and mechanisms used and adopted by SMF resulted
from many years of discussion and related work within the MANET WG
since the late 1990s. There are obviously many contributors 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 earlier 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 design, content
editing, prototype implementation, and core discussions are listed
below in alphabetical order. We appreciate input from many others we
may have missed in this list as well.
Design contributors in alphabetical order:
Brian Adamson
Teco Boot
Ian Chakeres
Thomas Clausen
Justin Dean
Brian Haberman
Charles Perkins
Pedro Ruiz
Fred Templin
Maoyu Wang
The RFC text was produced using Marshall Rose's xml2rfc tool and Bill
Fenner's XMLmind add-ons.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 41]
Internet-Draft SMF for MANET February 2008
13. References
13.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-nhdp-05, Work in progress ,
December 2007.
[OLSRv2] Clausen, T. and et al, "Optimized Link State Routing
Protocol version 2", draft-ietf-manet-olsrv2-04, Work in
progress , July 2007.
[PacketBB]
Clausen, T. and et al, "Generalized MANET Packet/Message
Format", draft-ietf-manet-packetbb-11, Work in progress ,
November 2007.
[RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791,
September 1981.
[RFC1321] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321,
April 1992.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC2434] Narten, T. and H. Alvestrand, "Guidelines for Writing an
IANA Considerations Section in RFCs", BCP 26, RFC 2434,
October 1998.
[RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6
(IPv6) Specification", RFC 2460, December 1998.
[RFC2644] Senie, D., "Changing the Default for Directed Broadcasts
in Routers", BCP 34, RFC 2644, August 1999.
[RFC2780] Bradner, S., "IANA Allocation Guidelines For Values In the
Internet Protocol and Related Headers", March 2000.
[RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing
Protocol", 2003.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 42]
Internet-Draft SMF for MANET February 2008
[RFC4302] Kent, S., "IP Authentication Header", December 2005.
13.2. Informative References
[GJ79] Garey, M. and D. Johnson, "Computers and Intractability: A
Guide to the Theory of NP-Completeness.", Freeman and
Company , 1979.
[GM99] Garcia-Luna-Aceves, JJ. and E. Madruga, "The core-assisted
mesh protocol", Selected Areas in Communications, IEEE
Journal on Volume 17, Issue 8, August 1999.
[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.
[MDDA07] Macker, J., Downard, I., Dean, J., and R. Adamson,
"Evaluation of distributed cover set algorithms in mobile
ad hoc network for simplified multicast forwarding", ACM
SIGMOBILE Mobile Computing and Communications Review
Volume 11 , Issue 3 (July 2007), July 2007.
[MGL04] Mohapatra, P., Gui, C., and J. Li, "Group Communications
in Mobile Ad hoc Networks", IEEE Computer Vol. 37, No. 2,
February 2004.
[NTSC99] Ni, S., Tseng, Y., Chen, Y., and J. Sheu, "The Broadcast
Storm Problem in Mobile Ad hoc Networks", Proceedings Of
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.
[RFC3973] Adams, A., Nicholas, J., and W. Siadak, "Protocol
Independent Multicast - Dense Mode (PIM-DM): Protocol
Specification (Revised)", RFC 3973, January 2005.
[RFC4601] Fenner, B., Handley, M., Holbrook, H., and I. Kouvelas,
"Protocol Independent Multicast - Sparse Mode (PIM-SM):
Protocol Specification (Revised)", RFC 4601, August 2006.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 43]
Internet-Draft SMF for MANET February 2008
[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 August 28, 2008 [Page 44]
Internet-Draft SMF for MANET February 2008
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 relays from their set of neighboring nodes. Relays are
selected so that forwarding to the node's complete two-hop neighbor
set is covered. This distributed relay set selection technique has
been shown to approximate a minimal connected dominating set (MCDS)
in [JLMV02]. Individual nodes must collect two-hop neighborhood
information from neighbors, determine an appropriate current relay
set, and inform selected neighbors of their relay status. Note that
since each node picks its neighboring relays independently, S-MPR
forwarders depend upon previous hop information (e.g, source MAC
address) to operate correctly. 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 it has
been demonstrated operationally in dynamic network environments.
It is RECOMMENDED that the SMF_RELAY_ALG message TLV be included in
NHDP_HELLO messages that are generated by nodes conducting S-MPR SMF
operation.
A.1. S-MPR Relay Set Selection Overview
A RECOMMENDED algorithm for S-MPR set selection is described in the
[OLSRv2] specification. As this algorithm has had considerable use
to support the OLSR control plane, it is expected to perform
adequately to support data plane multicast traffic. To summarize,
the S-MPR algorithm uses bi-directional 1-hop and 2-hop neighborhood
information collected via NHDP to select, from a node's 1-hop
neighbors, a set of relays that will cover the node's entire 2-hop
neighbor set upon forwarding. The algorithm described uses a
"greedy" heuristic of first picking the 1-hop neighbor who will cover
the most 2-hop neighbors. Then, excluding those 2-hop neighbors that
have been covered, additional relays from its 1-hop neighbor set are
iteratively selected until the entire 2-hop neighborhood is covered.
Note that 1-hop neighbors also identified as 2-hop neighbors are
considered as 1-hop neighbors only. This is only a partial
description of the S-MPR algorithm. The [RFC3626] specification
provides a complete description including the use of a "willingness"
metric that can be used to influence S-MPR forwarder selection. That
specification also describes a "WILLINGNESS" message TLV that can be
used in NHDP by nodes to advertise their "willingness" metric value
to their neighbors.
NHDP_HELLO messages are used to signal relay selections to 1-hop
neighbors. The "MPR" address block TLV specified in [RFC3626] MUST
be used to mark the addresses of selected neighbor relays in the
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 45]
Internet-Draft SMF for MANET February 2008
NHDP_HELLO message address block(s). It is important to note that
S-MPR forwarding is dependent upon the previous hop of an incoming
packet. A S-MPR node MUST forward packets only for neighbors which
have explicitly selected it as a relay (i.e., its "selectors").
There are also some additional requirements for duplicate packet
detection to support S-MPR SMF operation that are described below.
For multiple interface operation, MPR selection SHOULD be conducted
on a per-interface basis. However, it is possible to economize MPR
selection among multiple interfaces by selecting common MPRs to the
extent possible. It is important to note that the S-MPR forwarding
rules described in assume per-interface MPR selection (i.e. MPRs are
_not_ selected in the context of all interfaces). This is consistent
with the MPR selection heuristics described in [RFC3626]. Other
source-based approaches may be possible, but would require
alternative selection and forwarding rules be specified.
A.2. S-MPR Forwarding Rules
An S-MPR relay MUST only forward packets for neighbors that have
explicitly selected it as a forwarder. The source-based forwarding
technique also stipulates some additional duplicate packet detection
operations. For multiple network interfaces, independent DPD state
MUST be maintained for each separate interface. The following table
provides the procedure for S-MPR packet forwarding given the arrival
of a packet on a given interface, denoted <srcIface>. There are
three possible actions, depending upon the previous-hop transmitter:
1. If the previous-hop transmitter has selected the current node as
a relay,
A. The packet identifier is checked against the DPD state for
each possible outbound interface, including the <srcIface>.
B. If the packet is not a duplicate for an outbound interface,
the packet is forwarded via that interface and a DPD entry is
made for the given packet identifier for the interface.
C. If the packet is a duplicate, no action is taken for that
interface.
2. Else, if the previous-hop transmitter is a 1-hop symmetric
neighbor,
A. A DPD entry is made for that packet for the <srcIface>, but
the packet is not forwarded.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 46]
Internet-Draft SMF for MANET February 2008
3. Otherwise, no action is taken.
Case number two in the above table is non-intuitive, but important to
ensure correctness of S-MPR SMF operation. The selection of source-
based relays does not result in a common set among neighboring nodes,
so relays MUST mark in their DPD state, packets received from non-
selector, symmetric, one-hop neighbors (for a given interface) and
not forward subsequent duplicates of that packet if received on that
interface. Deviation here can result in unnecessary, repeated packet
forwarding throughout the network, or incomplete flooding.
Nodes not participating in neighborhood discovery and relay set
selection will not be able to source multicast packets into the area
and have SMF forward them. Correct S-MPR relay behavior will occur
with the introduction of repeaters (non-NHDP/SMF participants that
relay multicast packets using duplicate detection and CF) but the
repeaters will not efficiently contribute to S-MPR forwarding as
these nodes will not be identified as neighbors (symmetric or
otherwise) in the S-MPR forwarding process. NHDP/SMF participants
MUST NOT provide extra forwarding, forwarding packets which are not
selected by the algorithm, as this can disrupt network-wide S-MPR
flooding, resulting in incomplete or inefficient flooding.
A.3. S-MPR Neighborhood Discovery Requirements
S-MPR election operation requires 2-hop neighbor knowledge as
provided by the NHDP protocol [NHDP] or from external sources. MPRs
are dynamically selected by each node and selections MUST be
advertised and dynamically updated within NHDP or an equivalent
protocol or mechanism. For NHDP use, the MPR-specific TLVs defined
in OLSRv2 [OLSRv2] are also required to be implemented by NHDP. This
includes the "MPR" address block TLV type for designating selected
1-hop neighbors and the optional "WILLINGNESS" TLV described in that
specification. The NHDP or external process must also provide link-
layer (MAC) addresses of 1-hop neighbor nodes and MPR selectors so
that S-MPR forwarding can be conducted properly.
A.4. S-MPR Selection Algorithm
This section describes a basic algorithm for the S-MPR selection
process. Note that the selection is with respect to a specific
interface of the node performing selection and other node interfaces
referenced are reachable from this reference node interface. This is
consistent with the S-MPR forwarding rules described above. When
multiple interfaces per node are used, it is possible to enhance the
overall selection process across multiple interfaces such that common
nodes are selected as MPRs for each interface to avoid unnecessary
inefficiencies in flooding. This is described further in [OLSRv2].
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 47]
Internet-Draft SMF for MANET February 2008
The following steps describe a basic algorithm for conducting S-MPR
selection for a node interface "n0":
1. Initialize the set "MPR" to empty.
2. Initialize the set "N1" to include all 1-hop neighbors of "n0".
3. Initialize the set "N2" to include all 2-hop neighbors, excluding
"n0" and any nodes in "N1".
4. For each interface "y" in "N1", initialize a set "N2(y)" to
include any interfaces in "N2" that are 1-hop neighbors of "y".
5. For each interface "x" in "N1" with a willingness value of
"WILL_ALWAYS" (or using CF relay algorithm), select "x" as a MPR:
A. Add "x" to the set "MPR" and remove "x" from "N1".
B. For each interface "z" in "N2(x)", remove "z" from "N2"
C. For each interface "y" in "N1", remove any interfaces in
"N2(x)" from "N2(y)"
6. For each interface "z" in "N2", initialize the set "N1(z)" to
include any interfaces in "N1" that are 1-hop neighbors of "z".
7. For each interface "x" in "N2" where "N1(x)" has only one member,
select "x" as a MPR:
A. Add "x" to the set "MPR" and remove "x" from "N1".
B. For each interface "z" in "N2(x)", remove "z" from "N2" and
delete "N1(z)"
C. For each interface "y" in "N1", remove any interfaces in
"N2(x)" from "N2(y)"
8. While "N2" is not empty, select the interface "x" in "N1" with
the largest number of members in "N_2(x)" as a MPR:
A. Add "x" to the set "MPR" and remove "x" from "N1".
B. For each interface "z" in "N2(x)", remove "z" from "N2"
C. For each interface "y" in "N1", remove any interfaces in
"N2(x)" from "N2(y)"
After the set of nodes "MPR" is selected, node "n_0" must signal its
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 48]
Internet-Draft SMF for MANET February 2008
selections to its neighbors. With NHDP, this is done by using the
MPR address block TLV to mark selected neighbor addresses in
NHDP_HELLO messages. Neighbors MUST record their MPR selection
status and the previous hop address (e.g., link or MAC layer) of the
selector. Note these steps are re-evaluated upon neighborhood status
changes.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 49]
Internet-Draft SMF for MANET February 2008
Appendix B. Essential Connecting Dominating Set (E-CDS) Algorithm
The "Essential Connected Dominating Set" (E-CDS) algorithm [E-CDS]
allows nodes to use 2-hop neighborhood topology information to
dynamically elect _themselves_ as relay nodes to form a CDS. Its
packet forwarding rules are not dependent upon previous hop
knowledge. Additionally, E-CDS SMF forwarders can be easily mixed
without problem with CF SMF forwarders, even those not participating
in NHDP. Another benefit is that packets opportunistically received
from non-symmetric neighbors may be forwarded without compromising
flooding efficiency or correctness. Furthermore, multicast sources
not participating in NHDP may freely inject their traffic and
neighboring E-CDS relays will properly forward the traffic. The
E-CDS based relay set selection algorithm is based upon the summary
within [E-CDS]. E-CDS was originally discussed in the context of
forming partial adjacencies and efficient flooding for MANET OSPF
extensions work and the core algorithm is applied here for SMF.
It is RECOMMENDED that the SMF_RELAY_ALG message TLV be included in
NHDP_HELLO messages that are generated by nodes conducting E-CDS SMF
operation.
B.1. E-CDS Relay Set Selection Overview
The E-CDS relay set selection requires 2-hop neighborhood information
collected through NHDP or another process. Relay nodes, in E-CDS SMF
selection, are "self-elected" using a Router ID (identifier, that may
be represented by an interface address) and an optional nodal metric,
referred to here as "Router Priority" for all 1-hop and 2-hop
neighbors. To ensure proper relay set self-election, the Router ID
and Router Priority MUST be consistent among nodes participating and
it is RECOMMENDED that NHDP be used to share this information. The
E-CDS self-election process can be summarized as follows:
1. If an SMF node has a higher ordinal (Router Priority, Router ID)
than all of its symmetric neighbors, it elects itself to act as a
forwarder for all received multicast packets,
2. Else, if there does not exist a path from neighbor "j" with
largest (Router Priority, Router ID) to any 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 provide for redundant relay set election
(e.g., bi-connected) but such capability is supported by the basic
E-CDS design.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 50]
Internet-Draft SMF for MANET February 2008
B.2. E-CDS Forwarding Rules
With E-CDS, any SMF node that has selected itself as a relay performs
DPD and forward all non-duplicative multicast traffic allowed by the
present forwarding policy. Packet previous hop knowledge is not
needed for forwarding decisions when using E-CDS.
1. Upon packet reception, DPD is performed. Note E-CDS require one
duplicate table for the set of interfaces associated with the
relay set selection.
2. If the packet is a duplicate, no further action is taken.
3. If the packet is non-duplicative:
A. A DPD entry is made for the packet identifier
B. The packet is forwarded out all interfaces associated with
the relay set selection
As previously mentioned, even packets sourced (or relayed) by nodes
not participating in NHDP and/or the E-CDS relay set selection may be
forwarded by E-CDS forwarders without problem. A particular
deployment MAY choose to not forward packets from sources or relays
that have been explicitly identified via NHDP or other means as
operating as part of a different relay set algorithm (e.g. S-MPR) to
allow coexistent deployments to operate correctly. Also, E-CDS relay
set selection may be configured to be influenced by statically-
configured CF relays that are identified via NHDP or other means.
B.3. E-CDS Neighborhood Discovery Requirements
It is possible to perform E-CDS relay set selection without
modification of NHDP, basing the self-election process exclusively on
the Router IDs (interface addresses) of participating SMF nodes.
However, it has been shown that use of the "Router Priority" metric
as part of the selection process can result in improved performance
in certain cases. Note that SMF nodes with higher "Router Priority"
values will tend to be favored as relays over other nodes. Thus,
preferred relays MAY be administratively configured to be selected
when possible. Additionally, other metrics (e.g. nodal degree,
energy capacity, etc) for "Router Priority" may be used to produce
desired network performance. In either case it is required that SMF
nodes MUST have been assigned unique "Router ID" values. For
multiple interface operation, it is necessary that a consistent
"Router ID" be advertised in NHDP messages for the originator and its
1-hop symmetric neighbors (_TBD - Does NHDP provide for this? If so,
how? Or do we need to define an SMF_RTR_ID TLV?_).
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 51]
Internet-Draft SMF for MANET February 2008
The SMF_PRIORITY message TLV and SMF_NBR_PRIORITY address block TLV
described in Section 7.2 are RECOMMENDED for use with SMF E-CDS
operation. The SMF_PRIORITY message TLV is used to share a node's
"Router Priority" with its 1-hop neighbors and the SMF_NBR_PRIORITY
address block TLV is used to convey "Router Priority" values among
2-hop neighborhoods. A default technique of using nodal degree (i.e.
count of 1-hop neighbors) is RECOMMENDED for the value field of these
TLV types.
B.4. E-CDS Selection Algorithm
This section describes an algorithm for E-CDS relay selection (self-
election). The algorithm described uses 2-hop information. Note it
is possible to extend this algorithm to use k-hop information with
added computational complexity and mechanisms for sharing k-hop
topology information that are not described in this document or the
NHDP specification. It should also be noted that this algorithm does
not impose the "hop limit" bound described in [E-CDS] when performing
the path search that is used for relay selection. However, the
algorithm below could be easily augmented to accommodate this
additional criteria. In normal operation, it is not expected that
the "hop limit" bound will provide significant benefit.
The tuple of "Router Priority" and "Router ID" is used in E-CDS relay
set selection. Precedence is given to the "Router Priority" portion
and the "Router ID" value is used as a tie-breaker. The evaluation
of this tuple is referred to as "RtrPri(n)" in the description below
where "n" references a specific node. Note it is possible that the
"Router Priority" portion may be optional and the evaluation of
"RtrPri()" be solely based upon the unique "Router ID". Since there
MUST NOT be any duplicate "Router ID" values among SMF nodes, a
comparison of RtrPri(n) between any two nodes will always be an
inequality. The following steps describe a basic algorithm for
conducting E-CDS relay selection for a node "n0":
1. Initialize the set "N1" to include all 1-hop neighbors of "n0".
2. If "N1" has less than 2 members, then "n0" does _not_ select
itself as a relay and no further steps are taken.
3. Initialize the set "N2" to include all 2-hop neighbors, excluding
"n0" and any nodes in "N1".
4. If "RtrPri(n0)" is greater than that of all nodes in the union of
"N1" and "N2", then "n0" selects itself as a relay and no further
steps are taken.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 52]
Internet-Draft SMF for MANET February 2008
5. Initialize all nodes in the union of "N1" and "N2" as
"unvisited".
6. Find the node "n1_Max" that has the largest "RtrPri()" of all
nodes in "N1"
7. Initialize queue "Q" to contain "n1_Max", marking "n1_Max" as
"visited"
8. While node queue "Q" is not empty, remove node "x" from the head
of "Q", and for each 1-hop neighbor "n" of node "x" (excluding
"n0") that is _not_ marked "visited"
A. Mark node "n" as "visited"
B. If "RtrPri(n)" is greater than "RtrPri(n0), append "n" to "Q"
9. If any node in "N1" remains "unvisited", then "n0" selects itself
as a relay. Otherwise "n0" does not act as an relay.
Note these steps are re-evaluated upon neighborhood status changes.
Steps 5 through 8 of this procedure describe an approach to a path
search. The purpose of this path search is to determine if paths
exist from the 1-hop neighbor with maximum "RtrPri()" to all other
1-hop neighbors without traversing an intermediate node with a
""RtrPri()" value less than "RtrPri(n0)". These steps comprise a
breadth-first traversal that evaluates only paths that meet that
criteria. If all 1-hop neighbors of "n0" are "visited" during this
traversal, then the path search has succeeded and node "n0" does not
need to provide relay. It can be assumed that other nodes will
provide relay operation to ensure SMF connectivity.
It is possible to extend this algorithm to consider neighboring SMF
nodes that are known to be statically configured for CF (always
relaying). The modification to the above algorithm is to process
such nodes as having a maximum possible "Router Priority" value. It
is expected that nodes configured for CF and participating in NHDP
would indicate this with use of the SMF_RELAY_ALG and
SMF_NBR_RELAY_ALG TLV types in their NHDP_HELLO message and address
blocks, respectively.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 53]
Internet-Draft SMF for MANET February 2008
Appendix C. Multipoint Relay Connected Dominating Set (MPR-CDS)
Algorithm
The MPR-CDS algorithm is an extension to the basic S-MPR election
algorithm that results in a shared (non source-specific) SMF CDS.
Thus its forwarding rules are not dependent upon previous hop
information similar to E-CDS. An overview of the MPR-CDS selection
algorithm is provided in [MPR-CDS].
It is RECOMMENDED that the SMF_RELAY_ALG message TLV be included in
NHDP_HELLO messages that are generated by nodes conducting MPR-CDS
SMF operation.
C.1. MPR-CDS Relay Set Selection Overview
The MPR-CDS relay set selection process is based upon the MPR
selection process of the S-MPR algorithm with the added refinement of
a distributed technique for subsequently down-selecting to a common
reduced, shared relay set. A node ordering (or "prioritization")
metric is used as part of this down-selection process Like the E-CDS
algorithm, this metric can be based upon node address or some other
unique router identifier ("Router ID") as well as an additional
"Router Priority" measure, if desired. The process for MPR-CDS relay
selection is as follows:
1. First, MPR selection per the S-MPR algorithm is conducted, with
selectors informing their MPRs (via NHDP) of their selection.
2. Then, the following rules are used on a distributed basis by
selected nodes to possibly unselect themselves and thus jointly
establish a common set of shared SMF relays:
A. If a selected node has a larger "RtrPri()" than all of its
1-hop symmetric neighbors, then it acts as a relay for all
multicast traffic, regardless of the previous hop
B. Else, if the 1-hop symmetric neighbor with the largest
"RtrPri()" value has selected the node, then it also acts as
a relay for all multicast traffic, regardless of the previous
hop.
C. Otherwise, it unselects itself as a relay and does not
forward any traffic unless changes occur that require re-
evaluation of the above steps.
This technique shares many of the desirable properties of the E-CDS
technique with regards to compatibility with multicast sources not
participating in NHDP and the opportunity for statically-configure CF
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 54]
Internet-Draft SMF for MANET February 2008
nodes to be present, regardless of their participation in NHDP.
C.2. MPR-CDS Forwarding Rules
The forwarding rules for MPR-CDS are common with those of E-CDS. Any
SMF node that has selected itself as a relay performs DPD and forward
all non-duplicative multicast traffic allowed by the present
forwarding policy. Packet previous hop knowledge is not needed for
forwarding decisions when using MPR-CDS.
1. Upon packet reception, DPD is performed. Note MPR-CDS require
one duplicate table for the set of interfaces associated with the
relay set selection.
2. If the packet is a duplicate, no further action is taken.
3. If the packet is non-duplicative:
A. A DPD entry is made for the packet identifier
B. The packet is forwarded out all interfaces associated with
the relay set selection
As previously mentioned, even packets sourced (or relayed) by nodes
not participating in NHDP and/or the MPR-CDS relay set selection may
be forwarded by E-CDS forwarders without problem. A particular
deployment MAY choose to not forward packets from sources or relays
that have been explicitly identified via NHDP or other means as
operating as part of a different relay set algorithm (e.g. S-MPR) to
allow coexistent deployments to operate correctly. Also, MPR-CDS
relay set selection may be configured to be influenced by statically-
configured CF relays that are identified via NHDP or other means.
C.3. MPR-CDS Neighborhood Discovery Requirements
The neighborhood discovery requirements for MPR-CDS have commonality
with both the S-MPR and E-CDS algorithms. MPR-CDS selection
operation requires 2-hop neighbor knowledge as provided by the NHDP
protocol [NHDP] or from external sources. In the S-MPR phase of MPR-
CDS selection, MPRs are dynamically determined by each node and
selections MUST be advertised and dynamically updated using NHDP or
an equivalent protocol or mechanism. For NHDP use, the TLVs defined
in OLSRv2 [OLSRv2] to support MPR selection and notification are also
required. This includes the "MPR" address block TLV type for
designating selected 1-hop neighbors and the optional "WILLINGNESS"
TLV described in that specification. Unlike S-MPR operation, there
is no need for associating link-layer address information with 1-hop
neighbors since MPR-CDS forwarding is independent of the previous
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 55]
Internet-Draft SMF for MANET February 2008
hop. In common with E-CDS, the SMF_RTR_PRIORITY TLV MAY be used to
advertise an optional "Router Priority" value associated with a node.
However, in MPR-CDS, only the message TLV for "Router Priority" needs
to be used since only 1-hop knowledge of "Router Priority" is
required.
The NHDP or external process must also provide link-layer (MAC)
addresses of 1-hop neighbor nodes and MPR selectors so that S-MPR
forwarding can be conducted properly.
C.4. MPR-CDS Selection Algorithm
This section describes an algorithm for the MPR-CDS selection
process. Note that the selection described is with respect to a
specific interface of the node performing selection and other node
interfaces referenced are reachable from this reference node
interface. An ordered tuple of "Router Priority" and "Router ID" is
used in MPR-CDS relay set selection. Precedence is given to the
"Router Priority" portion and the "Router ID" value is used as a tie-
breaker. The evaluation of this tuple is referred to as "RtrPri(n)"
in the description below where "n" references a specific node. Note
it is possible that the "Router Priority" portion may be optional and
the evaluation of "RtrPri()" be solely based upon the unique "Router
ID". Since there MUST NOT be any duplicate "Router ID" values among
SMF nodes, a comparison of RtrPri(n) between any two nodes will
always be an inequality. Additionally, since this process includes
S-MPR selection as part of its execution, the S-MPR "WILLINGNESS"
value that nodes MAY use is also taken into consideration. Note
that, if a node is configured with a "WILLINGNESS" value of
"WILL_ALWAYS", then that node's "RtrPtr()" should be evaluated
assuming the maximum possible "Router Priority". The following
steps, repeated upon any changes detected within the 1-hop and 2-hop
neighborhood, describe a basic algorithm for conducting MPR-CDS
selection for a node interface "n0":
1. Perform steps 1-8 of Appendix A.4 to select MPRs from the set of
1-hop neighbors of "n0" and notify/update neighbors of
selections.
2. Upon being selected as an MPR (or any change in the set of nodes
selecting "n0" as an MPR):
A. If no neighbors have selected "n0" as an MPR, "n0" does not
act as a relay and no further steps are taken until a change
in neighborhood topology or selection status occurs.
B. Determine the node "n1_max" that has the maximum "RtrPri()"
of all 1-hop neighbors.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 56]
Internet-Draft SMF for MANET February 2008
C. If "RtrPri(n0)" is greater than "RtrPri(n1_max)", then "n0"
selects itself as a relay for all multicast packets,
D. Else, if "n1_max" has selected "n0" as an MPR, then "0"
selects itself as a relay for all multicast packets.
E. Otherwise, "n0" does not act as a relay.
It is possible to extend this algorithm to consider neighboring SMF
nodes that are known to be statically configured for CF (always
relaying). The modification to the above algorithm is to process
such nodes as having a maximum possible "Router Priority" value.
This is the same as the case for participating nodes that have been
configured with a S-MPR "WILLINGNESS" value of "WILL_ALWAYS". It is
expected that nodes configured for CF and participating in NHDP would
indicate their status with use of the SMF_RELAY_ALG TLV type in their
NHDP_HELLO message TLV block.
Macker, editor & SMF Design Team Expires August 28, 2008 [Page 57]
Internet-Draft SMF for MANET February 2008
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 August 28, 2008 [Page 58]
Internet-Draft SMF for MANET February 2008
Full Copyright Statement
Copyright (C) The IETF Trust (2008).
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 August 28, 2008 [Page 59]
