Mobile Ad hoc Networking (MANET) T. Clausen Internet-Draft LIX, Ecole Polytechnique, France Intended status: Informational C. Dearlove Expires: October 12, 2006 BAE Systems Advanced Technology Centre J. Dean Naval Research Laboratory The OLSRv2 Design Team MANET Working Group April 10, 2006 Neighborhood Discovery for OLSRv2 draft-clausen-manet-olsrv2nd-00rc2 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 October 12, 2006. Copyright Notice Copyright (C) The Internet Society (2006). Clausen, et al. Expires October 12, 2006 [Page 1] Internet-Draft OLSRv2-ND April 2006 Abstract This document describes the neighborhood discovery protocol for the Optimized Link State Routing Protocol version 2. The protocol provides each node with local topology up to two hops distance, describing a node's 1-hop neighbors and symmetric 2-hop neighbors. This is achieved through periodic message exchange. The neighborhood discovery protocol may be used by other 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 October 12, 2006 [Page 2] Internet-Draft OLSRv2-ND April 2006 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 1.2. Applicability Statement . . . . . . . . . . . . . . . . . 5 2. Protocol Overview and Functioning . . . . . . . . . . . . . . 6 3. Neighborhood Information Base . . . . . . . . . . . . . . . . 7 3.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2. Symmetric Neighbor Set . . . . . . . . . . . . . . . . . . 8 3.3. Neighborhood Address Association Set . . . . . . . . . . . 9 3.4. 2-Hop Neighbor Set . . . . . . . . . . . . . . . . . . . . 9 4. OLSRv2 Control Message Structures . . . . . . . . . . . . . . 11 4.1. General Message TLVs . . . . . . . . . . . . . . . . . . . 11 4.1.1. VALIDITY_TIME TLV . . . . . . . . . . . . . . . . . . 11 4.1.2. INTERVAL_TIME TLV . . . . . . . . . . . . . . . . . . 12 4.2. Local Interface Blocks . . . . . . . . . . . . . . . . . . 12 4.3. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 13 4.3.1. HELLO Message: Address Blocks TLVs . . . . . . . . . . 13 5. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 14 5.1. HELLO Message: Transmission . . . . . . . . . . . . . . . 15 6. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 16 6.1. Populating the Link Set . . . . . . . . . . . . . . . . . 16 6.2. Populating the Symmetric Neighbor Set . . . . . . . . . . 17 6.3. Populating the Neighborhood Address Association Set . . . 18 6.4. Populating the 2-Hop Neighbor Set . . . . . . . . . . . . 19 6.5. Neighborhood Changes . . . . . . . . . . . . . . . . . . . 20 7. Proposed Values for Constants . . . . . . . . . . . . . . . . 21 7.1. Message Intervals . . . . . . . . . . . . . . . . . . . . 21 7.2. Holding Times . . . . . . . . . . . . . . . . . . . . . . 21 7.3. Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22 8.1. Multicast Addresses . . . . . . . . . . . . . . . . . . . 22 8.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 22 8.3. TLV Types . . . . . . . . . . . . . . . . . . . . . . . . 22 8.4. LINK_STATUS and OTHER_NEIGHB Values . . . . . . . . . . . 23 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 24 9.1. Normative References . . . . . . . . . . . . . . . . . . . 24 9.2. Informative References . . . . . . . . . . . . . . . . . . 24 Appendix A. Heuristics for Generating HELLO Messages . . . . . . 25 Appendix B. HELLO Message Example . . . . . . . . . . . . . . . . 28 Appendix C. Representing Time . . . . . . . . . . . . . . . . . . 30 Appendix D. Security Considerations . . . . . . . . . . . . . . . 31 Appendix E. Flow and Congestion Control . . . . . . . . . . . . . 33 Appendix F. Contributors . . . . . . . . . . . . . . . . . . . . 34 Appendix G. Acknowledgements . . . . . . . . . . . . . . . . . . 35 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 36 Intellectual Property and Copyright Statements . . . . . . . . . . 37 Clausen, et al. Expires October 12, 2006 [Page 3] Internet-Draft OLSRv2-ND April 2006 1. Introduction The Optimized Link State Routing Protocol version 2 (OLSRv2) [3] uses an exchange of HELLO messages in order that each node can determine its neighborhood up to two hops distant. This document is a specification of that discovery protocol. This discovery 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. This protocol may also be used by protocols other than OLSRv2 and 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 the neighborhood discovery protocol as specified in this document. MANET interface - A network device participating in a MANET and using this Neighborhood Discovery protocol. A node may have several MANET interfaces, each interface assigned one or more IP addresses. 1-hop neighbor - A node X is an 1-hop neighbor of node Y if node Y can hear node X (i.e., a link exists from a MANET interface on node X to an MANET interface on node Y). 2-hop neighbor - A node X is a 2-hop neighbor of node Y if node X is a 1-hop neighbor of a 1-hop neighbor of node Y, but is not node Y itself. 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 October 12, 2006 [Page 4] Internet-Draft OLSRv2-ND April 2006 asymmetric link - A link which is not symmetric. 1-hop neighborhood - The 1-hop neighborhood of any node X is the set of 1-hop neighbors of node X. symmetric 1-hop neighborhood - A subset of the 1-hop neighborhood, the symmetric 1-hop neighborhood of any node X is the set of nodes which have at least one symmetric link to node X. symmetric 2-hop neighborhood - The symmetric 2-hop neighborhood of node X is the set of nodes, excluding node X itself, which have a symmetric link to the symmetric 1-hop neighborhood of X. (This may include nodes in the 1-hop neighborhood of 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. The protocol uses the message exchange format specified in [1]. This implies that the HELLO messages specified by this neighborhood discovery protocol may be extended by the TLV mechanisms described in [1], e.g. to signal 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]. This specification assumes that all addresses have an associated prefix length. The prefix length of an address is, in control messages, indicated using the PREFIX_LENGTH TLV from [1]. If no PREFIX_LENGTH TLV is present for a given address, it is assumed that the prefix length for that address is identical 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 various sets of this specification (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 control messages. Clausen, et al. Expires October 12, 2006 [Page 5] Internet-Draft OLSRv2-ND April 2006 2. Protocol Overview and Functioning This protocol consists of a specification of local signaling, which serves to: o discover links to adjacent MANET nodes; o perform bidirectionality check on the discovered links; o advertise neighbors and hence discover symmetric 2-hop neighbors. This signaling consists of a single type of message known as a HELLO message. HELLO messages are transmitted periodically by each node. This allows nodes to continuously track changes in their 1-hop and symmetric 2-hop neighborhoods. HELLO messages MAY, in addition to periodic transmissions, also be generated as a response to some event (e.g. if a layer 2 notification is available and indicates a change in the link to a neighbor). However a node MUST respect a minimum interval, MIN_INTERVAL between successive HELLO message transmissions. This neighborhood discovery protocol is designed to work in a completely distributed manner and does not depend on any central entity. The protocol does not require reliable transmission of HELLO messages: because each node sends HELLO messages periodically, it can sustain a reasonable loss of some HELLO messages. Such losses can occur frequently in radio networks due to collisions or other transmission problems. This protocol does not require any changes to the format of IP packets. Thus any existing IP stack can be used as is. Clausen, et al. Expires October 12, 2006 [Page 6] Internet-Draft OLSRv2-ND April 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 neighborhood of another node, Y, concurrently. If the link between node X and node Y breaks, this allows that node X is taken into consideration as a symmetric 2-hop neighbor by node Y immediately, rather than by awaiting a HELLO message exchange cycle. 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 node is or was heard; L_neighbor_iface_addr is the address of the MANET interface of the 1-hop neighbor node; L_SYM_time is the time until which the link to the 1-hop neighbor node is considered symmetric; 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. Clausen, et al. Expires October 12, 2006 [Page 7] Internet-Draft OLSRv2-ND April 2006 +-------------+-------------+-----------+ | 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 node has or had a symmetric link; N_neighbor_iface_addr is an address of the MANET interface of a 1-hop neighbor node 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; 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. Clausen, et al. Expires October 12, 2006 [Page 8] Internet-Draft OLSRv2-ND April 2006 +-------------+-----------+ | 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 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. N2_local_iface_addr is the address of the local MANET interface over which the information defining this 2-Hop Neighbor Tuple was received; Clausen, et al. Expires October 12, 2006 [Page 9] Internet-Draft OLSRv2-ND April 2006 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 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 October 12, 2006 [Page 10] Internet-Draft OLSRv2-ND April 2006 4. OLSRv2 Control Message Structures 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: HELLO message; 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 headers may be included as specified by the protocol which uses the neighborhood discovery protocol; o message header options may be used as specified by the protocol which uses this neighborhood discovery protocol; o this protocol specifies two message TLVs and three address block TLVs; other TLVs MAY be included as specified by the protocol which uses this neighborhood discovery protocol. The remainder of this section defines, within the framework of [1], TLVs specific to this neighborhood discovery protocol. 4.1. General Message TLVs This section specifies two message TLVs, VALIDITY_TIME and INTERVAL_TIME. 4.1.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 October 12, 2006 [Page 11] Internet-Draft OLSRv2-ND April 2006 VALIDITY_TIME Message TLV Specification Overview +----------------+------+-------------------+----------------------+ | Name | Type | Length | Value | +----------------+------+-------------------+----------------------+ | VALIDITY_TIME | TBD | 8 bits | | +----------------+------+-------------------+----------------------+ Table 3 where is the period for which the information is valid as specified in Appendix C. 4.1.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. The INTERVAL_TIME message TLV specification is given in Table 4. INTERVAL_TIME Message TLV Specification Overview +----------------+------+-------------------+----------------------+ | Name | Type | Length | Value | +----------------+------+-------------------+----------------------+ | INTERVAL_TIME | TBD | 8 bits |