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. Copyright Notice Copyright (c) 2011 IETF Trust and the persons identified as the document authors. All rights reserved. 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: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Version| Traffic Class | Flow Label | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Payload Length | Next Header | Hop Limit | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source Address | . . +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + Destination Address | . . +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + Extension Headers | . . +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Code | Checksum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Target Address | . . +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Options ... +-+-+-+-+-+-+-+-+-+-+-+- 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 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.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]