Mobile Ad hoc Networking (MANET) T. Clausen Internet-Draft LIX, Ecole Polytechnique, France Intended status: Standards Track C. Dearlove Expires: August 5, 2007 BAE Systems Advanced Technology Centre J. Dean Naval Research Laboratory The OLSRv2 Design Team MANET Working Group February 2007 MANET Neighborhood Discovery Protocol (NHDP) draft-ietf-manet-nhdp-02 Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on August 5, 2007. Copyright Notice Copyright (C) The IETF Trust (2007). Clausen, et al. Expires August 5, 2007 [Page 1] Internet-Draft MANET-NHDP February 2007 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 . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 6 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 7 4.1. HELLO Message Generation . . . . . . . . . . . . . . . . . 7 4.2. HELLO message content . . . . . . . . . . . . . . . . . . 8 4.3. Node Behavior . . . . . . . . . . . . . . . . . . . . . . 8 5. Local Information Base . . . . . . . . . . . . . . . . . . . . 10 5.1. Local Interface Set . . . . . . . . . . . . . . . . . . . 10 6. Neighborhood Information Base . . . . . . . . . . . . . . . . 11 6.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . . . 11 6.2. Symmetric Neighbor Set . . . . . . . . . . . . . . . . . . 12 6.3. Neighborhood Address Association Set . . . . . . . . . . . 13 6.4. 2-Hop Neighbor Set . . . . . . . . . . . . . . . . . . . . 13 7. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 15 7.1. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 15 7.1.1. Local Interface Block . . . . . . . . . . . . . . . . 16 7.1.2. Address Block TLVs . . . . . . . . . . . . . . . . . . 16 8. Local Information Base Changes . . . . . . . . . . . . . . . . 17 8.1. Adding a MANET Interface . . . . . . . . . . . . . . . . . 17 8.2. Removing a MANET Interface . . . . . . . . . . . . . . . . 17 8.3. Adding an Address to a MANET Interface . . . . . . . . . . 18 8.4. Removing an Address from a MANET Interface . . . . . . . . 18 8.5. Changing the Principal Address of a MANET Interface . . . 18 9. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 19 9.1. HELLO Message: Transmission . . . . . . . . . . . . . . . 20 9.1.1. HELLO Message: Jitter . . . . . . . . . . . . . . . . 21 10. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 22 10.1. Populating the Link Set . . . . . . . . . . . . . . . . . 22 10.2. Populating the Symmetric Neighbor Set . . . . . . . . . . 23 10.3. Populating the Neighborhood Address Association Set . . . 24 10.4. Populating the 2-Hop Neighbor Set . . . . . . . . . . . . 25 10.5. Neighborhood Changes . . . . . . . . . . . . . . . . . . . 26 11. Link Hysteresis . . . . . . . . . . . . . . . . . . . . . . . 27 11.1. Link Quality . . . . . . . . . . . . . . . . . . . . . . . 28 12. Proposed Values for Constants . . . . . . . . . . . . . . . . 29 12.1. Message Intervals . . . . . . . . . . . . . . . . . . . . 29 12.2. Holding Times . . . . . . . . . . . . . . . . . . . . . . 29 12.3. Hysteresis values . . . . . . . . . . . . . . . . . . . . 29 12.4. Jitter Times . . . . . . . . . . . . . . . . . . . . . . . 30 Clausen, et al. Expires August 5, 2007 [Page 2] Internet-Draft MANET-NHDP February 2007 12.5. Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 13. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 31 13.1. Multicast Addresses . . . . . . . . . . . . . . . . . . . 31 13.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 31 13.3. TLV Types . . . . . . . . . . . . . . . . . . . . . . . . 31 13.4. LINK_STATUS and OTHER_NEIGHB Values . . . . . . . . . . . 32 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 33 14.1. Normative References . . . . . . . . . . . . . . . . . . . 33 14.2. Informative References . . . . . . . . . . . . . . . . . . 33 Appendix A. Address Block TLV Combinations . . . . . . . . . . . 34 Appendix B. HELLO Message Example . . . . . . . . . . . . . . . 35 Appendix C. Time TLVs . . . . . . . . . . . . . . . . . . . . . 37 C.1. Representing Time . . . . . . . . . . . . . . . . . . . . 37 C.2. General Time TLV Structure . . . . . . . . . . . . . . . . 37 C.3. Message TLVs . . . . . . . . . . . . . . . . . . . . . . . 39 C.3.1. VALIDITY_TIME TLV . . . . . . . . . . . . . . . . . . 39 C.3.2. INTERVAL_TIME TLV . . . . . . . . . . . . . . . . . . 39 Appendix D. Message Jitter . . . . . . . . . . . . . . . . . . . 40 D.1. Jitter . . . . . . . . . . . . . . . . . . . . . . . . . . 40 D.1.1. Periodic message generation . . . . . . . . . . . . . 40 D.1.2. Externally triggered message generation . . . . . . . 41 D.1.3. Message forwarding . . . . . . . . . . . . . . . . . . 42 D.1.4. Maximum Jitter Determination . . . . . . . . . . . . . 43 Appendix E. Utilizing Link Layer Information . . . . . . . . . . 44 Appendix F. Security Considerations . . . . . . . . . . . . . . 46 Appendix F.1. Invalid HELLO messages . . . . . . . . . . . . . . . 46 Appendix G. Flow and Congestion Control . . . . . . . . . . . . 48 Appendix H. Contributors . . . . . . . . . . . . . . . . . . . . 49 Appendix I. Acknowledgements . . . . . . . . . . . . . . . . . . 50 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 51 Intellectual Property and Copyright Statements . . . . . . . . . . 52 Clausen, et al. Expires August 5, 2007 [Page 3] Internet-Draft MANET-NHDP February 2007 1. Introduction This document describes a neighborhood discovery protocol (NHDP) for a mobile ad hoc network (MANET). The protocol uses an exchange of HELLO messages in order that each node can determine its 1-hop and symmetric 2-hop neighborhoods. This specification describes both this HELLO message exchange, the messages being defined as instances of the specification [1], and the information storage required for neighborhood discovery. This protocol makes no assumptions about the underlying link layer, other than support of link local multicast. Link layer information and notifications 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) [3]. Clausen, et al. Expires August 5, 2007 [Page 4] Internet-Draft MANET-NHDP February 2007 2. Terminology The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC2119 [2]. The terms "packet", "message", "address block", "TLV", and "TLV block" in this document are to be interpreted as described in [1]. Additionally, this document uses the following terminology: Node - A MANET router which implements this neighborhood discovery protocol. MANET interface - A network device participating in a MANET and using this neighborhood discovery protocol. A node may have several MANET interfaces, each being assigned one or more IP addresses. Link - A pair of MANET interfaces from two different nodes, where at least one interface is able to receive traffic from the other. Symmetric link - A link where both MANET interfaces are able to receive traffic from the other. 1-hop neighbor - A node X is a 1-hop neighbor of a node Y if node Y can hear node X (i.e. a link exists from a MANET interface on node X to a MANET interface on node Y). Symmetric 1-hop neighbor - A node X is a symmetric 1-hop neighbor of a node Y if a symmetric link exists from a MANET interface on node X to a MANET interface on node Y. Symmetric 2-hop neighbor - A node X is a symmetric 2-hop neighbor of a node Y if node X is a symmetric 1-hop neighbor of a symmetric 1-hop neighbor of node Y, but is not node Y itself. 1-hop neighborhood - The 1-hop neighborhood of a node X is the set of the 1-hop neighbors of node X. Symmetric 1-hop neighborhood - The symmetric 1-hop neighborhood of a node X is the set of the symmetric 1-hop neighbors of node X. Symmetric 2-hop neighborhood - The symmetric 2-hop neighborhood of a node X is the set of the symmetric 2-hop neighbors of node X. (This may include nodes in the 1-hop neighborhood, or even in the symmetric 1-hop neighborhood, of node X.) Clausen, et al. Expires August 5, 2007 [Page 5] Internet-Draft MANET-NHDP February 2007 3. Applicability Statement This neighborhood discovery protocol supports nodes which have one or more interfaces participating in the MANET. It provides each node with local topology information up to two hops away. This information is made available to other protocols through a Neighborhood Information Base, described in Section 6. The protocol is designed to work in networks where messages may be lost, such as due to collisions in wireless networks. If relevant link layer information is available then it may be used by this protocol. This protocol to works in a completely distributed manner and does not depend on any central entity. It does not require any changes to the format of IP packets, thus any existing IP stack can be used as is. This protocol uses the packet and message formats specified in [1]. HELLO messages specified by this protocol may be extended using the TLV mechanisms described in [1]. For example, if multipoint relays (MPRs) are to be calculated similarly to as in OLSR [3] and signaled to neighbors, then this information may be added to HELLO messages using an address block TLV. HELLO messages can also be transmitted in packets with messages from other protocols that also use [1]. Clausen, et al. Expires August 5, 2007 [Page 6] Internet-Draft MANET-NHDP February 2007 4. Protocol Overview and Functioning This protocol specifies local (one hop) signaling that: o advertises the presence of a node and its MANET interfaces; o discovers links to adjacent nodes; o performs bidirectionality checks on the discovered links; o advertises discovered links and whether each is symmetric to its 1-hop neighbors and hence discover symmetric 2-hop neighbors; o maintains an information base describing discovered links and their status, 1-hop neighbors and their MANET interfaces, symmetric 1-hop neighbors and symmetric 2-hop neighbors. Signaling consists of a single type of message, known as a HELLO message. A HELLO message identifies its originator node and that node's MANET interfaces and addresses. As a node receives HELLO messages and populates its information base, a list of 1-hop neighbors' MANET interface addresses and their link status (lost, symmetric or heard) is included in subsequent HELLO messages. Thus, the periodic transmission allows nodes to continuously track changes in their 1-hop and symmetric 2-hop neighborhoods. If information about link quality is available from the link layer, then this may also be used, see Appendix E. 4.1. HELLO Message Generation HELLO messages MAY be sent: o Proactively, at a regular interval, known as HELLO_INTERVAL. HELLO_INTERVAL may be fixed, as suggested in Section 12, or may be dynamic. For example HELLO_INTERVAL may be backed off due to congestion or network stability. Note that if HELLO_INTERVAL is dynamic, it is interpreted as the interval within which the next HELLO message will be sent on the same MANET interface. o As a response to a change in the node itself, or its neighborhood, for example on first becoming active or in response to a new, broken 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 9.1, MAY be used if appropriate. Clausen, et al. Expires August 5, 2007 [Page 7] Internet-Draft MANET-NHDP February 2007 HELLO messages are sent independently on each MANET interface. 4.2. HELLO message content Each HELLO message sent over a MANET interface need not contain all of the information appropriate to that MANET interface, however: o A HELLO message MUST contain all of its own local interface information. o Within every time interval of length REFRESH_INTERVAL, HELLO messages sent over a MANET interface MUST include all of the information appropriate to that interface in at least one HELLO message sent on that interface. This applies to otherwise purely responsive nodes as well as proactive nodes. o A HELLO message MUST include a VALIDITY_TIME message TLV that indicates the length of time for which the message content is to be considered valid and included in the receiving node's Neighborhood Information Base. o A HELLO message SHOULD include an INTERVAL_TIME message TLV that indicates the current value of HELLO_INTERVAL. 4.3. Node Behavior A node MUST: o Respect a minimum interval, HELLO_MIN_INTERVAL, between successive HELLO message transmissions over a given interface. If jitter is used then this interval MAY be reduced, but only by a random value not exceeding HP_MAXJITTER. o Ensure that if HELLO_INTERVAL and other parameters are maintained dynamically, changes do not invalidate the guarantees of Section 9.1. o Maintain, based on received HELLO messages, estimates of its 1-hop and symmetric 2-hop neighborhoods as this protocol operates. Formally defined in Section 6, this can be summarized as consisting of the following sets: Link Set - Records the status of all links from and to current and former 1-hop neighbors. Clausen, et al. Expires August 5, 2007 [Page 8] Internet-Draft MANET-NHDP February 2007 Symmetric Neighbor Set - Records the status of current and former symmetric 1-hop neighbors. If any of these nodes have more than one MANET interface then this set may record addresses that are not in the Link Set. Neighborhood Address Association Set - Allows the addresses of the MANET interfaces of each 1-hop neighbor to be associated with each other. 2-Hop Neighbor Set - Records the addresses of the MANET interfaces of symmetric 2-hop neighbors. The information in the Link Set and Symmetric Neighbor Set MUST be maintained in order for a node to correctly generate HELLO messages. Clausen, et al. Expires August 5, 2007 [Page 9] Internet-Draft MANET-NHDP February 2007 5. Local Information Base A node maintains a Local Information Base that records information about its MANET interfaces. Each MANET interface MUST have at least one address, and MAY have more than one address. All addresses have an associated prefix length, which is included all addresses in the Local Information Base. If an address otherwise does not have a prefix length it is set equal to the address length. Two addresses are considered equal if and only if their associated prefix lengths are also equal. One of the addresses of each MANET interface is denoted the principal address of that interface. A node MAY choose which address is the principal address in any manner; it SHOULD choose the address so as to minimize changes of principal address. The selection of an address as a principal address only affects how the node organizes its information storage, it has no effect on the messages it creates and sends. The Local Information Base is not modified by this protocol. This protocol may respond to changes of this Local Information Base which MUST reflect corresponding changes in the node's status. 5.1. Local Interface Set A node's Local Interface Set records its local MANET interfaces. It consists of Local Interface Tuples, one per MANET interface: (I_local_iface_addr_list) where: I_local_iface_addr_list is a list of the addresses of this MANET interface, with the first of the listed addresses being considered as the principal address of the interface. Clausen, et al. Expires August 5, 2007 [Page 10] Internet-Draft MANET-NHDP February 2007 6. Neighborhood Information Base A node maintains a Neighborhood Information Base that records information about its 1-hop and symmetric 2-hop neighborhoods. The Neighborhood Information Base includes the Link Set, the Symmetric Neighbor Set, the Neighborhood Address Association Set and the 2-Hop Neighbor Set. A node, X, can be present in both the 1-hop and symmetric 2-hop neighborhoods of another node, Y, concurrently. This allows node X to be immediately considered as a symmetric 2-hop neighbor by node Y if the link between them fails. All addresses MUST have an associated prefix length, which is included in all addresses in the Neighborhood Information Base. Prefix lengths are indicated in HELLO messages using the PREFIX_LENGTH TLV specified in [1]; if an address has no such TLV, then its prefix length is equal to the address length. Two addresses are considered equal if and only if their associated prefix lengths are also equal. 6.1. Link Set A node's Link Set records its 1-hop neighborhood. It consists of Link Tuples: (L_local_iface_addr, L_neighbor_iface_addr_list, L_SYM_time, L_ASYM_time, L_LOST_time, L_quality, L_pending, L_lost, L_time) where: L_local_iface_addr is the principal address of the local MANET interface on which the 1-hop neighbor is or was heard; L_neighbor_iface_addr_list is a list of the addresses of the MANET interface of the 1-hop neighbor; L_SYM_time is the time until which the link to the 1-hop neighbor is considered symmetric; L_ASYM_time is the time until which the MANET interface of the 1-hop neighbor is considered heard; L_LOST_time is the time until which the MANET interface of the 1-hop neighbor is considered lost; if L_lost is true and L_LOST_time is expired, then this Tuple MUST be removed; Clausen, et al. Expires August 5, 2007 [Page 11] Internet-Draft MANET-NHDP February 2007 L_quality is a dimensionless number between 0 (included) and 1 (included) describing the quality of a link; 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 link quality and hysteresis; L_time specifies when this Tuple expires and MUST be removed. The status of the link as obtained through simple message exchange, denoted H_STATUS, can be derived based on the elements L_SYM_time and L_ASYM_time as defined in Table 1. +-------------+-------------+-----------+ | L_SYM_time | L_ASYM_time | H_STATUS | +-------------+-------------+-----------+ | Expired | Expired | LOST | | | | | | Not Expired | Expired | SYMMETRIC | | | | | | Not Expired | Not Expired | SYMMETRIC | | | | | | Expired | Not Expired | HEARD | +-------------+-------------+-----------+ Table 1 The status of the link, taking link quality and hysteresis into account, denoted L_STATUS, is defined by: 1. if L_pending is true, then L_STATUS = PENDING; 2. otherwise, if L_lost is true, then L_STATUS = LOST; 3. otherwise, if L_LOST_time is not expired, then L_STATUS = LOST; 4. otherwise, L_STATUS = H_STATUS. 6.2. Symmetric Neighbor Set A node's Symmetric Neighbor Set records its symmetric 1-hop neighborhood. It consists of Symmetric Neighbor Tuples: (N_local_iface_addr, N_neighbor_iface_addr, N_SYM_time, N_time) where: Clausen, et al. Expires August 5, 2007 [Page 12] Internet-Draft MANET-NHDP February 2007 N_local_iface_addr is the principal address of the local MANET interface to which the 1-hop neighbor has or had a symmetric link; N_neighbor_iface_addr is an address of a MANET interface of a 1-hop neighbor which is or was a symmetric 1-hop neighbor of this node; N_SYM_time is the time until which the 1-hop neighbor is considered to be a symmetric 1-hop neighbor; N_time specifies when this Tuple expires and MUST be removed. The status of the 1-hop neighbor, denoted N_STATUS, can be derived based on the field N_SYM_time as defined in Table 2. +-------------+-----------+ | N_SYM_time | N_STATUS | +-------------+-----------+ | Expired | LOST | | | | | Not Expired | SYMMETRIC | +-------------+-----------+ Table 2 6.3. Neighborhood Address Association Set A node's Neighborhood Address Association Set records the MANET interface configuration of its 1-hop neighbors. It consists of Neighborhood Address Association Tuples: (NA_neighbor_iface_addr_list, NA_time) where: NA_neighbor_iface_addr_list is a list of interface addresses of a 1-hop neighbor; NA_time specifies when this Tuple expires and MUST be removed. 6.4. 2-Hop Neighbor Set A node's 2-Hop Neighbor Set records its symmetric 2-hop neighborhood. It consists of 2-Hop Neighbor Tuples: (N2_local_iface_addr, N2_neighbor_iface_addr_list, N2_2hop_iface_addr, N2_time) where: Clausen, et al. Expires August 5, 2007 [Page 13] Internet-Draft MANET-NHDP February 2007 N2_local_iface_addr is the principal address of the local MANET interface on which this information was received; N2_neighbor_iface_addr_list is a list of the addresses of the MANET interface of the 1-hop neighbor from which this information was received; N2_2hop_iface_addr is an address of a MANET interface 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 the time at which this Tuple expires and MUST be removed. Clausen, et al. Expires August 5, 2007 [Page 14] Internet-Draft MANET-NHDP February 2007 7. Packets and Messages The packet and message format used by this neighborhood discovery protocol is defined in [1], which is used with the following considerations: o this protocol specifies one message type, the HELLO message; o HELLO message header options may be used as specified by the protocol which uses this neighborhood discovery protocol; o HELLO messages MUST NOT be forwarded; o HELLO messages may be included in multi-message packets as specified in [1]; o packet header options may be used as specified by the protocol which uses this neighborhood discovery protocol. 7.1. HELLO Messages A HELLO message MUST contain: o A VALIDITY_TIME message TLV as specified in Appendix C, representing time value (at distance one hop) H_HOLD_TIME, which MUST NOT be less than REFRESH_INTERVAL. If HELLO messages may be lost then H_HOLD_TIME SHOULD be a multiple of REFRESH_INTERVAL. o An address block, and associated TLV block, known as the Local Interface Block, as specified in Section 7.1.1. A HELLO message which is transmitted at a regular interval SHOULD contain, and otherwise MAY contain: o An INTERVAL_TIME message TLV as specified in Appendix C, representing time value (at distance one hop) HELLO_INTERVAL. A HELLO message MAY contain: o One or more address blocks, with associated address block TLVs, containing current or former 1-hop neighbors' MANET interface addresses. Other addresses (i.e. addresses of non-neighbor nodes) MAY be included in these address blocks, but MUST NOT be associated with any of the TLVs specified in Section 7.1.2. o Other message TLVs. Clausen, et al. Expires August 5, 2007 [Page 15] Internet-Draft MANET-NHDP February 2007 7.1.1. Local Interface Block The first address block, plus following TLV block, in a HELLO message is known as the Local Interface Block. The Local Interface Block is not distinguished in any way other than by being the first address block in the message. The Local Interface Block MUST contain all of the addresses of all of the MANET interfaces of the originating node (i.e. all addresses appearing in an I_local_iface_addr_list). Those addresses, if any, which correspond to MANET interfaces other than that on which the HELLO message is transmitted MUST be associated with a corresponding TLV with Type == OTHER_IF as specified in Section 7.1.2, addresses of the MANET interface on which the HELLO message is transmitted MUST NOT be associated with such a TLV. Other addresses (i.e. not of any MANET interface of this node) which are local to this node only may be included in the Local Interface Block, they MUST be included in HELLO messages transmitted on all MANET interfaces, and MUST always be associated with a TLV with Type == OTHER_IF. Note that a Local Interface Block MAY include more than one address for each MANET interface, and hence a HELLO message MAY contain more than one address without an OTHER_IF TLV. 7.1.2. Address Block TLVs The three address block TLVs used in HELLO messages are specified in Table 3. +----------------+------+-------------------+-----------------------+ | Name | Type | Length | Value | +----------------+------+-------------------+-----------------------+ | OTHER_IF | TBD | 0 bits | Not Applicable | | | | | | | LINK_STATUS | TBD | 8 bits | One of LOST, | | | | | SYMMETRIC or HEARD | | | | | | | OTHER_NEIGHB | TBD | 8 bits | One of LOST or | | | | | SYMMETRIC | +----------------+------+-------------------+-----------------------+ Table 3 Clausen, et al. Expires August 5, 2007 [Page 16] Internet-Draft MANET-NHDP February 2007 8. Local Information Base Changes The Local Information Base MUST change to respond to changes in the node's MANET interfaces. The protocol MUST update its Neighborhood Information Base in response to such changes, and MAY transmit HELLO messages in response to such changes. 8.1. Adding a MANET Interface If a MANET interface is added to the node then this is indicated by the addition of a Local Interface Tuple to the Local Interface Set. The Neighbor Interface Base is not changed. A HELLO message MAY be sent on all MANET interfaces, it SHOULD be sent on the new interface. If using scheduled messages, a message schedule MUST be established on the new interface. 8.2. Removing a MANET Interface If a MANET interface is removed from the node, then this MUST result be the removal of information from the Local Information Base and the Neighborhood Information Base as follows: 1. Identify the Local Interface Tuple from the Local Interface Set which corresponds to the interface to be removed, and: 1. all Link Tuples whose L_local_iface_addr is included in the I_local_iface_addr_list of that Local Interface Tuple MUST be removed; 2. all Symmetric Neighbor Tuples whose N_local_iface_addr is included in the I_local_iface_addr_list of that Local Interface Tuple MUST be removed; 3. all 2-Hop Neighbor Tuples whose N2_local_iface_addr is included in the I_local_iface_addr_list of the Local Interface Tuple MUST be removed; 4. the Local Interface Tuple MUST be removed from the Local Interface Set. 2. All Neighborhood Address Association Tuples for which none of the addresses in its NA_neighbor_iface_addr_list may be found in any L_neighbor_iface_addr_list in the Link Set SHOULD be removed. If the removed interface is the last MANET interface of the node, then the Neighborhood Information Base SHOULD be empty, and the node no longer participates in the protocol. Clausen, et al. Expires August 5, 2007 [Page 17] Internet-Draft MANET-NHDP February 2007 A HELLO message MAY be sent on all remaining MANET interfaces. 8.3. Adding an Address to a MANET Interface If an address is added to a MANET interface then this is indicated by the addition of an address to the appropriate I_local_iface_addr_list. No change is made to the Neighbor Information Base. A HELLO message MAY be sent on all MANET interfaces. 8.4. Removing an Address from a MANET Interface If an address is removed from a MANET interface then this is indicated by the removal of an address to the appropriate I_local_iface_addr_list. No change is made to the Neighbor Information Base unless the removed address is the principal address of the MANET Interface, in which case first a new principal address of the interface is selected, as described in Section 8.5. A HELLO message MAY be sent on all MANET interfaces. 8.5. Changing the Principal Address of a MANET Interface If the principal address of a MANET interface of a node is changed then this is indicated by a reordering of the appropriate I_local_iface_addr_list. The following changes MUST be made to the Local Information Base: 1. all Link Tuples whose L_local_iface_addr is equal to the old first address in this I_local_iface_addr_list have that L_local_iface_addr set equal to the new first address in this I_local_iface_addr_list; 2. all Symmetric Neighbor Tuples whose N_local_iface_addr is equal to the old first address in this I_local_iface_addr_list have that N_local_iface_addr set equal to the new first address in this I_local_iface_addr_list; 3. all 2-Hop Neighbor Tuples whose N2_local_iface_addr is equal to the old first address in this I_local_iface_addr_list have that N2_local_iface_addr set equal to the new first address in this I_local_iface_addr_list. A HELLO message SHOULD NOT be sent in response to this change. Clausen, et al. Expires August 5, 2007 [Page 18] Internet-Draft MANET-NHDP February 2007 9. HELLO Message Generation HELLO messages MUST be generated and transmitted independently on each MANET interface. If using the HELLO message interval HELLO_INTERVAL then, following a HELLO message transmission on a MANET interface, another HELLO message MUST be sent on the same 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 9.1.1. A HELLO message MUST include a Local Interface Block as specified in Section 7.1.1 as its first address block. Other addresses which MUST be included in HELLO messages are: o addresses of 1-hop neighbors from the Link Set; o addresses of 1-hop neighbors from the Symmetric Neighbor Set. These addresses MUST NOT be included in the Local Interface Block. These addresses MAY be included in any HELLO messages sent on the appropriate MANET interface. These addresses, and their associated TLVs, are: 1. For each address which appears in an L_neighbor_iface_addr_list (a neighbor address) in one or more Link Tuples whose L_local_iface_addr is the principal address of the MANET interface over which the HELLO message is to be sent (i.e. the first address listed in the corresponding I_local_iface_addr_list), and whose L_STATUS does not equal PENDING, include the neighbor address with an associated TLV with: * Type = LINK_STATUS; AND * Value = L_STATUS. 2. For each address which appears as an N_neighbor_iface_addr in one or more Symmetric Neighbor Tuples: 1. if this address has already been included with an associated TLV with Type == LINK_STATUS and Value == SYMMETRIC, do not add an associated TLV with Type == OTHER_NEIGHB; 2. otherwise if, for one or more of these Symmetric Neighbor Tuples, N_STATUS == SYMMETRIC, then include this N_neighbor_iface_addr with an associated TLV with: Clausen, et al. Expires August 5, 2007 [Page 19] Internet-Draft MANET-NHDP February 2007 + Type = OTHER_NEIGHB; AND + Value = SYMMETRIC. 3. otherwise if, for all of these Symmetric Neighbor Tuples, N_STATUS == LOST, and this address has not already been included with an associated TLV with Type == LINK_STATUS and Value == LOST, then include this N_neighbor_iface_addr with an associated TLV with: + Type = OTHER_NEIGHB; AND + Value = LOST. On each of its MANET interfaces, for each specified 1-hop neighbor address and associated TLV, the address and associated TLV MUST be included in at least one HELLO message in every interval of length REFRESH_INTERVAL. If an address is specified with more than one associated TLV, then these TLVs MAY be independently included or excluded from each HELLO messages as long as each such TLV is included associated with that address in a HELLO message sent on that MANET interface in every interval of length REFRESH_INTERVAL. TLVs associated with the same address included in the same HELLO message MAY be applied to the same or different copies of that address. 9.1. HELLO Message: Transmission Messages are transmitted in the packet/message format specified by [1] using the ALL-MANET-NEIGHBORS multicast address as destination IP address, and with the HELLO message hop limit = 1. If the parameters of the protocol are changed, then guarantees given for the old values of the parameters MUST still be respected. In particular: o If HELLO_INTERVAL is increased, then a HELLO message MUST be sent within the old HELLO_INTERVAL of the previous HELLO message sent on each MANET interface. o If REFRESH_INTERVAL is increased, then all information (addresses and associated TLVs) must be sent again on each MANET interface within the old REFRESH_INTERVAL of the previous HELLO message that included that information. Clausen, et al. Expires August 5, 2007 [Page 20] Internet-Draft MANET-NHDP February 2007 9.1.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 Appendix D. Internally triggered message generation 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 Appendix D requires a parameter MAXJITTER. These parameters may be dynamic, and are specified by: o For periodic message generation: HP_MAXJITTER, which MUST be significantly less than HELLO_INTERVAL. o For externally triggered message generation: HT_MAXJITTER. If HELLO messages are also periodically generated then HT_MAXJITTER also MUST be significantly less than HELLO_INTERVAL. 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. In this case HP_MAXJITTER MUST NOT be greater than HELLO_MIN_INTERVAL. Clausen, et al. Expires August 5, 2007 [Page 21] Internet-Draft MANET-NHDP February 2007 10. HELLO Message Processing On receiving a HELLO message, a node MUST update its neighborhood information base. For the purpose of this section, note the following definitions: o the "validity time" of a message is calculated from the VALIDITY_TIME TLV of the HELLO message as specified in Appendix C; o the "Receiving Address List" is the I_local_iface_addr_list corresponding to the MANET interface on which the HELLO message was received; o the "Receiving Address" is the first address in the Receiving Address List, i.e. is the principal address of the MANET interface on which the HELLO message was received; o the "Sending Address List" is the list of the addresses contained in the Local Interface Block of the HELLO message which do not have an associated TLV with Type == OTHER_IF; o the word EXPIRED indicates that a timer is set to a value clearly preceding the current time (e.g. current time - 1). 10.1. Populating the Link Set On receiving a HELLO message, a node SHOULD update its Link Set: 1. If there is no Link Tuple such that: * L_local_iface_addr == Receiving Address; AND * L_neighbor_iface_addr_list contains one or more addresses in the Sending Address List. then create a new Link Tuple with: * L_local_iface_addr = Receiving Address; * L_SYM_time = EXPIRED; * L_quality = INITIAL_QUALITY; * L_pending = INITIAL_PENDING; * L_lost = false; Clausen, et al. Expires August 5, 2007 [Page 22] Internet-Draft MANET-NHDP February 2007 * L_LOST_time = EXPIRED; * L_time = current time + validity time. 2. This Link Tuple (existing or new) is then modified as follows: 1. If the node finds any address in the Receiving Address List in one of the address blocks included in the HELLO message, other than the Local Interface Block, then the Link Tuple is modified as follows: 1. If any such address in the HELLO message is associated with a TLV with Type == LINK_STATUS and (Value == HEARD or Value == SYMMETRIC) then: - L_SYM_time = current time + validity time; - L_time = L_SYM_time + L_HOLD_TIME. 2. Otherwise if any such address in the HELLO message is associated with a TLV with Type == LINK_STATUS and Value == LOST then: 1. if L_STATUS == SYMMETRIC: o L_time = current time + max(validity time, L_HOLD_TIME), o L_SYM_time = EXPIRED. 2. L_neighbor_iface_addr_list = Sending Address List; 3. L_ASYM_time = current time + validity time; 4. L_time = max(L_time, L_ASYM_time). 10.2. Populating the Symmetric Neighbor Set On receiving a HELLO message, a node SHOULD update its Symmetric Neighbor Set: 1. If any address in the Receiving Address List is in an address block of the HELLO message, other than the Local Interface Block, with an associated TLV with Type == LINK_STATUS and (Value == HEARD or Value == SYMMETRIC) then: 1. For each address (henceforth neighbor address) in the HELLO message's Local Interface Block where a corresponding link Clausen, et al. Expires August 5, 2007 [Page 23] Internet-Draft MANET-NHDP February 2007 tuple with L_STATUS == SYMMETRIC exists in the link set: 1. If there is no Symmetric Neighbor Tuple such that: - N_local_iface_addr == Receiving Address; AND - N_neighbor_iface_addr == neighbor address, then create a new Symmetric Neighbor Tuple with: - N_local_iface_addr = Receiving Address; - N_neighbor_iface_addr = neighbor address; 2. This Symmetric Neighbor Tuple (existing or new) is then modified as follows: - N_SYM_time = current time + validity time; - N_time = N_SYM_time + N_HOLD_TIME. 2. Otherwise if any address in the Receiving Address List is in an address block of the HELLO message, other than the Local Interface Block, with an associated TLV with Type == LINK_STATUS and Value == LOST, then: 1. For each address (henceforth neighbor address) in the HELLO message Local Interface Block, if there exists a Symmetric Neighbor Tuple with: + N_local_iface_addr == Receiving Address; AND + N_neighbor_iface_addr == neighbor address, then update this Symmetric Neighbor Tuple to have: + N_SYM_time = EXPIRED; + N_time = min(N_time, current time + N_HOLD_TIME). 10.3. Populating the Neighborhood Address Association Set On receiving a HELLO message, the node SHOULD update its Neighborhood Address Association Set: 1. Remove all Neighborhood Address Association Tuples where: Clausen, et al. Expires August 5, 2007 [Page 24] Internet-Draft MANET-NHDP February 2007 * NA_neighbor_iface_addr_list contains at least one address which is contained in the Local Interface Block of the received HELLO message, and create a new Neighborhood Address Association Tuple with: * NA_neighbor_iface_addr_list = list of all addresses contained in the Local Interface Block of the received HELLO message; * NA_time = current time + validity time. 10.4. Populating the 2-Hop Neighbor Set On receiving a HELLO message the node SHOULD update its 2-Hop Neighbor Set: 1. If there exists a Link Tuple with L_local_iface_addr == Source Address and for which L_STATUS == SYMMETRIC then: 1. For each address (henceforth 2-hop neighbor address) in an address block of the HELLO message, other than the Local Interface Block, which is not in any I_local_iface_addr_list (i.e. is not an address of a MANET interface of the receiving node): 1. If the 2-hop neighbor address has an associated TLV with: - Type == LINK_STATUS and Value == SYMMETRIC; OR - Type == OTHER_NEIGHB and Value == SYMMETRIC, then, if there is no 2-Hop Neighbor Tuple such that: - N2_local_iface_addr == Receiving Address; - N2_neighbor_iface_addr_list contains one or more addresses in the Sending Address List; AND - N2_2hop_iface_addr == 2-hop neighbor address. then create a 2-Hop Neighbor Tuple with: - N2_local_iface_addr = Receiving Address; - N2_2hop_iface_addr = 2-hop neighbor address. This 2-Hop Neighbor Tuple (existing or new) is then modified as follows: Clausen, et al. Expires August 5, 2007 [Page 25] Internet-Draft MANET-NHDP February 2007 - N2_neighbor_iface_addr_list = Sending Address List; - N2_time = current time + validity time. 2. Otherwise if the 2-hop neighbor address has a TLV with: - Type == LINK_STATUS and (Value == LOST or Value == HEARD); OR - Type == OTHER_NEIGHB and Value == LOST; then remove all 2-Hop Neighbor Tuples with: - N2_local_iface_addr == Receiving Address; AND - N2_neighbor_iface_addr_list contains one or more addresses in the Sending Address List; AND - N2_2hop_iface_addr == 2-hop neighbor address. 10.5. Neighborhood Changes If L_STATUS of a Link Tuple changes from SYMMETRIC to any other status, due to any of: o L_SYM_time expires; o L_SYM_time is set to EXPIRED as result of processing a TLV with Type == LINK_STATUS and Value == LOST; o A change in L_quality resulting in L_quality < HYST_REJECT then all 2-Hop Neighbor Tuples with: o N2_local_iface_addr == L_local_iface_addr from the Link Tuple, AND; o N2_neighbor_iface_addr_list contains one or more addresses in the L_neighbor_iface_addr_list from the Link Tuple, MUST be deleted. In this, or any other case of neighborhood change, a node MAY send a HELLO message reporting updated information, subject to the constraints in Section 9. Clausen, et al. Expires August 5, 2007 [Page 26] Internet-Draft MANET-NHDP February 2007 11. Link Hysteresis Link hysteresis allows associating a L_quality value with a link. Using this L_quality in conjunction with two thresholds, HYST_ACCEPT and HYST_REJECT, as well as for each link a L_pending and a L_lost flag, Section 6.1 allows determining the L_STATUS of a link. The basic principles of link hysteresis are as follows: o A node does not advertise a neighbor interface in any state until L_quality is acceptable. If INITIAL_PENDING == true, this is such that L_quality >= HYST_ACCEPT, otherwise this is such that L_quality >= HYST_REJECT; to ensure the latter a node MUST NOT define INITIAL_PENDING == false and INITIAL_QUALITY < HYST_REJECT. (A node also MUST NOT define INITIAL_PENDING == true and INITIAL_QUALITY >= HYST_ACCEPT.) A link which is not yet advertised has L_pending == true. o Once L_quality >= HYST_ACCEPT, the L_pending flag is set 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. If L_quality for a link changes, the following actions MUST be taken: 1. if L_quality >= HYST_ACCEPT then the corresponding Link Tuple is modified by: * L_pending = false; * L_lost = false; * L_LOST_time = EXPIRED. 2. if L_quality < HYST_REJECT then the corresponding Link Tuple is modified by: * L_lost = true Clausen, et al. Expires August 5, 2007 [Page 27] Internet-Draft MANET-NHDP February 2007 * L_LOST_time = current time + L_HOLD_TIME Any corresponding Tuples in the Symmetric Neighbor Set and 2-Hop Neighbor Set MUST be removed. 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 processing described in Section 10. (If the receipt of the HELLO message, or the packet containing it, creates the Link Tuple then instead the Link Tuple MUST be created with the updated L_quality value.) 11.1. Link Quality A node MAY never update link quality (L_quality). In this case the node MUST define: o INITIAL_PENDING = false; o INITIAL_QUALITY >= HYST_REJECT (there is no reason not to define INITIAL_QUALITY = 1). A node MAY update link quality based on any information available to it. Particular cases that MAY be used include: o Link layer information, see Appendix E. o Receipt or loss of packets. Provided packets include a packet sequence number as defined in [1], packets on a link SHOULD have sequential packet sequence numbers, whether or not they include HELLO messages. Link quality can be updated when a packet is received based on, for example, whether the last N out of M packets on the link were received, or a "leaky integrator" tracking packets. o Receipt or loss of HELLO messages. If the maximum interval between HELLO messages is known (possibly by inclusion of a message TLV with Type == INTERVAL_TIME as defined in Appendix C.2 in HELLO messages) then the loss of HELLO messages can be determined without the need to receive a 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. Clausen, et al. Expires August 5, 2007 [Page 28] Internet-Draft MANET-NHDP February 2007 12. Proposed Values for Constants This section lists proposed values for the constants used in the specification of the protocol. 12.1. Message Intervals o HELLO_INTERVAL = 2 seconds o REFRESH_INTERVAL = HELLO_INTERVAL o HELLO_MIN_INTERVAL = HELLO_INTERVAL/4 12.2. Holding Times o H_HOLD_TIME = 3 x REFRESH_INTERVAL o L_HOLD_TIME = H_HOLD_TIME o N_HOLD_TIME = H_HOLD_TIME 12.3. Hysteresis values If link quality is not changed then: o HYST_ACCEPT = 1 o HYST_REJECT = 0 o INITIAL_QUALITY = 1 o INITIAL_PENDING = false Otherwise, i.e. if link quality is changed, then these parameters will be dependent on the link quality process used. Example possible parameters are: o HYST_ACCEPT = 0.75 o HYST_REJECT = 0.25 o INITIAL_QUALITY = 0.5 o INITIAL_PENDING = true Clausen, et al. Expires August 5, 2007 [Page 29] Internet-Draft MANET-NHDP February 2007 12.4. Jitter Times o HP_MAXJITTER = HELLO_INTERVAL/4 o HT_MAXJITTER = HELLO_INTERVAL/4 12.5. Time o C = 0.0625 second (1/16 second) In order to achieve interoperability, C MUST be the same on all nodes. Clausen, et al. Expires August 5, 2007 [Page 30] Internet-Draft MANET-NHDP February 2007 13. IANA Considerations 13.1. Multicast Addresses A well-known link-local multicast address, ALL-MANET-NEIGHBORS, must be registered and defined for both IPv6 and IPv4. 13.2. Message Types This specification defines one message type, which must be allocated from the "Assigned Message Types" repository of [1]. +--------------------+-------+--------------------------------------+ | Mnemonic | Value | Description | +--------------------+-------+--------------------------------------+ | HELLO | TBD | Local signaling | +--------------------+-------+--------------------------------------+ Table 4 13.3. TLV Types This specification defines two Message TLV types, which must be allocated from the "Assigned Message TLV Types" repository of [1]. +--------------------+-------+--------------------------------------+ | Mnemonic | Value | Description | +--------------------+-------+--------------------------------------+ | VALIDITY_TIME | TBD | The time (in seconds) from receipt | | | | of the message during which the | | | | information contained in the message | | | | is to be considered valid | | | | | | INTERVAL_TIME | TBD | The maximum time (in seconds) | | | | between two successive transmissions | | | | of messages of the appropriate type | +--------------------+-------+--------------------------------------+ Table 5 This specification defines three Address Block TLV types, which must be allocated from the "Assigned Address Block TLV Types" repository of [1]. Clausen, et al. Expires August 5, 2007 [Page 31] Internet-Draft MANET-NHDP February 2007 +--------------------+-------+--------------------------------------+ | Mnemonic | Value | Description | +--------------------+-------+--------------------------------------+ | OTHER_IF | TBD | Specifies that the address, in the | | | | Local Interface Block of the | | | | message, is an address associated | | | | with a MANET interface other than | | | | the one on which the message is | | | | transmitted | | | | | | LINK_STATUS | TBD | Specifies the status of the link to | | | | the indicated address (LOST, | | | | SYMMETRIC or HEARD) | | | | | | OTHER_NEIGHB | TBD | Specifies that the address is | | | | (SYMMETRIC) or was (LOST) of a MANET | | | | interface of a symmetric 1-hop | | | | neighbor of the node transmitting | | | | the HELLO message, but does not have | | | | a matching or better LINK_STATUS TLV | +--------------------+-------+--------------------------------------+ Table 6 13.4. LINK_STATUS and OTHER_NEIGHB Values The values which the LINK_STATUS TLV can use are the following: o LOST = 0 o SYMMETRIC = 1 o HEARD = 2 The values which the OTHER_NEIGHB TLV can use are the following: o LOST = 0 o SYMMETRIC = 1 Clausen, et al. Expires August 5, 2007 [Page 32] Internet-Draft MANET-NHDP February 2007 14. References 14.1. Normative References [1] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, "Generalized MANET Packet/Message Format", Work In Progress draft-ietf-manet-packetbb-03.txt, January 2007. [2] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, BCP 14, March 1997. 14.2. Informative References [3] Clausen, T. and P. Jacquet, "The Optimized Link State Routing Protocol", RFC 3626, October 2003. Clausen, et al. Expires August 5, 2007 [Page 33] Internet-Draft MANET-NHDP February 2007 Appendix A. Address Block TLV Combinations The algorithm for generating HELLO messages in Section 9 specifies which addresses MAY be included in the address blocks after the Local Interface Block, and with which associated TLVs. These TLVs may have Type == LINK_STATUS or Type == OTHER_NEIGHB, or both. TLVs with Type == LINK_STATUS may have three possible values (Value == HEARD, Value == SYMMETRIC or Value == LOST), and TLVs of TYPE == OTHER_NEIGHB may have two possible values (Value == SYMMETRIC or Value == LOST). When both TLVs are associated with the same address only certain combinations of these TLV values are necessary, and are the only combinations generated by the algorithm in Section 9. These combinations are indicated in Table 7. Cells labeled with "Yes" indicate the possible combinations which are generated by the algorithm in Section 9. Cells labeled with "No" indicate combinations not generated by the algorithm in Section 9, but which are correctly parsed and interpreted by the algorithm in Section 10. +----------------+----------------+----------------+----------------+ | | 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 7 Clausen, et al. Expires August 5, 2007 [Page 34] Internet-Draft MANET-NHDP February 2007 Appendix B. HELLO Message Example An example HELLO message, sent by an originator node with a single MANET interface, is as follows. The message uses IPv4 (four octet) addresses without prefix TLVs. The message is sent with a full message header (message semantics octet is 0) with a hop limit of 1 and a hop count of 0. The overall message length is 50 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 TLV with semantics value 4, indicating that no start and stop indexes are included, and each has a value length of 1 octet. The values included (0x68 and 0x50) are time codes representing the default values of parameters H_HOLD_TIME and HELLO_INTERVAL, respectively (6 seconds and 2 seconds). The first address block contains 1 local interface address. The semantics octet value 2 indicates no address tail, and the head length of 4 octets indicates no address mid sections. This address block has no TLVs (TLV block content length 0 octets). The second, and last, address block contains 4 neighbor interface addresses. The semantics octet value 2 indicates no address tail, the head length of 3 octets indicates address mid sections of one octet each. The following TLV block (content length 7 octets) includes one LINK_STATUS TLV which reports the link status values of all reported neighbors in a single multivalue TLV: the first two addresses are HEARD, the third address is SYMMETRIC and the fourth address is LOST. The TLV semantics value of 20 indicates, in addition to that this is a multivalue TLV, that no start and stop indexes are included, since values for all addresses are included. The TLV value length of 4 octets indicates one octet per value per address. Clausen, et al. Expires August 5, 2007 [Page 35] Internet-Draft MANET-NHDP February 2007 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 0 0|0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |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 0 0 1 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 1|0 1 1 0 1 0 0 0| INTERVAL_TIME |0 0 0 0 0 1 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 1|0 1 0 1 0 0 0 0|0 0 0 0 0 0 0 1|0 0 0 0 0 0 1 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 1 0 0| Head | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Head (cont) |0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 1 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 1 0|0 0 0 0 0 0 1 1| Head | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Head (cont) | Mid | Mid | Mid | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Mid |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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Clausen, et al. Expires August 5, 2007 [Page 36] Internet-Draft MANET-NHDP February 2007 Appendix C. Time TLVs This appendix specifies a general time TLV structure for expressing either single time values or a set of time values with each value associated with a range of distances. Furthermore, using this general time TLV structure, this document specifies the INTERVAL_TIME and VALIDITY_TIME TLVs, which are used by NHDP. C.1. Representing Time This document specifies a TLV structure in which time values are each represented in an 8 bit time code, one or more of which may be used in a TLV's value field. Of these 8 bits, the least significant four bits represent the mantissa (a), and the most significant four bits represent the exponent (b), so that: o time value = (1 + a/16) * 2^b * C o time code = 16 * b + a All nodes in the network MUST use the same value of C, which will be specified in seconds, hence so will be all time values. Note that ascending values of the time code represent ascending time values, time values may thus be compared by comparison of time codes. An algorithm for computing the time code representing the smallest representable time value not less than the time value t is: 1. find the largest integer b such that t/C >= 2^b; 2. set a = 16 * (t / (C * 2^b) - 1), rounded up to the nearest integer; 3. if a == 16 then set b = b + 1 and set a = 0; 4. if a and b are in the range 0 and 15 then the required time value can be represented by the time code 16 * b + a, otherwise it can not. The minimum time value that can be represented in this manner is C. The maximum time value that can be represented in this manner is 63488 * C. C.2. General Time TLV Structure A Time TLV may be a packet, message or address block TLV. If it is a packet or message TLV then it must be a single value TLV as defined in [1]; if it is an address block TLV then it may be single value or Clausen, et al. Expires August 5, 2007 [Page 37] Internet-Draft MANET-NHDP February 2007 multivalue TLV. The specific Time TLVs specified in this document, in Appendix C.3 are message, and hence single value, TLVs. Note that even a single value Time TLV may contain a multiple octet field. The purpose of a single value Time TLV is to allow a single time value to be determined by a node receiving an entity containing the Time TLV, based on its distance from the entity's originator. The Time TLV may contain information that allows that time value to be a function of distance, and thus different receiving nodes may determine different time values. If a receiving node will not be able to determine its distance from the originating node, then the form of this Time TLV with a single time code in a field (or single value subfield) SHOULD be used. The field of a single value Time TLV is specified, using the regular expression syntax of [1], by: = {