Mobile Ad hoc Networking (MANET) T. Clausen Internet-Draft LIX, Ecole Polytechnique Intended status: Standards Track C. Dearlove Expires: January 14, 2010 BAE Systems ATC J. Dean Naval Research Laboratory The OLSRv2 Design Team MANET Working Group July 13, 2009 MANET Neighborhood Discovery Protocol (NHDP) draft-ietf-manet-nhdp-10 Status of This Memo This Internet-Draft is submitted to IETF 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. 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 January 14, 2010. Copyright Notice Clausen, et al. Expires January 14, 2010 [Page 1] Internet-Draft MANET-NHDP July 2009 Copyright (c) 2009 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 in effect on the date of publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Abstract This document describes a 1-hop and symmetric 2-hop neighborhood discovery protocol (NHDP) for mobile ad hoc networks (MANETs). Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 6 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 9 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 10 4.1. Routers and Interfaces . . . . . . . . . . . . . . . . . . 11 4.2. Information Base Overview . . . . . . . . . . . . . . . . 11 4.2.1. Local Information Base . . . . . . . . . . . . . . . . 12 4.2.2. Interface Information Bases . . . . . . . . . . . . . 12 4.2.3. Neighbor Information Base . . . . . . . . . . . . . . 13 4.3. Signaling Overview . . . . . . . . . . . . . . . . . . . . 14 4.3.1. HELLO Message Generation . . . . . . . . . . . . . . . 14 4.3.2. HELLO Message Content . . . . . . . . . . . . . . . . 15 4.3.3. HELLO Message Processing . . . . . . . . . . . . . . . 15 4.4. Link Quality . . . . . . . . . . . . . . . . . . . . . . . 16 5. Protocol Parameters and Constants . . . . . . . . . . . . . . 16 5.1. Protocol and Port Numbers . . . . . . . . . . . . . . . . 16 5.2. Multicast Address . . . . . . . . . . . . . . . . . . . . 16 5.3. Interface Parameters . . . . . . . . . . . . . . . . . . . 16 5.3.1. Message Intervals . . . . . . . . . . . . . . . . . . 17 5.3.2. Information Validity Times . . . . . . . . . . . . . . 18 5.3.3. Link Quality . . . . . . . . . . . . . . . . . . . . . 19 5.3.4. Jitter . . . . . . . . . . . . . . . . . . . . . . . . 19 5.4. Router Parameters . . . . . . . . . . . . . . . . . . . . 20 5.4.1. Information Validity Time . . . . . . . . . . . . . . 20 5.5. Parameter Change Constraints . . . . . . . . . . . . . . . 20 5.6. Constants . . . . . . . . . . . . . . . . . . . . . . . . 21 6. Local Information Base . . . . . . . . . . . . . . . . . . . . 21 6.1. Local Interface Set . . . . . . . . . . . . . . . . . . . 22 6.2. Removed Interface Address Set . . . . . . . . . . . . . . 22 7. Interface Information Base . . . . . . . . . . . . . . . . . . 23 7.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . . . 23 Clausen, et al. Expires January 14, 2010 [Page 2] Internet-Draft MANET-NHDP July 2009 7.2. 2-Hop Set . . . . . . . . . . . . . . . . . . . . . . . . 24 8. Neighbor Information Base . . . . . . . . . . . . . . . . . . 25 8.1. Neighbor Set . . . . . . . . . . . . . . . . . . . . . . . 25 8.2. Lost Neighbor Set . . . . . . . . . . . . . . . . . . . . 25 9. Local Information Base Changes . . . . . . . . . . . . . . . . 26 9.1. Adding an Interface . . . . . . . . . . . . . . . . . . . 26 9.2. Removing an Interface . . . . . . . . . . . . . . . . . . 26 9.3. Adding an Address to an Interface . . . . . . . . . . . . 27 9.4. Removing an Address from an Interface . . . . . . . . . . 28 10. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 28 10.1. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 29 10.1.1. Address Blocks . . . . . . . . . . . . . . . . . . . . 29 11. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 31 11.1. HELLO Message Specification . . . . . . . . . . . . . . . 31 11.2. HELLO Message Transmission . . . . . . . . . . . . . . . . 33 11.2.1. HELLO Message Jitter . . . . . . . . . . . . . . . . . 33 12. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 34 12.1. Invalid Message . . . . . . . . . . . . . . . . . . . . . 34 12.2. Definitions . . . . . . . . . . . . . . . . . . . . . . . 35 12.3. Updating the Neighbor Set . . . . . . . . . . . . . . . . 36 12.4. Updating the Lost Neighbor Set . . . . . . . . . . . . . . 37 12.5. Updating the Link Set . . . . . . . . . . . . . . . . . . 37 12.6. Updating the 2-Hop Set . . . . . . . . . . . . . . . . . . 39 13. Other Information Base Changes . . . . . . . . . . . . . . . . 40 13.1. Link Tuple Symmetric . . . . . . . . . . . . . . . . . . . 41 13.2. Link Tuple Not Symmetric . . . . . . . . . . . . . . . . . 42 13.3. Link Tuple Heard Timeout . . . . . . . . . . . . . . . . . 43 14. Link Quality . . . . . . . . . . . . . . . . . . . . . . . . . 43 14.1. Deployment Without Link Quality . . . . . . . . . . . . . 43 14.2. Basic Principles of Link Quality . . . . . . . . . . . . . 44 14.3. When Link Quality Changes . . . . . . . . . . . . . . . . 45 14.4. Updating Link Quality . . . . . . . . . . . . . . . . . . 45 15. Proposed Values for Parameters and Constants . . . . . . . . . 46 15.1. Message Interval Interface Parameters . . . . . . . . . . 46 15.2. Information Validity Time Interface Parameters . . . . . . 46 15.3. Information Validity Time Router Parameters . . . . . . . 46 15.4. Link Quality Interface Parameters . . . . . . . . . . . . 46 15.5. Jitter Interface Parameters . . . . . . . . . . . . . . . 47 15.6. Constants . . . . . . . . . . . . . . . . . . . . . . . . 47 16. Usage with Other Protocols . . . . . . . . . . . . . . . . . . 47 17. Security Considerations . . . . . . . . . . . . . . . . . . . 48 17.1. Invalid HELLO messages . . . . . . . . . . . . . . . . . . 49 17.2. Authentication, Integrity and Confidentiality Suggestions . . . . . . . . . . . . . . . . . . . . . . . 50 18. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 51 18.1. Expert Review: Evaluation Guidelines . . . . . . . . . . . 51 18.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 51 18.3. Message-Type-specific TLV Type Registries . . . . . . . . 51 Clausen, et al. Expires January 14, 2010 [Page 3] Internet-Draft MANET-NHDP July 2009 18.4. Address Block TLV Types . . . . . . . . . . . . . . . . . 52 18.5. LOCAL_IF, LINK_STATUS and OTHER_NEIGHB Values . . . . . . 53 19. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 53 20. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 54 21. References . . . . . . . . . . . . . . . . . . . . . . . . . . 54 21.1. Normative References . . . . . . . . . . . . . . . . . . . 54 21.2. Informative References . . . . . . . . . . . . . . . . . . 54 Appendix A. Address Block TLV Combinations . . . . . . . . . . . 55 Appendix B. Constraints . . . . . . . . . . . . . . . . . . . . . 56 Appendix C. HELLO Message Example . . . . . . . . . . . . . . . . 58 Appendix D. Flow and Congestion Control . . . . . . . . . . . . . 61 Appendix E. Interval and Timer Illustrations . . . . . . . . . . 62 E.1. HELLO Message Generation Timing . . . . . . . . . . . . . 62 E.2. HELLO Message Processing Timing . . . . . . . . . . . . . 68 E.3. Other HELLO Message Timing . . . . . . . . . . . . . . . . 69 Appendix F. Topology Pictures . . . . . . . . . . . . . . . . . . 71 F.1. Example 1: Standard Single Interface Topology . . . . . . 71 F.2. Example 2: Dual Addressed Interface on One Hop Neighbor . 72 F.3. Example 3: Dual Addressed Interface on Two Hop Neighbor . 73 F.4. Example 4: Dual Addressed Interfaces . . . . . . . . . . . 73 F.5. Example 5: Dual Interface on Two Hop Neighbor . . . . . . 74 F.6. Example 6: Dual interface on One Hop Neighbor . . . . . . 74 F.7. Example 7: Dual Interface on One and Two Hop Neighbors . . 75 F.8. Example 8: Dual Interface Locally and on One Hop Neighbor . . . . . . . . . . . . . . . . . . . . . . . . . 76 F.9. Example 9: Dual Interface on All Routers . . . . . . . . . 76 F.10. Example 10: Dual Addressed Dual Interfaces on All Routers . . . . . . . . . . . . . . . . . . . . . . . . . 77 F.11. Example 11: Single Addressed Dual Interface Locally . . . 78 Clausen, et al. Expires January 14, 2010 [Page 4] Internet-Draft MANET-NHDP July 2009 1. Introduction This document describes a neighborhood discovery protocol (NHDP) for a mobile ad hoc network (MANET) [RFC2501]. This protocol uses a local exchange of HELLO messages in order that each router can determine the presence of, and connectivity to, its 1-hop and symmetric 2-hop neighbors. Messages are defined and sent in packets according to the specification [RFC5444]. 1-hop and symmetric 2-hop neighborhood information is recorded in the form of Information Bases. These are available for use by other protocols, such as MANET routing protocols, which require information regarding the local network connectivity. This protocol is designed to maintain the information in these Information Bases even in the presence of a dynamic network topology and wireless communication channel characteristics. This protocol makes no assumptions about the underlying link layer, other than support of local broadcast or multicast for communication to 1-hop neighbor routers. Link layer information may be used if available and applicable. This protocol is based on the neighborhood discovery process contained in the Optimized Link State Routing Protocol (OLSR) [RFC3626]. 1.1. Motivation MANETs differ from more traditional wired and infrastructure based wireless networks, due to their envisioned applicability also over more challenging communication channels (e.g., wireless, lossy, broadcast channels with moderate and shared bandwidth, hidden and exposed terminals and interference from other network devices and the environment) and in more challenging topological conditions (e.g., rapid and unpredictable mobility, dynamic and non-predetermined network membership). Due to the properties of wireless transmissions, communication between two neighboring routers may not be bidirectional; even if router A is able to receive packets from router B, the converse is not guaranteed to be true. Furthermore, because of the localized nature of wireless broadcast communication, neighboring routers within the same communications channel may have different sets of neighbors. That is, when using the same communication channel, even if router A is able to exchange packets with router B and router B is able to exchange packets with router C, then this does not guarantee that router A and router C can exchange packets directly. Clausen, et al. Expires January 14, 2010 [Page 5] Internet-Draft MANET-NHDP July 2009 Each router in a MANET may use more than one communication channel. In particular, between the same pair of routers, more than one distinct communication channel may exist, each with different properties. For use by MANET routing protocols, as well as for establishing a router's neighbors, a router may also need to determine whether each communication channel with that neighbor is bidirectional. The set of neighbor routers of a given MANET router may be continuously changing, often due to router mobility or a changing physical environment in which the MANET is located. There is typically no information from lower layers which would enable an IP routing protocol to detect and, as appropriate, react to such changes. Such changes can often take place on a short timescale, such as of the order of seconds, requiring MANET routing protocols to act rapidly to ensure suitable convergence properties. MANET routing protocols, for example [RFC3626] and [RFC5449], often employ relay set reductions in order to conserve network capacity when maintaining network-wide topological information, with calculation of these reduced relay sets employing up to two hop information. The neighborhood discovery protocol specified in this document provides continued tracking of neighborhood changes, link bidirectionality, and local topological information up to two hops. Combined, this allows a MANET routing protocol access to information describing link establishment/disappearance, and provides the necessary topological information for reduced relay set selection and other purposes. 2. Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. All terms introduced in [RFC5444], including "packet", "message", "Address Block", "TLV Block" and "TLV", are to be interpreted as described there. Additionally, this document uses the following terminology: Clausen, et al. Expires January 14, 2010 [Page 6] Internet-Draft MANET-NHDP July 2009 Router - A MANET router which implements this neighborhood discovery protocol. Interface - A network device, configured and assigned one or more addresses. Address - An IPv4 or IPv6 address, as assigned to an interface. It corresponds to an address as specified in [RFC5444], and may be either an address or an address prefix. An address without a prefix length is considered to have a prefix length equal to its length (in bits). MANET interface - An interface participating in a MANET and using this neighborhood discovery protocol. A router may have several MANET interfaces. Heard - A MANET interface of router X is considered heard on a MANET interface of a router Y if the latter can receive traffic from the former. Link - A link between two MANET interfaces exists if either can be heard by the other. Symmetric link - A symmetric link between two MANET interfaces exists if both can be heard by the other. 1-hop neighbor - A router X is a 1-hop neighbor of a router Y if a MANET interface of router X is heard by a MANET interface of router Y. Symmetric 1-hop neighbor - A router X is a symmetric 1-hop neighbor of a router Y if a symmetric link exists between a MANET interface on router X and a MANET interface on router Y. 2-hop neighbor - A router X is a 2-hop neighbor of a router Y if router X is a 1-hop neighbor of a 1-hop neighbor of router Y, but is not router Y itself. Symmetric 2-hop neighbor - A router X is a symmetric 2-hop neighbor of a router Y if router X is a symmetric 1-hop neighbor of a symmetric 1-hop neighbor of router Y, but is not router Y itself. 1-hop neighborhood - The 1-hop neighborhood of a router X is the set of the 1-hop neighbors of router X. Clausen, et al. Expires January 14, 2010 [Page 7] Internet-Draft MANET-NHDP July 2009 Symmetric 1-hop neighborhood - The symmetric 1-hop neighborhood of a router X is the set of the symmetric 1-hop neighbors of router X. 2-hop neighborhood - The 2-hop neighborhood of a router X is the set of the 2-hop neighbors of router X. (This may include routers in the 1-hop neighborhood of router X.) Symmetric 2-hop neighborhood - The symmetric 2-hop neighborhood of a router X is the set of the symmetric 2-hop neighbors of router X. (This may include routers in the 1-hop neighborhood, or even in the symmetric 1-hop neighborhood, of router X.) Constant - A numerical value which MUST be the same for all MANET interfaces of all routers in the MANET, at all times. Interface parameter - A boolean or numerical value, specified separately for each MANET interface of each router. A router MAY change interface parameter values at any time, subject to some constraints. Router parameter - A boolean or numerical value, specified for each router, and not specific to an interface. A router MAY change router parameter values at any time, subject to some constraints. Information Base - A collection of information maintained by this protocol, and which is to be made available to MANET routing protocols. An Information Base may be associated with a MANET interface, or with a router. Furthermore, this document uses the following notational conventions: X contains y, or y is contained in X, is an unordered list membership operator, returning true if the unordered list X includes the element y, and returning false otherwise. X contains Y, or Y is contained in X, is an unordered list inclusion operator, returning true if the unordered list X contains all elements y which are contained in Y, and returning false otherwise. a := b is an assignment operator, whereby the left side (a) is assigned the value of the right side (b). a and b may be values, addresses, or unordered lists (they must be of the same type). c = d is a comparison operator, returning true if the value of the left side (c) is equal to the value of the right side (d). c and d may be values, addresses, or unordered lists (they must be of the same type). If c and d are unordered lists, then they are Clausen, et al. Expires January 14, 2010 [Page 8] Internet-Draft MANET-NHDP July 2009 considered to be equal if they contain the same set of elements, regardless of the order in which they are recorded in either list (in which case c is contains d, and d contains c). If c and d are addresses, they are considered equal only if their prefix lengths are also equal. e != f is a comparison operator, returning true where (e = f) would have returned false, and returning false where (e = f) would have returned true. 3. Applicability Statement This protocol: o Is applicable to networks, especially wireless networks, in which unknown neighbors can be reached by local broadcast or multicast packets. o Is designed to work in networks with a dynamic topology, and in which messages may be lost, such as due to collisions in wireless networks. o Supports routers that each have one or more participating MANET interfaces. The set of a router's interfaces may change over time. Each interface may have one or more interface addresses, and these may also be dynamically changing. o Provides each router with current local topology information up to two hops away, and makes this local topology information available to MANET routing protocols in Information Bases. o Uses the packet and message formats specified in [RFC5444]. This includes the definition of a HELLO Message Type, used for signaling local topology information. o Allows "external" and "internal" extensibility as enabled by [RFC5444]. o May interact with, and be extended by, other protocols, such as MANET routing protocols, see Section 16. o Can use relevant link layer information if it is available. o Is designed to work in a completely distributed manner, and does not depend on any central entity. Clausen, et al. Expires January 14, 2010 [Page 9] Internet-Draft MANET-NHDP July 2009 4. Protocol Overview and Functioning The objective of this protocol is, for each router: o To identify 1-hop neighbors and symmetric 1-hop neighbors of this router. o To find the interface addresses of the router's symmetric 2-hop neighbors. o To record this information in Information Bases that can be used by other protocols, which extend this neighborhood discovery protocol. These objectives are achieved using local (1-hop) signaling that: o Advertises the presence of a router and its interface addresses. o Discovers links from neighboring routers. o Performs bidirectionality checks on the discovered links. o Advertises discovered links, and whether each is symmetric, to its 1-hop neighbors, and hence discovers symmetric 2-hop neighbors. This specification defines, in turn: o Parameters and constants used by the protocol. Parameters used by this protocol may, where appropriate, be specific to a given MANET interface, or to a MANET router. This protocol allows all parameters to be changed dynamically, and to be set independently for each MANET router or MANET interface, as appropriate. o The Information Bases describing local interfaces, discovered links and their status, current and former 1-hop neighbors, and symmetric 2-hop neighbors. o The format of the HELLO message that is used for local signaling. o The generation of HELLO messages from some of the information in the Information Bases. o The updating of the Information Bases according to received HELLO messages and other events. o The response to other events, such as the expiration of information in the Information Bases. Clausen, et al. Expires January 14, 2010 [Page 10] Internet-Draft MANET-NHDP July 2009 4.1. Routers and Interfaces In order for a router to participate in a MANET, it MUST have at least one, and possibly more, MANET interfaces. Each MANET interface: o Is configured with one or more addresses. These addresses MUST be unique at least within the router's 2-hop neighborhood. o Has a set of interface parameters, defining the behavior of this MANET interface. Each MANET interface MAY be individually parameterized. o Has an Interface Information Base, recording information regarding links to this MANET interface and symmetric 2-hop neighbors which can be reached through such links. o Generates and processes HELLO messages. In addition to a set of MANET interfaces as described above, each router has: o A Local Information Base, containing the addresses of the interfaces (MANET and non-MANET) of this router. The contents of this Information Base are not changed by signaling. o A Neighbor Information Base, recording information regarding current and recently lost 1-hop neighbors of this router. A router may have both MANET interfaces and non-MANET interfaces. Interfaces of both of these types are recorded in a router's Local Information Base, which is used, but not updated, by the signaling of this protocol. 4.2. Information Base Overview Each router maintains the Information Bases described in the following sections. These are used for describing the protocol in this document. An implementation of this protocol MAY maintain this information in the indicated form, or in any other organization which offers access to this information. In particular, note that it is not necessary to remove Tuples from Sets at the exact time indicated, only to behave as if the Tuples were removed at that time. Information in the Local Information Base is defined locally, and included in HELLO messages. Information in the Interface Information Base and the Neighbor Information Base is determined from received HELLO messages; some of this information may also be included in Clausen, et al. Expires January 14, 2010 [Page 11] Internet-Draft MANET-NHDP July 2009 transmitted HELLO messages. Such information has a limited duration in which it is considered valid, this is determined from the VALIDITY_TIME TLV in the HELLO message in which the information is received, which in turn is set by the router which originated the HELLO message, using its corresponding interface parameter H_HOLD_TIME. Appendix E illustrates the relationship between message reception, included VALIDITY_TIME TLVs, and the duration for which information received in a HELLO message is considered valid. Appendix F illustrates some example two hop topologies and how they correspond to information in the Information Bases. 4.2.1. Local Information Base Each router maintains a Local Information Base, which contains the router's local configuration information, specifically: o The Local Interface Set, which consists of Local Interface Tuples, each of which represents an interface (MANET or non-MANET) of the router. o The Removed Interface Address Set, which consists of Removed Interface Address Tuples, each of which records a recently used address of an interface (MANET or non-MANET) of the router. The Local Interface Set is used for generating HELLO messages, specifically for determining which interface addresses are to be included and identified as local interfaces. The Removed Interface Address Set is used to avoid incorrectly recording a formerly used address as a symmetric 2-hop neighbor's address. The Local Information Base is used for generating signaling, but is not itself updated by signaling specified in this document. Updates to the Local Information Base are due to changes of the router configuration, and may be allowed to trigger signaling. 4.2.2. Interface Information Bases Each router maintains, for each of its MANET interfaces, an Interface Information Base, which contains 1-hop neighborhood and symmetric 2-hop neighborhood information collected from this MANET interface, specifically: o A Link Set, which records information about current and recently lost links between this MANET interface and MANET interfaces of 1-hop neighbors. The Link Set consists of Link Tuples, each of which contains information about a single link. Link quality Clausen, et al. Expires January 14, 2010 [Page 12] Internet-Draft MANET-NHDP July 2009 information (see Section 14), when used, is recorded in Link Tuples. o A 2-Hop Set, which records the existence of symmetric links between symmetric 1-hop neighbors of this MANET interface and other routers (symmetric 2-hop neighbors). The 2-Hop Set consists of 2-Hop Tuples, each of which records an address of a symmetric 2-hop neighbor, and all addresses of the corresponding symmetric 1-hop neighbor. The Link Set for a MANET interface is used for generating HELLO messages. Specifically, the Link Set information is included to both allow other routers to identify symmetric links and to populate the 2-Hop Set. Recently lost links are recorded in the Link Set for a MANET interface so that they can be advertised in HELLO messages, accelerating their removal from relevant 1-hop neighbors' Link Sets. The Link Set for a MANET interface is itself updated on receiving a HELLO message, including recording symmetric links as indicated above. The 2-Hop Set for a MANET interface is updated as indicated above, and is not itself used in generating HELLO messages. 4.2.3. Neighbor Information Base Each router maintains a Neighbor Information Base, which contains collected information about current and recently lost 1-hop neighbors, specifically: o The Neighbor Set consists of Neighbor Tuples, each of which records all addresses of a single 1-hop neighbor. Neighbor Tuples are maintained as long as there are corresponding Link Tuples. o The Lost Neighbor Set consists of Lost Neighbor Tuples, each of which records an address of a recently lost symmetric 1-hop neighbor. The Neighbor Set associates all addresses of each 1-hop neighbor. These addresses may be included when generating a HELLO message, so that other symmetric 1-hop neighbors can record this information in a 2-Hop Set. The Neighbor Set can be updated on receiving a HELLO message. The Lost Neighbor Set is used to determine which addresses are to be included in a HELLO message as being lost (of a recently symmetric 1-hop neighbor). The Lost Neighbor Set can itself be updated on receiving a HELLO message. Clausen, et al. Expires January 14, 2010 [Page 13] Internet-Draft MANET-NHDP July 2009 4.3. Signaling Overview This protocol contains a signaling mechanism for maintaining the Interface Information Bases and the Neighbor Information Base. If information from the link layer, or any other source, is available and appropriate, it may also be used to update these Information Bases. Such updates are subject to the constraints specified in Appendix B. Signaling consists of a single type of message, known as a HELLO message. Each router generates HELLO messages on each of its MANET interfaces. HELLO messages are generated independently on each MANET interface of a MANET router; the content of a given HELLO message depends on the MANET interface for which it has been generated. Each HELLO message identifies the MANET interface for which it is generated and transmitted; this allows recipients to identify that MANET interface. Each HELLO message also reports the other interfaces (MANET and non-MANET) of the router; this allows recipients to associate a set of addresses with a single 1-hop neighbor. Each HELLO message also includes 1-hop neighbor information from the Information Bases; this allows detection of local symmetric links, and symmetric 2-hop neighbors. HELLO message generation, and the validity of the information recorded as a consequence of processing a HELLO message, is affected by timers and validity information included in HELLO messages through TLVs. The relationship between message timers and intervals is illustrated in Appendix E. 4.3.1. HELLO Message Generation HELLO messages are generated by a router for each of its MANET interfaces, and MAY be sent: o Proactively, at a regular interval, known as HELLO_INTERVAL. HELLO_INTERVAL may be fixed, or may be dynamic. For example HELLO_INTERVAL may be backed off due to congestion or network stability. o As a response to a change in the router itself, or its 1-hop neighborhood, for example on first becoming active or in response to a new, lost, or changed status link. o In a combination of these proactive and responsive mechanisms. Jittering of HELLO message generation and transmission, as described in Section 11.2, SHOULD be used if appropriate. Clausen, et al. Expires January 14, 2010 [Page 14] Internet-Draft MANET-NHDP July 2009 HELLO messages MAY be scheduled independently for each MANET interface, or, interface parameters permitting, using the same schedule for all MANET interfaces of a router. 4.3.2. HELLO Message Content The content of a HELLO message MUST satisfy the following: o A HELLO message MUST contain all of the addresses in the Local Interface Set of the router to which the MANET interface belongs. o For each MANET interface, within every time interval equal to the corresponding REFRESH_INTERVAL, the HELLO messages sent MUST collectively include all of the relevant information in the corresponding Link Set and the Neighbor Information Base. Note that when determining whether to include information in a HELLO message, the sender MUST consider all times up to the latest time when it may send its next HELLO message on this MANET interface. o A HELLO message MUST include exactly one VALIDITY_TIME Message TLV, as specified in [RFC5497], that indicates the length of time for which the message content is to be considered valid, and is therefore to be included in the receiving router's Interface Information Base. o A periodically generated HELLO message SHOULD include exactly one INTERVAL_TIME Message TLV, as specified in [RFC5497], that indicates the current value of HELLO_INTERVAL for that MANET interface, i.e. the period within which a further HELLO message is guaranteed to be sent on that MANET interface. 4.3.3. HELLO Message Processing HELLO messages received by a router are used to update the Interface Information Base for the MANET interface on which that HELLO message is received and the Neighbor Information Base. Specifically: o The router ensures that there is a single Neighbor Tuple corresponding to the originator of that HELLO message. o The router ensures that there is a Link Tuple, with appropriate status (heard or symmetric) and advertised duration, corresponding to the link between the MANET interfaces on which that HELLO message was sent and received. One or more Lost Neighbor Tuples may be created if the HELLO message reports that the link was lost. Clausen, et al. Expires January 14, 2010 [Page 15] Internet-Draft MANET-NHDP July 2009 o If the link between the MANET interfaces on which the HELLO message was sent and received is symmetric, then the router ensures that there are the appropriate 2-Hop Tuples, with advertised duration. The processing defined in this specification handles any unexpected and erroneous information in a HELLO message, maintaining the constraints on Information Base contents specified in Appendix B. 4.4. Link Quality Some links in a MANET may be marginal, e.g., due to adverse wireless propagation. In order to avoid using such marginal links, a link quality value is recorded in each Link Tuple. A MANET router considers links for which an insufficient link quality is recorded as lost. Modifying the recorded link quality in a Link Tuple is OPTIONAL. If link quality is not to be modified it MUST be set to indicate an always usable quality link. Link quality information is only used locally and is not used in signaling. Routers may interoperate whether they are using the same, different, or no, link quality information. Link quality information is thus not equivalent to a link metric. 5. Protocol Parameters and Constants The parameters and constants used in this specification are described in this section. 5.1. Protocol and Port Numbers This protocol specifies HELLO messages, which are included in packets as defined by [RFC5444]. These packets may be sent either using the "manet" protocol number or the "manet" well-known UDP port number, as specified in [RFC5498]. 5.2. Multicast Address This protocol specifies HELLO messages, which are included in packets as defined by [RFC5444]. These packets may be locally transmitted using the link local multicast address "LL-MANET-Routers", as specified in [RFC5498]. 5.3. Interface Parameters The interface parameters used by this specification may be classified into the following four categories: Clausen, et al. Expires January 14, 2010 [Page 16] Internet-Draft MANET-NHDP July 2009 o Message intervals o Information validity times o Link quality o Jitter These are detailed in the following sections. Different MANET interfaces (on the same or on different routers) MAY employ different interface parameter values, and MAY change their interface parameter values dynamically, subject to the constraints given in this section. A particular case is where all MANET interfaces on all MANET routers within a given MANET employ the same set of interface parameter values. 5.3.1. Message Intervals HELLO messages serve two principal functions: o To advertise this router's interface addresses to its 1-hop neighbors. The frequency of these advertisements is regulated by the interface parameters HELLO_INTERVAL and HELLO_MIN_INTERVAL. o To advertise this router's knowledge of each of its 1-hop neighbors. The frequency of the advertisement of each such neighbor is regulated by the interface parameter REFRESH_INTERVAL. Specifically, these parameters are as follows: HELLO_INTERVAL - is the maximum time between the transmission of two successive HELLO messages on this MANET interface. If using periodic transmission of HELLO messages, these SHOULD be at a separation of HELLO_INTERVAL, possibly modified by jitter as specified in [RFC5148]. HELLO_MIN_INTERVAL - is the minimum interval between transmission of two successive HELLO messages, on this MANET interface. (This minimum interval MAY be modified by jitter, as defined in [RFC5148].) REFRESH_INTERVAL - is the maximum interval between advertisements in a HELLO message of each 1-hop neighbor address and its status. In all intervals of length REFRESH_INTERVAL, a router MUST include each 1-hop neighbor address and its status in at least one HELLO message on this MANET interface. (This may be in the same or in different HELLO messages.) Clausen, et al. Expires January 14, 2010 [Page 17] Internet-Draft MANET-NHDP July 2009 The following constraints apply to these interface parameters: o HELLO_INTERVAL > 0 o HELLO_MIN_INTERVAL >= 0 o HELLO_INTERVAL >= HELLO_MIN_INTERVAL o REFRESH_INTERVAL >= HELLO_INTERVAL o If an INTERVAL_TIME Message TLV as defined in [RFC5497] is included in a HELLO messages, then HELLO_INTERVAL MUST be representable as described in [RFC5497]. If REFRESH_INTERVAL > HELLO_INTERVAL, then a router may distribute its neighbor advertisements between HELLO messages in any manner, subject to the constraints above. For a router to employ this protocol in a purely responsive manner on a MANET interface, REFRESH_INTERVAL and HELLO_INTERVAL SHOULD both be set to a value such that a responsive HELLO message is always expected in a shorter period than this value. If a router has more than one MANET interface, then, even if the router configures different values of HELLO_INTERVAL on each MANET interface, the router SHOULD configure the same value of HELLO_MIN_INTERVAL on all MANET interfaces on which responsive HELLO messages may be sent. 5.3.2. Information Validity Times The following interface parameters manage the validity time of link information: L_HOLD_TIME - is the period of advertisement, on this MANET interface, of former 1-hop neighbor addresses as lost in HELLO messages, allowing recipients of these HELLO messages to accelerate removal of this information from their Link Sets. L_HOLD_TIME MAY be set to zero, if accelerated information removal is not required. H_HOLD_TIME - is used as the Value in the VALIDITY_TIME Message TLV included in all HELLO messages on this MANET interface. It is then used by each router receiving such a HELLO message to indicate the validity of the information taken from that HELLO message and recorded in the receiving router's Information Bases. The following constraints apply to these interface parameters: Clausen, et al. Expires January 14, 2010 [Page 18] Internet-Draft MANET-NHDP July 2009 o L_HOLD_TIME >= 0 o H_HOLD_TIME >= REFRESH_INTERVAL o If HELLO messages can be lost then both parameters SHOULD be significantly greater than REFRESH_INTERVAL. o H_HOLD_TIME MUST be representable as described in [RFC5497]. 5.3.3. Link Quality The following interface parameters manage the usage of link quality (see Section 14): HYST_ACCEPT - is the link quality threshold at or above which a link becomes usable, if it was not already so. HYST_REJECT - is the link quality threshold below which a link becomes unusable, if it was not already so. INITIAL_QUALITY - is the initial quality of a newly identified link. INITIAL_PENDING - if true, then a newly identified link is considered pending, and is not usable until the link quality has reached or exceeded the HYST_ACCEPT threshold. The following constraints apply to these interface parameters: o 0 <= HYST_REJECT <= HYST_ACCEPT <= 1 o 0 <= INITIAL_QUALITY <= 1. o If link quality is not updated, then INITIAL_QUALITY >= HYST_ACCEPT. o If INITIAL_QUALITY >= HYST_ACCEPT, then INITIAL_PENDING := false. o If INITIAL_QUALITY < HYST_REJECT, then INITIAL_PENDING := true. 5.3.4. Jitter If jitter, as defined in [RFC5148], is used then these parameters are as follows: HP_MAXJITTER - represents the value of MAXJITTER used in [RFC5148] for periodically generated HELLO messages on this MANET interface. Clausen, et al. Expires January 14, 2010 [Page 19] Internet-Draft MANET-NHDP July 2009 HT_MAXJITTER - represents the value of MAXJITTER used in [RFC5148] for externally triggered HELLO messages on this MANET interface. For constraints on these interface parameters see [RFC5148]. 5.4. Router Parameters The two router parameters defined by this specification are in the category of information validity time. 5.4.1. Information Validity Time The following router parameter manages the validity time of lost symmetric 1-hop neighbor information: N_HOLD_TIME - is used as the period during which former 1-hop neighbor addresses are advertised as lost in HELLO messages, allowing recipients of these HELLO messages to accelerate removal of this information from their 2-Hop Sets. N_HOLD_TIME MAY be set to zero, if accelerated information removal is not required. I_HOLD_TIME - is the period for which a recently used local interface address is recorded. The following constraints applies to these router parameters: o N_HOLD_TIME >= 0 o I_HOLD_TIME >= 0 5.5. Parameter Change Constraints If protocol parameters are changed dynamically, the constraints in this section apply. HELLO_INTERVAL * If the HELLO_INTERVAL for a MANET interface increases, then the next HELLO message on this MANET interface MUST be generated according to the previous, shorter, HELLO_INTERVAL. A number of subsequent HELLO messages MAY be generated according to the previous, shorter, HELLO_INTERVAL (but MUST include times according to current parameters). * If the HELLO_INTERVAL for a MANET interface decreases, then the following HELLO messages on this MANET interface MUST be generated according to this current, shorter, HELLO_INTERVAL. Clausen, et al. Expires January 14, 2010 [Page 20] Internet-Draft MANET-NHDP July 2009 REFRESH_INTERVAL * If the REFRESH_INTERVAL for a MANET interface increases, then the content of subsequent HELLO messages must be organized such that the specification of the old value of REFRESH_INTERVAL is satisfied for a further period equal to the old value of REFRESH_INTERVAL. * If the REFRESH_INTERVAL for a MANET interface decreases, then it MAY be necessary to reschedule HELLO message generation on that MANET interface, in order that the specification of REFRESH_INTERVAL is satisfied from the time of change. HYST_ACCEPT and HYST_REJECT * If HYST_ACCEPT or HYST_REJECT changes, then the appropriate actions for link quality change, as specified in Section 14.3, MUST be taken. L_HOLD_TIME * If L_HOLD_TIME changes, then L_time for all relevant Link Tuples MUST be changed. N_HOLD_TIME * If N_HOLD_TIME changes, then NL_time for all relevant Lost Neighbor Tuples MUST be changed. HP_MAXJITTER * If HP_MAXJITTER changes, then the periodic HELLO message schedule on this MANET interface MAY be changed. HT_MAXJITTER * If HT_MAXJITTER changes, then externally triggered HELLO messages on this MANET interface MAY be rescheduled. 5.6. Constants The constant C (time granularity) is used as specified in [RFC5497]. 6. Local Information Base A router maintains a Local Information Base that records information about its interfaces (MANET and non-MANET). Each interface MUST have at least one address, and MAY have more than one address. Clausen, et al. Expires January 14, 2010 [Page 21] Internet-Draft MANET-NHDP July 2009 The Local Information Base is not modified by signaling. If a router's interface configuration changes, then the Local Information Base MUST reflect these changes. This MAY also result in signaling to advertise these changes. Interfaces and addresses MAY be excluded from the Local Information Base, and hence from HELLO messages, if they are not to be used for routing. 6.1. Local Interface Set A router's Local Interface Set records its local interfaces. It consists of Local Interface Tuples, one per interface: (I_local_iface_addr_list, I_manet) where: I_local_iface_addr_list is an unordered list of the addresses of this interface. I_manet is a boolean flag, describing if this interface is a MANET interface. Local Interface Tuples are removed from the Local Interface Set only when the routers' interface configuration changes, subject to Section 9, i.e. they are not subject to timer-based expiration. 6.2. Removed Interface Address Set A router's Removed Interface Address Set records addresses which were recently used as local interface addresses. If a router's interface addresses are immutable then the Removed Interface Address Set is always empty and MAY be omitted. It consists of Removed Interface Address Tuples, one per address: (IR_local_iface_addr, IR_time) where: IR_local_iface_addr is a recently used address of an interface of this router. IR_time specifies when this Tuple expires and MUST be removed. Clausen, et al. Expires January 14, 2010 [Page 22] Internet-Draft MANET-NHDP July 2009 7. Interface Information Base A router maintains an Interface Information Base for each of its MANET interfaces. This records information about links to that MANET interface and symmetric 2-hop neighbors which can be reached in two hops using those links as the first hop. The Interface Information Base includes the Link Set and the 2-Hop Set. An address of a symmetric 2-hop neighbor can also be present as the address of a 1-hop neighbor. This allows the router using this address to be immediately considered as a symmetric 2-hop neighbor if it fails to be a symmetric 1-hop neighbor. An element which specifies a time is considered expired if the current time is greater than or equal to that time. One such element, present in most Tuples, indicates when expired that the Tuple itself is considered expired and MUST be removed. Tuples which do not have such a time element are removed at other times as specified, for example a Neighbor Tuple is removed when all corresponding Link Tuples have been removed. 7.1. Link Set A router's Link Set records links from other routers which are, or recently were, 1-hop neighbors. It consists of Link Tuples, each representing a single link: (L_neighbor_iface_addr_list, L_HEARD_time, L_SYM_time, L_quality, L_pending, L_lost, L_time) where: L_neighbor_iface_addr_list is an unordered list of the addresses of the MANET interface of the 1-hop neighbor; L_HEARD_time is the time until which the MANET interface of the 1-hop neighbor would be considered heard if not considering link quality; L_SYM_time is the time until which the link to the 1-hop neighbor would be considered symmetric if not considering link quality; L_quality is a dimensionless number between 0 (inclusive) and 1 (inclusive) describing the quality of a link; a greater value of L_quality indicating a higher quality link; Clausen, et al. Expires January 14, 2010 [Page 23] Internet-Draft MANET-NHDP July 2009 L_pending is a boolean flag, describing if a link is considered pending (i.e. a candidate, but not yet established, link); L_lost is a boolean flag, describing if a link is considered lost due to low link quality; L_time specifies when this Tuple expires and MUST be removed. The status of the link, as obtained through HELLO message exchange and using link quality, is denoted L_status. L_status can take the values PENDING, HEARD, SYMMETRIC and LOST. The values LOST, SYMMETRIC and HEARD are defined in Section 18.5. The value PENDING is never used in a HELLO message, it is only used locally by a router, and any value distinct from LOST, SYMMETRIC and HEARD may be used. L_status is defined by: 1. If L_pending = true, then L_status := PENDING; 2. otherwise, if L_lost = true, then L_status := LOST; 3. otherwise, if L_SYM_time is not expired, then L_status := SYMMETRIC; 4. otherwise, if L_HEARD_time is not expired, then L_status := HEARD; 5. otherwise, L_status := LOST. 7.2. 2-Hop Set A router's 2-Hop Set records addresses of symmetric 2-hop neighbors, and the symmetric links to symmetric 1-hop neighbors through which these symmetric 2-hop neighbors can be reached. It consists of 2-Hop Tuples, each representing a single address of a symmetric 2-hop neighbor, and a single MANET interface of a symmetric 1-hop neighbor. (N2_neighbor_iface_addr_list, N2_2hop_addr, N2_time) where: N2_neighbor_iface_addr_list is an unordered list of the addresses of the MANET interface of the symmetric 1-hop neighbor from which this information was received; Clausen, et al. Expires January 14, 2010 [Page 24] Internet-Draft MANET-NHDP July 2009 N2_2hop_addr is an address of a symmetric 2-hop neighbor which has a symmetric link (using any MANET interface) to the indicated symmetric 1-hop neighbor; N2_time specifies when this Tuple expires and MUST be removed. 8. Neighbor Information Base Each router maintains a Neighbor Information Base that records information about addresses of current and recently symmetric 1-hop neighbors. 8.1. Neighbor Set A router's Neighbor Set records all addresses of each 1-hop neighbor. It consists of Neighbor Tuples, each representing a single 1-hop neighbor: (N_neighbor_addr_list, N_symmetric) where: N_neighbor_addr_list is an unordered list of the addresses of a 1-hop neighbor; N_symmetric is a boolean flag, describing if this is a symmetric 1-hop neighbor. Neighbor Tuples are removed from the Neighbor Set only when corresponding Link Tuples expire from the routers' Link Set, i.e. Neighbor Tuples are not directly subject to timer-based expiration. 8.2. Lost Neighbor Set A router's Lost Neighbor Set records addresses of routers which recently were symmetric 1-hop neighbors, but are now advertised as lost. It consists of Lost Neighbor Tuples, each representing a single such address: (NL_neighbor_addr, NL_time) where: NL_neighbor_addr is an address of a router which recently was a symmetric 1-hop neighbor of this router; Clausen, et al. Expires January 14, 2010 [Page 25] Internet-Draft MANET-NHDP July 2009 NL_time specifies when this Tuple expires and MUST be removed. 9. Local Information Base Changes The Local Information Base MUST change to respond to changes in the router's local interface configuration. The router MUST update its Interface Information Base and Neighbor Information Base in response to such changes. If any changes in the Interface Information Base or the Neighbor Information Base satisfy any of the conditions described in Section 13, then those changes must be applied immediately, unless noted otherwise. A router MAY transmit HELLO messages in response to these changes. 9.1. Adding an Interface If an interface is added to the router then this is indicated by the addition of a Local Interface Tuple to the Local Interface Set. If the new interface is a MANET interface then an initially empty Interface Information Base MUST be created for this new MANET interface. The actions in Section 9.3 MUST be taken for each address of this added interface. A HELLO message MAY be sent on all MANET interfaces, it SHOULD be sent on the new interface if it is a MANET interface. If using scheduled messages, then a message schedule MUST be established on the new MANET interface. 9.2. Removing an Interface If an interface is removed from the router, then this MUST result in changes to the Local Information Base and to the Neighbor Information Base as follows: 1. Identify the Local Interface Tuple that corresponds to the interface to be removed. 2. For each address (henceforth removed address) in the I_local_iface_addr_list of that Local Interface Tuple, create a Removed Interface Address Tuple with: * IR_local_iface_addr := removed address; * IR_time := current time + I_HOLD_TIME. 3. Remove that Local Interface Tuple from the Local Interface Set. 4. If the interface to be removed is a MANET interface (i.e. with I_manet = true) then: Clausen, et al. Expires January 14, 2010 [Page 26] Internet-Draft MANET-NHDP July 2009 1. Remove the Interface Information Base for that MANET interface; 2. All Neighbor Tuples for which none of the addresses in its N_neighbor_addr_list are contained in any L_neighbor_iface_addr_list in any remaining Link Set, are removed. If the removed interface is the last MANET interface of the router, then there will be no remaining Interface Information Bases, and the router will longer participate in this protocol. After removing the interface and making these changes, a HELLO message MAY be sent on all remaining MANET interfaces. 9.3. Adding an Address to an Interface If an address is added to an interface then this is indicated by the addition of an address to the appropriate I_local_iface_addr_list. The following changes MUST be made to the Information Bases: 1. The Neighbor Tuples, if any, whose N_neighbor_addr_list contains the added address, are removed. 2. Any Link Tuples, in any Link Set, whose L_neighbor_iface_addr_list contains: * the added address; OR * any address in the N_neighbor_addr_list of any removed Neighbor Tuple are removed; apply Section 13.2, but not Section 13.3. 3. Any Lost Neighbor Tuples whose NL_neighbor_addr = the added address, are removed. 4. Any 2-Hop Tuples whose N2_2hop_addr = the added address, are removed. After adding the address and making these changes, a HELLO message MAY be sent on all MANET interfaces. These changes, other than to the appropriate I_local_iface_addr_list, are made in order to maintain consistency of the Information Bases. Specifically, these changes remove any record of any use of this address by routers in the 1-hop neighborhood or in the symmetric 2-hop neighborhood of this router. Clausen, et al. Expires January 14, 2010 [Page 27] Internet-Draft MANET-NHDP July 2009 9.4. Removing an Address from an Interface If an address (henceforth removed address) is removed from an interface then: 1. Identify the Local Interface Tuple that corresponds to the address to be removed. 2. If this is the only address of that interface (the only address in the corresponding I_local_iface_addr_list) then remove that interface as specified in Section 9.2. 3. Otherwise: 1. Remove the removed address from this I_local_iface_addr_list. 2. Create a Removed Interface Address Tuple with: + IR_local_iface_addr := removed address; + IR_time := current time + I_HOLD_TIME. After removing the address and making these changes, a HELLO message MAY be sent on all MANET interfaces. 10. Packets and Messages The packet and message format used by this protocol is defined in [RFC5444], which is used with the following considerations: o This protocol specifies one Message Type, the HELLO message. o A HELLO message MAY use any combination of Message Header options specified in [RFC5444]. o HELLO messages MUST NOT be forwarded. o HELLO messages MAY be included in multi-message packets as specified in [RFC5444]. o Received HELLO messages MUST be parsed in accordance with [RFC5444]. A HELLO message which is not in conformance with [RFC5444] MUST be discarded. A HELLO message may also be discarded for other reasons, see Section 12.1. o This protocol specifies three Address Block TLVs. It also uses two Message TLVs defined in [RFC5497]. These five TLV Types are all defined only with Type Extension = 0. TLVs of other types, Clausen, et al. Expires January 14, 2010 [Page 28] Internet-Draft MANET-NHDP July 2009 and of these types but without Type Extension = 0, are ignored by this protocol. All references in this specification to, for example, an Address Block TLV with Type = LINK_STATUS, are to be considered as referring to an Address Block TLV with Type = LINK_STATUS and Type Extension = 0. 10.1. HELLO Messages A HELLO message MUST contain: o Exactly one VALIDITY_TIME Message TLV as specified in [RFC5497], representing H_HOLD_TIME for the transmitting MANET interface. The options included in [RFC5497] for representing zero and infinite times MUST NOT be used. A HELLO message which is transmitted periodically SHOULD contain, and otherwise MAY contain: o Exactly one INTERVAL_TIME Message TLV as specified in [RFC5497], representing HELLO_INTERVAL for the transmitting MANET interface. The options included in [RFC5497] for representing zero and infinite times MUST NOT be used. A HELLO message MAY contain: o Other Message TLVs. o One or more Address Blocks, each with an associated Address Block TLV Block, which MAY contain other Address Block TLVs. 10.1.1. Address Blocks All addresses in a router's Local Interface Set (i.e. in any I_local_iface_addr_list) MUST be included in the Address Blocks in all generated HELLO messages with the following exception. If the MANET interface on which the HELLO message is to be sent has a single address with maximum prefix length (i.e. /32 for IPv4, /128 for IPv6), then that address MAY be omitted from being included in any Address Block, provided that this address is included as the sending address of the IP datagram in which the HELLO message is included. All addresses of the router's interfaces included in an Address Block MUST be associated with an Address Block TLV with Type = LOCAL_IF, as defined in Table 1. Clausen, et al. Expires January 14, 2010 [Page 29] Internet-Draft MANET-NHDP July 2009 +----------+---------+----------------------------------------------+ | Name | Value | Description | | | Length | | +----------+---------+----------------------------------------------+ | LOCAL_IF | 1 octet | Specifies that the address is an address | | | | associated with the MANET interface on which | | | | the message was sent (THIS_IF) or another | | | | interface of the sending router (OTHER_IF). | +----------+---------+----------------------------------------------+ Table 1: LOCAL_IF TLV definition Address Blocks MAY contain current or recently lost 1-hop neighbors' addresses, each of which is associated with one or both Address Block TLVs as described in Table 2. +--------------+---------+------------------------------------------+ | Name | Value | Description | | | Length | | +--------------+---------+------------------------------------------+ | LINK_STATUS | 1 octet | Specifies the status of the link from | | | | the indicated address (LOST, SYMMETRIC | | | | or HEARD). | | OTHER_NEIGHB | 1 octet | Specifies that the address is | | | | (SYMMETRIC) or was (LOST) of an | | | | interface of a symmetric 1-hop neighbor | | | | of the router transmitting the HELLO | | | | message. | +--------------+---------+------------------------------------------+ Table 2: LINK_STATUS and OTHER_NEIGHB TLV definition An Address Block TLV with Type = LINK_STATUS and Value = SYMMETRIC or Value = LOST also performs the function of an Address Block TLV with Type = OTHER_NEIGHB and the same Value. The latter SHOULD NOT also be included associated with the same address. If an Address Block TLV with Type = LINK_STATUS and Value = SYMMETRIC is combined with an Address Block TLV with Type = OTHER_NEIGHB and Value = LOST associated with the same address, then the latter MUST be ignored, and SHOULD NOT be included. See Appendix A. Other addresses MAY be included in Address Blocks, but MUST NOT be associated with any of the Address Block TLVs specified in this specification. Clausen, et al. Expires January 14, 2010 [Page 30] Internet-Draft MANET-NHDP July 2009 11. HELLO Message Generation Each MANET interface MUST generate HELLO messages according to the specification in this section. HELLO messages are generated for each MANET interface independently. HELLO message generation and scheduling MUST be according to the interface parameters for that MANET interface, and MAY be independent for each MANET interface or, interface parameters permitting, MANET interfaces MAY use the same schedule. If transmitting periodic HELLO messages then, following a HELLO message transmission on a MANET interface, another HELLO message MUST be transmitted on the same MANET interface after an interval not greater than HELLO_INTERVAL. Two successive HELLO message transmissions on the same MANET interface MUST be separated by at least HELLO_MIN_INTERVAL, except as noted in Section 11.2.1. 11.1. HELLO Message Specification HELLO messages are generated independently on each MANET interface. All addresses in any I_local_iface_addr_list MUST be included, except that: o If the interface on which the HELLO message is to be sent has a single address with maximum prefix length (i.e. /32 for IPv4, /128 for IPv6) then that address MAY be omitted, provided that this address is included as the sending address of the IP datagram in which the HELLO message is included. All such included addresses MUST be associated with an Address Block TLV with Type := LOCAL_IF and Value according to the following: o If the address is an address of the sending MANET interface, then Value := THIS_IF. o Otherwise, Value := OTHER_IF. The following addresses of current or former 1-hop neighbors MAY be included in any HELLO message, respecting the parameter REFRESH_INTERVAL for each association for that MANET interface: o Addresses of MANET interfaces of 1-hop neighbors from the Link Set of the Interface Information Base for this MANET interface (i.e. from an L_neighbor_iface_addr_list), other than those from Link Tuples with L_status = PENDING. Clausen, et al. Expires January 14, 2010 [Page 31] Internet-Draft MANET-NHDP July 2009 o Other addresses of symmetric 1-hop neighbors from the Neighbor Set of this router's Neighbor Information Base (i.e. from an N_neighbor_addr_list). o Addresses of MANET interfaces of previously symmetric or heard 1-hop neighbors connected on this MANET interface from the Link Set of the Interface Information Base for this MANET interface (i.e. from an L_neighbor_iface_addr_list with L_status = LOST). o Other addresses of previously symmetric 1-hop neighbors from the Lost Neighbor Set of this router's Neighbor Information Base (i.e. from an NL_neighbor_addr). Each such address MUST be associated with one or more appropriate Address Block TLVs. Specifically: 1. For each address (henceforth linked address) which is contained in an L_neighbor_iface_addr_list of a Link Tuple in the Link Set for this MANET interface, for which L_status != PENDING, include the linked address with an associated Address Block TLV with: * Type := LINK_STATUS; AND * Value := L_status. 2. For each address (henceforth neighbor address) which is contained in an N_neighbor_addr_list in a Neighbor Tuple with N_symmetric = true, and which has not already been included with an associated Address Block TLV with Type = LINK_STATUS and Value = SYMMETRIC, include the neighbor address with an associated Address Block TLV with: * Type := OTHER_NEIGHB; AND * Value := SYMMETRIC. 3. For each Lost Neighbor Tuple whose NL_neighbor_addr (henceforth lost address) has not already been included, include the lost address with an associated Address Block TLV with: * Type := OTHER_NEIGHB; AND * Value := LOST. If any such addresses have been added to these Information Bases since the last HELLO message was sent on this MANET interface, or if their status (as indicated by these TLVs and the Values they associate with that address) have changed since that address was last Clausen, et al. Expires January 14, 2010 [Page 32] Internet-Draft MANET-NHDP July 2009 reported on this MANET interface, then that address, and the indicated TLVs, MUST be included in the HELLO message. If an address of a 1-hop neighbor is specified with more than one associated Address Block TLV, then these Address Block TLVs MAY be independently included or excluded from each HELLO message. Each such Address Block TLV MUST be included associated with that address in a HELLO message sent on that MANET interface in every interval of length equal to that MANET interface's parameter REFRESH_INTERVAL. Address Block TLVs associated with the same address included in the same HELLO message MAY be applied to the same or different copies of that address. 11.2. HELLO Message Transmission HELLO messages are transmitted in the format specified by [RFC5444]. 11.2.1. HELLO Message Jitter HELLO messages MAY be sent using periodic message generation or externally triggered message generation. If using data link and physical layers which are subject to packet loss due to collisions, HELLO messages SHOULD be jittered as described in [RFC5148]. Internally triggered message generation (such as due to a change in local interfaces) MAY be treated as if externally generated message generation, or MAY be not jittered. HELLO messages MUST NOT be forwarded, and thus message forwarding jitter does not apply to HELLO messages. Each form of jitter described in [RFC5148] requires a parameter MAXJITTER. These interface parameters may be dynamic, and are specified by: o For periodic message generation: HP_MAXJITTER. o For externally triggered message generation: HT_MAXJITTER. When HELLO message generation is delayed in order that a HELLO message is not sent within HELLO_MIN_INTERVAL of the previous HELLO message on the same MANET interface, then HELLO_MIN_INTERVAL SHOULD be reduced by jitter, with maximum reduction HP_MAXJITTER, as described in [RFC5148]. In this case HP_MAXJITTER MUST NOT be greater than HELLO_MIN_INTERVAL. Clausen, et al. Expires January 14, 2010 [Page 33] Internet-Draft MANET-NHDP July 2009 12. HELLO Message Processing On receiving a HELLO message, a router MUST first check if the message is invalid for processing by this router, as defined in Section 12.1. Otherwise the receiving router MUST update its appropriate Interface Information Base and its Neighbor Information Base as specified in Section 12.3 to Section 12.6. These updates MUST be performed in the order in which they are presented in this specification. If any changes satisfy any of the conditions described in Section 13 then the indicated consequences in that section MUST be applied immediately, unless noted otherwise. All message processing, including determination of whether a message is invalid, considers only TLVs with Type Extension = 0. TLVs with any other type extension are ignored. All references to, for example, a TLV with Type = LINK_STATUS refer to a TLV with Type = LINK_STATUS and Type Extension = 0. 12.1. Invalid Message A received HELLO message is invalid for processing by this router if any of the following conditions are true: o The address length as specified in the Message Header is not equal to the length of the addresses used by this router. o The message has a field in its Message Header with a value other than one. (Note that the message need not have a field.) o The message has a field in its Message Header with a value other than zero. (Note that the message need not have a field.) o The message does not have a Message TLV with Type = VALIDITY_TIME in its Message TLV Block. o The message has more than one Message TLV with Type = VALIDITY_TIME in its Message TLV Block. o The message has more than one Message TLV with Type = INTERVAL_TIME in its Message TLV Block. o The message has any Address Block TLV(s) with Type = LOCAL_IF and any single Value v such that v != THIS_IF and v != OTHER_IF. o Any address (including different copies of an address, in the same or different Address Blocks) is associated with more than one Clausen, et al. Expires January 14, 2010 [Page 34] Internet-Draft MANET-NHDP July 2009 Value by one or more Address Block TLV(s) with Type = LOCAL_IF. o Any address (henceforth the local address) associated with an Address Block TLV with Type = LOCAL_IF is one of the receiving router's current or recently used addresses (i.e. the local address is contained in any I_local_iface_addr_list in the Local Interface Set or the local address = any IR_local_iface_addr in the Removed Interface Address Set). o The message has any Address Block TLV(s) with Type = LINK_STATUS with any single Value v such that v != LOST, v != SYMMETRIC, and v != HEARD. o Any address (including different copies of an address, in the same or different Address Blocks) is associated with more than one Value by one or more Address Block TLVs with Type = LINK_STATUS. o The message has any Address Block TLV(s) with Type = OTHER_NEIGHB with any single Value v such that v != LOST and v != SYMMETRIC. o Any address (including different copies of an address, in the same or different Address Blocks) is associated with more than one Value by one or more Address Block TLVs with Type = OTHER_NEIGHB. A router MAY recognize additional reasons for identifying that a message is badly formed and therefore invalid for processing. An invalid message MUST be silently discarded, without updating the router's Information Bases. 12.2. Definitions For the purpose of this section, note the following definitions: o "validity time" is calculated from the Message TLV with Type = VALIDITY_TIME of the HELLO message as specified in [RFC5497]. (Note that, as specified by Section 12.1, there must be exactly one such Message TLV in the HELLO message.) All information in the HELLO message used by this specification has the same validity time. o "Receiving Address List" is the I_local_iface_addr_list corresponding to the MANET interface on which the HELLO message was received o "Sending Address List" is the list of the addresses contained in the HELLO message with an associated Address Block TLV with Type = LOCAL_IF and Value = THIS_IF. If the Sending Address List is Clausen, et al. Expires January 14, 2010 [Page 35] Internet-Draft MANET-NHDP July 2009 otherwise empty, then the Sending Address List contains a single address (with maximum prefix length, i.e. /32 for IPv64, /128 for IPv6) equal to the sending address of the IP datagram in which the HELLO message was included. o "Neighbor Address List" is the Sending Address List, plus the addresses contained in the HELLO message with an associated Address Block TLV with Type = LOCAL_IF and Value = OTHER_IF. o EXPIRED indicates that a timer is set to a value clearly preceding the current time (e.g., current time - 1). o "Removed Address List" is a list of addresses created by this HELLO message processing which were formerly reported as local by the router originating the HELLO message, but which are not included in the Neighbor Address List. This list is initialized as empty. o "Lost Address List" is a subset of the Removed Address List containing addresses which were formerly considered as symmetric. This list is initialized as empty. 12.3. Updating the Neighbor Set On receiving a HELLO message, the router MUST update its Neighbor Set and populate the Removed Address List and Lost Address List: 1. Find all Neighbor Tuples (henceforth matching Neighbor Tuples) where: * N_neighbor_addr_list contains at least one address in the Neighbor Address List. 2. If there are no matching Neighbor Tuples, then: 1. Create a new Neighbor Tuple with: + N_neighbor_addr_list := Neighbor Address List; + N_symmetric := false. 3. If there is one matching Neighbor Tuple, then: 1. If the matching Neighbor Tuple's N_neighbor_addr_list != Neighbor Address List, then: 1. For each address (henceforth removed address) which is contained in that N_neighbor_addr_list, but is not Clausen, et al. Expires January 14, 2010 [Page 36] Internet-Draft MANET-NHDP July 2009 contained in the Neighbor Address List: 1. Add the removed address to the Removed Address List. 2. If N_symmetric = true, then add the removed address to the Lost Address List. 2. Update the matching Neighbor Tuple by: - N_neighbor_addr_list := Neighbor Address List. 4. If there are two or more matching Neighbor Tuples, then: 1. For each address (henceforth removed address) which is contained in the N_neighbor_addr_list of any of the matching Neighbor Tuples: 1. Add the removed address to the Removed Address List. 2. If N_symmetric = true, then add the removed address to the Lost Address List. 2. Replace the matching Neighbor Tuples by a single Neighbor Tuple with: + N_neighbor_addr_list := Neighbor Address List; + N_symmetric := false 12.4. Updating the Lost Neighbor Set On receiving a HELLO message, a router MUST update its Lost Neighbor Set: 1. For each address (henceforth lost address) which is contained in the Lost Address List, if no Lost Neighbor Tuple with NL_neighbor_addr = lost address exists, then add a Lost Neighbor Tuple with: * NL_neighbor_addr := lost address; * NL_time := current time + N_HOLD_TIME. 12.5. Updating the Link Set On receiving a HELLO message, a router MUST update its Link Set for the MANET interface on which the HELLO message is received: Clausen, et al. Expires January 14, 2010 [Page 37] Internet-Draft MANET-NHDP July 2009 1. Remove all addresses in the Removed Address List from the L_neighbor_iface_addr_list of all Link Tuples. 2. Remove all Link Tuples whose L_neighbor_iface_addr_list is now empty; apply Section 13.2, but not Section 13.3. 3. Find all Link Tuples (henceforth matching Link Tuples) where: * L_neighbor_iface_addr_list contains one or more addresses in the Sending Address List. 4. If there is more than one matching Link Tuple, then remove them all; apply Section 13.2, but not Section 13.3. 5. If no matching Link Tuples remain, then create a new matching Link Tuple with: * L_neighbor_iface_addr_list := empty; * L_HEARD_time := EXPIRED; * L_SYM_time := EXPIRED; * L_quality := INITIAL_QUALITY; * L_pending := INITIAL_PENDING; * L_lost := false; * L_time := current time + validity time. 6. The matching Link Tuple, existing or new, is then modified as follows: 1. If the router finds any address (henceforth receiving address) in the Receiving Address List in an Address Block in the HELLO message, then the Link Tuple is modified as follows: 1. If any receiving address in the HELLO message is associated with an Address Block TLV with Type = LINK_STATUS and with Value = HEARD or Value = SYMMETRIC then: - L_SYM_time := current time + validity time. Clausen, et al. Expires January 14, 2010 [Page 38] Internet-Draft MANET-NHDP July 2009 2. Otherwise if any receiving address in the HELLO message is associated with an Address Block TLV with Type = LINK_STATUS and Value = LOST then: 1. if L_SYM_time has not expired, then: 1. L_SYM_time := EXPIRED. 2. if L_status = HEARD or L_status = SYMMETRIC, then: * L_time := current time + L_HOLD_TIME. 2. L_neighbor_iface_addr_list := Sending Address List. 3. L_HEARD_time := max(current time + validity time, L_SYM_time). 4. If L_status = PENDING, then: + L_time := max(L_time, L_HEARD_time). 5. Otherwise if L_status = HEARD or L_status = SYMMETRIC, then: + L_time := max(L_time, L_HEARD_time + L_HOLD_TIME). 12.6. Updating the 2-Hop Set On receiving a HELLO message a router MUST update its 2-Hop Set for the MANET interface on which the HELLO message was received: 1. Remove all addresses in the Removed Address List from the N2_neighbor_iface_addr_list of all 2-Hop Tuples. 2. If the Link Tuple whose L_neighbor_iface_addr_list = Sending Address List, has L_status = SYMMETRIC then: 1. For each address (henceforth 2-hop address) in an Address Block of the HELLO message, where: + 2-hop address is not contained in the Neighbor Address List; + 2-hop address is not contained in any I_local_iface_addr_list; AND + 2-hop address != any IR_local_iface_addr Clausen, et al. Expires January 14, 2010 [Page 39] Internet-Draft MANET-NHDP July 2009 4. If 2-hop address has an associated Address Block TLV with: - Type = LINK_STATUS and Value = SYMMETRIC; OR - Type = OTHER_NEIGHB and Value = SYMMETRIC, then, if there is no 2-Hop Tuple such that: - N2_neighbor_iface_addr_list contains one or more addresses in the Sending Address List; AND - N2_2hop_addr = 2-hop address. then create a 2-Hop Neighbor Tuple with: - N2_2hop_addr := 2-hop address. This 2-Hop Tuple (existing or new) is then modified as follows: - N2_neighbor_iface_addr_list := Sending Address List; - N2_time := current time + validity time. 5. Otherwise if the 2-hop address has an Address Block TLV with: - Type = LINK_STATUS and Value = LOST or Value = HEARD; OR - Type = OTHER_NEIGHB and Value = LOST; then remove all 2-Hop Tuples with: - N2_neighbor_iface_addr_list contains one or more addresses in the Sending Address List; AND - N2_2hop_addr = 2-hop address. 13. Other Information Base Changes The Interface and Neighbor Information Bases MUST be changed when certain events occur. These events may result from HELLO message processing, or may be otherwise generated (e.g., expiry of timers or link quality changes). Events which cause changes in the Information Bases are: Clausen, et al. Expires January 14, 2010 [Page 40] Internet-Draft MANET-NHDP July 2009 o A Link Tuple's L_status changes to SYMMETRIC. In this case, the actions specified in Section 13.1 are performed. o A Link Tuple's L_status changes from SYMMETRIC, or the Link Tuple is removed. In this case, the actions specified in Section 13.2 are performed. o A Link Tuple's L_HEARD_time expires, or the Link Tuple is removed. In this case, the actions specified in Section 13.3 are performed. o Local interface address changes. In this case, the actions specified in Section 9 are performed. o Link quality changes. In this case, the actions specified in Section 14 are performed. If a Link Tuple is removed, or if L_status changes from SYMMETRIC and L_HEARD_time expires, then the actions specified in Section 13.2 MUST be performed before the actions specified in Section 13.3 are performed for that Link Tuple. A router MAY report updated information in response to any of these changes in HELLO message(s), subject to the constraints in Section 11. A router which transmits HELLO messages in response to such changes SHOULD transmit a HELLO message: o On all MANET interfaces, if the Neighbor Set changes such as to indicate the change in symmetry of any 1-hop neighbors (including addition or removal of symmetric 1-hop neighbors). o Otherwise, on all those MANET interfaces whose Link Set changes such as to indicate a change in L_status of any 1-hop neighbors (including the addition or removal of any 1-hop neighbors, other than those considered pending). 13.1. Link Tuple Symmetric If, for any Link Tuple which does not have L_status = SYMMETRIC: o L_status changes to SYMMETRIC; (this includes a newly created Link Tuple which is immediately updated such that L_status = SYMMETRIC) then: 1. For the Neighbor Tuple whose N_neighbor_addr_list contains L_neighbor_iface_addr_list, set: Clausen, et al. Expires January 14, 2010 [Page 41] Internet-Draft MANET-NHDP July 2009 * N_symmetric := true. 2. Remove all Lost Neighbor Tuples whose NL_neighbor_addr is contained in that N_neighbor_addr_list. 13.2. Link Tuple Not Symmetric If for any Link Tuple with L_status = SYMMETRIC: o L_status changes to any other value; OR o the Link Tuple is removed; then: 1. All 2-Hop Tuples for the same MANET interface with: * N2_neighbor_iface_addr_list contains one or more addresses in L_neighbor_iface_addr_list; are removed. 2. For the Neighbor Tuple whose N_neighbor_addr_list contains L_neighbor_iface_addr_list: 1. If there are no remaining Link Tuples for any MANET interface where: + L_neighbor_iface_addr_list is contained in N_neighbor_addr_list; AND + L_status = SYMMETRIC; then modify the Neighbor Tuple by: 1. N_symmetric := false. 2. For each address (henceforth neighbor address) in N_neighbor_addr_list, add a Lost Neighbor Tuple with: - NL_neighbor_addr := neighbor address; - NL_time := current time + N_HOLD_TIME. Clausen, et al. Expires January 14, 2010 [Page 42] Internet-Draft MANET-NHDP July 2009 13.3. Link Tuple Heard Timeout If, for any Link Tuple: o L_HEARD_time expires; OR o the Link Tuple is removed; then: 1. For the Neighbor Tuple whose N_neighbor_addr_list contains L_neighbor_iface_addr_list, if no Link Tuples for any MANET interface remain where: * L_neighbor_iface_addr_list is contained in N_neighbor_addr_list; AND * L_HEARD_time is not expired; then remove the Neighbor Tuple. 14. Link Quality Link quality is a mechanism whereby a router MAY take considerations other than message exchange into account for determining when a link is and is not a candidate for being considered as HEARD or SYMMETRIC. Link quality information for a link is generated (e.g., through access to signal to noise ratio, packet loss rate, or other information from the link layer) and used only locally, i.e. is not included in signaling, and routers may interoperate whether they are using the same, different, or no, link quality information. For deployments where no link quality is used, the considerations in Section 14.1 apply. For deployments where link quality is used, the general principles of link quality usage are described in Section 14.2. Section 14.3 and Section 14.4 detail link quality functioning. 14.1. Deployment Without Link Quality In order for a router to not employ link quality, the router MUST define: o INITIAL_PENDING := false; o INITIAL_QUALITY >= HYST_REJECT (there is no reason not to define INITIAL_QUALITY := 1). Clausen, et al. Expires January 14, 2010 [Page 43] Internet-Draft MANET-NHDP July 2009 14.2. Basic Principles of Link Quality To enable link quality usage, the L_quality value of a Link Tuple is used in conjunction with two thresholds, HYST_ACCEPT and HYST_REJECT, to set the flags L_pending and L_lost of that Link Tuple. Based on these flags, the link status to advertise for that Link Tuple is determined as described in Section 7.1. The use of two thresholds implements link hysteresis, whereby a link which has HYST_REJECT <= L_quality < HYST_ACCEPT may be either accepted or rejected (depending on which threshold it has most recently crossed, or, if neither, on the value of parameter INITIAL_PENDING). With appropriate values of these parameters, this prevents over-rapid changes of link status. The basic principles of link quality usage are as follows: o A router does not advertise a neighbor interface in any state until L_quality is acceptable: * If INITIAL_PENDING = true, then the link is advertised when link L_quality >= HYST_ACCEPT. * Otherwise the link is advertised when L_quality >= HYST_REJECT. A link which is not yet advertised has L_pending = true. o Once L_quality >= HYST_ACCEPT, the router sets L_pending := false, indicating that the link can be advertised. o A link for which L_pending = false is advertised until its L_quality drops below HYST_REJECT. o If a link has L_pending = false and L_quality < HYST_REJECT, the link is LOST and is advertised as such. This link is not reconsidered as a candidate HEARD or SYMMETRIC link until L_quality >= HYST_ACCEPT. o A link which has an acceptable quality may be advertised as HEARD, SYMMETRIC or LOST according to the exchange of HELLO messages. In order that these principles can all hold, a router MUST NOT define: o INITIAL_PENDING = false and INITIAL_QUALITY < HYST_REJECT; OR o INITIAL_PENDING = true and INITIAL_QUALITY >= HYST_ACCEPT. Clausen, et al. Expires January 14, 2010 [Page 44] Internet-Draft MANET-NHDP July 2009 14.3. When Link Quality Changes If L_quality for a link changes, then the following actions MUST be taken: 1. If L_quality >= HYST_ACCEPT then the corresponding Link Tuple is modified by: 1. L_pending := false; 2. L_lost := false; 3. If L_status = HEARD or L_status = SYMMETRIC, then: + L_time := max(L_time, L_HEARD_time + L_HOLD_TIME). 2. If L_status != PENDING, and L_quality < HYST_REJECT then the corresponding Link Tuple is modified by: 1. If L_lost = false, then: + L_lost := true; + L_time := min(L_time, current time + L_HOLD_TIME). Any appropriate action indicted in Section 13 MUST also be taken. If L_quality for a link is updated based on HELLO message reception, or on reception of a packet including a HELLO message, then L_quality MUST be updated prior to the HELLO message processing described in Section 12. (If the receipt of the HELLO message, or the packet containing it, creates the Link Tuple, then the Link Tuple MUST be created with the appropriately updated L_quality value, rather than with L_quality := INITIAL_QUALITY.) 14.4. Updating Link Quality A router MAY update link quality based on any information available to it. Particular cases that MAY be used include: o Information from the link layer, such as signal to noise ratio or packet acknowledgement reception and loss information. o Receipt or loss of control packets. If control packets include a sequential packet sequence number, as defined in [RFC5444], then link quality can be updated when a control packet is received, whether or not it contains a HELLO message. The link quality may then, for example, be based on whether the last N out of M control Clausen, et al. Expires January 14, 2010 [Page 45] Internet-Draft MANET-NHDP July 2009 packets on the link were received, or may use a "leaky integrator" tracking packet reception and loss. o Receipt or loss of HELLO messages. If the maximum interval between HELLO messages is known (such as by inclusion in HELLO messages of a Message TLV with Type := INTERVAL_TIME, as defined in [RFC5497]) then the loss of HELLO messages can be determined without the need to receive a later HELLO message. Note that if this case is combined with the previous case then care must be taken to avoid "double counting" a lost HELLO message in a lost packet. 15. Proposed Values for Parameters and Constants This section lists the parameters and constants used in the specification of the protocol, and proposed values of each which may be used when a single value of each is used. 15.1. Message Interval Interface Parameters o HELLO_INTERVAL := 2 seconds o HELLO_MIN_INTERVAL := HELLO_INTERVAL/4 o REFRESH_INTERVAL := HELLO_INTERVAL 15.2. Information Validity Time Interface Parameters o H_HOLD_TIME := 3 x REFRESH_INTERVAL o L_HOLD_TIME := H_HOLD_TIME 15.3. Information Validity Time Router Parameters o N_HOLD_TIME := L_HOLD_TIME o I_HOLD_TIME := N_HOLD_TIME 15.4. Link Quality Interface Parameters If link quality is changed, then parameter values will depend on the link quality process. If link quality is not changed, then: o HYST_ACCEPT := 1 o HYST_REJECT := 0 Clausen, et al. Expires January 14, 2010 [Page 46] Internet-Draft MANET-NHDP July 2009 o INITIAL_QUALITY := 1 o INITIAL_PENDING := false 15.5. Jitter Interface Parameters o HP_MAXJITTER := HELLO_INTERVAL/4 o HT_MAXJITTER := HP_MAXJITTER 15.6. Constants o C := 1/1024 second 16. Usage with Other Protocols Other protocols, such as MANET routing protocols, which use neighborhood discovery may need to interact with this protocol. This protocol is designed to permit such interactions, in particular: o Through accessing, and possibly extending, the information in the Local Information Base (Section 6), the Interface Information Base (Section 7) and the Neighbor Information Base (Section 8). These Information Bases record the interface configuration of the router, as well as the local connectivity, up to two hops away. All updates to the elements specified in this document are subject to the constraints specified in Appendix B. o Through accessing an outgoing HELLO message prior to it being transmitted over any MANET interface, and to add information (e.g., TLVs) as specified in [RFC5444]. This may, for example, be to allow a security protocol, as suggested in Section 17, to add a TLV containing a cryptographic signature to the message, or be to allow inserting relay selection information into a HELLO message by way of adding a TLV to an outgoing HELLO message prior to it being transmitted. o Through accessing an incoming HELLO message, and potentially discarding it prior to processing by this protocol. This may, for example, allow a security protocol as suggested in Section 17 to perform verification of HELLO message signatures and prevent processing of unverifiable HELLO messages by this protocol. o Through accessing an incoming HELLO message after it has been completely processed by this protocol. This may, in particular, allow a protocol which has added information, such as relay selection information by way of inclusion of appropriate TLVs, access to such information after appropriate updates have been Clausen, et al. Expires January 14, 2010 [Page 47] Internet-Draft MANET-NHDP July 2009 recorded in the Information Bases in this protocol. o Through requesting that a HELLO message be generated at a specific time. In that case, HELLO message generation MUST still respect the constraints in Appendix B. 17. Security Considerations The objective of this protocol is to allow each router in the network to acquire information describing its 1-hop neighborhood and symmetric 2-hop neighborhood. This is acquired through HELLO message exchange between neighboring routers. This information is made available through the Interface Information Bases and Neighbor Information Base, describing the router's 1-hop neighborhood and symmetric 2-hop neighborhood. Under normal circumstances, the information recorded in these Information Bases is correct, i.e. corresponds to the actual network topology, apart from any changes which have not (yet) been tracked by the HELLO message exchanges. If a router for some reason, whether malice or malfunction, transmits invalid HELLO messages, incorrect information may be recorded in other routers' Information Bases. This protocol specification does, however, prevent inconsistent information from being included in the Information Bases through the specified processing, which maintains the constraints in Appendix B. The exact consequence of information inexactness depends on the use of these Information Bases, and should be reflected in the specification of protocols which use information provided by this neighborhood discovery protocol. This section, therefore, firstly outlines the ways in which correctly formed, but still invalid, HELLO messages may appear, in Section 17.1. Injection of invalid HELLO messages into a network may be prevented by different means. If, for example, a network is deployed in a site to which access is strictly regulated, in order that physical access and proximity to the network is prevented, then further security mechanisms to protect against malicious routers injecting invalid HELLO messages may not be required. Similarly, if the link layer over which the network is formed provides appropriate confidentiality, authentication, and integrity, then this may, for a given deployment, suffice to appropriately protect against disclosure of information to an eavesdropper, and against a malicious router injecting invalid HELLO messages. In the latter case the link layer would discard frames that fail the link layer checks, without attempting to deliver such frames to IP. Finally, certain usage may Clausen, et al. Expires January 14, 2010 [Page 48] Internet-Draft MANET-NHDP July 2009 be of a nature where disruption of service is of no consequence, or at least not of sufficient consequence to warrant deployment of additional security mechanisms. A further point to stress, and which follows from the discussions above is, that it will not be the case that "one size security fits all". Different deployments may have different requirements. For example in a deployment of a low value sensor network, authentication using a simple message authentication code and shared symmetric keys may suffice, while anything beyond that may require too many computational resources to be viable. Conversely, in, for example, a community network, verifying not only that the originator of a HELLO message "has the right key" but also the precise identity of the originator may be required to be proved, and computational resources may be available to make such a requirement feasible. Section 17.2, therefore, does not specify a single "one-size-fits- all" mechanism, but rather details how the security suggestions in [RFC5444] are considered for applicability within the context of this protocol, and with the purpose of aiding deployment-specific security mechanisms to be developed. 17.1. Invalid HELLO messages A correctly formed, but still invalid, HELLO message may take any of the following forms. Note that a present or absent address in an Address Block, does not in and by itself cause a problem. It is the presence, absence, or incorrectness of associated LOCAL_IF, LINK_STATUS and OTHER_NEIGHB Address Block TLVs that causes problems. A router may provide false information about its own identity: * The HELLO message may contain addresses with an associated LOCAL_IF Address Block TLV which do not correspond to addresses of interfaces of the router transmitting the HELLO message. * The HELLO message may omit addresses, or their associated LOCAL_IF Address Block TLV, of interfaces of the router transmitting the HELLO message (other than the allowed omission of the only local interface address of the MANET interface over which the HELLO message is transmitted, if that is the case). * The HELLO message may incorrectly specify the LOCAL_IF Address Block TLV Value associated with one or more local interface addresses, indicating incorrectly whether they are associated with the MANET interface over which the HELLO message is transmitted. Clausen, et al. Expires January 14, 2010 [Page 49] Internet-Draft MANET-NHDP July 2009 A router may provide false information about the identity of other routers: * A present LINK_STATUS Address Block TLV may, incorrectly, identify an address as being of a MANET interface which is or was heard on the MANET interface over which the HELLO message is transmitted. * A consistently absent LINK_STATUS Address Block TLV may, incorrectly, fail to identify an address as being of a MANET interface which is or was heard on the MANET interface over which the HELLO message is transmitted. * A present OTHER_NEIGHB Address Block TLV may, incorrectly, identify an address as being of a router which is or was in the sending router's symmetric 1-hop neighborhood; * A consistently absent OTHER_NEIGHB Address Block TLV may, incorrectly, fail to identify an address as being of a router which is or was in the sending router's symmetric 1-hop neighborhood; * The Value of a LINK_STATUS Address Block TLV may incorrectly indicate the status (LOST, SYMMETRIC or HEARD) of the link from a 1-hop neighbor. * The Value of an OTHER_NEIGHB Address Block TLV may incorrectly indicate the status (LOST or SYMMETRIC) of a symmetric 1-hop neighbor. 17.2. Authentication, Integrity and Confidentiality Suggestions The security suggestions in [RFC5444] regarding inclusion of a cryptographic signature in a Message TLV or a Packet TLV can be applied to this protocol. Failure to verify either form of cryptographic signature should cause a HELLO message to be rejected without being processed. The following simplification of the suggestions for end-to-end authentication for integrity in [RFC5444] may be applied to HELLO messages: o As the Message Header fields and are either omitted or will always have the values 0 and 1, respectively, an end to end cryptographic signature can be calculated based on the entire HELLO message, including its unmodified Message Header. Clausen, et al. Expires January 14, 2010 [Page 50] Internet-Draft MANET-NHDP July 2009 The security mechanisms suggested in [RFC5444] with respect to confidentiality can be directly applied to this protocol. 18. IANA Considerations This specification defines one Message Type, which must be allocated from the "Message Types" repository of [RFC5444], and three Address Block TLV Types, which must be allocated from the "Address Block TLV Types" repository of [RFC5444]. 18.1. Expert Review: Evaluation Guidelines For the registries where an Expert Review is required, the designated expert SHOULD take the same general recommendations into consideration as are specified by [RFC5444]. 18.2. Message Types This specification defines one Message Type, to be allocated from the 0-223 range of the "Message Types" namespace defined in [RFC5444], as specified in Table 3. +-------+------+-----------------+ | Name | Type | Description | +-------+------+-----------------+ | HELLO | TBD1 | Local signaling | +-------+------+-----------------+ Table 3: Message Type assignment 18.3. Message-Type-specific TLV Type Registries IANA is requested to create a registry for Message-Type-specific Message TLVs for HELLO messages, in accordance with Section 6.2.1 of [RFC5444], and with initial assignments and allocation policies as specified in Table 4. +---------+-------------+-------------------+ | Type | Description | Allocation Policy | +---------+-------------+-------------------+ | 128-223 | Unassigned | Expert Review | +---------+-------------+-------------------+ Table 4: HELLO Message-Type-specific Message TLV Types IANA is requested to create a registry for Message-Type-specific Address Block TLVs for HELLO messages, in accordance with Section 6.2.1 of [RFC5444], and with initial assignments and allocation Clausen, et al. Expires January 14, 2010 [Page 51] Internet-Draft MANET-NHDP July 2009 policies as specified in Table 5. +---------+-------------+-------------------+ | Type | Description | Allocation Policy | +---------+-------------+-------------------+ | 128-223 | Unassigned | Expert Review | +---------+-------------+-------------------+ Table 5: HELLO Message-Type-specific Address Block TLV Types 18.4. Address Block TLV Types This specification defines three Address Block TLV Types, which must be allocated from the "Address Block TLV Types" namespace defined in [RFC5444]. IANA are requested to make allocations in the 0-127 range for these types. This will create three new type extension registries with assignments as specified in Table 6, Table 7 and Table 8. Specifications of these Address Block TLVs are in Section 10.1.1, with Value Constants defined in Section 18.5. +------------+------+-----------+-----------------------------------+ | Name | Type | Type | Description | | | | extension | | +------------+------+-----------+-----------------------------------+ | LOCAL_IF | TBD2 | 0 | Specifies that the address is | | | | | associated with a local interface | | | | | of the sending router | | Unassigned | TBD2 | 1-255 | Expert Review | +------------+------+-----------+-----------------------------------+ Table 6: Address Block TLV Type assignment: LOCAL_IF +-------------+------+-----------+----------------------------------+ | Name | Type | Type | Description | | | | extension | | +-------------+------+-----------+----------------------------------+ | LINK_STATUS | TBD3 | 0 | Specifies the status of the link | | | | | from the indicated address | | | | | (LOST, SYMMETRIC or HEARD) | | Unassigned | TBD3 | 1-255 | Expert Review | +-------------+------+-----------+----------------------------------+ Table 7: Address Block TLV Type assignment: LINK_STATUS Clausen, et al. Expires January 14, 2010 [Page 52] Internet-Draft MANET-NHDP July 2009 +--------------+------+-----------+---------------------------------+ | Name | Type | Type | Description | | | | extension | | +--------------+------+-----------+---------------------------------+ | OTHER_NEIGHB | TBD4 | 0 | Specifies that the address is | | | | | (SYMMETRIC) or recently was | | | | | (LOST) of an interface of a | | | | | symmetric 1-hop neighbor of the | | | | | router transmitting the message | | Unassigned | TBD4 | 1-255 | Expert Review | +--------------+------+-----------+---------------------------------+ Table 8: Address Block TLV Type assignment: OTHER_NEIGHB 18.5. LOCAL_IF, LINK_STATUS and OTHER_NEIGHB Values The Values which the LOCAL_IF Address Block TLV can use are the following: o THIS_IF := 0 o OTHER_IF := 1 The Values which the LINK_STATUS Address Block TLV can use are the following: o LOST := 0 o SYMMETRIC := 1 o HEARD := 2 The Values which the OTHER_NEIGHB Address Block TLV can use are the following: o LOST := 0 o SYMMETRIC := 1 19. Contributors This specification is the result of the joint efforts of the following contributors, listed alphabetically. o Brian Adamson, NRL, USA, o Cedric Adjih, INRIA, France, Clausen, et al. Expires January 14, 2010 [Page 53] Internet-Draft MANET-NHDP July 2009 o Thomas Heide Clausen, LIX, France, o Justin Dean, NRL, USA, o Christopher Dearlove, BAE Systems ATC, UK, o Philippe Jacquet, INRIA, France, 20. Acknowledgements The authors would like to acknowledge the team behind OLSRv1, specified in RFC3626 for their contributions. The authors would like to gratefully acknowledge the following people for intense technical discussions, early reviews and comments on the specification and its components (listed alphabetically): Alan Cullen (BAE Systems), Ulrich Herberg (LIX), Satoh Hiroki (Hitachi) Joe Macker (NRL), Charles E. Perkins (WiChorus), Laurent Viennot (INRIA), and the entire IETF MANET working group. 21. References 21.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, BCP 14, March 1997. [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter considerations in MANETs", RFC 5148, February 2008. [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, "Generalized MANET Packet/Message Format", RFC 5444, February 2009. [RFC5497] Clausen, T. and C. Dearlove, "Representing multi-value time in MANETs", RFC 5497, March 2009. [RFC5498] Chakeres, I., "IANA Allocations for MANET Protocols", RFC 5498, March 2009. 21.2. Informative References [RFC2501] Macker, J. and S. Corson, "Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations", RFC 2501, January 1999. [RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link State Clausen, et al. Expires January 14, 2010 [Page 54] Internet-Draft MANET-NHDP July 2009 Routing Protocol", RFC 3626, October 2003. [RFC5449] Clausen, T., Baccelli, E., Nguyen, D., and P. Jacquet, "OSPF Multipoint Relay (MPR) Extension for Ad Hoc Networks", RFC 5449, February 2009. Appendix A. Address Block TLV Combinations The algorithm for generating HELLO messages in Section 11 specifies which 1-hop addresses may be included in the Address Blocks, and with which associated Address Block TLVs. These Address Block TLVs may have Type = LINK_STATUS or Type = OTHER_NEIGHB, or both. Address Block TLVs with Type = LINK_STATUS may have three possible Values (Value = HEARD, Value = SYMMETRIC or Value = LOST), and Address Block TLVs of TYPE = OTHER_NEIGHB may have two possible Values (Value = SYMMETRIC or Value = LOST). When both Address Block TLVs are associated with the same address only certain combinations of these Address Block TLV Values are necessary, and are the only combinations generated by the algorithm in Section 11. These combinations are indicated in Table 9. Cells labeled with "Yes" indicate the possible combinations which are generated by the algorithm in Section 11. Cells labeled with "No" indicate combinations not generated by the algorithm in Section 11, but which are correctly parsed and interpreted by the algorithm in Section 12. The cell labeled with "No*" is actually inconsistent, it is handled by ignoring the Address Block TLV with Type = OTHER_NEIGHB. Clausen, et al. Expires January 14, 2010 [Page 55] Internet-Draft MANET-NHDP July 2009 +----------------+----------------+----------------+----------------+ | | Type = | Type = | Type = | | | OTHER_NEIGHB | OTHER_NEIGHB, | OTHER_NEIGHB, | | | (absent) | Value = | Value = LOST | | | | SYMMETRIC | | +----------------+----------------+----------------+----------------+ | Type = | No | Yes | Yes | | LINK_STATUS | | | | | (absent) | | | | | Type = | Yes | Yes | Yes | | LINK_STATUS, | | | | | Value = HEARD | | | | | Type = | Yes | No | No* | | LINK_STATUS, | | | | | Value = | | | | | SYMMETRIC | | | | | Type = | Yes | Yes | No | | LINK_STATUS, | | | | | Value = LOST | | | | +----------------+----------------+----------------+----------------+ Table 9: LINK_STATUS and OTHER_NEIGHB TLV combinations Appendix B. Constraints Any process which updates the Local Information Base or the Neighbor Information Base MUST ensure that all constraints specified in this appendix are maintained. In each Local Interface Tuple: o I_local_iface_addr_list MUST NOT be empty. o I_local_iface_addr_list MUST NOT contain any duplicated addresses. o I_local_iface_addr_list MUST NOT contain any address which is in the I_local_iface_addr_list of any other Local Interface Tuple. In each Removed Interface Address Tuple: o IR_local_iface_addr MUST NOT contain any address which is in the I_local_iface_addr_list of any Local Interface Tuple. o IR_local_iface_addr MUST NOT equal the IR_local_iface_addr of any other Removed Interface Address Tuple. In each Link Tuple: Clausen, et al. Expires January 14, 2010 [Page 56] Internet-Draft MANET-NHDP July 2009 o L_neighbor_iface_addr_list MUST NOT be empty. o L_neighbor_iface_addr_list MUST NOT contain any address which is in the I_local_iface_addr_list of any Local Interface Tuple or the IR_local_iface_addr of any Removed Interface Address Tuple. o L_neighbor_iface_addr_list MUST NOT contain any duplicated addresses. o L_neighbor_iface_addr_list MUST NOT contain any address which is in the L_neighbor_iface_addr_list of any other Link Tuple in the same Link Set. o If L_HEARD_time has not expired then there MUST be a Neighbor Tuple whose N_neighbor_addr_list contains L_neighbor_iface_addr_list. o L_HEARD_time MUST NOT be greater than L_time. o L_SYM_time MUST NOT be greater than L_HEARD_time (unless both are expired). o L_quality MUST NOT be less than 0 or greater than 1. o If L_quality >= HYST_ACCEPT then L_pending MUST be false. o If L_quality < HYST_REJECT then L_status MUST be PENDING or LOST. o L_pending MUST NOT be set to true if it is currently false. In each Neighbor Tuple: o N_neighbor_addr_list MUST NOT contain any address which is in the I_local_iface_addr_list of any Local Interface Tuple or the IR_local_iface_addr of any Removed Interface Address Tuple. o N_neighbor_addr_list MUST NOT contain any duplicated addresses. o N_neighbor_addr_list MUST NOT contain any address which is in the N_neighbor_addr_list of any other Neighbor Tuple. o If N_symmetric is = true, then there MUST be one or more Link Tuples with: * L_neighbor_iface_addr_list contained in N_neighbor_addr_list; AND Clausen, et al. Expires January 14, 2010 [Page 57] Internet-Draft MANET-NHDP July 2009 * L_status = SYMMETRIC. o If N_symmetric is = false, then there MUST be one or more Link Tuples with: * L_neighbor_iface_addr_list contained in N_neighbor_addr_list. All such Link Tuples MUST NOT have L_status = SYMMETRIC. At least one such Link Tuple MUST have L_HEARD_time not expired. In each Lost Neighbor Tuple: o NL_neighbor_addr MUST NOT be in the I_local_iface_addr_list of any Local Interface Tuple or the IR_local_iface_addr of any Removed Interface Address Tuple. o NL_neighbor_addr MUST NOT equal the NL_neighbor_addr of any other Lost Neighbor Tuple. o NL_neighbor_addr MUST NOT be in the N_neighbor_addr_list of any Neighbor Tuple with N_symmetric = true. In each 2-Hop Tuple: o There MUST be a Link Tuple associated with the same MANET interface with: * L_neighbor_iface_addr_list = N2_neighbor_iface_addr_list; AND * L_status = SYMMETRIC. o N2_2hop_addr MUST NOT be in the I_local_iface_addr_list of any Local Interface Tuple or the IR_local_iface_addr of any Removed Interface Address Tuple. o N2_2hop_addr MUST NOT be the N2_2hop_addr of any other 2-Hop Tuple in the same 2-Hop Set and with the same N2_neighbor_iface_addr_list. o N2_2hop_addr MUST NOT be in the N2_neighbor_iface_addr_list of the same 2-Hop Tuple. Appendix C. HELLO Message Example An example HELLO message, transmitted by an originating router with a single MANET interface, is as follows. The message has Message Header containing hop-limit, hop-count and Clausen, et al. Expires January 14, 2010 [Page 58] Internet-Draft MANET-NHDP July 2009 message sequence number (four bit Flags field value is 14). Its four bit Message Address Length field has value 3 and hence addresses in the message have length four octets, here being IPv4 addresses. The message is as transmitted with a hop limit of 1 and a hop count of 0. The overall message length is 45 octets. The message contains a Message TLV Block with content length 8 octets containing two Message TLVs, of types VALIDITY_TIME and INTERVAL_TIME. Each uses a Message TLV with Flags octet value 16, indicating that each has a Value. Each has a Value Length of 1 octet; the Values included (0x64 and 0x58) are time codes representing the default values of parameters H_HOLD_TIME and HELLO_INTERVAL, respectively (6 seconds and 2 seconds) assuming the default value of constant C (1/1024 second). The message has a single Address Block containing 5 addresses. The Flags octet value 128 indicates an address Head but no address Tail, and no address prefixes. The Head Length of 3 octets indicates address Mid sections of one octet each (Mid 0 to Mid 4). The following Address Block TLV Block (content length 14 octets) includes two Address Block TLVs. The first is a LOCAL_IF Address Block TLV which (with Flags octet value 80) indicates that a single address, with index 0 (i.e. Head:Mid 0) is the single local interface address of this router (the 1 octet Value THIS_IF indicates that this address is of this interface). The second is a LINK_STATUS Address Block TLV which (with Flags octet value 48) specifies the link status values of all reported neighbors in a single multivalue Address Block TLV which covers the addresses with indexes 1 to 4. The Address Block TLV Value Length of 4 octets indicates one octet per Value per address. The last four addresses have associated link status, the first and second HEARD, the third SYMMETRIC, and the fourth LOST. Clausen, et al. Expires January 14, 2010 [Page 59] Internet-Draft MANET-NHDP July 2009 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | HELLO |1 1 1 0 0 0 1 1|0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 1|0 0 0 0 0 0 0 0| Message Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0| VALIDITY_TIME |0 0 0 1 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 1|0 1 1 0 0 1 0 0| INTERVAL_TIME |0 0 0 1 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 1|0 1 0 1 1 0 0 0|0 0 0 0 0 1 0 1|1 0 0 0 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 1 1| Head | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Mid 0 | Mid 1 | Mid 2 | Mid 3 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Mid 4 |0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0| LOCAL_IF | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 1 0 1 0 0 0 0|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 1| THIS_IF | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LINK_STATUS |0 0 1 1 0 0 0 0|0 0 0 0 0 0 0 1|0 0 0 0 0 1 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 1 0 0| HEARD | HEARD | SYMMETRIC | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LOST | +-+-+-+-+-+-+-+-+ Note that this example is for illustrative purposes. The essential information can be conveyed, more efficiently (assuming that the local interface address will be supplied by IP, and that the INTERVAL_TIME TLV is not needed) by the 29 octets: Clausen, et al. Expires January 14, 2010 [Page 60] Internet-Draft MANET-NHDP July 2009 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | HELLO |0 0 0 0 0 0 1 1|0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0| VALIDITY_TIME |0 0 0 1 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 1|0 1 1 0 0 1 0 0|0 0 0 0 0 1 0 0|1 0 0 0 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 1 1| Head | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Mid 1 | Mid 2 | Mid 3 | Mid 4 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1| LINK_STATUS |0 0 0 1 0 1 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 1 0 0| HEARD | HEARD | SYMMETRIC | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LOST | +-+-+-+-+-+-+-+-+ Appendix D. Flow and Congestion Control This protocol specifies one Message Type, the HELLO message. The maximum size of a HELLO message is proportional to the size of the originating router's 1-hop neighborhood. HELLO messages MUST NOT be forwarded. A router MUST report its 1-hop neighborhood in HELLO messages on each of its MANET interfaces at least each REFRESH_INTERVAL. This puts a lower bound on the control traffic generated by each router in the network employing this protocol. A router MUST ensure that two successive HELLO messages sent on the same MANET interface are separated by at least HELLO_MIN_INTERVAL. (If using jitter then this may be reduced to a mean minimum value of HELLO_MIN_INTERVAL - HP_MAXJITTER/2.) Thus, this puts an upper bound on the control traffic generated by each router in the network employing this protocol. Clausen, et al. Expires January 14, 2010 [Page 61] Internet-Draft MANET-NHDP July 2009 Appendix E. Interval and Timer Illustrations This informative appendix illustrates the relationship between message timers and intervals. (The adjustments to this timing when using timing jitter, as defined in [RFC5148], are not shown.) E.1. HELLO Message Generation Timing Figure 1 illustrates a basic HELLO message schedule for a router, on a MANET interface, employing strictly periodic transmission of HELLO messages. The router transmits a HELLO message each HELLO_INTERVAL. Each HELLO message contains all neighbor addresses of the router that are to be reported in any such HELLO message. (The parameter REFRESH_INTERVAL, not shown, is in this example equal to the parameter HELLO_INTERVAL.) The router includes a VALIDITY_TIME TLV in each HELLO message, encoding the parameter H_HOLD_TIME, the duration for which information received in the HELLO message should be considered valid by receiving routers. Receiving routers will, when recording the information received in the HELLO message, each use this for setting the L_HEARD_time, L_SYM_time and L_time elements of their corresponding Link Tuple, and the N2_time in the corresponding 2-Hop Tuple for each address. Only L_time is illustrated in Figure 1. H_HOLD_TIME: |-----------------------------| ... HELLO_INTERVAL: |---------|---------|---------| ... Time: ---*---------*---------*---------*------> ^ ^ ^ ^ | | | | HELLO (a, b, c, d) | | | | | | HELLO (a, b, c, d) | | ... | | HELLO (a, b, c, d) | | HELLO (a, b, c, d) L_time: |-----------------------------| |-------------------- ... |---------- ... | ... Figure 1: HELLO message generation: regular schedule Clausen, et al. Expires January 14, 2010 [Page 62] Internet-Draft MANET-NHDP July 2009 Figure 2 illustrates a message schedule similar to Figure 1, where the router announces its own presence more frequently by sending additional HELLO messages. HELLO messages are still sent regularly, at a reduced interval defined by a new value of HELLO_INTERVAL. However REFRESH_INTERVAL has not been reduced. Each neighbor address included in these HELLO messages need be advertised only once within each REFRESH_INTERVAL. Consequently the additional HELLO messages due to the reduced value of HELLO_INTERVAL may therefore be empty. (This is not the only allowed distribution of neighbor addresses, they could, for example, be sent alternately a, b and c, d.) H_HOLD_TIME: |-----------------------------| ... REFRESH_INTERVAL: |---------|---------|---------| ... HELLO_INTERVAL: |----|----|----|----|----|----| ... Time: ---*---------*---------*---------*------> ^ ^ ^ ^ ^ ^ ^ | | | | | | | HELLO (a, b, c, d) | | | | | | | | | | | | HELLO () | | | | | | | | | | HELLO (a, b, c, d) | | | | | | | | ... HELLO () | | | | | | HELLO (a, b, c, d) | | | | HELLO () | | HELLO (a, b, c, d) L_time: |-----------------------------| |------------------------- ... |-------------------- ... |--------------- ... |---------- ... |----- ... | ... Figure 2: HELLO message generation: regular schedule with different HELLO_INTERVAL and REFRESH_INTERVAL HELLO messages may also be sent in response to events. The minimal interval between two successive HELLO message transmissions by a Clausen, et al. Expires January 14, 2010 [Page 63] Internet-Draft MANET-NHDP July 2009 router is HELLO_MIN_INTERVAL, setting an upper bound of the HELLO message emission rate. Hence, for each HELLO message transmission, a router must wait at least HELLO_MIN_INTERVAL before the next HELLO message transmission. Similarly, the maximum interval between two successive HELLO message transmissions is HELLO_INTERVAL, setting a lower bound on the message transmission rate. Hence, for each HELLO message transmission, the router must ensure that the next HELLO message transmission must not wait more than HELLO_INTERVAL. Figure 3 illustrates a message schedule similar to Figure 1, but with HELLO messages responding to events at maximum rate, i.e. with HELLO messages being sent each HELLO_MIN_INTERVAL. Note that when a HELLO message is sent, it is assumed that the following messages may all be scheduled at an interval of HELLO_INTERVAL, and hence each HELLO message contains all neighbor addresses. In each HELLO message in this example, a new neighbor address is added, reflecting the changes occuring since the last HELLO message was sent. HELLO messages are sent at the maximum allowed rate in order to signal these changes as rapidly as possible. Clausen, et al. Expires January 14, 2010 [Page 64] Internet-Draft MANET-NHDP July 2009 H_HOLD_TIME: |-----------------------------| ... HELLO_INTERVAL: |---------|---------|---------| ... HELLO_MIN_INTERVAL: |----|----|----|----|----|----| ... Time: ---*---------*---------*---------*------> ^ ^ ^ ^ ^ ^ ^ | | | | | | | HELLO () | | | | | | | | | | | | HELLO (a) | | | | | | | | | | HELLO (a, b) | | | | | | | | ... HELLO (a, b, c) | | | | | | HELLO (a, b, c, d) | | | | HELLO (a, b, c, d, e) | | HELLO (a, b, c, d, e, f) L_time: |-----------------------------| |------------------------- ... |-------------------- ... |--------------- ... |---------- ... |----- ... | ... Figure 3: HELLO message generation: regular schedule with responsive messages Figure 4 shows the same example as Figure 3, but with an increased REFRESH_INTERVAL, and showing partial HELLO messages which include only the necessary addresses. Clausen, et al. Expires January 14, 2010 [Page 65] Internet-Draft MANET-NHDP July 2009 H_HOLD_TIME: |-----------------------------| ... REFRESH_INTERVAL: |-------------------|---------- ... |-------------------|----- ... |-------------------| ... |--------------- ... |---------- ... |----- ... | ... HELLO_INTERVAL: |---------|---------|---------| ... HELLO_MIN_INTERVAL: |----|----|----|----|----|----| ... Time: ---*---------*---------*---------*------> ^ ^ ^ ^ ^ ^ ^ | | | | | | | HELLO () | | | | | | | | | | | | HELLO (a) | | | | | | | | | | HELLO (b) | | | | | | | | ... HELLO (c) | | | | | | HELLO (a, d) | | | | HELLO (b, e) | | HELLO (c, f) L_time: |-----------------------------| |------------------------- ... |-------------------- ... |--------------- ... |---------- ... |----- ... | ... Figure 4: HELLO message generation: regular schedule with responsive messages and different HELLO_INTERVAL and REFRESH_INTERVAL Clausen, et al. Expires January 14, 2010 [Page 66] Internet-Draft MANET-NHDP July 2009 Figure 5 summarizes the overall relationship between the intervals governing HELLO message transmissions by a router. H_HOLD_TIME: |------------------------------------| REFRESH_INTERVAL: |----------------| HELLO_INTERVAL: |----------| HELLO_MIN_INTERVAL: |---| Time: -----------------------------------------------> ^ ^ ^ ^ ^ | | | | | | | | | Time until which HELLO message | | | received HELLO transmission | | | message content | | | is valid. | | | | | Time before which all | | neighbor information must | | be transmitted in HELLO | | messages (one or more) | | | Latest time for next HELLO message | transmission | Earliest time for next HELLO message transmission Figure 5: HELLO message generation intervals Clausen, et al. Expires January 14, 2010 [Page 67] Internet-Draft MANET-NHDP July 2009 E.2. HELLO Message Processing Timing Figure 6 illustrates the Link Set timers when receiving a HELLO message not including the address of the receiving MANET interface. VALIDITY_TIME: |--------------------------| L_time: |--------------------------| L_HEARD_time: |--------------------------| L_SYM_time: *-| (i.e. expired) Time: ---*--------------------------------> ^ | HELLO () received Figure 6: HELLO message processing: address not present Figure 7 illustrates the Link Set timers when, following the received HELLO message illustrated in Figure 6, a router receives a HELLO message including the address (a) of the receiving interface with link status = HEARD (or SYM). VALIDITY_TIME: |--------------------------| |--------------------------| L_time: |--------------------------| |--------------------------| L_HEARD_time: |--------------------------| |--------------------------| L_SYM_time: *-| (i.e. expired) L_SYM_time: |--------------------------| Time: -*-----*---------------------------------> ^ ^ | | HELLO () received | | HELLO (a:HEARD) received Figure 7: HELLO message processing: address present Figure 8 illustrates the Link Set timers when, following the received HELLO messages illustrated in Figure 7, a router receives a HELLO Clausen, et al. Expires January 14, 2010 [Page 68] Internet-Draft MANET-NHDP July 2009 message including the address (a) of the receiving interface with link status = LOST. VALIDITY_TIME: |--------------------------| |--------------------------| |--------------------------| L_time: |--------------------------| |--------------------------| |--------------------------| L_HEARD_time: |--------------------------| |--------------------------| |--------------------------| L_SYM_time: *-| (i.e. expired) |--------------------------| *-| (i.e. expired) Time: -*-----*-----*---------------------------------> ^ ^ ^ | | | HELLO () received | | | | HELLO (a:HEARD) received | | HELLO (a:LOST) received Figure 8: HELLO message processing: address lost E.3. Other HELLO Message Timing There are three other timing parameters which are used by a router to control HELLO message generation and processing. Figure 9 illustrates the time, with duration L_HOLD_TIME, during which the appropriate addresses of a formerly, but no longer, symmetric 1-hop neighbor, as connected by this MANET interface, are advertised as LOST using a LINK_STATUS TLV in HELLO messages on this MANET interface, thus allowing that 1-hop neighbor to update its Link Set accordingly. Clausen, et al. Expires January 14, 2010 [Page 69] Internet-Draft MANET-NHDP July 2009 L_HOLD_TIME: |----------------------------| Time: ---*----------------------------------> ^ ^ | | Formerly symmetric 1-hop neighbor | ceases to be symmetric on this | MANET interface | | Time until which addresses of this neighbor connected using this MANET interface are advertised in HELLO messages on this MANET interface using a LINK_STATUS TLV, Value = LOST Figure 9: HELLO message generation: advertisement of formerly symmetric 1-hop neighbor on this MANET interface as lost Figure 10 illustrates the time, with duration N_HOLD_TIME, during which all addresses of a formerly, but no longer, symmetric 1-hop neighbor, are advertised as LOST in HELLO messages on all MANET interfaces using an OTHER_NEIGHB TLV (if not also reported using a LINK_STATUS TLV) thus allowing all other symmetric 1-hop neighbors to update their 2-Hop Sets accordingly. L_HOLD_TIME: |----------------------------| Time: ---*----------------------------------> ^ ^ | | Formerly symmetric 1-hop neighbor | ceases to be symmetric | | Time until which addresses of this neighbor are advertised in HELLO messages on all MANET interfaces using an OTHER_NEIGHB TLV, Value = LOST Figure 10: HELLO message generation: advertisement of formerly symmetric 1-hop neighbor on any MANET interface as lost Figure 11 illustrates the time, with duration I_HOLD_TIME, during which a formerly, but no longer, used local interface address is excluded from being considered as a 2-hop neighbor address (in order that a router is not recorded as its own 2-hop neighbor during that period). Clausen, et al. Expires January 14, 2010 [Page 70] Internet-Draft MANET-NHDP July 2009 I_HOLD_TIME: |----------------------------| Time: ---*-----------------------------------> ^ ^ | | Formerly used local interface | address ceases to be assigned | to a local interface | | Time until which this address is excluded from being included in this router's 2-Hop Set Figure 11: Local interface removed address Appendix F. Topology Pictures This appendix illustrates various examples of physical topologies, as well as how these are logically recorded by NHDP from the point of view of the router A. This representation is a composite of information which would be contained within A's various Information Bases after NHDP has been running for sufficiently long time for the state to converge. Note that the examples given in this appendix are NOT exhaustive, but are selected to be illustrative of NHDP neighborhood representations of physical MANET topologies. The example topologies presented contain 3 physical routers A, B and C. Each of these routers has one or two distinct interfaces, denoted "top" and "bottom". Each interface has one or two addresses, and symmetric connectivity between a pair of interfaces is illustrated by these being connected by a line. In all examples, the topology is described as it is recorded by NHDP in router A. F.1. Example 1: Standard Single Interface Topology In Figure 12, each router has a single interface, each with a single IP address. This is the simplest possible network, and the resulting representation is given to the right in Figure 12. Clausen, et al. Expires January 14, 2010 [Page 71] Internet-Draft MANET-NHDP July 2009 __________ __________ | | | {1} {2} {3} | | | {1}--------{2}--------{3} +--'--+ +--'--+ +--'--+ | A | | B | | C | +-----+ +-----+ +-----+ Figure 12: Standard single interface topology (left), and corresponding NHDP representation (right) The Local Information Set in A contains a single Local Interface Tuple which has an I_local_iface_addr_list of {1}. This value is denoted with a {1} on the leftmost part of the resulting representation. The Interface Information Base has only one Link Set, which represents the "top" interface of A, or {1}. This Link Set's only Link Tuple has an L_neighbor_iface_addr_list containing {2}; this corresponds to the dashed line from {1} to {2} to the right in Figure 12. The 2-Hop Set contains a single 2-Hop Tuple, with N2_neighbor_iface_addr_list being {2} and N2_hop_addr being {3}; this corresponds to the dashed line from {2} to {3} to the right in Figure 12. The descriptions of the following examples in this appendix will be derived similarly, and use the same notational conventions. F.2. Example 2: Dual Addressed Interface on One Hop Neighbor In Figure 13, the network is identical to that in Example 1, except that the middle router, B, has two IP addresses on its single interface. __________ __________ | | | {1} {2,4} {3} | | | {1}-------{2,4}-------{3} +--'--+ +--'--+ +--'--+ | A | | B | | C | +-----+ +-----+ +-----+ Figure 13: Single interfaces, with 1-hop neighbor B having two addresses (left), and corresponding NHDP representation (right) The content of the Interface Information Base is in this case identical to Example 1, except that L_neighbor_iface_addr_list is Clausen, et al. Expires January 14, 2010 [Page 72] Internet-Draft MANET-NHDP July 2009 {2,4} and N2_neighbor_iface_addr_list is {2,4}. F.3. Example 3: Dual Addressed Interface on Two Hop Neighbor In Figure 14, the network is identical to that in Example 1, except that the rightmost router, C, has two IP addresses on its interface. __________ __________ | | | {1} {2} {3,4} _.---{3} | | | {1}--------{2}--<_ +--'--+ +--'--+ +--'--+ '---{4} | A | | B | | C | +-----+ +-----+ +-----+ Figure 14: Single interfaces, with 2-hop neighbor C having two addresses (left), and corresponding NHDP representation (right) The content of the Interface Information Base is in this case identical to than in Example 1, except that the 2-Hop Set contains an extra 2-Hop Tuple with N2_neighbor_iface_addr_list being {2} and N2_hop_addr being {4}. These two 2-Hop Tuples are illustrated by the two lines from {2} to {3} and (2) to {4}, respectively. F.4. Example 4: Dual Addressed Interfaces In Figure 15, the network is identical to that in Example 1, except that all routers have two IP addresses on their interface. The Local Information Base in router A is the same as in Example 1, except that I_local_iface_addr_list is {1,5}. __________ __________ | | | {1,5} {2,6} {3,4} _.---{3} | | | {1,5}------{2,6}-<_ +--'--+ +--'--+ +--'--+ '---{4} | A | | B | | C | +-----+ +-----+ +-----+ Figure 15: Single interfaces, all routers having two addresses (left), and corresponding NHDP representation (right) The content of the Interface Information Base is in this case a combination of the Interface Information Bases from Example 1, Example 2 and Example 3. Clausen, et al. Expires January 14, 2010 [Page 73] Internet-Draft MANET-NHDP July 2009 F.5. Example 5: Dual Interface on Two Hop Neighbor In Figure 16, all routers have a single IP address on each interface, and with the 2-hop neighbor having two interfaces. __________ __________ | | | {1} {2} {3} _.---{3} | | | {1}--------{2}--<_ +--'--+ +--'--+ +-----+ '---{4} | A | | B | | C | +-----+ +-----+ +-----+ | {4} Figure 16: Single addresses, with 2-hop neighbor C having two interfaces (left), and corresponding NHDP representation (right) The Interface Information Base is identical to that in Example 3; NHDP does not distinguish topologically between this example and Example 3. F.6. Example 6: Dual interface on One Hop Neighbor In Figure 17, all routers have a single IP address on each interface, and with the 1-hop neighbor having two interfaces. __________ | | {1} {2} ,-. | | {1}-------/{2}\-------{4} +--'--+ +--'--+ +-----+ \{5}/ | A | | B | | C | `-' +-----+ +-----+ +-----+ | | {5} {4} |__________| Figure 17: Single addresses, with 1-hop neighbor B having two interfaces (left), and corresponding NHDP representation (right) The Local Information Base is identical to that in Example 1. The Interface Information Base has only one Link Set containing one Link Tuple with L_neighbor_iface_addr_list being {2}. The 2-Hop Set Clausen, et al. Expires January 14, 2010 [Page 74] Internet-Draft MANET-NHDP July 2009 contains a single 2-Hop Tuple, with N2_neighbor_iface_addr_list being {2} and N2_hop_addr being {4}. The Neighbor Information Base contains a Neighbor Set containing a single Neighbor Tuple, which represents router B, with N_neighbor_addr_list being {2,5}. This entry is represented on the right of Figure 17 by circling {2} with {5}. Note that router A does not have information indicating which of router B's interfaces is connected to router C. However, router A knows that the address {4} (and thus router C) is reachable by using {2} as next hop. F.7. Example 7: Dual Interface on One and Two Hop Neighbors In Figure 18, all routers have a single IP address on each interface, and both the 1-hop and 2-hop neighbors have two interfaces. Furthermore, there are now two physical links between routers B and C, over distinct interface pairs. __________ __________ | | | {1} {2} {3} ,-. _.---{3} | | | {1}-------/{2}\--<_ +--'--+ +--'--+ +-----+ \{5}/ '---{4} | A | | B | | C | `-' +-----+ +-----+ +-----+ | | {5} {4} |__________| Figure 18: Single addresses, with 1-hop and 2-hop neighbors B and C having two interfaces (left), and corresponding NHDP representation (right) The Local Information Base is identical to that in Example 1. The Link Set is identical to that in Example 6, and the 2-Hop Set contains, as in Example 5 (and similarly to Examples 3 and 4), two 2-Hop Tuples representing the two links between routers B and C Note that router A does not have information describing which of router B's interfaces is connected to which interfaces of router C, or even that the interfaces with addresses {3} and {4} are interfaces of the same router. However, router A knows that the addresses {3} and {4} (and thus router C) are reachable using {2} as next hop. Clausen, et al. Expires January 14, 2010 [Page 75] Internet-Draft MANET-NHDP July 2009 F.8. Example 8: Dual Interface Locally and on One Hop Neighbor In Figure 19, all routers have a single IP address on each interface, and both A and its the 1-hop neighbor B have two interfaces. Furthermore, there are now two physical links between routers A and B, over distinct interface pairs. __________ __________ | | | ,-. {1} {2} {3} {1}-------/{2}\--------{3} | | | \{5}/ +--'--+ +--'--+ +-----+ `-' | A | | B | | C | +-----+ +-----+ +-----+ ,-. | | /{2}\ {6} {5} {6}-------\{5}/--------{3} |__________| `-' Figure 19: Single addresses, with both A and 1-hop neighbor B having two interfaces (left), and corresponding NHDP representation (right) The Local Information Set contains two Local Interface Tuples, with I_local_iface_addr_list of {1} and {6}, respectively. Each Interface Information Base's Link Set contains one Link Tuple, representing the links between {1} and {2}, and between {6} and {5}, respectively. The 2-Hop Set for interface {1} contains a single 2-Hop Tuple, with N2_neighbor_iface_addr_list being {2} and N2_hop_addr being {3}. The 2-Hop Set for interface {6} contains a single 2-Hop Tuple, with N2_neighbor_iface_addr_list being {5} and N2_hop_addr being {3}. The Neighbor Information Base contains a Neighbor Set containing a single Neighbor Tuple, which represents router B, with N_neighbor_addr_list being {2,5}. This entry is denoted by circling {2} with {5}. F.9. Example 9: Dual Interface on All Routers In Figure 20, all routers have a single IP address on each interface, and all routers have two interfaces. Furthermore, there are now two physical links between A and B, over distinct interface pairs, and two physical links between B and C, also over distinct interface pairs. Clausen, et al. Expires January 14, 2010 [Page 76] Internet-Draft MANET-NHDP July 2009 __________ __________ | | | ,-. _.---{3} {1} {2} {3} {1}-------/{2}\--<_ | | | \{5}/ '---{4} +--'--+ +--'--+ +-----+ `-' | A | | B | | C | +-----+ +-----+ +-----+ ,-. | | | /{2}\ _.---{3} {6} {5} {4} {6}-------\{5}/--<_ |__________|__________| `-' '---{4} Figure 20: Single addresses, with all routers having two interfaces (left), and corresponding NHDP representation (right) The Local Information Set is identical to that in Example 8. The Interface Information Base for each interface in A is also identical to that in Example 8, except that an additional 2-Hop Tuple is present in each 2-Hop Set, each representing the link between router B and the interface of router C with address {4}. As in Example 7, router A does not have information describing which of router B's interfaces is connected to which interface of C, or even that the interfaces with addresses {3} and {4} are interfaces of the same router. However, router A knows that the addresses {3} and {4} (and router C) are reachable by using {2} or {5} (depending on via which of its local interfaces) as next hop. F.10. Example 10: Dual Addressed Dual Interfaces on All Routers In Figure 21, all routers have two IP addresses on each interface, and all routers have two interfaces. Furthermore, there are now two physical links between A and B, over distinct interface pairs, and two physical links between B and C, also over distinct interface pairs. Clausen, et al. Expires January 14, 2010 [Page 77] Internet-Draft MANET-NHDP July 2009 __________ __________ _ _.--{9} | | | ,' `. _.-<__-{10} {1,2} {5,6} {9,10} {1,2}--|{5,6}|-<_ __ | | | |{7,8}| '-<_ -{11} +--'--+ +--'--+ +-----+ `._,' '-{12} | A | | B | | C | _ +-----+ +-----+ +-----+ ,' `. _.--{9} | | | |{5,6}| _.-<__-{10} {3,4} {7,8} {11,12} {3,4}--|{7,8}|-<_ __ |__________|__________| `._,' '-<_ -{11} '-{12} Figure 21: Dual addresses, with all routers having two interfaces (left) and corresponding NHDP representation (right) This example is the combination of all the preceding examples in this appendix. The Local Information Set in A contains Local Information Tuples for each of its interfaces, and each Interface Information Base contains in its Link Set a representation of links {1,2}-{5,6} or {3,4}-{7,8}, respectively. The Neighbor Set (in the Neighbor Information Base) records the existence of router B and all of its addresses on all its interfaces, i.e. {5,6,7,8}. As in Example 9, each interface address of router C is represented in the 2-Hop Set of each Interface Information Base as a link from router B to each of these addresses. Router A does not have information describing which of router B's interfaces is connected to which interface of C, nor that the addresses {9}, {10}, {11}, and {12} are addresses of the same router (or that some of these, such as {9} and {10}, are addresses on the same interface of the router). F.11. Example 11: Single Addressed Dual Interface Locally In Figure 22, all routers have a single interface, except for router A which has two. Each of A's two interfaces has a link with the single interface of router B. All interfaces have a single address. Clausen, et al. Expires January 14, 2010 [Page 78] Internet-Draft MANET-NHDP July 2009 __________ __________ | _____| | {1} | {2} {3} {1}--------{2}---------{3} | | | | +--'--+ | +--'--+ +-----+ | A | | | B | | C | +-----+ | +-----+ +-----+ | | {6} | {6}--------{2}---------{3} |____| Figure 22: Single addresses, with A having two interfaces, both linked to the single interface of B (left), and corresponding NHDP representation (right) This is similar to Example 8, except that the single address {2} also replaces the address {5}. In particular both Link Tuples (one in each Link Set, each in its corresponding Interface Information Base) have L_neighbor_iface_addr_list being {2}, the Neighbor Set (in the Neighbor Information Base) contains a single Neighbor Tuple with N_neighbor_addr_list being {2}, and both 2-Hop Tuples (one in each 2-Hop Set, each in its corresponding Interface Information Base) have N2_neighbor_iface_list being {2} and N2_2hop_addr being {3}. Authors' Addresses Thomas Heide Clausen LIX, Ecole Polytechnique Phone: +33 6 6058 9349 EMail: T.Clausen@computer.org URI: http://www.ThomasClausen.org/ Christopher Dearlove BAE Systems ATC Phone: +44 1245 242194 EMail: chris.dearlove@baesystems.com URI: http://www.baesystems.com/ Clausen, et al. Expires January 14, 2010 [Page 79] Internet-Draft MANET-NHDP July 2009 Justin W. Dean Naval Research Laboratory Phone: +1 202 767 3397 EMail: jdean@itd.nrl.navy.mil URI: http://pf.itd.nrl.navy.mil/ The OLSRv2 Design Team MANET Working Group Clausen, et al. Expires January 14, 2010 [Page 80]