draft-ietf-manet-nhdp-02.txt   draft-ietf-manet-nhdp-03.txt 
Mobile Ad hoc Networking (MANET) T. Clausen Mobile Ad hoc Networking (MANET) T. Clausen
Internet-Draft LIX, Ecole Polytechnique, France Internet-Draft LIX, Ecole Polytechnique, France
Intended status: Standards Track C. Dearlove Intended status: Standards Track C. Dearlove
Expires: August 5, 2007 BAE Systems Advanced Technology Expires: December 1, 2007 BAE Systems Advanced Technology
Centre Centre
J. Dean J. Dean
Naval Research Laboratory Naval Research Laboratory
The OLSRv2 Design Team The OLSRv2 Design Team
MANET Working Group MANET Working Group
February 2007 May 30, 2007
MANET Neighborhood Discovery Protocol (NHDP) MANET Neighborhood Discovery Protocol (NHDP)
draft-ietf-manet-nhdp-02 draft-ietf-manet-nhdp-03
Status of this Memo Status of this Memo
By submitting this Internet-Draft, each author represents that any By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware 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 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. aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
skipping to change at page 1, line 40 skipping to change at page 1, line 40
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft will expire on August 5, 2007. This Internet-Draft will expire on December 1, 2007.
Copyright Notice Copyright Notice
Copyright (C) The IETF Trust (2007). Copyright (C) The IETF Trust (2007).
Abstract Abstract
This document describes a 1-hop and symmetric 2-hop neighborhood This document describes a 1-hop and symmetric 2-hop neighborhood
discovery protocol (NHDP) for mobile ad hoc networks (MANETs). discovery protocol (NHDP) for mobile ad hoc networks (MANETs).
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Applicability Statement . . . . . . . . . . . . . . . . . . . 6 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 7
4. Protocol Overview and Functioning . . . . . . . . . . . . . . 7 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 8
4.1. HELLO Message Generation . . . . . . . . . . . . . . . . . 7 4.1. Nodes and Interfaces . . . . . . . . . . . . . . . . . . . 8
4.2. HELLO message content . . . . . . . . . . . . . . . . . . 8 4.2. Information Base Overview . . . . . . . . . . . . . . . . 9
4.3. Node Behavior . . . . . . . . . . . . . . . . . . . . . . 8 4.3. Signaling Overview . . . . . . . . . . . . . . . . . . . . 10
5. Local Information Base . . . . . . . . . . . . . . . . . . . . 10 4.3.1. HELLO Message Generation . . . . . . . . . . . . . . . 10
5.1. Local Interface Set . . . . . . . . . . . . . . . . . . . 10 4.3.2. HELLO Message Content . . . . . . . . . . . . . . . . 11
6. Neighborhood Information Base . . . . . . . . . . . . . . . . 11 5. Protocol Parameters and Constants . . . . . . . . . . . . . . 12
6.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . . . 11 5.1. Interface Parameters . . . . . . . . . . . . . . . . . . . 12
6.2. Symmetric Neighbor Set . . . . . . . . . . . . . . . . . . 12 5.1.1. Message Intervals . . . . . . . . . . . . . . . . . . 12
6.3. Neighborhood Address Association Set . . . . . . . . . . . 13 5.1.2. Information Validity Times . . . . . . . . . . . . . . 13
6.4. 2-Hop Neighbor Set . . . . . . . . . . . . . . . . . . . . 13 5.1.3. Link Quality . . . . . . . . . . . . . . . . . . . . . 14
7. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 15 5.1.4. Jitter . . . . . . . . . . . . . . . . . . . . . . . . 14
7.1. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 15 5.2. Node Parameters . . . . . . . . . . . . . . . . . . . . . 15
7.1.1. Local Interface Block . . . . . . . . . . . . . . . . 16 5.2.1. Information Validity Time . . . . . . . . . . . . . . 15
7.1.2. Address Block TLVs . . . . . . . . . . . . . . . . . . 16 5.3. Parameter Change Constraints . . . . . . . . . . . . . . . 15
8. Local Information Base Changes . . . . . . . . . . . . . . . . 17 5.4. Constants . . . . . . . . . . . . . . . . . . . . . . . . 16
8.1. Adding a MANET Interface . . . . . . . . . . . . . . . . . 17 6. Local Information Base . . . . . . . . . . . . . . . . . . . . 17
8.2. Removing a MANET Interface . . . . . . . . . . . . . . . . 17 6.1. Local Interface Set . . . . . . . . . . . . . . . . . . . 17
8.3. Adding an Address to a MANET Interface . . . . . . . . . . 18 7. Interface Information Base . . . . . . . . . . . . . . . . . . 18
8.4. Removing an Address from a MANET Interface . . . . . . . . 18 7.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . . . 18
8.5. Changing the Principal Address of a MANET Interface . . . 18 7.2. 2-Hop Set . . . . . . . . . . . . . . . . . . . . . . . . 19
9. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 19 8. Node Information Base . . . . . . . . . . . . . . . . . . . . 20
9.1. HELLO Message: Transmission . . . . . . . . . . . . . . . 20 8.1. Neighbor Set . . . . . . . . . . . . . . . . . . . . . . . 20
9.1.1. HELLO Message: Jitter . . . . . . . . . . . . . . . . 21 8.2. Lost Neighbor Set . . . . . . . . . . . . . . . . . . . . 20
10. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 22 9. Local Information Base Changes . . . . . . . . . . . . . . . . 21
10.1. Populating the Link Set . . . . . . . . . . . . . . . . . 22 9.1. Adding an Interface . . . . . . . . . . . . . . . . . . . 21
10.2. Populating the Symmetric Neighbor Set . . . . . . . . . . 23 9.2. Removing an Interface . . . . . . . . . . . . . . . . . . 21
10.3. Populating the Neighborhood Address Association Set . . . 24 9.3. Adding an Address to an Interface . . . . . . . . . . . . 22
10.4. Populating the 2-Hop Neighbor Set . . . . . . . . . . . . 25 9.4. Removing an Address from an Interface . . . . . . . . . . 22
10.5. Neighborhood Changes . . . . . . . . . . . . . . . . . . . 26 10. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 23
11. Link Hysteresis . . . . . . . . . . . . . . . . . . . . . . . 27 10.1. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 23
11.1. Link Quality . . . . . . . . . . . . . . . . . . . . . . . 28 10.1.1. Local Interface Block . . . . . . . . . . . . . . . . 23
12. Proposed Values for Constants . . . . . . . . . . . . . . . . 29 10.1.2. Neighbor Address Blocks . . . . . . . . . . . . . . . 24
12.1. Message Intervals . . . . . . . . . . . . . . . . . . . . 29 11. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 26
12.2. Holding Times . . . . . . . . . . . . . . . . . . . . . . 29 11.1. HELLO Message Specification . . . . . . . . . . . . . . . 26
12.3. Hysteresis values . . . . . . . . . . . . . . . . . . . . 29 11.2. HELLO Message Transmission . . . . . . . . . . . . . . . . 27
12.4. Jitter Times . . . . . . . . . . . . . . . . . . . . . . . 30 11.2.1. HELLO Message Jitter . . . . . . . . . . . . . . . . . 27
12.5. Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 12. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 29
13. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 31 12.1. Updating the Neighbor Set . . . . . . . . . . . . . . . . 29
13.1. Multicast Addresses . . . . . . . . . . . . . . . . . . . 31 12.2. Updating the Lost Neighbor Set . . . . . . . . . . . . . . 31
13.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 31 12.3. Updating the Link Set . . . . . . . . . . . . . . . . . . 31
13.3. TLV Types . . . . . . . . . . . . . . . . . . . . . . . . 31 12.4. Updating the 2-Hop Set . . . . . . . . . . . . . . . . . . 32
13.4. LINK_STATUS and OTHER_NEIGHB Values . . . . . . . . . . . 32 13. Other Information Base Changes . . . . . . . . . . . . . . . . 34
14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 33 13.1. Link Tuple Not Symmetric . . . . . . . . . . . . . . . . . 34
14.1. Normative References . . . . . . . . . . . . . . . . . . . 33 13.2. Link Tuple Symmetric . . . . . . . . . . . . . . . . . . . 35
14.2. Informative References . . . . . . . . . . . . . . . . . . 33 13.3. Link Tuple Heard Timeout . . . . . . . . . . . . . . . . . 36
Appendix A. Address Block TLV Combinations . . . . . . . . . . . 34 14. Link Quality . . . . . . . . . . . . . . . . . . . . . . . . . 37
Appendix B. HELLO Message Example . . . . . . . . . . . . . . . 35 14.1. Deployment Without Link Quality . . . . . . . . . . . . . 37
Appendix C. Time TLVs . . . . . . . . . . . . . . . . . . . . . 37 14.2. Basic Principles of Link Quality . . . . . . . . . . . . . 37
C.1. Representing Time . . . . . . . . . . . . . . . . . . . . 37 14.3. When Link Quality Changes . . . . . . . . . . . . . . . . 38
C.2. General Time TLV Structure . . . . . . . . . . . . . . . . 37 14.4. Updating Link Quality . . . . . . . . . . . . . . . . . . 39
C.3. Message TLVs . . . . . . . . . . . . . . . . . . . . . . . 39 15. Proposed Values for Parameters and Constants . . . . . . . . . 40
C.3.1. VALIDITY_TIME TLV . . . . . . . . . . . . . . . . . . 39 15.1. Message Interval Interface Parameters . . . . . . . . . . 40
C.3.2. INTERVAL_TIME TLV . . . . . . . . . . . . . . . . . . 39 15.2. Information Validity Time Interface Parameters . . . . . . 40
Appendix D. Message Jitter . . . . . . . . . . . . . . . . . . . 40 15.3. Information Validity Time Node Parameters . . . . . . . . 40
D.1. Jitter . . . . . . . . . . . . . . . . . . . . . . . . . . 40 15.4. Link Quality Interface Parameters . . . . . . . . . . . . 40
D.1.1. Periodic message generation . . . . . . . . . . . . . 40 15.5. Jitter Interface Parameters . . . . . . . . . . . . . . . 40
D.1.2. Externally triggered message generation . . . . . . . 41 15.6. Constants . . . . . . . . . . . . . . . . . . . . . . . . 40
D.1.3. Message forwarding . . . . . . . . . . . . . . . . . . 42 16. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 41
D.1.4. Maximum Jitter Determination . . . . . . . . . . . . . 43 16.1. Message Types . . . . . . . . . . . . . . . . . . . . . . 41
Appendix E. Utilizing Link Layer Information . . . . . . . . . . 44 16.2. TLV Types . . . . . . . . . . . . . . . . . . . . . . . . 41
Appendix F. Security Considerations . . . . . . . . . . . . . . 46 16.3. LINK_STATUS and OTHER_NEIGHB Values . . . . . . . . . . . 41
Appendix F.1. Invalid HELLO messages . . . . . . . . . . . . . . . 46 17. References . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Appendix G. Flow and Congestion Control . . . . . . . . . . . . 48 17.1. Normative References . . . . . . . . . . . . . . . . . . . 43
Appendix H. Contributors . . . . . . . . . . . . . . . . . . . . 49 17.2. Informative References . . . . . . . . . . . . . . . . . . 43
Appendix I. Acknowledgements . . . . . . . . . . . . . . . . . . 50 Appendix A. Address Block TLV Combinations . . . . . . . . . . . 44
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 51 Appendix B. HELLO Message Example . . . . . . . . . . . . . . . 45
Intellectual Property and Copyright Statements . . . . . . . . . . 52 Appendix C. Constraints . . . . . . . . . . . . . . . . . . . . 47
Appendix D. Security Considerations . . . . . . . . . . . . . . 49
Appendix D.1. Invalid HELLO messages . . . . . . . . . . . . . . . 49
Appendix E. Flow and Congestion Control . . . . . . . . . . . . 51
Appendix F. Contributors . . . . . . . . . . . . . . . . . . . . 52
Appendix G. Acknowledgements . . . . . . . . . . . . . . . . . . 53
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 54
Intellectual Property and Copyright Statements . . . . . . . . . . 55
1. Introduction 1. Introduction
This document describes a neighborhood discovery protocol (NHDP) for This document describes a neighborhood discovery protocol (NHDP) for
a mobile ad hoc network (MANET). The protocol uses an exchange of a mobile ad hoc network (MANET) [7]. This protocol uses an exchange
HELLO messages in order that each node can determine its 1-hop and of HELLO messages in order that each node can determine the presence
symmetric 2-hop neighborhoods. and status of its 1-hop and symmetric 2-hop neighbors. This protocol
is designed to maintain this information in the presence of a dynamic
network topology.
This specification describes both this HELLO message exchange, the The information maintained by this protocol may be used by other
protocols, such as MANET routing protocols, for determining local
connectivity and node configuration.
This specification describes both the HELLO message exchange, the
messages being defined as instances of the specification [1], and the messages being defined as instances of the specification [1], and the
information storage required for neighborhood discovery. information storage required for neighborhood discovery.
This protocol makes no assumptions about the underlying link layer, This protocol makes no assumptions about the underlying link layer,
other than support of link local multicast. Link layer information other than support of link local multicast. Link layer information
and notifications may be used if available and applicable. may be used if available and applicable.
This protocol is based on the neighborhood discovery process This protocol is based on the neighborhood discovery process
contained in the Optimized Link State Routing Protocol (OLSR) [3]. contained in the Optimized Link State Routing Protocol (OLSR) [6].
2. Terminology 2. Terminology
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC2119 [2]. document are to be interpreted as described in RFC2119 [5].
The terms "packet", "message", "address block", "TLV", and "TLV The terms "packet", "message", "address", "address block", "TLV", and
block" in this document are to be interpreted as described in [1]. "TLV block" in this document are to be interpreted as described in
[1].
Additionally, this document uses the following terminology: Additionally, this document uses the following terminology:
Node - A MANET router which implements this neighborhood discovery Node - A MANET router which implements this neighborhood discovery
protocol. protocol.
MANET interface - A network device participating in a MANET and Interface - A network device, configured and assigned one or more IP
using this neighborhood discovery protocol. A node may have
several MANET interfaces, each being assigned one or more IP
addresses. addresses.
MANET interface - An interface participating in a MANET and using
this neighborhood discovery protocol. A node may have several
MANET interfaces.
Heard - A MANET interface of node X is considered heard on a MANET
interface of a node Y if the latter can receive traffic from the
former.
Link - A pair of MANET interfaces from two different nodes, where at Link - A pair of MANET interfaces from two different nodes, where at
least one interface is able to receive traffic from the other. least one interface is heard by the other.
Symmetric link - A link where both MANET interfaces are able to Symmetric link - A link where both MANET interfaces are heard by the
receive traffic from the other. other.
1-hop neighbor - A node X is a 1-hop neighbor of a node Y if node Y 1-hop neighbor - A node X is a 1-hop neighbor of a node Y if a MANET
can hear node X (i.e. a link exists from a MANET interface on node interface of node X is heard by a MANET interface of node Y.
X to a MANET interface on node Y).
Symmetric 1-hop neighbor - A node X is a symmetric 1-hop neighbor of 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 a node Y if a symmetric link exists between a MANET interface on
X to a MANET interface on node Y. node X and a MANET interface on node Y.
Symmetric 2-hop neighbor - A node X is a symmetric 2-hop neighbor of 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 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 neighbor of node Y, but is not node Y itself.
1-hop neighborhood - The 1-hop neighborhood of a node X is the set 1-hop neighborhood - The 1-hop neighborhood of a node X is the set
of the 1-hop neighbors of node X. of the 1-hop neighbors of node X.
Symmetric 1-hop neighborhood - The symmetric 1-hop neighborhood of a 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. 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 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. 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 (This may include nodes in the 1-hop neighborhood, or even in the
symmetric 1-hop neighborhood, of node X.) symmetric 1-hop neighborhood, of node X.)
Constant - A constant is a numerical value which MUST be the same
for all MANET interfaces of all nodes in the MANET, at all times.
Interface parameter - An interface parameter is a boolean or
numerical value, specified separately for each MANET interface of
each node. A node MAY change interface parameter values at any
time, subject to some constraints.
Node parameter - A node parameter is a boolean or numerical value,
specified for each node. A node MAY change node parameter values
at any time, subject to some constraints.
3. Applicability Statement 3. Applicability Statement
This neighborhood discovery protocol supports nodes which have one or This neighborhood discovery protocol supports nodes which each have
more interfaces participating in the MANET. It provides each node one or more interfaces participating in the MANET [7]. It provides
with local topology information up to two hops away. This each node with local topology information up to two hops away. This
information is made available to other protocols through a information is made available to other protocols through Interface
Neighborhood Information Base, described in Section 6. Information Bases and a Node Information Base, described in Section 7
and Section 8.
The protocol is designed to work in networks where messages may be The protocol is designed to work in networks with a dynamic topology,
lost, such as due to collisions in wireless networks. If relevant and where messages may be lost, such as due to collisions in wireless
link layer information is available then it may be used by this networks. If relevant link layer information is available then it
protocol. may be used by this protocol.
This protocol to works in a completely distributed manner and does This protocol is designed to work in a completely distributed manner,
not depend on any central entity. It does not require any changes to and does not depend on any central entity. It does not require any
the format of IP packets, thus any existing IP stack can be used as changes to the format of IP packets, thus any existing IP protocol
is. stack can be used as is. It can use the link local multicast address
and MANET UDP port specified in [2].
This protocol uses the packet and message formats specified in [1]. This protocol uses the packet and message formats specified in [1].
HELLO messages specified by this protocol may be extended using the HELLO messages specified by this protocol may be extended using the
TLV mechanisms described in [1]. For example, if multipoint relays TLV mechanisms described in [1]. For example, if multipoint relays
(MPRs) are to be calculated similarly to as in OLSR [3] and signaled (MPRs) are to be calculated similarly to as in OLSR [6] and signaled
to neighbors, then this information may be added to HELLO messages to neighbors, then this information may be added to HELLO messages
using an address block TLV. HELLO messages can also be transmitted using an address block TLV. HELLO messages can also be transmitted
in packets with messages from other protocols that also use [1]. in packets with messages from other protocols that also use [1].
4. Protocol Overview and Functioning 4. Protocol Overview and Functioning
This protocol specifies local (one hop) signaling that: This protocol specifies local (one hop) signaling that:
o advertises the presence of a node and its MANET interfaces; o Advertises the presence of a node and its interfaces.
o discovers links to adjacent nodes; o Discovers links from adjacent nodes.
o performs bidirectionality checks on the discovered links; o Performs bidirectionality checks on the discovered links.
o advertises discovered links and whether each is symmetric to its o Advertises discovered links, and whether each is symmetric, to its
1-hop neighbors and hence discover symmetric 2-hop neighbors; 1-hop neighbors, and hence discovers symmetric 2-hop neighbors.
o maintains an information base describing discovered links and o Maintains information bases describing discovered links, their
their status, 1-hop neighbors and their MANET interfaces, MANET interface addresses and status, current and former 1-hop
symmetric 1-hop neighbors and symmetric 2-hop neighbors. neighbors, and symmetric 2-hop neighbors.
4.1. Nodes and Interfaces
In order for a node to participate in a MANET, it MUST have at least
one, possibly more, MANET interfaces. Each MANET interface:
o Is characterized by a set of interface parameters, defining the
behavior of this interface. Each MANET interface MAY be
individually parameterized to accommodate the characteristics
experienced and the behavior desired on that interface.
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. Each MANET interface has its
own Interface Information Base.
o Generates and processes HELLO messages, according to the interface
parameters for that interface.
In addition to a set of MANET interfaces as described above, each
node has:
o A Local Information Base, containing the IP addresses of the
interfaces of this node.
o A Node Information Base, recording information regarding current
and recently lost symmetric 1-hop neighbors of this node.
A node may have both MANET interfaces and non-MANET interfaces.
Interfaces of both of these types are recorded in a node's Local
Information Base, which is used, but not updated, by the signaling of
this protocol.
4.2. Information Base Overview
Each node maintains a Local Information Base, which contains:
o The Local Interface Set, which consists of Local Interface Tuples,
each of which records the addresses of an interface of the node.
Each node maintains, for each of its MANET interfaces, an Interface
Information Base, which contains:
o A Link Set, which consists of Link Tuples, each of which records
information about a current or recently lost link from a MANET
interface of a 1-hop neighbor to this MANET interface. A Link
Tuple for a lost link is maintained for purposes of advertisement
in HELLO messages and hence accelerated removal of this link from
the relevant 1-hop neighbors' Link Sets. Link quality
information, if used and available, may be recorded in a Link
Tuple; if this indicates that a link is of too low quality to be
currently useable, then that link is also treated as lost.
o A 2-Hop Set, which consists of 2-Hop Tuples, each of which records
a MANET interface of a symmetric 1-hop neighbor, and an address of
a symmetric 2-hop neighbor of this node. The former MANET
interface must have a symmetric link to this interface, and the
former node must be a symmetric 1-hop neighbor of the latter node.
The 2-Hop Set is updated by the signaling of this protocol, but is
not itself reported in that signaling.
Each node maintains a Node Information Base, which contains:
o The Neighbor Set, which consists of Neighbor Tuples, each of which
records all interface addresses of a 1-hop neighbor. There MUST
be a current link from a MANET interface of this 1-hop neighbor to
a MANET interface of this node, although this link MAY be
currently considered as lost due to insufficient link quality.
Neighbor Tuples are maintained in the Neighbor Set as long as
there are corresponding current Link Tuples in the Link Set. A
Neighbor Tuple allows all addresses of all interfaces of a 1-hop
neighbors to be associated with each other, including addresses of
interfaces not represented in the Link Set. Neighbor Tuples allow
all addresses of interfaces of symmetric 1-hop neighbors to be
included in HELLO messages on all MANET interfaces of this node.
o The Lost Neighbor Set, which consists of Lost Neighbor Tuples,
each of which records an address of an interface of a recently
lost symmetric 1-hop neighbor. Lost Neighbor Tuples allow
advertising such addresses as lost, in order that these addresses
can be removed from other nodes' 2-Hop Sets.
These sets 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.
This protocol contains a signaling mechanism for maintaining the
Interface Information Bases and the Node Information Base. If
information from the link layer, or any other source, is available
and appropriate, it may be used to update these. Such updates are
subject to the constraints specified in Appendix C.
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 is associated with each link in the Link Set, and links with
insufficient link quality are considered lost. Modifying the link
quality of a link 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, it is not used in
signaling, and nodes may interoperate whether they are using the
same, different, or no, link quality information.
4.3. Signaling Overview
Signaling consists of a single type of message, known as a HELLO Signaling consists of a single type of message, known as a HELLO
message. A HELLO message identifies its originator node and that message. Each node generates HELLO messages for each of its MANET
node's MANET interfaces and addresses. As a node receives HELLO interfaces. Each HELLO message identifies that MANET interface, and
messages and populates its information base, a list of 1-hop reports the other interfaces of the node. Each HELLO message
neighbors' MANET interface addresses and their link status (lost, includes information from the Link Set of the Interface Information
symmetric or heard) is included in subsequent HELLO messages. Thus, Base of the MANET interface, and from the Node Information Base of
the periodic transmission allows nodes to continuously track changes the node.
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 4.3.1. HELLO Message Generation
HELLO messages MAY be sent: HELLO messages are generated by a node for each of its MANET
interfaces, and MAY be sent:
o Proactively, at a regular interval, known as HELLO_INTERVAL. o Proactively, at a regular interval, known as HELLO_INTERVAL.
HELLO_INTERVAL may be fixed, as suggested in Section 12, or may be HELLO_INTERVAL may be fixed, or may be dynamic. For example
dynamic. For example HELLO_INTERVAL may be backed off due to HELLO_INTERVAL may be backed off due to congestion or network
congestion or network stability. Note that if HELLO_INTERVAL is stability.
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, o As a response to a change in the node itself, or its 1-hop
for example on first becoming active or in response to a new, neighborhood, for example on first becoming active or in response
broken or changed status link. to a new, broken, or changed status link.
o In a combination of these proactive and responsive mechanisms. o In a combination of these proactive and responsive mechanisms.
Jittering of HELLO message generation and transmission, as described Jittering of HELLO message generation and transmission, as described
in Section 9.1, MAY be used if appropriate. in Section 11.2, MAY be used if appropriate.
HELLO messages are sent independently on each MANET interface. HELLO messages are generated independently on each MANET interface of
a node. HELLO messages MAY be scheduled independently for each MANET
interface, or, interface parameters permitting, using the same
schedule for all MANET interfaces of a node.
4.2. HELLO message content 4.3.2. HELLO Message Content
Each HELLO message sent over a MANET interface need not contain all Each HELLO message sent over a MANET interface need not contain all
of the information appropriate to that MANET interface, however: of the information appropriate to that MANET interface, however:
o A HELLO message MUST contain all of its own local interface o A HELLO message MUST contain all of the addresses in the Local
information. Interface Set of the node to which the MANET interface belongs.
o Within every time interval of length REFRESH_INTERVAL, HELLO o Within every time interval of length REFRESH_INTERVAL, the HELLO
messages sent over a MANET interface MUST include all of the messages sent on each MANET interface of a node must collectively
information appropriate to that interface in at least one HELLO include:
message sent on that interface. This applies to otherwise purely
responsive nodes as well as proactive nodes. * All of the information in the Link Set of the Interface
Information Base of that MANET interface (other than link
quality and information relating to pending links).
* All of the information in the Node Information Base of that
node.
This applies to otherwise purely responsive nodes as well as
proactive nodes. In either case it means that all information
appropriate to that MANET interface will have always been
transmitted, in one or more HELLO messages, since the time
REFRESH_INTERVAL ago.
o A HELLO message MUST include a VALIDITY_TIME message TLV that o A HELLO message MUST include a VALIDITY_TIME message TLV that
indicates the length of time for which the message content is to indicates the length of time for which the message content is to
be considered valid and included in the receiving node's be considered valid, and included in the receiving node's
Neighborhood Information Base. Interface Information Base.
o A HELLO message SHOULD include an INTERVAL_TIME message TLV that o A periodically generated HELLO message SHOULD include an
indicates the current value of HELLO_INTERVAL. INTERVAL_TIME message TLV 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. Node Behavior 5. Protocol Parameters and Constants
A node MUST: The parameters and constants used in this specification are described
in this section.
o Respect a minimum interval, HELLO_MIN_INTERVAL, between successive 5.1. Interface Parameters
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 The interface parameters used by this specification may be classified
dynamically, changes do not invalidate the guarantees of into the following four categories:
Section 9.1.
o Maintain, based on received HELLO messages, estimates of its 1-hop o Message intervals
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 o Information validity times
and former 1-hop neighbors.
Symmetric Neighbor Set - Records the status of current and former o Link quality
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 o Jitter
the MANET interfaces of each 1-hop neighbor to be associated
with each other.
2-Hop Neighbor Set - Records the addresses of the MANET These are detailed in the following sections.
interfaces of symmetric 2-hop neighbors.
The information in the Link Set and Symmetric Neighbor Set MUST be Different MANET interfaces (on the same or on different nodes) MAY
maintained in order for a node to correctly generate HELLO employ different interface parameter values, and may change their
messages. interface parameter values dynamically, subject to the constraints
given in this section. A particular case is where all MANET
interfaces on all MANET nodes within a given MANET employ the same
set of interface parameter values.
5. Local Information Base 5.1.1. Message Intervals
A node maintains a Local Information Base that records information The following interface parameters regulate HELLO message
about its MANET interfaces. Each MANET interface MUST have at least transmissions over a given MANET interface.
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 HELLO messages serve two principal functions:
address of that interface. A node MAY choose which address is the
principal address in any manner; it SHOULD choose the address so as o To advertise this nodes own addresses to its 1-hop neighbors. The
to minimize changes of principal address. The selection of an frequency of these advertisements is regulated by the interface
address as a principal address only affects how the node organizes parameters HELLO_INTERVAL and HELLO_MIN_INTERVAL.
its information storage, it has no effect on the messages it creates
and sends. o To advertise this nodes 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 [4].
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 [4].)
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 node MUST include all
1-hop neighbor information which it is specified as sending in at
least one HELLO message on this MANET interface.
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 INTERVAL_TIME TLVs as defined in [3] are included in HELLO
messages, then HELLO_INTERVAL MUST be representable as described
in [3].
If REFRESH_INTERVAL > HELLO_INTERVAL, then a node may distribute its
neighbor advertisements between HELLO messages in any manner, subject
to the constraints above.
For a node 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.
5.1.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 information from their Link Sets.
L_HOLD_TIME can be set to zero if accelerated information removal
is not required.
H_HOLD_TIME - is used as the value in the VALIDITY_TIME TLV included
in all HELLO messages on this MANET interface.
The following constraints apply to these interface parameters:
o L_HOLD_TIME >= 0
o H_HOLD_TIME >= REFRESH_INTERVAL
o If HELLO messages can be lost then both SHOULD be significantly
greater than REFRESH_INTERVAL.
o H_HOLD_TIME MUST be representable as described in [3].
5.1.3. Link Quality
The following interface parameters manage the usage of link quality:
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.1.4. Jitter
If jitter, as defined in [4], is used then these parameters are as
follows:
HP_MAXJITTER - represents the value of MAXJITTER used in [4] for
periodically generated HELLO messages on this MANET interface.
HT_MAXJITTER - represents the value of MAXJITTER used in [4] for
externally triggered HELLO messages on this MANET interface.
For constraints on these interface parameters see [4].
5.2. Node Parameters
Only one node parameter is defined by this specification, in the
category of information validity time.
5.2.1. Information Validity Time
The following node 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 information from their 2-Hop Sets. N_HOLD_TIME can be set to
zero if accelerated information removal is not required.
The following constraint applies to this node parameter:
o N_HOLD_TIME >= 0
5.3. Parameter Change Constraints
This section presents guidelines, applicable if protocol parameters
are changed dynamically.
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. Additional
subsequent HELLO messages MAY be generated according to the
previous, shorter, HELLO_INTERVAL.
* If the HELLO_INTERVAL for a MANET interface decreases, then the
following HELLO messages on this MANET interface SHOULD be
generated according to this current, shorter, HELLO_INTERVAL.
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 SHOULD be changed.
N_HOLD_TIME
* If N_HOLD_TIME changes, then NL_time for all relevant Lost
Neighbor Tuples SHOULD 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.4. Constants
The constant C is used as specified in [3].
6. Local Information Base
A node maintains a Local Information Base that records information
about its local interfaces (MANET interfaces or otherwise). Each
such interface MUST have at least one address, and MAY have more than
one address. All addresses have an associated prefix length, which
is included with all addresses in the Local Information Base. If an
address otherwise does not have a prefix length then it is considered
to be equal to the address length. Two addresses are considered
equal if and only if their associated prefix lengths are also equal.
The Local Information Base is not modified by this protocol. This The Local Information Base is not modified by this protocol. This
protocol may respond to changes of this Local Information Base which protocol MAY respond to changes of this Local Information Base which
MUST reflect corresponding changes in the node's status. MUST reflect corresponding changes in the node's interface
configuration.
5.1. Local Interface Set 6.1. Local Interface Set
A node's Local Interface Set records its local MANET interfaces. It A node's Local Interface Set records its local interfaces. It
consists of Local Interface Tuples, one per MANET interface: consists of Local Interface Tuples, one per interface:
(I_local_iface_addr_list) (I_local_iface_addr_list, I_manet)
where: where:
I_local_iface_addr_list is a list of the addresses of this MANET I_local_iface_addr_list is a list of the addresses of this
interface, with the first of the listed addresses being considered interface.
as the principal address of the interface.
6. Neighborhood Information Base I_manet is a boolean flag, describing if this interface is a MANET
interface.
A node maintains a Neighborhood Information Base that records 7. Interface Information Base
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 A node maintains an Interface Information Base for each of its MANET
neighborhoods of another node, Y, concurrently. This allows node X interfaces. This records information about links to that MANET
to be immediately considered as a symmetric 2-hop neighbor by node Y interface and symmetric 2-hop neighbors which can be reached in two
if the link between them fails. hops using those links as the first hop. The Interface Information
Base includes the Link Set and the 2-Hop Set.
A MANET interface address can be present in both the Link Set and as
of a symmetric 2-hop neighbor. This allows the node with this MANET
interface address to be immediately considered as a symmetric 2-hop
neighbor if it fails to be a symmetric 1-hop neighbor.
All addresses MUST have an associated prefix length, which is All addresses MUST have an associated prefix length, which is
included in all addresses in the Neighborhood Information Base. included in all addresses in the Interface Information Base. Prefix
Prefix lengths are indicated in HELLO messages using the lengths are indicated in HELLO messages using the PREFIX_LENGTH TLV
PREFIX_LENGTH TLV specified in [1]; if an address has no such TLV, specified in [1]; if an address has no such TLV, then its prefix
then its prefix length is equal to the address length. Two addresses length is equal to the address length. Two addresses are considered
are considered equal if and only if their associated prefix lengths equal if and only if their associated prefix lengths are also equal.
are also equal.
6.1. Link Set 7.1. Link Set
A node's Link Set records its 1-hop neighborhood. It consists of A node's Link Set records links from other nodes which are, or
Link Tuples: recently were, 1-hop neighbors. It consists of Link Tuples, each
representing a single link:
(L_local_iface_addr, L_neighbor_iface_addr_list, L_SYM_time, (L_neighbor_iface_addr_list, L_HEARD_time,
L_ASYM_time, L_LOST_time, L_quality, L_pending, L_lost, L_time) L_SYM_time, L_quality, L_pending, L_lost, L_time)
where: 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 L_neighbor_iface_addr_list is a list of the addresses of the MANET
interface of the 1-hop neighbor; interface of the 1-hop neighbor;
L_SYM_time is the time until which the link to the 1-hop neighbor is L_HEARD_time is the time until which the MANET interface of the
considered symmetric; 1-hop neighbor would be considered heard if not considering link
quality;
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 L_SYM_time is the time until which the link to the 1-hop neighbor
neighbor is considered lost; if L_lost is true and L_LOST_time is would be considered symmetric if not considering link quality;
expired, then this Tuple MUST be removed;
L_quality is a dimensionless number between 0 (included) and 1
(included) describing the quality of a link;
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;
L_pending is a boolean flag, describing if a link is considered L_pending is a boolean flag, describing if a link is considered
pending (i.e. a candidate, but not yet established, link); pending (i.e. a candidate, but not yet established, link);
L_lost is a boolean flag, describing if a link is considered lost L_lost is a boolean flag, describing if a link is considered lost
due to link quality and hysteresis; due to link quality;
L_time specifies when this Tuple expires and MUST be removed. L_time specifies when this Tuple expires and MUST be removed.
The status of the link as obtained through simple message exchange, The status of the link, as obtained through HELLO message exchange,
denoted H_STATUS, can be derived based on the elements L_SYM_time and and also taking link quality into account, denoted L_status, is
L_ASYM_time as defined in Table 1. defined by:
+-------------+-------------+-----------+
| 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 1. If L_pending is true, then L_status = PENDING;
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;
2. otherwise, if L_lost is true, then L_STATUS = LOST; 3. otherwise, if L_SYM_time is not expired, then L_status =
SYMMETRIC;
3. otherwise, if L_LOST_time is not expired, then L_STATUS = LOST; 4. otherwise, if L_HEARD_time is not expired, then L_status = HEARD;
4. otherwise, L_STATUS = H_STATUS. 5. otherwise, L_status = LOST.
6.2. Symmetric Neighbor Set 7.2. 2-Hop Set
A node's Symmetric Neighbor Set records its symmetric 1-hop A node's 2-Hop Set records symmetric 2-hop neighbors, and the
neighborhood. It consists of Symmetric Neighbor Tuples: symmetric links to symmetric 1-hop neighbors through which the
symmetric 2-hop neighbors can be reached. It consists of 2-Hop
Tuples, each representing a single interface address of a symmetric
2-hop neighbor, and a single MANET interface of a symmetric 1-hop
neighbor.
(N_local_iface_addr, N_neighbor_iface_addr, N_SYM_time, N_time) (N2_neighbor_iface_addr_list, N2_2hop_iface_addr, N2_time)
where: where:
N_local_iface_addr is the principal address of the local MANET N2_neighbor_iface_addr_list is a list of the addresses of the MANET
interface to which the 1-hop neighbor has or had a symmetric link; interface of the symmetric 1-hop neighbor from which this
information was received;
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 N2_2hop_iface_addr is an address of an interface of a symmetric
to be a symmetric 1-hop neighbor; 2-hop neighbor which has a symmetric link (using any MANET
interface) to the indicated symmetric 1-hop neighbor;
N_time specifies when this Tuple expires and MUST be removed. N2_time specifies when this Tuple expires and MUST be removed.
The status of the 1-hop neighbor, denoted N_STATUS, can be derived 8. Node Information Base
based on the field N_SYM_time as defined in Table 2.
+-------------+-----------+ Each node maintains a Node Information Base that records information
| N_SYM_time | N_STATUS | about addresses of current and recently symmetric 1-hop neighbors.
+-------------+-----------+
| Expired | LOST |
| | |
| Not Expired | SYMMETRIC |
+-------------+-----------+
Table 2 All addresses MUST have an associated prefix length, which is
included in all addresses in the Node 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.3. Neighborhood Address Association Set 8.1. Neighbor Set
A node's Neighborhood Address Association Set records the MANET A node's Neighbor Set records all interface addresses of each 1-hop
interface configuration of its 1-hop neighbors. It consists of neighbor. It consists of Neighbor Tuples, each representing a single
Neighborhood Address Association Tuples: 1-hop neighbor:
(NA_neighbor_iface_addr_list, NA_time) (N_neighbor_iface_addr_list, N_symmetric)
where: where:
NA_neighbor_iface_addr_list is a list of interface addresses of a N_neighbor_iface_addr_list is a list of the interface addresses of a
1-hop neighbor; 1-hop neighbor;
NA_time specifies when this Tuple expires and MUST be removed. N_symmetric is a boolean flag, describing if this is a symmetric
1-hop neighbor.
6.4. 2-Hop Neighbor Set 8.2. Lost Neighbor Set
A node's 2-Hop Neighbor Set records its symmetric 2-hop neighborhood. A node's Lost Neighbor Set records addresses of all interfaces of
It consists of 2-Hop Neighbor Tuples: nodes 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:
(N2_local_iface_addr, N2_neighbor_iface_addr_list, (NL_neighbor_iface_addr, NL_time)
N2_2hop_iface_addr, N2_time)
where: where:
N2_local_iface_addr is the principal address of the local MANET NL_neighbor_iface_addr is an address of an interface of a node which
interface on which this information was received; recently was a symmetric 1-hop neighbor of this node;
N2_neighbor_iface_addr_list is a list of the addresses of the MANET NL_time specifies when this Tuple expires and MUST be removed.
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 9. Local Information Base Changes
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 The Local Information Base MUST change to respond to changes in the
removed. node's interfaces. The node MUST update its Interface and Node
Information Bases in response to such changes. If any changes in the
Interface and Node Information Bases satisfy any of the conditions
described in Section 13, then those changes must be applied
immediately, unless noted otherwise.
7. Packets and Messages A node MAY transmit HELLO messages in response to these changes.
The packet and message format used by this neighborhood discovery 9.1. Adding an Interface
protocol is defined in [1], which is used with the following
considerations:
o this protocol specifies one message type, the HELLO message; If an interface is added to the node 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 the 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 a new MANET interface.
o HELLO message header options may be used as specified by the 9.2. Removing an Interface
protocol which uses this neighborhood discovery protocol;
o HELLO messages MUST NOT be forwarded; If a MANET interface is removed from the node, then this MUST result
in removal of information from the Local Information Base and the
Neighborhood Information Base as follows:
o HELLO messages may be included in multi-message packets as 1. Remove the Local Interface Tuple that corresponds to the
specified in [1]; interface to be removed from the Local Interface Set.
o packet header options may be used as specified by the protocol 2. If the interface to be removed is a MANET interface (i.e. with
which uses this neighborhood discovery protocol. I_manet == true) then:
7.1. HELLO Messages 1. Remove the Interface Information Base for that MANET
interface;
A HELLO message MUST contain: 2. All Neighbor Tuples for which none of the addresses in its
N_neighbor_iface_addr_list are found in any
L_neighbor_iface_addr_list in any remaining Link Set, are
removed.
o A VALIDITY_TIME message TLV as specified in Appendix C, If a node removes the Local Interface Tuple that contains the
representing time value (at distance one hop) H_HOLD_TIME, which interface address that is used to define the node's originator
MUST NOT be less than REFRESH_INTERVAL. If HELLO messages may be address, as defined in [1], then the node MAY change originator
lost then H_HOLD_TIME SHOULD be a multiple of REFRESH_INTERVAL. address.
o An address block, and associated TLV block, known as the Local If the removed interface is the last MANET interface of the node,
Interface Block, as specified in Section 7.1.1. then there will be no remaining Interface Information Bases, and the
node will longer participate in this protocol.
A HELLO message which is transmitted at a regular interval SHOULD A HELLO message MAY be sent on all remaining MANET interfaces.
contain, and otherwise MAY contain:
o An INTERVAL_TIME message TLV as specified in Appendix C, 9.3. Adding an Address to an Interface
representing time value (at distance one hop) HELLO_INTERVAL.
A HELLO message MAY contain: 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:
o One or more address blocks, with associated address block TLVs, 1. The Neighbor Tuples, if any, whose N_neighbor_iface_addr_list
containing current or former 1-hop neighbors' MANET interface contains the added address, are removed.
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. 2. Any Link Tuples, in any Link Set, whose
L_neighbor_iface_addr_list contains:
7.1.1. Local Interface Block * the added address; OR
The first address block, plus following TLV block, in a HELLO message * any address in the N_neighbor_iface_addr_list of the removed
is known as the Local Interface Block. The Local Interface Block is Neighbor Tuples, if any
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 are removed; apply Section 13.1, but not Section 13.3.
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 3. Any Lost Neighbor Tuples whose NL_neighb_iface_addr is the added
for each MANET interface, and hence a HELLO message MAY contain more address, are removed.
than one address without an OTHER_IF TLV.
7.1.2. Address Block TLVs 4. Any 2-Hop Tuples whose N2_2hop_iface_addr is the added address,
are removed.
The three address block TLVs used in HELLO messages are specified in A HELLO message MAY be sent on all MANET interfaces.
Table 3.
+----------------+------+-------------------+-----------------------+ 9.4. Removing an Address from an Interface
| 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 If an address is removed from an interface then this is indicated by
the removal of an address from the appropriate
I_local_iface_addr_list. If this list is now empty then the
corresponding Local Interface Tuple MUST be removed.
8. Local Information Base Changes If a node removes the interface address that is used to define the
node's originator address, as defined in [1], then the node MAY
change originator address.
The Local Information Base MUST change to respond to changes in the A HELLO message MAY be sent on all MANET interfaces.
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 10. Packets and Messages
If a MANET interface is added to the node then this is indicated by The packet and message format used by this protocol is defined in
the addition of a Local Interface Tuple to the Local Interface Set. [1], which is used with the following considerations:
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 o This protocol specifies one message type, the HELLO message.
If a MANET interface is removed from the node, then this MUST result o HELLO message header options MAY be used as specified by a
be the removal of information from the Local Information Base and the protocol which uses this neighborhood discovery protocol.
Neighborhood Information Base as follows:
1. Identify the Local Interface Tuple from the Local Interface Set o HELLO messages MUST NOT be forwarded.
which corresponds to the interface to be removed, and:
1. all Link Tuples whose L_local_iface_addr is included in the o HELLO messages MAY be included in multi-message packets as
I_local_iface_addr_list of that Local Interface Tuple MUST be specified in [1].
removed;
2. all Symmetric Neighbor Tuples whose N_local_iface_addr is o Packet header options MAY be used as specified by a protocol which
included in the I_local_iface_addr_list of that Local uses this neighborhood discovery protocol.
Interface Tuple MUST be removed;
3. all 2-Hop Neighbor Tuples whose N2_local_iface_addr is 10.1. HELLO Messages
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 A HELLO message MUST contain:
Interface Set.
2. All Neighborhood Address Association Tuples for which none of the o A VALIDITY_TIME message TLV as specified in [3], representing
addresses in its NA_neighbor_iface_addr_list may be found in any H_HOLD_TIME for the transmitting MANET interface.
L_neighbor_iface_addr_list in the Link Set SHOULD be removed.
If the removed interface is the last MANET interface of the node, o An address block, with an associated TLV block, known as the Local
then the Neighborhood Information Base SHOULD be empty, and the node Interface Block, as specified in Section 10.1.1.
no longer participates in the protocol.
A HELLO message MAY be sent on all remaining MANET interfaces. A HELLO message which is transmitted periodically SHOULD contain, and
otherwise MAY contain:
8.3. Adding an Address to a MANET Interface o An INTERVAL_TIME message TLV as specified in [3], representing
HELLO_INTERVAL for the transmitting MANET interface.
If an address is added to a MANET interface then this is indicated by A HELLO message MAY contain:
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 o One or more address blocks, each with an associated TLV block,
known as Neighbor Address Blocks, as specified in Section 10.1.2.
If an address is removed from a MANET interface then this is o Other message TLVs.
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 10.1.1. Local Interface Block
If the principal address of a MANET interface of a node is changed The first address block, plus following TLV block, in a HELLO message
then this is indicated by a reordering of the appropriate is known as the Local Interface Block. The Local Interface Block is
I_local_iface_addr_list. The following changes MUST be made to the not distinguished in any way other than by being the first address
Local Information Base: block in the HELLO message.
1. all Link Tuples whose L_local_iface_addr is equal to the old The Local Interface Block MUST contain all of the addresses in that
first address in this I_local_iface_addr_list have that node's Local Interface Set. Those addresses, if any, which correspond
L_local_iface_addr set equal to the new first address in this to interfaces other than the MANET interface for which the HELLO
I_local_iface_addr_list; message is transmitted MUST be associated with a corresponding TLV
with Type == OTHER_IF as specified in Table 1. Addresses of the
MANET interface on which the HELLO message is transmitted MUST NOT be
associated with such a TLV.
2. all Symmetric Neighbor Tuples whose N_local_iface_addr is equal Note that a Local Interface Block MAY include more than one address
to the old first address in this I_local_iface_addr_list have for each MANET interface, and hence a HELLO message MAY contain more
that N_local_iface_addr set equal to the new first address in than one address without an OTHER_IF TLV.
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 | Name | Value Length | Description |
N2_local_iface_addr set equal to the new first address in this +--------------+-----------------+----------------------------------+
I_local_iface_addr_list. | OTHER_IF | 0 bits | Specifies that the address, in |
| | | the Local Interface Block of the |
| | | message, is an address |
| | | associated with an interface |
| | | other than the MANET interface |
| | | on which the message is |
| | | transmitted |
+--------------+-----------------+----------------------------------+
A HELLO message SHOULD NOT be sent in response to this change. Table 1
9. HELLO Message Generation 10.1.2. Neighbor Address Blocks
HELLO messages MUST be generated and transmitted independently on Address blocks, each with a following TLV block, in a HELLO message,
each MANET interface. If using the HELLO message interval after the Local Interface Block, are known as Neighbor Address
HELLO_INTERVAL then, following a HELLO message transmission on a Blocks. These Neighbor Address Blocks are not distinguished in any
MANET interface, another HELLO message MUST be sent on the same way other than by not being the first address block in the HELLO
interface after an interval not greater than HELLO_INTERVAL. Two message. A HELLO message MAY contain no Neighbor Address Blocks.
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 A Neighbor Address Block contains current or recently lost 1-hop
Section 7.1.1 as its first address block. neighbors' interface addresses, each of which is associated with
address block TLVs as described in Table 2. Other addresses MAY be
included in Neighbor Address Blocks, but MUST NOT be associated with
any of the TLVs specified in Table 2.
Other addresses which MUST be included in HELLO messages are: +--------------+-----------------+----------------------------------+
| Name | Value Length | Description |
+--------------+-----------------+----------------------------------+
| LINK_STATUS | 8 bits | Specifies the status of the link |
| | | from the indicated address |
| | | (LOST, SYMMETRIC or HEARD) |
| | | |
| OTHER_NEIGHB | 8 bits | Specifies that the address is |
| | | (SYMMETRIC) or was (LOST) of an |
| | | interface of a symmetric 1-hop |
| | | neighbor of the node |
| | | transmitting the HELLO message |
+--------------+-----------------+----------------------------------+
o addresses of 1-hop neighbors from the Link Set; Table 2
o addresses of 1-hop neighbors from the Symmetric Neighbor Set. A TLV with Type == LINK_STATUS and (Value == SYMMETRIC or Value ==
LOST) also performs the function of a TLV with Type == OTHER_IF and
the same value. The latter SHOULD NOT also be included. If a TLV
with Type == LINK_STATUS and Value == SYMMETRIC is combined with a
TLV with Type == OTHER_IF and Value == LOST then the latter MUST be
ignored, and SHOULD NOT be included. See Appendix A.
These addresses MUST NOT be included in the Local Interface Block. 11. HELLO Message Generation
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 Each MANET interface MUST generate HELLO messages according to the
(a neighbor address) in one or more Link Tuples whose specification in this section. HELLO message generation and
L_local_iface_addr is the principal address of the MANET scheduling MUST be according to the interface parameters for that
interface over which the HELLO message is to be sent (i.e. the MANET interface and MAY be independent for each MANET interface or,
first address listed in the corresponding interface parameters permitting, MANET interfaces MAY use the same
I_local_iface_addr_list), and whose L_STATUS does not equal schedule.
PENDING, include the neighbor address with an associated TLV
with:
* Type = LINK_STATUS; AND 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.
* Value = L_STATUS. 11.1. HELLO Message Specification
2. For each address which appears as an N_neighbor_iface_addr in one HELLO messages are generated independently on each MANET interface.
or more Symmetric Neighbor Tuples:
1. if this address has already been included with an associated A HELLO message MUST include a Local Interface Block, as specified in
TLV with Type == LINK_STATUS and Value == SYMMETRIC, do not Section 10.1.1, as its first address block.
add an associated TLV with Type == OTHER_NEIGHB;
2. otherwise if, for one or more of these Symmetric Neighbor Other addresses which MUST be included in Neighbor Address Blocks, as
Tuples, N_STATUS == SYMMETRIC, then include this specified in Section 10.1.2, in HELLO messages sent over a given
N_neighbor_iface_addr with an associated TLV with: MANET interface are:
+ Type = OTHER_NEIGHB; AND o Addresses of MANET interfaces of 1-hop neighbors from the Link Set
of the Interface Information Base for this MANET interface.
+ Value = SYMMETRIC. o Other addresses of symmetric 1-hop neighbors from the Neighbor Set
of this node's Node Information Base.
3. otherwise if, for all of these Symmetric Neighbor Tuples, o Addresses of MANET interfaces of previously symmetric or heard
N_STATUS == LOST, and this address has not already been 1-hop neighbors connected on this MANET interface from the Link
included with an associated TLV with Type == LINK_STATUS and Set of the Interface Information Base for this MANET interface.
Value == LOST, then include this N_neighbor_iface_addr with (These are advertised for a period equal to this interface's
L_HOLD_TIME after loss.)
o Other addresses of previously symmetric 1-hop neighbors from the
Lost Neighbor Set of this node's Node Information Base. (These
are advertised for a period equal to N_HOLD_TIME after loss.)
The addresses, and their associated TLVs, which may be included in
any HELLO message sent on this MANET interface (respecting
REFRESH_INTERVAL for this MANET interface) are:
1. For each address (henceforth linked address) which appears in a
Link Tuple in the Link Set for this MANET interface, for which
L_status does not equal PENDING, include the linked address with
an associated TLV with: an associated TLV with:
+ Type = OTHER_NEIGHB; AND * Type = LINK_STATUS; AND
+ Value = LOST. * Value = L_status.
On each of its MANET interfaces, for each specified 1-hop neighbor 2. For each address (henceforth neighbor address) which appears in
address and associated TLV, the address and associated TLV MUST be an N_neighbor_iface_addr_list in a Neighbor Tuple with
included in at least one HELLO message in every interval of length N_symmetric == true, and which has not already been included with
REFRESH_INTERVAL. an associated TLV with (Type == LINK_STATUS and Value ==
SYMMETRIC), include the neighbor address with an associated TLV
with:
* Type = OTHER_NEIGHB; AND
* Value = SYMMETRIC.
3. For each Lost Neighbor Tuple whose NL_neighbor_iface_addr
(henceforth lost address) has not already been included, include
the lost address with an associated TLV with:
* Type = OTHER_NEIGHB; AND
* Value = LOST.
If an address is specified with more than one associated TLV, then If an address is specified with more than one associated TLV, then
these TLVs MAY be independently included or excluded from each HELLO these TLVs MAY be independently included or excluded from each HELLO
messages as long as each such TLV is included associated with that message. Each such TLV MUST be included associated with that address
address in a HELLO message sent on that MANET interface in every in a HELLO message sent on that MANET interface in every interval of
interval of length REFRESH_INTERVAL. length equal to that MANET interface's parameter REFRESH_INTERVAL.
TLVs associated with the same address included in the same HELLO TLVs associated with the same address included in the same HELLO
message MAY be applied to the same or different copies of that message MAY be applied to the same or different copies of that
address. address.
9.1. HELLO Message: Transmission 11.2. 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 HELLO messages are transmitted in the packet/message format specified
and associated TLVs) must be sent again on each MANET interface by [1] using the "LL MANET Routers" multicast address specified by
within the old REFRESH_INTERVAL of the previous HELLO message that [2] as destination IP address, using the MANET UDP port specified in
included that information. [2].
9.1.1. HELLO Message: Jitter 11.2.1. HELLO Message Jitter
HELLO messages MAY be sent using periodic message generation or HELLO messages MAY be sent using periodic message generation or
externally triggered message generation. If using data link and externally triggered message generation. If using data link and
physical layers which are subject to packet loss due to collisions, physical layers which are subject to packet loss due to collisions,
HELLO messages SHOULD be jittered as described in Appendix D. HELLO messages SHOULD be jittered as described in [4].
Internally triggered message generation MAY be treated as if Internally triggered message generation (such as due to a change in
externally generated message generation, or MAY be not jittered. 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 HELLO messages MUST NOT be forwarded, and thus message forwarding
jitter does not apply to HELLO messages. jitter does not apply to HELLO messages.
Each form of jitter described in Appendix D requires a parameter Each form of jitter described in [4] requires a parameter MAXJITTER.
MAXJITTER. These parameters may be dynamic, and are specified by: These interface parameters may be dynamic, and are specified by:
o For periodic message generation: HP_MAXJITTER, which MUST be o For periodic message generation: HP_MAXJITTER, which MUST be
significantly less than HELLO_INTERVAL. significantly less than HELLO_INTERVAL.
o For externally triggered message generation: HT_MAXJITTER. If o For externally triggered message generation: HT_MAXJITTER. If
HELLO messages are also periodically generated then HT_MAXJITTER HELLO messages are also periodically generated, then HT_MAXJITTER
also MUST be significantly less than HELLO_INTERVAL. also MUST be significantly less than HELLO_INTERVAL.
When HELLO message generation is delayed in order that a HELLO When HELLO message generation is delayed in order that a HELLO
message is not sent within HELLO_MIN_INTERVAL of the previous HELLO message is not sent within HELLO_MIN_INTERVAL of the previous HELLO
message on the same MANET interface, then HELLO_MIN_INTERVAL SHOULD message on the same MANET interface, then HELLO_MIN_INTERVAL SHOULD
be reduced by jitter, with maximum reduction HP_MAXJITTER. In this be reduced by jitter, with maximum reduction HP_MAXJITTER. In this
case HP_MAXJITTER MUST NOT be greater than HELLO_MIN_INTERVAL. case HP_MAXJITTER MUST NOT be greater than HELLO_MIN_INTERVAL.
10. HELLO Message Processing 12. HELLO Message Processing
On receiving a HELLO message, a node MUST update its neighborhood On receiving a HELLO message, a node MUST first check if any address
information base. in its Local Interface Block is one of its interface addresses (i.e.
is in any I_local_iface_addr_list in the Local Interface Set). If so
then the HELLO message MUST be discarded.
Otherwise the receiving node MUST update its appropriate Interface
Information Base and its Node Information Base according to this
section. If any changes satisfy any of the conditions described in
Section 13 then the indicated consequences MUST be applied
immediately, unless noted otherwise.
For the purpose of this section, note the following definitions: For the purpose of this section, note the following definitions:
o the "validity time" of a message is calculated from the o "validity time" is calculated from the VALIDITY_TIME TLV of the
VALIDITY_TIME TLV of the HELLO message as specified in Appendix C; HELLO message as specified in [3].
o the "Receiving Address List" is the I_local_iface_addr_list o "Receiving Address List" is the I_local_iface_addr_list
corresponding to the MANET interface on which the HELLO message corresponding to the MANET interface on which the HELLO message
was received; was received
o the "Receiving Address" is the first address in the Receiving o "Neighbor Address List" is the list of the addresses contained in
Address List, i.e. is the principal address of the MANET interface the Local Interface Block of the HELLO message.
on which the HELLO message was received;
o the "Sending Address List" is the list of the addresses contained o "Sending Address List" is the list of the addresses contained in
in the Local Interface Block of the HELLO message which do not the Local Interface Block of the HELLO message which do not have
have an associated TLV with Type == OTHER_IF; an associated TLV with Type == OTHER_IF.
o the word EXPIRED indicates that a timer is set to a value clearly o EXPIRED indicates that a timer is set to a value clearly preceding
preceding the current time (e.g. current time - 1). the current time (e.g. current time - 1).
10.1. Populating the Link Set o "Removed Address List" is a list of addresses created by this
HELLO message processing which were formerly reported as local by
the node originating the HELLO message, but which are not included
in the Neighbor Address List. This list is initialized as empty.
On receiving a HELLO message, a node SHOULD update its Link Set: 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.
1. If there is no Link Tuple such that: 12.1. Updating the Neighbor Set
* L_local_iface_addr == Receiving Address; AND On receiving a HELLO message, the node MUST update its Neighbor Set
and populate the Removed Address List and Lost Address List:
* L_neighbor_iface_addr_list contains one or more addresses in 1. Find all Neighbor Tuples (hereafter matching Neighbor Tuples)
the Sending Address List. where:
then create a new Link Tuple with: * N_neighbor_iface_addr_list contains at least one address in
the Neighbor Address List.
* L_local_iface_addr = Receiving Address; 2. If there are no matching Neighbor Tuples, then:
* L_SYM_time = EXPIRED; 1. Create a new Neighbor Tuple with:
* L_quality = INITIAL_QUALITY; + N_neighbor_iface_addr_list = Neighbor Address List;
* L_pending = INITIAL_PENDING; + N_symmetric = false.
* L_lost = false; 3. If there is one matching Neighbor Tuple, then:
* L_LOST_time = EXPIRED;
* L_time = current time + validity time. 1. If the N_neighbor_iface_addr_list of the matching Neighbor
Tuple is not equal to the Neighbor Address List, then:
2. This Link Tuple (existing or new) is then modified as follows: 1. For each address (henceforth removed address) which is in
the N_neighbor_iface_addr_list, but not in the Neighbor
Address List:
1. If the node finds any address in the Receiving Address List 1. Add the removed address to the Removed 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 2. If N_symmetric == true, then add the removed address
with a TLV with Type == LINK_STATUS and (Value == HEARD to the Lost Address List.
or Value == SYMMETRIC) then:
- L_SYM_time = current time + validity time; 2. Update the matching Neighbor Tuple by:
- L_time = L_SYM_time + L_HOLD_TIME. - N_neighbor_iface_addr_list = Neighbor Address List.
2. Otherwise if any such address in the HELLO message is 4. If there are two or more matching Neighbor Tuples, then:
associated with a TLV with Type == LINK_STATUS and Value
== LOST then:
1. if L_STATUS == SYMMETRIC: 1. For each address (henceforth removed address) which is in the
N_neighbor_iface_addr_list of any of the matching Neighbor
Tuples:
o L_time = current time + max(validity time, 1. Add the removed address to the Removed Address List.
L_HOLD_TIME),
o L_SYM_time = EXPIRED. 2. If N_symmetric == true, then add the removed address to
the Lost Address List.
2. L_neighbor_iface_addr_list = Sending Address List; 2. Replace the matching Neighbor Tuples by a single Neighbor
Tuple with:
3. L_ASYM_time = current time + validity time; + N_neighbor_iface_addr_list = Neighbor Address List;
4. L_time = max(L_time, L_ASYM_time). + N_symmetric = false
10.2. Populating the Symmetric Neighbor Set 12.2. Updating the Lost Neighbor Set
On receiving a HELLO message, a node SHOULD update its Symmetric On receiving a HELLO message, a node MUST update its Lost Neighbor
Neighbor Set: Set:
1. If any address in the Receiving Address List is in an address 1. For each address (henceforth lost address) in the Lost Neighbor
block of the HELLO message, other than the Local Interface Block, List, if no Lost Neighbor Tuple with NL_neighbor_iface_addr ==
with an associated TLV with Type == LINK_STATUS and (Value == lost address exists, then add a Lost Neighbor Tuple with:
HEARD or Value == SYMMETRIC) then:
1. For each address (henceforth neighbor address) in the HELLO * NL_neighbor_iface_addr = lost address;
message's Local Interface Block where a corresponding link
tuple with L_STATUS == SYMMETRIC exists in the link set:
1. If there is no Symmetric Neighbor Tuple such that: * NL_time = current time + N_HOLD_TIME.
- N_local_iface_addr == Receiving Address; AND 12.3. Updating the Link Set
- N_neighbor_iface_addr == neighbor address, On receiving a HELLO message, a node MUST update its Link Set for the
MANET interface on which the HELLO message is received:
then create a new Symmetric Neighbor Tuple with: 1. Remove all addresses in the Removed Address List from the
L_neighbor_iface_addr_list of all Link Tuples.
- N_local_iface_addr = Receiving Address; 2. Remove all Link Tuples whose L_neighbor_iface_addr_list is now
empty; apply Section 13.1, but not Section 13.3.
- N_neighbor_iface_addr = neighbor address; 3. Find all Link Tuples (hereafter matching Link Tuples) where:
2. This Symmetric Neighbor Tuple (existing or new) is then * L_neighbor_iface_addr_list contains one or more addresses in
modified as follows: the Sending Address List.
- N_SYM_time = current time + validity time; 4. If there is more than one matching Link Tuple, then remove them
all; apply Section 13.1, but not Section 13.3.
- N_time = N_SYM_time + N_HOLD_TIME. 5. If no matching Link Tuples remain, then create a new matching
Link Tuple with:
2. Otherwise if any address in the Receiving Address List is in an * L_neighbor_iface_addr_list = empty;
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 * L_HEARD_time = EXPIRED;
message Local Interface Block, if there exists a Symmetric
Neighbor Tuple with:
+ N_local_iface_addr == Receiving Address; AND * L_SYM_time = EXPIRED;
+ N_neighbor_iface_addr == neighbor address, * L_quality = INITIAL_QUALITY;
then update this Symmetric Neighbor Tuple to have: * L_pending = INITIAL_PENDING;
+ N_SYM_time = EXPIRED; * L_lost = false;
* L_time = current time + validity time.
+ N_time = min(N_time, current time + N_HOLD_TIME). 6. The matching Link Tuple, existing or new, is then modified as
follows:
10.3. Populating the Neighborhood Address Association Set 1. If the MANET interface finds any address (henceforth
receiving address) in the Receiving Address List in a
Neighbor Address Block in the HELLO message, then the Link
Tuple is modified as follows:
On receiving a HELLO message, the node SHOULD update its Neighborhood 1. If any receiving address in the HELLO message is
Address Association Set: associated with a TLV with Type == LINK_STATUS and (Value
== HEARD or Value == SYMMETRIC) then:
1. Remove all Neighborhood Address Association Tuples where: - L_SYM_time = current time + validity time.
* NA_neighbor_iface_addr_list contains at least one address 2. Otherwise if any receiving address in the HELLO message
which is contained in the Local Interface Block of the is associated with a TLV with Type == LINK_STATUS and
received HELLO message, Value == LOST then:
and create a new Neighborhood Address Association Tuple with: 1. if L_SYM_time has not expired, then:
* NA_neighbor_iface_addr_list = list of all addresses contained 1. L_SYM_time = EXPIRED.
in the Local Interface Block of the received HELLO message;
* NA_time = current time + validity time. 2. if L_status == HEARD or SYMMETRIC, then:
10.4. Populating the 2-Hop Neighbor Set * L_time = current time + L_HOLD_TIME.
On receiving a HELLO message the node SHOULD update its 2-Hop 2. L_neighbor_iface_addr_list = Sending Address List.
Neighbor Set:
1. If there exists a Link Tuple with L_local_iface_addr == Source 3. L_HEARD_time = max(current time + validity time, L_SYM_time).
Address and for which L_STATUS == SYMMETRIC then:
1. For each address (henceforth 2-hop neighbor address) in an 4. If L_status == PENDING, then:
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: + L_time = max(L_time, L_HEARD_time).
5. Otherwise if L_status == HEARD or SYMMETRIC, then:
+ L_time = max(L_time, L_HEARD_time + L_HOLD_TIME).
12.4. Updating the 2-Hop Set
On receiving a HELLO message a node 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 with L_neighbor_iface_addr_list == Sending
Address List has L_STATUS == SYMMETRIC then:
1. For each address (henceforth 2-hop address) in a Neighbor
Address Block of the HELLO message, which is not in the
Neighbor Address List or in any I_local_iface_addr_list:
1. If the 2-hop address has an associated TLV with:
- Type == LINK_STATUS and Value == SYMMETRIC; OR - Type == LINK_STATUS and Value == SYMMETRIC; OR
- Type == OTHER_NEIGHB and Value == SYMMETRIC, - Type == OTHER_NEIGHB and Value == SYMMETRIC,
then, if there is no 2-Hop Neighbor Tuple such that: then, if there is no 2-Hop Tuple such that:
- N2_local_iface_addr == Receiving Address;
- N2_neighbor_iface_addr_list contains one or more - N2_neighbor_iface_addr_list contains one or more
addresses in the Sending Address List; AND addresses in the Sending Address List; AND
- N2_2hop_iface_addr == 2-hop neighbor address. - N2_2hop_iface_addr == 2-hop address.
then create a 2-Hop Neighbor Tuple with: then create a 2-Hop Neighbor Tuple with:
- N2_local_iface_addr = Receiving Address; - N2_2hop_iface_addr = 2-hop address.
- N2_2hop_iface_addr = 2-hop neighbor address.
This 2-Hop Neighbor Tuple (existing or new) is then This 2-Hop Tuple (existing or new) is then modified as
modified as follows: follows:
- N2_neighbor_iface_addr_list = Sending Address List; - N2_neighbor_iface_addr_list = Sending Address List;
- N2_time = current time + validity time. - N2_time = current time + validity time.
2. Otherwise if the 2-hop neighbor address has a TLV with: 2. Otherwise if the 2-hop address has a TLV with:
- Type == LINK_STATUS and (Value == LOST or Value == - Type == LINK_STATUS and (Value == LOST or Value ==
HEARD); OR HEARD); OR
- Type == OTHER_NEIGHB and Value == LOST; - Type == OTHER_NEIGHB and Value == LOST;
then remove all 2-Hop Neighbor Tuples with: then remove all 2-Hop Tuples with:
- N2_local_iface_addr == Receiving Address; AND
- N2_neighbor_iface_addr_list contains one or more - N2_neighbor_iface_addr_list contains one or more
addresses in the Sending Address List; AND addresses in the Sending Address List; AND
- N2_2hop_iface_addr == 2-hop neighbor address. - N2_2hop_iface_addr == 2-hop address.
10.5. Neighborhood Changes 13. Other Information Base Changes
If L_STATUS of a Link Tuple changes from SYMMETRIC to any other The Interface and Node Information Bases MUST be changed when some
status, due to any of: events occur. These events may result from HELLO message processing,
or may be otherwise generated (e.g. expiry of timers or link quality
changes).
o L_SYM_time expires; Events which cause changes in the Information Bases are:
o L_SYM_time is set to EXPIRED as result of processing a TLV with o A Link Tuple's state changes from symmetric, or the Link Tuple is
Type == LINK_STATUS and Value == LOST; removed.
o A change in L_quality resulting in L_quality < HYST_REJECT o A Link Tuple's state changes to symmetric.
then all 2-Hop Neighbor Tuples with: o A Link Tuple's L_HEARD_time expires, or the Link Tuple is removed.
o N2_local_iface_addr == L_local_iface_addr from the Link Tuple, o Local interface address changes, as specified in Section 9.
AND;
o N2_neighbor_iface_addr_list contains one or more addresses in the o Link quality changes, as specified in Section 14.
L_neighbor_iface_addr_list from the Link Tuple,
MUST be deleted. A node MAY report updated information in response to any of these
changes in HELLO message(s), subject to the constraints in
Section 11.
In this, or any other case of neighborhood change, a node MAY send a A node which transmits HELLO messages in response to such changes
HELLO message reporting updated information, subject to the SHOULD transmit a HELLO message:
constraints in Section 9.
11. Link Hysteresis 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).
Link hysteresis allows associating a L_quality value with a link. o Otherwise, on all those MANET interfaces whose Link Set changes
Using this L_quality in conjunction with two thresholds, HYST_ACCEPT such as to indicate a change in status of any 1-hop neighbors
and HYST_REJECT, as well as for each link a L_pending and a L_lost (including the addition or removal of any 1-hop neighbors, other
flag, Section 6.1 allows determining the L_STATUS of a link. than those considered pending).
The basic principles of link hysteresis are as follows: 13.1. 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_iface_addr_list contains
L_neighbor_iface_addr_list:
1. If there are no remaining Link Tuples for any MANET interface
with:
+ L_neighbor_iface_addr_list contained in
N_neighbor_iface_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_iface_addr_list, add a Lost Neighbor Tuple
with:
- NL_neighbor_iface_addr = neighbor address;
- NL_time = current time + N_HOLD_TIME.
13.2. 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 to have L_status == SYMMETRIC) then:
1. For the Neighbor Tuple whose N_neighbor_iface_addr_list includes
L_neighbor_iface_addr_list, set:
* N_symmetric = true.
2. Remove all Lost Neighbor Tuples whose LN_neighbor_iface_addr is
included in that N_neighbor_iface_addr_list.
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_iface_addr_list contains
L_neighbor_iface_addr_list, if no Link Tuples for any MANET
interface remain with:
* L_neighbor_iface_addr_list contained in
N_neighbor_iface_addr_list;
* L_HEARD_time is not expired;
then remove the Neighbor Tuple.
14. Link Quality
Link quality is a mechanism whereby a node 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.
For deployments where no link quality is used, the considerations in
Section 14.1 apply. For deployments were 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.
Link quality is used only locally by a node, and nodes may fully
interoperate whether they are using the same, different or no link
quality methods.
14.1. Deployment Without Link Quality
In order for a node to not employ link quality, the node MUST define:
o INITIAL_PENDING = false;
o INITIAL_QUALITY >= HYST_REJECT (there is no reason not to define
INITIAL_QUALITY = 1).
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 the value of INITIAL_QUALITY). 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 node does not advertise a neighbor interface in any state until o A node does not advertise a neighbor interface in any state until
L_quality is acceptable. If INITIAL_PENDING == true, this is such L_quality is acceptable:
that L_quality >= HYST_ACCEPT, otherwise this is such that
L_quality >= HYST_REJECT; to ensure the latter a node MUST NOT * If INITIAL_PENDING == true, then this is such that L_quality >=
define INITIAL_PENDING == false and INITIAL_QUALITY < HYST_REJECT. HYST_ACCEPT.
(A node also MUST NOT define INITIAL_PENDING == true and
INITIAL_QUALITY >= HYST_ACCEPT.) A link which is not yet * Otherwise this is such that L_quality >= HYST_REJECT. To
advertised has L_pending == true. ensure this, 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, o Once L_quality >= HYST_ACCEPT, the L_pending flag is set false,
indicating that the link can be advertised. indicating that the link can be advertised.
o A link for which L_pending == false is advertised until its o A link for which L_pending == false is advertised until its
L_quality drops below HYST_REJECT. L_quality drops below HYST_REJECT.
o If a link has L_pending == false and L_quality < HYST_REJECT, the 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 link is LOST and is advertised as such. This link is not
reconsidered as a candidate HEARD or SYMMETRIC link until reconsidered as a candidate HEARD or SYMMETRIC link until
L_quality >= HYST_ACCEPT. L_quality >= HYST_ACCEPT.
o A link which has an acceptable quality may be advertised as HEARD, o A link which has an acceptable quality may be advertised as HEARD,
SYMMETRIC or LOST according to the exchange of HELLO messages. SYMMETRIC or LOST according to the exchange of HELLO messages.
If L_quality for a link changes, the following actions MUST be taken: 14.3. When Link Quality Changes
1. if L_quality >= HYST_ACCEPT then the corresponding Link Tuple is 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: modified by:
* L_pending = false; 1. L_pending = false.
* L_lost = false; 2. L_lost = false.
* L_LOST_time = EXPIRED. 3. If L_status == HEARD or L_status == SYMMETRIC, then:
2. if L_quality < HYST_REJECT then the corresponding Link Tuple is + L_time = max(L_time, L_HEARD_time + L_HOLD_TIME)
modified by:
* L_lost = true 2. If L_status is not equal to PENDING, and L_quality < HYST_REJECT
* L_LOST_time = current time + L_HOLD_TIME then the corresponding Link Tuple is modified by:
Any corresponding Tuples in the Symmetric Neighbor Set and 2-Hop 1. If L_lost == false, then:
Neighbor Set MUST be removed.
If L_quality for a link is updated based on HELLO message reception, + L_lost = true
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 + L_time = min(L_time, current time + L_HOLD_TIME)
A node MAY never update link quality (L_quality). In this case the Any appropriate action indicted in Section 13 MUST also be taken.
node MUST define:
o INITIAL_PENDING = false; 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 instead the Link Tuple
MUST be created with the updated, from INITIAL_QUALITY, L_quality
value.)
o INITIAL_QUALITY >= HYST_REJECT (there is no reason not to define 14.4. Updating Link Quality
INITIAL_QUALITY = 1).
A node MAY update link quality based on any information available to A node MAY update link quality based on any information available to
it. Particular cases that MAY be used include: it. Particular cases that MAY be used include:
o Link layer information, see Appendix E. o Information from the link layer, such as signal to noise ratio.
o Receipt or loss of packets. Provided packets include a packet o Receipt or loss of packets. If packets include a packet sequence
sequence number as defined in [1], packets on a link SHOULD have number as defined in [1], then packets on a link SHOULD have
sequential packet sequence numbers, whether or not they include sequential packet sequence numbers, whether or not they include
HELLO messages. Link quality can be updated when a packet is HELLO messages. Link quality can be updated when a packet is
received based on, for example, whether the last N out of M received based on, for example, whether the last N out of M
packets on the link were received, or a "leaky integrator" packets on the link were received, or a "leaky integrator"
tracking packets. tracking packets.
o Receipt or loss of HELLO messages. If the maximum interval o Receipt or loss of HELLO messages. If the maximum interval
between HELLO messages is known (possibly by inclusion of a between HELLO messages is known (such as by inclusion of a message
message TLV with Type == INTERVAL_TIME as defined in Appendix C.2 TLV with Type == INTERVAL_TIME, as defined in [3], in HELLO
in HELLO messages) then the loss of HELLO messages can be messages) then the loss of HELLO messages can be determined
determined without the need to receive a HELLO message. Note that without the need to receive a HELLO message. Note that if this
if this case is combined with the previous case then care must be case is combined with the previous case then care must be taken to
taken to avoid "double counting" a lost HELLO message in a lost avoid "double counting" a lost HELLO message in a lost packet.
packet.
12. Proposed Values for Constants 15. Proposed Values for Parameters and Constants
This section lists proposed values for the constants used in the This section lists the parameters and constants used in the
specification of the protocol. specification of the protocol, and proposed values of each which may
be used when a single value of each is used.
12.1. Message Intervals 15.1. Message Interval Interface Parameters
o HELLO_INTERVAL = 2 seconds o HELLO_INTERVAL = 2 seconds
o REFRESH_INTERVAL = HELLO_INTERVAL
o HELLO_MIN_INTERVAL = HELLO_INTERVAL/4 o HELLO_MIN_INTERVAL = HELLO_INTERVAL/4
12.2. Holding Times o REFRESH_INTERVAL = HELLO_INTERVAL
15.2. Information Validity Time Interface Parameters
o H_HOLD_TIME = 3 x REFRESH_INTERVAL o H_HOLD_TIME = 3 x REFRESH_INTERVAL
o L_HOLD_TIME = H_HOLD_TIME o L_HOLD_TIME = H_HOLD_TIME
o N_HOLD_TIME = H_HOLD_TIME 15.3. Information Validity Time Node Parameters
12.3. Hysteresis values o N_HOLD_TIME = L_HOLD_TIME
If link quality is not changed then: 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_ACCEPT = 1
o HYST_REJECT = 0 o HYST_REJECT = 0
o INITIAL_QUALITY = 1 o INITIAL_QUALITY = 1
o INITIAL_PENDING = false o INITIAL_PENDING = false
Otherwise, i.e. if link quality is changed, then these parameters 15.5. Jitter Interface 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
12.4. Jitter Times
o HP_MAXJITTER = HELLO_INTERVAL/4 o HP_MAXJITTER = HELLO_INTERVAL/4
o HT_MAXJITTER = HELLO_INTERVAL/4 o HT_MAXJITTER = HP_MAXJITTER
12.5. Time 15.6. Constants
o C = 0.0625 second (1/16 second) o C = 0.0625 second (1/16 second)
In order to achieve interoperability, C MUST be the same on all 16. IANA Considerations
nodes.
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 16.1. Message Types
This specification defines one message type, which must be allocated This specification defines one message type, which must be allocated
from the "Assigned Message Types" repository of [1]. from the "Assigned Message Types" repository of [1].
+--------------------+-------+--------------------------------------+ +--------------+------+--------------------------------------+
| Mnemonic | Value | Description | | Name | Type | Description |
+--------------------+-------+--------------------------------------+ +--------------+------+--------------------------------------+
| HELLO | TBD | Local signaling | | 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 16.2. TLV Types
This specification defines three Address Block TLV types, which must This specification defines three Address Block TLV types, which must
be allocated from the "Assigned Address Block TLV Types" repository be allocated from the "Assigned Address Block TLV Types" repository
of [1]. of [1].
+--------------------+-------+--------------------------------------+ +--------------+------+---------------------------------------------+
| Mnemonic | Value | Description | | Name | Type | Description |
+--------------------+-------+--------------------------------------+ +--------------+------+---------------------------------------------+
| OTHER_IF | TBD | Specifies that the address, in the | | OTHER_IF | TBD | Specifies that the address, in the Local |
| | | Local Interface Block of the | | | | Interface Block, is an address associated |
| | | message, is an address associated | | | | with an interface other than the MANET |
| | | with a MANET interface other than | | | | interface on which the message is |
| | | the one on which the message is |
| | | transmitted | | | | transmitted |
| | | | | | | |
| LINK_STATUS | TBD | Specifies the status of the link to | | LINK_STATUS | TBD | Specifies the status of the link from the |
| | | the indicated address (LOST, | | | | indicated address (LOST, SYMMETRIC or |
| | | SYMMETRIC or HEARD) | | | | HEARD) |
| | | | | | | |
| OTHER_NEIGHB | TBD | Specifies that the address is | | OTHER_NEIGHB | TBD | Specifies that the address is (SYMMETRIC) |
| | | (SYMMETRIC) or was (LOST) of a MANET | | | | or recently was (LOST) of an interface of a |
| | | interface of a symmetric 1-hop | | | | symmetric 1-hop neighbor of the node |
| | | neighbor of the node transmitting | | | | transmitting the message |
| | | the HELLO message, but does not have | +--------------+------+---------------------------------------------+
| | | a matching or better LINK_STATUS TLV |
+--------------------+-------+--------------------------------------+
Table 6
13.4. LINK_STATUS and OTHER_NEIGHB Values 16.3. LINK_STATUS and OTHER_NEIGHB Values
The values which the LINK_STATUS TLV can use are the following: The values which the LINK_STATUS TLV can use are the following:
o LOST = 0 o LOST = 0
o SYMMETRIC = 1 o SYMMETRIC = 1
o HEARD = 2 o HEARD = 2
The values which the OTHER_NEIGHB TLV can use are the following: The values which the OTHER_NEIGHB TLV can use are the following:
o LOST = 0 o LOST = 0
o SYMMETRIC = 1 o SYMMETRIC = 1
14. References 17. References
14.1. Normative References 17.1. Normative References
[1] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, "Generalized [1] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, "Generalized
MANET Packet/Message Format", Work In MANET Packet/Message Format", Work In
Progress draft-ietf-manet-packetbb-03.txt, January 2007. Progress draft-ietf-manet-packetbb-04.txt, January 2007.
[2] Bradner, S., "Key words for use in RFCs to Indicate Requirement [2] Chakeres, I., "Internet Assigned Numbers Authority (IANA)
Allocations for the Mobile Ad hoc Networks (MANET) Working
Group", Work In Progress draft-ietf-manet-iana-04.txt, May 2007.
[3] Clausen, T. and C. Dearlove, "Representing multi-value time in
MANETs", Work In Progress draft-ietf-manet-timetlv-00.txt,
April 2007.
[4] Clausen, T., Dearlove, C., and B. Adamson, "Jitter
considerations in MANETs", Work In
Progress draft-ietf-manet-jitter-00.txt, April 2007.
[5] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", RFC 2119, BCP 14, March 1997. Levels", RFC 2119, BCP 14, March 1997.
14.2. Informative References 17.2. Informative References
[3] Clausen, T. and P. Jacquet, "The Optimized Link State Routing [6] Clausen, T. and P. Jacquet, "The Optimized Link State Routing
Protocol", RFC 3626, October 2003. Protocol", RFC 3626, October 2003.
[7] Macker, J. and S. Corson, "Mobile Ad hoc Networking (MANET):
Routing Protocol Performance Issues and Evaluation
Considerations", RFC 2501, January 1999.
Appendix A. Address Block TLV Combinations Appendix A. Address Block TLV Combinations
The algorithm for generating HELLO messages in Section 9 specifies The algorithm for generating HELLO messages in Section 11 specifies
which addresses MAY be included in the address blocks after the Local which addresses may be included in the address blocks after the Local
Interface Block, and with which associated TLVs. These TLVs may have Interface Block, and with which associated TLVs. These TLVs may have
Type == LINK_STATUS or Type == OTHER_NEIGHB, or both. TLVs with Type Type == LINK_STATUS or Type == OTHER_NEIGHB, or both. TLVs with Type
== LINK_STATUS may have three possible values (Value == HEARD, Value == LINK_STATUS may have three possible values (Value == HEARD, Value
== SYMMETRIC or Value == LOST), and TLVs of TYPE == OTHER_NEIGHB may == SYMMETRIC or Value == LOST), and TLVs of TYPE == OTHER_NEIGHB may
have two possible values (Value == SYMMETRIC or Value == LOST). When have two possible values (Value == SYMMETRIC or Value == LOST). When
both TLVs are associated with the same address only certain both TLVs are associated with the same address only certain
combinations of these TLV values are necessary, and are the only combinations of these TLV values are necessary, and are the only
combinations generated by the algorithm in Section 9. These combinations generated by the algorithm in Section 11. These
combinations are indicated in Table 7. combinations are indicated in Table 5.
Cells labeled with "Yes" indicate the possible combinations which are Cells labeled with "Yes" indicate the possible combinations which are
generated by the algorithm in Section 9. Cells labeled with "No" generated by the algorithm in Section 11. Cells labeled with "No"
indicate combinations not generated by the algorithm in Section 9, indicate combinations not generated by the algorithm in Section 11,
but which are correctly parsed and interpreted by the algorithm in but which are correctly parsed and interpreted by the algorithm in
Section 10. Section 12.
+----------------+----------------+----------------+----------------+ +----------------+----------------+----------------+----------------+
| | Type == | Type == | Type == | | | Type == | Type == | Type == |
| | OTHER_NEIGHB | OTHER_NEIGHB, | OTHER_NEIGHB, | | | OTHER_NEIGHB | OTHER_NEIGHB, | OTHER_NEIGHB, |
| | (absent) | Value == | Value == LOST | | | (absent) | Value == | Value == LOST |
| | | SYMMETRIC | | | | | SYMMETRIC | |
+----------------+----------------+----------------+----------------+ +----------------+----------------+----------------+----------------+
| Type == | No | Yes | Yes | | Type == | No | Yes | Yes |
| LINK_STATUS | | | | | LINK_STATUS | | | |
| (absent) | | | | | (absent) | | | |
skipping to change at page 34, line 49 skipping to change at page 44, line 49
| Type == | Yes | No | No | | Type == | Yes | No | No |
| LINK_STATUS, | | | | | LINK_STATUS, | | | |
| Value == | | | | | Value == | | | |
| SYMMETRIC | | | | | SYMMETRIC | | | |
| | | | | | | | | |
| Type == | Yes | Yes | No | | Type == | Yes | Yes | No |
| LINK_STATUS, | | | | | LINK_STATUS, | | | |
| Value == LOST | | | | | Value == LOST | | | |
+----------------+----------------+----------------+----------------+ +----------------+----------------+----------------+----------------+
Table 7 Table 5
Appendix B. HELLO Message Example Appendix B. HELLO Message Example
An example HELLO message, sent by an originator node with a single An example HELLO message, transmitted by an originator node with a
MANET interface, is as follows. The message uses IPv4 (four octet) single MANET interface, is as follows. The message uses IPv4 (four
addresses without prefix TLVs. The message is sent with a full octet) addresses without prefix TLVs. The message is transmitted
message header (message semantics octet is 0) with a hop limit of 1 with a full message header (message semantics octet is 0) with a hop
and a hop count of 0. The overall message length is 50 octets. 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 The message contains a message TLV block with content length 8 octets
containing two message TLVs, of types VALIDITY_TIME and containing two message TLVs, of types VALIDITY_TIME and
INTERVAL_TIME. Each uses a TLV with semantics value 4, indicating INTERVAL_TIME. Each uses a TLV with semantics value 4, indicating
that no start and stop indexes are included, and each has a value 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 length of 1 octet. The values included (0x68 and 0x50) are time
codes representing the default values of parameters H_HOLD_TIME and codes representing the default values of parameters H_HOLD_TIME and
HELLO_INTERVAL, respectively (6 seconds and 2 seconds). HELLO_INTERVAL, respectively (6 seconds and 2 seconds) assuming a
default value of constant C (0.0625 second).
The first address block contains 1 local interface address. The The first address block contains 1 local interface address. The
semantics octet value 2 indicates no address tail, and the head semantics octet value 2 indicates no address tail, and the head
length of 4 octets indicates no address mid sections. This address length of 4 octets indicates no address mid sections. This address
block has no TLVs (TLV block content length 0 octets). block has no TLVs (TLV block content length 0 octets).
The second, and last, address block contains 4 neighbor interface The second, and last, address block contains 4 neighbor interface
addresses. The semantics octet value 2 indicates no address tail, addresses. The semantics octet value 2 indicates no address tail,
the head length of 3 octets indicates address mid sections of one the head length of 3 octets indicates address mid sections of one
octet each. The following TLV block (content length 7 octets) octet each. The following TLV block (content length 7 octets)
skipping to change at page 37, line 5 skipping to change at page 47, line 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Head (cont) | Mid | Mid | Mid | | Head (cont) | Mid | Mid | Mid |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Mid |0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1| LINK_STATUS | | 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 | |0 0 0 1 0 1 0 0|0 0 0 0 0 1 0 0| HEARD | HEARD |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SYMMETRIC | LOST | | SYMMETRIC | LOST |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Appendix C. Time TLVs Appendix C. Constraints
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
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 <value>
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 <value> field (or
single value subfield) SHOULD be used.
The <value> field of a single value Time TLV is specified, using the
regular expression syntax of [1], by:
<value> = {<time><distance>}*<time>
where:
<time> is an 8 bit field containing a time code as defined in
Appendix C.1.
<distance> is an 8 bit field specifying a distance from the message
originator, in hops.
A single value <value> field thus consists of an odd number of
octets; with a repetition factor of n in the regular expression
syntax it contains 2n+1 octets, thus the <length> field of a single
value Time TLV, which MUST always be present, is given by:
o <length> = 2n+1
A single value <value> field may be thus represented by:
<t_1><d_1><t_2><d_2> ... <t_i><d_i> ... <t_n><d_n><t_default>
<d_1>, ... <d_n>, if present, MUST be a strictly increasing sequence.
Then, at the receiving node's distance from the originator node, the
time value indicated is that represented by the time code:
o <t_1>, if n > 0 and distance <= <d_1>;
o <t_i+1>, if n > 1 and <d_i> < distance <= <d_i+1> for some i such
that 1 <= i < n;
o <t_default> otherwise, i.e. if n == 0 or distance > <d_n>.
In a multivalue Time TLV, each single value subfield of the
multivalue Time TLV is defined as above. Note that [1] requires that
each single value subfield has the same length (i.e. the same value
of n) but they need not use the same values of <d_1> to <d_n>.
C.3. Message TLVs
Two message TLVs are defined, for signaling message validity time
(VALIDITY_TIME) and message interval (INTERVAL_TIME).
C.3.1. VALIDITY_TIME TLV
A VALIDITY TIME TLV is a message TLV that defines the validity time
of the information carried in the message in which the TLV is
contained. After this time the receiving node MUST consider the
message content to no longer be valid (unless repeated in a later
message). The validity time of a message MAY be specified to depend
on the distance from its originator. (This is appropriate if
messages are sent with different hop limits, so that receiving nodes
at greater distances receive information less frequently and must
treat is as valid for longer.)
A VALIDITY_TIME TLV is an example of a Time TLV specified as in
Appendix C.1.
C.3.2. INTERVAL_TIME TLV
An INTERVAL_TIME TLV is a message TLV that defines the maximum time
before another message of the same type as this message from the same
originator should be received. This interval time MAY be specified
to depend on the distance from the originator. (This is appropriate
if messages are sent with different hop limits, so that receiving
nodes at greater distances have an increased interval time.)
An INTERVAL_TIME TLV is an example of a Time TLV specified as in
Appendix C.1.
Appendix D. Message Jitter
Since NHDP employs periodic message transmission in order to detect
neighborhoods, and since NHDP is a building block for MANET routing
protocols employing other triggered or periodic message exchanges,
this appendix presents global concerns pertaining to jittering of
MANET control traffic.
D.1. Jitter
In order to prevent nodes in a MANET from simultaneous transmission,
whilst retaining the MANET characteristic of maximum node autonomy, a
randomization of the transmission time of packets by nodes, known as
jitter, MAY be employed. Three jitter mechanisms, which target
different aspects of this problem, MAY be employed, with the aim of
reducing the likelihood of simultaneous transmission, and, if it
occurs, preventing it from continuing.
Three cases exist:
o Periodic message generation;
o Externally triggered message generation;
o Message forwarding.
Each of these cases uses a parameter, denoted MAXJITTER, for the
maximum timing variation that it introduces. If more than one of
these cases is used by a protocol, it MAY use the same or a different
value of MAXJITTER for each case. It also MAY use the same or
different values of MAXJITTER according to message type, and under
different circumstances - in particular if other parameters (such as
message interval) vary.
Issues relating to the value of MAXJITTER are considered in
Appendix D.1.4.
D.1.1. Periodic message generation Any process which updates the Local Information Base or the
Neighborhood Information Base MUST ensure that all constraints
specified in this appendix are maintained.
When a node generates a message periodically, two successive messages In each Local Interface Tuple:
will be separated by a well-defined interval, denoted
MESSAGE_INTERVAL. A node MAY maintain more than one such interval,
e.g. for different message types or in different circumstances (such
as backing off transmissions to avoid congestion). Jitter MAY be
applied by reducing this delay by a random amount, so that the delay
between consecutive transmissions of a messages of the same type is
equal to (MESSAGE_INTERVAL - jitter), where jitter is the random
value.
Subtraction of the random value from the message interval ensures o I_local_iface_addr_list MUST NOT be empty.
that the message interval never exceeds MESSAGE_INTERVAL, and does
not adversely affect timeouts or other mechanisms which may be based
on message late arrival or failure to arrive. By basing the message
transmission time on the previous transmission time, rather than by
jittering a fixed clock, nodes can become completely desynchronized,
which minimizes their probability of repeated collisions. This is
particularly useful when combined with externally triggered message
generation and rescheduling.
The jitter value SHOULD be taken from a uniform distribution between o I_local_iface_addr_list MUST NOT contain any address which is in
zero and MAXJITTER. the I_local_iface_addr_list of any other Local Interface Tuple.
Note that a node will know its own MESSAGE_INTERVAL value and can In each Link Tuple:
readily ensure that any MAXJITTER value used satisfies the conditions
in Appendix D.1.4.
D.1.2. Externally triggered message generation o L_neighbor_iface_addr_list MUST NOT be empty.
An internal or external condition or event MAY trigger message o L_neighbor_iface_addr_list MUST NOT contain any address which is
generation by a node. Depending upon the protocol, this condition in the I_local_iface_addr_list of any Local Interface Tuple.
MAY trigger generation of a single message, initiation of a new
periodic message schedule, or rescheduling of existing periodic
messaging. Collision between externally triggered messages is made
more likely if more than one node is likely to respond to the same
event. To reduce this likelihood, an externally triggered message
MAY be jittered by delaying it by a random duration; an internally
triggered message MAY also be so jittered if appropriate. This delay
SHOULD be generated uniformly in an interval between zero and
MAXJITTER. If periodically transmitted messages are rescheduled,
then this SHOULD be based on this delayed time, with subsequent
messages treated as described in Appendix D.1.1.
When messages are triggered, whether or not they are also o L_neighbor_iface_addr_list MUST NOT contain any address which is
periodically transmitted, a protocol MAY impose a minimum interval in the L_neighbor_iface_addr_list of any other Link Tuple in the
between messages of the same type, denoted MESSAGE_MIN_INTERVAL. It same Link Set.
is however appropriate to also allow this interval to be reduced by
jitter, so that when a message is transmitted the next message is
allowed after a time (MESSAGE_MIN_INTERVAL - jitter), where jitter
SHOULD be generated uniformly in an interval between zero and
MAXJITTER (using a value of MAXJITTER appropriate to periodic message
transmission). This is because otherwise, when external triggers are
more frequent than MESSAGE_MIN_INTERVAL, it takes the role of
MESSAGE_INTERVAL and the arguments applying to jittering of the
latter also apply to the former. This also permits
MESSAGE_MIN_INTERVAL to equal MESSAGE_INTERVAL even when jitter is
used.
D.1.3. Message forwarding o If L_HEARD_time has not expired then there MUST be a Neighbor
Tuple whose N_neighbor_iface_addr_list contains
L_neighbor_iface_addr_list.
When a node forwards a message, it may be jittered by delaying it by o L_HEARD_time MUST NOT be greater than L_time.
a random duration. This delay SHOULD be generated uniformly in an
interval between zero and MAXJITTER.
Unlike the cases of periodically generated and externally triggered o L_SYM_time MUST NOT be greater than L_HEARD_time (unless both are
messages, a node is not automatically aware of the message expired).
originator's value of MESSAGE_INTERVAL, which is required to select a
value of MAXJITTER which is known to be valid. This may require
prior agreement as to the value (or minimum value) of
MESSAGE_INTERVAL, may be by inclusion in the message of
MESSAGE_INTERVAL (the time until the next relevant message, rather
than the time since the last message) or be by any other protocol
specific mechanism, which may include estimation of the value of
MESSAGE_INTERVAL based on received message times.
For several possible reasons (differing parameters, message o L_quality MUST NOT be less than 0 or greater than 1.
rescheduling, extreme random values) a node may receive a message
while still waiting to forward an earlier message of the same type
originating from the same node. This is possible without jitter, but
may occur more often with it. The appropriate action to take is
protocol specific (typically to discard the earlier message or to
forward both, possible modifying timing to maintain message order).
In many cases, including [3] and protocols using the full o If L_quality >= HYST_ACCEPT then L_pending MUST be false.
functionality of [1], messages are transmitted hop by hop in
potentially multi-message packets, and some or all of those messages
may need to be forwarded. For efficiency this should be in a single
packet, and hence the forwarding jitter of all messages received in a
single packet should be the same. (This also requires that a single
value of MAXJITTER is used in this case.) For this to have the
intended uniform distribution it is necessary to choose a single
random jitter for all messages. It is not appropriate to give each
message a random jitter and then to use the smallest of these jitter
values, as that produces a jitter with a non-uniform distribution and
a reduced mean value.
In addition, the protocol may permit messages received in different o If L_quality < HYST_REJECT then L_status MUST be PENDING or LOST.
packets to be combined, possibly also with locally generated messages
(periodically generated or triggered). However in this case the
purpose of the jitter will be accomplished by choosing any of the
independently scheduled times for these events as the single
forwarding time; this may have to be the earliest time to achieve all
constraints. This is because without combining messages, a
transmission was due at this time anyway.
D.1.4. Maximum Jitter Determination o L_pending MUST NOT be set to true if it is currently false.
In considering how the maximum jitter (one or more instances of In each Neighbor Tuple:
parameter MAXJITTER) may be determined, the following points may be
noted:
o While jitter may resolve the problem of simultaneous o N_neighbor_iface_addr_list MUST NOT contain any address which is
transmissions, the timing changes (in particular the delays) it in the I_local_iface_addr_list of any Local Interface Tuple.
introduces will otherwise only have a negative impact on a well-
designed protocol. Thus MAXJITTER should always be minimized,
subject to acceptably achieving its intent.
o When messages are periodically generated, all of the following o N_neighbor_iface_addr_list MUST NOT contain any address which is
that are relevant apply to each instance of MAXJITTER: in the N_neighbor_iface_addr_list of any other Neighbor Tuple.
* it MUST NOT be greater than MESSAGE_INTERVAL/2; o If N_symmetric == true, then there MUST be one or more Link Tuples
with:
* it SHOULD be significantly less than MESSAGE_INTERVAL; * L_neighbor_iface_addr_list contained in
N_neighbor_iface_addr_list; AND
* it MUST NOT be greater than MESSAGE_MIN_INTERVAL; * L_status == SYMMETRIC.
* it SHOULD NOT be greater than MESSAGE_MIN_INTERVAL/2. o If N_symmetric == false, then there MUST be one or more Link
Tuples with:
o As well as the decision as to whether to use jitter being * L_neighbor_iface_addr_list contained in
dependent on the medium access control and lower layers, the N_neighbor_iface_addr_list.
selection of the MAXJITTER parameter should be appropriate to
those mechanisms.
o As jitter is intended to reduce collisions, greater jitter, i.e. All such Link Tuples MUST NOT have L_status == SYMMETRIC. At
an increased value of MAXJITTER, is appropriate when the chance of least one such Link Tuple MUST have L_HEARD_time not expired.
collisions is greater. This is particularly the case with
increased node density, where node density should be considered
relative to (the square of) the interference range rather than
useful signal range.
o The choice of MAXJITTER used when forwarding messages may also In each Lost Neighbor Tuple:
take into account the expected number of times that the message
may be sequentially forwarded, up to the network diameter in hops.
Appendix E. Utilizing Link Layer Information o NL_neighbor_iface_addr MUST NOT be in the I_local_iface_addr_list
of any Local Interface Tuple.
The interface between NHDP and any protocol(s) using NHDP is through o NL_neighbor_iface_addr MUST NOT equal the NL_neighbor_iface_addr
the Neighborhood Information Base as defined in Section 6. The of any other Lost Neighbor Tuple.
message exchange and associated processing specified in Section 9 and
Section 10 allow fully maintaining this Neighborhood Information
Base.
Different link layers, and even different implementations of the same o NL_neighbor_iface_addr MUST NOT be in the
link layer, may make varying amount of information available N_neighbor_iface_addr_list of any Neighbor Tuple with N_symmetric
describing local connectivity. If present, such link layer == true.
information MAY be used to supplement, or replace, elements of NHDP
as follows:
No link layer information - Absent any link layer information on a In each 2-Hop Tuple:
MANET interface, NHDP MUST be employed for populating all sets of
the Neighborhood Information Base as defined in this
specification.
Failed data delivery - If link layer information is available on a o There MUST be a Link Tuple associated with the same MANET
MANET interface, identifying when data delivery to a presumed interface with:
directly connected node has failed, NHDP MUST be employed for
populating all sets of the Neighborhood Information Base as
defined in this specification. The link layer information MAY be
used to degrade a presumed directly connected node from being
considered as SYMMETRIC to being considered HEARD or LOST. A
HELLO message reflecting these changes MAY be generated,
respecting the considerations in Section 9.
Link quality information - The link layer may make available "soft" * L_neighbor_iface_addr_list == N2_neighbor_iface_addr_list; AND
information (possibly derived from the physical layer) relating to
the link quality. NHDP MAY be able to use this information, in a
normalized form, to adjust the link status between LOST, HEARD and
SYMMETRIC.
Local (1-hop) connectivity - If link layer information is available * L_status == SYMMETRIC.
on a MANET interface, identifying the local (1-hop) connectivity
via that interface, then this information MAY be used as follows
when generating HELLO messages over that interface:
* Step 1 in Hello Message Generation (Section 9) MAY be ignored. o N2_2hop_iface_addr MUST NOT be in the I_local_iface_addr_list of
This implies that local connectivity verification over that any Local Interface Tuple.
MANET interface is not performed by NHDP, but is using the link
layer information.
* All other steps in Hello Message Generation (Section 9) MUST be o N2_2hop_iface_addr MUST NOT be the N2_2hop_iface_addr of any other
carried out, such that Neighborhood Address Association Sets 2-Hop Tuple in the same 2-Hop Set and with the same
and 2-Hop Neighbor Sets can be populated correctly. N2_neighbor_iface_addr_list.
* All MANET interfaces which do not have local (1-hop) o N2_2hop_iface_addr MUST NOT be in the N2_neighbor_iface_addr_list
connectivity information available MUST employ the message of the same 2-Hop Tuple.
exchange as detailed in this specification.
Appendix F. Security Considerations Appendix D. Security Considerations
The objective of this protocol is to allow each node in the network The objective of this protocol is to allow each node in the network
to acquire information describing its 1-hop and symmetric 2-hop to acquire information describing its 1-hop and symmetric 2-hop
neighborhoods. This is acquired through message exchange between neighborhoods. This is acquired through message exchange between
neighboring nodes. The information is made available through a neighboring nodes. The information is made available through a
collection of sets, describing the node's 1-hop neighborhood and collection of sets, describing the node's 1-hop neighborhood and
symmetric 2-hop neighborhood. symmetric 2-hop neighborhood.
Under normal circumstances, the information recorded in these sets is Under normal circumstances, the information recorded in these sets is
correct - i.e. corresponds to the actual network topology, apart from correct - i.e. corresponds to the actual network topology, apart from
any changes which have not (yet) been tracked by the HELLO message any changes which have not (yet) been tracked by the HELLO message
exchanges. exchanges.
If some node for some reason, malice or malfunction, injects invalid If some node for some reason, malice or malfunction, injects invalid
HELLO messages, incorrect information may be recorded in the sets HELLO messages, incorrect information may be recorded in the sets
maintained. The exact consequence of this inexactness depends on the maintained. The protocol specification does, however, prevent
use of these sets, and MUST be explicitly reflected in the inconsistent information from being injected in the protocol sets
specification of protocols which use information provided by NHDP. through the constraints in Appendix C. The exact consequence of
information inexactness depends on the use of these sets, and should
be reflected in the specification of protocols which use information
provided by NHDP.
This appendix, therefore, only outlines the ways in which correctly This appendix, therefore, only outlines the ways in which correctly
formed, but still invalid, HELLO messages may appear. formed, but still invalid, HELLO messages may appear.
Appendix F.1. Invalid HELLO messages Appendix D.1. Invalid HELLO messages
A correctly formed, but still invalid, HELLO message may take any of A correctly formed, but still invalid, HELLO message may take any of
the following forms: the following forms:
A node may provide false information about its own identity: A node may provide false information about its own identity:
* The Local Interface Block of the HELLO message may contain * The Local Interface Block of the HELLO message may contain
addresses which do not correspond to addresses of MANET addresses which do not correspond to addresses of interfaces of
interfaces of the local node which transmits the HELLO message; the node transmitting the HELLO message.
* The Local Interface Block of the HELLO message may omit * The Local Interface Block of the HELLO message may omit
addresses of MANET interfaces of the local node which transmits addresses of interfaces of the local node transmitting the
the HELLO message; HELLO message.
* The Local Interface Block may contain OTHER_IF TLVs, indicating * The Local Interface Block may contain additional OTHER_IF TLVs,
incorrectly that an address is associated with a MANET indicating incorrectly that an address is associated with an
interface other than the one over which the HELLO message is interface other than that over which the HELLO message is
being transmitted; transmitted.
* The Local Interface Block may omit OTHER_IF TLVs, thereby * The Local Interface Block may omit OTHER_IF TLVs, thereby
indicating incorrect addresses associated with the MANET indicating incorrect addresses associated with the MANET
interface over which the HELLO message is being transmitted; interface over which the HELLO message is transmitted.
A node may provide false information about the identity of other A node may provide false information about the identity of other
nodes: nodes:
* A present or absent address in an address block, other than in * A present or absent address in a Neighbor Block, does not in
the Local Interface Block, does not in and by itself cause a and by itself cause a problem. It is the presence, absence, or
problem. It is the presence, absence or incorrectness of incorrectness of associated LINK_STATUS and OTHER_NEIGHB TLVs
associated LINK_STATUS and OTHER_NEIGHB TLVs that cause that causes problems.
problems;
* A present LINK_STATUS TLV may, incorrectly, identify an address * A present LINK_STATUS TLV may, incorrectly, identify an address
as being of a node which is or was in the sending node's 1-hop as being of a MANET interface which is or was heard on the
neighborhood; MANET interface over which the HELLO message is transmitted.
* A consistently absent LINK_STATUS TLV may, incorrectly, fail to * A consistently absent LINK_STATUS TLV may, incorrectly, fail to
identify an address as being of a node which is or was in the identify an address as being of a MANET interface which is or
sending node's 1-hop neighborhood; was heard on the MANET interface over which the HELLO message
is transmitted.
* A present OTHER_NEIGHB TLV may, incorrectly, identify an * A present OTHER_NEIGHB TLV may, incorrectly, identify an
address as being of a node which is or was in the sending address as being of a node which is or was in the sending
node's symmetric 1-hop neighborhood; node's symmetric 1-hop neighborhood;
* A consistently absent OTHER_NEIGHB TLV may, incorrectly, fail * A consistently absent OTHER_NEIGHB TLV may, incorrectly, fail
to identify an address as being of a node which is or was in to identify an address as being of a node which is or was in
the sending node's symmetric 1-hop neighborhood; the sending node's symmetric 1-hop neighborhood;
* The value of a LINK_STATUS or OTHER_NEIGHB TLV may incorrectly * The value of a LINK_STATUS TLV may incorrectly indicate the
indicate the status (LOST, SYMMETRIC, HEARD) of a 1-hop status (LOST, SYMMETRIC or HEARD) of the link from a 1-hop
neighbor. neighbor.
Appendix G. Flow and Congestion Control * The value of an OTHER_NEIGHB TLV may incorrectly indicate the
status (LOST or SYMMETRIC) of a symmetric 1-hop neighbor.
This document specifies one message type, the HELLO message. The Appendix E. Flow and Congestion Control
size of each complete HELLO message is proportional to the size of
the originating node's 1-hop neighborhood; some or all of this This protocol specifies one message type, the HELLO message. The
information on each of the node's MANET interfaces. HELLO messages maximum size of a HELLO message is proportional to the size of the
MUST NOT be forwarded. originating node's 1-hop neighborhood. HELLO messages MUST NOT be
forwarded.
A node MUST report its 1-hop neighborhood in HELLO messages on each A node MUST report its 1-hop neighborhood in HELLO messages on each
of its MANET interfaces at least each REFRESH_INTERVAL. Thus, this of its MANET interfaces at least each REFRESH_INTERVAL. This puts a
puts a lower bound on the control traffic generated by each node in lower bound on the control traffic generated by each node in the
the network employing this neighborhood discovery protocol. network employing this protocol.
A node MUST ensure that two successive HELLO messages sent on the A node MUST ensure that two successive HELLO messages sent on the
same MANET interface are separated by at least HELLO_MIN_INTERVAL. 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 (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 HELLO_MIN_INTERVAL - HP_MAXJITTER/2.) Thus, this puts an upper bound
on the control traffic generated by each node in the network on the control traffic generated by each node in the network
employing this neighborhood discovery protocol. employing this protocol.
Appendix H. Contributors Appendix F. Contributors
This specification is the result of the joint efforts of the This specification is the result of the joint efforts of the
following contributors -- listed alphabetically. following contributors -- listed alphabetically.
o Brian Adamson, NRL, USA, <adamson@itd.nrl.navy.mil> o Brian Adamson, NRL, USA, <adamson@itd.nrl.navy.mil>
o Cedric Adjih, INRIA, France, <Cedric.Adjih@inria.fr> o Cedric Adjih, INRIA, France, <Cedric.Adjih@inria.fr>
o Emmanuel Baccelli, Hitachi Labs Europe, France, o Emmanuel Baccelli, Hitachi Labs Europe, France,
<Emmanuel.Baccelli@inria.fr> <Emmanuel.Baccelli@inria.fr>
o Thomas Heide Clausen, PCRI, France, <T.Clausen@computer.org> o Thomas Heide Clausen, PCRI, France, <T.Clausen@computer.org>
o Justin Dean, NRL, USA, <jdean@itd.nrl.navy.mil> o Justin Dean, NRL, USA, <jdean@itd.nrl.navy.mil>
o Christopher Dearlove, BAE Systems, UK, o Christopher Dearlove, BAE Systems, UK,
<Chris.Dearlove@baesystems.com> <Chris.Dearlove@baesystems.com>
o Philippe Jacquet, INRIA, France, <Philippe.Jacquet@inria.fr> o Philippe Jacquet, INRIA, France, <Philippe.Jacquet@inria.fr>
Appendix I. Acknowledgements Appendix G. Acknowledgements
The authors would like to acknowledge the team behind OLSRv1, The authors would like to acknowledge the team behind OLSRv1,
specified in RFC3626, for their contributions. specified in RFC3626 for their contributions.
The authors would like to gratefully acknowledge the following people The authors would like to gratefully acknowledge the following people
for intense technical discussions, early reviews and comments on the for intense technical discussions, early reviews and comments on the
specification and its components: Joe Macker (NRL), Alan Cullen (BAE specification and its components: Joe Macker (NRL), Alan Cullen (BAE
Systems), and the entire IETF MANET working group. Systems), and the entire IETF MANET working group.
Authors' Addresses Authors' Addresses
Thomas Heide Clausen Thomas Heide Clausen
LIX, Ecole Polytechnique, France LIX, Ecole Polytechnique, France
Phone: +33 6 6058 9349 Phone: +33 6 6058 9349
Email: T.Clausen@computer.org Email: T.Clausen@computer.org
URI: http://www.lix.polytechnique.fr/Labo/Thomas.Clausen/ URI: http://www.ThomasClausen.org/
Christopher M. Dearlove Christopher M. Dearlove
BAE Systems Advanced Technology Centre BAE Systems Advanced Technology Centre
Phone: +44 1245 242194 Phone: +44 1245 242194
Email: chris.dearlove@baesystems.com Email: chris.dearlove@baesystems.com
URI: http://www.baesystems.com/ocs/sharedservices/atc/ URI: http://www.baesystems.com/
Justin W. Dean Justin W. Dean
Naval Research Laboratory Naval Research Laboratory
Phone: +1 202 767 3397 Phone: +1 202 767 3397
Email: jdean@itd.nrl.navy.mil Email: jdean@itd.nrl.navy.mil
URI: http://pf.itd.nrl.navy.mil/ URI: http://pf.itd.nrl.navy.mil/
The OLSRv2 Design Team The OLSRv2 Design Team
MANET Working Group MANET Working Group
 End of changes. 363 change blocks. 
1167 lines changed or deleted 1358 lines changed or added

This html diff was produced by rfcdiff 1.33. The latest version is available from http://tools.ietf.org/tools/rfcdiff/