draft-ietf-manet-olsr-08.txt   draft-ietf-manet-olsr-09.txt 
INTERNET-DRAFT Cedric Adjih INTERNET-DRAFT Cedric Adjih
IETF MANET Working Group Thomas Clausen IETF MANET Working Group Thomas Clausen
Expiration: 03 September 2003 Philippe Jacquet Expiration: 15 October 2003 Philippe Jacquet
Anis Laouiti Anis Laouiti
Pascale Minet Pascale Minet
Paul Muhlethaler Paul Muhlethaler
Amir Qayyum Amir Qayyum
Laurent Viennot Laurent Viennot
INRIA Rocquencourt, France INRIA Rocquencourt, France
03 March 2003 15 April 2003
Optimized Link State Routing Protocol Optimized Link State Routing Protocol
draft-ietf-manet-olsr-08.txt draft-ietf-manet-olsr-09.txt
Status of this Memo Status of this Memo
This document is a submission by the Mobile Ad Hoc Networking Working This document is a submission by the Mobile Ad Hoc Networking Working
Group of the Internet Engineering Task Force (IETF). Comments should Group of the Internet Engineering Task Force (IETF). Comments should
be submitted to the manet@itd.nrl.navy.mil mailing list. be submitted to the manet@itd.nrl.navy.mil mailing list.
Distribution of this memo is unlimited. Distribution of this memo is unlimited.
This document is an Internet-Draft and is in full conformance with This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC 2026. all provisions of Section 10 of RFC 2026.
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 other Task Force (IETF), its areas, and its working groups. Note that
groups may also distribute working documents as Internet-Drafts. other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
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
skipping to change at page 2, line 15 skipping to change at page 2, line 15
Abstract Abstract
This document describes the Optimized Link State Routing (OLSR) This document describes the Optimized Link State Routing (OLSR)
protocol for mobile ad hoc networks. The protocol is an optimization protocol for mobile ad hoc networks. The protocol is an optimization
of the classical link state algorithm tailored to the requirements of of the classical link state algorithm tailored to the requirements of
a mobile wireless LAN. The key concept used in the protocol is that a mobile wireless LAN. The key concept used in the protocol is that
of multipoint relays (MPRs) [1], [2]. MPRs are selected nodes which of multipoint relays (MPRs) [1], [2]. MPRs are selected nodes which
forward broadcast messages during the flooding process. This forward broadcast messages during the flooding process. This
technique substantially reduces the message overhead as compared to a technique substantially reduces the message overhead as compared to a
classical flooding mechanism, where every node retransmits each classical flooding mechanism, where every node retransmits each
message when it receives the first copy of the message. In OLSR, link message when it receives the first copy of the message. In OLSR,
state information is generated only by nodes elected as MPRs. Thus, a link state information is generated only by nodes elected as MPRs.
second optimization is achieved by minimizing the number of control Thus, a second optimization is achieved by minimizing the number of
messages flooded in the network. As a third optimization, an MPR node control messages flooded in the network. As a third optimization, an
may chose to report only links between itself and its MPR selectors. MPR node may chose to report only links between itself and its MPR
Hence, as contrary to the classic link state algorithm, partial link selectors. Hence, as contrary to the classic link state algorithm,
state information is distributed in the network. This information is partial link state information is distributed in the network. This
then used by for route calculation. OLSR provides optimal routes (in information is then used by for route calculation. OLSR provides
terms of number of hops). The protocol is particularly suitable for optimal routes (in terms of number of hops). The protocol is
large and dense networks as the technique of MPRs works well in this particularly suitable for large and dense networks as the technique
context. of MPRs works well in this context.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 6 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1. Changes . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1. Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2. OLSR Terminology . . . . . . . . . . . . . . . . . . . . . 7 1.2. OLSR Terminology . . . . . . . . . . . . . . . . . . . . . . . 7
1.3. Applicability . . . . . . . . . . . . . . . . . . . . . . 9 1.3. Applicability . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4. Protocol Overview . . . . . . . . . . . . . . . . . . . . 9 1.4. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . . 10
1.5. Multipoint Relays . . . . . . . . . . . . . . . . . . . . 10 1.5. Multipoint Relays . . . . . . . . . . . . . . . . . . . . . . . 11
2. Protocol Functioning . . . . . . . . . . . . . . . . . . . . . . 12
2. Protocol Functioning . . . . . . . . . . . . . . . . . . . . 11 2.1. Core Functioning . . . . . . . . . . . . . . . . . . . . . . . 12
2.1. Core Functioning . . . . . . . . . . . . . . . . . . . . . 12 2.2. Auxiliary Functioning . . . . . . . . . . . . . . . . . . . . . 14
2.2. Auxiliary Functioning . . . . . . . . . . . . . . . . . . 12 3. Packet Format and Forwarding . . . . . . . . . . . . . . . . . . 15
3.1. Protocol and Port Number . . . . . . . . . . . . . . . . . . . 16
3. Packet Format and Forwarding . . . . . . . . . . . . . . . . 13 3.2. Main Address . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.1. Protocol and Port Number . . . . . . . . . . . . . . . . . 14 3.3. Packet Format . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2. Main Address . . . . . . . . . . . . . . . . . . . . . . . 14 3.3.1. Packet Header . . . . . . . . . . . . . . . . . . . . . . . . 17
3.3. Packet Format . . . . . . . . . . . . . . . . . . . . . . 14 3.3.2. Message Header . . . . . . . . . . . . . . . . . . . . . . . 17
3.3.1. Packet Header . . . . . . . . . . . . . . . . . . . . . 15 3.4. Packet Processing and Message Flooding . . . . . . . . . . . . 19
3.3.2. Message Header . . . . . . . . . . . . . . . . . . . . . 15 3.4.1. Default Forwarding Algorithm . . . . . . . . . . . . . . . . 21
3.4. Packet Processing and Message Flooding . . . . . . . . . . 17 3.4.2. Considerations on Processing and Forwarding . . . . . . . . . 22
3.4.1. Default Forwarding Algorithm . . . . . . . . . . . . . . 18 3.5. Message Emission and Jitter . . . . . . . . . . . . . . . . . . 23
3.4.2. Considerations on Processing and Forwarding . . . . . . 19 4. Information Repositories . . . . . . . . . . . . . . . . . . . . 24
3.5. Message Emission and Jitter . . . . . . . . . . . . . . . 20 4.1. Multiple Interface Association Information Base . . . . . . . . 24
4.2. Link sensing: Local Link Information Base . . . . . . . . . . . 25
4. Link Sensing and Neighbor Detection . . . . . . . . . . . . 21 4.2.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1. Local Link Information Base . . . . . . . . . . . . . . . 21 4.3. Neighbor Detection: Neighborhood Information Base . . . . . . . 25
4.1.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . . 21 4.3.1. Neighbor Set . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1.2. Neighbor Set . . . . . . . . . . . . . . . . . . . . . . 22 4.3.2. 2-hop Neighbor Set . . . . . . . . . . . . . . . . . . . . . 26
4.1.3. 2-hop Neighbor Set . . . . . . . . . . . . . . . . . . . 22 4.3.3. MPR Set . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.1.4. MPR Set . . . . . . . . . . . . . . . . . . . . . . . . 22 4.3.4. MPR Selector Set . . . . . . . . . . . . . . . . . . . . . . 26
4.1.5. MPR Selector Set . . . . . . . . . . . . . . . . . . . . 22 4.4. Topology Information Base . . . . . . . . . . . . . . . . . . . 26
4.2. HELLO Message Format . . . . . . . . . . . . . . . . . . . 23 5. Main Addresses and Multiple Interfaces . . . . . . . . . . . . . 27
4.2.1. Link Code as Link Type and Neighbor Type . . . . . . . . 25 5.1. MID Message Format . . . . . . . . . . . . . . . . . . . . . . 27
4.3. HELLO Message Generation . . . . . . . . . . . . . . . . . 26 5.2. MID Message Generation . . . . . . . . . . . . . . . . . . . . 28
4.4. Populating the Link Set . . . . . . . . . . . . . . . . . 28 5.3. MID Message Forwarding . . . . . . . . . . . . . . . . . . . . 28
4.4.1. HELLO Message Processing . . . . . . . . . . . . . . . . 29 5.4. MID Message Processing . . . . . . . . . . . . . . . . . . . . 29
4.5. Populating the Neighbor Set . . . . . . . . . . . . . . . 30 5.5. Resolving a Main Address from an Interface Address . . . . . . 29
4.5.1. HELLO Message Processing . . . . . . . . . . . . . . . . 32 6. HELLO Message Format and Generation . . . . . . . . . . . . . . . 30
4.6. Populating the 2-hop Neighbor Set . . . . . . . . . . . . 32 6.1. HELLO Message Format . . . . . . . . . . . . . . . . . . . . . 30
4.6.1. Hello Message Processing . . . . . . . . . . . . . . . . 32 6.1.1. Link Code as Link Type and Neighbor Type . . . . . . . . . . 33
4.6.2. Populating the MPR set . . . . . . . . . . . . . . . . . 34 6.2. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 34
4.6.3. MPR Computation . . . . . . . . . . . . . . . . . . . . 34 6.3. HELLO Message Forwarding . . . . . . . . . . . . . . . . . . . 36
4.7. Populating the MPR Selector Set . . . . . . . . . . . . . 35 6.4. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 36
4.7.1. Hello Message Processing . . . . . . . . . . . . . . . . 35 7. Link Sensing . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.8. Neighborhood and 2-hop Neighborhood Changes . . . . . . . 36 7.1. Populating the Link Set . . . . . . . . . . . . . . . . . . . . 37
7.1.1. HELLO Message Processing . . . . . . . . . . . . . . . . . . 37
5. Topology Discovery . . . . . . . . . . . . . . . . . . . . . 37 8. Neighbor Detection . . . . . . . . . . . . . . . . . . . . . . . 39
5.1. TC Message Format . . . . . . . . . . . . . . . . . . . . 37 8.1. Populating the Neighbor Set . . . . . . . . . . . . . . . . . . 39
5.2. Topology Information Base . . . . . . . . . . . . . . . . 38 8.1.1. HELLO Message Processing . . . . . . . . . . . . . . . . . . 40
5.3. Advertised Neighbor Set . . . . . . . . . . . . . . . . . 39 8.2. Populating the 2-hop Neighbor Set . . . . . . . . . . . . . . . 41
5.4. TC Message Generation . . . . . . . . . . . . . . . . . . 39
5.5. TC Message Forwarding. . . . . . . . . . . . . . . . . . 39
5.6. TC Message Processing . . . . . . . . . . . . . . . . . . 40
5.7. Routing Table Calculation . . . . . . . . . . . . . . . . 41
6. Node Configuration . . . . . . . . . . . . . . . . . . . . . 43
6.1. Address Assignment . . . . . . . . . . . . . . . . . . . . 43
6.2. Routing Configuration . . . . . . . . . . . . . . . . . . 43
6.3. Data Packet Forwarding . . . . . . . . . . . . . . . . . . 44
7. Multiple OLSR Interfaces . . . . . . . . . . . . . . . . . . 44
7.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 44
7.2. Multiple Interface Functioning . . . . . . . . . . . . . . 45
7.3. Multiple Interface Declaration . . . . . . . . . . . . . . 47
7.3.1. Multiple Interface Association Information Base . . . . 47
7.3.2. MID Message Format . . . . . . . . . . . . . . . . . . . 47
7.3.3. MID Message Generation . . . . . . . . . . . . . . . . . 48
7.3.4. MID Message Forwarding . . . . . . . . . . . . . . . . . 48
7.3.5. MID Message Processing . . . . . . . . . . . . . . . . . 48
7.4. Main Addresses vs. Interface Addresses . . . . . . . . . . 49
7.5. Populating the Neighbor Set . . . . . . . . . . . . . . . 50
7.6. Populating the MPR Set . . . . . . . . . . . . . . . . . . 50
7.6.1. MPR Computation . . . . . . . . . . . . . . . . . . . . 51
7.7. Routing Table Calculation . . . . . . . . . . . . . . . . 51
7.8. Changes to the "Default Forwarding Algorithm" . . . . . . 52
8. Non OLSR Interfaces . . . . . . . . . . . . . . . . . . . . 55
8.1. HNA Message Format . . . . . . . . . . . . . . . . . . . . 55
8.2. Host and Network Association Information Base . . . . . . 56
8.3. HNA Message Generation . . . . . . . . . . . . . . . . . . 57
8.4. HNA Message Forwarding . . . . . . . . . . . . . . . . . . 57
8.5. HNA Message Processing . . . . . . . . . . . . . . . . . . 57
8.6. Routing Table Calculation . . . . . . . . . . . . . . . . 58
9. Link Layer Notification . . . . . . . . . . . . . . . . . . 58
10. Link Hysteresis . . . . . . . . . . . . . . . . . . . . . . 59
10.1. Local Link Set . . . . . . . . . . . . . . . . . . . . . 59
10.2. Hello Message Generation . . . . . . . . . . . . . . . . 60
10.3. Hysteresis Strategy . . . . . . . . . . . . . . . . . . . 61
11. Distributing Redundant Topology Information . . . . . . . . 62
11.1. TC_REDUNDANCY Parameter . . . . . . . . . . . . . . . . . 62
12. MPR Redundancy . . . . . . . . . . . . . . . . . . . . . . 63
12.1. MPR_COVERAGE Parameter . . . . . . . . . . . . . . . . . 63
12.2. MPR Computation . . . . . . . . . . . . . . . . . . . . . 64
13. IPv6 Considerations . . . . . . . . . . . . . . . . . . . . 65
14. Security Considerations . . . . . . . . . . . . . . . . . . 65
14.1. Confidentiality . . . . . . . . . . . . . . . . . . . . . 65
14.2. Integrity . . . . . . . . . . . . . . . . . . . . . . . . 65
14.3. Interaction with External Routing Domains . . . . . . . . 66
15. Proposed Values for Constants . . . . . . . . . . . . . . . 67
15.1. Setting emission interval and holding times . . . . . . . 67
15.2. Emission Interval . . . . . . . . . . . . . . . . . . . . 68
15.3. Holding time . . . . . . . . . . . . . . . . . . . . . . 68
15.4. Message Types . . . . . . . . . . . . . . . . . . . . . . 69
15.5. Link Types . . . . . . . . . . . . . . . . . . . . . . . 69
15.6. Neighbor Types . . . . . . . . . . . . . . . . . . . . . 69
15.7. Link Hysteresis . . . . . . . . . . . . . . . . . . . . . 69
15.8. Willingness . . . . . . . . . . . . . . . . . . . . . . . 70
15.9. Misc. Constants . . . . . . . . . . . . . . . . . . . . . 70
16. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . 71
17. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 71
18. Authors' Addresses . . . . . . . . . . . . . . . . . . . . 71 8.2.1. HELLO Message Processing . . . . . . . . . . . . . . . . . . 41
8.3. Populating the MPR set . . . . . . . . . . . . . . . . . . . . 42
8.3.1. MPR Computation . . . . . . . . . . . . . . . . . . . . . . . 43
8.4. Populating the MPR Selector Set . . . . . . . . . . . . . . . . 45
8.4.1. HELLO Message Processing . . . . . . . . . . . . . . . . . . 45
8.5. Neighborhood and 2-hop Neighborhood Changes . . . . . . . . . . 46
9. Topology Discovery . . . . . . . . . . . . . . . . . . . . . . . 47
9.1. TC Message Format . . . . . . . . . . . . . . . . . . . . . . . 47
9.2. Advertised Neighbor Set . . . . . . . . . . . . . . . . . . . . 48
9.3. TC Message Generation . . . . . . . . . . . . . . . . . . . . . 49
9.4. TC Message Forwarding. . . . . . . . . . . . . . . . . . . . . 49
9.5. TC Message Processing . . . . . . . . . . . . . . . . . . . . . 49
10. Routing Table Calculation . . . . . . . . . . . . . . . . . . . 51
11. Node Configuration . . . . . . . . . . . . . . . . . . . . . . . 54
11.1. Address Assignment . . . . . . . . . . . . . . . . . . . . . . 54
11.2. Routing Configuration . . . . . . . . . . . . . . . . . . . . 55
11.3. Data Packet Forwarding . . . . . . . . . . . . . . . . . . . . 55
12. Non OLSR Interfaces . . . . . . . . . . . . . . . . . . . . . . 55
12.1. HNA Message Format . . . . . . . . . . . . . . . . . . . . . . 56
12.2. Host and Network Association Information Base . . . . . . . . 56
12.3. HNA Message Generation . . . . . . . . . . . . . . . . . . . . 57
12.4. HNA Message Forwarding . . . . . . . . . . . . . . . . . . . . 57
12.5. HNA Message Processing . . . . . . . . . . . . . . . . . . . . 57
12.6. Routing Table Calculation . . . . . . . . . . . . . . . . . . 58
12.7. Interoperability Considerations . . . . . . . . . . . . . . . 59
13. Link Layer Notification . . . . . . . . . . . . . . . . . . . . 59
13.1. Interoperability Considerations . . . . . . . . . . . . . . . 60
14. Link Hysteresis . . . . . . . . . . . . . . . . . . . . . . . . 60
14.1. Local Link Set . . . . . . . . . . . . . . . . . . . . . . . . 61
14.2. Hello Message Generation . . . . . . . . . . . . . . . . . . . 61
14.3. Hysteresis Strategy . . . . . . . . . . . . . . . . . . . . . 62
14.4. Interoperability Considerations . . . . . . . . . . . . . . . 64
15. Redundant Topology Information . . . . . . . . . . . . . . . . . 64
15.1. TC_REDUNDANCY Parameter . . . . . . . . . . . . . . . . . . . 64
15.2. Interoperability Considerations . . . . . . . . . . . . . . . 65
16. MPR Redundancy . . . . . . . . . . . . . . . . . . . . . . . . . 65
16.1. MPR_COVERAGE Parameter . . . . . . . . . . . . . . . . . . . . 66
16.2. MPR Computation . . . . . . . . . . . . . . . . . . . . . . . 66
16.3. Interoperability Considerations . . . . . . . . . . . . . . . 67
17. IPv6 Considerations . . . . . . . . . . . . . . . . . . . . . . 67
18. Proposed Values for Constants . . . . . . . . . . . . . . . . . 68
18.1. Setting emission interval and holding times . . . . . . . . . 68
18.2. Emission Interval . . . . . . . . . . . . . . . . . . . . . . 68
18.3. Holding time . . . . . . . . . . . . . . . . . . . . . . . . . 69
18.4. Message Types . . . . . . . . . . . . . . . . . . . . . . . . 70
18.5. Link Types . . . . . . . . . . . . . . . . . . . . . . . . . . 70
18.6. Neighbor Types . . . . . . . . . . . . . . . . . . . . . . . . 70
18.7. Link Hysteresis . . . . . . . . . . . . . . . . . . . . . . . 71
18.8. Willingness . . . . . . . . . . . . . . . . . . . . . . . . . 71
18.9. Misc. Constants . . . . . . . . . . . . . . . . . . . . . . . 72
19. References . . . . . . . . . . . . . . . . . . . . . . . . 72 19. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . . . 72
20. Security Considerations . . . . . . . . . . . . . . . . . . . . 72
20.1. Confidentiality . . . . . . . . . . . . . . . . . . . . . . . 73
20.2. Integrity . . . . . . . . . . . . . . . . . . . . . . . . . . 73
20.3. Interaction with External Routing Domains . . . . . . . . . . 74
20.4. Node Identity . . . . . . . . . . . . . . . . . . . . . . . . 74
21. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 75
22. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . 75
23. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 75
24. References . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
1. Introduction 1. Introduction
The Optimized Link State Routing Protocol (OLSR) is developed for The Optimized Link State Routing Protocol (OLSR) is developed for
mobile ad hoc networks. It operates as a table driven, proactive pro- mobile ad hoc networks. It operates as a table driven, proactive
tocol, i.e exchanges topology information with other nodes of the protocol, i.e exchanges topology information with other nodes of the
network regularly. Each node selects a set of its neighbor nodes as network regularly. Each node selects a set of its neighbor nodes as
"multipoint relays" (MPR). In OLSR, only nodes, selected as such "multipoint relays" (MPR). In OLSR, only nodes, selected as such
MPRs, are responsible for forwarding control traffic, intended for MPRs, are responsible for forwarding control traffic, intended for
diffusion into the entire network. I.e. MPRs provide an efficient diffusion into the entire network. MPRs provide an efficient mecha-
mechanism for flooding control traffic by reducing the number of nism for flooding control traffic by reducing the number of transmis-
transmissions required. sions required.
Nodes, selected as MPRs, also have a special responsibility when Nodes, selected as MPRs, also have a special responsibility when
declaring link state information in the network. Indeed, the only declaring link state information in the network. Indeed, the only
requirement for OLSR to provide routes to all destinations is that requirement for OLSR to provide shortest path routes to all destina-
MPR nodes declare link-state information for links between them self tions is that MPR nodes declare link-state information for their MPR
and their MPR selectors. Additional available link-state information selectors. Additional available link-state information may be uti-
may be utilized, e.g. for redundancy. lized, e.g. for redundancy.
Nodes which have been selected as a multipoint relay by some neighbor Nodes which have been selected as multipoint relays by some neighbor
node(s) announce this information periodically in their control mes- node(s) announce this information periodically in their control mes-
sages. Thereby a node announces to the network, that it has reacha- sages. Thereby a node announces to the network, that it has reacha-
bility to the nodes which have selected it as MPR. In route calcula- bility to the nodes which have selected it as an MPR. In route cal-
tion, the MPRs are used to form the route from a given node to any culation, the MPRs are used to form the route from a given node to
destination in the network. Furthermore, the protocol uses the MPRs any destination in the network. Furthermore, the protocol uses the
to facilitate efficient flooding of control messages in the network. MPRs to facilitate efficient flooding of control messages in the net-
work.
A node selects MPRs from among its one hop neighbors with "symmetri- A node selects MPRs from among its one hop neighbors with "symmetri-
cal", i.e. bi-directional, linkages. Therefore, selecting the route cal", i.e. bi-directional, linkages. Therefore, selecting the route
through MPRs automatically avoids the problems associated with data through MPRs automatically avoids the problems associated with data
packet transfer over uni-directional links (such as the problem of packet transfer over uni-directional links (such as the problem of
not getting link-layer acknowledgments for data packets at each hop) not getting link-layer acknowledgments for data packets at each hop,
for link-layers employing this technique for unicast traffic).
OLSR is developed to work independently from other protocols. Like- OLSR is developed to work independently from other protocols. Like-
wise, OLSR makes no assumptions about the underlying link-layer. wise, OLSR makes no assumptions about the underlying link-layer.
OLSR inherits the concept of forwarding and relaying from HIPERLAN (a OLSR inherits the concept of forwarding and relaying from HIPERLAN (a
MAC layer protocol) which is standardized by ETSI [3]. The protocol MAC layer protocol) which is standardized by ETSI [3]. The protocol
is developed in the IPANEMA project (part of the Euclid program) and is developed in the IPANEMA project (part of the Euclid program) and
in the PRIMA project (part of the RNRT program). in the PRIMA project (part of the RNRT program).
1.1. Changes 1.1. Changes
Major changes from version 07 to version 08 Major changes from version 08 to version 09
- Restructured draft in order to improve readability and modu- - Merged multiple interface
larity: core protocol functionality contained in the main part
of the draft. Advanced features (multiple interfaces, redun-
dant MPR flooding and tc-redundancy) are moved to later sec-
tions.
- Small change to message format. - Further separated link sensing, neighbor sensing and hello
message generation
- "Neighbor sensing" changed to "link sensing and neighbor - Collected information repositories in single section
detection" to improve readability and modularity.
- Non-core functions moved from the core part of the draft. - Misc. editorial changes.
1.2. OLSR Terminology 1.2. OLSR Terminology
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC2119 [5]. Addition- document are to be interpreted as described in RFC2119 [5]. Addi-
ally, this doccument uses the following terminology: tionally, this document uses the following terminology:
node node
A MANET router which implements the Optimized Link State Rout- A MANET router which implements the Optimized Link State Rout-
ing protocol as specified in this document. ing protocol as specified in this document.
OLSR interface
A network device participating in a MANET running OLSR. A
node may have several OLSR interfaces, each interface assigned
an unique IP address.
non OLSR interface
A network device, not participating in a MANET running OLSR.
A node may have several OLSR interfaces (wireless and/or
wired). Routing information from these interfaces MAY be
injected into the OLSR routing domain.
single OLSR interface node
A node which has a single OLSR interface, participating in an
OLSR routing domain.
multiple OLSR interface node
A node which has multiple OLSR interfaces, participating in an
OLSR routing domain.
main address main address
The main address of a node, which will be used in OLSR control The main address of a node, which will be used in OLSR control
traffic as the "originator address" of all messages emitted by traffic as the "originator address" of all messages emitted by
this node. It is the address of one of its interfaces. If a this node. It is the address of one of the interfaces of the
node has only one interface, the main address is the address node.
of that interface.
A single OLSR interface node uses the address of its only OLSR
interface as the main address.
A multiple OLSR interface node MUST choose one of its OLSR
interface addresses as its "main address" (equivalent of
"router ID" or "node identifier"). It is of no importance
which address is chosen, however a node SHOULD always use the
same address as its main address.
neighbor node neighbor node
A node X is a neighbor node of node Y if node Y can hear node A node X is a neighbor node of node Y if node Y can hear node
X (i.e. one of X interfaces is a neighbor interface of some X (i.e. one of X OLSR interfaces is a neighbor interface of
interface of Y). some OLSR interface of Y).
2-hop neighbor 2-hop neighbor
An node heard by a neighbor. A node heard by a neighbor.
strict 2-hop neighbor strict 2-hop neighbor
a 2-hop neighbor which is not the node itself or a neighbor of a 2-hop neighbor which is not the node itself or a neighbor of
the node the node, and in addition is a neighbor of a neighbor, with
willingness different from WILL_NEVER, of the node.
multipoint relay (MPR) multipoint relay (MPR)
A node which is selected by its one-hop neighbor, node X, to A node which is selected by its one-hop neighbor, node X, to
"re-transmit" all the broadcast messages that it receives from "re-transmit" all the broadcast messages that it receives from
X, provided that the same message is not already received, and X, provided that the message is not a duplicate, and that the
the time to live field of the message is greater than one. time to live field of the message is greater than one.
multipoint relay selector (MPR selector, MS) multipoint relay selector (MPR selector, MS)
A node which has selected its one-hop neighbor, node X, as its A node which has selected its one-hop neighbor, node X, as its
multipoint relay, will be called a multipoint relay selector multipoint relay, will be called a multipoint relay selector
of node X. of node X.
interface
A network device participating in the MANET (usually a wire-
less device). A node may have several interfaces, each inter-
face assigned an unique IP address.
link link
A link is a pair of interfaces (from two different nodes) sus- A link is a pair of OLSR interfaces (from two different nodes)
ceptible to hear one another (i.e. one may be able to receive susceptible to hear one another (i.e. one may be able to
traffic from the other). A node is said to have a link to receive traffic from the other). A node is said to have a
another node when one of its interface has a link to one of link to another node when one of its interface has a link to
the interfaces of the other node. one of the interfaces of the other node.
symmetric link symmetric link
A bi-directional link between two interfaces, i.e. interface I A verified bi-directional link between two OLSR interfaces.
and interface J where both can hear each other.
asymmetric link asymmetric link
A link between two interfaces I and J, where it is confirmed A link between two OLSR interfaces I and J, verified in only
that I can hear J but not confirmed if J can hear I. one direction.
symmetric neighborhood symmetric 1-hop neighborhood
The symmetric neighborhood of any node X is the set of nodes The symmetric 1-hop neighborhood of any node X is the set of
which have at least one symmetric link to X. nodes which have at least one symmetric link to X.
symmetric 2-hop neighborhood symmetric 2-hop neighborhood
The symmetric 2-hop neighborhood of X is the set of nodes, The symmetric 2-hop neighborhood of X is the set of nodes,
excluding X itself, which have a symmetric link to the sym- excluding X itself, which have a symmetric link to the sym-
metric neighborhood of X. metric 1-hop neighborhood of X.
symmetric strict 2-hop neighborhood symmetric strict 2-hop neighborhood
The symmetric 2-hop neighborhood of X is the set of nodes, The symmetric 2-hop neighborhood of X is the set of nodes,
excluding X itself and its neighbor, which have a symmetric excluding X itself and its neighbors, which have a symmetric
link to the symmetric neighborhood of X. link to some symmetric 1-hop neighbor, with willingness dif-
ferent of WILL_NEVER, of X.
1.3. Applicability 1.3. Applicability
OLSR is a proactive routing protocol for mobile ad-hoc networks OLSR is a proactive routing protocol for mobile ad-hoc networks
(MANETs). It is well suited to large and dense mobile networks, as (MANETs). It is well suited to large and dense mobile networks, as
the optimization achieved using the MPRs works well in this context. the optimization achieved using the MPRs works well in this context.
The larger and more dense a network, the more optimization can be The larger and more dense a network, the more optimization can be
achieved as compared to the classic link state algorithm. OLSR uses achieved as compared to the classic link state algorithm. OLSR uses
hop-by-hop routing, i.e. each node uses its local information to hop-by-hop routing, i.e. each node uses its local information to
route packets. route packets.
OLSR is well suited for networks, where the traffic is random and OLSR is well suited for networks, where the traffic is random and
sporadic between "several" nodes rather than being almost exclusively sporadic between a larger set of nodes nodes rather than being almost
between a small specific set of nodes. As a proactive protocol, OLSR exclusively between a small specific set of nodes. As a proactive
is also suitable for scenarios where the communicating pairs change protocol, OLSR is also suitable for scenarios where the communicating
over time: no additional control traffic is generated in this situa- pairs change over time: no additional control traffic is generated in
tion since routes are maintained for all known destinations at all this situation since routes are maintained for all known destinations
times. at all times.
1.4. Protocol Overview 1.4. Protocol Overview
OLSR is a proactive routing protocol for mobile ad hoc networks. The OLSR is a proactive routing protocol for mobile ad hoc networks. The
protocol inherits the stability of a link state algorithm and has the protocol inherits the stability of a link state algorithm and has the
advantage of having routes immediately available when needed due to advantage of having routes immediately available when needed due to
its proactive nature. OLSR is an optimization over the classical link its proactive nature. OLSR is an optimization over the classical
state protocol, tailored for mobile ad hoc networks. link state protocol, tailored for mobile ad hoc networks.
OLSR minimizes the overhead from flooding of control traffic by using OLSR minimizes the overhead from flooding of control traffic by using
only selected nodes, called MPRs, to retransmit control messages. only selected nodes, called MPRs, to retransmit control messages.
This technique significantly reduces the number of retransmissions This technique significantly reduces the number of retransmissions
required to flood a message to all nodes in the network. Secondly, required to flood a message to all nodes in the network. Secondly,
OLSR requires only partial link state to be flooded in order to pro- OLSR requires only partial link state to be flooded in order to pro-
vide optimal routes. The minimal set of link state information vide shortest path routes. The minimal set of link state information
required is, that all nodes, selected as MPRs, MUST declare the links required is, that all nodes, selected as MPRs, MUST declare the links
to their MPR selectors. Additional topological information, if to their MPR selectors. Additional topological information, if pre-
present, MAY be utilized e.g. for redundancy purposes. sent, MAY be utilized e.g. for redundancy purposes.
OLSR MAY optimize the reactivity to topological changes by reducing OLSR MAY optimize the reactivity to topological changes by reducing
the maximum time interval for periodic control message transmission. the maximum time interval for periodic control message transmission.
Furthermore, as OLSR continuously maintains routes to all destina- Furthermore, as OLSR continuously maintains routes to all destina-
tions in the network, the protocol is beneficial for traffic patterns tions in the network, the protocol is beneficial for traffic patterns
where a large subset of nodes are communicating with another large where a large subset of nodes are communicating with another large
subset of nodes, and where the [source, destination] pairs are chang- subset of nodes, and where the [source, destination] pairs are chang-
ing over time. The protocol is particularly suited for large and ing over time. The protocol is particularly suited for large and
dense networks, as the optimization done using MPRs works well in dense networks, as the optimization done using MPRs works well in
this context. The larger and more dense a network, the more optimiza- this context. The larger and more dense a network, the more opti-
tion can be achieved as compared to the classic link state algorithm. mization can be achieved as compared to the classic link state algo-
rithm.
OLSR is designed to work in a completely distributed manner and does OLSR is designed to work in a completely distributed manner and does
thus not depend on any central entity. The protocol does NOT REQUIRE not depend on any central entity. The protocol does NOT REQUIRE
reliable transmission of control messages: each node sends control reliable transmission of control messages: each node sends control
messages periodically, and can therefore sustain an occasional loss messages periodically, and can therefore sustain a reasonable loss of
of some such messages. Such losses occur frequently in radio networks some such messages. Such losses occur frequently in radio networks
due to collisions or other transmission problems. due to collisions or other transmission problems.
Also, OLSR does not require sequenced delivery of messages. Each con- Also, OLSR does not require sequenced delivery of messages. Each
trol message contains a sequence number which is incremented for each control message contains a sequence number which is incremented for
message. Thus the recipient of a control message can, if required, each message. Thus the recipient of a control message can, if
easily identify which information is newer - even if messages have required, easily identify which information is more recent - even if
been re-ordered while in transmission. messages have been re-ordered while in transmission.
Furthermore, OLSR provides support for protocol extensions such as Furthermore, OLSR provides support for protocol extensions such as
sleep mode operation, multicast-routing etc. Such extensions may be sleep mode operation, multicast-routing etc. Such extensions may be
introduced as additions to the protocol without breaking backwards introduced as additions to the protocol without breaking backwards
compatibility with earlier versions. compatibility with earlier versions.
OLSR does not require any changes to the format of IP packets. Thus OLSR does not require any changes to the format of IP packets. Thus
any existing IP stack can be used as is: the protocol only interacts any existing IP stack can be used as is: the protocol only interacts
with routing table management. with routing table management.
1.5. Multipoint Relays 1.5. Multipoint Relays
The idea of multipoint relays is to minimize the overhead of flooding The idea of multipoint relays is to minimize the overhead of flooding
messages in the network by reducing duplicate retransmissions in the messages in the network by reducing redundant retransmissions in the
same region. Each node in the network selects a set of nodes in its same region. Each node in the network selects a set of nodes in its
symmetric neighborhood which may retransmit its messages. This set of symmetric 1-hop neighborhood which may retransmit its messages. This
selected neighbor nodes is called the "Multipoint Relay" (MPR) set of set of selected neighbor nodes is called the "Multipoint Relay" (MPR)
that node. The neighbors of node N which are *NOT* in its MPR set, set of that node. The neighbors of node N which are *NOT* in its MPR
receive and process broadcast messages but do not retransmit broad- set, receive and process broadcast messages but do not retransmit
cast messages received from node N. broadcast messages received from node N.
Each node selects its MPR set from among its one hop symmetric Each node selects its MPR set from among its one hop symmetric neigh-
neighbors. This set is selected such that it covers (in terms of bors. This set is selected such that it covers (in terms of radio
radio range) all nodes that are two hops away. The MPR set of N, range) all nodes that are two hops away. The MPR set of N, denoted
denoted as MPR(N), is then an arbitrary subset of the symmetric as MPR(N), is then an arbitrary subset of the symmetric 1-hop neigh-
neighborhood of N which satisfies the following condition: every node borhood of N which satisfies the following condition: every node in
in the symmetric strict 2-hop neighborhood of N must have a symmetric the symmetric strict 2-hop neighborhood of N must have a symmetric
link towards MPR(N). The smaller an MPR set, the less control traffic link towards MPR(N). The smaller a MPR set, the less control traffic
overhead results from the routing protocol. [2] gives an analysis and overhead results from the routing protocol. [2] gives an analysis
example of MPR selection algorithms. and example of MPR selection algorithms.
Each node maintains information about the set of neighbors that have Each node maintains information about the set of neighbors that have
selected it as MPR. This set is called the "Multipoint Relay Selector selected it as MPR. This set is called the "Multipoint Relay Selec-
set" (MPR selector set) of a node. A node obtains this information tor set" (MPR selector set) of a node. A node obtains this informa-
from periodic HELLO messages received from the neighbors. tion from periodic HELLO messages received from the neighbors.
A broadcast message, intended to be diffused in the whole network, A broadcast message, intended to be diffused in the whole network,
coming from any of the MPR selectors of node N is assumed to be coming from any of the MPR selectors of node N is assumed to be
retransmitted by node N. This set can change over time (i.e. when a retransmitted by node N, if N has not received it yet. This set can
node selects another MPR-set) and is indicated by the selector nodes change over time (i.e. when a node selects another MPR-set) and is
in their HELLO messages. indicated by the selector nodes in their HELLO messages.
2. Protocol Functioning 2. Protocol Functioning
This section outlines the overall the protocol functioning. This section outlines the overall protocol functioning.
OLSR is modularized into a "core" of functionality, which is always OLSR is modularized into a "core" of functionality, which is always
required for the protocol to operate, and a set of auxiliary func- required for the protocol to operate, and a set of auxiliary func-
tions. tions.
The core specifies, in its own right, a protocol able to provide The core specifies, in its own right, a protocol able to provide
routing in a stand-alone MANET. routing in a stand-alone MANET.
Each auxiliary function provides additional functionality, which may Each auxiliary function provides additional functionality, which may
be applicable in specific scenarios. E.g. in case a node is providing be applicable in specific scenarios. E.g. in case a node is provid-
connectivity between the MANET and another routing domain. ing connectivity between the MANET and another routing domain.
All auxiliary functions are compatible, to the extend where any All auxiliary functions are compatible, to the extend where any
(sub)set of auxiliary functions may be implemented with the core. (sub)set of auxiliary functions may be implemented with the core.
Furthermore, the protocol allows heterogeneous nodes, i.e. nodes Furthermore, the protocol allows heterogeneous nodes, i.e. nodes
which implement different subsets of the auxiliary functions, to which implement different subsets of the auxiliary functions, to
coexist in the network. coexist in the network.
The purpose of dividing the functioning of OLSR into a core function- The purpose of dividing the functioning of OLSR into a core function-
ality and a set of auxiliary functions is to provide a simple and ality and a set of auxiliary functions is to provide a simple and
easy-to-comprehend protocol, and to provide a way of only adding com- easy-to-comprehend protocol, and to provide a way of only adding com-
plexity where specific additional functionality is required. plexity where specific additional functionality is required.
2.1. Core Functioning 2.1. Core Functioning
The core functionality of OLSR specifies the behavior of a node, The core functionality of OLSR specifies the behavior of a node,
equipped with OLSR interfaces participating in the MANET and running equipped with OLSR interfaces participating in the MANET and running
OLSR as routing protocol. This includes an universal specification of OLSR as routing protocol. This includes a universal specification of
OLSR protocol messages and their transmission through the network, as OLSR protocol messages and their transmission through the network, as
well as link sensing, topology diffusion and route calculation. well as link sensing, topology diffusion and route calculation.
The "Link Sensing and Neighbor Detection" mechanism provides nodes Specifically, the core is made up from the following components:
with information about their neighbors and offers an optimized mecha-
nism for flooding messages through the concept of MPRs. It completely
relies on the exchange of HELLO messages.
The "Topology Discovery" mechanism relies on the "Packet Forwarding" Packet Format and Forwarding
and "Link Sensing and Neighbor Discovery" mechanisms. A node uses
neighbor and MPR information from the "Link Sensing" mechanism in An universal specification of the packet format and an opti-
diffusing local topology information to the larger network. Topology mized flooding mechanism serves as the transport mechanism for
information is diffused through the "Packet Forwarding" mechanism, all OLSR control traffic.
and relies on TC messages. Resulting from the "Topology Discovery"
mechanism is information which allows routing table calculation. Link Sensing
Link Sensing is accomplished through periodic emission of
HELLO messages over the interfaces through which connectivity
is checked. A separate HELLO message is generated for each
interface and emitted in correspondence with the provisions in
section 7.
Resulting from Link Sensing is a local link set, describing
links between "local interfaces" and "remote interfaces" -
i.e. interfaces on neighbor nodes.
If sufficient information is provided by the link-layer, this
may be utilized to populate the local link set instead of
HELLO message exchange.
Neighbor detection
Given a network with only single interface nodes, a node may
deduct the neighbor set directly from the information
exchanged as part of link sensing: the "main address" of a
single interface node is, by definition, the address of the
only interface on that node.
In a network with multiple interface nodes, additional infor-
mation is required in order to map interface addresses to main
addresses (and, thereby, to nodes). This additional informa-
tion is acquired through multiple interface declaration (MID)
messages, described in section 5.
MPR Selection and MPR Signaling
The objective of MPR selection is for a node to select a sub-
set of its neighbors such that a broadcast message, retrans-
mitted by these selected neighbors, will be received by all
nodes 2 hops away. A node will thus compute its MPR set such
that it, for each interface, satisfies this condition. The
information required to perform this calculation is acquired
throuth the periodic exchange of HELLO messages, as described
in section 6. MPR selection procedures are
detailed in section 8.3.
MPR signaling is provided in correspondence with the provi-
sions in the section 6.
Topology Control Message Diffusion
Topology Control messages are diffused with the purpose of
providing each node in the network with sufficient link-state
information to allow route calculation. Topology Control mes-
sages are diffused in correspondence with the provisions in
section 9.
Route Calculation
Given the link state information acquired through periodic
message exchange, as well as the interface configuration of
the nodes, the routing table for each node can be computed.
This is detailed in section 10
The key notion for these mechanisms is the MPR relationship. The key notion for these mechanisms is the MPR relationship.
The following table specifies the component of the core functionality The following table specifies the component of the core functionality
of OLSR, as well as their relations to this document. of OLSR, as well as their relations to this document.
Feature | Section Feature | Section
------------------------------+-------------- ------------------------------+--------------
Packet format and forwarding | 3 Packet format and forwarding | 3
Link sensing | 4 Information repositories | 4
Topology discovery | 5 Main addr and multiple if. | 5
Node configuration | 6 Hello messages | 6
Multiple OLSR interfaces | 7 Link sensing | 7
Neighbor detection | 8
Multiple interface compliance is needed when: Topology discovery | 9
Routing table computation | 10
- a node has multiple interfaces which participate in the OLSR Node configuration | 11
domain,
- a node exists in a domain where other nodes with multiple OLSR
interfaces are present.
2.2. Auxiliary Functioning 2.2. Auxiliary Functioning
In addition to the core functioning of OLSR, there are situations In addition to the core functioning of OLSR, there are situations
where additional functionality is needed. This includes situations where additional functionality is needed. This includes situations
where a node has multiple interfaces, some of which participate in where a node has multiple interfaces, some of which participate in
another routing domain, where the programming interface to the net- another routing domain, where the programming interface to the net-
working hardware provides additional information in form of link- working hardware provides additional information in form of link-
layer notifications and where it is desired to provide redundant layer notifications and where it is desired to provide redundant
topological information to the network on expense of protocol over- topological information to the network on expense of protocol over-
head. head.
The following table specifies auxiliary functions and their relation The following table specifies auxiliary functions and their relation
to this document. to this document.
Feature | Section Feature | Section
------------------------------+-------------- ------------------------------+--------------
Non-OLSR interfaces | 8 Non-OLSR interfaces | 12
Link-layer notifications | 9 Link-layer notifications | 13
Advanced link sensing | 10 Advanced link sensing | 14
Redundant topology | 11 Redundant topology | 15
Redundant MPR flooding | 12 Redundant MPR flooding | 16
The interpretation of the above table is as follows: if the feature
listed is required, it SHOULD be provided as specified in the corre-
sponding section.
3. Packet Format and Forwarding 3. Packet Format and Forwarding
OLSR communicates using a unified packet format for all data related OLSR communicates using an unified packet format for all data related
to the protocol. The purpose of this is to facilitate extensibility to the protocol. The purpose of this is to facilitate extensibility
of the protocol without breaking backwards compatibility. Also, this of the protocol without breaking backwards compatibility. Also, this
provides an easy way of piggybacking different "types" of information provides an easy way of piggybacking different "types" of information
into a single transmission, and thus for a given implementation to into a single transmission, and thus for a given implementation to
optimize towards utilizing the maximal frame-size, provided by the optimize towards utilizing the maximal frame-size, provided by the
network. These packets are embedded in UDP datagrams for transmission network. These packets are embedded in UDP datagrams for transmis-
over the network. The present draft is presented with IPv4 addresses. sion over the network. The present draft is presented with IPv4
Considerations regarding IPv6 are given in section 13. addresses. Considerations regarding IPv6 are given in section
17.
Each packet encapsulates one or more messages. The messages share a Each packet encapsulates one or more messages. The messages share a
common header format, which enables nodes to correctly accept and (if common header format, which enables nodes to correctly accept and (if
applicable) retransmit messages of an unknown type. applicable) retransmit messages of an unknown type.
Messages can be flooded onto the entire network, or flooding can be Messages can be flooded onto the entire network, or flooding can be
limited to nodes within a diameter (in terms of number of hops) from limited to nodes within a diameter (in terms of number of hops) from
the originator of the message. Thus transmitting a message to the the originator of the message. Thus transmitting a message to the
neighborhood of a node is just a special case of flooding. When neighborhood of a node is just a special case of flooding. When
flooding any control message, duplicate retransmissions will be elim- flooding any control message, duplicate retransmissions will be elim-
inated locally (i.e. each node maintains a duplicate table to prevent inated locally (i.e. each node maintains a duplicate set to prevent
transmitting the same message twice) and minimized in the entire net- transmitting the same OLSR control message twice) and minimized in
work through the usage of MPRs as described in later sections. the entire network through the usage of MPRs as described in later
sections.
Furthermore, a node can examine the header of a message to obtain Furthermore, a node can examine the header of a message to obtain
information on the distance (in terms of number of hops) to the orig- information on the distance (in terms of number of hops) to the orig-
inator of the message. This feature may be useful in situations inator of the message. This feature may be useful in situations
where, e.g., the time information from a received control messages where, e.g., the time information from a received control messages
stored in a node depends on the distance to the originator. stored in a node depends on the distance to the originator.
3.1. Protocol and Port Number 3.1. Protocol and Port Number
Packets in OLSR are communicated using UDP. Port 698 has been Packets in OLSR are communicated using UDP. Port 698 has been
skipping to change at page 15, line 15 skipping to change at page 17, line 15
3.3.1. Packet Header 3.3.1. Packet Header
Packet Length Packet Length
The length (in bytes) of the packet The length (in bytes) of the packet
Packet Sequence Number Packet Sequence Number
The Packet Sequence Number (PSN) MUST be incremented by one The Packet Sequence Number (PSN) MUST be incremented by one
each time a new OLSR packet is transmitted. "Wrap-around" is each time a new OLSR packet is transmitted. "Wrap-around" is
handled as described in section 16. handled as described in section 19. A separate Packet
Sequence Number is maintained for each interface such that
packets transmitted over an interface are sequentially enumer-
ated.
The sender information for a packet is obtainable from the IP header. The IP address of the interface over which a packet was transmitted
Any received packet whose "Packet Length" is less or equal to 12 is obtainable from the IP header of the packet.
(i.e. the packet contains no messages), MUST be silently dropped.
If the packet contains no messages (i.e. the Packet Length is less
than or equal to the size of the packet header), the packet MUST
silently be discarded.
For IPv4 addresses, this implies that packets, where the Packet
Length < 16 MUST silently be discarded.
3.3.2. Message Header 3.3.2. Message Header
Message Type Message Type
This field indicates which type of message is to be found in This field indicates which type of message is to be found in
the "MESSAGE" part. Message types in the range of 0-127 are the "MESSAGE" part. Message types in the range of 0-127 are
reserved for messages in this document and in possible exten- reserved for messages in this document and in possible exten-
sions. sions.
Vtime Vtime
This field indicates for how long time after reception a node This field indicates for how long time after reception a node
must consider the information contained in the message for MUST consider the information contained in the message as
valid. The validity time is represented by its mantissa (four valid, unless a more recent update to the information is
highest bits of Vtime field) and by its exponent (four lowest received. The validity time is represented by its mantissa
bits of Vtime field). In other words: (four highest bits of Vtime field) and by its exponent (four
lowest bits of Vtime field). In other words:
validity time = C*(1+a/16)* 2^b validity time = C*(1+a/16)* 2^b [in seconds]
where a is the integer represented by the four highest bits of where a is the integer represented by the four highest bits of
Vtime field and b the integer represented by the four lowest Vtime field and b the integer represented by the four lowest
bits of Vtime field. The proposed value of the scaling factor bits of Vtime field. The proposed value of the scaling factor
C is specified in section 15. C is specified in section 18.
Message Size Message Size
This field gives the size of this message, counted in bytes This field gives the size of this message, counted in bytes
and measured from the beginning of the "Message Type" field and measured from the beginning of the "Message Type" field
and until the beginning of the next "Message Type" field (or - and until the beginning of the next "Message Type" field (or -
if there are no following messages - until the end of the if there are no following messages - until the end of the
packet). packet).
Originator Address Originator Address
skipping to change at page 16, line 25 skipping to change at page 18, line 41
This field contains the main address of the node, which has This field contains the main address of the node, which has
originally generated this message. This field SHOULD NOT be originally generated this message. This field SHOULD NOT be
confused with the source address from the IP header, which is confused with the source address from the IP header, which is
changed each time to the address of the intermediate interface changed each time to the address of the intermediate interface
which is re-transmitting this message. The Originator Address which is re-transmitting this message. The Originator Address
field MUST *NEVER* be changed in retransmissions. field MUST *NEVER* be changed in retransmissions.
Time To Live Time To Live
This field contains the maximum number of hops a message will This field contains the maximum number of hops a message will
be transmitted. Before a message is retransmitted, the Time To be transmitted. Before a message is retransmitted, the Time
Live MUST be decremented by 1. When a node receives a message To Live MUST be decremented by 1. When a node receives a mes-
with a Time To Live equal to 0 or 1, the message MUST NOT be sage with a Time To Live equal to 0 or 1, the message MUST NOT
retransmitted under any circumstances. Normally, a node would be retransmitted under any circumstances. Normally, a node
not receive a message with a TTL of zero. would not receive a message with a TTL of zero.
Thus, by setting this field, the originator of a message can Thus, by setting this field, the originator of a message can
limit the flooding radius. limit the flooding radius.
Hop Count Hop Count
This field contains the number of hops a message has attained. This field contains the number of hops a message has attained.
Before a message is retransmitted, the Hop Count MUST be Before a message is retransmitted, the Hop Count MUST be
incremented by 1. incremented by 1.
Initially, this is set to '0' by the originator of the mes- Initially, this is set to '0' by the originator of the mes-
sage. sage.
Message Sequence Number Message Sequence Number
While generating a message, the "originator" node will assign While generating a message, the "originator" node will assign
a unique identification number to each message. This number is a unique identification number to each message. This number
inserted into the Sequence Number field of the message. The is inserted into the Sequence Number field of the message.
sequence number is increased by 1 (one) for each message orig- The sequence number is increased by 1 (one) for each message
inating from the node. "Wrap-around" is handled as described originating from the node. "Wrap-around" is handled as
in section 16. Message sequence numbers are used to described in section 19. Message sequence numbers are
ensure that a given message is not retransmitted more than used to ensure that a given message is not retransmitted more
once by any node. than once by any node.
3.4. Packet Processing and Message Flooding 3.4. Packet Processing and Message Flooding
Upon receiving a basic packet, a node examines each of the "message Upon receiving a basic packet, a node examines each of the "message
headers". Based on the value of the "Message Type" field, the node headers". Based on the value of the "Message Type" field, the node
can determine the fate of the message. A node may receive the same can determine the fate of the message. A node may receive the same
message several times. Thus, to avoid re-processing of some messages message several times. Thus, to avoid re-processing of some messages
which were already received and processed, each node maintains a which were already received and processed, each node maintains a
Duplicate Table. In this table, the node records information about Duplicate Set. In this set, the node records information about the
the most recently received messages where duplicate processing of a most recently received messages where duplicate processing of a mes-
message is to be avoided. For such a message, a node records a sage is to be avoided. For such a message, a node records a "Dupli-
"Duplicate Tuple" (D_addr, D_seq_num, D_time), where D_addr is the cate Tuple" (D_addr, D_seq_num, D_retransmitted, D_iface_list,
originator address of the message, D_seq_num is the message sequence D_time), where D_addr is the originator address of the message,
number of the message and D_time specifies the time at which a tuple D_seq_num is the message sequence number of the message, D_retrans-
expires and *MUST* be removed. mitted is a boolean indicating whether the message has been already
retransmitted, D_iface_list is a list of the addresses of the inter-
faces on which the message has been received and D_time specifies the
time at which a tuple expires and *MUST* be removed.
In a node, the set of Duplicate Tuples are denoted the "Duplicate In a node, the set of Duplicate Tuples are denoted the "Duplicate
set". set".
In this section, the term "Originator Address" will be used for the In this section, the term "Originator Address" will be used for the
main address of the node which sent the message. The term "Sender main address of the node which sent the message. The term "Sender
Interface Address" will be used for the sender address (given in the Interface Address" will be used for the sender address (given in the
IP header of the packet containing the message) of the interface IP header of the packet containing the message) of the interface
which sent the message. which sent the message. The term "Receiving Interface Address" will
be used for the address of the interface of the node which received
the message.
Thus, upon receiving a basic packet, a node MUST perform the follow- Thus, upon receiving a basic packet, a node MUST perform the follow-
ing tasks for each encapsulated message: ing tasks for each encapsulated message:
1 If the time to live of the message is less than or equal to 1 If the packet contains no messages (i.e. the Packet Length is
'0' (zero), the message MUST silently be dropped.
2 If the packet contains no messages (i.e. the Packet Length is
less than or equal to the size of the packet header), the less than or equal to the size of the packet header), the
packet MUST silently be discarded. packet MUST silently be discarded.
For IPv4 addresses, this implies that packets, where the For IPv4 addresses, this implies that packets, where the
Packet Length < 16 MUST silently be discarded. Packet Length < 16 MUST silently be discarded.
2 If the time to live of the message is less than or equal to
'0' (zero), or if the message was sent by the receiving node
(i.e. the Originator Address of the message is the main
address of the receiving node): the message MUST silently be
dropped.
3 Processing condition: 3 Processing condition:
3.1 if there exists a tuple in the duplicate set, where: 3.1 if there exists a tuple in the duplicate set, where:
D_addr == Originator Address, AND D_addr == Originator Address, AND
D_seq_num == Message Sequence Number D_seq_num == Message Sequence Number
then the message has already been completely processed then the message has already been completely processed
and MUST not be processed again. and MUST not be processed again.
skipping to change at page 18, line 26 skipping to change at page 20, line 43
3.2 Otherwise, if the node implements the Message Type of the 3.2 Otherwise, if the node implements the Message Type of the
message, the message MUST be processed according to the message, the message MUST be processed according to the
specifications for the message type. specifications for the message type.
4 Forwarding condition: 4 Forwarding condition:
4.1 if there exists a tuple in the duplicate set, where: 4.1 if there exists a tuple in the duplicate set, where:
D_addr == Originator Address, AND D_addr == Originator Address, AND
D_seq_num == Message Sequence Number D_seq_num == Message Sequence Number,
AND
the receiving interface (address) is
in D_iface_list
then the message has already been considered for forward- then the message has already been considered for forward-
ing and SHOULD NOT be retransmitted again. ing and SHOULD NOT be retransmitted again.
4.2 Otherwise: 4.2 Otherwise:
4.2.1 4.2.1
If the node implements the Message Type of the mes- If the node implements the Message Type of the
sage, the message MUST be considered for forwarding message, the message MUST be considered for
according to the specifications for the message forwarding according to the specifications for
type. the message type.
4.2.2 4.2.2
Otherwise, if the node does not implement the Mes- Otherwise, if the node does not implement the
sage Type of the message, the message SHOULD be pro- Message Type of the message, the message SHOULD
cessed according to the default forwarding algorithm be processed according to the default forward-
described below. ing algorithm described below.
3.4.1. Default Forwarding Algorithm 3.4.1. Default Forwarding Algorithm
The default forwarding algorithm is the following: The default forwarding algorithm is the following:
1 If the sender interface address of the message is not detected 1 If the sender interface address of the message is not detected
to be in the symmetric neighborhood of the node, the message to be in the symmetric 1-hop neighborhood of the node, the
MUST silently be dropped. forwarding algorithm MUST silently stop here (and the message
MUST NOT be forwarded).
2 If the sender interface address of the message is detected to 2 If there exists a tuple in the duplicate set where:
be in the symmetric neighborhood of the node, an entry in the
duplicate set is recorded with:
D_addr = originator address D_addr == Originator Address
D_seq_num = Message Sequence Number D_seq_num == Message Sequence Number
D_time = current time + D_HOLD_TIME. Then the message will be further considered for forwarding if
and only if:
3 If the sender interface address is an interface address of a D_retransmitted is false, AND
the (address of the) interface which received the message
is not included among the addresses in D_iface_list
3 Otherwise, if such an entry doesn't exist, the message is fur-
ther considered for forwarding.
If after those steps, the message is not considered for forwarding,
then the processing of this section stops (i.e. steps 4 to 8 are
ignored), otherwise, if it is still considered for forwarding then
the following algorithm is used:
4 If the sender interface address is an interface address of a
MPR selector of this node and if the time to live of the mes- MPR selector of this node and if the time to live of the mes-
sage is greater than '1', the message MUST be forwarded sage is greater than '1', the message MUST be retransmitted
according to the following: (as described later in steps 6 to 8).
3.1 The TTL of the message is reduced by one. 5 If an entry in the duplicate set exists, with same Originator
Address, and same Message Sequence Number, the entry is
updated as follows:
3.2 The hop-count of the message is increased by one D_time = current time + DUP_HOLD_TIME.
3.3 The message is broadcasted on all interfaces running The receiving interface (address) is added to
OLSR. Notice: The remaining fields of the message header D_iface_list.
SHOULD be left unmodified.
D_retransmitted is set to true if and only if the message
will be retransmitted according to step 4.
Otherwise an entry in the duplicate set is recorded with:
D_addr = Originator Address
D_seq_num = Message Sequence Number
D_time = current time + DUP_HOLD_TIME.
D_iface_list contains the receiving interface address.
D_retransmitted is set to true if and only if the message
will be retransmitted according to step 4.
If, and only if, according to step 4, the message must be retransmit-
ted then:
6 The TTL of the message is reduced by one.
7 The hop-count of the message is increased by one
8 The message is broadcast on all interfaces (Notice: The
remaining fields of the message header SHOULD be left unmodi-
fied.)
3.4.2. Considerations on Processing and Forwarding 3.4.2. Considerations on Processing and Forwarding
It should be noted that processing and forwarding messages are two It should be noted that processing and forwarding messages are two
different actions, conditioned by different rules. Processing relates different actions, conditioned by different rules. Processing
to using the content of the messages, while forwarding is related to relates to using the content of the messages, while forwarding is
retransmitting the same message for other nodes of the network. related to retransmitting the same message for other nodes of the
network.
Notice that this specification includes a description for both the Notice that this specification includes a description for both the
forwarding and the processing of each known message type. Messages forwarding and the processing of each known message type. Messages
with known message types MUST *NOT* be forwarded "blindly" by this with known message types MUST *NOT* be forwarded "blindly" by this
algorithm. Forwarding (and setting the correct message header in the algorithm. Forwarding (and setting the correct message header in the
forwarded, known, message) is the responsibility of the algorithm forwarded, known, message) is the responsibility of the algorithm
specifying how the message is to be handled and, if necessary, specifying how the message is to be handled and, if necessary,
retransmitted. This enables, e.g., a message type to be specified retransmitted. This enables, e.g., a message type to be specified
such that the message can be modified while in transit (e.g. to such that the message can be modified while in transit (e.g. to
reflect the route the message has taken). Further, it enables that reflect the route the message has taken). Further, it enables that
the optimization through the MPRs can be bypassed: if for some reason the optimization through the MPRs can be bypassed: if for some reason
classical flooding of a message type is required, the algorithm which classical flooding of a message type is required, the algorithm which
specifies how such messages should be handled will simply rebroadcast specifies how such messages should be handled will simply rebroadcast
the message, regardless of MPRs. the message, regardless of MPRs.
By defining a set of message types, which MUST be recognized by all By defining a set of message types, which MUST be recognized by all
implementations of OLSR, it will be possible to extend the protocol implementations of OLSR, it will be possible to extend the protocol
through introduction of additional message types, while still be able through introduction of additional message types, while still being
to maintain compatibility with older implementations. The REQUIRED able to maintain compatibility with older implementations. The
message types for the core functionality of OLSR are: REQUIRED message types for the core functionality of OLSR are:
- HELLO-messages, performing the task of link sensing, neighbor - HELLO-messages, performing the task of link sensing, neighbor
detection and MPR signaling, detection and MPR signaling,
- TC-messages, performing the task of topology declaration - TC-messages, performing the task of topology declaration
(advertisement of link states). (advertisement of link states).
- MID-messages, performing the task of declaring the presence of - MID-messages, performing the task of declaring the presence of
multiple interfaces on a node. multiple interfaces on a node.
Other message types include those specified in later sections, as Other message types include those specified in later sections, as
well as possible future extensions such as for example messages well as possible future extensions such as for example messages
enabling power conservation / sleep mode, multicast routing, support enabling power conservation / sleep mode, multicast routing, support
for unidirectional links, auto-configuration/address assignment etc. for unidirectional links, auto-configuration/address assignment etc.
3.5. Message Emission and Jitter 3.5. Message Emission and Jitter
As a basic implementation requirement, synchronization of control As a basic implementation requirement, synchronization of control
messages SHOULD be avoided. As a consequence, periodic OLSR messages messages SHOULD be avoided. As a consequence, OLSR control messages
SHOULD be emitted such that they avoid synchronization. SHOULD be emitted such that they avoid synchronization.
Emission of control traffic from neighboring nodes may, for various Emission of control traffic from neighboring nodes may, for various
reasons (mainly timer interactions with packet processing), become reasons (mainly timer interactions with packet processing), become
synchronized such that several neighbor nodes attempt to transmit synchronized such that several neighbor nodes attempt to transmit
control traffic simultaneously. Depending on the nature of the under- control traffic simultaneously. Depending on the nature of the
lying link-layer, this may or may not lead to collisions and hence underlying link-layer, this may or may not lead to collisions and
message loss - possibly loss of several subsequent messages of the hence message loss - possibly loss of several subsequent messages of
same type. the same type.
To avoid such synchronizations, the following simple strategy for To avoid such synchronizations, the following simple strategy for
emitting control messages is proposed. A node MAY add an amount of emitting control messages is proposed. A node MAY add an amount of
jitter to the interval at which messages are generated. The jitter jitter to the interval at which messages are generated. The jitter
must be a random value for each message generated. Thus, for a node must be a random value for each message generated. Thus, for a node
utilizing jitter: utilizing jitter:
Actual message interval = MESSAGE_INTERVAL - jitter Actual message interval = MESSAGE_INTERVAL - jitter
Where jitter is a value, randomly selected from the interval Where jitter is a value, randomly selected from the interval
skipping to change at page 21, line 13 skipping to change at page 24, line 35
time : time :
Keep message period = jitter Keep message period = jitter
Where jitter is a random value in [0,MAXJITTER]. Where jitter is a random value in [0,MAXJITTER].
Notice that when the node sends a control message, the opportunity to Notice that when the node sends a control message, the opportunity to
piggyback other messages (before their keeping period is expired) may piggyback other messages (before their keeping period is expired) may
be taken to reduce the number of packet transmissions. be taken to reduce the number of packet transmissions.
It should be noticed that the present draft imposes a minimal rate of Notice, that a minimal rate of control messages is imposed. A node
control message emission. However a node MAY send control messages at MAY send control messages at a higher rate, if beneficial for a spe-
a higher rate (e.g. for better reacting to high mobility). Tuning the cific deployment.
rate of control traffic to the actual conditions under which the pro-
tocol is to operate is an implementation issue.
4. Link Sensing and Neighbor Detection 4. Information Repositories
This section describes how a node discovers its immediate topology, Through the exchange of OLSR control messages, each node accumulates
known as its "neighborhood". This implies detecting the quality of information about the network. This information is stored according
links to neighbor nodes, as well as discovering which nodes are in to the descriptions in this section.
the neighborhood and two-hop neighborhood.
Specifically, link sensing and neighbor detection populates the local 4.1. Multiple Interface Association Information Base
link information base.
4.1. Local Link Information Base For each destination in the network, "Interface Association Tuples"
(I_iface_addr, I_main_addr, I_time) are recorded. I_iface_addr is an
interface address of a node, I_main_addr is the main address of this
node. I_time specifies the time at which this tuple expires and
*MUST* be removed.
The local link information base stores information about neighbors, In a node, the set of Interface Association Tuples is denoted the
links to neighbors, links to 2-hop neighbors, MPRs and MPR selectors. "Interface Association Set".
4.1.1. Link Set 4.2. Link Sensing: Local Link Information Base
A node records a "Link Tuple" (L_local_iface_addr, L_neigh- The local link information base stores information about links to
neighbors.
4.2.1. Link Set
A node records a set of "Link Tuples" (L_local_iface_addr, L_neigh-
bor_iface_addr, L_SYM_time, L_ASYM_time, L_time). L_local_iface_addr bor_iface_addr, L_SYM_time, L_ASYM_time, L_time). L_local_iface_addr
is the (interface) address of the local node (i.e. one endpoint of is the interface address of the local node (i.e. one endpoint of the
the link), L_neighbor_iface_addr is the (interface) address of the link), L_neighbor_iface_addr is the interface address of the neighbor
neighbor node (i.e. the other endpoint of the link), L_SYM_time is node (i.e. the other endpoint of the link), L_SYM_time is the time
the time until which the link is considered symmetric, L_ASYM_time is until which the link is considered symmetric, L_ASYM_time is the time
the time until which the neighbor interface is considered heard, and until which the neighbor interface is considered heard, and L_time
L_time specifies the time at which this record expires and *MUST* be specifies the time at which this record expires and *MUST* be
removed. When L_SYM_time and L_ASYM_time are expired, the link is removed. When L_SYM_time and L_ASYM_time are expired, the link is
considered lost. considered lost.
This information is used when declaring the neighbor interfaces in This information is used when declaring the neighbor interfaces in
the HELLO messages. the HELLO messages.
L_SYM_time is used to decide the Link Type declared for the neighbor L_SYM_time is used to decide the Link Type declared for the neighbor
interface. If L_SYM_time is not expired, the link MUST be declared interface. If L_SYM_time is not expired, the link MUST be declared
symmetric. If L_SYM_time is expired, the link MUST be declared asym- symmetric. If L_SYM_time is expired, the link MUST be declared asym-
metric. If both L_SYM_time and L_ASYM_time are expired, the link MUST metric. If both L_SYM_time and L_ASYM_time are expired, the link
be declared lost. MUST be declared lost.
In a node, the set of Link Tuples are denoted the "Link Set". In a node, the set of Link Tuples are denoted the "Link Set".
4.1.2. Neighbor Set 4.3. Neighbor Detection: Neighborhood Information Base
The neighborhood information base stores information about neighbors,
2-hop neighbors, MPRs and MPR selectors.
4.3.1. Neighbor Set
A node records a set of "neighbor tuples" (N_neighbor_main_addr, A node records a set of "neighbor tuples" (N_neighbor_main_addr,
N_status, N_willingness), describing symmetric neighbors. N_neigh- N_status, N_willingness), describing symmetric neighbors. N_neigh-
bor_main_addr is the main address of a neighbor, N_status specifies bor_main_addr is the main address of a neighbor, N_status specifies
if the node is NOT_SYM or SYM. N_willingness in an integer between 0 if the node is NOT_SYM or SYM. N_willingness in an integer between 0
and 7, and specifies a nodes willingness to carry traffic on behalf and 7, and specifies a nodes willingness to carry traffic on behalf
of other nodes. of other nodes.
4.1.3. 2-hop Neighbor Set 4.3.2. 2-hop Neighbor Set
A node records a set of "2-hop tuples" (N_neighbor_main_addr, A node records a set of "2-hop tuples" (N_neighbor_main_addr,
N_2hop_addr, N_time), describing symmetric (and, since MPR links by N_2hop_addr, N_time), describing symmetric (and, since MPR links by
definition are also symmetric, thereby also MPR) links between its definition are also symmetric, thereby also MPR) links between its
neighbors and the symmetric 2-hop neighborhood. N_neighbor_main_addr neighbors and the symmetric 2-hop neighborhood. N_neighbor_main_addr
is the main address of a neighbor, N_2hop_addr is the main address of is the main address of a neighbor, N_2hop_addr is the main address of
a 2-hop neighbor with a symmetric link to N_neighbor_main_addr, and a 2-hop neighbor with a symmetric link to N_neighbor_main_addr, and
N_time specifies the time at which the tuple expires and *MUST* be N_time specifies the time at which the tuple expires and *MUST* be
removed. removed.
This information is gathered from the HELLO messages received by a
node from its neighbor nodes.
In a node, the set of 2-hop tuples are denoted the "2-hop Neighbor In a node, the set of 2-hop tuples are denoted the "2-hop Neighbor
Set". Set".
4.1.4. MPR Set 4.3.3. MPR Set
A node maintains a set of neighbors which are selected as MPR. Their A node maintains a set of neighbors which are selected as MPR. Their
main addresses are listed in the so-called MPR Set. main addresses are listed in the so-called MPR Set.
Section 4.6.2 describes how MPRs are selected. 4.3.4. MPR Selector Set
4.1.5. MPR Selector Set
A node maintains information (obtained from the HELLO messages) about
the neighbors which have selected this node as a MPR.
Thus, a node records an MPR-selector tuple (MS_main_addr, MS_time). A node records a set of MPR-selector tuples (MS_main_addr, MS_time),
describing the neighbors which have selected this node as a MPR.
MS_main_addr is the main address of a node, which has selected this MS_main_addr is the main address of a node, which has selected this
node as MPR. MS_time specifies the time at which a tuple expires and node as MPR. MS_time specifies the time at which a tuple expires and
*MUST* be removed. *MUST* be removed.
In a node, the set of MPR-selector tuples are denoted the "MPR Selec- In a node, the set of MPR-selector tuples are denoted the "MPR Selec-
tor Set". tor Set".
4.2. HELLO Message Format 4.4. Topology Information Base
Each node in the network maintains topological information about the
network. This information is acquired from TC-messages and is used
for routing table calculations.
Thus, for each destination in the network, a "Topology Tuple"
(T_dest_addr, T_last_addr, T_seq, T_time) is recorded. T_dest_addr
is the main address of a node, which may be reached in one hop from
the node with the main address T_last_addr. Typically, T_last_addr
is a MPR of T_dest_addr. T_seq is a sequence number, and T_time
specifies the time at which this tuple expires and *MUST* be removed.
In a node, the set of Topology Tuples are denoted the "Topology Set".
5. Main Addresses and Multiple Interfaces
For single OLSR interface nodes, the relationship between an OLSR
interface address and the corresponding main address is trivial: the
main address is the OLSR interface address. For multiple OLSR inter-
face nodes, the relationship between OLSR interface addresses and
main addresses is defined through the exchange of Multiple Interface
Declaration (MID) messages. This section describes how MID messages
are exchanged and processed.
Each node with multiple interfaces MUST announce, periodically,
information describing its interface configuration to other nodes in
the network. This is accomplished through flooding a Multiple Inter-
face Declaration message to all nodes in the network through the MPR
flooding mechanism.
Each node in the network maintains interface information about the
other nodes in the network. This information acquired from MID-mes-
sages, emitted by nodes with multiple interfaces participating in the
MANET, and is used for routing table calculations.
Specifically, multiple interface declaration associates multiple
interfaces to a node (and to a main address) through populating the
multiple interface association base in each node.
5.1. MID Message Format
The proposed format of a MID message is as follows:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| OLSR Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| OLSR Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This is sent as the data-portion of the general packet format
described in section 3.4, with the "Message Type" set to
MID_MESSAGE. The time to live SHOULD be set to 255 (maximum value)
to diffuse the message into the entire network and Vtime set
accordingly to the value of MID_HOLD_TIME, as specified in section
18.3.
OLSR Interface Address
This field contains the address of an OLSR interface of the
node, excluding the nodes main address (which already indi-
cated in the originator address).
All interface addresses other than the main address of the originator
node are put in the MID message. If the maximum allowed message size
(as imposed by the network) is reached while there are still inter-
face addresses which have not been inserted into the MID-message,
more MID messages are generated until the entire interface addresses
set has been sent.
5.2. MID Message Generation
A MID message is sent by a node in the network to declare its multi-
ple interfaces (if any). I.e., the MID message contains the list of
interface addresses which are associated to its main address. The
list of addresses can be partial in each MID message (e.g. due to
message size limitations, imposed by the network), but parsing of all
MID messages describing the interface set from a node MUST be com-
plete within a certain refreshing period (MID_INTERVAL). The infor-
mation diffused in the network by these MID messages will help each
node to calculate its routing table. A node which has only a single
interface address participating in the MANET (i.e. running OLSR),
MUST NOT generate any MID message.
A node with more interfaces, where only one is participating in the
MANET and running OLSR (e.g. a node is connected to a wired network
as well as to a MANET) MUST NOT generate any MID messages.
A node with more interfaces, where more than one is participating in
the MANET and running OLSR MUST generate MID messages as specified.
5.3. MID Message Forwarding
MID messages are broadcast and retransmitted by the MPRs in order to
diffuse the messages in the entire network. The "default forwarding
algorithm" (described in section 3.4) MUST be used for for-
warding of MID messages.
5.4. MID Message Processing
The tuples in the multiple interface association set are recorded
with the information that is exchanged through MID messages.
Upon receiving a MID message, the "validity time" MUST be computed
from the Vtime field of the message header (as described in section
3.3.2). The Multiple Interface Association Information Base
SHOULD then be updated as follows:
1 If the sender interface (NB: not originator) of this message
is not in the symmetric 1-hop neighborhood of this node, the
message MUST be discarded.
2 For each interface address listed in the MID message:
2.1 If there exist some tuple in the interface association
set where:
I_iface_addr == interface address, AND
I_main_addr == originator address,
then the holding time of that tuple is set to:
I_time = current time + validity time.
2.2 Otherwise, a new tuple is recorded in the interface asso-
ciation set where:
I_iface_addr = interface address,
I_main_addr = originator address,
I_time = current time + validity time.
5.5. Resolving a Main Address from an Interface Address
In general, the only part of OLSR requiring use of "interface
addresses" is link sensing. The remaining parts of OLSR operate on
nodes, uniquely identified by their "main addresses" (effectively,
the main address of a node is its "node id" - which for convenience
corresponds to the address of one of its interfaces). In a network
with only single interface nodes, the main address of a node will, by
definition, be equal to the interface address of the node. In net-
works with multiple interface nodes operating within a common OLSR
area, it is required to be able to map any interface address to the
corresponding main address.
The exchange of MID messages provides a way in which interface infor-
mation is acquired by nodes in the network. This permits identifica-
tion of a nodes "main address", given one of its interface addresses.
Given an interface address:
1 if there exists some tuple in the interface association set
where:
I_iface_addr == interface address
then the result of the main address search is the originator
address I_main_addr of the tuple.
2 Otherwise, the result of the main address search is the inter-
face address itself.
6. HELLO Message Format and Generation
A common mechanism is employed for populating the local link informa- A common mechanism is employed for populating the local link informa-
tion base, namely periodic exchange of HELLO messages. Thus this sec- tion base and the neighborhood information base, namely periodic
tion describes the general HELLO message mechanism, followed by a exchange of HELLO messages. Thus this section describes the general
description of link sensing and topology detection, respectively. HELLO message mechanism, followed by a description of link sensing
and topology detection, respectively.
To accommodate for link sensing and neighbor detection, as well as to 6.1. HELLO Message Format
accommodate for future extensions, an approach similar to the overall
packet format is taken. Thus the proposed format of a HELLO message To accommodate for link sensing, neighborhood detection and MPR
is: selection signalling, as well as to accommodate for future exten-
sions, an approach similar to the overall packet format is taken.
Thus the proposed format of a HELLO message is as follows:
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved | Htime | Willingness | | Reserved | Htime | Willingness |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Code | Reserved | Link Message Size | | Link Code | Reserved | Link Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address | | Neighbor Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address | | Neighbor Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: . . . : : . . .
:
: : : :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Code | Reserved | Link Message Size | | Link Code | Reserved | Link Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address | | Neighbor Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address | | Neighbor Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: : : :
: : : :
(etc) (etc)
This is sent as the data-portion of the general packet format This is sent as the data-portion of the general packet format
described in section 3.4, with the "Message Type" set to described in section 3.4, with the "Message Type" set to
HELLO_MESSAGE, the TTL field set to 1 (one) and Vtime set accordingly HELLO_MESSAGE, the TTL field set to 1 (one) and Vtime set accordingly
to the value of NEIGHB_HOLD_TIME, specified in section 15.3. to the value of NEIGHB_HOLD_TIME, specified in section 18.3.
Reserved Reserved
This field must be set to "0000000000000" to be in compliance This field must be set to "0000000000000" to be in compliance
with this specification. with this specification.
HTime HTime
This field specifies the HELLO emission interval used by the This field specifies the HELLO emission interval used by the
node on this particular interface, i.e. the time before the node on this particular interface, i.e. the time before the
transmission of the next HELLO (this information is used in transmission of the next HELLO (this information may be used
advanced link sensing). The HELLO emission interval is repre- in advanced link sensing, see section 14). The
sented by its mantissa (four highest bits of Htime field) and HELLO emission interval is represented by its mantissa (four
by its exponent (four lowest bits of Htime field). In other highest bits of Htime field) and by its exponent (four lowest
words: bits of Htime field). In other words:
HELLO emission interval=C*(1+a/16)*2^b HELLO emission interval=C*(1+a/16)*2^b [in seconds]
where a is the integer represented by the four highest bits of where a is the integer represented by the four highest bits of
Htime field and b the integer represented by the four lowest Htime field and b the integer represented by the four lowest
bits of Htime field. The proposed value of the scaling factor bits of Htime field. The proposed value of the scaling factor
C is specified in section 15. C is specified in section 18.
Willingness Willingness
This field specifies the willingness of a node to carry and This field specifies the willingness of a node to carry and
forward traffic for other nodes. forward traffic for other nodes.
A node with willingness WILL_NEVER (see section 15.8, for A node with willingness WILL_NEVER (see section 18.8, for
willingness constants) MUST never be selected as MPR by any willingness constants) MUST never be selected as MPR by any
node. A node with willingness WILL_ALWAYS MUST always be node. A node with willingness WILL_ALWAYS MUST always be
selected as MPR. By default, a node SHOULD advertise a will- selected as MPR. By default, a node SHOULD advertise a will-
ingness of WILL_DEFAULT. ingness of WILL_DEFAULT.
Link Code Link Code
This field specifies informations about the link between the This field specifies informations about the link between the
interface of the sender and the following list of neighbor interface of the sender and the following list of neighbor
interfaces. It also specifies informations about the status of interfaces. It also specifies informations about the status
the neighbor. of the neighbor.
Link codes, not known by a node, are silently discarded. Link codes, not known by a node, are silently discarded.
Link Message Size Link Message Size
The size of the link message, counted in bytes and measured The size of the link message, counted in bytes and measured
from the beginning of the "Link Code" field and until the next from the beginning of the "Link Code" field and until the next
"Link Code" field (or - if there are no more link types - the "Link Code" field (or - if there are no more link types - the
end of the message). end of the message).
Neighbor Address Neighbor Interface Address
An address of a neighbor node. An address of the interface of a neighbor node.
4.2.1. Link Code as Link Type and Neighbor Type 6.1.1. Link Code as Link Type and Neighbor Type
This document specifies processing only of Link Codes < 16. This document only specifies processing of Link Codes < 16.
If the Link Code value is less or equal to 15, then it MUST be inter- If the Link Code value is less or equal to 15, then it MUST be inter-
preted as holding two different fields, of two bits each: preted as holding two different fields, of two bits each:
7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+-------+-------+-------+-------+-------+-------+-------+-------+ +-------+-------+-------+-------+-------+-------+-------+-------+
| 0 | 0 | 0 | 0 | Neighbor Type | Link Type | | 0 | 0 | 0 | 0 | Neighbor Type | Link Type |
+-------+-------+-------+-------+-------+-------+-------+-------+ +-------+-------+-------+-------+-------+-------+-------+-------+
The following four "Link Types" are REQUIRED by OLSR: The following four "Link Types" are REQUIRED by OLSR:
- UNSPEC_LINK - indicating that no specific information about - UNSPEC_LINK - indicating that no specific information about
the links is given. the links is given.
- ASYM_LINK - indicating that the links are asymmetric (i.e. the - ASYM_LINK - indicating that the links are asymmetric (i.e.
neighbor interface is "heard"). the neighbor interface is "heard").
- SYM_LINK - indicating that the links are symmetric with the - SYM_LINK - indicating that the links are symmetric with the
interface. interface.
- LOST_LINK - indicating that the links have been lost. - LOST_LINK - indicating that the links have been lost.
The following three "Neighbor Types" are REQUIRED by OLSR: The following three "Neighbor Types" are REQUIRED by OLSR:
- SYM_NEIGH - indicating that the neighbors have at least one - SYM_NEIGH - indicating that the neighbors have at least one
symmetrical link with this node. symmetrical link with this node.
- MPR_NEIGH - indicating that the neighbors have at least one - MPR_NEIGH - indicating that the neighbors have at least one
symmetrical link AND have been been selected as MPR by the symmetrical link AND have been been selected as MPR by the
sender. sender.
- NOT_NEIGH - indicating that the nodes are either no longer or - NOT_NEIGH - indicating that the nodes are either no longer or
have not yet become symmetrical neighbors. have not yet become symmetrical neighbors.
Note that the implementation should be careful in not confusing Link Note that an implementation should be careful in not confusing Link
Type with Neighbor Type nor the constants (confusing SYM_NEIGH with Type with Neighbor Type nor the constants (confusing SYM_NEIGH with
SYM_LINK for instance). SYM_LINK for instance).
A link code advertising: A link code advertising:
Link Type == SYM_LINK AND Link Type == SYM_LINK AND
Neighbor type == NOT_NEIGH Neighbor Type == NOT_NEIGH
is invalid, and any links listed as such MUST be silently discarded is invalid, and any links adverticed as such MUST be silently dis-
without any processing. carded without any processing.
4.3. HELLO Message Generation Likewise a Neighbor Type field advertising a numerical value which is
not one of the constants SYM_NEIGH, MPR_NEIGH, NOT_NEIGH, is invalid,
and any links adverticed as such MUST be silently discarded without
any processing.
6.2. HELLO Message Generation
This involves transmitting the Link Set, the Neighbor Set and the MPR This involves transmitting the Link Set, the Neighbor Set and the MPR
Set. In principle, a HELLO message serves three independent tasks: Set. In principle, a HELLO message serves three independent tasks:
- link sensing - link sensing
- neighbor detection - neighbor detection
- MPR selection signaling - MPR selection signaling
Three tasks are all are based on periodic information exchange within Three tasks are all are based on periodic information exchange within
a nodes neighborhood, and serve the common purpose of "local topology a nodes neighborhood, and serve the common purpose of "local topology
discovery". A HELLO message is therefore generated based on the discovery". A HELLO message is therefore generated based on the
information stored in the Local Link Set, the Neighbor Set and the information stored in the Local Link Set, the Neighbor Set and the
MPR Set from the local link information base. MPR Set from the local link information base.
A node must perform link sensing on each interface, in order to A node must perform link sensing on each interface, in order to
detect links between the interface and neighbor interfaces. Further- detect links between the interface and neighbor interfaces. Further-
more, a node must advertise its entire symmetric neighborhood on each more, a node must advertise its entire symmetric 1-hop neighborhood
interface in order to perform neighbor detection. Hence, for a given on each interface in order to perform neighbor detection. Hence, for
interface, a HELLO message will contain a list of links on that a given interface, a HELLO message will contain a list of links on
interface (with associated link types), as well as a list of the that interface (with associated link types), as well as a list of the
entire neighborhood (with an associated neighbor types). entire neighborhood (with an associated neighbor types).
The Vtime field is set such that it corresponds to the value of the The Vtime field is set such that it corresponds to the value of the
node's NEIGHB_HOLD_TIME parameter. The Htime field is set such that node's NEIGHB_HOLD_TIME parameter. The Htime field is set such that
it corresponds to the value of the node's HELLO_INTERVAL parameter it corresponds to the value of the node's HELLO_INTERVAL parameter
(see section 15.3). (see section 18.3).
The Willingness field is set such that it corresponds to the nodes The Willingness field is set such that it corresponds to the node's
willingness to forward traffic on behalf of other nodes (see section willingness to forward traffic on behalf of other nodes (see section
15.8). A node MUST advertise the same willingness on all inter- 18.8). A node MUST advertise the same willingness on all
faces. interfaces.
The lists of addresses declared in a HELLO message are computed as The lists of addresses declared in a HELLO message is a list of
follows: neighbor interface addresses computed as follows:
For each tuple in the Link Set, where L_local_iface_addr is the For each tuple in the Link Set, where L_local_iface_addr is the
interface where the HELLO is to be transmitted, and where L_time >= interface where the HELLO is to be transmitted, and where L_time >=
current time (i.e. not expired), L_neighbor_iface_addr is advertised current time (i.e. not expired), L_neighbor_iface_addr is advertised
with: with:
1 The Link Type set according to the following: 1 The Link Type set according to the following:
if L_SYM_time >= current time (not expired) AND 1.1 if L_SYM_time >= current time (not expired)
L_time >= current time (not expired)
Link Type = SYM_LINK Link Type = SYM_LINK
Otherwise, if L_ASYM_time >= current time (not expired) 1.2 Otherwise, if L_ASYM_time >= current time (not expired)
AND AND
L_SYM_time < current time (expired) AND L_SYM_time < current time (expired)
L_time >= current time (not expired)
Link Type = ASYM_LINK Link Type = ASYM_LINK
Otherwise, if L_ASYM_time < current time (expired) AND 1.3 Otherwise, if L_ASYM_time < current time (expired) AND
L_SYM_time < current time (expired) AND
L_time >= current time (not expired) L_SYM_time < current time (expired)
Link Type = LOST_LINK Link Type = LOST_LINK
2 The Neighbor Type is set according to the following: 2 The Neighbor Type is set according to the following:
2.1 If the main address, corresponding to L_neigh- 2.1 If the main address, corresponding to L_neigh-
bor_iface_addr, is included in the MPR set: bor_iface_addr, is included in the MPR set:
Neighbor Type = MPR_NEIGH Neighbor Type = MPR_NEIGH
2.2 Otherwise, if the main address, corresponding to L_neigh- 2.2 Otherwise, if the main address, corresponding to L_neigh-
bor_iface_addr, is included in the neighbor set: bor_iface_addr, is included in the neighbor set:
2.2.1
if N_status == SYM if N_status == SYM
Neighbor Type = SYM_NEIGH Neighbor Type = SYM_NEIGH
Otherwise, if N_status == NOT_SYM
2.2.2
Otherwise, if N_status == NOT_SYM
Neighbor Type = NOT_NEIGH Neighbor Type = NOT_NEIGH
For each tuple in the Neighbor Set, for which no L_neigh- For each tuple in the Neighbor Set, for which no L_neigh-
bor_iface_addr from an associated link tuple has been advertised by bor_iface_addr from an associated link tuple has been advertised by
the previous algorithm, N_neighbor_main_addr is advertised with: the previous algorithm, N_neighbor_main_addr is advertised with:
- Link Type = UNSPEC_LINK - Link Type = UNSPEC_LINK,
- Neighbor Type set according to the way described above, in step 2 - Neighbor Type set as described in step 2 above
For a node with a single OLSR interface, the main address is simply For a node with a single OLSR interface, the main address is simply
the address of the OLSR interface. I.e. for a node with a single OLSR the address of the OLSR interface. I.e. for a node with a single
interface, the main address, corresponding to L_neighbor_iface_addr OLSR interface, the main address, corresponding to L_neigh-
is simply L_neighbor_iface_addr. bor_iface_addr is simply L_neighbor_iface_addr.
The list of neighbors in a HELLO message can be partial (e.g. due to A HELLO message can be partial (e.g. due to message size limita-
message size limitations, imposed by the network), the rule being the tions, imposed by the network), the rule being the following, on each
following: each neighbor node MUST be cited at least once within a interface: each link and each neighbor node MUST be cited at least
predetermined refreshing period, REFRESH_INTERVAL: at least once with once within a predetermined refreshing period, REFRESH_INTERVAL. To
the correct "Link Type", and at least once with the correct "Neighbor keep track of fast connectivity changes, a HELLO message must be sent
Type" (and, as implemented above, preferably both at the same time). at least every HELLO_INTERVAL period, smaller than or equal to
To keep track of fast connectivity changes, a HELLO message must be
sent at least every HELLO_INTERVAL period, smaller than or equal to
REFRESH_INTERVAL. REFRESH_INTERVAL.
Notice that for limiting the impact from loss of control messages, it Notice that for limiting the impact from loss of control messages, it
is desirable that a message (plus the generic package header) can fit is desirable that a message (plus the generic packet header) can fit
into a single MAC frame. into a single MAC frame.
Each HELLO message generated is broadcast by the node to its neigh- 6.3. HELLO Message Forwarding
bors.
4.4. Populating the Link Set Each HELLO message generated is broadcast by the node on one inter-
face to its neighbors. HELLO messages MUST never be forwarded.
6.4. HELLO Message Processing
A node processes incoming HELLO messages for the purpose of conduct-
ing link sensing (detailed in section 7), neighbor detection
and MPR selector set population (detailed in section 8)
7. Link Sensing
Link sensing populates the local link information base. Link sensing
is exclusively concerned with OLSR interface addresses and the abil-
ity to exchange packets between such OLSR interfaces.
The mechanism for link sensing is the periodic exchange of HELLO
messages.
7.1. Populating the Link Set
The Link Set is populated with information on links to neighbor The Link Set is populated with information on links to neighbor
nodes. The process of populating this set is denoted "link sensing" nodes. The process of populating this set is denoted "link sensing"
and is performed using HELLO message exchange, updating a local link and is performed using HELLO message exchange, updating a local link
information base in each node. information base in each node.
Each node should detect the links between itself and neighbor nodes. Each node should detect the links between itself and neighbor nodes.
Uncertainties over radio propagation may make some links unidirec- Uncertainties over radio propagation may make some links unidirec-
tional. Consequently, all links MUST be checked in both directions in tional. Consequently, all links MUST be checked in both directions
order to be considered valid. in order to be considered valid.
A "link" is described by a pair of interfaces: a local and a remote A "link" is described by a pair of interfaces: a local and a remote
interface. interface.
For the purpose of link sensing, each neighbor node (more specifi- For the purpose of link sensing, each neighbor node (more specifi-
cally, the link to each neighbor) has an associated status of either cally, the link to each neighbor) has an associated status of either
"symmetric" or "asymmetric". "Symmetric" indicates, that the link to "symmetric" or "asymmetric". "Symmetric" indicates, that the link to
that neighbor node has been verified to be bi-directional, i.e. it is that neighbor node has been verified to be bi-directional, i.e. it
possible to transmit data in both directions. "Asymmetric" indicates is possible to transmit data in both directions. "Asymmetric" indi-
that HELLO messages from the node have been heard (i.e. communication cates that HELLO messages from the node have been heard (i.e. commu-
from the neighbor node is possible), however it is not confirmed that nication from the neighbor node is possible), however it is not con-
this node is also able to receive messages (i.e. communication to the firmed that this node is also able to receive messages (i.e. commu-
neighbor node is not confirmed). nication to the neighbor node is not confirmed).
The information, acquired through and used by the link sensing is The information, acquired through and used by the link sensing, is
accumulated in the link set. accumulated in the link set.
4.4.1. HELLO Message Processing 7.1.1. HELLO Message Processing
The "Originator Address" of a HELLO message is the (main) address of The "Originator Address" of a HELLO message is the main address of
the node, which has emitted the message. In the case where only one the node, which has emitted the message.
interface of a node is participating in the MANET running OLSR, this
address is equivalent of the "Source Address" as can be found in the
IP header of the packet containing the message.
Upon receiving a HELLO message, a node SHOULD update its Link Set. Upon receiving a HELLO message, a node SHOULD update its Link Set.
Notice, that a HELLO message MUST neither be forwarded nor be Notice, that a HELLO message MUST neither be forwarded nor be
recorded in the duplicate table. recorded in the duplicate set.
Upon receiving a HELLO message, the "validity time" MUST be computed Upon receiving a HELLO message, the "validity time" MUST be computed
from the Vtime field of the message header (see section 3.3.2). from the Vtime field of the message header (see section 3.3.2).
Then, the Link Set SHOULD be updated as follows: Then, the Link Set SHOULD be updated as follows:
1 Upon receiving a HELLO message, if there exists no link tuple 1 Upon receiving a HELLO message, if there exists no link tuple
with with
L_neighbor_iface_addr == Source Address L_neighbor_iface_addr == Source Address
a new tuple is created with a new tuple is created with
L_neighbor_iface_addr = Source Address L_neighbor_iface_addr = Source Address
L_local_iface_addr = Address of the interface which L_local_iface_addr = Address of the interface
received the HELLO message which received the
HELLO message
L_SYM_time = current time - 1 (expired) L_SYM_time = current time - 1 (expired)
L_time = current time + validity time L_time = current time + validity time
2 The tuple (existing or new) with: 2 The tuple (existing or new) with:
L_neighbor_iface_addr == Source Address L_neighbor_iface_addr == Source Address
is then modified as follows: is then modified as follows:
2.1 L_ASYM_time = current time + validity time; 2.1 L_ASYM_time = current time + validity time;
skipping to change at page 30, line 18 skipping to change at page 38, line 34
L_neighbor_iface_addr == Source Address L_neighbor_iface_addr == Source Address
is then modified as follows: is then modified as follows:
2.1 L_ASYM_time = current time + validity time; 2.1 L_ASYM_time = current time + validity time;
2.2 if the node finds the address of the interface which 2.2 if the node finds the address of the interface which
received the HELLO message among the addresses listed in received the HELLO message among the addresses listed in
the link message then the tuple is modified as follows: the link message then the tuple is modified as follows:
2.2.1
if Link Type is equal to LOST_LINK then if Link Type is equal to LOST_LINK then
L_SYM_time = current time - 1 (i.e. expired) L_SYM_time = current time - 1 (i.e. expired)
2.2.2
else if Link Type is equal to SYM_LINK or ASYM_LINK else if Link Type is equal to SYM_LINK or ASYM_LINK
then then
L_SYM_time = current time + validity time, L_SYM_time = current time + validity time,
L_time = L_SYM_time + NEIGHB_HOLD_TIME L_time = L_SYM_time + NEIGHB_HOLD_TIME
2.3 L_time = max(L_time, L_ASYM_time) 2.3 L_time = max(L_time, L_ASYM_time)
The above rule for setting L_time is the following: a link losing its The above rule for setting L_time is the following: a link losing its
symmetry SHOULD still be advertised during at least the duration of symmetry SHOULD still be advertised during at least the duration of
the "validity time" advertised in the generated HELLO. This allows the "validity time" advertised in the generated HELLO. This allows
neighbors to detect the link breakage. neighbors to detect the link breakage.
4.5. Populating the Neighbor Set 8. Neighbor Detection
Neighbor detection populates the neighborhood information base and
concerns itself with nodes and node main addresses. The relationship
between OLSR interface addresses and main addresses is described in
section 5.
The mechanism for neighbor detection is the periodic exchange of
HELLO messages.
8.1. Populating the Neighbor Set
A node maintains a set of neighbor tuples, based on the link tuples. A node maintains a set of neighbor tuples, based on the link tuples.
This information is updated according to changes in the Link Set. This information is updated according to changes in the Link Set.
The Link Set keeps the information about the links, while the Neigh- The Link Set keeps the information about the links, while the Neigh-
bor Set keeps the information about the neighbors. There is a clear bor Set keeps the information about the neighbors. There is a clear
association between those two sets, since a node is a neighbor of association between those two sets, since a node is a neighbor of
another if and only if there is at least one link between the two another node if and only if there is at least one link between the
nodes. With multiple interface nodes, there might even be several two nodes.
links between two nodes.
In any case, the formal correspondence between links and neighbors is In any case, the formal correspondence between links and neighbors is
defined as follows: defined as follows:
The "associated neighbor tuple" of a link tuple, is, if it The "associated neighbor tuple" of a link tuple, is, if it
exists, the neighbor tuple such as: exists, the neighbor tuple where:
N_neighbor_main_addr == main address of L_neigh- N_neighbor_main_addr == main address of
bor_iface_addr L_neighbor_iface_addr
The "associated link tuples" of a neighbor tuple, are all the The "associated link tuples" of a neighbor tuple, are all the
link tuples, such as the same condition applies: link tuples, where:
N_neighbor_main_addr == main address of L_neigh- N_neighbor_main_addr == main address of
bor_iface_addr L_neighbor_iface_addr
The Neighbor Set MUST populated by maintaining the proper correspon- The Neighbor Set MUST be populated by maintaining the proper corre-
dence between link tuples and associated neighbor tuples, as follows: spondence between link tuples and associated neighbor tuples, as fol-
lows:
Creation Creation
Each time a link appears, that is, each time a link tuple is Each time a link appears, that is, each time a link tuple is
created, the associated neighbor tuple MUST be created with created, the associated neighbor tuple MUST be created, if it
the following values: doesn't already exist, with the following values:
N_neighbor_main_addr = main address of L_neigh- N_neighbor_main_addr = main address of
bor_iface_addr (from the link tuple) L_neighbor_iface_addr
(from the link tuple)
The N_status MUST then computed as described in the next step In any case, the N_status MUST then be computed as described
in the next step
Update Update
Each time a link changes, that is, each time the information Each time a link changes, that is, each time the information
of a link tuple is modified, the node MUST ensure that the of a link tuple is modified, the node MUST ensure that the
N_status of the associated neighbor tuple respects the prop- N_status of the associated neighbor tuple respects the prop-
erty: erty:
If the neighbor has any associated link which is a sym- If the neighbor has any associated link tuple which indi-
metrical link (i.e. with L_SYM_time >= current time), cates a symmetrical link (i.e. with L_SYM_time >= cur-
then rent time), then
N_status is set to SYM N_status is set to SYM
else N_status is set to NOT_SYM else N_status is set to NOT_SYM
Removal Removal
Each time a link is deleted, that is, each time a link tuple Each time a link is deleted, that is, each time a link tuple
is removed, the associated neighbor tuple MUST be removed if is removed, the associated neighbor tuple MUST be removed if
it has no longer any associated links. it has no longer any associated link tuples.
Those rules ensure that there is exactly one associated neighbor These rules ensure that there is exactly one associated neighbor
tuple for a link tuple, and that every neighbor tuple has at least tuple for a link tuple, and that every neighbor tuple has at least
one associated link tuple. one associated link tuple.
4.5.1. HELLO Message Processing 8.1.1. HELLO Message Processing
The "Originator Address" of a HELLO message is the (main) address of The "Originator Address" of a HELLO message is the main address of
the node, which has emitted the message. In the case where only one the node, which has emitted the message. Likewise, the "willingness"
interface of a node is participating in the MANET running OLSR, this MUST be computed from the Willingness field of the HELLO message (see
address is equivalent of the "Source Address" as can be found in the section 6.1).
IP header of the packet containing the message. Likewise, the "will-
ingness" MUST be computed from the Willingness field of the HELLO
message (see section 4.2).
Upon receiving a HELLO message, a node SHOULD first update its Link Upon receiving a HELLO message, a node SHOULD first update its Link
Set as described before It SHOULD then update its Neighbor Set as Set as described before. It SHOULD then update its Neighbor Set as
follows: follows:
- if the Originator Address is the N_neighbor_main_addr from a - if the Originator Address is the N_neighbor_main_addr from a
neighbor tuple included in the Neighbor Set: neighbor tuple included in the Neighbor Set:
then, the neighbor tuple SHOULD be updated as follows: then, the neighbor tuple SHOULD be updated as follows:
N_willingness = willingness from the HELLO message N_willingness = willingness from the HELLO message
4.6. Populating the 2-hop Neighbor Set 8.2. Populating the 2-hop Neighbor Set
The 2-hop neighbor set describes the set of nodes which have a sym- The 2-hop neighbor set describes the set of nodes which have a sym-
metric link to a symmetric neighbor. This information set is main- metric link to a symmetric neighbor. This information set is main-
tained through periodic exchange of HELLO messages as described in tained through periodic exchange of HELLO messages as described in
this section. this section.
4.6.1. HELLO Message Processing 8.2.1. HELLO Message Processing
The "Originator Address" of a HELLO message is the (main) address of The "Originator Address" of a HELLO message is the main address of
the node, which has emitted the message. In the case where only one the node, which has emitted the message.
interface of a node is participating in the MANET running OLSR, this
address is equivalent of the "Source Address" as can be found in the
IP header of the packet containing the message.
Upon receiving a HELLO message from a symmetric neighbor, a node Upon receiving a HELLO message from a symmetric neighbor, a node
SHOULD update its 2-hop Neighbor Set. Notice, that a HELLO message SHOULD update its 2-hop Neighbor Set. Notice, that a HELLO message
MUST neither be forwarded nor be recorded in the duplicate table. MUST neither be forwarded nor be recorded in the duplicate set.
Upon receiving a HELLO message, the "validity time" MUST be computed Upon receiving a HELLO message, the "validity time" MUST be computed
from the Vtime field of the message header (see section 3.3.2). from the Vtime field of the message header (see section 3.3.2).
If the Originator Address is the main address of a L_neigh- If the Originator Address is the main address of a L_neigh-
bor_iface_addr from a link tuple included in the Link Set with bor_iface_addr from a link tuple included in the Link Set with
L_SYM_time >= current time (not expired) L_SYM_time >= current time (not expired)
(in other words: if the Originator Address is included in the Neigh- (in other words: if the Originator Address is a symmetric neighbor)
bor Set with N_status = SYM) then the 2-hop Neighbor Set SHOULD then then the 2-hop Neighbor Set SHOULD be updated as follows:
be updated as follows:
1 for each address (henceforth: 2-hop neighbor address), listed 1 for each address (henceforth: 2-hop neighbor address), listed
in the HELLO message with Neighbor Type equal to SYM_NEIGH or in the HELLO message with Neighbor Type equal to SYM_NEIGH or
MPR_NEIGH: MPR_NEIGH:
1.1 if 2-hop neighbor address = main address of receiving 1.1 if the main address of the 2-hop neighbor address = main
node: address of receiving node:
silently discard the 2-hop neighbor address. silently discard the 2-hop neighbor address.
(in other words: a node is not its own 2-hop neighbor). (in other words: a node is not its own 2-hop neighbor).
1.2 Otherwise, a 2-hop tuple is created with: 1.2 Otherwise, a 2-hop tuple is created with:
N_neighbor_main_addr = Originator Address; N_neighbor_main_addr = Originator Address;
N_2hop_addr = main address of the 2-hop neighbor; N_2hop_addr = main address of the
2-hop neighbor;
N_time = current time + validity time. N_time = current time
+ validity time.
This tuple may replace an older similar tuple with same This tuple may replace an older similar tuple with same
N_neighbor_main_addr and N_2hop_addr values. N_neighbor_main_addr and N_2hop_addr values.
2 For each 2-hop node listed in the HELLO message with Neighbor 2 For each 2-hop node listed in the HELLO message with Neighbor
Type equal to NOT_NEIGH, all 2-hop tuples where: Type equal to NOT_NEIGH, all 2-hop tuples where:
N_neighbor_main_addr == Originator Address AND N_neighbor_main_addr == Originator Address AND
N_2hop_addr == main address of the 2-hop neighbor N_2hop_addr == main address of the
2-hop neighbor
are deleted. are deleted.
4.6.2. Populating the MPR set 8.3. Populating the MPR set
MPRs are used to flood control messages from a node into the network MPRs are used to flood control messages from a node into the network
while reducing the number of retransmissions that will occur in a while reducing the number of retransmissions that will occur in a
region. Thus, the concept of MPR is an optimization of a classical region. Thus, the concept of MPR is an optimization of a classical
flooding mechanism. flooding mechanism.
Each node in the network selects, independently, its own set of MPRs Each node in the network selects, independently, its own set of MPRs
among its symmetric neighborhood. The symmetric links with MPRs are among its symmetric 1-hop neighborhood. The symmetric links with
advertised with Link Type MPR_NEIGH instead of SYM_NEIGH in HELLO MPRs are advertised with Link Type MPR_NEIGH instead of SYM_NEIGH in
messages. HELLO messages.
The MPR set MUST be calculated by a node in such a way that it, The MPR set MUST be calculated by a node in such a way that it,
through the neighbors in the MPR-set, can reach all symmetric strict through the neighbors in the MPR-set, can reach all symmetric strict
2-hop neighbors. (Notice that a node, a, which is a direct neighbor 2-hop neighbors. (Notice that a node, a, which is a direct neighbor
of another node, b, is not also a strict 2-hop neighbor of node b). of another node, b, is not also a strict 2-hop neighbor of node b).
This means that the union of the symmetric neighborhoods of the MPR This means that the union of the symmetric 1-hop neighborhoods of the
nodes contains the symmetric strict 2-hop neighborhood. MPR set MPR nodes contains the symmetric strict 2-hop neighborhood. MPR set
recalculation should occur when changes are detected in the neighbor- recalculation should occur when changes are detected in the neighbor-
hood or in the 2-hop neighborhood. hood or in the 2-hop neighborhood.
While it is not essential that the MPR set is minimal, it is essen- MPRs are computed per interface, the union of the MPR sets of each
tial that all strict 2-hop neighbors can be reached through the interface make up the MPR set for the node.
While it is not essential that the MPR set is minimal, it is
essential that all strict 2-hop neighbors can be reached through the
selected MPR nodes. A node SHOULD select an MPR set such that any selected MPR nodes. A node SHOULD select an MPR set such that any
strict 2-hop neighbor is covered by at least one MPR node. This strict 2-hop neighbor is covered by at least one MPR node. This
ensures that the overhead of the protocol is kept at a minimum. ensures that the overhead of the protocol is kept at a minimum.
By default, the MPR set can coincide with the entire symmetric neigh- The MPR set can coincide with the entire symmetric neighbor set.
bor set. This will be the case at network initialization (and will This could be the case at network initialization (and will correspond
correspond to classic link-state routing). to classic link-state routing).
4.6.3. MPR Computation 8.3.1. MPR Computation
The following specifies a proposed heuristic for selection of MPRs. The following specifies a proposed heuristic for selection of MPRs.
It constructs an MPR-set that enables a node to reach any node in the It constructs an MPR-set that enables a node to reach any node in the
symmetrical strict 2-hop neighborhood through relaying by one MPR symmetrical strict 2-hop neighborhood through relaying by one MPR
node. The following terminology will be used in describing this algo- node with willingness different from WILL_NEVER. The heuristic MUST
rithm: be applied per interface, I. The MPR set for a node is the union of
the MPR sets found for each interface. The following terminology
will be used in describing the heuristics:
neighbor of an interface
a node is a "neighbor of an interface" if the interface
(on the local node) has a link to any one interface of
the neighbor node.
2-hop neighbors reachable from an interface
the list of 2-hop neighbors of the node that can be
reached from neighbors of this interface.
MPR set of an interface
a (sub)set of the neighbors of an interface with a will-
ingness different from WILL_NEVER, selected such that
through these selected nodes, all strict 2-hop neighbors
reachable from that interface are reachable.
N: N:
The set of neighbors with which there exists a symmetric link.
N is the subset of neighbors of the node, which are
neighbor of the interface I.
N2: N2:
The set made of the nodes in the symmetric 2-hop neighbor set
excluding (i) the nodes only reachable by members of N with The set of two-hop neighbors reachable from the interface
N_willingness WILL_NEVER, (ii) all the nodes in N and (iii) I, excluding:
the node performing the computation.
(i) the nodes only reachable by members of N with will-
ingness WILL_NEVER
(ii) the node performing the computation
(iii)
all the symmetric neighbors: the nodes for which
there exists a symmetric link to this node on some
interface.
D(y): D(y):
The degree of an one hop neighbor node y (where y is a member The degree of an one hop neighbor node y (where y is a
of N), is defined as the number of symmetric neighbors of node member of N), is defined as the number of symmetric
y, EXCLUDING all the members of N and EXCLUDING the node per- neighbors of node y, EXCLUDING all the members of N and
forming the computation. EXCLUDING the node performing the computation.
The proposed heuristic is as follows: The proposed heuristic is as follows:
1 Start with an MPR set made of all members of N with N_willing- 1 Start with an MPR set made of all members of N with N_willing-
ness equal to WILL_ALWAYS ness equal to WILL_ALWAYS
2 Calculate D(y), where y is a member of N, for all nodes in N. 2 Calculate D(y), where y is a member of N, for all nodes in N.
3 While there exist nodes in N2 which are not covered by at 3 Add to the MPR set those nodes in N, which are the *only*
nodes to provide reachability to a node in N2. I.e. if node
b in N2 can be reached only through a symmetric link to node a
in N, then add node a to the MPR set. Remove the nodes from
N2 which are now covered by a node in the MPR set.
4 While there exist nodes in N2 which are not covered by at
least one node in the MPR set: least one node in the MPR set:
3.1 For each node in N, calculate the reachability, i.e. the 4.1 For each node in N, calculate the reachability, i.e. the
number of nodes in N2 which are not yet covered by at number of nodes in N2 which are not yet covered by at
least one node in the MPR set, and which are reachable least one node in the MPR set, and which are reachable
through this one hop neighbor; through this one hop neighbor;
3.2 Select as a MPR the node with highest N_willingness among 4.2 Select as a MPR the node with highest N_willingness among
the nodes in N with non-zero reachability. In case of the nodes in N with non-zero reachability. In case of
multiple choice select the node which provides reachabil- multiple choice select the node which provides
ity to the maximum number of nodes in N2. In case of reachability to the maximum number of nodes in N2. In
multiple nodes providing the same amount of reachability, case of multiple nodes providing the same amount of
select the node as MPR whose D(y) is greater. Remove the reachability, select the node as MPR whose D(y) is
nodes from N2 which are now covered by a node in the MPR greater. Remove the nodes from N2 which are now covered
set. by a node in the MPR set.
4 As an optimization, process each node y in the MPR set in the 5 A node's MPR set is generated from the union of the MPR sets
increasing order of their willingness. If all nodes in N2 are for each interface. As an optimization, process each node, y,
still covered by at least one node in the MPR set excluding y in the MPR set in increasing order of N_willingness. If all
and N_willingness of node y is smaller than WILL_ALWAYS, then nodes in N2 are still covered by at least one node in the MPR
node y is removed from the MPR set. set excluding node y, and if N_willingness of node y is
smaller than WILL_ALWAYS, then node y MAY be removed from the
MPR set.
4.7. Populating the MPR Selector Set Other algorithms, as well as improvements over this algorithm, are
possible. For example, assume that in a multiple-interface scenario
there exists more than one link between nodes 'a' and 'b'. If node
'a' has selected node 'b' as MPR for one of its interfaces, then node
'b' can be selected as MPR without additional performance loss by any
other interfaces on node 'a'.
8.4. Populating the MPR Selector Set
The MPR selector set of a node, n, is populated by the main addresses The MPR selector set of a node, n, is populated by the main addresses
of the nodes which have selected n as MPR. MPR selection is signaled of the nodes which have selected n as MPR. MPR selection is signaled
through HELLO messages. through HELLO messages.
4.7.1. HELLO Message Processing 8.4.1. HELLO Message Processing
Upon receiving a HELLO message, if a node finds one of its own inter- Upon receiving a HELLO message, if a node finds one of its own inter-
face addresses in the list with a Neighbor Type equal to MPR_NEIGH, face addresses in the list with a Neighbor Type equal to MPR_NEIGH,
information from the HELLO message must be recorded in the MPR information from the HELLO message must be recorded in the MPR Selec-
Selector Set. tor Set.
The "validity time" MUST be computed from the Vtime field of the mes- The "validity time" MUST be computed from the Vtime field of the mes-
sage header (see section 3.3.2). The MPR Selector Set SHOULD sage header (see section 3.3.2). The MPR Selector Set SHOULD
then be updated as follows: then be updated as follows:
1 If there exists no MPR selector tuple with: 1 If there exists no MPR selector tuple with:
MS_main_addr == Originator Address MS_main_addr == Originator Address
then a new tuple is created with: then a new tuple is created with:
MS_main_addr = Originator Address MS_main_addr = Originator Address
3 The tuple is then modified as follows: 2 The tuple (new or otherwise) with
MS_main_addr == Originator Address
is then modified as follows:
MS_time = current time + validity time. MS_time = current time + validity time.
Deletion of MPR selector tuples occurs in case of expiration of the Deletion of MPR selector tuples occurs in case of expiration of the
timer or in case of link breakage as described in the "Neighborhood timer or in case of link breakage as described in the "Neighborhood
and 2-hop Neighborhood Changes". and 2-hop Neighborhood Changes".
4.8. Neighborhood and 2-hop Neighborhood Changes 8.5. Neighborhood and 2-hop Neighborhood Changes
A change in the neighborhood is detected when: A change in the neighborhood is detected when:
- The L_SYM_time field of a link tuple expires. This is consid- - The L_SYM_time field of a link tuple expires. This is consid-
ered as a neighbor loss if it was the last link with a neigh- ered as a neighbor loss if the link described by the expired
bor node (on the contrary, a link with an interface may break tuple was the last link with a neighbor node (on the contrary,
while a link with another interface of the neighbor node a link with an interface may break while a link with another
remains). interface of the neighbor node remains without being observed
as a neighborhood change).
- A new link tuple is inserted in the Link Set with a non- - A new link tuple is inserted in the Link Set with a non-
expired L_SYM_time or a tuple with expired L_SYM_time is modi- expired L_SYM_time or a tuple with expired L_SYM_time is modi-
fied so that L_SYM_time becomes non-expired. This is consid- fied so that L_SYM_time becomes non-expired. This is consid-
ered as a neighbor appearance if there was previously no link ered as a neighbor appearance if there was previously no link
with the corresponding neighbor node. tuple describing a link with the corresponding neighbor node.
A change in the 2-hop neighborhood is detected when a 2-hop neighbor A change in the 2-hop neighborhood is detected when a 2-hop neighbor
tuple expires or is deleted according to section 4.6. tuple expires or is deleted according to section 8.2.
The following processing occurs when changes in the neighborhood or The following processing occurs when changes in the neighborhood or
the 2-hop neighborhood are detected: the 2-hop neighborhood are detected:
- In case of neighbor loss, all the 2-hop tuples with N_neigh- - In case of neighbor loss, all 2-hop tuples with N_neigh-
bor_main_addr == Main Address of the neighbor MUST be deleted. bor_main_addr == Main Address of the neighbor MUST be deleted.
- In case of neighbor loss, all the MPR selector tuples with - In case of neighbor loss, all MPR selector tuples with
MS_main_addr == Main Address of the neighbor MUST be deleted MS_main_addr == Main Address of the neighbor MUST be deleted
- The MPR set MUST be re-calculated when a neighbor appearance - The MPR set MUST be re-calculated when a neighbor appearance
or loss is detected, or when a change in the 2-hop neighbor- or loss is detected, or when a change in the 2-hop neighbor-
hood is detected. hood is detected.
- An additional HELLO message MAY be sent when the MPR set - An additional HELLO message MAY be sent when the MPR set
changes. changes.
5. Topology Discovery 9. Topology Discovery
The link sensing and neighbor detection part of the protocol basi- The link sensing and neighbor detection part of the protocol basi-
cally offers, to each node, a list of neighbors with which it can cally offers, to each node, a list of neighbors with which it can
communicate directly and, in combination with the Packet Format and communicate directly and, in combination with the Packet Format and
Forwarding part, an optimized flooding mechanism through MPRs. Based Forwarding part, an optimized flooding mechanism through MPRs. Based
on this, topology information is disseminated through the network. on this, topology information is disseminated through the network.
The present section describes what part of the information given by The present section describes what part of the information given by
the link sensing and neighbor detection is disseminated to the entire the link sensing and neighbor detection is disseminated to the entire
network and how it is used to construct routes. network and how it is used to construct routes.
Routes are constructed through advertised links and links with neigh- Routes are constructed through advertised links and links with neigh-
bors. A node must at least disseminate links between itself and the bors. A node must at least disseminate links between itself and the
nodes in its MPR-selector set, in order to provide sufficient infor- nodes in its MPR-selector set, in order to provide sufficient infor-
mation to enable routing. mation to enable routing.
5.1. TC Message Format 9.1. TC Message Format
The proposed format of a TC message is The proposed format of a TC message is as follows:
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ANSN | Reserved | | ANSN | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Advertised neighbor Main Address | | Advertised Neighbor Main Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Advertised neighbor Main Address | | Advertised Neighbor Main Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... | | ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This is sent as the data-portion of the general message format with This is sent as the data-portion of the general message format with
the "Message Type" set to TC_MESSAGE. The time to live SHOULD be set the "Message Type" set to TC_MESSAGE. The time to live SHOULD be set
to 255 (maximum value) to diffuse the message into the entire network to 255 (maximum value) to diffuse the message into the entire network
and Vtime set accordingly to the value of TOP_HOLD_TIME, as specified and Vtime set accordingly to the value of TOP_HOLD_TIME, as specified
in section 15.3. in section 18.3.
Advertised Neighbor Sequence Number (ANSN) Advertised Neighbor Sequence Number (ANSN)
A sequence number is associated with the advertised neighbor A sequence number is associated with the advertised neighbor
set. Every time a node detects a change in its advertised set. Every time a node detects a change in its advertised
neighbor set, it increments this sequence number ("Wrap- neighbor set, it increments this sequence number ("Wrap-
around" is handled as described in section 16). This around" is handled as described in section 19). This
number is sent in this ANSN field of the TC message to keep number is sent in this ANSN field of the TC message to keep
track of the most recent information. When a node receives a track of the most recent information. When a node receives a
TC message, it can decide on the basis of this Advertised TC message, it can decide on the basis of this Advertised
Neighbor Sequence Number, whether or not the received informa- Neighbor Sequence Number, whether or not the received informa-
tion about the advertised neighbors of the originator node is tion about the advertised neighbors of the originator node is
more recent than what it already has. more recent than what it already has.
Advertised Neighbor Main Address Advertised Neighbor Main Address
This field contains the main address of a neighbor node. All This field contains the main address of a neighbor node. All
main addresses of the advertised neighbors of the Originator main addresses of the advertised neighbors of the Originator
node are put in the TC message. If the maximum allowed message node are put in the TC message. If the maximum allowed mes-
size (as imposed by the network) is reached while there are sage size (as imposed by the network) is reached while there
still advertised neighbor addresses which have not been are still advertised neighbor addresses which have not been
inserted into the TC-message, more TC messages will be gener- inserted into the TC-message, more TC messages will be gener-
ated until the entire advertised neighbor set has been sent. ated until the entire advertised neighbor set has been sent.
Extra main addresses of neighbor nodes may be included, if Extra main addresses of neighbor nodes may be included, if
redundancy is desired. redundancy is desired.
Reserved Reserved
This field is reserved, and MUST be set to "0000000000000000" This field is reserved, and MUST be set to "0000000000000000"
for compliance with this document. for compliance with this document.
5.2. Topology Information Base 9.2. Advertised Neighbor Set
Each node in the network maintains topological information about the
network. This information is acquired from TC-messages and is used
for routing table calculations.
Thus, for each destination in the network, a "Topology Tuple"
(T_dest_addr, T_last_addr, T_seq, T_time) is recorded. T_dest_addr is
the main address of a node, which may be reached in one hop from the
node with the main address T_last_addr. Typically, T_last_addr is a
MPR of T_dest_addr. T_seq is a sequence number, and T_time specifies
the time at which this tuple expires and *MUST* be removed.
In a node, the set of Topology Tuples are denoted the "Topology Set".
5.3. Advertised Neighbor Set
A TC message is sent by a node in the network to declare a set of A TC message is sent by a node in the network to declare a set of
links, called advertised link set which MUST include at least the links, called advertised link set which MUST include at least the
links to all nodes of its MPR Selector set, i.e., the neighbors which links to all nodes of its MPR Selector set, i.e., the neighbors which
have selected the sender node as a MPR. If, for some reason, it is have selected the sender node as a MPR.
required to distribute redundant TC information, refer to section
11. If, for some reason, it is required to distribute redundant TC infor-
mation, refer to section 15.
The sequence number (ANSN) associated with the advertised neighbor The sequence number (ANSN) associated with the advertised neighbor
set is also sent with the list. The ANSN number MUST be incremented set is also sent with the list. The ANSN number MUST be incremented
when links are removed from the advertised neighbor set; the ANSN when links are removed from the advertised neighbor set; the ANSN
number SHOULD be incremented when links are added to the advertised number SHOULD be incremented when links are added to the advertised
neighbor set. neighbor set.
5.4. TC Message Generation 9.3. TC Message Generation
In order to build the topology information base needed, each node, In order to build the topology information base, each node, which has
which has been selected as MPR, broadcasts Topology Control (TC) mes- been selected as MPR, broadcasts Topology Control (TC) messages. TC
sages. TC messages are flooded to all nodes in the network and take messages are flooded to all nodes in the network and take advantage
advantage of MPRs. MPRs enable a better scalability in the distribu- of MPRs. MPRs enable a better scalability in the distribution of
tion of topology information [1]. topology information [1].
The list of addresses can be partial in each TC message (e.g. due to The list of addresses can be partial in each TC message (e.g. due to
message size limitations, imposed by the network), but parsing of all message size limitations, imposed by the network), but parsing of all
TC messages describing the advertised link set of a node MUST be com- TC messages describing the advertised link set of a node MUST be com-
plete within a certain refreshing period (TC_INTERVAL). The informa- plete within a certain refreshing period (TC_INTERVAL). The informa-
tion diffused in the network by these TC messages will help each node tion diffused in the network by these TC messages will help each node
calculate its routing table. calculate its routing table.
When the advertised link set of a node becomes empty, it SHOULD still When the advertised link set of a node becomes empty, it SHOULD still
send (empty) TC-messages during the a duration equal to "validity send (empty) TC-messages during the a duration equal to the "validity
time" of its TC-messages to invalidate the previous TC-messages. It time" (typically, this will be equal to TC_HOLD_TIME) of its previ-
SHOULD then stop sending TC-messages until some node is inserted in ously emitted TC-messages, in order to invalidate the previous TC-
its advertised link set. messages. It SHOULD then stop sending TC-messages until some node is
inserted in its advertised link set.
A node MAY transmit additional TC-messages to increase its reactive- A node MAY transmit additional TC-messages to increase its reactive-
ness to link failures. When a change to the MPR selector set is ness to link failures. When a change to the MPR selector set is
detected and this change can be attributed to a link failure, a TC- detected and this change can be attributed to a link failure, a TC-
message SHOULD be transmitted after a shorter interval than TC_INTER- message SHOULD be transmitted after a shorter interval than TC_INTER-
VAL. VAL.
5.5. TC Message Forwarding 9.4. TC Message Forwarding
TC messages are broadcasted and retransmitted by the MPRs in order to TC messages are broadcast and retransmitted by the MPRs in order to
diffuse the messages in the entire network. TC messages MUST be diffuse the messages in the entire network. TC messages MUST be for-
forwarded according to the "default forwarding algorithm". warded according to the "default forwarding algorithm".
5.6. TC Message Processing 9.5. TC Message Processing
Upon receiving a TC message, the "validity time" MUST be computed Upon receiving a TC message, the "validity time" MUST be computed
from the Vtime field of the message header (see section 3.3.2). from the Vtime field of the message header (see section 3.3.2).
The topology set SHOULD then be updated as follows (using section The topology set SHOULD then be updated as follows (using section
16 for comparison of ANSN): 19 for comparison of ANSN):
1 If the sender interface (NB: not originator) of this message 1 If the sender interface (NB: not originator) of this message
is not in the symmetric neighborhood of this node, the message is not in the symmetric 1-hop neighborhood of this node, the
MUST be discarded. message MUST be discarded.
2 If there exist some tuple in the topology set where: 2 If there exist some tuple in the topology set where:
T_last_addr == originator address AND T_last_addr == originator address AND
T_seq > ANSN, T_seq > ANSN,
then further processing of this TC message MUST NOT be per- then further processing of this TC message MUST NOT be per-
formed and the message MUST be silently discarded (case: mes- formed and the message MUST be silently discarded (case: mes-
sage received out of order). sage received out of order).
skipping to change at page 41, line 18 skipping to change at page 51, line 5
set where: set where:
T_dest_addr = advertised neighbor main address, T_dest_addr = advertised neighbor main address,
T_last_addr = originator address, T_last_addr = originator address,
T_seq = ANSN, T_seq = ANSN,
T_time = current time + validity time. T_time = current time + validity time.
5.7. Routing Table Calculation 10. Routing Table Calculation
Each node maintains a routing table which allows it to route data, Each node maintains a routing table which allows it to route data,
destined for the other nodes in the network. The routing table is destined for the other nodes in the network. The routing table is
based on the information contained in the link set and the topology based on the information contained in the link set and the topology
set. Therefore, if any of these sets are changed, the routing table set. Therefore, if any of these sets are changed, the routing table
is re-calculated to update the route information about each destina- is re-calculated to update the route information about each destina-
tion in the network. The route entries are recorded in the routing tion in the network. The route entries are recorded in the routing
table in the following format: table in the following format:
1. R_dest_addr R_next_addr R_dist R_iface_addr 1. R_dest_addr R_next_addr R_dist R_iface_addr
2. R_dest_addr R_next_addr R_dist R_iface_addr 2. R_dest_addr R_next_addr R_dist R_iface_addr
3. ,, ,, ,, ,, 3. ,, ,, ,, ,,
Each entry in the table consists of R_dest_addr, R_next_addr, R_dist, Each entry in the table consists of R_dest_addr, R_next_addr, R_dist,
and R_iface_addr which specifies that the node identified by and R_iface_addr. Such entry specifies that the node identified by
R_dest_addr is estimated to be R_dist hops away from the local node, R_dest_addr is estimated to be R_dist hops away from the local node,
and that the symmetric neighbor node with interface address that the symmetric neighbor node with interface address R_next_addr
R_next_addr is the next hop node in the route to R_dest_addr, and is the next hop node in the route to R_dest_addr, and that this sym-
this one hop is reachable through the local interface R_iface_addr. metric neighbor node is reachable through the local interface with
Entries are recorded in the table for each destination in the network the address R_iface_addr. Entries are recorded in the routing table
for which the route is known. All the destinations for which the for each destination in the network for which a route is known. All
route is broken or partially known are not entered in the table. the destinations, for which a route is broken or only partially
known, are not recorded in the table.
The routing table is updated when a change is detected in the neigh- The routing table is updated when a change is detected in either:
bor information base and the topology set (and also the Multiple
Interface Association Information Base, section 7.3.1, and the - the link set,
Host and Network Association Information Base, section 8,
if applicable). More precisely, the routing table is re-calculated in - the neighbor set,
case of neighbor appearance or loss, or when a topology tuple is cre-
ated or removed. The update of this routing information does not gen- - the 2-hop neighbor set,
erate or trigger any messages to be transmitted, neither in the net-
work, nor in the one-hop neighborhood. - the topology set,
- the Multiple Interface Association Information Base,
More precisely, the routing table is re-calculated in case of neigh-
bor appearance or loss, when a 2-hop tuple is created or removed,when
a topology tuple is created or removed or when multiple interface
association information changes. The update of this routing informa-
tion does not generate or trigger any messages to be transmitted,
neither in the network, nor in the 1-hop neighborhood.
To construct the routing table of node X, a shortest path algorithm To construct the routing table of node X, a shortest path algorithm
is run on the directed graph containing the arcs X -> Y where Y is is run on the directed graph containing the arcs X -> Y where Y is
any symmetric neighbor of X (with Link Type equal to SYM_LINK) and any symmetric neighbor of X (with Neighbor Type equal to SYM), the
the arcs U -> V where there exists an entry in the topology set with arcs Y -> Z where Y is a neighbor node with willingness different of
V as T_dest_addr and U as T_last_addr. WILL_NEVER and there exists an entry in the 2-hop Neighbor set with Y
as N_neighbor_main_addr and Z as N_2hop_addr, and the arcs U -> V,
where there exists an entry in the topology set with V as T_dest_addr
and U as T_last_addr.
The following procedure is given as an example to calculate (or re- The following procedure is given as an example to calculate (or re-
calculate) the routing table : calculate) the routing table :
1 All the entries from the routing table are removed. 1 All the entries from the routing table are removed.
2 The new routing entries are added starting with the symmetric 2 The new routing entries are added starting with the symmetric
neighbors (h=1) as the destination nodes. I.e. for each link neighbors (h=1) as the destination nodes. I.e. for each
tuple in the link set where: neighbor tuple in the neighbor set where:
L_SYM_time >= current time N_status = SYM
(there is a symmetric link to the neighbor), a new routing (there is a symmetric link to the neighbor), and for each
entry is recorded in the routing table with: associated link tuple of the neighbor node such that L_time >=
current time, a new routing entry is recorded in the routing
table with:
R_dest_addr = main address of the neighbor with inter- R_dest_addr = L_neighbor_iface_addr, of the
face L_neighbor_iface_addr; associated link tuple;
R_next_addr = L_neighbor_iface_addr; R_next_addr = L_neighbor_iface_addr, of the
associated link tuple;
R_dist = 1; R_dist = 1;
R_iface_addr = L_local_iface_addr of the entry. R_iface_addr = L_local_iface_addr of the
associated link tuple.
If in the above, R_dest_addr is distinct from R_next, another If in the above, no R_dest_addr is equal to the main address
new routing entry with MUST be added, with: of the neighbor, then another new routing entry with MUST be
added, with:
R_dest_addr = L_neighbor_iface_addr; R_dest_addr = main address of the neighbor;
R_next_addr = L_neighbor_iface_addr; R_next_addr = L_neighbor_iface_addr of one of the
associated link tuple with L_time >= cur-
rent time;
R_dist = 1; R_dist = 1;
R_iface_addr = L_local_iface_addr. R_iface_addr = L_local_iface_addr of the
associated link tuple.
3 for each node in N2, i.e a 2-hop neighbor which is not a
neighbor node or the node itself, and such that there exist at
least one entry in the 2-hop neighbor set where N_neigh-
bor_main_addr correspond to a neighbor node with willingness
different of WILL_NEVER, one selects one 2-hop tuple and cre-
ates one entry in the routing table with:
R_dest_addr = the main address of the two hop neighbor;
R_next_addr = the R_next_addr of the entry in the
routing table with:
R_dest_addr == N_neighbor_main_addr
of the 2-hop tuple;
R_dist = 2;
R_iface_addr = the R_iface_addr of the entry in the
routing table with:
R_dest_addr == N_neighbor_main_addr
of the 2-hop tuple;
3 The new route entries for the destination nodes h+1 hops away 3 The new route entries for the destination nodes h+1 hops away
are recorded in the routing table. The following procedure are recorded in the routing table. The following procedure
MUST be executed for each value of h, starting with h=1 and MUST be executed for each value of h, starting with h=2 and
incrementing it by 1 each time. The execution will stop if no incrementing it by 1 each time. The execution will stop if no
new entry is recorded in an iteration. new entry is recorded in an iteration.
3.1 For each topology entry in the topology table, if its 3.1 For each topology entry in the topology table, if its
T_dest_addr does not correspond to R_dest_addr of any T_dest_addr does not correspond to R_dest_addr of any
route entry in the routing table AND its T_last_addr cor- route entry in the routing table AND its T_last_addr cor-
responds to R_dest_addr of a route entry whose R_dist is responds to R_dest_addr of a route entry whose R_dist is
equal to h, then a new route entry MUST be recorded in equal to h, then a new route entry MUST be recorded in
the routing table (if it does not already exist) where: the routing table (if it does not already exist) where:
R_dest_addr = T_dest_addr; R_dest_addr = T_dest_addr;
R_next_addr = R_next_addr of the recorded route R_next_addr = R_next_addr of the recorded
entry whose R_dest_addr == T_last_addr route entry where:
R_dest_addr == T_last_addr
R_dist = h+1; and R_dist = h+1; and
R_iface_addr = R_iface_addr of the recorded
route entry where:
R_iface_addr = R_iface_addr of the recorded route R_dest_addr == T_last_addr.
entry whose R_dest_addr == T_last_addr.
3.2 Several topology entries may be used to select a next hop 3.2 Several topology entries may be used to select a next hop
R_next_addr for reaching the node R_dest_addr. When h=1, R_next_addr for reaching the node R_dest_addr. When h=1,
ties should be broken such that nodes with highest will- ties should be broken such that nodes with highest will-
ingness and MPR selectors are preferred as next hop. ingness and MPR selectors are preferred as next hop.
If the MPR set has changed, a TC message containing the new MPR 4 For each entry in the multiple interface association base
selector set SHOULD be generated. where there exists a routing entry such that:
6. Node Configuration R_dest_addr == I_main_addr (of the multiple interface
association entry)
AND there is no routing entry such that:
R_dest_addr == I_iface_addr
then a route entry is created in the routing table with:
R_dest_addr = I_iface_addr (of the multiple interface
association entry)
R_next_addr = R_next_addr (of the recorded
route entry)
R_dist = R_dist (of the recorded
route entry)
R_iface_addr = R_iface_addr (of the recorded
route entry).
11. Node Configuration
This section outlines how a node should be configured, in order to This section outlines how a node should be configured, in order to
operate in an OLSR manet. operate in an OLSR MANET.
6.1. Address Assignment 11.1. Address Assignment
The nodes in the MANET network SHOULD be assigned addresses within a The nodes in the MANET network SHOULD be assigned addresses within a
defined address sequence. I.e., the nodes in the MANET SHOULD be defined address sequence. I.e., the nodes in the MANET SHOULD be
addressable through a network address and a netmask. addressable through a network address and a netmask.
Likewise, the nodes in each associated network SHOULD be assigned Likewise, the nodes in each associated network SHOULD be assigned
addresses from a defined address sequence, distinct from that being addresses from a defined address sequence, distinct from that being
used in the MANET. used in the MANET.
6.2. Routing Configuration 11.2. Routing Configuration
Any MANET node with associated networks or hosts SHOULD be configured Any MANET node with associated networks or hosts SHOULD be configured
such that it has routes set up to the interfaces with associated such that it has routes set up to the interfaces with associated
hosts or network. hosts or network.
6.3. Data Packet Forwarding 11.3. Data Packet Forwarding
OLSR itself does not perform packet forwarding. Rather, it maintains OLSR itself does not perform packet forwarding. Rather, it maintains
the routing table in the underlying operating system, which is the routing table in the underlying operating system, which is
assumed to be forwarding packets as specified in RFC1812. assumed to be forwarding packets as specified in RFC1812.
7. Multiple OLSR Interfaces 12. Non OLSR Interfaces
A node may have multiple interfaces, each with a distinct IP address.
These interfaces may either participate in the OLSR routing domain -
or they may participate in other routing domains. Integrating infor-
mation from non-OLSR routing domains into OLSR is described in sec-
tion 8.
A node with only a single OLSR interface, which wishes to participate
in a network of nodes with multiple OLSR interfaces SHOULD implement
the provisions described in section #REF:midmf and 7.7.
For nodes with multiple OLSR interfaces, participating in the OLSR
routing domain, the provisions in this section MUST be applied.
7.1. Terminology
For the purpose of Multiple OLSR Interfaces, the following terminol-
ogy is introduced or refined:
Multiple Interface Node
A node which has multiple interfaces, participating in an
OLSR routing domain.
Single Interface Node
A node which has a single interface, participating in an
OLSR routing domain.
Notice, that both a "Multiple Interface Node" and a "Single Interface
Node" may have additional interfaces, not participating in the OLSR
routing domain. Integrating information from these non OLSR inter-
faces is described in section 8.
Main Address
The main address of a node, which will be used in OLSR
control traffic as the "originator address" of all mes-
sages emitted by this node. It is the address of one of
the interfaces of the node.
A multiple interface node MUST choose one of its inter-
face addresses as its "main address". It is of no impor-
tance which address is chosen, however a node SHOULD
always use the same address as its main address.
7.2. Multiple Interface Functioning
A node with multiple interfaces functions like a node with a single
interface, i.e. through performing link-sensing, neighbor- and 2-hop
neighbor detection, MPR selection and signaling, diffusion of topol-
ogy control messages and route calculation.
This section outlines the few additional provisions which must be
made to accommodate for multiple interfaces in OLSR.
Packet Sequence Number
The Packet Sequence Number (PSN), is now maintained per inter-
face. Each interface has its own PSN, which is put in the
packet header as specified in section 3.3.1, and incre-
mented each time a packet is sent on this interface.
Link Sensing
Link Sensing is accomplished through periodic emission of
HELLO messages over the interfaces through which connectivity
is checked. A separate HELLO message is generated per inter-
face and emitted in correspondence with the provisions in sec-
tion 4.4.
Resulting from Link Sensing is a local link set, describing
links between "local interfaces" and "remote interfaces" -
i.e. interfaces on neighbor nodes.
Neighbor detection
Given a network with only single interface nodes, a node may
deduct the neighbor set directly from the information
exchanged as part of link sensing: the "main address" of a
single interface node is, by definition, the address of the
only interface on that node.
In a network with multiple interface nodes, additional infor-
mation is required in order to map interface addresses to main
addresses (and, thereby, to nodes). This additional informa-
tion is acquired through multiple interface declaration (MID)
messages, as described in section 7.3
Thus, in the presence of multiple interfaces, the neighbor set
MUST be computed based on the information acquired through
HELLO messages and MID messages, as described in section
7.5.
MPR Selection and MPR Signaling
The objective of MPR selection is for a node to select a sub-
set of its neighbors such that a broadcasted message, retrans-
mitted by these select neighbors, will be received by all
nodes 2 hops away. A node will thus compute its MPR set such
that it, for each interface, satisfies this condition. This is
detailed in section 7.6.
MPR signaling is provided in correspondence with the provi-
sions in the previous section 4.3.
Topology Control Message Diffusion
Topology Control messages are diffused in correspondence with
the provisions in the previous section 5.5
Route Calculation
Multiple interfaces per node corresponds, effectively, to mul-
tiple network destinations per node. Hence, the interface
association informations acquired through the multiple inter-
face declaration messages must be taken into account when pop-
ulating the routing table. This is detailed in section
7.7
7.3. Multiple Interface Declaration
Each node with multiple interfaces MUST announce, periodically,
information describing its interface configuration to other nodes in
the network. This is accomplished through flooding a Multiple Inter-
face Declaration message to all nodes in the network through the MPR
flooding mechanism.
Each node in the network maintains interface information about the
other nodes in the network. This information acquired from MID-mes-
sages, emitted by nodes with multiple interfaces participating in the
MANET, and is used for routing table calculations.
Specifically, multiple interface declaration associates multiple
interfaces to a node (and to a main address) through populating the
multiple interface association base in each node.
7.3.1. Multiple Interface Association Information Base
For each destination in the network, "Interface association Tuples"
(I_iface_addr, I_main_addr, I_time) are recorded. I_iface_addr is an
interface address of a node, I_main_addr is the main address of this
node. I_time specifies the time at which this tuple expires and
*MUST* be removed.
In a node, the set of Interface association Tuples is denoted the
"Interface association Set".
7.3.2. MID Message Format
The proposed format of a MID message is
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This is sent as the data-portion of the general packet format
described in section 3.4, with the "Message Type" set to
MID_MESSAGE. The time to live SHOULD be set to 255 (maximum value) to
diffuse the message into the entire network and Vtime set accordingly
to the value of MID_HOLD_TIME, as specified in section 15.3.
Interface Address
This field contains the address of an interface of the node
other than its main address (which already indicated in the
originator address).
All interface addresses other than the main address of the Originator
node are put in the MID message. If the maximum allowed message size
(as imposed by the network) is reached while there are still inter-
face addresses which have not been inserted into the MID-message,
more MID messages are generated until the entire interface addresses
set has been sent.
7.3.3. MID Message Generation
A MID message is sent by a node in the network to declare its multi-
ple interfaces (if any). I.e., the MID message contains the list of
interface addresses which are associated to its main address. The
list of addresses can be partial in each MID message (e.g. due to
message size limitations, imposed by the network), but parsing of all
MID messages describing the interface set from a node MUST be com-
plete within a certain refreshing period (MID_INTERVAL). The informa-
tion diffused in the network by these MID messages will help each
node to calculate its routing table. A node which has only a single
interface address participating in the MANET (i.e. running OLSR),
MUST NOT generate any MID message.
A node with more interfaces, where only one is participating in the
MANET and running OLSR (e.g. a node is connected to a wired network
as well as to a MANET) MUST NOT generate any MID messages.
7.3.4. MID Message Forwarding
MID messages are broadcasted and retransmitted by the MPRs in order
to diffuse the messages in the entire network. The "default forward-
ing algorithm" (described in section 3.4.1) MUST be used
for forwarding of MID messages.
7.3.5. MID Message Processing
The tuples in the multiple interface association set are recorded
with the information that is exchanged through MID messages.
Upon receiving a MID message, the "validity time" MUST be computed
from the Vtime field of the message header (as described in the sec-
tion 4.2). The Multiple Interface Association Informa-
tion Base SHOULD then be updated as follows:
For each interface address listed in the MID message:
1 If there exist some tuple in the interface association
set where:
I_iface_addr == interface address, AND
I_main_addr == originator address,
then the holding time of that tuple is set to:
I_time = current time + validity time.
2 Otherwise, a new tuple is recorded in the interface asso-
ciation set where:
I_iface_addr = interface address,
I_main_addr = originator address,
I_time = current time + validity time.
7.4. Main Addresses vs. Interface Addresses
In general, the only part of OLSR concerning "interface addresses" is
link sensing. The remaining parts of OLSR operates on nodes, uniquely
identified by their "main addresses" (effectively, the main address
of a node is its "node id" - which for convenience corresponds to the
address of one of its interfaces). In a network with only single
interface nodes, the main address of a node will, by definition, be
equal to the interface address of the node. In networks with multiple
interface nodes, it is required to be able to map any interface
address to the corresponding main address.
Section 7.3 provides a way in which interface information is
acquired by nodes in the network. This permits identification of a
nodes "main address", given one of its interface addresses.
Given an interface address:
1 if there exists some tuple in the interface association set
where:
I_iface_addr == interface address
then the result of the main address search is the originator
address I_main_addr of the tuple.
2 Otherwise, the result of the main address search is the inter-
face address itself.
7.5. Populating the Neighbor Set
The Neighbor Set is populated in accordance with the provisions in
section 4.4, with the precision that for each interface
address, the corresponding Main Address for creating the neighbor
tuple is obtained through the mechanism described in section
7.4 and inserted into the Neighbor Set.
7.6. Populating the MPR Set
The MPR set MUST be calculated by a node in such a way that it,
through the neighbors in the MPR-set, can reach all symmetric strict
2-hop neighbors.
For the purpose of computing the MPR set in a node with multiple
interfaces, the following additional definitions are required:
neighbor of an interface
a node is a "neighbor of an interface" if the interface
(on the local node) has a link to any one interface of
the neighbor node.
two-hop neighbors reachable from an interface
the list of two-hop neighbors of the node that can be
reached from neighbors of this interface.
MPR set of an interface
A (sub)set of the neighbors of an interface, selected
such that through these selected nodes, all two-hop
neighbors reachable from that interface are reachable.
7.6.1. MPR Computation
The heuristics, proposed in section 4.6.2, is applied, with the
following changes:
- The algorithm is applied per interface I.
- N is now defined as "The subset of neighbors of the node,
which are neighbor of the interface I".
- N2 is now defined as "The set of two-hop neighbors reachable
from the interface I, excluding:
(i) the nodes only reachable by members of N with willingness
WILL_NEVER
(ii) the node performing the computation
(iii)
all the symmetric neighbors: the nodes for which there
exists a symmetric link to this node on some interface."
The MPR set of a node is then the union of the MPR sets found for
each interface.
Note that other algorithms and improvements are possible. For exam-
ple, when the MPRs of the first m interfaces have already been iden-
tified, for each of them which is also neighbor of the (m+1)th inter-
face, it is possible to ignore its two-hop neighbors (i.e. it is
assumed to be chosen as MPR again by the (m+1)th interface 'for
free').
7.7. Routing Table Calculation
A multiple interface compliant implementation MUST complement further
the routing table using the multiple interface association set, after
it has been (re)calculated:
1 For each entry in the multiple interface association base
where there exists a routing entry such that:
R_dest_addr == I_main_addr (of the multiple interface
interface association entry)
a route entry is created in the routing table with:
R_dest_addr = I_iface_addr (of the multiple interface
association entry)
R_next_addr = R_next_addr (of the recorded route entry)
R_dist = R_dist (of the recorded route entry)
R_iface_addr = R_iface_addr (of the recorded route
entry).
In addition, now, the routing table is updated by recalculating also
when the multiple interface association set has changed.
7.8. Changes to the "Default Forwarding Algorithm"
When a node as several interfaces, both the "Forwarding condition" of
section 3.4 (step 4.1), and the "default forwarding algo-
rithm" described previously in section 3.4.1 MUST be
changed.
The Forwarding condition of section 3.4 (step 4.1) MUST be
changed for all messages to the following:
4 Forwarding condition:
4.1 if there exists a tuple in the duplicate set, where:
D_addr == Originator Address, AND
D_seq_num == Message Sequence Number,
AND
the sender interface address is in
D_interface_list
then the message has already been considered for forward-
ing and SHOULD NOT be retransmitted again.
4.2 Otherwise: do as specified before in step 4.2 in section
3.4 ...
Additionality, the "default forwarding algorithm" described previ-
ously in section 3.4.1 MUST be changed. This change
applies to unknown message types, but also to all known messages
which are explicitly documented to use the "default forwarding algo-
rithm" in this specification.
First two new fields must be added to the duplicate set:
D_retransmitted
A boolean indicating whether the message has been already
retransmitted.
D_interface_list
A list of the addresses of the interfaces on which the message
has been received.
The multiple interface default forwarding algorithm is the following:
1 If the sender interface address of the message is not detected
to be in the symmetric neighborhood of the node, the forward-
ing algorithm MUST silently stop here (and the message will
not be forwarded).
2 If an entry exists in the duplicate set with:
D_addr = originator address
D_seq_num = Message Sequence Number
Then the message will be further considered for forwarding if
and only if:
D_retransmitted is false
and the (address of the) interface which received the
message isn't in D_interface_list
3 Otherwise, if such an entry doesn't exist, the message is fur-
ther considered for forwarding.
If after those steps, the message is not considered for forwarding,
then the processing of this section stops (i.e. steps 4 to 7 are
ignored), otherwise, if it is still considered for forwarding then
the following algorithm is used:
4 If the sender interface address is an interface address of a
MPR selector of this node and if the time to live of the mes-
sage is greater than '1', the message MUST be retransmitted
(as described later).
5 If entry in the duplicate set exists, with same originator
address, and same message sequence number
Then it is updated:
D_time = current time + D_HOLD_TIME.
The receiving interface address is added to D_inter-
face_list.
D_retransmitted is set to true if and only if the message
will be retransmitted according to step 4.
Otherwise an entry in the duplicate set is recorded with:
D_addr = originator address
D_seq_num = Message Sequence Number
D_time = current time + D_HOLD_TIME.
D_interface_list contains the receiving interface
address.
D_retransmitted is set to true if and only if the message
will be retransmitted according to step 4.
If, and only if, according to step 4, the message must be retransmit-
ted then the following steps are followed:
5 The TTL of the message is reduced by one.
6 The hop-count of the message is increased by one
7 The message is broadcasted on all interfaces (Notice: The
remaining fields of the message header SHOULD be left unmodi-
fied.)
8. Non OLSR Interfaces
A node MAY be equipped with multiple interfaces, some of which do not A node MAY be equipped with multiple interfaces, some of which do not
participate in the OLSR manet. These non-OLSR interfaces may be point participate in the OLSR MANET. These non-OLSR interfaces may be
to point connections to other singular hosts or may connect to sepa- point to point connections to other singular hosts or may connect to
rate networks. separate networks.
In order to provide connectivity from the OLSR manet interface(s) to In order to provide connectivity from the OLSR MANET interface(s) to
these non-OLSR interface(s), a node SHOULD be able to inject external these non-OLSR interface(s), a node SHOULD be able to inject external
route information to the OLSR manet. route information to the OLSR MANET.
Injecting routing information from the OLSR manet to non-OLSR inter- Injecting routing information from the OLSR MANET to non-OLSR inter-
faces is outside the scope of this specification. It should be clear, faces is outside the scope of this specification. It should be
however, that the routing information for the OLSR manet can be clear, however, that the routing information for the OLSR MANET can
extracted from the topology table (see section 5.2) or directly be extracted from the topology table (see section 4.4) or
from the routing table of OLSR, and must be injected onto the non- directly from the routing table of OLSR, and SHOULD be injected onto
OLSR interfaces following whatever mechanism (routing protocol, the non-OLSR interfaces following whatever mechanism (routing proto-
static configuration etc.) is provided on these interfaces. col, static configuration etc.) is provided on these interfaces.
An example of such a situation could be where a node is equipped with An example of such a situation could be where a node is equipped with
a fixed network (e.g. an Ethernet) connecting to a larger network a fixed network (e.g. an Ethernet) connecting to a larger network
running, as well as a wireless network interface running OLSR. running, as well as a wireless network interface running OLSR.
Notice that this is a different case from that of "multiple inter- Notice that this is a different case from that of "multiple inter-
faces", where all the interfaces are participating in the MANET faces", where all the interfaces are participating in the MANET
through running the OLSR protocol. Multiple interfaces participating through running the OLSR protocol.
in the OLSR manet is described in section 7.
In order to provide this capability of injecting external routing In order to provide this capability of injecting external routing
information into an OLSR manet, a node with such non-MANET interfaces information into an OLSR MANET, a node with such non-MANET interfaces
periodically issues an Host and Network Association (HNA) message, periodically issues a Host and Network Association (HNA) message,
containing sufficient information for the recipients to construct an containing sufficient information for the recipients to construct an
appropriate routing table. appropriate routing table.
8.1. HNA Message Format 12.1. HNA Message Format
The proposed format of an HNA-message is: The proposed format of an HNA-message is:
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Network Address | | Network Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Netmask | | Netmask |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
skipping to change at page 56, line 18 skipping to change at page 56, line 24
| Network Address | | Network Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Netmask | | Netmask |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Network Address | | Network Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Netmask | | Netmask |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... | | ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This is sent as the data part of the general packet format with the This is sent as the data part of the general packet format with the
"Message Type" set to HNA_MESSAGE, the TTL field set to 255 and Vtime "Message Type" set to HNA_MESSAGE, the TTL field set to 255 and Vtime
set accordingly to the value of HNA_HOLD_TIME, as specified in sec- set accordingly to the value of HNA_HOLD_TIME, as specified in sec-
tion 15.3. tion 18.3.
It should be noticed, that the HNA-message can be considered as a
"generalized version" of the TC-message: the originator of both the
HNA- and TC-messages announce "reachability" to some other host(s).
In the TC-message, no netmask is required, since all reachability is
announced on a per-host basis. In HNA-messages, announcing reachabil-
ity to an address sequence through a network- and netmask address is
typically preferred over announcing reachability to individual host
addresses.
An important difference between TC- and HNA-messages is, that a TC
message may have a cancelling effect on previous information (if the
MSSN is incremented), whereas information in HNA-messages is removed
only upon expiration.
Network Address Network Address
The network address of the associated network The network address of the associated network
Netmask Netmask
The netmask, corresponding to the network address immediately The netmask, corresponding to the network address immediately
above. above.
8.2. Host and Network Association Information Base 12.2. Host and Network Association Information Base
Each node maintains information concerning which nodes may act as Each node maintains information concerning which nodes may act as
"gateways" to associated hosts and networks by recording "association "gateways" to associated hosts and networks by recording "association
tuples" (A_gateway_addr, A_network_addr, A_netmask, A_time), where tuples" (A_gateway_addr, A_network_addr, A_netmask, A_time), where
A_gateway_addr is the address of a OLSR interface of the gateway, A_gateway_addr is the address of a OLSR interface of the gateway,
A_network_addr and A_netmask specifies the network address and net- A_network_addr and A_netmask specify the network address and netmask
mask of a network, reachable through this gateway, and A_time speci- of a network, reachable through this gateway, and A_time specifies
fies the time at which this tuple expires and hence *MUST* be the time at which this tuple expires and hence *MUST* be removed.
removed.
The set of all association tuples in a node is called the "associa- The set of all association tuples in a node is called the "associa-
tion set". tion set".
8.3. HNA Message Generation It should be noticed, that the HNA-message can be considered as a
"generalized version" of the TC-message: the originator of both the
HNA- and TC-messages announce "reachability" to some other host(s).
In the TC-message, no netmask is required, since all reachability is
announced on a per-host basis. In HNA-messages, announcing reacha-
bility to an address sequence through a network- and netmask address
is typically preferred over announcing reachability to individual
host addresses.
An important difference between TC- and HNA-messages is, that a TC
message may have a canceling effect on previous information (if the
ANSN is incremented), whereas information in HNA-messages is removed
only upon expiration.
12.3. HNA Message Generation
A node with associated hosts and/or networks SHOULD periodically gen- A node with associated hosts and/or networks SHOULD periodically gen-
erate a Host and Network Association (HNA) message, containing pairs erate a Host and Network Association (HNA) message, containing pairs
of (network address, netmask) corresponding to the connected hosts of (network address, netmask) corresponding to the connected hosts
and networks. HNA-messages SHOULD be transmitted periodically every and networks. HNA-messages SHOULD be transmitted periodically every
HNA_INTERVAL. The Vtime is set accordingly to the value of HNA_INTERVAL. The Vtime is set accordingly to the value of
HNA_HOLD_TIME, as specified in section 15.3. HNA_HOLD_TIME, as specified in section 18.3.
A node without any associated hosts and/or networks SHOULD NOT gener- A node without any associated hosts and/or networks SHOULD NOT gener-
ate HNA-messages. ate HNA-messages.
8.4. HNA Message Forwarding 12.4. HNA Message Forwarding
Upon receiving a HNA message, and thus following the rules of section Upon receiving a HNA message, and thus following the rules of section
3, in this version of the specification, the message MUST be 3, in this version of the specification, the message MUST be
forwarded according to section 3.4. forwarded according to section 3.4.
8.5. HNA Message Processing 12.5. HNA Message Processing
In this section, the term "originator address" is used to designate In this section, the term "originator address" is used to designate
the main address on the OLSR manet of the node which originally the main address on the OLSR MANET of the node which originally
issued the HNA-message. issued the HNA-message.
Upon processing a HNA-message, the "validity time" MUST be computed Upon processing a HNA-message, the "validity time" MUST be computed
from the Vtime field of the message header (see section 3.3.2). from the Vtime field of the message header (see section 3.3.2).
The association base SHOULD then be updated as follows: The association base SHOULD then be updated as follows:
1 For each (network address, netmask) pair in the message: 1 If the sender interface (NB: not originator) of this message
is not in the symmetric 1-hop neighborhood of this node, the
message MUST be discarded.
1.1 if an entry in the association set already exists, where: 2 Otherwise, for each (network address, netmask) pair in the
message:
2.1 if an entry in the association set already exists, where:
A_gateway_addr == originator address A_gateway_addr == originator address
A_network_addr == network address A_network_addr == network address
A_netmask == netmask A_netmask == netmask
then the holding time for that tuple MUST be set to: then the holding time for that tuple MUST be set to:
A_time = current time + validity time A_time = current time + validity time
1.2 otherwise, a new tuple MUST be recorded with: 2.2 otherwise, a new tuple MUST be recorded with:
A_gateway_addr = originator address A_gateway_addr = originator address
A_network_addr = network address A_network_addr = network address
A_netmask = netmask A_netmask = netmask
A_time = current time + validity time A_time = current time + validity time
8.6. Routing Table Calculation 12.6. Routing Table Calculation
In addition to the routing table computation as described in section In addition to the routing table computation as described in section
5.7, the host and network association set MUST be added as 10, the host and network association set MUST be added as
follows: follows:
1 For each tuple in the routing set, an entry in the routing For each tuple in the association set,
table MUST be recorded, with:
1 If there is no entry in the routing table with:
R_dest_addr == A_network_addr/A_netmask
then a new routing entry is created is created.
2 If a new routing entry was created at the previous step, or
else if there existed one with:
R_dest_addr == A_network_addr/A_netmask
R_dist > dist to A_gateway_addr of
current association set tuple,
then the routing entry is modified as follows:
R_dest_addr = A_network_addr/A_netmask R_dest_addr = A_network_addr/A_netmask
R_next_addr = the next hop on the path from the node R_next_addr = the next hop on the path
to A_gateway_addr from the node to A_gateway_addr
R_dist = dist to A_gateway_addr R_dist = dist to A_gateway_addr
R_next_addr and R_iface_addr MUST be set to the same val- R_next_addr and R_iface_addr MUST be set to the same val-
ues as the tuple from the routing set with R_dest_addr == ues as the tuple from the routing set with R_dest_addr ==
A_gateway_addr. A_gateway_addr.
9. Link Layer Notification 12.7. Interoperability Considerations
Nodes, which do not implement support for non-OLSR interfaces, can
coexist in a network with nodes which do implement support for non-
OLSR interfaces: the generic packet format and message forwarding
(section 3) ensures that HNA messages are correctly for-
warded by all nodes . Nodes which implement support for non-OLSR
interfaces may thus transmit and process HNA messages according to
this section.
Nodes, which do not implement support for non-OLSR interfaces can not
take advantage of the functionality specified in this section, how-
ever will forward HNA messages correctly, as specified in section
3.
13. Link Layer Notification
OLSR is designed not to impose or expect any specific information OLSR is designed not to impose or expect any specific information
from the link layer. However, if information from the link-layer is from the link layer. However, if information from the link-layer
available, a node MAY use this as described in this section. describing link breakage is available, a node MAY use this as
described in this section.
If link layer information describing connectivity to neighboring If link layer information describing connectivity to neighboring
nodes is available (i.e. loss of connectivity such as through absence nodes is available (i.e. loss of connectivity such as through
of a link layer acknowledgment), this information is used in addition absence of a link layer acknowledgment), this information is used in
to the information from the HELLO-messages to maintain the neighbor addition to the information from the HELLO-messages to maintain the
information base and the MPR selector set. neighbor information base and the MPR selector set.
Thus, upon receiving a link-layer notification that the link between Thus, upon receiving a link-layer notification that the link between
a node and a neighbor interface is broken, the following actions are a node and a neighbor interface is broken, the following actions are
taken with respect to link sensing: taken with respect to link sensing:
Each link tuple in the local link set SHOULD, in addition to what is Each link tuple in the local link set SHOULD, in addition to what is
described in section 4.1, include a L_LOST_LINK_time field. described in section 4.2, include a L_LOST_LINK_time field.
L_LOST_LINK_time is a timer for declaring a link as lost when an L_LOST_LINK_time is a timer for declaring a link as lost when an
established link becomes pending. (Notice, that this is a subset of established link becomes pending. (Notice, that this is a subset of
what is reccomended in section 10.3, thus link hysteresis what is recommended in section 14, thus link hysteresis
and link layer notifications can coexist). and link layer notifications can coexist).
HELLO message generation should consider those new fields as follows: HELLO message generation should consider those new fields as follows:
1 if L_LOST_LINK_time is not expired, the link is advertised 1 if L_LOST_LINK_time is not expired, the link is advertised
with a link type of LOST_LINK and neighbor type NOT_NEIGH ; with a link type of LOST_LINK. In addition, it is not consid-
ered as a symmetrical link in the updates of the associated
neighbor tuple (see section 8.1).
1 if the link to a neighboring symmetric or asymmetric interface 2 if the link to a neighboring symmetric or asymmetric interface
is broken, the corresponding link tuple is modified: is broken, the corresponding link tuple is modified:
L_LOST_LINK_time and L_time are set to current time + L_LOST_LINK_time and L_time are set to current time +
NEIGHB_HOLD_TIME. NEIGHB_HOLD_TIME.
2 this is considered as a link loss and the appropriate process- 3 this is considered as a link loss and the appropriate process-
ing described in section 4.8 should be performed. ing described in section 8.5 should be performed.
10. Link Hysteresis 13.1. Interoperability Considerations
Link layer notifications provide, for a node, an additional criterion
by which a node may determine if a link to a neighbor node is lost.
Once a link is detected as lost, it is advertised, in accordance with
the provisions described in the previous sections of this specifica-
tion.
14. Link Hysteresis
Established links should be as reliable as possible to avoid data Established links should be as reliable as possible to avoid data
packet loss. To enhance the reliability of the link sensing mecha- packet loss. This implies that link sensing should be robust against
nism, the following implementation recommendations should be consid- bursty loss or transient connectivity between nodes. Hence, to
ered. enhance the robustness of the link sensing mechanism, the following
implementation recommendations SHOULD be considered.
10.1. Local Link Set 14.1. Local Link Set
Each link tuple in the local link set SHOULD, in addition to what is Each link tuple in the local link set SHOULD, in addition to what is
described in section 4.1, include a L_link_pending field, a described in section 4.2, include a L_link_pending field, a
L_link_quality field, and a L_LOST_LINK_time field. L_link_pending L_link_quality field, and a L_LOST_LINK_time field. L_link_pending
is a boolean value specifying if the link is considered pending (i.e. is a boolean value specifying if the link is considered pending (i.e.
the link is not considered established). L_link_quality is a dimen- the link is not considered established). L_link_quality is a dimen-
sionless number between 0 and 1 describing the quality of the link. sionless 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 L_LOST_LINK_time is a timer for declaring a link as lost when an
established link becomes pending. established link becomes pending.
10.2. Hello Message Generation 14.2. Hello Message Generation
HELLO message generation should consider those new fields as follows: HELLO message generation should consider those new fields as follows:
1 if L_LOST_LINK_time is not expired, the link is advertised 1 if L_LOST_LINK_time is not expired, the link is advertised
with a link type of LOST_LINK and neighbor type NOT_NEIGH ; with a link type of LOST_LINK.
2 otherwise, if L_LOST_LINK_time is expired and L_link_pending 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; 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 3 otherwise, if L_LOST_LINK_time is expired and L_link_pending
is set to "false", the link is advertised as described previ- is set to "false", the link is advertised as described previ-
ously in section 4. ously in section 6.
A node considers that it has a symmetric link for each link tuple A node considers that it has a symmetric link for each link tuple
where where:
1 L_LOST_LINK_time is expired, AND 1 L_LOST_LINK_time is expired, AND
2 L_link_pending is "false", AND 2 L_link_pending is "false", AND
3 L_SYM_time is not expired. 3 L_SYM_time is not expired.
This should be taken as definition for computing the symmetric neigh- This definition for "symmetric link" SHOULD be used the updates of
borhood when computing the MPR set. This should also be taken as the the associated neighbor tuple (see section 8.1) for computing
definition of "the symmetric neighbors" in the first steps of the the N_status of a neighbor node. This definition SHOULD thereby also
routing table calculation. be used as basis for the symmetric neighborhood when computing the
MPR set, as well as for "the symmetric neighbors" in the first steps
of the routing table calculation.
Apart from the above points, what has been described previously does Apart from the above, what has been described previously does not
not interfere with these advanced link sensing fields in the link interfere with the advanced link sensing fields in the link tuples.
tuples. The L_link_quality, L_link_pending and L_LOST_LINK_time The L_link_quality, L_link_pending and L_LOST_LINK_time fields are
fields are exclusively updated according to the present section. This exclusively updated according to the present section. This section
section does not modify the function of any other fields in the link does not modify the function of any other fields in the link tuples.
tuples.
10.3. Hysteresis Strategy 14.3. Hysteresis Strategy
The link between a node and some of its neighbor interfaces might be 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 "bad", i.e. from time to time let HELLOs pass through only to fade
out immediately after. In this case, the neighbor information base out immediately after. In this case, the neighbor information base
would contain a bad link for at least NEIGHB_HOLD_TIME. In absence of would contain a bad link for at least "validity time". The following
link layer notification, such a bad link might affect routing badly. hysteresis strategy SHOULD be adopted to counter this situation.
To cope with such unstable links, the following hysteresis strategy
SHOULD be adopted.
For each neighbor interface NI heard by interface I, the L_link_qual- For each neighbor interface NI heard by interface I, the L_link_qual-
ity field of the corresponding Link Tuple determines the establish- ity field of the corresponding Link Tuple determines the establish-
ment of the link. The value of L_link_quality is compared to two ment of the link. The value of L_link_quality is compared to two
thresholds HYST_THRESHOLD_HIGH, HYST_THRESHOLD_LOW, fixed between 0 thresholds HYST_THRESHOLD_HIGH, HYST_THRESHOLD_LOW, fixed between 0
and 1 and such that HYST_THRESHOLD_HIGH >= HYST_THRESHOLD_LOW. and 1 and such that HYST_THRESHOLD_HIGH >= HYST_THRESHOLD_LOW.
The L_link_pending field is set according to the following: The L_link_pending field is set according to the following:
1 if L_link_quality > HYST_THRESHOLD_HIGH: 1 if L_link_quality > HYST_THRESHOLD_HIGH:
skipping to change at page 61, line 37 skipping to change at page 62, line 39
L_LOST_LINK_time = current time - 1 (expired) L_LOST_LINK_time = current time - 1 (expired)
2 otherwise, if L_link_quality < HYST_THRESHOLD_LOW: 2 otherwise, if L_link_quality < HYST_THRESHOLD_LOW:
L_link_pending = true L_link_pending = true
L_LOST_LINK_time = min (L_time, current time + L_LOST_LINK_time = min (L_time, current time +
NEIGHB_HOLD_TIME) NEIGHB_HOLD_TIME)
(the link is then considered as lost according to section (the link is then considered as lost according to section
4.8 and this may produce a neighbor loss). 8.5 and this may produce a neighbor loss).
3 otherwise, if HYST_THRESHOLD_LOW <= L_link_quality <= 3 otherwise, if HYST_THRESHOLD_LOW <= L_link_quality
HYST_THRESHOLD_HIGH: <= HYST_THRESHOLD_HIGH:
L_link_pending and L_LOST_LINK_time remain unchanged. L_link_pending and L_LOST_LINK_time remain unchanged.
The condition for considering a link established is thus stricter The condition for considering a link established is thus stricter
than the condition for loosing it. than the condition for dropping a link. Notice thus, that a link can
be dropped based on either timer expiration (as described in section
7) 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 (as described in section 7). Specif-
ically, this implies that, regardless of whether or not the link hys-
teresis considers a link as "established", 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 As a basic implementation requirement, an estimation of the link
quality must be maintained and stored in the L_link_quality field. If quality must be maintained and stored in the L_link_quality field.
some measure of the signal/noise level on a received message is If some measure of the signal/noise level on a received message is
available (e.g. as a link layer notification), then it can be used as available (e.g. as a link layer notification), then it can be used
estimation after normalization. as estimation after normalization.
If no signal/noise information is available from the link layer, an If no signal/noise information or other link quality information is
algorithm such as the following can be utilized (it is an exponen- available from the link layer, an algorithm such as the following can
tially smoothed moving average of the transmission success rate). be utilized (it is an exponentially smoothed moving average of the
The algorithm is parameterized by a scaling parameter HYST_SCALING transmission success rate). The algorithm is parameterized by a
which is a number fixed between 0 and 1. For each neighbor interface scaling parameter HYST_SCALING which is a number fixed between 0 and
NI heard by interface I, the first time NI is heard by I, 1. For each neighbor interface NI heard by interface I, the first
L_link_quality is set to HYST_SCALING (L_link_pending is set to true time NI is heard by I, L_link_quality is set to HYST_SCALING
and L_LOST_LINK_time to current time - 1). (L_link_pending is set to true and L_LOST_LINK_time to current time -
1).
A tuple is updated according to two rules. Every time an OLSR packet 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: emitted by NI is received by I, the stability rule is applied:
L_link_quality = (1-HYST_SCALING)*L_link_quality + HYST_SCAL- L_link_quality = (1-HYST_SCALING)*L_link_quality
ING. + HYST_SCALING.
When an OLSR packet emitted by NI is lost by I, the instability When an OLSR packet emitted by NI is lost by I, the instability
rule is applied: rule is applied:
L_link_quality = (1-HYST_SCALING)*L_link_quality. L_link_quality = (1-HYST_SCALING)*L_link_quality.
The loss of OLSR packet is detected by tracking the missing Packet The loss of OLSR packet is detected by tracking the missing Packet
Sequence Numbers on a per interface basis and by long period of Sequence Numbers on a per interface basis and by "long period of
silence. If no OLSR packet has been received on interface I from silence" from a node. A "long period of silence may be detected
interface NI during hello emission interval of interface NI (computed thus: if no OLSR packet has been received on interface I from inter-
from the Htime field in the last hello message received from NI), a face NI during HELLO emission interval of interface NI (computed from
loss of an OLSR packet is detected. the Htime field in the last HELLO message received from NI), a loss
of an OLSR packet is detected.
11. Distributing Redundant Topology Information 14.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 e.g. the nature of the media
over which they are communicating. Once a link is accepted, it is
advertised, in accordance with the provisions described in the previ-
ous sections of this specification.
15. Redundant Topology Information
In order to provide redundancy to topology information base, the In order to provide redundancy to topology information base, the
advertised link set of a node can contain links to neighbor nodes advertised link set of a node MAY contain links to neighbor nodes
which are not in MPR selector set of the node. The advertised link which are not in MPR selector set of the node. The advertised link
set can be the whole neighbor set of the node. In this case the nodes set MAY contain links to the whole neighbor set of the node. The
receiving the TC message will get the knowledge of all the adjacent minimal set of links that any node MUST advertise in its TC messages
links of the sender node. The advertised link set can be built is the links to the nodes MPR selectors. The advertised link set can
according to the following rule based on a local parameter called be built according to the following rule based on a local parameter
TC_REDUNDANCY parameter. called TC_REDUNDANCY parameter.
11.1. TC_REDUNDANCY Parameter 15.1. TC_REDUNDANCY Parameter
The parameter TC_REDUNDANCY specifies, for the local node, the amount The parameter TC_REDUNDANCY specifies, for the local node, the amount
of information that is included in the TC messages. The parameter is of information that MAY be included in the TC messages. The parame-
interpreted as follows: ter SHOULD be interpreted as follows:
- if the TC_REDUNDANCY parameter of the node is 0, then its - if the TC_REDUNDANCY parameter of the node is 0, then the
advertised link set is limited to the MPR selector set (as advertised link set of the node set is limited to the MPR
described in section 4.6.2), selector set (as described in section 8.3),
- if the TC_REDUNDANCY parameter of the node is 1, then its - if the TC_REDUNDANCY parameter of the node is 1, then the
advertised set is the union of its MPR set and its MPR selec- advertised link set of the node is the union of its MPR set
tor set, and its MPR selector set,
- if the TC_REDUNDANCY parameter of the node is 2, then its - if the TC_REDUNDANCY parameter of the node is 2, then the
advertised set is neighbor set (full link-state information is advertised link set of the node is the full neighbor link set.
diffused).
A node with willingness equal to zero SHOULD have TC_REDUNDANCY also A node with willingness equal to WILL_NEVER SHOULD have TC_REDUNDANCY
equal to zero. also equal to zero.
12. MPR Redundancy 15.2. Interoperability Considerations
A TC message is sent by a node in the network to declare a set of
links, called advertised link set which MUST include at least the
links to all nodes of its MPR Selector set, i.e., the neighbors which
have selected the sender node as a MPR. This is sufficient informa-
tion to ensure that routes can be computed in accordance with section
10.
The provisions in this section specifies how additional information
may be declared, as specified through a TC_REDUNDANCY parameter.
TC_REDUNDANCY = 0 implies that the information declared corresponds
exactly to the MPR Selector set, identical to section 9. Other
values of TC_REDUNDANCY specifies additional information to be
declared, i.e. the contents of the MPR Selector set is always
declared. Thus, nodes with different values of TC_REDUNDANCY may
coexist in a network: control messages are carried by all nodes in
accordance with section 3, and all nodes will receive at
least the link-state information required to construct routes as
described in section 10.
16. MPR Redundancy
MPR redundancy specifies the ability for a node to select redundant MPR redundancy specifies the ability for a node to select redundant
MPRs. Section 4.5 specifies that a node should select its MPR set to MPRs. Section 4.5 specifies that a node should select its MPR set to
be as small as possible, in order to reduce protocol overhead. The be as small as possible, in order to reduce protocol overhead. The
criteria for selecting MPRs being, that all strict 2-hop nodes must criteria for selecting MPRs is, that all strict 2-hop nodes must be
be reachable through, at least, one MPR node. Redundancy of the MPR reachable through, at least, one MPR node. Redundancy of the MPR set
set affects the overhead through affecting the amount of links being affects the overhead through affecting the amount of links being
advertised, the amount of nodes advertising links to the MPR selector advertised, the amount of nodes advertising links and the efficiency
and the efficiency of the MPR flooding mechanism. On the other hand, of the MPR flooding mechanism. On the other hand, redundancy in the
redundancy in the MPR set ensures that reachability for a node is MPR set ensures that reachability for a node is advertised by more
advertised by more nodes, thus additional links are diffused to the nodes, thus additional links are diffused to the network.
network.
While, in general, a minimal MPR set provides the least overhead, While, in general, a minimal MPR set provides the least overhead,
there are situations in which overhead can be traded off for other there are situations in which overhead can be traded off for other
benefits. E.g. a node can may decide to increase its MPR coverage if benefits. E.g. a node can may decide to increase its MPR coverage
it observes many changes in its neighbor information base caused by if it observes many changes in its neighbor information base caused
mobility, while otherwise keeping a low MPR coverage. by mobility, while otherwise keeping a low MPR coverage.
12.1. MPR_COVERAGE Parameter 16.1. MPR_COVERAGE Parameter
The MPR coverage is defined by a single local parameter, MPR_COVER- The MPR coverage is defined by a single local parameter, MPR_COVER-
AGE, specifying by how many MPR nodes any strict 2-hop node should be AGE, specifying by how many MPR nodes any strict 2-hop node should be
covered. MPR_COVERAGE=1 specifies that the overhead of the protocol covered. MPR_COVERAGE=1 specifies that the overhead of the protocol
is kept at a minimum and causes the MPR selection to operate as is kept at a minimum and causes the MPR selection to operate as
described in section 4.6.3. MPR_COVERAGE=m ensures that, if described in section 8.3.1. MPR_COVERAGE=m ensures that, if
possible, a node selects its MPR set such that all strict 2-hop nodes possible, a node selects its MPR set such that all strict 2-hop nodes
are reachable through at least m MPR nodes. for an interface are reachable through at least m MPR nodes on that
interface. MPR_COVERAGE can assume any integer value > 0. The
heuristic MUST be applied per interface, I. The MPR set for a node
is the union of the MPR sets found for each interface.
Notice that MPR_COVERAGE can be tuned locally without affecting the Notice that MPR_COVERAGE can be tuned locally without affecting the
consistency of the protocol. I.e. nodes in a network may operate with consistency of the protocol. I.e. nodes in a network may operate
different values of MPR_COVERAGE. with different values of MPR_COVERAGE.
12.2. MPR Computation 16.2. MPR Computation
Using MPR coverage, the MPR selection heuristics is extended from Using MPR coverage, the MPR selection heuristics is extended from
that described in the section 4.6.3 by one definition: that described in the section 8.3.1 by one definition:
Poorly covered node: Poorly covered node:
A poorly covered node is a node in N2 which is covered by less A poorly covered node is a node in N2 which is covered by less
than MPR_COVERAGE nodes in N. than MPR_COVERAGE nodes in N.
The proposed heuristic for selecting MPRs is then as follows: The proposed heuristic for selecting MPRs is then as follows:
1 Start with an MPR set made of all members of N with willing- 1 Start with an MPR set made of all members of N with willing-
ness equal to WILL_ALWAYS ness equal to WILL_ALWAYS
2 Calculate D(y), where y is a member of N, for all nodes in N. 2 Calculate D(y), where y is a member of N, for all nodes in N.
skipping to change at page 64, line 33 skipping to change at page 67, line 4
nodes in N2. The nodes are then removed from N2 for the rest nodes in N2. The nodes are then removed from N2 for the rest
of the computation. of the computation.
4 While there exist nodes in N2 which are not covered by at 4 While there exist nodes in N2 which are not covered by at
least MPR_COVERAGE nodes in the MPR set: least MPR_COVERAGE nodes in the MPR set:
4.1 For each node in N, calculate the reachability, i.e. the 4.1 For each node in N, calculate the reachability, i.e. the
number of nodes in N2 which are not yet covered by at number of nodes in N2 which are not yet covered by at
least MPR_COVERAGE nodes in the MPR set, and which are least MPR_COVERAGE nodes in the MPR set, and which are
reachable through this one hop neighbor; reachable through this one hop neighbor;
4.2 Select as a MPR the node with highest willingness among 4.2 Select as a MPR the node with highest willingness among
the nodes in N with non-zero reachability. In case of the nodes in N with non-zero reachability. In case of
multiple choice select the node which provides reachabil- multiple choice select the node which provides reachabil-
ity to the maximum number of nodes in N2. In case of ity to the maximum number of nodes in N2. In case of
multiple nodes providing the same amount of reachability, multiple nodes providing the same amount of reachability,
select the node as MPR whose D(y) is greater. Remove the select the node as MPR whose D(y) is greater. Remove the
nodes from N2 which are now covered by MPR_COVERAGE nodes nodes from N2 which are now covered by MPR_COVERAGE nodes
in the MPR set. in the MPR set.
5 As an optimization, process each node y in the MPR set in the 5 A node's MPR set is generated from the union of the MPR sets
increasing order of their willingness. If all nodes in N2 are for each interface. As an optimization, process each node, y,
still covered by at least MPR_COVERAGE nodes in the MPR set in the MPR set in increasing order of N_willingness. If all
excluding y and willingness of node y is smaller than nodes in N2 are still covered by at least MPR_COVERAGE nodes
WILL_ALWAYS, then node y is removed from the MPR set. in the MPR set excluding node y, and if N_willingness of node
y is smaller than WILL_ALWAYS, then node y MAY be removed from
the MPR set.
When the MPR set has been computed, all the corresponding main When the MPR set has been computed, all the corresponding main
addresses are stored in the MPR Set. addresses are stored in the MPR Set.
Notice, that for MPR_COVERAGE=1, this heuristics is identical to the 16.3. Interoperability Considerations
heuristics specified in the section 4.6.3.
13. IPv6 Considerations
All the operations and parameters described in this document used by
OLSR for IP version 4 are the same as those used by OLSR for IP ver-
sion 6. However, to operate with IP version 6, the only required
change is to replace the IPv4 addresses with IPv6 address.
14. Security Considerations
Currently, OLSR does not specify any security measures. However as a
proactive routing protocol, it makes a target for various attacks.
The various possible vulnerability are discussed in this section.
14.1. Confidentiality
Being a proactive protocol, OLSR periodically diffuses topological
information. Hence, if used in an unprotected wireless network, the
network topology is revealed to anyone who listens to OLSR control
messages.
In situations where the confidentiality of the network topology is of
importance, regular cryptographic techniques can be applied to ensure
that control traffic can be read and interpreted by only those autho-
rized to do so.
14.2. Integrity
In OLSR, each node is injecting topological information into the net-
work through transmitting HELLO messages and, for some nodes, TC mes-
sages. If some nodes for some reason, malicious or malfunction,
injects invalid control traffic, network integrity may be compro-
mised.
Different such situations may occur:
1 a node generates TC (or HNA) messages, advertising links to
non-neighbor nodes:
2 a node generates TC (or HNA) messages, pretending to be
another node,
3 a node generate HELLO messages, advertising non-neighbor
nodes,
4 a node generate HELLO messages, pretending to be another node.
5 a node forwards altered control messages,
6 a node does not broadcast control messages,
7 a node does not select multipoint relays correctly.
8 a node forwards broadcast control messages unaltered, but does
not forward unicast data traffic
Authenticated signatures on control messages (for situation 2, 4 and
5) and on the individual links announced in the control messages (for
situation 1 and 3) may be used as a countermeasure. However to pre-
vent nodes from repeating old (and correctly authenticated) informa-
tion temporal information is required, allowing a node to positively
identify such delayed messages.
Signatures and other required security information may be transmitted The MPR set of a node MUST, according to section 8.3, be cal-
as a separate OLSR message type, thereby allowing that "secured" and culated by a node in such a way that it, through the neighbors in the
"unsecured" nodes can coexist in the same network, if desired. MPR-set, can reach all symmetric strict 2-hop neighbors. This is
achieved by the heuristics in this section, for all values of
MPR_COVERAGE > 0. MPR_COVERAGE is a local parameter for each node.
Setting this parameter affects only the amount of redundancy in part
of the network.
14.3. Interaction with External Routing Domains Notice that for MPR_COVERAGE=1, the heuristics in this section is
identical to the heuristics specified in the section 8.3.1.
OLSR does, through the HNA messages specified in section 8, Nodes with different values of MPR_COVERAGE may coexist in a network:
provide a basic mechanism for injecting external routing information control messages are carried by all nodes in accordance with section
to the OLSR domain. Section 8 also specifies that routing 3, and all nodes will receive at least the link-state infor-
information can be extracted from the topology table of OLSR and, mation required to construct routes as described in sections 9
potentially, injected into an external domain if the routing protocol and 10.
governing that domain permits.
Other than as described in the section 14.2, when operating 17. IPv6 Considerations
nodes, connecting OLSR to an external routing domain, care MUST be
taken not to allow potentially insecure and un-trustworthy informa-
tion to be injected from the OLSR domain to external routing domains.
I.e. a node MUST NOT take raw and invalidated information from the
OLSR topology tables and inject into any external routing domain.
Care MUST be taken to validate the correctness of information prior
to it being injected as to avoid polluting routing tables with
invalid information.
A recommended way of extending connectivity from an existing routing All the operations and parameters described in this document used by
domain to an OLSR routed manet is to assign an IP sequence (under the OLSR for IP version 4 are the same as those used by OLSR for IP ver-
authority of the nodes/gateways connecting the manet with the exiting sion 6. To operate with IP version 6, the only required change is to
routing domain) exclusively to the OLSR manet, and to configure the replace the IPv4 addresses with IPv6 address. The minimum packet and
gateways statically to advertise routes to that IP sequence to nodes message sizes (under which there is rejection) should be adjusted
in the existing routing domain. accordingly, considering the greater size of IPv6 addresses.
15. Proposed Values for Constants 18. Proposed Values for Constants
This section list the values for the constants used in the descrip- This section list the values for the constants used in the descrip-
tion of the protocol. tion of the protocol.
15.1. Setting emission intervals and holding times 18.1. Setting emission intervals and holding times
The proposed constant for C is the following: The proposed constant for C is the following:
C = 1/16 seconds (equal to 0.0625 seconds) C = 1/16 seconds (equal to 0.0625 seconds)
C is a scaling factor for the "validity time" calculation ("Vtime" C is a scaling factor for the "validity time" calculation ("Vtime"
and "Htime" fields in message headers, see section 15.3). and "Htime" fields in message headers, see section 18.3).
The "validity time" advertisement is designed such that nodes in a The "validity time" advertisement is designed such that nodes in a
network may have different and individually tuneable emmision inter- network may have different and individually tuneable emission inter-
vals, while still interoperate fully. For protocol functionning and vals, while still interoperate fully. For protocol functioning and
interoperability to work: interoperability to work:
- the advertised holding time MUST always be greater than the - the advertised holding time MUST always be greater than the
refresh interval of the advertised information. Moreover, it refresh interval of the advertised information. Moreover, it
is recommended that the relation between the interval (from is recommended that the relation between the interval (from
section 15.2), and the hold time is kept as specified section 18.2), and the hold time is kept as specified
in section 15.3, to allow for reasonable packet loss. in section 18.3, to allow for reasonable packet loss.
- the constant C SHOULD be set to the suggested value. In order - the constant C SHOULD be set to the suggested value. In order
to achieve interoperability, C MUST be the same on all nodes. to achieve interoperability, C MUST be the same on all nodes.
- the emission intervals (section 15.2), along with the - the emission intervals (section 18.2), along with the
advertised holding times (subject to the above constraints) advertised holding times (subject to the above constraints)
MAY be selected on a per node basis. MAY be selected on a per node basis.
15.2. Emission Intervals Note that the timer resolution of a given implementation might not be
sufficient to wake up the system on precise refresh times or on pre-
cise expire times: the implementation SHOULD round up the 'validity
time' ("Vtime" and "Htime" of packets) to compensate for coarser
timer resolution, at least in the case where "validity time" could be
shorter than the sum of emission interval and maximum expected timer
error.
18.2. Emission Intervals
HELLO_INTERVAL = 2 seconds HELLO_INTERVAL = 2 seconds
REFRESH_INTERVAL = 2 seconds REFRESH_INTERVAL = 2 seconds
TC_INTERVAL = 5 seconds TC_INTERVAL = 5 seconds
MID_INTERVAL = TC_INTERVAL MID_INTERVAL = TC_INTERVAL
HNA_INTERVAL = TC_INTERVAL HNA_INTERVAL = TC_INTERVAL
15.3. Holding Time 18.3. Holding Time
NEIGHB_HOLD_TIME = 3 x REFRESH_INTERVAL NEIGHB_HOLD_TIME = 3 x REFRESH_INTERVAL
TOP_HOLD_TIME = 3 x TC_INTERVAL TOP_HOLD_TIME = 3 x TC_INTERVAL
D_TIME = 30 seconds DUP_HOLD_TIME = 30 seconds
MID_HOLD_TIME = 3 x MID_INTERVAL MID_HOLD_TIME = 3 x MID_INTERVAL
HNA_HOLD_TIME = 3 x HNA_INTERVAL HNA_HOLD_TIME = 3 x HNA_INTERVAL
The Vtime in the message header (see section 3.3.2), and the The Vtime in the message header (see section 3.3.2), and the
Htime in the HELLO message (see section 4.2) are the Htime in the HELLO message (see section 6.1) are the
fields which hold information about the above values in mantissa and fields which hold information about the above values in mantissa and
exponent format (rounded up). In other words: exponent format (rounded up). In other words:
value = C*(1+a/16)*2^b
value = C*(1+a/16)*2^b [in seconds]
where a is the integer represented by the four highest bits of the where a is the integer represented by the four highest bits of the
field and b the integer represented by the four lowest bits of the field and b the integer represented by the four lowest bits of the
field. field.
Given one of the above holding times, one way to compute the man- Notice, that for the previous proposed value of C, (1/16 seconds),
the values, in seconds, expressed by the formula above can be stored,
without loss of precision, in binary fixed point or floating point
numbers with at least 8 bits of fractional part. This corresponds
with NTP time-stamps and single precision IEEE Standard 754 floating
point numbers.
Given one of the above holding times, a way of computing the man-
tissa/exponent representation of a number T (of seconds) is the fol- tissa/exponent representation of a number T (of seconds) is the fol-
lowing: lowing:
- find the biggest integer 'b' such as: T/C > 2^b - find the largest integer 'b' such that: T/C >= 2^b
- compute the expression 16*(T/(C*(2^b))-1), which may not be a - compute the expression 16*(T/(C*(2^b))-1), which may not be a
integer, and round it up. The result gives 'a' integer, and round it up. This results in the value for 'a'
- 'a' and 'b' should now be integers between 0 and 15, and the - if 'a' is equal to 16: increment 'b' by one, and set 'a' to 0
- now, 'a' and 'b' should be integers between 0 and 15, and the
field will be a byte holding the value a*16+b field will be a byte holding the value a*16+b
For instance, for values of 6 seconds, 15 seconds, and 30 seconds
respectively, a and b would be: (a=8,b=6), (a=14,b=7) and (a=14,b=8)
respectively.
15.4. Message Types For instance, for values of 2 seconds, 6 seconds, 15 seconds, and 30
seconds respectively, a and b would be: (a=0,b=5), (a=8,b=6),
(a=14,b=7) and (a=14,b=8) respectively.
18.4. Message Types
HELLO_MESSAGE = 1 HELLO_MESSAGE = 1
TC_MESSAGE = 2 TC_MESSAGE = 2
MID_MESSAGE = 3 MID_MESSAGE = 3
HNA_MESSAGE = 4 HNA_MESSAGE = 4
15.5. Link Types 18.5. Link Types
UNSPEC_LINK = 0 UNSPEC_LINK = 0
ASYM_LINK = 1 ASYM_LINK = 1
SYM_LINK = 2 SYM_LINK = 2
LOST_LINK = 3 LOST_LINK = 3
15.6. Neighbor Types 18.6. Neighbor Types
NOT_NEIGH = 0 NOT_NEIGH = 0
SYM_NEIGH = 1 SYM_NEIGH = 1
MPR_NEIGH = 2 MPR_NEIGH = 2
15.7. Link Hysteresis 18.7. Link Hysteresis
HYST_THRESHOLD_HIGH = 0.8 HYST_THRESHOLD_HIGH = 0.8
HYST_THRESHOLD_LOW = 0.3 HYST_THRESHOLD_LOW = 0.3
HYST_SCALING = 0.5 HYST_SCALING = 0.5
15.8. Willingness 18.8. Willingness
WILL_NEVER = 0 WILL_NEVER = 0
WILL_LOW = 1 WILL_LOW = 1
WILL_DEFAULT = 3 WILL_DEFAULT = 3
WILL_HIGH = 6 WILL_HIGH = 6
WILL_ALWAYS = 7 WILL_ALWAYS = 7
The willingness of a node may be set to any integer value from 0 to The willingness of a node may be set to any integer value from 0 to
7, and specifies how willing a node is to be forwarding traffic on 7, and specifies how willing a node is to be forwarding traffic on
behalf of other nodes. Nodes will, by default, have a willingness behalf of other nodes. Nodes will, by default, have a willingness
WILL_DEFAULT. WILL_NEVER indicates a node which does not wish to WILL_DEFAULT. WILL_NEVER indicates a node which does not wish to
carry traffic for other nodes, e.g. due to ressource constraints carry traffic for other nodes, e.g. due to resource constraints
(e.g. low on battery). WILL_ALWAYS indicates that a node always (e.g. low on battery). WILL_ALWAYS indicates that a node always
should be selected to carry traffic on behalf of other nodes, e.g. should be selected to carry traffic on behalf of other nodes, e.g.
due to ressource abundance (e.g. permanent power supply, high-capac- due to resource abundance (e.g. permanent power supply, high-capac-
ity interfaces to other nodes). ity interfaces to other nodes).
A node may dynamically change its willingness as its conditions A node may dynamically change its willingness as its conditions
change. change.
One possible application would, for example, be for a node, connected One possible application would, for example, be for a node, connected
to a permanent power supply and with fully charged batteries, to to a permanent power supply and with fully charged batteries, to
advertise a willingness of WILL_ALWAYS. Upon being disconnected from advertise a willingness of WILL_ALWAYS. Upon being disconnected from
the permanent power supply (e.g. a PDA being taken out of its charg- the permanent power supply (e.g. a PDA being taken out of its charg-
ing cradle), a willingness of WILL_DEFAULT is advertised. As battery ing cradle), a willingness of WILL_DEFAULT is advertised. As battery
capacity is drained, the willingness would be further reduced. First capacity is drained, the willingness would be further reduced. First
to the intermediate value between WILL_DEFAULT and WILL_LOW, then to to the intermediate value between WILL_DEFAULT and WILL_LOW, then to
WILL_LOW and finallt to WILL_NEVER, when the battery capacity of the WILL_LOW and finally to WILL_NEVER, when the battery capacity of the
node does no longer support carrying forigen traffic. node does no longer support carrying foreign traffic.
15.9. Misc. Constants 18.9. Misc. Constants
TC_REDUNDANCY = 0 TC_REDUNDANCY = 0
MPR COVERAGE = 1 MPR COVERAGE = 1
MAXJITTER = HELLO_INTERVAL / 4 MAXJITTER = HELLO_INTERVAL / 4
16. Sequence Numbers 19. Sequence Numbers
Sequence numbers are used in OLSR with the purpose of discarding Sequence numbers are used in OLSR with the purpose of discarding
"old" information, i.e. messages received out of order. However with "old" information, i.e. messages received out of order. However
a limited number of bits for representing sequence numbers, wrap- with a limited number of bits for representing sequence numbers,
around (that the sequence number is incremented from the maximum pos- wrap-around (that the sequence number is incremented from the maximum
sible value to zero) will occur. To prevent this from interfering possible value to zero) will occur. To prevent this from interfering
with the operation of the protocol, the following MUST be observed. with the operation of the protocol, the following MUST be observed.
The term MAXVALUE designates in the following the largest possible The term MAXVALUE designates in the following the largest possible
value for a sequence number. value for a sequence number.
The sequence number S1 is said to be "greater than" the sequence num- The sequence number S1 is said to be "greater than" the sequence num-
ber S2 iff: ber S2 iff:
S1 > S2 AND S1 - S2 <= MAXVALUE/2 OR S1 > S2 AND S1 - S2 <= MAXVALUE/2 OR
S2 > S1 AND S2 - S1 > MAXVALUE/2 S2 > S1 AND S2 - S1 > MAXVALUE/2
Thus when comparing two messages, it is possible - even in the pres- Thus when comparing two messages, it is possible - even in the pres-
ence of wrap-around - to determine which message contains the most ence of wrap-around - to determine which message contains the most
recent information. recent information.
17. Acknowledgments 20. Security Considerations
The authors would like to thank Joseph Macker and his team Currently, OLSR does does not specify any special security measures.
<macker@itd.nrl.navy.mil> for their valuable suggestions on the As a proactive routing protocol, OLSR makes a target for various
advanced neighbor sensing mechanism. attacks. The various possible vulnerability are discussed in this
section.
20.1. Confidentiality
Being a proactive protocol, OLSR periodically diffuses topological
information. Hence, if used in an unprotected wireless network, the
network topology is revealed to anyone who listens to OLSR control
messages.
In situations where the confidentiality of the network topology is of
importance, regular cryptographic techniques can be applied to ensure
that control traffic can be read and interpreted by only those autho-
rized to do so.
20.2. Integrity
In OLSR, each node is injecting topological information into the net-
work through transmitting HELLO messages and, for some nodes, TC mes-
sages. If some nodes for some reason, malicious or malfunction,
inject invalid control traffic, network integrity may be compromised.
Therefore, message authentication is recommended.
Different such situations may occur, for instance:
1 a node generates TC (or HNA) messages, advertising links to
non-neighbor nodes:
2 a node generates TC (or HNA) messages, pretending to be
another node,
3 a node generates HELLO messages, advertising non-neighbor
nodes,
4 a node generates HELLO messages, pretending to be another
node.
5 a node forwards altered control messages,
6 a node does not broadcast control messages,
7 a node does not select multipoint relays correctly.
8 a node forwards broadcast control messages unaltered, but does
not forward unicast data traffic;
9 a node "replays" previously recorded control traffic from
another node.
Authenticated signatures on control messages (for situation 2, 4 and
5) and on the individual links announced in the control messages (for
situation 1 and 3) may be used as a countermeasure. However to pre-
vent nodes from repeating old (and correctly authenticated) informa-
tion (situation 9) temporal information is required, allowing a node
to positively identify such delayed messages.
Signatures and other required security information may be transmitted
as a separate OLSR message type, thereby allowing that "secured" and
"unsecured" nodes can coexist in the same network, if desired.
20.3. Interaction with External Routing Domains
OLSR does, through the HNA messages specified in section 12,
provide a basic mechanism for injecting external routing information
to the OLSR domain. Section 12 also specifies that routing
information can be extracted from the topology table or the routing
table of OLSR and, potentially, injected into an external domain if
the routing protocol governing that domain permits.
Other than as described in the section 20.2, when operating
nodes, connecting OLSR to an external routing domain, care MUST be
taken not to allow potentially insecure and un-trustworthy informa-
tion to be injected from the OLSR domain to external routing domains.
Care MUST be taken to validate the correctness of information prior
to it being injected as to avoid polluting routing tables with
invalid information.
A recommended way of extending connectivity from an existing routing
domain to an OLSR routed MANET is to assign an IP prefix (under the
authority of the nodes/gateways connecting the MANET with the exiting
routing domain) exclusively to the OLSR MANET area, and to configure
the gateways statically to advertise routes to that IP sequence to
nodes in the existing routing domain.
20.4. Node Identity
OLSR does not make any assumption about node addresses, other than
that each node is assumed to have an unique IP addresses. Therefore,
no special considerations can be made about the applicability of
IPsec authentication headers or key exchange mechanisms.
21. IANA Considerations
OLSR defines a "Message Type" field for control messages. A new reg-
istry is to be created for the values for this Message Type field,
and the following values assigned:
Message Type Value
-------------------- -----
HELLO_MESSAGE 1
TC_MESSAGE 2
MID_MESSAGE 3
HNA_MESSAGE 4
Future values in the range 5-127 of the Message Type can be allocated
using standards action [7].
Additionally, values in the range 128-255 are reserved for pri-
vate/local use.
22. Acknowledgments
The authors would like to thank Joseph Macker
<macker@itd.nrl.navy.mil> and his team, including Justin Dean
<jdean@itd.nrl.navy.mil>, for their valuable suggestions on the
advanced neighbor sensing mechanism and other various aspects of the
protocol, including careful review of the protocol specification.
The authors would also like to thank Christopher Dearlove The authors would also like to thank Christopher Dearlove
<chris.dearlove@baesystems.com> for valuable input on the MPR selec- <chris.dearlove@baesystems.com> for valuable input on the MPR selec-
tion heuristics. tion heuristics and for careful reviews of the protocol specifica-
tion.
18. Authors' Addresses 23. Authors' Addresses
Cedric Adjih Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le Cedric Adjih Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le
Chesnay Cedex, France Phone: +33 1 3963 5215 Email: Chesnay Cedex, France Phone: +33 1 3963 5215 Email:
Cedric.Adjih@inria.fr Cedric.Adjih@inria.fr
Thomas Heide Clausen Project HIPERCOM INRIA Rocquencourt BP 105 78153 Thomas Heide Clausen Project HIPERCOM INRIA Rocquencourt BP 105 78153
Le Chesnay Cedex, France Phone: +33 1 3963 5133 Email: Le Chesnay Cedex, France Phone: +33 1 3963 5133 Email:
Thomas.Clausen@inria.fr Thomas.Clausen@inria.fr
Philippe Jacquet Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le Philippe Jacquet Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le
Chesnay Cedex, France Phone: +33 1 3963 5263 Email: Chesnay Cedex, France Phone: +33 1 3963 5263 Email:
skipping to change at page 72, line 20 skipping to change at page 76, line 20
Anis.Laouiti@inria.fr Anis.Laouiti@inria.fr
Pascale Minet Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le Pascale Minet Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le
Chesnay Cedex, France Phone: +33 1 3963 508832 Email: Pas- Chesnay Cedex, France Phone: +33 1 3963 508832 Email: Pas-
cale.Minet@inria.fr cale.Minet@inria.fr
Paul Muhlethaler Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le Paul Muhlethaler Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le
Chesnay Cedex, France Phone: +33 1 3963 5278 Email: Paul.Muh- Chesnay Cedex, France Phone: +33 1 3963 5278 Email: Paul.Muh-
lethaler@inria.fr lethaler@inria.fr
Amir Qayyum Avaz Networks 5-A Constitution Avenue Islamabad, Pakistan Amir Qayyum Center for Advanced Research in Engineering Pvt. Ltd.
Phone: +92-51-2826160 Email: qayyum@avaznet.com 19, Ataturk Avenue Islamabad, Pakistan Phone: +92-51-2874115 Email:
amir@carepvtltd.com
Laurent Viennot Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le Laurent Viennot Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le
Chesnay Cedex, France Phone: +33 1 3963 5225 Email: Laurent.Vien- Chesnay Cedex, France Phone: +33 1 3963 5225 Email: Laurent.Vien-
not@inria.fr not@inria.fr
19. References 24. References
1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing relia- 1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing
bility in cable free radio LANs: Low level forwarding in HIPERLAN. reliability in cable free radio LANs: Low level forwarding in
Wireless Personal Communications, 1996 HIPERLAN. Wireless Personal Communications, 1996
2. A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying: An efficient 2. A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying: An effi-
technique for flooding in mobile wireless networks. 35th Annual cient technique for flooding in mobile wireless networks. 35th
Hawaii International Conference on System Sciences (HICSS'2001). Annual Hawaii International Conference on System Sciences
(HICSS'2001).
3. ETSI STC-RES10 Committee. Radio equipment and systems: HIPERLAN type 3. ETSI STC-RES10 Committee. Radio equipment and systems: HIPERLAN
1, functional specifications ETS 300-652, ETSI, June 1996 type 1, functional specifications ETS 300-652, ETSI, June 1996
4. Philippe Jacquet and Laurent Viennot, Overhead in Mobile Ad-hoc Net- 4. Philippe Jacquet and Laurent Viennot, Overhead in Mobile Ad-hoc Net-
work Protocols, INRIA research report RR-3965, 2000 work Protocols, INRIA research report RR-3965, 2000
5. S. Bradner. Key words for use in RFCs to Indicate Requirement Lev- 5. S. Bradner. Key words for use in RFCs to Indicate Requirement Lev-
els. Request for Comments (Best Current Practice) 2119, Internet els. Request for Comments (Best Current Practice) 2119, Internet
Engineering Task Force, March 1997. Engineering Task Force, March 1997.
6. T. Clausen, G. Hansen, L. Christensen and G. Behrmann. The Optimized 6. T. Clausen, G. Hansen, L. Christensen and G. Behrmann. The
Link State Routing Protocol, Evaluation through Experiments and Optimized Link State Routing Protocol, Evaluation through Experi-
Simulation. IEEE Symposium on "Wireless Personal Mobile Communica- ments and Simulation. IEEE Symposium on "Wireless Personal Mobile
tions", September 2001. Communications", September 2001.
7. T. Clausen, P. Jacquet, A. Laouiti, P. Muhlethaler, A. Qayyum and L. 7. T. Clausen, P. Jacquet, A. Laouiti, P. Muhlethaler, A. Qayyum
Viennot. Optimized Link State Routing Protocol. IEEE INMIC Pakistan and L. Viennot. Optimized Link State Routing Protocol. IEEE
2001. INMIC Pakistan 2001.
8. T. Narten and H. Alvestrand. Guidelines for Writing an IANA Con-
siderations Section in RFCs. Request for Comments (Best Current
Practice) 2434, Internet Engineering Task Force, October 1998.
Reference [5] and [7] are normative; all others are informative.
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/