http://stupid.domain.name/ietf/

One document matched: draft-ietf-manet-smf-02.txt

Differences from draft-ietf-manet-smf-01.txt

Network Working Group J. Macker, editor
Internet-Draft NRL
Expires: September 6, 2006 SMF Design Team
IETF MANET WG
March 5, 2006

Simplified Multicast Forwarding for MANET
draft-ietf-manet-smf-02

Status of this Memo

By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.

Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.

Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."

The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.

The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.

This Internet-Draft will expire on September 6, 2006.

Abstract

This document describes the Simplified Multicast Forwarding (SMF)
protocol that provides a basic IP multicast forwarding capability
within mobile ad-hoc networks (MANET). SMF is designed to have
limited applicability as a forwarding mechanism for multicast packets
within MANET routing areas. In addition, it provides mechanisms to
support interoperability with a connected wired infrastructure. SMF
uses a simplified forwarding mechanism that delivers multicast

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 1]

Internet-Draft SMF for MANET March 2006

packets to all MANET multicast receivers within a MANET routing area.
The core design does not use receiver specific group information in
favor of reduced complexity and state maintenance within the mobile
topology. Such extensions may follow in later specifications. The
design accounts for the unique nature and behavior of MANET
interfaces and takes advantage of efficient relay set algorithms
previously designed and applied in the MANET routing control plane.
This document describes the SMF forwarding mechanisms in detail,
specifies an optional SMF neighborhood discovery protocol, and
describes several efficient relay set algorithms that have been
implemented in conjunction with SMF.

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 2]

Internet-Draft SMF for MANET March 2006

Table of Contents

1. Requirements Notation . . . . . . . . . . . . . . . . . . . . 4
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 7
2.2. Applicability . . . . . . . . . . . . . . . . . . . . . . 7
3. SMF Design Considerations . . . . . . . . . . . . . . . . . . 8
3.1. Previous Related Work . . . . . . . . . . . . . . . . . . 9
4. SMF Packet Processing and Forwarding . . . . . . . . . . . . . 10
5. SMF Duplicate Packet Detection . . . . . . . . . . . . . . . . 13
5.1. SMF IPv4 Duplicate Packet Detection . . . . . . . . . . . 14
5.2. SMF IPv6 Duplicate Packet Detection . . . . . . . . . . . 15
5.2.1. IPv6 SMF-DPD Header Option Format . . . . . . . . . . 16
6. Relay Set Selection . . . . . . . . . . . . . . . . . . . . . 17
7. Baseline SMF Neighborhood Discovery Protocol (NDP) . . . . . 18
7.1. SMF NDP Description . . . . . . . . . . . . . . . . . . . 18
7.2. SMF NDP Messaging . . . . . . . . . . . . . . . . . . . . 19
7.2.1. SMF_HELLO Message Header . . . . . . . . . . . . . . . 20
7.2.2. SMF_HELLO Message TLVs . . . . . . . . . . . . . . . . 20
7.2.3. SMF_HELLO Address Block TLVs . . . . . . . . . . . . . 20
8. SMF Multicast Border Gateway Considerations . . . . . . . . . 23
8.1. Forwarded Multicast Groups . . . . . . . . . . . . . . . . 23
8.2. Multicast Group Scoping . . . . . . . . . . . . . . . . . 23
8.3. Duplicate Packet Detection Marking . . . . . . . . . . . . 23
8.4. Interface with Exterior Multicast Routing Protocols . . . 24
8.5. Multiple Gateways . . . . . . . . . . . . . . . . . . . . 24
9. Security Considerations . . . . . . . . . . . . . . . . . . . 25
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26
11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 27
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 28
12.1. Normative References . . . . . . . . . . . . . . . . . . . 28
12.2. Informative References . . . . . . . . . . . . . . . . . . 28
Appendix A. Source-based Multipoint Relay (S-MPR) . . . . . . . . 30
A.1. S-MPR Relay Set Selection . . . . . . . . . . . . . . . . 30
A.2. Neighborhood Discovery Requirements . . . . . . . . . . . 31
Appendix B. Essential Connecting Dominating Set (E-CDS)
Algorithm . . . . . . . . . . . . . . . . . . . . . . 32
B.1. E-CDS Relay Set Selection . . . . . . . . . . . . . . . . 32
B.2. E-CDS Forwarding Rules . . . . . . . . . . . . . . . . . . 32
B.3. Neighborhood Discovery Requirements . . . . . . . . . . . 33
Appendix C. Multipoint Relay Connected Dominating Set
(MPR-CDS) Algorithm . . . . . . . . . . . . . . . . . 34
C.1. MPR-CDS Relay Set Selection . . . . . . . . . . . . . . . 34
C.2. MPR-CDS Forwarding Rules . . . . . . . . . . . . . . . . . 34
C.3. Neighborhood Discovery Requirements . . . . . . . . . . . 34
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 35
Intellectual Property and Copyright Statements . . . . . . . . . . 36

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 3]

Internet-Draft SMF for MANET March 2006

1. Requirements Notation

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119].

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 4]

Internet-Draft SMF for MANET March 2006

2. Introduction

Design and implementation progress has been made in developing and
implementing more efficient ways to flood control packets within
MANET wireless routing protocol designs. For example, algorithms
within MANET RFC 3626 [RFC3626]and RFC 3684 [RFC3684] specify
distributed methods of dynamically electing reduced relay sets for
the purposes of optimizing the flooding routing control packets to
all MANET nodes. In this document, we specify the Simplified
Multicast Forwarding (SMF) framework. The main purpose of SMF is to
adapt efficient flooding designs in MANET environments and apply
these mechanisms to IP multicast packet forwarding. When efficient
flooding is a sufficient technique, SMF can make multicast forwarding
available to data flows within a MANET routing area. The SMF
baseline design limits the scope to basic, best effort multicast
forwarding and its applicability is intended to be constrained within
a MANET routing area. Figure 1 provides an overview of the logical
SMF node architecture, consisting of "Neighborhood Discovery", "Relay
Set Selection" and "Forwarding Process" components. Typically, relay
set selection (or even self-election) will occur based on input from
a neighborhood discovery process, and the forwarding process will be
controlled by status based upon relay set selection. In some cases,
the forwarding decision for a packet may also depend on previous hop
or incoming interface information. The asterisks (*) in Figure 1
mark the primitives and relationships needed by relay set algorithms
requiring previous-hop packet forwarding knowledge.

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 5]

Internet-Draft SMF for MANET March 2006

Fig. 1 - SMF Node Architecture

This document describes a network layer multicast forwarding process
compatible with different neighborhood discovery protocols and relay
set selection algorithms. Different discovery mechanisms or relay
set algorithms may be applicable for different MANET routing
protocols and deployments. In the simplest case, Classical Flooding
(CF) can be supported, eliminating the need for any relay set
algorithm or neighborhood topology information. However, it is
expected that more efficient flooding techniques will be preferred
due to expected gains in network efficiency and reductions in
wireless congestion and contention. Efficient flooding is realized
by selecting a _subset_ of all possible nodes in a MANET area as the
forwarding relay set. Algorithms exist that can make use of local
network neighborhood topology information to determine an appropriate
relay set in a distributed, dynamic fashion. These relay set
selection algorithms can be used to provide a distribution tree for
user multicast data[MDC04]. A few such relay set selection
algorithms are described in Appendices of this document, but it is
possible that additional relay set algorithms or extensions may be
specified in the future for use with SMF.

As noted, neighborhood topology information is usually needed for a
relay set selection algorithm to determine an appropriate set of
forwarding nodes. In many cases, it is expected that neighborhood
topology discovery functions may be provided by a MANET unicast
routing protocol or HELLO protocol implementation running in
concurrence with SMF. Or, in other cases, it is possible that the
lower link layer or multiple access protocols may provide the
necessary neighborhood information through an enhanced interface.

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 6]

Internet-Draft SMF for MANET March 2006

Different distributed relay set algorithms and associated forwarding
decision logic often have differing neighborhood discovery and
signaling demands. This document states specific requirements for
neighborhood discovery with respect to the forwarding process and
relay set selection algorithms described herein and defines an
optional SMF Neighborhood Discovery (ND) protocol that can support
operation independent of any MANET unicast protocol.

Note 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 network layer
semantics. Also, a multicast border gateway mechanism MUST be used
when interoperating with other IP multicast routing in the wired
world (e.g., PIM). In present experiments, proxying methods have
been used to enable some gateway functionality at MANET border
gateways operating with wired multicast routing protocol interfaces.
Although SMF may be extended or combined with other protocols to
provide increased reliability and group specific forwarding state,
the details of those methods will be discussed in other documents.

2.1. Terminology

MANET : Mobile Ad hoc Networks

SMF : Simplified Multicast Forwarding

CF : Classical Flooding

CDS : Connected Dominating Set

MPR : Multi-point Relay

DPD: Duplicate Packet Detection

2.2. Applicability

A basic packet forwarding service that reaches all destinations
participating within a MANET environment can be a useful generic
group communication mechanism for an application layer. While the
design requirements for this are similar to those often needed by the
control plane of many MANET unicast routing protocol layers, it is
desirable to provide a more generic forwarding function for use by
other applications. There are a number of application areas that
could take advantage of a simple ALL_MANET_NODES delivery service
within a MANET routing region (e.g., multimedia streaming, peer-to-
peer middleware multicasting, auto-configuration, and multi-hop
discovery services).

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 7]

Internet-Draft SMF for MANET March 2006

3. SMF Design Considerations

The simplest design often conceived and adapted for MANET packet
flooding is something we designate as the "classical flooding" (CF)
algorithm. In CF, each participating forwarder node is required to
rebroadcast packets intended for dissemination once and only once.
This approach is extremely simple and only requires only some means
of duplicate packet detection (DPD) and a basic forwarding mechanism.
However, it is well known that using CF, especially within dense
networks, results in a significant number of redundant transmissions
often referred to as the broadcast storm problem [NTSC99]. Within
wireless multi-hop network direct contention and interference is
often experienced beyond the single hop interface and reducing
unnecessary channel contention within a MANET can also significantly
improve network performance. Therefore, minimizing the number of
required relay nodes is a heightened design goal in this environment.
Unfortunately, reducing the number of relay nodes in a MANET
environment may also decrease the robustness of packet delivery in a
mobile topology. There exists a design tradeoff between relay
efficiency and delivery robustness that is scenario and system
dependent and should be considered carefully. If needed, additional
reliability mechanisms MAY be considered for use with reduced relay
sets (e.g., backup and redundant relay set) but the use of limited
hop-by-hop retransmission schemes at the network layer are considered
out of scope for this document. If needed by an application, the use
of IETF reliable multicast transport layer protocols (e.g., RMT)
should be transparently supported by SMF's best effort delivery
mechanism. The basic design goal of SMF is support both a simple CF-
based forwarding capability and to supplement this with reduced relay
set algorithms for increased efficiency.

At a theoretic level, work in the area of minimizing packet
forwarders, or relay node sets, is often related to basic graph
theory problems. In graph theory, a dominating set (DS) for a graph
is a set of vertices that, along with their neighbors, constitute all
the vertices in the graph. A connected DS (CDS) is a DS where the
subgraph induced is connected. A minimum CDS (MCDS) is a set such
that the number of vertices is the minimum required to form a CDS.
Finding a small dominating set is one of the most fundamental
problems of traditional graph theory and is often related to the
problem of optimizing flooding algorithms in MANET routing protocols.
Finding an MCDS in a given graph is known to be NP-hard [GJ79].
These basic static graph theoretic issues are important to apply in
developing efficient relay sets, but in addition MANET relay set
designs require distributed and dynamic operation. To better explain
the design requirement, we formulated the following characteristics
desired of an effective MANET flooding algorithm solution for use in
SMF:

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 8]

Internet-Draft SMF for MANET March 2006

1. A resultant cover set that is small compared to the total number
of nodes as the network scales in size and density.

2. A robust approach somewhat resilient to network mobility and link
dynamics.

3. A cover set election/maintenance mechanism that is lightweight,
distributed, and adaptive in nature.

3.1. Previous Related Work

Previous novel work on MANET flooding and reduced relay set
mechanisms has been done and this document borrows from and builds
off previous work accomplished. In [WC02], a taxonomy of flooding
algorithms for use in MANET environments was presented and the work
examined performance issues related to various approaches. Other
important work has developed distributed mechanisms that select and
maintain reduced relay node sets. As we have already mentioned, the
design tradeoffs are further complicated by wireless contention,
topological classes, and the robustness of packet delivery and set
election under mobility scenarios. In addition, the actual protocol
implementation for IP multicast forwarding based upon these flooding
algorithms raises additional design tradeoffs and issues. This
includes:

1. protocol state maintenance

2. duplicate packet detection mechanisms

3. packet processing requirements and overhead

4. expected traffic distribution patterns

5. protocol signaling requirements

6. delivery robustness requirements

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 9]

Internet-Draft SMF for MANET March 2006

4. SMF Packet Processing and Forwarding

The SMF Packet Processing and Forwarding actions are conducted with
the following packet handling activities:

1. Interception of outbound, locally-generated multicast packets.

2. Reception of inbound packets on a specific network interface(s).

In the case that sequence-based DPD as described in Section 5 is
used, the purpose of intercepting outbound, locally-generated
multicast packets is to apply resequencing of the IPv4 ID header
field or add options headers as needed (e.g. IPv6). In the case
that resequencing is deemed necessary, it is RECOMMENDED that
sequence numbering be applied such that a different sequence number
space per <sourceAddress::destinationAddress> duple be used. For
initial SMF purposes where no distinct routing path decisions for
different IP Multicast address destinations occur, it might appear to
be sufficient to use sequence number spaces aggregated across all IP
Multicast destinations (or across all IP destinations for a source as
is the default implementation of the IPv4 ID field in many operating
systems). Future SMF extensions, beyond the present discussion, may
contain dynamic forwarding state dependent on the multicast
destination address. The future possibility that different
destinations may be routed differently suggests "per source/
destination" numbering be used. It should be noted that the default
global IPv4 ID sequence space may be sufficient for some SMF
deployments and interception of outbound packets may not be required
if end systems have numbered the IPv4 ID field in an acceptable
manner. In other cases, such as when IPSec headers have been applied
to packets, other sequence information (perhaps even "per flow") may
be available for the SMF process to make use of in its duplicate
table management.

Inbound multicast packets will be received by the SMF implementation
and processed for possible forwarding. Well-known multicast groups
for flooding to all nodes of an ad hoc network are specified for use
with the network-layer flooding provided by SMF. These multicast
groups are specified to contain all nodes of a contiguous ad hoc
network, so that packets transmitted to the multicast address
associated with the group will be delivered to all nodes as desired.
In other words, any node that is reachable, is automatically granted
membership in these multicast groups. For IPv6, the multicast
address is specified to be "site-local". The names of the multicast
groups are given as "ALL_IPv4_MANET_NODES" (TBD) and
"ALL_IPv6_MANET_NODES" (TBD). This document does not support
transmissions to any directed broadcast address ranges. Minimally
SMF SHALL forward unique (non-duplicate) packets received for these

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 10]

Internet-Draft SMF for MANET March 2006

well-known group addresses when the TTL or hop count value in the IP
header is greater than 1. Optionally, SMF deployments may choose to
forward packets for additional "global scope" multicast groups to
support application needs or to distribute multicast packets that
have ingressed the MANET area via border gateways. Additional
addresses will be specified by an a priori list or possible through a
dynamic address management interface. In all cases, the following
rules SHALL be observed for SMF multicast forwarding:

1. Multicast packets with TTL <= 1 MUST NOT be forwarded*.

2. Link Local multicast packets MUST NOT be forwarded

3. Incoming multicast packets with an IP source address matching one
of those of the local host interface(s) MUST NOT be forwarded.

4. Received packet frames with the MAC source address matching the
local host interface(s) MUST NOT be forwarded.

Note that rule #3 is important because in wireless networks, the
local host may receive re-transmissions of its own packets when they
are forwarded by neighboring nodes. This rule avoids unnecessary
retransmission of locally-generated packets even when other
forwarding decision rules would apply.

Once these criteria have been met, the implementation should
reference a forwarding decision algorithm, possibly in concert with
duplicate packet detection, to determine the next step in packet
processing. The forwarding decision may be implicit if the SMF
implementation is configured to perform classical flooding (CF) of IP
multicast packets. Otherwise, the forwarding decision may be
controlled by another process. Neighborhood discovery protocols
coupled with the source-based multi-point relay (S-MPR) or other CDS
selection algorithms described below MAY be used to determine the
local host's status with respect to forwarding. For example, some
algorithms may control forwarding based on a previous hop indentifier
(e.g. S-MPR forwarding), while others may designate the local host
as a forwarder of all packets (or at least those generated by known
neighbors) based on the neighborhood broadcast topology (e.g.
Essential CDS (E-CDS)).

DPD is the perhaps the most complex portion of the SMF forwarding
process. In general, detection of received duplicate packets is
necessary to avoid forwarding the same packet multiple times.
However, in some cases (e.g., S-MPR), duplicate detection of some
non-forwarded packets is also needed to maintain efficient
forwarding. Details on different duplicate packet detection and
forwarding rules for the S-MPR, and E-CDS algorithms are given in

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 11]

Internet-Draft SMF for MANET March 2006

Appendices of his document. The details for these classes of
algorithms may also apply to other similar algorithms.

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 12]

Internet-Draft SMF for MANET March 2006

5. SMF Duplicate Packet Detection

One important design difference between routing for MANET interfaces
and many wired network interfaces is that forwarding out the same
physical interface a packet arrived upon is a normal operation. This
operation is often disallowed or discouraged in wired multicast
routing designs to avoid possible looping. Similarly, any Reverse
Path Forwarding (RPF) logic also used needs to be softened when
operating over a single MANET interface. This MANET interface
characteristic leads to DPD as a common requirement in MANET packet
flooding. While this requires increased per packet processing, it is
necessary in MANET-specific multicasting because packets must be
potentially be forwarded out the same physical interface they may
arrive on and nodes can even receive copies of previously-transmitted
packets from other forwarding neighbors. This section describes a
basic SMF DPD mechanism and some alternative operational options as
considerations.

SMF SHOULD implement explicit detection of duplicate multicast
packets by a temporal packet identification scheme. This is
typically implemented by keeping a history of previous received and
forwarded packet identifiers for comparison against recently
forwarded multicast packets. There are different possible approaches
to packet identification that have been considered. Possibilities
include unique markings within packet header fields, such as packet
sequence numbering, or application of hash algorithms or similar
techniques to compactly and uniquely describe the history of recently
received packets. This document RECOMMENDS simple, sequence-based
schemes that can be accomplished without additional (non-IP)
encapsulation of packets and/or their content. Encapsulation
approaches are considered out-of-scope so that non-forwarding edge
nodes within a MANET area may easily receive flooded content without
any additional software beyond that of a typical IP stack. Packet
hashing approaches for DPD may be applicable in some cases, yet early
examination of these approaches indicated the computation complexity
may be prohibitive for per-packet processing on many candidate MANET
platforms (e.g., PDAs). Additionally, the unavoidable "cache-miss"
rates, while possibly low for some algorithms, result in the severe
penalty of false DPD (and thus packet loss) rather than the more
benign penalty of additional computation cycles as associated with
most applications of hashing.

Implementations will need to age and/or timeout duplicate packet
state as new packets are received and forwarded. In the case that
sequence-based packet identification is used, implementations SHOULD
timeout stale histories for <sourceAddress::destinationAddress>
entries where new, non-duplicate packets have not been recently
received. The proper duration of any timeout delay is a function of

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 13]

Internet-Draft SMF for MANET March 2006

expected possible network traversal time, roughly NET_DIAMETER (in
hops) times NODE_TRAVERSAL_TIME. NET_DIAMETER measures the maximum
possible number of hops given any two nodes in the network.
NODE_TRAVERSAL_TIME is a conservative estimate of the average one hop
traversal time for packets and should include queueing delays,
interrupt processing times, medium access delays, and propagation
delays. If the timeout is reset only upon reception of non-duplicate
packets, it also limits the time that packets might be incorrectly
dropped if a source node is stopped and restarted in the case of
sequence-based packet identification. The required size of the
duplication detection cache is similarly governed and is also a
function of the maximum expected packet rate.

Of course, the duplicate packet detection mechanism SHOULD avoid
keeping unnecessary state for packet flows such as those that are
locally generated or link local destinations that would not be
considered for forwarding.

5.1. SMF IPv4 Duplicate Packet Detection

IPv4 multicast packets from a particular source are assumed to be
marked with a temporally unique identification number in the ID field
of the IPv4 packet header that can serve as a "packetIdentifier" for
SMF purposes. Unfortunately, in present operating system networking
kernels, this IP header field value is not always generated or
applied in a consistent manner with respect to SMF needs. In order
to build a working implementation without encapsulating packets, an
SMF implementation SHOULD provide a sequence generation and marking
module that can maintain and set a monotonically increasing IP ID
field for locally-generated multicast packets with independent
sequence number spaces applied on a <sourceAddress::
destinationAddress> basis. When needed this process will also
recalculate and replace a proper IP header checksum for the
formulated header. For gateways injecting external IPv4 traffic into
an SMF MANET area, the gateways SHOULD perform this same IP ID field
re-sequencing. Note the presence of IPSec may prevent such
resequencing, but does provide its own organic means for duplicate
packet detection.

The use of IPSec for candidate packet flows presents the opportunity
to make use of the additional, perhaps more reliable, sequencing
information of the IPSec header for unique packet identification.
The IPSec header provides a packet identifier field that can be used
on a "per-security assocation" basis. The IP addressing and IPSec
Security Parameters Index (SPI) fields are used to identify security
associations and, hence, packet flows. So, if the packet is IPSec
encapsulated, SMF will check the <sourceAddress::destinationAddress::
SPI::packetIdentifier> where the <ESP_seq_number> or <AH_seq_number>

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 14]

Internet-Draft SMF for MANET March 2006

from the IPSec header serves as the "packetIdentifier" value.

Although it would be possible to support IP layer fragmentation , SMF
traffic sources or gateways SHOULD set the don't fragment bit for
traffic intended to be carried by SMF. This is recommended to avoid
the additional complexity and inefficiencies arising from supporting
IP layer fragmentation.

To perform duplicate detection, SMF will check the <sourceAddress::
destinationAddress::packetIdentifier> combination against a cache
history of received packet identifiers. Some forwarding algorithms
may require that unique packets are only noted when received from
certain neighbor nodes. Multiple interface semantics may also add
some additional considerations to the forwarding process depending
upon the specific relay set selection forwarding rules.

Although its use is demonstrated in working prototype code, the
adoption of the IPv4 ID field for widespread packet duplication
detection has some disadvantages that should be discussed. The main
disadvantage is that, as mentioned, the use and interpretation of the
field is known to be non-consistent across operating systems. The ID
field is also limited and may provide less robust detection for high
bandwidth applications since sequence wrap-around may occur
relatively frequently if it is not possible to achieve "per source/
destination" sequencing. As an alternative, the use of a header
option or encapsulation header in future implementations may provide
more flexibility and consistency (see IPv6 DPD). Another advantage
of using a header option (or other encapsulation, if determined
absolutely necessary) is that it would be possible for MANET gateway
nodes to assess whether packets ingressing a MANET area have already
been properly sequenced to avoid unnecessary re-injection of packets.
We leave these design alternatives to be further defined and
discussed in future work or later revisions of this ID. A basic
sequencing and marking design similar to the one we formulate here
can be easily adapted to work with future approaches or can be
bypassed when not needed.

5.2. SMF IPv6 Duplicate Packet Detection

The following section describes the mechanism and options for SMF
IPv6 DPD. The core IPv6 header does not provide an explicit
identification header field that we can exploit for DPD. SMF defines
two methods for IPv6 use: a hop-by-hop DPD options header and the use
of IPSec sequencing when an IPSec header is detected. SMF MUST
provide a DPD marking module that can insert the hop-by-hop IPv6
header option defined for locally generated MANET multicast. If the
packet is _not_ IPSec encapsulated, SMF will use the IPv6 packet
header and IPv6 DPD option to form <sourceAddress::

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 15]

Internet-Draft SMF for MANET March 2006

destinationAddress::packetIdentifier> that is checked against a cache
history of received IPv6 packet identifiers. Similarly to the case
for IPv4, the presence of IPSec may prevent the intermediate addition
of a hop-by-hop options header. Fortunately, the IPSec header
provides a packet identifier field that can be used on a "per-
security assocation" basis. The IP addressing fields and IPSec
Security Parameters Index (SPI) fields are used to identify security
associations and, hence, packet flows. So, if the packet is IPSec
encapsulated, SMF will check the <sourceAddress::destinationAddress::
SPI::packetIdentifier> where the <ESP_seq_number> or <AH_seq_number>
from the IPv6 IPSec header serves as a "packetIdentifier" value.

5.2.1. IPv6 SMF-DPD Header Option Format

Figure 2 illustrates the format of the IPv6 SMF Duplication Packet
Detection (SMF-DPD) hop-by-hop header option. (Discussion: Is there
any value in specifying this as a "destination" option instead?). If
this is the only hop-by-hop option present, this will result in the
addition of 8 bytes to the IPv6 packet header including the "Next
Header", "Header Extension Length", SMF-DPD option fields, and
padding.

0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
... | Option Type | Opt. Data Len |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| DPD packet identifier | ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Fig. 2 - IPv6 SMF-DPD Hop-by-hop Header Option
Option Type = (TBD)

Opt. Data Len = 2

DPD packet identifier = monotonically increasing 16-bit sequence
number assigned on a per <sourceAddress::destinationAddress> basis.

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 16]

Internet-Draft SMF for MANET March 2006

6. Relay Set Selection

As mentioned SMF MUST support CF-based forwarding as a basic
forwarding mechanism when optimized relay set information is not
available or not selected. In CF mode, each node transmits a locally
generated or newly received packet exactly once. The DPD technique
mentioned in the previous section is critical to proper operation and
avoids any duplicate packet retransmissions.

In the requirements sections, it was stated that SMF MUST support the
ability to modify forwarding rules based upon relay set information
that is received dynamically during operation. In this way, SMF can
operate more efficiently within the MANET multicast area. In the
section we define the interface and processing semantics to allow SMF
to support a variety of different relay set algorithms and
approaches.

Some recommended criteria for relay set selection algorithm
candidates:

1. Robust with respect to mobility or other network dynamics

2. Require minimal signaling for neighbor discovery and/or control

3. Allow nodes to express preference for/against selection as relay

Some relay set algorithms that meet this criteria are described in
the Appendices of this document. Different algorithms may be more
suitable for different MANET routing types or deployments.
Additional relay set selection algorithms may be specified in
separate documents in the future. The Appendices in this document
can serve as a template for the content of such potential future
specifications.

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 17]

Internet-Draft SMF for MANET March 2006

7. Baseline SMF Neighborhood Discovery Protocol (NDP)

In absence of a compatible, coexisting unicast routing protocol or
MAC layer protocol that provides neighborhood toplogy information
sufficient for relay set selection, this section defines a basline
SMF neighborhood discovery protocol (NDP) that MAY be run between SMF
nodes.

With respect to neighborhood topology knowledge and/or discovery,
there are three basic modes of SMF operation:

1. Classical Flooding (CF) mode with no requirement for discovery or
knowledge of neighborhood topology,

2. External control mode where an external process dynamically sets
the local SMF relay status (e.g., Early SMF prototypes have
leveraged neighborhood toplogy information collected by MANET
unicast routing protocols such as OLSRv2 or Manet-OSPF ), and

3. Independent operating mode using a neighborhood discovery
("hello") protocol to collect the local topology information
required for the various CDS algorithm modes discussed in the
Appendices.

We have previously discussed modes 1 and 2. This section will
specify a baseline, stand-alone NDP that can be used to operate SMF
independent of any MANET unicast routing protocol and still provide
optimized relay set functionality. The intention of this protocol
design is to be consistent with the Generalized MANET Packet/Message
Format work [PacketBB] in progress within the MANET WG and the SMF
protocol design is closely related to and borrows from the HELLO
protocol being specified by OLSRv2 [OLSRv2] but separates out
specific CDS algorithm support.

7.1. SMF NDP Description

SMF NDP messages are exchanged between local interface neighbor nodes
and SMF NDP messages are transmitted to a well-known link-local
multicast address, ALL_SMF_NEIGHBORS (TBD), on a well-known UDP port
number , SMF_NDP_PORT (TBD). The SMF NDP protocol provides the
following functions:

1. 1-hop neighbor link sensing: maintaining neighbor lists and
performing a basic bidirectionality check of neighbor links

2. 2-hop Neighborhood Discovery: collecting 2-hop symmetric
neighborhood information and any information relevant to relay
set election

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 18]

Internet-Draft SMF for MANET March 2006

3. Relay Set Signaling: signal relay set selection to neighbor nodes
if the relay set algorithm requires such information

SMF NDP messages are exchanged between link local neighbor nodes only
and are not forwarded.

7.2. SMF NDP Messaging

SMF-NDP nodes periodically generate a single message type, SMF_HELLO,
conforming to the Generalized MANET Packet/Message Format work
[PacketBB] in progress within the MANET WG. This generalized packet/
message format provides a standard message header convention and a
standard format for messages containing sets of type-length-value
(TLV) content and blocks of network addresses with associated TLV
content. This supports the needs of SMF-NDP and typical MANET
routing protocol messaging.

_(TBD - Differential NDP messages may be defined in future revisions
on this specification)_

SMF NDP messages are generated and transmitted per interface, i.e.
different SMF NDP messages are generated and transmitted per SMF
interface of a node. SMF NDP messages are generated and transmitted
periodically, with a default interval between two SMF NDP messages of
SMF_HELLO_INTERVAL. The transmission of SMF_HELLO messages are also
randomly jittered by a value establish by SMF_JITTER to decrease the
likelihood of increased contention caused by synchronized SMF_HELLO
intervals within a wireless network. The default value for
SMF_JITTER is 0.5, specified by valued between 0 and 1, and
represents a percentage of SMF_HELLO_INTERVAL around which to jitter
transmissions.

The SMF_HELLO message contains a header, a set of message TLVs
describing general properties of originating node (e.g., CDS
algorithm id, SMF_HELLO transmission interval, relay "willingness",
etc), and an address block of detected one-hop neighbors with an
associated TLV block indicating the status and other attributes of
connectivity to those neighbors. Thus, by exchanging these messages
with neighbors (via broadcast), SMF nodes gain knowledge of two-hop
neighborhood connectivity. This information can be used to execute
the different relay set selection algorithms described in the
Appendices of this document. It is also possible that the SMF_HELLO
message could be extended with additional address blocks and TLV sets
as needed to support other relay set selection algorithms outside of
the scope of this document.

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 19]

Internet-Draft SMF for MANET March 2006

7.2.1. SMF_HELLO Message Header

The SMF_HELLO message has a <message-header::type> value of SMF_HELLO
(TBD). The <msg-semantics> field SHALL have <bit 1> set to indicate
a reduced <message-header-info> with _no_ <msg-ttl> or <hop-count>
elements since the SMF_HELLO message is implicitly a one-hop message.
Thus, the <msg-header-info> content shall consist of only the
<originator-address> and<msg-seq-number> elements. The <originator-
address> SHALL correspond to the interface address on which the
SMF_HELLO message was transmitted and the <msg-seq-number> will be
incremented monotonically and receivers will use this field to track
SMF_HELLO message loss.

7.2.2. SMF_HELLO Message TLVs

*Relay Set Algorithm Identifier*: type=SMF_RELAY_ALGORITHM, length 1, values = {CF, S-MPR, E-CDS, MPR-CDS}

*Hello Transmission Interval*: type=SMF_HELLO_INTERVAL, length = 1,
value = time*

Note: The four highest bits of the 8-bit TLV value represent the
mantissa (a) and the four lowest bits represent the exponent (b),
yielding a time value equal to: time = (1+a/16)*2^b seconds. Thus,
values in the range from 62.5 msec to 32,768 seconds can be
represented.

*Relay "Willingness"*: type=SMF_RELAY_WILLING, length =1, value "willingness"

Note: If this message TLV is omitted, a default willingess value is
assumed. Also note that this particular TLV may be also be carried
in the address block portion(s) of the message to convey
"willingness" values learned from neighboring nodes.

7.2.3. SMF_HELLO Address Block TLVs

The first <address-block> of a SMF_HELLO message is comprised of a
list of the message originator's neighbors. The associated set of
TLVs for the <address-block> describe the status and other attributes
for the given list of neighbors. In general, the TLVs will be
"multivalue" TLVs that index the subset range of addresses to which
they apply. In some cases, a given TLV type may be provided for each
address in the block, while in other cases, some TLVs may apply only
to a subset of addresses. Where possible, it is RECOMMENDED that
implementations group address subsets within the <address-block>
accordingly to preserve message compactness and minimize message
processing demands.

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 20]

Internet-Draft SMF for MANET March 2006

There are two TLV types that can be applied to convey the status of
neighbors to the originating node. At least one of these One of
these "Link Status" is applied for neighbor nodes detected via the
same interface on which the SMF_HELLO message is transmitted, while
the other "Other Neighbor Status" conveys the status of neighbors on
other interfaces. For initial applications of SMF, it is expected
that the "Link Neighbor Status" TLV will be most applicable and the
"Other Neighbor Status" TLV will allow support when forwarding across
an SMF domain comprised of multiple interfaces is required.

*Link Neighbor Status*: type=SMF_LINK_STATUS, length=1, values {HEARD, SYMMETRIC, LOST}

*Other Neighbor Status*: type = SMF_OTHER_STATUS, length=1, value {SYMMETRIC, LOST}

The following table summarizes the use of these neighbor TLVs for
different cases:

_(TBD - We plan to define an optional "link quality" <address-block>
TLV (or a pair to convey quality))_

Other <address-block> TLV types are required to support the relay set
selection algorithms described in the Appendices of this document.
For example, the S-MPR and MPR-CDS algorithms require a TLV type to
indicate which address (if any) have been selected as MPRs for the
originating node. And the E-CDS algorithm requires a "Router
Priority" value for each symmetric neighbor in the address list to
enable its relay set selection mechanism. Those TLVs are described

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 21]

Internet-Draft SMF for MANET March 2006

in the corresponding appendices where applicable.

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 22]

Internet-Draft SMF for MANET March 2006

8. SMF Multicast Border Gateway Considerations

Typically, it is expected that SMF will be used to distribute
multicast traffic within a MANET area. However, it is also
envisioned to allow interconnection of SMF operation with networks
using other multicast routing protocols if appropriate conditions are
met. Some primary considerations for further defintion (TBD)
include:

1. Determining which multicast groups should transit the gateway
whether entering or exiting the attached MANET area(s).

2. TTL threshold or other scoping policies.

3. Any marking or labeling to enable DPD on ingressing packets.

4. Interface with exterior multicast routing protocols.

5. Possible operation with multiple gateways.

The behavior of gateway nodes is the same as that of non-gateway
nodes when forwarding packets to interfaces within the MANET area.
Packets that are passed to interfaces operating typical multicast
routing protocols SHOULD be evaluated for duplicate packet status
since standard multicast forwarding for wired interfaces do not
usually perform this function.

8.1. Forwarded Multicast Groups

Determining which groups should be forwarded to or from a MANET SMF
area presents challenges. 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
function so that MANET SMF nodes can inform attached gateways (and
hence multicast networks) of their current group membership status.

8.2. Multicast Group Scoping

(TBD)

8.3. Duplicate Packet Detection Marking

Packets sourced external to an SMF area may not have duplicate packet
sequencing properly applied and the gateway may need to provide that
sequencing information upon entry to the network. In the case of
IPv6, the gateway can apply the SMF DPD Hop-by-Hop options header to
packets forwarded into the MANET area for those packets that do not

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 23]

Internet-Draft SMF for MANET March 2006

already have the option applied. This header option provides the
side benefit that the gateway can explicitly determine if the packet
has already been marked and can use the packet identification field
to determine that it is not re-injecting a duplicate packet. For
IPv4, it is RECOMMENDED that gateway nodes re-sequence the ID field
of packets injected into the area. However, the IPv4 ID field does
not provide the gateway with explicit information on whether the
field has been previously set for SMF purposes. Thus, the potential
exists that duplicate IPv4 packets may be re-injected by a gateway
into an SMF area. Further discussion and experimentation is
recommended in this area.

_(If multiple gateways are injecting packets, how do we make sure
that dups are sequenced the same way? )_

8.4. Interface with Exterior Multicast Routing Protocols

(TBD)

8.5. Multiple Gateways

(TBD)

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 24]

Internet-Draft SMF for MANET March 2006

9. Security Considerations

Gratuitous use of option headers can cause problems in routers.
Routers outside of MANET routing areas should ignore SMF header
options if encountered.

Authentication mechanisms to identify the source of an option header
should be considered to reduce vulnerability to a variety of attacks.

Additional security consideration TBD.

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 25]

Internet-Draft SMF for MANET March 2006

10. IANA Considerations

There are number of discussions within this SMF specification that
will be subject to IANA registration. The IP Header Extensions being
defined within this document MUST have an IANA registry established
for them upon publication of the first RFC. Additionally, the well-
known multicast addresses intended for default use by the SMF
forwarding process should be registered and defined by the first RFC
published. These IANA considerations may in common or may be handed
in comjunction with other MANET protocol efforts including the
General Message Format specification and potentially common
neighborhood discovery protocol considerations.

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 26]

Internet-Draft SMF for MANET March 2006

11. Acknowledgments

Many of the concepts and mechanisms used and adopted by SMF resulted
from many years of discussion of related work within the MANET WG.
There are obviously many people that have contributed to past
discussions and related draft documents within the WG that have
influenced the development of SMF concepts that deserve
acknowledgment. In particular, the document is largely a direct
product of the SMF design team within the IETF MANET WG and borrows
text and implementation ideas from these individuals.

SMF Design Team Contributors

Thomas Clausen

Charles Perkins

Brian Adamson

Justin Dean

Brian Haberman

Ian Chakeres

Maoyu Wang

Et al

The RFC text was produced using Marshall Rose's xml2rfc tool.

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 27]

Internet-Draft SMF for MANET March 2006

12. References

12.1. Normative References

[E-CDS] Ogier, R., "MANET Extension of OSPF Using CDS Flooding",
Proceedings of the 62nd IETF , March 2005.

[MPR-CDS] Adjih, C., Jacquet, P., and L. Viennot, "Computing
Connected Dominating Sets with Multipoint Relays", Ad Hoc
and Sensor Wireless Networks , January 2005.

[OLSRv2] Clausen, T. and et al, "Optimized Link State Routing
Protocol version 2", draft-ietf-manet-olsrv2-00, Work in
progress , March 2006.

[PacketBB]
Clausen, T. and et al, "Generalized MANET Packet/Message
Format", draft-ietf-manet-packetbb-00, Work in progress ,
March 2006.

[RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791,
September 1981.

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.

[RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing
Protocol", 2003.

12.2. Informative References

[GJ79] Garey, M. and D. Johnson, "Computers and Intractability: A
Guide to the Theory of NP-Completeness.", Freeman and
Company , 1979.

[JLMV02] Jacquet, P., Laouiti, V., Minet, P., and L. Viennot,
"Performance of multipoint relaying in ad hoc mobile
routing protocols", Networking , 2002.

[MDC04] Macker, J., Dean, J., and W. Chao, "Simplified Multicast
Forwarding in Mobile Ad hoc Networks", IEEE MILCOM 2004
Proceedings , 2004.

[NTSC99] Ni, S., Tseng, Y., Chen, Y., and J. Sheu, "The Broadcast
Storm Problem in Mobile Ad hoc Networks", Proceedings Of
ACM Mobicom 99 , 1999.

[RFC2901] Macker, JP. and MS. Corson, "Mobile Ad hoc Networking

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 28]

Internet-Draft SMF for MANET March 2006

(MANET): Routing Protocol Performance Issues and
Evaluation Considerations", 1999.

[RFC3684] Ogier, R., Templin, F., and M. Lewis, "Topology
Dissemination Based on Reverse-Path Forwarding", 2003.

[WC02] Williams, B. and T. Camp, "Comparison of Broadcasting
Techniques for Mobile Ad hoc Networks", Proceedings of ACM
Mobihoc 2002 , 2002.

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 29]

Internet-Draft SMF for MANET March 2006

Appendix A. Source-based Multipoint Relay (S-MPR)

The source-based multipoint relay (S-MPR) set selection algorithm
enables individual nodes, using two-hop topology information to
select a minimum set of neighboring nodes that can provide relay to
all nodes within a two-hop radius. This distributed technique has
been shown to approximate selection of a MCDS in [JLMV02].
Individual nodes must collect two-hop neighborhood information from
neighbors, determine an appropriate current relay set, and then
inform the resultant selected neighbors of their relay status. The
Optimized Link State Routing (OLSR) protocol has used this algorithm
and protocol for relay of link state updates and other control
information[RFC3626] and has been shown to operate well even in
dynamic network environments.

Because a node's status as a relay is with respect to neighboring
nodes who have selected it (i.e., its "selectors"), the relaying node
must know the previous-hop transmitter of packets it receives in
order to make an appropriate forwarding decision. Additionally, it
is important that relay nodes forward packets only for those nodes
currently identified as symmetric, one-hop neighbors to maintain
correctness. Also, because the selection of relays does not result
in a common set among neighboring nodes, relays MUST mark in their
duplicate table any transmissions from non-selector, symmetric, one-
hop neighbors (for a given interface) and not forward subsequent
received copies of that packet even if received from a selector
neighbor. Deviation here may result in unecessary, even excessive,
repeat transmission of packets throughout the network. Or incorrect
duplicate table recording of packets received from non-symmetric
neighbors may result in incomplete flooding. In these respects,
flooding based on the S-MPR algorithm is more complex than that based
upon some other relay set selection algorithms.

When multiple interfaces are present, the S-MPR SMF forwarded must
keep some independent state for each interface with regards to
duplicate packets. For example, when a packet is received from a
non-selector, one-hop symmetric neighbor, an SMF forwarder using the
S-MPR algorithm must update its duplicate packet state with respect
to the interface on which the packet was received. If the SMF
forwarder receives that same packet from a selector neighbor on a
different interface, it MUST still forward that packet on all
interfaces it has not received that packet from a one-hop symmetric
neighbor. Once a packet has been forwarded in this fashion,
subsequent duplicates received on any interface are ignored.

A.1. S-MPR Relay Set Selection

If SMF is operating S-MPR relay set election independent of

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 30]

Internet-Draft SMF for MANET March 2006

coexistent OLSR operation, based upon SMF ND mechanisms, the election
algorithm defined within RFC3626 [RFC3626] should be used.

A.2. Neighborhood Discovery Requirements

S-MPR election operation requires 2-hop neighbor knowledge as
provided by the SMF NDP process or as available from external
sources. MPRs are dynamically selected by each node and selections
MUST be advertised and dynamically updated within the SMF NDP or
equivalent protocol. For SMF NDP, the following <address-block> TLV
is specified to indicate MPR selection status.

*MPR Designation*: type=SMF_MPR_SELECT, length=0, value = [no value]

Note this is a "no value" TLV, and the presence of this TLV implies
that the corresponding address(es) have been selected by the
SMF_HELLO message originator as MPR(s).

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 31]

Internet-Draft SMF for MANET March 2006

Appendix B. Essential Connecting Dominating Set (E-CDS) Algorithm

The "Essential connecting dominating set" (E-CDS) algorithm [E-CDS]
allows nodes to use two-hop topology information to appropriately
elect _themselves_ as relay nodes to form an efficient (for flooding)
CDS. While this algorithm does not tend to produce as small a set of
relay nodes (per forwarded packet) as the previously-described S-MPR
algorithm, it is not dependent upon previous-hop information to make
a forwarding decision; it simply forwards any received non-duplicate
packets. This property also allows relay nodes using the E-CDS
algorithm to be intermixed with nodes performing only classical
flooding. Additionally, the semantics for multiple interface support
are simplified as compared to S-MPR and even packets that are
received from non-symmetric neighbors may be forwarded without
compromising flooding efficiency or correctness.

B.1. E-CDS Relay Set Selection

This section provides a short description of the E-CDS based relay
set selection algorithm and is based upon Richard Ogier's original
summary within [E-CDS]. This was originally discussed in the context
of forming partial adjacencies and efficient flooding for MANET-OSPF
work but its core algorithm is applied here.

E-CDS requires two-hop neighbor information collected through the
SMF-NDP or other process. Each router has a Router Identifier (may
be represented by an interface address) and Router Priority value.
The Router Priority value may be dynamic and represent such metrics
as node degree. The fundamental election steps are as follows:

1. If an SMF node has a higher (Router Priority, Router ID) than all
of its symmetric neighbors, it elects itself to the relay set.

2. Else, if there does not exist a path from neighbor j with largest
(Router Priority, Router ID) to some other neighbor, via
neighbors with larger values of (Router Priority, Router ID),
then it elects itself to the relay set.

The basic form of E-CDS described and applied within this
specification does not at present define redundant relay set election
but such capability is supported by the E-CDS design.

B.2. E-CDS Forwarding Rules

E-CDS forwarding are quite simple and straightforward. As mentioned,
there is no need to check previous hop information during forwarding.
Upon electing itself as an E-CDS relay set forwarder, SMF nodes
perform DPD functions and forward all ranges of multicast traffic

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 32]

Internet-Draft SMF for MANET March 2006

allowed.

B.3. Neighborhood Discovery Requirements

To support functions required by the core E_CDS relay set algorithm
the following TLV is required to be transmitted by each node within a
SMF_HELLO message:

*Router Priority*: type=SMF_ROUTER_PRIORITY, length=1, value priority*

For E-CDS operation, some value of SMF_ROUTER_PRIORITY must be given
or assumed for each address in the <address-block> portion of the
SMF_HELLO message. If a SMF_HELLO message originator does not
provide a SMF_ROUTER_PRIORITY value for given address(es), a default
value SMF_RPRI_DEFAULT=(TBD) should be assumed. Local determination
of a node SMF_ROUTER_PRIORITY value can be done in multiple ways as
described in the [E-CDS]. An early implementation of SMF and E-CDS
has used node degree computed during neighbor discovery, yet it is
still unclear if this is the best method. Unlike the MPR method, the
E-CDS is a self-electing algorithm. SMF_ROUTER_PRIORITY needs to be
shared with all immediate neighbor nodes and 2-hop neighbor knowledge
is needed during the self election process. Further algorithm
examples and details are covered in the Appendices.

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 33]

Internet-Draft SMF for MANET March 2006

Appendix C. Multipoint Relay Connected Dominating Set (MPR-CDS)
Algorithm

The MPR-CDS algorithm is an extension to the basic MPR election
algorithm and results in a shared relay set that forms a CDS. Its
forwarding rules within SMF are non-dependent upon previous hop
information similar to E-CDS.

C.1. MPR-CDS Relay Set Selection

An overview of the the MPR-CDS selection algorithm is provided in
[MPR-CDS]. The basic requirements for election are similar to the
basic MPR algorithm with the addtion that some node ordering
knowledge is required. This is similar to the E-CDS requirement and
can be based upon node IP address or some other unique router
identifier. The rules for election are as follows:

A node decides it is in the relay set if:

1. the node is smaller than all its neighbors (Rule 1)

2. or the node is an MPR of its smallest neighbor (Rule 2)

C.2. MPR-CDS Forwarding Rules

MPR-CDS forwarding are quite simple and straightforward. As with
E-CDS, there is no need to check previous hop information during
forwarding. Upon electing itself as a MPR-CDS relay set forwarder,
SMF nodes perform DPD functions and forward all ranges of multicast
traffic allowed.

C.3. Neighborhood Discovery Requirements

No additional discovery requirements are needed beyond the basic
Hello and MPR-related TLVs already discussed.

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 34]

Internet-Draft SMF for MANET March 2006

Authors' Addresses

Joseph Macker
NRL
Washington, DC 20375
USA

Email: macker@itd.nrl.navy.mil

SMF Design Team
IETF MANET WG

Email: manet@ietf.org

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 35]

Internet-Draft SMF for MANET March 2006

Intellectual Property Statement

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.

Disclaimer of Validity

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 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.

Copyright (C) The Internet Society (2006). 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.

Acknowledgment

Funding for the RFC Editor function is currently provided by the
Internet Society.

Macker, editor & SMF Design Team Expires September 6, 2006 [Page 36]

PAFTECH AB 2003-2026

2026-04-23 09:01:16