draft-ietf-manet-nhdp-01.txt   draft-ietf-manet-nhdp-02.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 13, 2007 BAE Systems Advanced Technology Expires: August 5, 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 9, 2007 February 2007
MANET Neighborhood Discovery Protocol (NHDP) MANET Neighborhood Discovery Protocol (NHDP)
draft-ietf-manet-nhdp-01 draft-ietf-manet-nhdp-02
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 13, 2007. This Internet-Draft will expire on August 5, 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 . . . . . . . . . . . . . . . . . . . 6
4. Protocol Overview and Functioning . . . . . . . . . . . . . . 7 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 7
4.1. HELLO Message Generation . . . . . . . . . . . . . . . . . 7 4.1. HELLO Message Generation . . . . . . . . . . . . . . . . . 7
4.2. HELLO message content . . . . . . . . . . . . . . . . . . 8 4.2. HELLO message content . . . . . . . . . . . . . . . . . . 8
4.3. Node Behavior . . . . . . . . . . . . . . . . . . . . . . 8 4.3. Node Behavior . . . . . . . . . . . . . . . . . . . . . . 8
5. Neighborhood Information Base . . . . . . . . . . . . . . . . 10 5. Local Information Base . . . . . . . . . . . . . . . . . . . . 10
5.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . . . 10 5.1. Local Interface Set . . . . . . . . . . . . . . . . . . . 10
5.2. Symmetric Neighbor Set . . . . . . . . . . . . . . . . . . 11 6. Neighborhood Information Base . . . . . . . . . . . . . . . . 11
5.3. Neighborhood Address Association Set . . . . . . . . . . . 12 6.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.4. 2-Hop Neighbor Set . . . . . . . . . . . . . . . . . . . . 12 6.2. Symmetric Neighbor Set . . . . . . . . . . . . . . . . . . 12
6. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 13 6.3. Neighborhood Address Association Set . . . . . . . . . . . 13
6.1. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 13 6.4. 2-Hop Neighbor Set . . . . . . . . . . . . . . . . . . . . 13
6.1.1. Local Interface Block . . . . . . . . . . . . . . . . 14 7. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 15
6.1.2. Address Block TLVs . . . . . . . . . . . . . . . . . . 14 7.1. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 15
7. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 15 7.1.1. Local Interface Block . . . . . . . . . . . . . . . . 16
7.1. HELLO Message: Transmission . . . . . . . . . . . . . . . 16 7.1.2. Address Block TLVs . . . . . . . . . . . . . . . . . . 16
7.1.1. HELLO Message: Jitter . . . . . . . . . . . . . . . . 17 8. Local Information Base Changes . . . . . . . . . . . . . . . . 17
8. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 18 8.1. Adding a MANET Interface . . . . . . . . . . . . . . . . . 17
8.1. Populating the Link Set . . . . . . . . . . . . . . . . . 18 8.2. Removing a MANET Interface . . . . . . . . . . . . . . . . 17
8.2. Populating the Symmetric Neighbor Set . . . . . . . . . . 19 8.3. Adding an Address to a MANET Interface . . . . . . . . . . 18
8.3. Populating the Neighborhood Address Association Set . . . 20 8.4. Removing an Address from a MANET Interface . . . . . . . . 18
8.4. Populating the 2-Hop Neighbor Set . . . . . . . . . . . . 20 8.5. Changing the Principal Address of a MANET Interface . . . 18
8.5. Neighborhood Changes . . . . . . . . . . . . . . . . . . . 22 9. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 19
9. Proposed Values for Constants . . . . . . . . . . . . . . . . 23 9.1. HELLO Message: Transmission . . . . . . . . . . . . . . . 20
9.1. Message Intervals . . . . . . . . . . . . . . . . . . . . 23 9.1.1. HELLO Message: Jitter . . . . . . . . . . . . . . . . 21
9.2. Holding Times . . . . . . . . . . . . . . . . . . . . . . 23 10. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 22
9.3. Jitter Times . . . . . . . . . . . . . . . . . . . . . . . 23 10.1. Populating the Link Set . . . . . . . . . . . . . . . . . 22
9.4. Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 10.2. Populating the Symmetric Neighbor Set . . . . . . . . . . 23
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24 10.3. Populating the Neighborhood Address Association Set . . . 24
10.1. Multicast Addresses . . . . . . . . . . . . . . . . . . . 24 10.4. Populating the 2-Hop Neighbor Set . . . . . . . . . . . . 25
10.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 24 10.5. Neighborhood Changes . . . . . . . . . . . . . . . . . . . 26
10.3. TLV Types . . . . . . . . . . . . . . . . . . . . . . . . 24 11. Link Hysteresis . . . . . . . . . . . . . . . . . . . . . . . 27
10.4. LINK_STATUS and OTHER_NEIGHB Values . . . . . . . . . . . 25 11.1. Link Quality . . . . . . . . . . . . . . . . . . . . . . . 28
11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 26 12. Proposed Values for Constants . . . . . . . . . . . . . . . . 29
11.1. Normative References . . . . . . . . . . . . . . . . . . . 26 12.1. Message Intervals . . . . . . . . . . . . . . . . . . . . 29
11.2. Informative References . . . . . . . . . . . . . . . . . . 26 12.2. Holding Times . . . . . . . . . . . . . . . . . . . . . . 29
Appendix A. Address Block TLV Combinations . . . . . . . . . . . 27 12.3. Hysteresis values . . . . . . . . . . . . . . . . . . . . 29
Appendix B. HELLO Message Example . . . . . . . . . . . . . . . 28 12.4. Jitter Times . . . . . . . . . . . . . . . . . . . . . . . 30
Appendix C. Time TLVs . . . . . . . . . . . . . . . . . . . . . 30 12.5. Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
C.1. Representing Time . . . . . . . . . . . . . . . . . . . . 30 13. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 31
C.2. General Time TLV Structure . . . . . . . . . . . . . . . . 30 13.1. Multicast Addresses . . . . . . . . . . . . . . . . . . . 31
C.3. Message TLVs . . . . . . . . . . . . . . . . . . . . . . . 32 13.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 31
C.3.1. VALIDITY_TIME TLV . . . . . . . . . . . . . . . . . . 32 13.3. TLV Types . . . . . . . . . . . . . . . . . . . . . . . . 31
C.3.2. INTERVAL_TIME TLV . . . . . . . . . . . . . . . . . . 32 13.4. LINK_STATUS and OTHER_NEIGHB Values . . . . . . . . . . . 32
Appendix D. Message Jitter . . . . . . . . . . . . . . . . . . . 33 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 33
D.1. Jitter . . . . . . . . . . . . . . . . . . . . . . . . . . 33 14.1. Normative References . . . . . . . . . . . . . . . . . . . 33
D.1.1. Periodic message generation . . . . . . . . . . . . . 33 14.2. Informative References . . . . . . . . . . . . . . . . . . 33
D.1.2. Externally triggered message generation . . . . . . . 34 Appendix A. Address Block TLV Combinations . . . . . . . . . . . 34
D.1.3. Message forwarding . . . . . . . . . . . . . . . . . . 34 Appendix B. HELLO Message Example . . . . . . . . . . . . . . . 35
Appendix E. Utilizing Link Layer Information . . . . . . . . . . 36 Appendix C. Time TLVs . . . . . . . . . . . . . . . . . . . . . 37
Appendix F. Security Considerations . . . . . . . . . . . . . . 38 C.1. Representing Time . . . . . . . . . . . . . . . . . . . . 37
Appendix F.1. Invalid HELLO messages . . . . . . . . . . . . . . . 38 C.2. General Time TLV Structure . . . . . . . . . . . . . . . . 37
Appendix G. Flow and Congestion Control . . . . . . . . . . . . 40 C.3. Message TLVs . . . . . . . . . . . . . . . . . . . . . . . 39
Appendix H. Contributors . . . . . . . . . . . . . . . . . . . . 41 C.3.1. VALIDITY_TIME TLV . . . . . . . . . . . . . . . . . . 39
Appendix I. Acknowledgements . . . . . . . . . . . . . . . . . . 42 C.3.2. INTERVAL_TIME TLV . . . . . . . . . . . . . . . . . . 39
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 43 Appendix D. Message Jitter . . . . . . . . . . . . . . . . . . . 40
Intellectual Property and Copyright Statements . . . . . . . . . . 44 D.1. Jitter . . . . . . . . . . . . . . . . . . . . . . . . . . 40
D.1.1. Periodic message generation . . . . . . . . . . . . . 40
D.1.2. Externally triggered message generation . . . . . . . 41
D.1.3. Message forwarding . . . . . . . . . . . . . . . . . . 42
D.1.4. Maximum Jitter Determination . . . . . . . . . . . . . 43
Appendix E. Utilizing Link Layer Information . . . . . . . . . . 44
Appendix F. Security Considerations . . . . . . . . . . . . . . 46
Appendix F.1. Invalid HELLO messages . . . . . . . . . . . . . . . 46
Appendix G. Flow and Congestion Control . . . . . . . . . . . . 48
Appendix H. Contributors . . . . . . . . . . . . . . . . . . . . 49
Appendix I. Acknowledgements . . . . . . . . . . . . . . . . . . 50
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 51
Intellectual Property and Copyright Statements . . . . . . . . . . 52
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). The protocol uses an exchange of
HELLO messages in order that each node can determine its 1-hop and HELLO messages in order that each node can determine its 1-hop and
symmetric 2-hop neighborhoods. symmetric 2-hop neighborhoods.
This specification describes both this HELLO message exchange, the This specification describes both this 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
skipping to change at page 6, line 11 skipping to change at page 6, line 11
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.)
3. Applicability Statement 3. Applicability Statement
This neighborhood discovery protocol supports nodes which have one or This neighborhood discovery protocol supports nodes which have one or
more interfaces participating in the MANET. It provides each node more interfaces participating in the MANET. It provides each node
with local topology information up to two hops away. This 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 a
Neighborhood Information Base, described in Section 5. Neighborhood Information Base, described in Section 6.
The protocol is designed to work in networks where messages may be The protocol is designed to work in networks where messages may be
lost, such as due to collisions in wireless networks. If relevant lost, such as due to collisions in wireless networks. If relevant
link layer information is available then it may be used by this link layer information is available then it may be used by this
protocol. protocol.
This protocol to works in a completely distributed manner and does This protocol to works in a completely distributed manner and does
not depend on any central entity. It does not require any changes to not depend on any central entity. It does not require any changes to
the format of IP packets, thus any existing IP stack can be used as the format of IP packets, thus any existing IP stack can be used as
is. is.
skipping to change at page 7, line 35 skipping to change at page 7, line 35
messages and populates its information base, a list of 1-hop messages and populates its information base, a list of 1-hop
neighbors' MANET interface addresses and their link status (lost, neighbors' MANET interface addresses and their link status (lost,
symmetric or heard) is included in subsequent HELLO messages. Thus, symmetric or heard) is included in subsequent HELLO messages. Thus,
the periodic transmission allows nodes to continuously track changes the periodic transmission allows nodes to continuously track changes
in their 1-hop and symmetric 2-hop neighborhoods. If information in their 1-hop and symmetric 2-hop neighborhoods. If information
about link quality is available from the link layer, then this may about link quality is available from the link layer, then this may
also be used, see Appendix E. also be used, see Appendix E.
4.1. HELLO Message Generation 4.1. HELLO Message Generation
HELLO messages may be sent: HELLO messages 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 9, or may be HELLO_INTERVAL may be fixed, as suggested in Section 12, or may be
dynamic. For example HELLO_INTERVAL may be backed off due to dynamic. For example HELLO_INTERVAL may be backed off due to
congestion or network stability. Note that if HELLO_INTERVAL is congestion or network stability. Note that if HELLO_INTERVAL is
dynamic, it is interpreted as the interval within which the next dynamic, it is interpreted as the interval within which the next
HELLO message will be sent on the same MANET interface. 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 neighborhood,
for example on first becoming active or in response to a new, for example on first becoming active or in response to a new,
broken or changed status link. 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 7.1, may be appropriate. in Section 9.1, MAY be used if appropriate.
HELLO messages are sent independently on each MANET interface. HELLO messages are sent independently on each MANET interface.
4.2. HELLO message content 4.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 its own local interface
information. information.
skipping to change at page 8, line 35 skipping to change at page 8, line 35
o A HELLO message SHOULD include an INTERVAL_TIME message TLV that o A HELLO message SHOULD include an INTERVAL_TIME message TLV that
indicates the current value of HELLO_INTERVAL. indicates the current value of HELLO_INTERVAL.
4.3. Node Behavior 4.3. Node Behavior
A node MUST: A node MUST:
o Respect a minimum interval, HELLO_MIN_INTERVAL, between successive o Respect a minimum interval, HELLO_MIN_INTERVAL, between successive
HELLO message transmissions over a given interface. If jitter is HELLO message transmissions over a given interface. If jitter is
used then this interval may be reduced, but only by a random value used then this interval MAY be reduced, but only by a random value
not exceeding HP_MAXJITTER. not exceeding HP_MAXJITTER.
o Ensure that if HELLO_INTERVAL and other parameters are maintained o Ensure that if HELLO_INTERVAL and other parameters are maintained
dynamically, changes do not invalidate the guarantees of dynamically, changes do not invalidate the guarantees of
Section 7.1. Section 9.1.
o Maintain, based on received HELLO messages, estimates of its 1-hop o Maintain, based on received HELLO messages, estimates of its 1-hop
and symmetric 2-hop neighborhoods as this protocol operates. and symmetric 2-hop neighborhoods as this protocol operates.
Formally defined in Section 5, this can be summarized as Formally defined in Section 6, this can be summarized as
consisting of the following sets: consisting of the following sets:
Link Set - Records the status of all links from and to current Link Set - Records the status of all links from and to current
and former 1-hop neighbors. and former 1-hop neighbors.
Symmetric Neighbor Set - Records the status of current and former Symmetric Neighbor Set - Records the status of current and former
symmetric 1-hop neighbors. If any of these nodes have more symmetric 1-hop neighbors. If any of these nodes have more
than one MANET interface then this set may record addresses than one MANET interface then this set may record addresses
that are not in the Link Set. that are not in the Link Set.
skipping to change at page 10, line 5 skipping to change at page 10, line 5
the MANET interfaces of each 1-hop neighbor to be associated the MANET interfaces of each 1-hop neighbor to be associated
with each other. with each other.
2-Hop Neighbor Set - Records the addresses of the MANET 2-Hop Neighbor Set - Records the addresses of the MANET
interfaces of symmetric 2-hop neighbors. interfaces of symmetric 2-hop neighbors.
The information in the Link Set and Symmetric Neighbor Set MUST be The information in the Link Set and Symmetric Neighbor Set MUST be
maintained in order for a node to correctly generate HELLO maintained in order for a node to correctly generate HELLO
messages. messages.
5. Neighborhood Information Base 5. Local Information Base
A node maintains a Local Information Base that records information
about its MANET interfaces. Each MANET interface MUST have at least
one address, and MAY have more than one address. All addresses have
an associated prefix length, which is included all addresses in the
Local Information Base. If an address otherwise does not have a
prefix length it is set equal to the address length. Two addresses
are considered equal if and only if their associated prefix lengths
are also equal.
One of the addresses of each MANET interface is denoted the principal
address of that interface. A node MAY choose which address is the
principal address in any manner; it SHOULD choose the address so as
to minimize changes of principal address. The selection of an
address as a principal address only affects how the node organizes
its information storage, it has no effect on the messages it creates
and sends.
The Local Information Base is not modified by this protocol. This
protocol may respond to changes of this Local Information Base which
MUST reflect corresponding changes in the node's status.
5.1. Local Interface Set
A node's Local Interface Set records its local MANET interfaces. It
consists of Local Interface Tuples, one per MANET interface:
(I_local_iface_addr_list)
where:
I_local_iface_addr_list is a list of the addresses of this MANET
interface, with the first of the listed addresses being considered
as the principal address of the interface.
6. Neighborhood Information Base
A node maintains a Neighborhood Information Base that records A node maintains a Neighborhood Information Base that records
information about its 1-hop and symmetric 2-hop neighborhoods. The information about its 1-hop and symmetric 2-hop neighborhoods. The
Neighborhood Information Base includes the Link Set, the Symmetric Neighborhood Information Base includes the Link Set, the Symmetric
Neighbor Set, the Neighborhood Address Association Set and the 2-Hop Neighbor Set, the Neighborhood Address Association Set and the 2-Hop
Neighbor Set. Neighbor Set.
A node, X, can be present in both the 1-hop and symmetric 2-hop A node, X, can be present in both the 1-hop and symmetric 2-hop
neighborhoods of another node, Y, concurrently. This allows node X neighborhoods of another node, Y, concurrently. This allows node X
to be immediately considered as a symmetric 2-hop neighbor by node Y to be immediately considered as a symmetric 2-hop neighbor by node Y
if the link between them fails. if the link between them fails.
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 Neighborhood Information Base.
Prefix lengths are indicated in HELLO messages using the Prefix lengths are indicated in HELLO messages using the
PREFIX_LENGTH TLV specified in [1]; if an address has no such TLV, 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 then its prefix length is equal to the address length. Two addresses
are considered equal if and only if their associated prefix lengths are considered equal if and only if their associated prefix lengths
are also equal. are also equal.
5.1. Link Set 6.1. Link Set
A node's Link Set records its 1-hop neighborhood. It consists of A node's Link Set records its 1-hop neighborhood. It consists of
Link Tuples: Link Tuples:
(L_local_iface_addr, L_neighbor_iface_addr, L_SYM_time, (L_local_iface_addr, L_neighbor_iface_addr_list, L_SYM_time,
L_ASYM_time, L_time) L_ASYM_time, L_LOST_time, L_quality, L_pending, L_lost, L_time)
where: where:
L_local_iface_addr is the address of the local MANET interface on L_local_iface_addr is the principal address of the local MANET
which the 1-hop neighbor is or was heard; interface on which the 1-hop neighbor is or was heard;
L_neighbor_iface_addr is the address of the MANET interface of the L_neighbor_iface_addr_list is a list of the addresses of the MANET
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_SYM_time is the time until which the link to the 1-hop neighbor is
considered symmetric; considered symmetric;
L_ASYM_time is the time until which the MANET interface of the 1-hop L_ASYM_time is the time until which the MANET interface of the 1-hop
neighbor is considered heard; neighbor is considered heard;
L_LOST_time is the time until which the MANET interface of the 1-hop
neighbor is considered lost; if L_lost is true and L_LOST_time is
expired, then this Tuple MUST be removed;
L_quality is a dimensionless number between 0 (included) and 1
(included) describing the quality of a link;
L_pending is a boolean flag, describing if a link is considered
pending (i.e. a candidate, but not yet established, link);
L_lost is a boolean flag, describing if a link is considered lost
due to link quality and hysteresis;
L_time specifies when this Tuple expires and MUST be removed. L_time specifies when this Tuple expires and MUST be removed.
The status of the link, denoted L_STATUS, can be derived based on the The status of the link as obtained through simple message exchange,
fields L_SYM_time and L_ASYM_time as defined in Table 1. denoted H_STATUS, can be derived based on the elements L_SYM_time and
L_ASYM_time as defined in Table 1.
+-------------+-------------+-----------+ +-------------+-------------+-----------+
| L_SYM_time | L_ASYM_time | L_STATUS | | L_SYM_time | L_ASYM_time | H_STATUS |
+-------------+-------------+-----------+ +-------------+-------------+-----------+
| Expired | Expired | LOST | | Expired | Expired | LOST |
| | | | | | | |
| Not Expired | Expired | SYMMETRIC | | Not Expired | Expired | SYMMETRIC |
| | | | | | | |
| Not Expired | Not Expired | SYMMETRIC | | Not Expired | Not Expired | SYMMETRIC |
| | | | | | | |
| Expired | Not Expired | HEARD | | Expired | Not Expired | HEARD |
+-------------+-------------+-----------+ +-------------+-------------+-----------+
Table 1 Table 1
5.2. Symmetric Neighbor Set The status of the link, taking link quality and hysteresis into
account, denoted L_STATUS, is defined by:
1. if L_pending is true, then L_STATUS = PENDING;
2. otherwise, if L_lost is true, then L_STATUS = LOST;
3. otherwise, if L_LOST_time is not expired, then L_STATUS = LOST;
4. otherwise, L_STATUS = H_STATUS.
6.2. Symmetric Neighbor Set
A node's Symmetric Neighbor Set records its symmetric 1-hop A node's Symmetric Neighbor Set records its symmetric 1-hop
neighborhood. It consists of Symmetric Neighbor Tuples: neighborhood. It consists of Symmetric Neighbor Tuples:
(N_local_iface_addr, N_neighbor_iface_addr, N_SYM_time, N_time) (N_local_iface_addr, N_neighbor_iface_addr, N_SYM_time, N_time)
where: where:
N_local_iface_addr is the address of the local MANET interface to N_local_iface_addr is the principal address of the local MANET
which the 1-hop neighbor has or had a symmetric link; interface to which the 1-hop neighbor has or had a symmetric link;
N_neighbor_iface_addr is an address of a MANET interface of a 1-hop 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; 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 N_SYM_time is the time until which the 1-hop neighbor is considered
to be a symmetric 1-hop neighbor; to be a symmetric 1-hop neighbor;
N_time specifies when this Tuple expires and MUST be removed. N_time specifies when this Tuple expires and MUST be removed.
The status of the 1-hop neighbor, denoted N_STATUS, can be derived The status of the 1-hop neighbor, denoted N_STATUS, can be derived
based on the field L_SYM_time as defined in Table 2. based on the field N_SYM_time as defined in Table 2.
+-------------+-----------+ +-------------+-----------+
| N_SYM_time | N_STATUS | | N_SYM_time | N_STATUS |
+-------------+-----------+ +-------------+-----------+
| Expired | LOST | | Expired | LOST |
| | | | | |
| Not Expired | SYMMETRIC | | Not Expired | SYMMETRIC |
+-------------+-----------+ +-------------+-----------+
Table 2 Table 2
5.3. Neighborhood Address Association Set 6.3. Neighborhood Address Association Set
A node's Neighborhood Address Association Set records the MANET A node's Neighborhood Address Association Set records the MANET
interface configuration of its 1-hop neighbors. It consists of interface configuration of its 1-hop neighbors. It consists of
Neighborhood Address Association Tuples: Neighborhood Address Association Tuples:
(NA_neighbor_iface_addr_list, NA_time) (NA_neighbor_iface_addr_list, NA_time)
where: where:
NA_neighbor_iface_addr_list is a list of interface addresses of a NA_neighbor_iface_addr_list is a list of interface addresses of a
single 1-hop neighbor; 1-hop neighbor;
NA_time specifies when this Tuple expires and MUST be removed. NA_time specifies when this Tuple expires and MUST be removed.
5.4. 2-Hop Neighbor Set 6.4. 2-Hop Neighbor Set
A node's 2-Hop Neighbor Set records its symmetric 2-hop neighborhood. A node's 2-Hop Neighbor Set records its symmetric 2-hop neighborhood.
It consists of 2-Hop Neighbor Tuples: It consists of 2-Hop Neighbor Tuples:
(N2_local_iface_addr, N2_neighbor_iface_addr, N2_2hop_iface_addr, (N2_local_iface_addr, N2_neighbor_iface_addr_list,
N2_time) N2_2hop_iface_addr, N2_time)
where: where:
N2_local_iface_addr is the address of the local MANET interface on N2_local_iface_addr is the principal address of the local MANET
which this information was received; interface on which this information was received;
N2_neighbor_iface_addr is the address of the MANET interface of a N2_neighbor_iface_addr_list is a list of the addresses of the MANET
symmetric 1-hop neighbor; interface of the 1-hop neighbor from which this information was
received;
N2_2hop_iface_addr is the address of a MANET interface of a N2_2hop_iface_addr is an address of a MANET interface of a symmetric
symmetric 2-hop neighbor which has a symmetric link (using any 2-hop neighbor which has a symmetric link (using any MANET
MANET interface) to the indicated symmetric 1-hop neighbor; interface) to the indicated symmetric 1-hop neighbor;
N2_time specifies the time at which this Tuple expires and MUST be N2_time specifies the time at which this Tuple expires and MUST be
removed. removed.
6. Packets and Messages 7. Packets and Messages
The packet and message format used by this neighborhood discovery The packet and message format used by this neighborhood discovery
protocol is defined in [1], which is used with the following protocol is defined in [1], which is used with the following
considerations: considerations:
o this protocol specifies one message type, the HELLO message; o this protocol specifies one message type, the HELLO message;
o HELLO message header options may be used as specified by the o HELLO message header options may be used as specified by the
protocol which uses this neighborhood discovery protocol; protocol which uses this neighborhood discovery protocol;
o HELLO messages MUST NOT be forwarded; o HELLO messages MUST NOT be forwarded;
o HELLO messages may be included in multi-message packets as o HELLO messages may be included in multi-message packets as
specified in [1]; specified in [1];
o packet header options may be used as specified by the protocol o packet header options may be used as specified by the protocol
which uses this neighborhood discovery protocol. which uses this neighborhood discovery protocol.
6.1. HELLO Messages 7.1. HELLO Messages
A HELLO message MUST contain: A HELLO message MUST contain:
o A VALIDITY_TIME message TLV as specified in Appendix C, o A VALIDITY_TIME message TLV as specified in Appendix C,
representing time value (at distance one hop) H_HOLD_TIME, which representing time value (at distance one hop) H_HOLD_TIME, which
MUST NOT be less than REFRESH_INTERVAL. If HELLO messages may be MUST NOT be less than REFRESH_INTERVAL. If HELLO messages may be
lost then H_HOLD_TIME SHOULD be a multiple of REFRESH_INTERVAL. lost then H_HOLD_TIME SHOULD be a multiple of REFRESH_INTERVAL.
o An address block, and associated TLV block, known as the Local o An address block, and associated TLV block, known as the Local
Interface Block, as specified in Section 6.1.1. Interface Block, as specified in Section 7.1.1.
A HELLO message which is transmitted at a regular interval SHOULD A HELLO message which is transmitted at a regular interval SHOULD
contain, and otherwise MAY contain: contain, and otherwise MAY contain:
o An INTERVAL_TIME message TLV as specified in Appendix C, o An INTERVAL_TIME message TLV as specified in Appendix C,
representing time value (at distance one hop) HELLO_INTERVAL. representing time value (at distance one hop) HELLO_INTERVAL.
A HELLO message MAY contain: A HELLO message MAY contain:
o One or more address blocks, with associated address block TLVs, o One or more address blocks, with associated address block TLVs,
containing current or former 1-hop neighbors' MANET interface containing current or former 1-hop neighbors' MANET interface
addresses. Other addresses (i.e. addresses of non-neighbor nodes) addresses. Other addresses (i.e. addresses of non-neighbor nodes)
MAY be included in these address blocks, but MUST NOT be MAY be included in these address blocks, but MUST NOT be
associated with any of the TLVs specified in Section 6.1.2. associated with any of the TLVs specified in Section 7.1.2.
o Other message TLVs. o Other message TLVs.
6.1.1. Local Interface Block 7.1.1. Local Interface Block
The first address block, plus following TLV block, in a HELLO message The first address block, plus following TLV block, in a HELLO message
is known as the Local Interface Block. The Local Interface Block is is known as the Local Interface Block. The Local Interface Block is
not distinguished in any way other than by being the first address not distinguished in any way other than by being the first address
block in the message. block in the message.
The first address of the Local Interface Block MUST be the used
address of the MANET interface over which the HELLO message is
transmitted.
The Local Interface Block MUST contain all of the addresses of all of The Local Interface Block MUST contain all of the addresses of all of
the MANET interfaces of the originating node, and no other addresses. the MANET interfaces of the originating node (i.e. all addresses
Those addresses, if any, which correspond to MANET interfaces other appearing in an I_local_iface_addr_list). Those addresses, if any,
than that on which the HELLO message is transmitted MUST have a which correspond to MANET interfaces other than that on which the
corresponding OTHER_IF TLV as specified in Section 6.1.2, other HELLO message is transmitted MUST be associated with a corresponding
addresses (i.e. those of the MANET interface on which the HELLO TLV with Type == OTHER_IF as specified in Section 7.1.2, addresses of
message is transmitted) MUST NOT use this TLV. 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 Note that a Local Interface Block MAY include more than one address
for each MANET interface, and hence a HELLO message MAY contain more for each MANET interface, and hence a HELLO message MAY contain more
than one address without an OTHER_IF TLV. than one address without an OTHER_IF TLV.
6.1.2. Address Block TLVs 7.1.2. Address Block TLVs
The three address block TLVs used in HELLO messages are specified in The three address block TLVs used in HELLO messages are specified in
Table 3. Table 3.
+----------------+------+-------------------+-----------------------+ +----------------+------+-------------------+-----------------------+
| Name | Type | Length | Value | | Name | Type | Length | Value |
+----------------+------+-------------------+-----------------------+ +----------------+------+-------------------+-----------------------+
| OTHER_IF | TBD | 0 bits | Not Applicable | | OTHER_IF | TBD | 0 bits | Not Applicable |
| | | | | | | | | |
| LINK_STATUS | TBD | 8 bits | One of LOST, | | LINK_STATUS | TBD | 8 bits | One of LOST, |
| | | | SYMMETRIC or HEARD | | | | | SYMMETRIC or HEARD |
| | | | | | | | | |
| OTHER_NEIGHB | TBD | 8 bits | One of LOST or | | OTHER_NEIGHB | TBD | 8 bits | One of LOST or |
| | | | SYMMETRIC | | | | | SYMMETRIC |
+----------------+------+-------------------+-----------------------+ +----------------+------+-------------------+-----------------------+
Table 3 Table 3
7. HELLO Message Generation 8. Local Information Base Changes
The Local Information Base MUST change to respond to changes in the
node's MANET interfaces. The protocol MUST update its Neighborhood
Information Base in response to such changes, and MAY transmit HELLO
messages in response to such changes.
8.1. Adding a MANET Interface
If a MANET interface is added to the node then this is indicated by
the addition of a Local Interface Tuple to the Local Interface Set.
The Neighbor Interface Base is not changed. A HELLO message MAY be
sent on all MANET interfaces, it SHOULD be sent on the new interface.
If using scheduled messages, a message schedule MUST be established
on the new interface.
8.2. Removing a MANET Interface
If a MANET interface is removed from the node, then this MUST result
be the removal of information from the Local Information Base and the
Neighborhood Information Base as follows:
1. Identify the Local Interface Tuple from the Local Interface Set
which corresponds to the interface to be removed, and:
1. all Link Tuples whose L_local_iface_addr is included in the
I_local_iface_addr_list of that Local Interface Tuple MUST be
removed;
2. all Symmetric Neighbor Tuples whose N_local_iface_addr is
included in the I_local_iface_addr_list of that Local
Interface Tuple MUST be removed;
3. all 2-Hop Neighbor Tuples whose N2_local_iface_addr is
included in the I_local_iface_addr_list of the Local
Interface Tuple MUST be removed;
4. the Local Interface Tuple MUST be removed from the Local
Interface Set.
2. All Neighborhood Address Association Tuples for which none of the
addresses in its NA_neighbor_iface_addr_list may be found in any
L_neighbor_iface_addr_list in the Link Set SHOULD be removed.
If the removed interface is the last MANET interface of the node,
then the Neighborhood Information Base SHOULD be empty, and the node
no longer participates in the protocol.
A HELLO message MAY be sent on all remaining MANET interfaces.
8.3. Adding an Address to a MANET Interface
If an address is added to a MANET interface then this is indicated by
the addition of an address to the appropriate
I_local_iface_addr_list. No change is made to the Neighbor
Information Base. A HELLO message MAY be sent on all MANET
interfaces.
8.4. Removing an Address from a MANET Interface
If an address is removed from a MANET interface then this is
indicated by the removal of an address to the appropriate
I_local_iface_addr_list. No change is made to the Neighbor
Information Base unless the removed address is the principal address
of the MANET Interface, in which case first a new principal address
of the interface is selected, as described in Section 8.5. A HELLO
message MAY be sent on all MANET interfaces.
8.5. Changing the Principal Address of a MANET Interface
If the principal address of a MANET interface of a node is changed
then this is indicated by a reordering of the appropriate
I_local_iface_addr_list. The following changes MUST be made to the
Local Information Base:
1. all Link Tuples whose L_local_iface_addr is equal to the old
first address in this I_local_iface_addr_list have that
L_local_iface_addr set equal to the new first address in this
I_local_iface_addr_list;
2. all Symmetric Neighbor Tuples whose N_local_iface_addr is equal
to the old first address in this I_local_iface_addr_list have
that N_local_iface_addr set equal to the new first address in
this I_local_iface_addr_list;
3. all 2-Hop Neighbor Tuples whose N2_local_iface_addr is equal to
the old first address in this I_local_iface_addr_list have that
N2_local_iface_addr set equal to the new first address in this
I_local_iface_addr_list.
A HELLO message SHOULD NOT be sent in response to this change.
9. HELLO Message Generation
HELLO messages MUST be generated and transmitted independently on HELLO messages MUST be generated and transmitted independently on
each MANET interface. If using the HELLO message interval each MANET interface. If using the HELLO message interval
HELLO_INTERVAL then, following a HELLO message transmission on a HELLO_INTERVAL then, following a HELLO message transmission on a
MANET interface, another HELLO message MUST be sent on the same MANET interface, another HELLO message MUST be sent on the same
interface after an interval not greater than HELLO_INTERVAL. Two interface after an interval not greater than HELLO_INTERVAL. Two
successive HELLO message transmissions on the same MANET interface successive HELLO message transmissions on the same MANET interface
MUST be separated by at least HELLO_MIN_INTERVAL, except as noted in MUST be separated by at least HELLO_MIN_INTERVAL, except as noted in
Section 7.1.1. Section 9.1.1.
A HELLO message MUST include a Local Interface Block as specified in A HELLO message MUST include a Local Interface Block as specified in
Section 6.1.1 as its first address block. Section 7.1.1 as its first address block.
Other addresses which MUST be included in HELLO messages are: Other addresses which MUST be included in HELLO messages are:
o addresses of 1-hop neighbors from the Link Set; o addresses of 1-hop neighbors from the Link Set;
o addresses of 1-hop neighbors from the Symmetric Neighbor Set. o addresses of 1-hop neighbors from the Symmetric Neighbor Set.
These addresses MUST NOT be included in the Local Interface Block. These addresses MUST NOT be included in the Local Interface Block.
These addresses MAY be included in any HELLO messages sent on the These addresses MAY be included in any HELLO messages sent on the
appropriate MANET interface. These addresses, and their associated appropriate MANET interface. These addresses, and their associated
TLVs, are: TLVs, are:
1. For each address which appears as an L_neighbor_iface_addr in one 1. For each address which appears in an L_neighbor_iface_addr_list
or more Link Tuples whose L_local_iface_addr is an address of the (a neighbor address) in one or more Link Tuples whose
MANET interface over which the HELLO message is to be sent, L_local_iface_addr is the principal address of the MANET
include that L_neighbor_iface_addr with an associated TLV with: interface over which the HELLO message is to be sent (i.e. the
first address listed in the corresponding
I_local_iface_addr_list), and whose L_STATUS does not equal
PENDING, include the neighbor address with an associated TLV
with:
* Type = LINK_STATUS; AND * Type = LINK_STATUS; AND
* Value = L_STATUS. * Value = L_STATUS.
2. For each address which appears as an N_neighbor_iface_addr in one 2. For each address which appears as an N_neighbor_iface_addr in one
or more Symmetric Neighbor Tuples: or more Symmetric Neighbor Tuples:
1. if this address has already been included with an associated 1. if this address has already been included with an associated
TLV with Type == LINK_STATUS and Value == SYMMETRIC, do not TLV with Type == LINK_STATUS and Value == SYMMETRIC, do not
skipping to change at page 16, line 31 skipping to change at page 20, line 34
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 messages as long as each such TLV is included associated with that
address in a HELLO message sent on that MANET interface in every address in a HELLO message sent on that MANET interface in every
interval of length REFRESH_INTERVAL. interval of length 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.
7.1. HELLO Message: Transmission 9.1. HELLO Message: Transmission
Messages are transmitted in the packet/message format specified by Messages are transmitted in the packet/message format specified by
[1] using the ALL-MANET-NEIGHBORS multicast address as destination IP [1] using the ALL-MANET-NEIGHBORS multicast address as destination IP
address, and with the HELLO message hop limit = 1. address, and with the HELLO message hop limit = 1.
If the parameters of the protocol are changed, then guarantees given If the parameters of the protocol are changed, then guarantees given
for the old values of the parameters MUST still be respected. In for the old values of the parameters MUST still be respected. In
particular: particular:
o If HELLO_INTERVAL is increased, then a HELLO message MUST be sent o If HELLO_INTERVAL is increased, then a HELLO message MUST be sent
within the old HELLO_INTERVAL of the previous HELLO message sent within the old HELLO_INTERVAL of the previous HELLO message sent
on each MANET interface. on each MANET interface.
o If REFRESH_INTERVAL is increased, then all information (addresses o If REFRESH_INTERVAL is increased, then all information (addresses
and associated TLVs) must be sent again on each MANET interface and associated TLVs) must be sent again on each MANET interface
within the old REFRESH_INTERVAL of the previous HELLO message that within the old REFRESH_INTERVAL of the previous HELLO message that
included that information. included that information.
7.1.1. HELLO Message: Jitter 9.1.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 Appendix D.
Internally triggered message generation MAY be treated as if Internally triggered message generation MAY be treated as if
externally generated message generation, or MAY be not jittered. 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
skipping to change at page 18, line 5 skipping to change at page 22, line 5
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.
8. HELLO Message Processing 10. HELLO Message Processing
On receiving a HELLO message, a node MUST update its neighborhood On receiving a HELLO message, a node MUST update its neighborhood
information base. information base.
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 the "validity time" of a message is calculated from the
VALIDITY_TIME TLV of the message as specified in Appendix C; VALIDITY_TIME TLV of the HELLO message as specified in Appendix C;
o the "Source Address" is the first address, including prefix o the "Receiving Address List" is the I_local_iface_addr_list
length, of the Local Interface Block in the HELLO message; corresponding to the MANET interface on which the HELLO message
was received;
o the "Receiving Address" is the address, including prefix length, o the "Receiving Address" is the first address in the Receiving
of the MANET interface on which the HELLO message was received; Address List, i.e. is the principal address of the MANET interface
on which the HELLO message was received;
o the "Sending Address List" is the list of the addresses contained
in the Local Interface Block of the HELLO message which do not
have an associated TLV with Type == OTHER_IF;
o the word EXPIRED indicates that a timer is set to a value clearly o the word EXPIRED indicates that a timer is set to a value clearly
preceding the current time (e.g. current time - 1). preceding the current time (e.g. current time - 1).
8.1. Populating the Link Set 10.1. Populating the Link Set
On receiving a HELLO message, a node SHOULD update its Link Set: On receiving a HELLO message, a node SHOULD update its Link Set:
1. If there is no Link Tuple with: 1. If there is no Link Tuple such that:
* L_local_iface_addr == Receiving Address; AND * L_local_iface_addr == Receiving Address; AND
* L_neighbor_iface_addr == Source Address, * L_neighbor_iface_addr_list contains one or more addresses in
the Sending Address List.
then create a new Link Tuple with then create a new Link Tuple with:
* L_local_iface_addr = Receiving Address; * L_local_iface_addr = Receiving Address;
* L_neighbor_iface_addr = Source Address;
* L_SYM_time = EXPIRED; * L_SYM_time = EXPIRED;
* L_quality = INITIAL_QUALITY;
* L_pending = INITIAL_PENDING;
* L_lost = false;
* L_LOST_time = EXPIRED;
* L_time = current time + validity time. * L_time = current time + validity time.
2. This Link Tuple (existing or new) is then modified as follows: 2. This Link Tuple (existing or new) is then modified as follows:
1. If the node finds the Receiving Address in one of the address 1. If the node finds any address in the Receiving Address List
blocks included in the HELLO message, other than the Local in one of the address blocks included in the HELLO message,
Interface Block, then the Link Tuple is modified as follows: other than the Local Interface Block, then the Link Tuple is
modified as follows:
1. If the Receiving Address in that address block is 1. If any such address in the HELLO message is associated
with a TLV with Type == LINK_STATUS and (Value == HEARD
or Value == SYMMETRIC) then:
- L_SYM_time = current time + validity time;
- L_time = L_SYM_time + L_HOLD_TIME.
2. Otherwise if any such address in the HELLO message is
associated with a TLV with Type == LINK_STATUS and Value associated with a TLV with Type == LINK_STATUS and Value
== LOST then: == LOST then:
1. if L_STATUS == SYMMETRIC: 1. if L_STATUS == SYMMETRIC:
o L_time = current time + max(validity time, o L_time = current time + max(validity time,
L_HOLD_TIME), L_HOLD_TIME),
o L_SYM_time = EXPIRED. o L_SYM_time = EXPIRED.
2. Otherwise if the Receiving Address in that address block 2. L_neighbor_iface_addr_list = Sending Address List;
is associated with a TLV with Type == LINK_STATUS and
(Value == HEARD or Value == SYMMETRIC) then:
- L_SYM_time = current time + validity time;
- L_time = L_SYM_time + L_HOLD_TIME.
2. L_ASYM_time = current time + validity time; 3. L_ASYM_time = current time + validity time;
3. L_time = max(L_time, L_ASYM_time). 4. L_time = max(L_time, L_ASYM_time).
8.2. Populating the Symmetric Neighbor Set 10.2. Populating the Symmetric Neighbor Set
On receiving a HELLO message, a node SHOULD update its Symmetric On receiving a HELLO message, a node SHOULD update its Symmetric
Neighbor Set: Neighbor Set:
1. If the Receiving Address is in an address block of the HELLO 1. If any address in the Receiving Address List is in an address
message, other than the Local Interface Block, with an associated block of the HELLO message, other than the Local Interface Block,
TLV with Type == LINK_STATUS and (Value == HEARD or Value == with an associated TLV with Type == LINK_STATUS and (Value ==
SYMMETRIC) then: HEARD or Value == SYMMETRIC) then:
1. For each address (henceforth neighbor address) in the HELLO 1. For each address (henceforth neighbor address) in the HELLO
message's Local Interface Block: message's Local Interface Block where a corresponding link
tuple with L_STATUS == SYMMETRIC exists in the link set:
1. If there is a Symmetric Neighbor Tuple with: 1. If there is no Symmetric Neighbor Tuple such that:
- N_local_iface_addr == Receiving Address; AND - N_local_iface_addr == Receiving Address; AND
- N_neighbor_iface_addr == neighbor address, - N_neighbor_iface_addr == neighbor address,
then update this Symmetric Neighbor Tuple to have: then create a new Symmetric Neighbor Tuple with:
- N_SYM_time = current time + validity time;
- N_time = N_SYM_time + N_HOLD_TIME.
2. Otherwise create a new Symmetric Neighbor Tuple with:
- N_local_iface_addr = Receiving Address; - N_local_iface_addr = Receiving Address;
- N_neighbor_iface_addr = neighbor address; - N_neighbor_iface_addr = neighbor address;
2. This Symmetric Neighbor Tuple (existing or new) is then
modified as follows:
- N_SYM_time = current time + validity time; - N_SYM_time = current time + validity time;
- N_time = N_SYM_time + N_HOLD_TIME. - N_time = N_SYM_time + N_HOLD_TIME.
2. Otherwise if the Receiving Address is in an address block of the 2. Otherwise if any address in the Receiving Address List is in an
HELLO message, other than the Local Interface Block, with an address block of the HELLO message, other than the Local
associated TLV with Type == LINK_STATUS and Value == LOST, then: Interface Block, with an associated TLV with Type == LINK_STATUS
and Value == LOST, then:
1. For each address (henceforth neighbor address) in the HELLO 1. For each address (henceforth neighbor address) in the HELLO
message Local Interface Block, if there exists a Symmetric message Local Interface Block, if there exists a Symmetric
Neighbor Tuple with: Neighbor Tuple with:
+ N_local_iface_addr == Receiving Address; AND + N_local_iface_addr == Receiving Address; AND
+ N_neighbor_iface_addr == neighbor address, + N_neighbor_iface_addr == neighbor address,
update this Symmetric Neighbor Tuple to have: then update this Symmetric Neighbor Tuple to have:
+ N_SYM_time = EXPIRED; + N_SYM_time = EXPIRED;
+ N_time = min(N_time, current time + N_HOLD_TIME). + N_time = min(N_time, current time + N_HOLD_TIME).
8.3. Populating the Neighborhood Address Association Set 10.3. Populating the Neighborhood Address Association Set
On receiving a HELLO message, the node SHOULD update its Neighborhood On receiving a HELLO message, the node SHOULD update its Neighborhood
Address Association Set: Address Association Set:
1. Remove all Neighborhood Address Association Tuples where: 1. Remove all Neighborhood Address Association Tuples where:
* NA_neighbor_iface_addr_list contains at least one address * NA_neighbor_iface_addr_list contains at least one address
which is contained in the Local Interface Block of the which is contained in the Local Interface Block of the
received HELLO message, received HELLO message,
and create a new Neighborhood Address Association Tuple with: and create a new Neighborhood Address Association Tuple with:
* NA_neighbor_iface_addr_list = list of all addresses contained * NA_neighbor_iface_addr_list = list of all addresses contained
in the Local Interface Block of the received HELLO message; in the Local Interface Block of the received HELLO message;
* NA_time = current time + validity time. * NA_time = current time + validity time.
8.4. Populating the 2-Hop Neighbor Set 10.4. Populating the 2-Hop Neighbor Set
On receiving a HELLO message the node SHOULD update its 2-Hop On receiving a HELLO message the node SHOULD update its 2-Hop
Neighbor Set: Neighbor Set:
1. If there exists a Link Tuple with L_local_iface_addr == Source 1. If there exists a Link Tuple with L_local_iface_addr == Source
Address and L_STATUS == SYMMETRIC then: Address and for which L_STATUS == SYMMETRIC then:
1. For each address (henceforth 2-hop neighbor address) in an 1. For each address (henceforth 2-hop neighbor address) in an
address block of the HELLO message, other than the Local address block of the HELLO message, other than the Local
Interface Block, which is not an interface address of the Interface Block, which is not in any I_local_iface_addr_list
receiving node: (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: 1. If the 2-hop neighbor 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 with: then, if there is no 2-Hop Neighbor Tuple such that:
- N2_local_iface_addr == Receiving Address; - N2_local_iface_addr == Receiving Address;
- N2_neighbor_iface_addr == Source Address; - N2_neighbor_iface_addr_list contains one or more
addresses in the Sending Address List; AND
- N2_2hop_iface_addr == 2-hop neighbor address;
create a 2-Hop Neighbor Tuple with: - N2_2hop_iface_addr == 2-hop neighbor address.
- N2_local_iface_addr = Receiving Address; AND then create a 2-Hop Neighbor Tuple with:
- N2_neighbor_iface_addr = Source Address; AND - N2_local_iface_addr = Receiving Address;
- N2_2hop_iface_addr = 2-hop neighbor address. - N2_2hop_iface_addr = 2-hop neighbor address.
This 2-Hop Neighbor Tuple (existing or new) is then This 2-Hop Neighbor Tuple (existing or new) is then
modified as follows: modified as follows:
- 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 neighbor 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 Neighbor Tuples with:
- N2_local_iface_addr == Receiving Address; AND - N2_local_iface_addr == Receiving Address; AND
- N2_neighbor_iface_addr == Source Address; AND - N2_neighbor_iface_addr_list contains one or more
addresses in the Sending Address List; AND
- N2_2hop_iface_addr == 2-hop neighbor address. - N2_2hop_iface_addr == 2-hop neighbor address.
8.5. Neighborhood Changes 10.5. Neighborhood Changes
If the L_SYM_time field of a Link Tuple expires (either due to timing If L_STATUS of a Link Tuple changes from SYMMETRIC to any other
out, or as a result of processing a TLV with Type == LINK_STATUS and status, due to any of:
Value == LOST) then all 2-Hop Neighbor Tuples with:
o L_SYM_time expires;
o L_SYM_time is set to EXPIRED as result of processing a TLV with
Type == LINK_STATUS and Value == LOST;
o A change in L_quality resulting in L_quality < HYST_REJECT
then all 2-Hop Neighbor Tuples with:
o N2_local_iface_addr == L_local_iface_addr from the Link Tuple, o N2_local_iface_addr == L_local_iface_addr from the Link Tuple,
AND; AND;
o N2_neighbor_iface_addr == L_neighbor_iface_addr from the Link o N2_neighbor_iface_addr_list contains one or more addresses in the
Tuple, L_neighbor_iface_addr_list from the Link Tuple,
MUST be deleted. MUST be deleted.
In this, or any other case of neighborhood change, a node MAY send a In this, or any other case of neighborhood change, a node MAY send a
HELLO message reporting updated information, subject to the HELLO message reporting updated information, subject to the
constraints in Section 7. constraints in Section 9.
9. Proposed Values for Constants 11. Link Hysteresis
Link hysteresis allows associating a L_quality value with a link.
Using this L_quality in conjunction with two thresholds, HYST_ACCEPT
and HYST_REJECT, as well as for each link a L_pending and a L_lost
flag, Section 6.1 allows determining the L_STATUS of a link.
The basic principles of link hysteresis are as follows:
o A node does not advertise a neighbor interface in any state until
L_quality is acceptable. If INITIAL_PENDING == true, this is such
that L_quality >= HYST_ACCEPT, otherwise this is such that
L_quality >= HYST_REJECT; to ensure the latter a node MUST NOT
define INITIAL_PENDING == false and INITIAL_QUALITY < HYST_REJECT.
(A node also MUST NOT define INITIAL_PENDING == true and
INITIAL_QUALITY >= HYST_ACCEPT.) A link which is not yet
advertised has L_pending == true.
o Once L_quality >= HYST_ACCEPT, the L_pending flag is set false,
indicating that the link can be advertised.
o A link for which L_pending == false is advertised until its
L_quality drops below HYST_REJECT.
o If a link has L_pending == false and L_quality < HYST_REJECT, the
link is LOST and is advertised as such. This link is not
reconsidered as a candidate HEARD or SYMMETRIC link until
L_quality >= HYST_ACCEPT.
o A link which has an acceptable quality may be advertised as HEARD,
SYMMETRIC or LOST according to the exchange of HELLO messages.
If L_quality for a link changes, the following actions MUST be taken:
1. if L_quality >= HYST_ACCEPT then the corresponding Link Tuple is
modified by:
* L_pending = false;
* L_lost = false;
* L_LOST_time = EXPIRED.
2. if L_quality < HYST_REJECT then the corresponding Link Tuple is
modified by:
* L_lost = true
* L_LOST_time = current time + L_HOLD_TIME
Any corresponding Tuples in the Symmetric Neighbor Set and 2-Hop
Neighbor Set MUST be removed.
If L_quality for a link is updated based on HELLO message reception,
or on reception of a packet including a HELLO message, then L_quality
MUST be updated prior to the HELLO processing described in
Section 10. (If the receipt of the HELLO message, or the packet
containing it, creates the Link Tuple then instead the Link Tuple
MUST be created with the updated L_quality value.)
11.1. Link Quality
A node MAY never update link quality (L_quality). In this case the
node MUST define:
o INITIAL_PENDING = false;
o INITIAL_QUALITY >= HYST_REJECT (there is no reason not to define
INITIAL_QUALITY = 1).
A node MAY update link quality based on any information available to
it. Particular cases that MAY be used include:
o Link layer information, see Appendix E.
o Receipt or loss of packets. Provided packets include a packet
sequence number as defined in [1], packets on a link SHOULD have
sequential packet sequence numbers, whether or not they include
HELLO messages. Link quality can be updated when a packet is
received based on, for example, whether the last N out of M
packets on the link were received, or a "leaky integrator"
tracking packets.
o Receipt or loss of HELLO messages. If the maximum interval
between HELLO messages is known (possibly by inclusion of a
message TLV with Type == INTERVAL_TIME as defined in Appendix C.2
in HELLO messages) then the loss of HELLO messages can be
determined without the need to receive a HELLO message. Note that
if this case is combined with the previous case then care must be
taken to avoid "double counting" a lost HELLO message in a lost
packet.
12. Proposed Values for Constants
This section lists proposed values for the constants used in the This section lists proposed values for the constants used in the
specification of the protocol. specification of the protocol.
9.1. Message Intervals 12.1. Message Intervals
o HELLO_INTERVAL = 2 seconds o HELLO_INTERVAL = 2 seconds
o REFRESH_INTERVAL = HELLO_INTERVAL o REFRESH_INTERVAL = HELLO_INTERVAL
o HELLO_MIN_INTERVAL = HELLO_INTERVAL/4 o HELLO_MIN_INTERVAL = HELLO_INTERVAL/4
9.2. Holding Times 12.2. Holding Times
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 o N_HOLD_TIME = H_HOLD_TIME
9.3. Jitter Times 12.3. Hysteresis values
If link quality is not changed then:
o HYST_ACCEPT = 1
o HYST_REJECT = 0
o INITIAL_QUALITY = 1
o INITIAL_PENDING = false
Otherwise, i.e. if link quality is changed, then these parameters
will be dependent on the link quality process used. Example possible
parameters are:
o HYST_ACCEPT = 0.75
o HYST_REJECT = 0.25
o INITIAL_QUALITY = 0.5
o INITIAL_PENDING = true
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 = HELLO_INTERVAL/4
9.4. Time 12.5. Time
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 In order to achieve interoperability, C MUST be the same on all
nodes. nodes.
10. IANA Considerations 13. IANA Considerations
10.1. Multicast Addresses 13.1. Multicast Addresses
A well-known link-local multicast address, ALL-MANET-NEIGHBORS, must A well-known link-local multicast address, ALL-MANET-NEIGHBORS, must
be registered and defined for both IPv6 and IPv4. be registered and defined for both IPv6 and IPv4.
10.2. Message Types 13.2. 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 | | Mnemonic | Value | Description |
+--------------------+-------+--------------------------------------+ +--------------------+-------+--------------------------------------+
| HELLO | TBD | Local signaling | | HELLO | TBD | Local signaling |
+--------------------+-------+--------------------------------------+ +--------------------+-------+--------------------------------------+
Table 4 Table 4
10.3. TLV Types 13.3. TLV Types
This specification defines two Message TLV types, which must be This specification defines two Message TLV types, which must be
allocated from the "Assigned Message TLV Types" repository of [1]. allocated from the "Assigned Message TLV Types" repository of [1].
+--------------------+-------+--------------------------------------+ +--------------------+-------+--------------------------------------+
| Mnemonic | Value | Description | | Mnemonic | Value | Description |
+--------------------+-------+--------------------------------------+ +--------------------+-------+--------------------------------------+
| VALIDITY_TIME | TBD | The time (in seconds) from receipt | | VALIDITY_TIME | TBD | The time (in seconds) from receipt |
| | | of the message during which the | | | | of the message during which the |
| | | information contained in the message | | | | information contained in the message |
skipping to change at page 25, line 29 skipping to change at page 32, line 29
| OTHER_NEIGHB | TBD | Specifies that the address is | | OTHER_NEIGHB | TBD | Specifies that the address is |
| | | (SYMMETRIC) or was (LOST) of a MANET | | | | (SYMMETRIC) or was (LOST) of a MANET |
| | | interface of a symmetric 1-hop | | | | interface of a symmetric 1-hop |
| | | neighbor of the node transmitting | | | | neighbor of the node transmitting |
| | | the HELLO message, but does not have | | | | the HELLO message, but does not have |
| | | a matching or better LINK_STATUS TLV | | | | a matching or better LINK_STATUS TLV |
+--------------------+-------+--------------------------------------+ +--------------------+-------+--------------------------------------+
Table 6 Table 6
10.4. LINK_STATUS and OTHER_NEIGHB Values 13.4. 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
11. References 14. References
11.1. Normative References 14.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-03.txt, January 2007.
[2] Bradner, S., "Key words for use in RFCs to Indicate Requirement [2] 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.
11.2. Informative References 14.2. Informative References
[3] Clausen, T. and P. Jacquet, "The Optimized Link State Routing [3] Clausen, T. and P. Jacquet, "The Optimized Link State Routing
Protocol", RFC 3626, October 2003. Protocol", RFC 3626, October 2003.
Appendix A. Address Block TLV Combinations Appendix A. Address Block TLV Combinations
The algorithm for generating HELLO messages in Section 7 specifies The algorithm for generating HELLO messages in Section 9 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 7. These combinations generated by the algorithm in Section 9. These
combinations are indicated in Table 7. combinations are indicated in Table 7.
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 7. Cells labeled with "No" generated by the algorithm in Section 9. Cells labeled with "No"
indicate combinations not generated by the algorithm in Section 7, indicate combinations not generated by the algorithm in Section 9,
but which are correctly parsed and interpreted by the algorithm in but which are correctly parsed and interpreted by the algorithm in
Section 8. Section 10.
+----------------+----------------+----------------+----------------+ +----------------+----------------+----------------+----------------+
| | 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 33, line 18 skipping to change at page 40, line 18
neighborhoods, and since NHDP is a building block for MANET routing neighborhoods, and since NHDP is a building block for MANET routing
protocols employing other triggered or periodic message exchanges, protocols employing other triggered or periodic message exchanges,
this appendix presents global concerns pertaining to jittering of this appendix presents global concerns pertaining to jittering of
MANET control traffic. MANET control traffic.
D.1. Jitter D.1. Jitter
In order to prevent nodes in a MANET from simultaneous transmission, In order to prevent nodes in a MANET from simultaneous transmission,
whilst retaining the MANET characteristic of maximum node autonomy, a whilst retaining the MANET characteristic of maximum node autonomy, a
randomization of the transmission time of packets by nodes, known as randomization of the transmission time of packets by nodes, known as
jitter, may be employed. Note that while jitter may resolve the jitter, MAY be employed. Three jitter mechanisms, which target
problem of simultaneous transmissions, the delays it introduces will different aspects of this problem, MAY be employed, with the aim of
otherwise only have a negative impact on a well-designed protocol. reducing the likelihood of simultaneous transmission, and, if it
Thus jitter parameters should always be minimized, subject to their occurs, preventing it from continuing.
acceptably achieving their intent. 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: Three cases exist:
o Periodic message generation; o Periodic message generation;
o Externally triggered message generation; o Externally triggered message generation;
o Message forwarding. 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 D.1.1. Periodic message generation
When a node generates a message periodically, two successive messages When a node generates a message periodically, two successive messages
will be separated by a well-defined interval, denoted here will be separated by a well-defined interval, denoted
MESSAGE_INTERVAL. A node may maintain more than one such interval, MESSAGE_INTERVAL. A node MAY maintain more than one such interval,
e.g. for different message types or in different circumstances (such e.g. for different message types or in different circumstances (such
as backing off transmissions to avoid congestion). Jitter may be as backing off transmissions to avoid congestion). Jitter MAY be
applied by reducing this delay by a random amount, so that the delay applied by reducing this delay by a random amount, so that the delay
between consecutive transmissions of a messages of the same type is between consecutive transmissions of a messages of the same type is
equal to (MESSAGE_INTERVAL - jitter), where jitter is the random equal to (MESSAGE_INTERVAL - jitter), where jitter is the random
value. value.
Subtraction of the random value from the message interval ensures Subtraction of the random value from the message interval ensures
that the message interval never exceeds the nominal message interval, that the message interval never exceeds MESSAGE_INTERVAL, and does
and does not adversely affect timeouts or other mechanisms which may not adversely affect timeouts or other mechanisms which may be based
be based on message late arrival or failure to arrive. Note that by on message late arrival or failure to arrive. By basing the message
basing the message transmission time on the previous transmission transmission time on the previous transmission time, rather than by
time, rather than by jittering a fixed clock, nodes can become jittering a fixed clock, nodes can become completely desynchronized,
completely desynchronized, which minimizes their probability of which minimizes their probability of repeated collisions. This is
collisions. particularly useful when combined with externally triggered message
generation and rescheduling.
It is appropriate and convenient for the jitter value to be taken The jitter value SHOULD be taken from a uniform distribution between
from a uniform distribution between zero and a maximum value, denoted zero and MAXJITTER.
here MAXJITTER. MAXJITTER must be significantly less than the
current value of MESSAGE_INTERVAL. MAXJITTER may be a single fixed
parameter (in which case it must be significantly less than all
values of MESSAGE_INTERVAL) or be based on MESSAGE_INTERVAL (for
example it may be a fixed proportion of MESSAGE_INTERVAL).
Note that a node will know its own MESSAGE_INTERVAL value and can Note that a node will know its own MESSAGE_INTERVAL value and can
readily ensure that any MAXJITTER value used is appropriate. readily ensure that any MAXJITTER value used satisfies the conditions
in Appendix D.1.4.
D.1.2. Externally triggered message generation D.1.2. Externally triggered message generation
When a node responds to an externally triggered change in An internal or external condition or event MAY trigger message
circumstances which is likely to also affect other nodes by generation by a node. Depending upon the protocol, this condition
generating a message, that message may be jittered by delaying it by MAY trigger generation of a single message, initiation of a new
a random duration. If this message is of a type which is periodic message schedule, or rescheduling of existing periodic
periodically transmitted then it may be appropriate to restart its messaging. Collision between externally triggered messages is made
schedule of these messages, this should be based on this delayed more likely if more than one node is likely to respond to the same
time. In some cases there may be a minimum interval between such event. To reduce this likelihood, an externally triggered message
messages, in this case it may be appropriate to jitter that minimum MAY be jittered by delaying it by a random duration; an internally
interval time. 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.
The normal delay on a triggered message may be generated uniformly in When messages are triggered, whether or not they are also
an interval between zero and a maximum delay, denoted here MAXJITTER. periodically transmitted, a protocol MAY impose a minimum interval
Selection of MAXJITTER will be protocol specific. In some cases the between messages of the same type, denoted MESSAGE_MIN_INTERVAL. It
delay may be fixed, or fixed according to the message type. In the is however appropriate to also allow this interval to be reduced by
case of a regularly scheduled message, at an interval denoted here jitter, so that when a message is transmitted the next message is
MESSAGE_INTERVAL, MAXJITTER must be significantly less than allowed after a time (MESSAGE_MIN_INTERVAL - jitter), where jitter
MESSAGE_INTERVAL. This may require prior agreement as to the value SHOULD be generated uniformly in an interval between zero and
(or minimum value) of MESSAGE_INTERVAL, be by inclusion of MAXJITTER (using a value of MAXJITTER appropriate to periodic message
MESSAGE_INTERVAL (the time until the next relevant message, rather transmission). This is because otherwise, when external triggers are
than the time since the last) in the message, or use any other more frequent than MESSAGE_MIN_INTERVAL, it takes the role of
protocol specific mechanism. 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 D.1.3. Message forwarding
When a node forwards a message it may be jittered by delaying it by a When a node forwards a message, it may be jittered by delaying it by
random time. The normal delay on a triggered message may be a random duration. This delay SHOULD be generated uniformly in an
generated uniformly in an interval between zero and a maximum delay, interval between zero and MAXJITTER.
denoted here MAXJITTER. The value of MAXJITTER will be protocol
specific and may in some cases be fixed, possibly by message type. Unlike the cases of periodically generated and externally triggered
However in the case of a regularly scheduled message, at an interval messages, a node is not automatically aware of the message
denoted here MESSAGE_INTERVAL, MAXJITTER must be significantly less originator's value of MESSAGE_INTERVAL, which is required to select a
than MESSAGE_INTERVAL. This may require prior agreement as to the value of MAXJITTER which is known to be valid. This may require
value (or minimum value) of MESSAGE_INTERVAL, may be by inclusion in prior agreement as to the value (or minimum value) of
the message of MESSAGE_INTERVAL (the time until the next relevant MESSAGE_INTERVAL, may be by inclusion in the message of
message, rather than the time since the last message) or be by any MESSAGE_INTERVAL (the time until the next relevant message, rather
other protocol specific mechanism. The choice of MAXJITTER may also than the time since the last message) or be by any other protocol
take into account the expected number of times that the message may specific mechanism, which may include estimation of the value of
be forwarded. MESSAGE_INTERVAL based on received message times.
For several possible reasons (differing parameters, message For several possible reasons (differing parameters, message
rescheduling, extreme random values) a node may receive a message rescheduling, extreme random values) a node may receive a message
while still waiting to forward an earlier message of the same type while still waiting to forward an earlier message of the same type
originating from the same node. This is possible without jitter, but originating from the same node. This is possible without jitter, but
may occur more often with it. The appropriate action to take is may occur more often with it. The appropriate action to take is
protocol specific (typically to discard the earlier message or to protocol specific (typically to discard the earlier message or to
forward both, possible modifying timing to maintain message order). forward both, possible modifying timing to maintain message order).
In many cases, including [3] and protocols using the full In many cases, including [3] and protocols using the full
functionality of [1], messages are transmitted hop by hop in functionality of [1], messages are transmitted hop by hop in
potentially multi-message packets, and some or all of those messages potentially multi-message packets, and some or all of those messages
may need to be forwarded. For efficiency this should be in a single 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 packet, and hence the forwarding jitter of all messages received in a
single packet should be the same. For this to have the intended single packet should be the same. (This also requires that a single
distribution it is necessary to choose a single random jitter for all value of MAXJITTER is used in this case.) For this to have the
messages. It is not appropriate to give each message a random jitter intended uniform distribution it is necessary to choose a single
and then using the smallest of these jitter values, as that produces random jitter for all messages. It is not appropriate to give each
a jitter with a reduced mean value. 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 In addition, the protocol may permit messages received in different
packets to be combined, possibly also with locally generated messages packets to be combined, possibly also with locally generated messages
(scheduled or triggered). However in this case the purpose of the (periodically generated or triggered). However in this case the
jitter will be accomplished by choosing any of the independently purpose of the jitter will be accomplished by choosing any of the
scheduled times for these events as the single forwarding time; this independently scheduled times for these events as the single
may have to be the earliest time to achieve all constraints. This is forwarding time; this may have to be the earliest time to achieve all
because without combining messages, a transmission was due at this constraints. This is because without combining messages, a
time anyway. transmission was due at this time anyway.
D.1.4. Maximum Jitter Determination
In considering how the maximum jitter (one or more instances of
parameter MAXJITTER) may be determined, the following points may be
noted:
o While jitter may resolve the problem of simultaneous
transmissions, the timing changes (in particular the delays) it
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
that are relevant apply to each instance of MAXJITTER:
* it MUST NOT be greater than MESSAGE_INTERVAL/2;
* it SHOULD be significantly less than MESSAGE_INTERVAL;
* it MUST NOT be greater than MESSAGE_MIN_INTERVAL;
* it SHOULD NOT be greater than MESSAGE_MIN_INTERVAL/2.
o As well as the decision as to whether to use jitter being
dependent on the medium access control and lower layers, the
selection of the MAXJITTER parameter should be appropriate to
those mechanisms.
o As jitter is intended to reduce collisions, greater jitter, i.e.
an increased value of MAXJITTER, is appropriate when the chance of
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
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 Appendix E. Utilizing Link Layer Information
The interface between NHDP and any protocol(s) using NHDP is through The interface between NHDP and any protocol(s) using NHDP is through
the Neighborhood Information Base as defined in Section 5. The the Neighborhood Information Base as defined in Section 6. The
message exchange and associated processing specified in Section 7 and message exchange and associated processing specified in Section 9 and
Section 8 allow fully maintaining this Neighborhood Information Base. Section 10 allow fully maintaining this Neighborhood Information
Base.
Different link layers, and even different implementations of the same Different link layers, and even different implementations of the same
link layer, may make varying amount of information available link layer, may make varying amount of information available
describing local connectivity. If present, such link layer describing local connectivity. If present, such link layer
information MAY be used to supplement, or replace, elements of NHDP information MAY be used to supplement, or replace, elements of NHDP
as follows: as follows:
No link layer information - Absent any link layer information on a No link layer information - Absent any link layer information on a
MANET interface, NHDP MUST be employed for populating all sets of MANET interface, NHDP MUST be employed for populating all sets of
the Neighborhood Information Base as defined in this the Neighborhood Information Base as defined in this
specification. specification.
Failed data delivery - If link layer information is available on a Failed data delivery - If link layer information is available on a
MANET interface, identifying when data delivery to a presumed MANET interface, identifying when data delivery to a presumed
directly connected node has failed, NHDP MUST be employed for directly connected node has failed, NHDP MUST be employed for
populating all sets of the Neighborhood Information Base as populating all sets of the Neighborhood Information Base as
defined in this specification. The link layer information MAY be defined in this specification. The link layer information MAY be
used to degrade a presumed directly connected node from being used to degrade a presumed directly connected node from being
considered as SYMMETRIC to being considered HEARD or LOST. A considered as SYMMETRIC to being considered HEARD or LOST. A
HELLO message reflecting these changes MAY be generated, HELLO message reflecting these changes MAY be generated,
respecting the considerations in Section 7. respecting the considerations in Section 9.
Link quality information - The link layer may make available "soft" Link quality information - The link layer may make available "soft"
information (possibly derived from the physical layer) relating to information (possibly derived from the physical layer) relating to
the link quality. NHDP MAY be able to use this information, in a the link quality. NHDP MAY be able to use this information, in a
normalized form, to adjust the link status between LOST, HEARD and normalized form, to adjust the link status between LOST, HEARD and
SYMMETRIC. SYMMETRIC.
Local (1-hop) connectivity - If link layer information is available Local (1-hop) connectivity - If link layer information is available
on a MANET interface, identifying the local (1-hop) connectivity on a MANET interface, identifying the local (1-hop) connectivity
via that interface, then this information MAY be used as follows via that interface, then this information MAY be used as follows
when generating HELLO messages over that interface: when generating HELLO messages over that interface:
* Step 1 in Hello Message Generation (Section 7) MAY be ignored. * Step 1 in Hello Message Generation (Section 9) MAY be ignored.
This implies that local connectivity verification over that This implies that local connectivity verification over that
MANET interface is not performed by NHDP, but is using the link MANET interface is not performed by NHDP, but is using the link
layer information. layer information.
* All other steps in Hello Message Generation (Section 7) MUST be * All other steps in Hello Message Generation (Section 9) MUST be
carried out, such that Neighborhood Address Association Sets carried out, such that Neighborhood Address Association Sets
and 2-Hop Neighbor Sets can be populated correctly. and 2-Hop Neighbor Sets can be populated correctly.
* All MANET interfaces which do not have local (1-hop) * All MANET interfaces which do not have local (1-hop)
connectivity information available MUST employ the message connectivity information available MUST employ the message
exchange as detailed in this specification. exchange as detailed in this specification.
Appendix F. Security Considerations Appendix F. 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
skipping to change at page 38, line 33 skipping to change at page 46, line 33
specification of protocols which use information provided by NHDP. 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 F.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 lie 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 MANET
interfaces of the local node which transmits the HELLO message; interfaces of the local node which transmits 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 MANET interfaces of the local node which transmits
the HELLO message; the HELLO message;
* The Local Interface Block may contain OTHER_IF TLVs, indicating * The Local Interface Block may contain OTHER_IF TLVs, indicating
incorrectly that an address is associated with a MANET incorrectly that an address is associated with a MANET
interface other than the one over which the HELLO message is interface other than the one over which the HELLO message is
being transmitted; being 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 being transmitted;
A node may lie about the identity of other nodes: A node may provide false information about the identity of other
nodes:
* A present or absent address in an address block, other than in * A present or absent address in an address block, other than in
the Local Interface Block, does not in and by itself cause a the Local Interface Block, does not in and by itself cause a
problem. It is the presence, absence or incorrectness of problem. It is the presence, absence or incorrectness of
associated LINK_STATUS and OTHER_NEIGHB TLVs that cause associated LINK_STATUS and OTHER_NEIGHB TLVs that cause
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 node which is or was in the sending node's 1-hop
neighborhood; neighborhood;
 End of changes. 118 change blocks. 
275 lines changed or deleted 641 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/