Mobile Ad hoc Networking (MANET) T. Clausen Internet-Draft LIX, Ecole Polytechnique, France Expires: December 21, 2006 C. Dearlove BAE Systems Advanced Technology Centre J. Dean Naval Research Laboratory The OLSRv2 Design Team MANET Working Group June 19, 2006 MANET Neighborhood Discovery Protocol (NHDP) draft-ietf-manet-nhdp-00 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 December 21, 2006. Copyright Notice Copyright (C) The Internet Society (2006). Abstract This document describes a neighborhood discovery protocol (NHDP) for a mobile ad hoc network (MANET). The protocol provides each MANET Clausen, et al. Expires December 21, 2006 [Page 1] Internet-Draft MANET-NHDP June 2006 node with local topology up to two hops distant, describing a node's 1-hop neighbors and symmetric 2-hop neighbors. This is achieved through periodic message exchange. This neighborhood discovery protocol may be used by any MANET protocols which need neighborhood information. The protocol imposes minimum requirements to the network by not requiring sequenced or reliable transmission of control traffic. Clausen, et al. Expires December 21, 2006 [Page 2] Internet-Draft MANET-NHDP June 2006 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 1.2. Applicability Statement . . . . . . . . . . . . . . . . . 5 2. Protocol Overview and Functioning . . . . . . . . . . . . . . 7 3. Neighborhood Information Base . . . . . . . . . . . . . . . . 9 3.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2. Symmetric Neighbor Set . . . . . . . . . . . . . . . . . . 10 3.3. Neighborhood Address Association Set . . . . . . . . . . . 11 3.4. 2-Hop Neighbor Set . . . . . . . . . . . . . . . . . . . . 11 4. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 13 4.1. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 13 4.1.1. Local Interface Block . . . . . . . . . . . . . . . . 14 4.1.2. Message TLVs . . . . . . . . . . . . . . . . . . . . . 14 4.1.3. Address Block TLVs . . . . . . . . . . . . . . . . . . 16 5. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 17 5.1. HELLO Message: Transmission . . . . . . . . . . . . . . . 18 6. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 19 6.1. Populating the Link Set . . . . . . . . . . . . . . . . . 19 6.2. Populating the Symmetric Neighbor Set . . . . . . . . . . 20 6.3. Populating the Neighborhood Address Association Set . . . 21 6.4. Populating the 2-Hop Neighbor Set . . . . . . . . . . . . 22 6.5. Neighborhood Changes . . . . . . . . . . . . . . . . . . . 23 7. Proposed Values for Constants . . . . . . . . . . . . . . . . 24 7.1. Message Intervals . . . . . . . . . . . . . . . . . . . . 24 7.2. Holding Times . . . . . . . . . . . . . . . . . . . . . . 24 7.3. Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 25 8.1. Multicast Addresses . . . . . . . . . . . . . . . . . . . 25 8.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 25 8.3. TLV Types . . . . . . . . . . . . . . . . . . . . . . . . 25 8.4. LINK_STATUS and OTHER_NEIGHB Values . . . . . . . . . . . 26 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 27 9.1. Normative References . . . . . . . . . . . . . . . . . . . 27 9.2. Informative References . . . . . . . . . . . . . . . . . . 27 Appendix A. Heuristics for Generating HELLO Messages . . . . . . 28 Appendix B. HELLO Message Example . . . . . . . . . . . . . . . . 31 Appendix C. Security Considerations . . . . . . . . . . . . . . . 33 Appendix D. Flow and Congestion Control . . . . . . . . . . . . . 35 Appendix E. Contributors . . . . . . . . . . . . . . . . . . . . 36 Appendix F. Acknowledgements . . . . . . . . . . . . . . . . . . 37 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 38 Intellectual Property and Copyright Statements . . . . . . . . . . 39 Clausen, et al. Expires December 21, 2006 [Page 3] Internet-Draft MANET-NHDP June 2006 1. Introduction This document describes a neighborhood discovery protocol (NHDP) for a mobile ad hoc network (MANET). It was originally developed for the Optimized Link State Routing Protocol version 2 (OLSRv2) [3], based on that used in the Optimized Link State Routing Protocol version 1 [4]. It uses an exchange of HELLO messages in order that each node can determine its neighborhood up to two hops distant. This protocol is used by OLSRv2 to determine a node's 1-hop neighbors for routing, and to allow the selection of MultiPoint Relays (MPRs) for optimized flooding and topology reporting. This specification however only describes the message exchange and information storage required for 1-hop and symmetric 2-hop neighborhood discovery. It may be used by any MANET protocols which need neighborhood information, and which may add an MPR mechanism, or an alternative to it, using appropriate TLVs (type-length-value objects) as specified in [1], using which this protocol's HELLO message format is defined. This protocol makes no assumptions about the underlying link layer, other than support of local multicast. Link layer information and notifications may be used if available and applicable to qualify the neighborhood information. 1.1. Terminology The keywords "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 [2]. Additionally, this document uses the following terminology: node - A MANET router which implements this neighborhood discovery protocol. MANET interface - A network device participating in a MANET and using this neighborhood discovery protocol. A node may have several MANET interfaces, each interface being assigned one or more IP addresses. link - A link is a pair of MANET interfaces from two different nodes, where at least one interface is able to hear (i.e. receive traffic from) the other. symmetric link - A link where both MANET interfaces are able to hear (i.e. receive traffic from) the other. Clausen, et al. Expires December 21, 2006 [Page 4] Internet-Draft MANET-NHDP June 2006 asymmetric link - A link which is not symmetric. 1-hop neighbor - A node X is a 1-hop neighbor of a node Y if node Y can hear node X (i.e. a link exists from a MANET interface on node X to a MANET interface on node Y). symmetric 1-hop neighbor - A node X is a symmetric 1-hop neighbor of a node Y if a symmetric link exists from a MANET interface on node X to a MANET interface on node Y. symmetric 2-hop neighbor - A node X is a symmetric 2-hop neighbor of a node Y if node X is a symmetric 1-hop neighbor of a symmetric 1-hop neighbor of node Y, but is not node Y itself. 1-hop neighborhood - The 1-hop neighborhood of a node X is the set of the 1-hop neighbors of node X. symmetric 1-hop neighborhood - The symmetric 1-hop neighborhood of a node X is the set of the symmetric 1-hop neighbors of node X. symmetric 2-hop neighborhood - The symmetric 2-hop neighborhood of a node X is the set of the symmetric 2-hop neighbors of node X. (This may include nodes in the 1-hop neighborhood, or even in the symmetric 1-hop neighborhood, of node X.) 1.2. Applicability Statement This neighborhood discovery protocol supports nodes which have one or more interfaces which participate in the MANET. It provides each node with local topology information up to two hops away. This information is made available to other protocols through a collection of sets describing the node's 1-hop neighborhood and symmetric 2-hop neighborhood, collectively known as the neighborhood information base. The specification is designed specifically with IP (IPv4/IPv6) in mind. All addresses within a control message are assumed to be of the same size, deduced from IP. In the case of mixed IPv6 and IPv4 addresses, IPv4 addresses are carried in IPv6 as specified in [5]. The packets defined by this specification may use any transport protocol appropriate to the protocol using this specification. When the diffusion mechanism enabled by this specification is employed, UDP may be most appropriate. This protocol uses the message exchange format specified in [1]. This implies that the HELLO messages specified by this protocol may be extended using the TLV mechanisms described in [1], e.g. to signal Clausen, et al. Expires December 21, 2006 [Page 5] Internet-Draft MANET-NHDP June 2006 MPR selection as required by OLSRv2 [3]. This also implies that neighborhood discovery protocol messages can be transmitted in packets with messages from other protocols, so long as these protocols also use [1]. Clausen, et al. Expires December 21, 2006 [Page 6] Internet-Draft MANET-NHDP June 2006 2. Protocol Overview and Functioning This protocol consists of a specification of local signaling, which serves to: o advertise the presence of a node and its MANET interfaces to adjacent nodes (1-hop neighbors); o discover links to adjacent nodes; o perform bidirectionality (symmetry) checks on the discovered links; o advertise discovered links and whether each is symmetric to its 1-hop neighbors and hence discover symmetric 2-hop neighbors; o maintain an information base consisting of discovered links and their status, 1-hop neighbors and their MANET interfaces, symmetric 1-hop neighbors and symmetric 2-hop neighbors. Signaling consists of a single type of periodically transmitted message known as a HELLO message. A HELLO message identifies its originator node and that node's MANET interfaces and addresses. As a node receives HELLO messages and populates its information base, a list of 1-hop neighbors' MANET interface addresses and their link status is included in subsequent HELLO message content. Thus, the periodic transmission allows nodes to continuously track changes in their 1-hop and symmetric 2-hop neighborhoods. Because each node sends HELLO messages periodically, the protocol can tolerate reasonable message loss without requiring reliable transmission. Such losses can occur frequently in radio networks due to collisions or other transmission problems. The nominal time interval of a node's periodic HELLO transmission is known as HELLO_INTERVAL and MAY be included in the HELLO message. The HELLO message MUST include a validity time value that indicates the length of time for which the message content is to be considered valid and included in the receiving node's information base. In some uses the validity time may be a multiple of HELLO_INTERVAL to allow for lossy exchange of HELLO messages. HELLO messages MAY, in addition to periodic transmissions, also be generated as a response to some event (e.g. a change in the advertised neighborhood indicated by a received HELLO message or by a layer 2 notification, if available, indicating a change in a link to a neighbor). However a node MUST respect a minimum interval, HELLO_MIN_INTERVAL, between successive HELLO message transmissions in Clausen, et al. Expires December 21, 2006 [Page 7] Internet-Draft MANET-NHDP June 2006 order to maintain an upper bound on signaling traffic. This protocol is designed to work in a completely distributed manner and does not depend on any central entity. This protocol does not require any changes to the format of IP packets, thus any existing IP stack can be used as is. Each MANET node will form estimates of its 1-hop and symmetric 2-hop neighborhoods as this protocol operates. These estimates can be maintained in an information base comprised of the data sets listed below. These are defined formally in Section 3 and can be summarized as follows: Link Set - This set records the status of all links from and, if symmetric, to 1-hop neighbors. It also records as lost links which used to be symmetric but have since failed. A node MUST record the Link Set in order to correctly send HELLO messages. Symmetric Neighbor Set - This set records the addresses of the MANET interfaces of symmetric 1-hop neighbors, or, as lost, those which used to be. Note that if any of these nodes have more than one MANET interface then this set may record addresses that are not in the Link Set. A node MUST record the Symmetric Neighbor Set in order to correctly send HELLO messages. Neighborhood Address Association Set - This set allows the addresses of the MANET interfaces of each 1-hop neighbor to be associated with each other. It is required for processes such as MPR selection as in [3]. 2-Hop Neighbor Set - This set records the addresses of the MANET interfaces of symmetric 2-hop neighbors. It is required for processes such as MPR selection as in [3]. Clausen, et al. Expires December 21, 2006 [Page 8] Internet-Draft MANET-NHDP June 2006 3. Neighborhood Information Base The neighborhood information base stores information about the 1-hop neighborhood and the symmetric 2-hop neighborhood of a node. Note that it is possible for a node, X, to be present in both the 1-hop and symmetric 2-hop neighborhoods of another node, Y, concurrently. If the link between node X and node Y breaks, this allows node X to be taken into consideration as a symmetric 2-hop neighbor by node Y immediately, rather than waiting for a HELLO message exchange cycle. This specification assumes that all addresses have an associated prefix length. The prefix length of an address is, in HELLO messages, indicated using the PREFIX_LENGTH TLV specified in [1]. If no PREFIX_LENGTH TLV is present for a given address, it is assumed that the prefix length for that address is equal to the length of the address. Two addresses are identical if and only if both the addresses and their associated prefix lengths are identical. Addresses recorded in the neighborhood information base (L_local_iface_addr, L_neighbor_iface_addr, N_local_iface_addr, N_neighbor_iface_addr, N2_local_iface_addr, N2_neighbor_iface_addr, N2_2hop_iface_addr and those listed in NA_neighbor_iface_addr_list) MUST all be recorded with prefix lengths, in order to allow comparison with addresses received in HELLO messages. 3.1. Link Set A node records a set of "Link Tuples", recording information about its 1-hop neighborhood: (L_local_iface_addr, L_neighbor_iface_addr, L_SYM_time, L_ASYM_time, L_time) each describing a link between a MANET interface of this node and a MANET interface of one of its 1-hop neighbors, where: L_local_iface_addr is the address of the MANET interface of the local node on which the 1-hop neighbor is or was heard; L_neighbor_iface_addr is the address of the MANET interface of the 1-hop neighbor; L_SYM_time is the time until which the link to the 1-hop neighbor is considered symmetric; Clausen, et al. Expires December 21, 2006 [Page 9] Internet-Draft MANET-NHDP June 2006 L_ASYM_time is the time until which the MANET interface of the 1-hop neighbor is considered heard; L_time specifies when this Link Tuple expires and MUST be removed. The status of the link, denoted L_STATUS, can be derived based on the fields L_SYM_time and L_ASYM_time as defined in Table 1. +-------------+-------------+-----------+ | L_SYM_time | L_ASYM_time | L_STATUS | +-------------+-------------+-----------+ | Expired | Expired | LOST | | | | | | Not Expired | Expired | SYMMETRIC | | | | | | Not Expired | Not Expired | SYMMETRIC | | | | | | Expired | Not Expired | HEARD | +-------------+-------------+-----------+ Table 1 In a node, the set of Link Tuples is denoted the "Link Set". 3.2. Symmetric Neighbor Set A node records a set of "Symmetric Neighbor Tuples", recording information about its symmetric 1-hop neighborhood: (N_local_iface_addr, N_neighbor_iface_addr, N_SYM_time, N_time) each describing an address of a MANET interface of this node and an address of a MANET interface of one of its symmetric 1-hop neighbors, where: N_local_iface_addr is the address of the MANET interface of the local node to which the 1-hop neighbor has or had a symmetric link; N_neighbor_iface_addr is an address of a MANET interface of a 1-hop neighbor which is or was in this node's symmetric 1-hop neighborhood; N_SYM_time is the time until which the 1-hop neighbor is considered to be in this node's symmetric 1-hop neighborhood; Clausen, et al. Expires December 21, 2006 [Page 10] Internet-Draft MANET-NHDP June 2006 N_time specifies when this Symmetric Neighborhood Tuple expires and MUST be removed. The status of the 1-hop neighbor, denoted N_STATUS, can be derived based on the field L_SYM_time as defined in Table 2. +-------------+-----------+ | N_SYM_time | N_STATUS | +-------------+-----------+ | Expired | LOST | | | | | Not Expired | SYMMETRIC | +-------------+-----------+ Table 2 In a node, the set of Symmetric Neighbor Tuples is denoted the "Symmetric Neighbor Set". 3.3. Neighborhood Address Association Set A node records a set of "Neighborhood Address Association Tuples", recording information about the MANET interface configuration of its 1-hop neighbors: (NA_neighbor_iface_addr_list, NA_time) NA_neighbor_iface_addr_list is a list of interface addresses of a single 1-hop neighbor; NA_time specifies when this Neighborhood Address Association Tuple expires and MUST be removed. In a node, the set of Neighborhood Address Association Tuples is denoted the "Neighborhood Address Association Set". 3.4. 2-Hop Neighbor Set A node records a set of "2-Hop Neighbor Tuples", recording information about a its symmetric 2-hop neighborhood: (N2_local_iface_addr, N2_neighbor_iface_addr, N2_2hop_iface_addr, N2_time) each describing a symmetric link between an address of a MANET interface of one of this node's symmetric 1-hop neighbors and an address of a MANET interface of a node in this node's symmetric 2-hop neighborhood. Clausen, et al. Expires December 21, 2006 [Page 11] Internet-Draft MANET-NHDP June 2006 N2_local_iface_addr is the address of the local MANET interface over which the information defining this 2-Hop Neighbor Tuple was received; N2_neighbor_iface_addr is the address of the MANET interface address of a symmetric 1-hop neighbor; N2_2hop_iface_addr is the address of a MANET interface of a symmetric 2-hop neighbor which has a symmetric link (not necessarily using this address) to the node with MANET interface address N2_neighbor_iface_addr; N2_time specifies the time at which this 2-Hop Neighbor Tuple expires and MUST be removed. In a node, the set of 2-Hop Neighbor Tuples is denoted the "2-Hop Neighbor Set". Clausen, et al. Expires December 21, 2006 [Page 12] Internet-Draft MANET-NHDP June 2006 4. Packets and Messages The packet and message format used by this neighborhood discovery protocol is defined in [1], which is used with the following considerations: o this protocol specifies one message type, the HELLO message, in Section 4.1; o HELLO message header options may be used as specified by the protocol which uses this neighborhood discovery protocol; o HELLO messages are transmitted only one hop, i.e. MUST NOT be forwarded; o multi-message packets may be created using other messages as specified by the protocol which uses this neighborhood discovery protocol; o packet header options may be used as specified by the protocol which uses this neighborhood discovery protocol. 4.1. HELLO Messages A HELLO message MUST contain: o a message TLV with Type == VALIDITY_TIME and Value == H_HOLD_TIME, as specified in Section 4.1.2.1 o an address block known as the Local Interface Block, as specified in Section 4.1.1; other addresses MUST NOT be added to this address block. A HELLO message MAY contain: o a message TLV with Type == INTERVAL_TIME and Value == HELLO_INTERVAL, as specified in Section 4.1.2.2; o one or more address blocks with associated address block TLVs as specified in Section 4.1.3; these address blocks contain current or former 1-hop neighbors' MANET interface addresses with associated TLVs. Other addresses (i.e. addresses of non-neighbor nodes) MAY be added to these address blocks, however if they are then these addresses MUST NOT have associated TLVs from the address block TLVs specified in Section 4.1.3. This protocol specifies two message TLVs and three address block TLVs used in HELLO messages in Section 4.1.2 and Section 4.1.3; other TLVs Clausen, et al. Expires December 21, 2006 [Page 13] Internet-Draft MANET-NHDP June 2006 MAY be included as specified by the protocol which uses this neighborhood discovery protocol. 4.1.1. Local Interface Block The first address block, plus following TLV block, in a HELLO message is known as the Local Interface Block. The Local Interface Block is not distinguished in any way other than by being the first address block in the message. The first address of the Local Interface Block MUST contain the used address of the interface over which the HELLO message is transmitted. If that interface has an associated prefix different from the length of the address, a PREFIX_LENGTH TLV MUST be associated with this address. This first address, with associated prefix length, of the Local Interface Block is henceforth denoted the "Source Address". The Local Interface Block MUST contain all of the addresses of all of the MANET interfaces of the originating node, using the standard syntax specified in [1]. Those addresses, if any, which correspond to MANET interfaces other than that on which the HELLO message is transmitted MUST have a corresponding OTHER_IF TLV as specified in Section 4.1.3, other addresses MUST NOT use this TLV. Note that a Local Interface Block MAY include more than one address for each MANET interface, and hence a HELLO message MAY contain more than one address without an OTHER_IF TLV. A Local Interface Block MUST NOT contain any addresses which are not of MANET interfaces of the originating node. 4.1.2. Message TLVs This section specifies two message TLVs: VALIDITY_TIME and INTERVAL_TIME. 4.1.2.1. VALIDITY_TIME TLV All HELLO messages MUST include a VALIDITY_TIME TLV, specifying for how long a node may, upon receiving a message, consider the message content to be valid. The VALIDITY_TIME TLV, described in this document, contains a single value since HELLO messages are transmitted only one hop. Note that [1] specifies an extended version of this VALIDITY_TIME TLV, which is compatible with the format of the VALIDITY_TIME TLV in this specification. The VALIDITY_TIME message TLV specification is given in Table 3. Clausen, et al. Expires December 21, 2006 [Page 14] Internet-Draft MANET-NHDP June 2006 +----------------+------+-------------------+----------------------+ | Name | Type | Length | Value | +----------------+------+-------------------+----------------------+ | VALIDITY_TIME | TBD | 8 bits | | +----------------+------+-------------------+----------------------+ Table 3 where is the period for which the information is valid, represented as specified in Section 4.1.2.3. 4.1.2.2. INTERVAL_TIME TLV HELLO messages MAY include an INTERVAL_TIME message TLV, specifying the interval at which HELLO messages are being generated by the originator node. Note that HELLO messages which are not part of a regular schedule SHALL be ignored in defining the interval. If, for whatever reason, HELLO messages are sent in an irregular pattern, then this SHALL be the longest interval in that pattern. The INTERVAL_TIME message TLV specification is given in Table 4. +----------------+------+-------------------+----------------------+ | Name | Type | Length | Value | +----------------+------+-------------------+----------------------+ | INTERVAL_TIME | TBD | 8 bits |