INTERNET-DRAFT Thomas Clausen
IETF MANET Working Group Emmanuel Baccelli
Expiration: 11 January 2006 LIX, Ecole Polytechnique, France
11 July 2005
OLSRv2 Link Hysteresis
draft-clausen-olsrv2-link-hysteresis-00.txt
Status of this Memo
This document is a submission to the Mobile Adhoc NETworks (MANET)
Working Group of the Internet Engineering Task Force (IETF). Comments
should be submitted to the manet@ietf.org mailing list.
Distribution of this memo is unlimited.
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC 2026.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that other
groups may also distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Abstract
Established links between MANET nodes should be as reliable as
possible in order to avoid data packet loss. This implies that MANET
nodes' link sensing should be robust against bursty loss or transient
connectivity between nodes. Therefore, in order to enhance the
robustness of link sensing mechanisms, additional link hysteresis
strategies are used. This draft describes such a hysteresis mechanism
for OLSRv2.
Clausen, Baccelli [Page 1]
INTERNET-DRAFT OLSRv2 Link Hysteresis 9 July 2005
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2. Applicability . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. OLSRv2 Link Hysteresis . . . . . . . . . . . . . . . . . . . . . 4
2.1. Additional Information in the Link Set . . . . . . . . . . . . 4
2.2. Additional Steps in Hello Message Generation . . . . . . . . . 4
2.3. Hysteresis Strategy . . . . . . . . . . . . . . . . . . . . . . 5
2.4. Interoperability Considerations . . . . . . . . . . . . . . . . 7
2.5. Proposed Values for Constants . . . . . . . . . . . . . . . . . 7
3. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 8
4. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5. References . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
6. Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . . 9
8. Security Considerations . . . . . . . . . . . . . . . . . . . . . 9
9. Copyright . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Clausen, Baccelli [Page 2]
INTERNET-DRAFT OLSRv2 Link Hysteresis 9 July 2005
1. Introduction
Established links between MANET nodes should be as reliable as possi-
ble in order to avoid data packet loss. This implies that link sens-
ing should be robust against bursty loss or transient connectivity
between nodes. Hence, to enhance the robustness of the link sensing
mechanism, an additional link hysteresis strategy should be used.
This draft describes such a hysteresis mechanism for OLSRv2. This
draft supplements OLSRv2 basic specifications [2].
1.1. Terminology
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC2119 [5].
This document supplements the OLSRv2 specification. Several refer-
ences are made to the OLSR terminology described in [1] and [2].
Among others, this document uses the following terminology:
- Node: a device capable of participating in a MANET.
- Neighbor Node: A node X is a neighbor node of node Y if node
Y can hear node X.
- Multipoint Relay (MPR): A node which is selected by its
neighbor, node X, to "re-transmit" all the broadcast messages
it emits.
- Neighbor Set: The information repository including the list
of the links established by a node with its neighbors. This
information also includes the quality of those links.
- HELLO messages: A node performs link sensing (the discovery
of its neighborhood) via the periodic exchange of HELLO
messages with its neighbors.
- TLV: a TLV is an attribute, associated to a message or set of
addresses. This attribute is in a type-length-value format.
1.2. Applicability
This draft describes a link hysteresis mechanism for OLSRv2. The
specified recommendations SHOULD be considered for an OLSRv2 imple-
mentation. This draft supplements OLSRv2 basic specifications [2].
Clausen, Baccelli [Page 3]
INTERNET-DRAFT OLSRv2 Link Hysteresis 9 July 2005
2. OLSRv2 Link Hysteresis
Established links should be as reliable as possible to avoid data
packet loss. This implies that link sensing should be robust against
bursty loss or transient connectivity between nodes. Hence, to
enhance the robustness of the link sensing mechanism, the following
implementation recommendations SHOULD be considered in OLSRv2. These
recommendations are supplement to the specifications of [2].
2.1. Additional Information in the Link Set
Each link tuple in the neighbor links set of a given OLSRv2 node
SHOULD include (i) a L_link_pending field, (ii) a L_link_quality
field, and (iii) a L_LOST_LINK_time field. L_link_pending is a
boolean value specifying if the link is considered pending (i.e., the
link is not considered established). L_link_quality is a dimension-
less number between 0 and 1 describing the quality of the link.
L_LOST_LINK_time is a timer for declaring a link as lost when an
established link becomes pending.
2.2. Additional Steps in Hello Message Generation
HELLO message generation SHOULD consider those fields as follows:
1 if L_LOST_LINK_time is not expired, the link is advertised
with a link type of LOST_LINK.
2 otherwise, if L_LOST_LINK_time is expired and L_link_pending
is set to "true", the link SHOULD NOT be advertised at all;
3 otherwise, if L_LOST_LINK_time is expired and L_link_pending
is set to "false", the link is advertised.
A node considers that it has a symmetric link for each link tuple
where:
1 L_LOST_LINK_time is expired, AND
2 L_link_pending is "false", AND
3 L_SYM_time is not expired.
This definition for "symmetric link" SHOULD thereby also be used as
basis for the symmetric neighborhood when computing the MPR set, as
Clausen, Baccelli [Page 4]
INTERNET-DRAFT OLSRv2 Link Hysteresis 9 July 2005
well as for "the symmetric neighbors" in the first steps of the rout-
ing table calculation.
The L_link_quality, L_link_pending and L_LOST_LINK_time fields are
exclusively updated according to the present section. This section
does not modify the function of any other fields in the link tuples.
Additionally, HELLO messages must include a specific message TLV
called H-Time (see Table 1).
+-------------+-------------------------------------+---------------+
| TLV Type | TLV Value | Default Value |
+-------------+-------------------------------------+---------------+
| H-Time | HELLO emission interval | HTIME_DEFAULT |
+-------------+-------------------------------------+---------------+
Table 1
This TLV specifies the HELLO emission interval used by the node on
this particular interface, i.e., the time before the transmission of
the next HELLO. The HELLO emission interval is represented by its
mantissa (four highest bits of H-Time field) and by its exponent
(four lowest bits of Htime field). In other words:
HELLO emission interval = C*(1+a/16)*2^b [in seconds]
where a is the integer represented by the four highest bits of H-Time
field and b the integer represented by the four lowest bits of H-Time
field. This H-Time value, as the additional parameters
L_LOST_LINK_time, L_link_pending and L_link_quality, is used by the
hysteresis strategy described in the following section.
2.3. Hysteresis Strategy
The link between a node and some of its neighbor interfaces might be
"bad", i.e., from time to time let HELLOs pass through only to fade
out immediately after. In this case, the neighbor information base
would contain a bad link for at least "validity time". The following
hysteresis strategy SHOULD be adopted to counter this situation.
For each neighbor interface NI heard by interface I, the L_link_qual-
ity field of the corresponding Link Tuple determines the establish-
ment of the link. The value of L_link_quality is compared to two
thresholds HYST_THRESHOLD_HIGH, HYST_THRESHOLD_LOW, fixed between 0
and 1 and such that HYST_THRESHOLD_HIGH >= HYST_THRESHOLD_LOW. With
Clausen, Baccelli [Page 5]
INTERNET-DRAFT OLSRv2 Link Hysteresis 9 July 2005
L_time specifying the time at which the Link Tuple expires, the
L_link_pending field is set according to the following:
1 if L_link_quality > HYST_THRESHOLD_HIGH:
L_link_pending = false
L_LOST_LINK_time = current time - 1 (expired)
2 otherwise, if L_link_quality < HYST_THRESHOLD_LOW:
L_link_pending = true
L_LOST_LINK_time = min (L_time, current time +
NEIGHB_HOLD_TIME)
3 otherwise, if HYST_THRESHOLD_LOW <= L_link_quality
<= HYST_THRESHOLD_HIGH:
L_link_pending and L_LOST_LINK_time remain unchanged.
The condition for considering a link established is thus stricter
than the condition for dropping a link. Notice thus, that a link can
be dropped based on either timer expiration or on L_link_quality
dropping below HYST_THRESHOLD_LOW.
Also notice, that even if a link is not considered as established by
the link hysteresis, the link tuples are still updated for each
received HELLO message. Specifically, this implies that, regardless
of whether or not the link hysteresis considers a link as "estab-
lished", tuples in the link set do not expire except as determined by
the L_time field of the link tuples.
As a basic implementation requirement, an estimation of the link
quality must be maintained and stored in the L_link_quality field.
If some measure of the signal/noise level on a received message is as
estimation after normalization.
If no signal/noise information or other link quality information is
available from the link layer, an algorithm such as the following can
be utilized (it is an exponentially smoothed moving average of the
transmission success rate). The algorithm is parameterized by a
scaling parameter HYST_SCALING which is a number fixed between 0 and
1. For each neighbor interface NI heard by interface I, the first
time NI is heard by I, L_link_quality is set to HYST_SCALING
(L_link_pending is set to true and L_LOST_LINK_time to current time -
1).
Clausen, Baccelli [Page 6]
INTERNET-DRAFT OLSRv2 Link Hysteresis 9 July 2005
A tuple is updated according to two rules. Every time an OLSR packet
emitted by NI is received by I, the stability rule is applied:
L_link_quality = (1-HYST_SCALING)*L_link_quality
+ HYST_SCALING.
When an OLSRv2 packet emitted by NI is lost by I, the instability
rule is applied:
L_link_quality = (1-HYST_SCALING)*L_link_quality.
The loss of OLSRv2 packet is detected by tracking the missing Packet
Sequence Numbers on a per interface basis and by "long period of
silence" from a node. A "long period of silence" may be detected
thus: if no OLSRv2 packet has been received on interface I from
interface NI during HELLO emission interval of interface NI (computed
from the H-Time field in the last HELLO message received from NI), a
loss of an OLSRv2 packet is detected.
2.4. Interoperability Considerations
Link hysteresis determines, for a node, the criteria at which a link
to a neighbor node is accepted or rejected. Nodes in a network may
have different criteria, according to the nature of the media over
which they are communicating. Once a link is accepted, it is adver-
tised, in accordance with the provisions described in the previous
sections of this specification.
2.5. Proposed Values for Constants
Here are the proposed values for the constants mentionned in the pre-
vious sections.
HYST_THRESHOLD_HIGH = 0.8
HYST_THRESHOLD_LOW = 0.3
HYST_SCALING = 0.5
NEIGHB_HOLD_TIME = 6 seconds
H-Time = 2 seconds
C = 1/16
Clausen, Baccelli [Page 7]
INTERNET-DRAFT OLSRv2 Link Hysteresis 9 July 2005
3. Authors' Addresses
Thomas Heide Clausen,
Project PCRI
Pole Commun de Recherche en Informatique du plateau de Saclay,
CNRS, Ecole Polytechnique, INRIA, Universite Paris Sud,
Ecole polytechnique,
Laboratoire d'informatique,
91128 Palaiseau Cedex, France
Phone: +33 1 69 33 40 73,
Email: T.Clausen@computer.org
Emmanuel Baccelli
HITACHI Labs Europe/ Project PCRI,
Pole Commun de Recherche en Informatique du plateau de Saclay,
CNRS, Ecole Polytechnique, INRIA, Universite Paris Sud,
Ecole polytechnique,
Laboratoire d'informatique,
91128 Palaiseau Cedex, France
Phone: +33 1 69 33 40 73,
Email: Emmanuel.Baccelli@inria.fr
4. Contributors
Cedric Adjih, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153 Le
Chesnay Cedex, France, Phone: +33 1 3963 5215, Email:
Cedric.Adjih@inria.fr
Philippe Jacquet, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153
Le Chesnay Cedex, France, Phone: +33 1 3963 5263, Email:
Philippe.Jacquet@inria.fr
Anis Laouiti, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153 Le
Chesnay Cedex, France, Phone: +33 1 3963 5088, Email:
Anis.Laouiti@inria.fr
Paul Muhlethaler, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153
Le Chesnay Cedex, France, Phone: +33 1 3963 5278, Email:
Paul.Muhlethaler@inria.fr
Clausen, Baccelli [Page 8]
INTERNET-DRAFT OLSRv2 Link Hysteresis 9 July 2005
Ryuji Wakikawa, Keio University and WIDE, 5322 Endo Fujisawa
Kanagawa, 252 JAPAN, Email: ryuji@sfc.wide.ad.jp
Christopher Dearlove, BAE SYSTEMS Advanced Technology Centre, Great
Baddow, Chelmsford, UK. Phone: +44 1245 242194 Email:
chris.dearlove@baesystems.com
Amir Qayyum Center for Advanced Research in Engineering Pvt. Ltd. 19
Ataturk Avenue Islamabad, Pakistan Phone: +92-51-2874115 Email:
amir@carepvtltd.com
Laurent Viennot Project HIPERCOM INRIA Rocquencourt, BP 105 78153 Le
Chesnay Cedex, France Phone: +33 1 3963 5225 Email:
Laurent.Viennot@inria.fr
5. References
[1] T. Clausen, P. Jacquet, RFC 3626: Optimized Link State Routing Pro-
tocol. Request for Comments (Experimental), Internet Engineering
Task Force, October 2003.
[2] T. Clausen, Optimized Link State Routing Protocol version 2, IETF
Internet Draft draft-clausen-manet-olsrv2-00, July 2005.
6. Changes
This is the initial version of this specification.
7. IANA Considerations
This document does currently not specify IANA considerations.
8. Security Considerations
This document does not specify any security considerations.
9. Copyright
Copyright (C) The Internet Society (2005). This document is subject
to the rights, licenses and restrictions contained in BCP 78, and
except as set forth therein, the authors retain all their rights.
This document and the information contained herein are provided on
Clausen, Baccelli [Page 9]
INTERNET-DRAFT OLSRv2 Link Hysteresis 9 July 2005
an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE
REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE
INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.