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.