grajzer-autoconf-ndpp-00.txt

Internet DRAFT - draft-grajzer-autoconf-ndpp

draft-grajzer-autoconf-ndpp

Last Version:	draft-grajzer-autoconf-ndpp-00.txt	Tracker Entry
Date:	`08-Mar-2011`
Disposition:	expired

MANET Autoconfiguration (Autoconf) M. Grajzer
Internet Draft Telcordia Poland Sp. z o.o.
Intended status: Standard March 4, 2011
Expires: September 2011

ND++ - an extended IPv6 Neighbor Discovery protocol for enhanced
duplicate address detection to support stateless address auto-
configuration in IPv6 mobile ad hoc networks.
draft-grajzer-autoconf-ndpp-00.txt

Abstract

This document proposes the extended IPv6 Neighbor Discovery protocol
for enhanced duplicate address detection in mobile ad hoc networks.
It exploits Multipoint Relay concept for flooding of multihop
protocol messages. As a result the protocol extension provides
support for the stateless address auto-configuration in mobile ad
hoc networks.

Status of this Memo

This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.

This document may contain material from IETF Documents or IETF
Contributions published or made publicly available before November
10, 2008. The person(s) controlling the copyright in some of this
material may not have granted the IETF Trust the right to allow
modifications of such material outside the IETF Standards Process.
Without obtaining an adequate license from the person(s) controlling
the copyright in such materials, this document may not be modified
outside the IETF Standards Process, and derivative works of it may
not be created outside the IETF Standards Process, except to format
it for publication as an RFC or to translate it into languages other
than English.

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.

Grajzer Expires September 4, 2011 [Page 1]

Internet-Draft Neighbor Discovery ++ March 2011

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 4, 2011.

This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with
respect to this document. Code Components extracted from this
document must include Simplified BSD License text as described in
Section 4.e of the Trust Legal Provisions and are provided without
warranty as described in the Simplified BSD License.

Table of Contents

1. Introduction...................................................3
2. Remarks and Terminology........................................4
3. Protocol extension overview....................................5
3.1. Extended DAD..............................................5
3.2. Additional functionality:.................................7
4. Message type and format........................................8
4.1. Neighbor Solicitation with multi-hop capabilities:........9
4.2. Neighbour Advertisement with 1-hop capabilities:..........9
4.2.1. MPR Parameters Option:..............................10
4.2.2. MPR Announcement Option:............................11
4.3. Random ID option of Hop-by-hop extension header..........12
4.4. Neighbour Advertisement with multi-hop capabilities:.....13

Grajzer Expires September 4, 2011 [Page 2]

Internet-Draft Neighbor Discovery ++ March 2011

4.4.1. Topology and Link Control Info Option:..............14
5. Detailed protocol description.................................15
5.1. MPR Processes............................................15
5.2. Usage of Random ID Option................................17
5.3. Forwarding of multi-hop messages.........................18
5.4. DAD++ procedure..........................................18
5.5. Link monitoring and topology discovery...................19
6. Security Considerations.......................................20
7. IANA Considerations...........................................20
8. References....................................................20
8.1. Normative References.....................................20
8.2. Informative References...................................21
9. Acknowledgments...............................................21

1. Introduction

In Mobile Ad hoc NETworks (MANETs) the behavior of nodes is
determined by a network design assuming the lack of both - a pre-
defined infrastructure and a central network administration. This is
accompanied by a relatively high dynamicity and node mobility.

Rapidly changing topology and node mobility put a demand on address
auto-configuration in MANETs, where configuration needs to be kept
even when the network is changing. Thus it is especially important
in IPv6-based MANETs to verify the uniqueness of the addresses used
by each node, since possible duplication may cause network protocols
to misbehave. In particular verification of address uniqueness is
also a core element of stateless address auto-configuration.

Duplicate Address Detection (DAD) procedure is proposed for IPv6
networks as a way of verifying the uniqueness of node's addresses.
In basic IPv6 solutions ([RFC4861],[RFC4862]) it is performed only
in the one-hope neighborhood of each node, since it was originally
proposed for fixed networks. However changing topology and node
mobility put a demand on DAD in MANETs, which should span across a
wider range of nodes. Verification of the uniqueness of addresses in
this case must be performed efficiently and the protocol message
overhead should be minimized.

In this document the Neighbor Discovery (ND) protocol [RFC4861]
extension, denoted as ND++, is proposed, which is designed to
address the needs of MANET networks. The extension enables Neighbor
Discovery protocol to verify the uniqueness of an address in the
range of several hops (enhanced DAD). It incorporates Multipoint
Relay (MPR) concept originally proposed for OLSR routing protocol in

Grajzer Expires September 4, 2011 [Page 3]

Internet-Draft Neighbor Discovery ++ March 2011

[RFC3626], which provides means for efficient flooding of multihop
protocol messages. As a result ND++ comes up with an efficient
support for stateless address auto-configuration (SAA) in IPv6-based
MANET networks.

2. Remarks and Terminology

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 RFC-2119 [RFC2119].

Whenever "address" is mentioned in this document, it is an IPv6
address assigned to one of node's interfaces.

This document uses the following terminology, which is mostly
derived from [RFC3626] and [RFC4861]:

node

a device that implements IPv6, can be either a router or a
host

router

a node that forwards IP packets not explicitly addressed to
itself

host

any node that is not a router

neighbours

nodes attached to the same link, a node x is a neighbour node
of node y if node y can hear node x

2-hop neighbour

a node heard by a neighbour; a node attached on the same link
with a neighbour

strict 2-hop neighbour

Grajzer Expires September 4, 2011 [Page 4]

Internet-Draft Neighbor Discovery ++ March 2011

a 2-hop neighbour which is not a node itself or a neighbour of
the node and in addition is a neighbour of a node's neighbour
with a willingness different from WILL_NEVER

Multipoint Relay (MPR)

a node which is selected by its 1-hop neighbour, node x, to
"re-transmit" all the broadcast messages that it receives from
x, provided that the message is not a duplicate, and that the
hop limit field of the message is greater than one and
different from 255

MPR Selector

a node which has selected its 1-hop neighbour as its
Multipoint Relay

3. Protocol extension overview

3.1. Extended DAD

The proposed ND++ extension is designed to implement the mechanism
of enhanced DAD (DAD++) performed in n-hop range. It aims to verify
the uniqueness of the node's address in the range of n hops. The
DAD++ procedure is performed in two stages: at first in the 1-hop
neighborhood (referred to as DAD) and second in the range of n hops
covering possibly whole MANET domain (referred to as n-DAD). The
whole duplicate address detection process is thus denoted as DAD++.
This two-stage approach enables to introduce improved flooding of
multihop ND++ messages by means of the MPR concept, which requires
valid node identifiers at least in a range of 1 hop.

In the DAD++ procedure a node first starts 1-hop DAD by sending 1-
hop Neighbor Solicitation (NS) message to all its neighbors, as
defined in basic ND protocol [RFC4861]. If the recipient of the
message detects that the target address listed in NS message is
equal to one of its valid addresses, it sends the notification -
Neighbor Advertisement (NA) message, to let the sender know that it
cannot use the requested address. If at this stage duplication was
not found, the node can start preparation for n-DAD. At this stage
it chooses from its 1-hop neighborhood nodes willing to forward
packets on its behalf - the MPRs. Only MPRs will be allowed to
forward packets, so this way flooding of ND++ protocol multihop
messages is optimized. To complete DAD++, the node starts to send
multihop NS messages that will be forwarded by MPRs. These messages

Grajzer Expires September 4, 2011 [Page 5]

Internet-Draft Neighbor Discovery ++ March 2011

have wider range and can be used to verify the uniqueness of the
address within the range of n hops. If there is any node within this
range, that has the same address as the one specified as a target
address, it will reply with multihop NA message to inform the sender
about duplication. All multicast messages are propagated by means of
MPRs. They follow the same procedures as 1-hop NS and NA messages,
but can be forwarded. Detailed description of the ND++ protocol
functionality is given in the remaining part of this document.

MPR-related procedures are derived from [RFC3626]. In this approach
each node in a network recognizes its one hope neighborhood. From
this 1-hop neighborhood it chooses particular nodes (denoted as
MPRs) willing to forward packets on its behalf. MPRs are chosen in
such a way that they ensure that all strict 2-hop neighbors will
receive the forwarded message with minimum overhead. The MPR
selection algorithm is defined in [RFC3626] and is used in the ND++
extension. The messages used to gather information necessary for
choosing MPRs are exchanged as newly proposed options to ND++
protocol messages. The proposed ND++ options: MPR Parameters Option,
MPR Announcement Option and Topology and Link Control Info Option
are incorporating some concepts introduced in [RFC3626] into the ND
protocol. Their internal structure is based on the message types
proposed for OLSR protocol.

The proposed solution exploits the design paradigms of IPv6 protocol
stack. It incorporates into ND protocol new sub-types of messages
with multi-hop capabilities and new option types supporting MPR
processes. The proposed protocol exploits also new option proposed
as a Hop-by-hop Extension Header option, which is carried in the
IPv6 packet header. Since the ND++ is an extension to basic ND
(specified in [RFC4861]), the core functionality of ND remains
unchanged and must be supported in order to ensure proper
interactions with nodes that do not support ND++ implementation. The
IPv6 design is flexible and therefore enables such coexistence. Thus
the extension is backward compatible.

In the ND++ extension two main types of Neighbor Solicitation (NS)
and Neighbor Advertisement (NA) messages are envisioned:

o 1-hop NS and NA messages having link-local scope, not being
forwarded - similar to the one proposed in basic ND protocol

o Multi-hop NS and NA messages used to recognize node's further
neighborhood and perform Duplicate Address Detection in n-hop
range (n-DAD) - new message sub-types proposed for ND++

Grajzer Expires September 4, 2011 [Page 6]

Internet-Draft Neighbor Discovery ++ March 2011

In order to realize the DAD++ functionality, new options are
introduced to enable MPR selection and the usage of MPRs throughout
the process:

o MPR Parameters option - used by each node in a network to
advertise its forwarding capabilities - it specifies willingness
of a node to act as an MPR for other nodes and lists node
neighbors along with the information about their type and the
type of link to them. The option is based on the functionality
and message structure from OLSR routing protocol [RFC3626]

o MPR Announcement option - proposed for announcing which nodes
have been chosen to act as an MPR for a certain MPR selector
(message originator)

o Random ID Option attached to Hop-by-hop Extension Header
(included in the IPv6 packet header) - enables to distinguish
copies of own messages and is essential in MANET networks

DAD++ being incorporated with the ND++ protocol is able to verify
the uniqueness of the node's address in the n-hop range. The
procedure is performed also on the link-local addresses (valid in
link-local scope). This helps to keep proper network configuration
in the situations of node mobility. In such a case however, some
address auto-configuration procedure should follow DAD++, to obtain
routable address. For example an address having a site-local scope
should be generated by means of a prefix distributed within auto-
configuration procedures. This procedure is out of the scope of this
document.

3.2. Additional functionality:

The proposed ND++ extensions can be also exploited for link
monitoring and topology data collection. Such functionality can be
easily applied on top of the MPR-based flooding scheme that is used
in ND++. Thus following the OLSR specification [RFC 3626], link
monitoring and topology discovery mechanisms can be brought to ND++
and serve as a source of information for other interested processes
in a network (especially useful in autonomic networks, where network
monitoring is of great importance). MPRs incorporated in the process
are therefore not only means of efficient flooding but can also be
used to optimize data collection. The proposed Topology and Link

Grajzer Expires September 4, 2011 [Page 7]

Internet-Draft Neighbor Discovery ++ March 2011

Control Info Option can be used with multi-hop NA messages to enable
network data collection. Topology and link control information is
exchanged in a manner similar to the one described in [RFC3626].

4. Message type and format

Below the changes proposed to extend the ND protocol are specified.
They are incorporated as new sub-types of Neighbor Solicitation and
Neighbor Advertisement messages or included in the proposed new
options. Structure of options and their lengths are chosen according
to appropriate RFCs for IPv6 [RFC4443], [RFC2460].

An overview of IPv6 packet with inserted basic structure of NS and
NA option is given below for reference. This figure also depicts the
placement of ND options (NS or NA type) and Extension Headers:

Grajzer Expires September 4, 2011 [Page 8]

Internet-Draft Neighbor Discovery ++ March 2011

4.1. Neighbor Solicitation with multi-hop capabilities:

Functionality:

o To perform n-DAD - Duplicate Address Detection in n-hop scope in
order to resolve addresses of a node in a wider scope

o It is used with basic ND options

o Sent to all-nodes multicast address instead of solicited-node
multicast to avoid packet drop at intermediate nodes

Modifications:

IP Fields:

HopLimit: n (instead of 255)

ICMP Fields:

Code: 1 (instead of 0) - to introduce additional level
of message granularity as specified in [RFC4443]
and specify that this is a multi-hop message type

HopsSent: (OPTIONAL)field introduced as younger 8 bits of
Reserved filed, specifies HopLimit with which
message was sent by the originating node - can be
used by receiver to estimate number of hops
necessary to reply to this message. With external
network configuration this may not be necessary

4.2. Neighbour Advertisement with 1-hop capabilities:

Functionality (beyond the one described in [RFC4862]):

o To enable the MPR selection - for this purpose MPR Parameters
Option and MPR Announcement Option types are used with this
message type

Grajzer Expires September 4, 2011 [Page 9]

Internet-Draft Neighbor Discovery ++ March 2011

4.2.1. MPR Parameters Option:

The proposed option format is presented below:

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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length | Willingness | Link Code |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address 1 |
. .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. .
. .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address m |
. .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Link Code field - details:

0 1 2 3 4 5 6 7
+-------+-------+-------+-------+-------+-------+-------+-------+
| 0 | 0 | 0 | 0 | Neigh. Type | Link Type |
+-------+-------+-------+-------+-------+-------+-------+-------+

Type: 6 (TBD)
Length: 2m+1 (in 8-octet units, including Type and Length fields;
m - number of addresses held in the payload)

Willingness: specifies willingness of a node to become an MPR,
to be defined as in [RFC3626]:

WILL_NEVER = 0

WILL_LOW = 1

WILL_DEFAULT = 3

WILL_HIGH = 6

Grajzer Expires September 4, 2011 [Page 10]

Internet-Draft Neighbor Discovery ++ March 2011

WILL_ALWAYS = 7

Neighbor Address: Field used to advertise addresses of node's
neighbors

Link Code:

Neighbor Type (Neigh. Type): specifies type of neighbor, as
proposed in [RFC3626]:

NOT_NEIGH = 0

SYM_NEIGH = 1

MPR_NEIGH = 2

Link Type: specifies link type, as proposed in [RFC3626]:

UNSPEC_LINK = 0

ASYM_LINK = 1

SYM_LINK = 2

LOST_LINK = 3

Additional settings:

o Target Address field of 1-hop NA message carrying an option must
be set to node's main address

o Each MPR Parameters option is listing neighbors with the same
Link Code value; options with data for each Link Code value must
be inserted one after another

4.2.2. MPR Announcement Option:

The proposed option format is presented below:

Grajzer Expires September 4, 2011 [Page 11]

Internet-Draft Neighbor Discovery ++ March 2011

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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length | Reserved 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| MPR Address 1 |
. .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. .
. .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| MPR Address m |
. .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Type: 9 (TBD)

Length: 2m+1 (in 8-octet units, including Type and Length fields;
m - number of addresses held in the payload)

MPR Address: Field used to advertise addresses of nodes chosen to
be MPRs

4.3. Random ID option of Hop-by-hop extension header

The proposed option format is presented below:

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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Random node ID | Sequence Number (SN) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Functionality:

o To enable a node to distinguish echoes of its own previous
messages in fast and simple manner

Grajzer Expires September 4, 2011 [Page 12]

Internet-Draft Neighbor Discovery ++ March 2011

o Can be used to distinguish two nodes having duplicated addresses
before the completion of DAD++ (possible improvement of the MPR
selection procedure in MANETs - OPTIONAL)

o It can be appended to all messages sent in a MANET network, as
the functionality should be sustained during entire node's
operation mentioned above.

o It MUST be added to all outgoing multihop ND++ messages

Type: 7(TBD)

Length: 4 (in octets)

Random node ID: random number selected by each node as its
random ID (e.g. by using MD5 algorithm and
hostname as a seed)

Sequence Number (SN): can be used for fast detection of
duplicated messages

4.4. Neighbour Advertisement with multi-hop capabilities:

Functionality:

o To send answers to multihop NS messages (to all-nodes multicast
address)

o To exchange topology and link state information (OPTIONAL)

Modifications:

IP Fields:

HopLimit: n (instead of 255)

ICMP Fields:

Grajzer Expires September 4, 2011 [Page 13]

Internet-Draft Neighbor Discovery ++ March 2011

Code: 1 (instead of 0) - to introduce additional level of
message granularity as specified in [RFC4443] and
specify that this is multi-hop message type

4.4.1. Topology and Link Control Info Option:

The proposed option format is presented below:

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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length | ANSN |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Code | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbour Address 1 |
. .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. .
. .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbour Address m |
. .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Type: 10(TBD)

Length: 2m+1 (in 8-octet units; m - number of addresses held in
the payload)

Advertised Neighbour
Sequence Number (ANSN): value incremented after a change in
advertised parameters, enables for the

Grajzer Expires September 4, 2011 [Page 14]

Internet-Draft Neighbor Discovery ++ March 2011

node to decide which information is the
most recent [RFC3626]

5. Detailed protocol description

Below the detailed overview of the procedures proposed for ND++
extensions is given. It depicts:

o MPR processes

o Usage of Random ID Option

o Forwarding of multi-hop messages

o DAD++ procedure

o Link monitoring and topology discovery

5.1. MPR Processes

MPRs are used for the flooding optimization. Each node in a network
selects from its 1-hop neighborhood nodes willing to forward packets
and being chosen in such a way that their connections cover a strict
2-hop neighborhood in full in a locally optimal manner. These nodes
are denoted as Multipoint Relays (MPRs) whereas the node
initializing the process is called MPR Selector, according to
[RFC3626]. The MPR selection procedure is performed by means of the
proposed MPR Parameters Option and MPR Announcement Option.

Several structures must exist to store the data necessary for MPR
processes:

o Neighbors Set - a set of 1-hop neighbors along with 2-hop
neighbors they reported

o MPR Set - a set of all nodes chosen to be MPRs

o MPR Selector Set - a set of nodes which selected the owner of the
set as an MPR, i.e. the set of nodes for which the owner should
forward packets

MPR Parameters Option is attached to 1-hop Neighbor Advertisement
message. It enables announcing the willingness of the sender to

Grajzer Expires September 4, 2011 [Page 15]

Internet-Draft Neighbor Discovery ++ March 2011

become MPR along with the list of its 1-hop neighbors. By default a
node will have a willingness value set to WILL_DEFAULT [RFC3626].
This value can be however modified to adapt to the current
conditions in a network. Reserved field is set to zeroes. Each node
in a network listens to the NA messages with this option and
collects information about its neighboring nodes:

o their IPv6 address (only one address is used by each node to
advertise MPR Parameters - the node's "main" address on a given
interface; it is passed in the Target Address field of NA
message)

o their willingness to become MPR

o IPv6 addresses of their 1-hop neighbors (excluding own address)

Based on this information the MPR selection heuristic is used to
choose MPRs in the way described in [RFC3626]. A node is allowed to
send messages with this option type on a given interface only when
it has at least one valid IPv6 address assigned to this interface
(this would usually mean that the node has successfully completed
the 1-hop DAD procedure and has at least link-local address
identified as unique in the link-local scope). Each interface has
its own list of MPRs and the MPR processes on different interfaces
are independent. Nodes chosen as MPRs are listed in the MPR Set.

The MPR Announcement Option is attached to 1-hop NA message in order
to announce by the node (being an MPR Selector) which neighbors it
has chosen as MPRs. Addresses of all MPR neighbors are listed in the
option one after another. A node that receives a message with this
option checks if its own address is listed. If it finds an entry
with one of its addresses, it keeps the sender address in the MPR
Selector Set carrying addresses of all nodes that have chosen it as
MPR.

MPR Parameters option and MPR Announcement option are sent in the 1-
hop NA messages periodically, each mpr_delay seconds. Mpr_delay is a
configurable parameter. MPR Announcement option is attached after
MPR Parameters option in the same message only if there are MPRs
chosen by the sending node. The 1-hop NA message is sent with the
following parameters:

o Source address - node's main address

o Destination address - all-nodes link-local multicast address

o Target address - node's main address

Grajzer Expires September 4, 2011 [Page 16]

Internet-Draft Neighbor Discovery ++ March 2011

Once the interface becomes "up" the Random ID is chosen. If there is
at least one valid address assigned to this interface, MPR processes
will be started. If all addresses are tentative, first DAD would
need to be completed. A node however can also initiate MPR processes
on some interface upon receiving MPR Parameters option or MPR
Announcement option from some other node. If at this point there is
no valid address, the messages with MPR Parameters option of this
node will not be sent, however attempts will be made periodically.

At the start of MPR processes MPR lists implementing above mentioned
Neighbour Set, MPR Set and MPR Selectors Set are initiated for a
given interface. Then first MPR Parameters option is sent and the
timer enabling periodic sending of MPR options is started. At each
timer stop after mpr_delay seconds MPRs are chosen based on the
currently known neighborhood. If the operation was successful MPR
Announcement option is sent along with the next outgoing MPR
Parameters option. In the opposite case, only MPR Parameters option
is sent. The timer is started again to repeat the procedure
periodically. It is also possible that MPRs are chosen only if a
change in node's neighborhood was detected at timer stop. The
performance of both cases would depend on the particular
implementation.

All activities related to the estimation of Link Type are performed
as described in [RFC3626].

5.2. Usage of Random ID Option

Random ID Option is a new option to be used in Hop-by-hop extension
header [RFC2460]. It is used to enable the node to distinguish
copies of its own messages forwarded back. This option is included
in the IPv6 packet header, so such detection can be performed in
fast and simple manner without the need for looking into packet
content. The detection can be made regardless of message type
conveyed by IPv6 packets, which makes this extension useful also in
other protocols developed for MANET networks.

Random ID option can be also used as a support for another purpose -
limiting the number of forwarded messages. Such a usage is OPTIONAL
- it is not mandatory, but it can enhance protocol's performance.
MPRs which are forwarding packets can be thus responsible for
detecting duplicate packets that are not supposed to be forwarded
any further. The detection can be performed by means of the Sequence
Number (SN) field in the Random ID Option of Hop-by-Hop Options
extension header. SN is a message counter that can be incremented

Grajzer Expires September 4, 2011 [Page 17]

Internet-Draft Neighbor Discovery ++ March 2011

with each message sent by a node. As a result, the receiving node is
able to infer without comparison of the message payload, that two
messages with the same source address, destination address, Random
ID and sequence number are duplicated.

5.3. Forwarding of multi-hop messages

Packets having an n-hop scope, i.e. multi-hop NS and multi-hop NA
messages, will have a Hop Limit field set to n by the packet
originator. This implicates that they can be forwarded - in contrary
to standard ND messages. As such in order to ensure an efficient
flooding of ND++ messages in the network, only nodes selected as
MPRs are allowed to forward packets. Packets are forwarded using
multicast transmission in IPv6 by means of all-nodes multicast
address having a link-local scope.

For each incoming multi-hop NS or multi-hop NA packet receiving node
checks if the sender is its MPR Selector (is in MPR Selectors Set).
If yes, the message is forwarded, if no - it is not. It is also
assumed that if it happens that MPR processes are not initiated by a
node yet, it will forward the packet anyway.

Each forwarder is also an envisioned recipient of the message, so
the copy of the message is forwarded, but the message itself is
processed by the receiving node as well.

5.4. DAD++ procedure

DAD++ procedure is performed in two stages. In the first stage of
this process DAD in a 1-hop range is performed in a similar way as
in the standard ND protocol. Next the part of DAD++, denoted as n-
DAD, is performed to verify uniqueness of node's address in n-hop
scope.

After a new address is assigned or the need for DAD++ is
communicated from external source (e.g. user space application,
triggered by network administrator, etc.) node starts the DAD++
procedure by performing 1-hop DAD. If duplication was detected at
this stage, DAD++ is terminated and necessary actions are performed,
as defined in [RFC4862] (the address cannot be used). However if DAD
was completed and no duplicates were found, the procedure will
follow with the MPR selection. Data from other nodes necessary to
choose MPRs are collected constantly since the interface is up. The

Grajzer Expires September 4, 2011 [Page 18]

Internet-Draft Neighbor Discovery ++ March 2011

MPR procedures should be performed in parallel to DAD++, however for
safety they can be also initiated after completion of DAD. Thus
after completion of 1-hop DAD MPRs are chosen and MPR Announcement
option is sent to inform node's neighbors. This message is also sent
for safety reasons, as in most cases the originating node will have
MPRs already chosen. n-DAD procedure is started after ndad_delay
seconds. ndad_delay parameter is configurable, but it must be larger
than mpr_delay.

n-DAD++ is executed by means of NS messages with multi-hop
capabilities specified above along with option types defined in the
basic ND protocol description for DAD. It follows the procedures
specified for basic ND in [RFC4861]. Thus the address for which
DAD++ is run must not be included as the source address in the IPv6
packet [RFC4861] and is included in the Target Address field of NS
messages. If the address is duplicated, NA message is sent by the
node, which recognizes target address as its own, to the all-nodes
multicast address [RFC4861]. This message is flooded within the
network by means of MPRs. Such a solution enables performing the
DAD++ procedure before the routing is present in a network.

n-DAD is performed in the range of n hops. The value of n is a
configurable protocol parameter. In general it should be chosen
possibly large - e.g. to cover the whole MANET domain, however in
large scale MANETs some restrictions towards the DAD++ range should
be specified in order to keep the message overhead at a reasonable
level. Investigation of how to choose the best Hop Limit value is
out of the scope of this document.

After the whole DAD++ process is completed the ND++ protocol may be
used to fulfill the remaining goals. It's necessary however, that
either Stateless or Stateful Address Auto-configuration is completed
first in order to guarantee that nodes will acquire routable
addresses.

5.5. Link monitoring and topology discovery

In order to incorporate additional functionalities of ND++ protocol
extension, Topology and Link Control Info Option (Figure 6) can be
added to NA messages with multihop capabilities. This way node-local
knowledge about topology and link states can be disseminated to
other nodes in the network. In order to reduce the amount of the
transmitted information only MPRs and links to MPRs of each node
should be reported (indicated by means of Neighbor Type fields).
Each node reports only information about the addresses of nodes in

Grajzer Expires September 4, 2011 [Page 19]

Internet-Draft Neighbor Discovery ++ March 2011

its 1-hop neighborhood. It is important that the main address of the
originating node should be conveyed by the Target Address field in
ICMP part of the NA message. Topology and Link Control Info Option
is used to report the state of links between a node and its
neighbors (inference about link types is derived from ([RFC3626]).
Neighbors are grouped according to their type and link type between
them and the node performing an action. Addresses of all neighbors
from the group are incorporated into one option. Different options
are created for different groups by exploiting Neighbor Type and
Link Type bits in the Link Code field. Once an update to the link
information is needed the node increments the Advertised Neighbor
Sequence Number (ANSN), so that information recipients can be
notified that the current message is not a copy of the previously
sent one and the information stored in its cache should be updated
[RFC3626].

6. Security Considerations

TBD.

7. IANA Considerations

This document specifies new ICMPv6 option types to be assigned for
MPR Parameters Option, MPR Announcement Option and Topology and Link
Control Info Option as well as new Hop-by-hop option type for Random
ID option. Values used in this document are a subject for discussion
and are assigned temporarily. The same holds true for the ICMPv6
code value for usage with multihop NS and NA messages.

8. References

8.1. Normative References

[RFC4861]Narten, T.and Nordmark, E. and Simpson, W. and Soliman, H.,
"Neighbor Discovery for IP version 6 (IPv6)", RFC 4861,
September 2007.

[RFC4862] Thomson, S.and Narten, T. and Jinmei, T., "IPv6 Stateless
Address Autoconfiguration", RFC 4862, September 2007.

Grajzer Expires September 4, 2011 [Page 20]

Internet-Draft Neighbor Discovery ++ March 2011

[RFC3626] Clausen, T. and Jacquet, P., "Optimised Link State Routing
Protocol (OLSR)", RFC 3626, October 2003

8.2. Informative References

[RFC4443] Conta, A. and Deering, S. and Gupta, M., "Internet Control
Message Protocol (ICMPv6) for the Internet Protocol
Version 6 (IPv6) Specification", RFC 4443, March 2006

[RFC2460] Deering, S. and Hinden, R., "Internet Protocol, Version 6
(IPv6) Specification", RFC 2460, December 1998

9. Acknowledgments

The author would like to thank Agnieszka Betkowska Cavalcante and
Tomasz Zernicki for their help during the implementation of ND++
extension.

This work has been supported by EC FP7 EFIPSANS project (INFSO-ICT-
215549)

This document was prepared using 2-Word-v2.0.template.dot.

Authors' Addresses

Monika Grajzer
Telcordia Poland Sp. z o.o.
ul. Umultowska 85
61-614 Poznan
Poland

Phone: +48 61 829 63 74
Email: mgrajzer@telcordia.com

Grajzer Expires September 4, 2011 [Page 21]