draft-ietf-manet-olsr-07.txt   draft-ietf-manet-olsr-08.txt 
INTERNET-DRAFT Thomas Clausen INTERNET-DRAFT Cedric Adjih
IETF MANET Working Group Philippe Jacquet IETF MANET Working Group Thomas Clausen
Expiration: 10 June 2003 Anis Laouiti Expiration: 03 September 2003 Philippe Jacquet
Anis Laouiti
Pascale Minet Pascale Minet
Paul Muhlethaler Paul Muhlethaler
Amir Qayyum Amir Qayyum
Laurent Viennot Laurent Viennot
INRIA Rocquencourt, France INRIA Rocquencourt, France
10 December 2002 03 March 2003
Optimized Link State Routing Protocol Optimized Link State Routing Protocol
draft-ietf-manet-olsr-07.txt draft-ietf-manet-olsr-08.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
skipping to change at page 2, line 16 skipping to change at page 2, line 22
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, link
state information is generated only by nodes elected as MPRs. Thus, a state information is generated only by nodes elected as MPRs. Thus, a
second optimization is achieved by minimizing the number of control second optimization is achieved by minimizing the number of control
messages flooded in the network. As a third optimization, an MPR node messages flooded in the network. As a third optimization, an MPR node
may chose to report only links between itself and its MPR selectors. may chose to report only links between itself and its MPR selectors.
Hence, as contrary to the classic link state algorithm, partial link Hence, as contrary to the classic link state algorithm, partial link
state information is distributed in the network. This information is state information is distributed in the network. This information is
then used by the OLSR protocol for route calculation. OLSR provides then used by for route calculation. OLSR provides optimal routes (in
optimal routes (in terms of number of hops). The protocol is terms of number of hops). The protocol is particularly suitable for
particularly suitable for large and dense networks as the technique large and dense networks as the technique of MPRs works well in this
of MPRs works well in this context. context.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1. Changes . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1. Changes . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2. OLSR Terminology . . . . . . . . . . . . . . . . . . . . . 6 1.2. OLSR Terminology . . . . . . . . . . . . . . . . . . . . . 7
1.3. Applicability Section . . . . . . . . . . . . . . . . . . 8 1.3. Applicability . . . . . . . . . . . . . . . . . . . . . . 9
1.4. Protocol Overview . . . . . . . . . . . . . . . . . . . . 8 1.4. Protocol Overview . . . . . . . . . . . . . . . . . . . . 9
1.5. Multipoint Relays . . . . . . . . . . . . . . . . . . . . 9 1.5. Multipoint Relays . . . . . . . . . . . . . . . . . . . . 10
2. Protocol Functioning . . . . . . . . . . . . . . . . . . . . 10 2. Protocol Functioning . . . . . . . . . . . . . . . . . . . . 11
2.1. Packet Format and Forwarding . . . . . . . . . . . . . . . 10 2.1. Core Functioning . . . . . . . . . . . . . . . . . . . . . 12
2.1.1. Protocol and Port Number . . . . . . . . . . . . . . . . 11 2.2. Auxiliary Functioning . . . . . . . . . . . . . . . . . . 12
2.1.2. Multiple Interfaces and Main Address . . . . . . . . . . 11
2.1.3. Packet Format . . . . . . . . . . . . . . . . . . . . . 12
2.1.3.1. Packet Header . . . . . . . . . . . . . . . . . . . . 12
2.1.3.2. Message Header . . . . . . . . . . . . . . . . . . . . 13
2.1.4. Packet Processing and Message Flooding . . . . . . . . . 14
2.1.5. Message Emission and Jitter . . . . . . . . . . . . . . 16
2.2. Neighbor Sensing . . . . . . . . . . . . . . . . . . . . . 17 3. Packet Format and Forwarding . . . . . . . . . . . . . . . . 13
2.2.1. HELLO Message Format . . . . . . . . . . . . . . . . . . 18 3.1. Protocol and Port Number . . . . . . . . . . . . . . . . . 14
2.2.2. Neighbor Sensing Information Base . . . . . . . . . . . 21 3.2. Main Address . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.2.1. Neighbor Set . . . . . . . . . . . . . . . . . . . . . 21 3.3. Packet Format . . . . . . . . . . . . . . . . . . . . . . 14
2.2.2.2. 2-hop Neighbor Set . . . . . . . . . . . . . . . . . . 21 3.3.1. Packet Header . . . . . . . . . . . . . . . . . . . . . 15
2.2.2.3. MPR Set . . . . . . . . . . . . . . . . . . . . . . . 22 3.3.2. Message Header . . . . . . . . . . . . . . . . . . . . . 15
2.2.2.4. MPR Selector Set . . . . . . . . . . . . . . . . . . . 22 3.4. Packet Processing and Message Flooding . . . . . . . . . . 17
2.2.3. HELLO Message Generation . . . . . . . . . . . . . . . . 22 3.4.1. Default Forwarding Algorithm . . . . . . . . . . . . . . 18
2.2.4. HELLO Message Processing . . . . . . . . . . . . . . . . 23 3.4.2. Considerations on Processing and Forwarding . . . . . . 19
2.2.5. Multipoint Relay Selection . . . . . . . . . . . . . . . 27 3.5. Message Emission and Jitter . . . . . . . . . . . . . . . 20
2.2.6. Neighborhood and 2-hop Neighborhood Changes . . . . . . 30
2.2.7. Advanced Neighbor Sensing Functioning . . . . . . . . . 30
2.2.7.1. Link Hysteresis . . . . . . . . . . . . . . . . . . . 32
2.2.7.2. Optional Link layer notification . . . . . . . . . . . 33
2.3. Topology Discovery . . . . . . . . . . . . . . . . . . . . 34 4. Link Sensing and Neighbor Detection . . . . . . . . . . . . 21
2.3.1. TC Message Format . . . . . . . . . . . . . . . . . . . 34 4.1. Local Link Information Base . . . . . . . . . . . . . . . 21
2.3.2. Topology Information Base . . . . . . . . . . . . . . . 35 4.1.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.3. Advertized Neighbor Set . . . . . . . . . . . . . . . . 35 4.1.2. Neighbor Set . . . . . . . . . . . . . . . . . . . . . . 22
2.3.4. TC Message Generation . . . . . . . . . . . . . . . . . 36 4.1.3. 2-hop Neighbor Set . . . . . . . . . . . . . . . . . . . 22
2.3.5. TC Message Processing . . . . . . . . . . . . . . . . . 37 4.1.4. MPR Set . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.6. Multiple Interface Association . . . . . . . . . . . . . 39 4.1.5. MPR Selector Set . . . . . . . . . . . . . . . . . . . . 22
2.3.6.1. Multiple Interface Association Information Base . . . 39 4.2. HELLO Message Format . . . . . . . . . . . . . . . . . . . 23
2.3.6.2. MID Message Format . . . . . . . . . . . . . . . . . . 39 4.2.1. Link Code as Link Type and Neighbor Type . . . . . . . . 25
2.3.6.3. MID Message Generation . . . . . . . . . . . . . . . . 40 4.3. HELLO Message Generation . . . . . . . . . . . . . . . . . 26
2.3.6.4. MID Message Processing . . . . . . . . . . . . . . . . 40 4.4. Populating the Link Set . . . . . . . . . . . . . . . . . 28
2.3.7. Associated Networks and Hosts . . . . . . . . . . . . . 42 4.4.1. HELLO Message Processing . . . . . . . . . . . . . . . . 29
2.3.7.1. HNA Message Format . . . . . . . . . . . . . . . . . . 42 4.5. Populating the Neighbor Set . . . . . . . . . . . . . . . 30
2.3.7.2. Host and Network Association Information Base . . . . 43 4.5.1. HELLO Message Processing . . . . . . . . . . . . . . . . 32
2.3.7.3. HNA Message Generation . . . . . . . . . . . . . . . . 43 4.6. Populating the 2-hop Neighbor Set . . . . . . . . . . . . 32
2.3.7.4. HNA Message Processing . . . . . . . . . . . . . . . . 43 4.6.1. Hello Message Processing . . . . . . . . . . . . . . . . 32
2.3.8. Routing Table Calculation . . . . . . . . . . . . . . . 45 4.6.2. Populating the MPR set . . . . . . . . . . . . . . . . . 34
2.3.9. Advanced Topology Discovery Functioning . . . . . . . . 48 4.6.3. MPR Computation . . . . . . . . . . . . . . . . . . . . 34
2.3.9.1. Reaction to Link Failure with a MPR Selector . . . . . 48 4.7. Populating the MPR Selector Set . . . . . . . . . . . . . 35
2.3.9.2. Advanced Fast Re-routing Mechanism . . . . . . . . . . 48 4.7.1. Hello Message Processing . . . . . . . . . . . . . . . . 35
2.3.9.2.1. FRR Message Format . . . . . . . . . . . . . . . . . 49 4.8. Neighborhood and 2-hop Neighborhood Changes . . . . . . . 36
2.3.9.2.2. FRR Message Generation . . . . . . . . . . . . . . . 50
2.3.9.2.3. FRR Message Processing . . . . . . . . . . . . . . . 50
3. Node Configuration . . . . . . . . . . . . . . . . . . . . . 51 5. Topology Discovery . . . . . . . . . . . . . . . . . . . . . 37
3.1. Address Assignment . . . . . . . . . . . . . . . . . . . . 51 5.1. TC Message Format . . . . . . . . . . . . . . . . . . . . 37
3.2. Routing Configuration . . . . . . . . . . . . . . . . . . 51 5.2. Topology Information Base . . . . . . . . . . . . . . . . 38
3.3. Data Packet Forwarding . . . . . . . . . . . . . . . . . . 51 5.3. Advertised Neighbor Set . . . . . . . . . . . . . . . . . 39
5.4. TC Message Generation . . . . . . . . . . . . . . . . . . 39
5.5. TC Message Forwarding. . . . . . . . . . . . . . . . . . 39
5.6. TC Message Processing . . . . . . . . . . . . . . . . . . 40
5.7. Routing Table Calculation . . . . . . . . . . . . . . . . 41
4. IPv6 Considerations . . . . . . . . . . . . . . . . . . . . 51 6. Node Configuration . . . . . . . . . . . . . . . . . . . . . 43
5. Security Considerations . . . . . . . . . . . . . . . . . . 52 6.1. Address Assignment . . . . . . . . . . . . . . . . . . . . 43
5.1. Confidentiality . . . . . . . . . . . . . . . . . . . . . 52 6.2. Routing Configuration . . . . . . . . . . . . . . . . . . 43
5.2. Integrity . . . . . . . . . . . . . . . . . . . . . . . . 52 6.3. Data Packet Forwarding . . . . . . . . . . . . . . . . . . 44
6. Proposed Values for the Constants . . . . . . . . . . . . . 53
7. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . 54 7. Multiple OLSR Interfaces . . . . . . . . . . . . . . . . . . 44
8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 55 7.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 44
9. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . 55 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
19. References . . . . . . . . . . . . . . . . . . . . . . . . 72
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 pro-
tocol. I.e., exchanges topology information with other nodes of the tocol, 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. I.e. MPRs provide an efficient
mechanism for flooding control traffic by reducing the number of mechanism for flooding control traffic by reducing the number of
transmissions required. transmissions 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 routes to all destinations is that
MPR nodes declare link-state information for links between them self MPR nodes declare link-state information for links between them self
and their MPR selectors. Additional available link-state information and their MPR selectors. Additional available link-state information
may be utilized e.g. for redundancy. may be utilized, e.g. for redundancy.
These nodes which have been selected as a multipoint relay by some Nodes which have been selected as a multipoint relay by some neighbor
neighbor nodes announce this information periodically in their con- node(s) announce this information periodically in their control mes-
trol messages. Thereby, a node announces to the network, that it has sages. Thereby a node announces to the network, that it has reacha-
reachability to the nodes which have selected it as MPR. In route bility to the nodes which have selected it as MPR. In route calcula-
calculation, the MPRs are used to form the route from a given node to tion, the MPRs are used to form the route from a given node to any
any destination in the network. Furthermore, the protocol uses the destination in the network. Furthermore, the protocol uses the MPRs
MPRs to facilitate efficient flooding of control messages in the net- to facilitate efficient flooding of control messages in the network.
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)
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 06 to version 07 Major changes from version 07 to version 08
- Introduction of relay willingness in hellos
- Introduction of redundant link set in TC messages
- Introduction of packet sequence number in order to clarify
link management
Major changes from version 05 to version 06
- Clarification of the usage of link layer notification and fast
re-routing
- Clarification of MPR selection
- Clarification of multiple interfaces
Major changes from version 04 to version 05
- Introduction of support for multiple interfaces - Restructured draft in order to improve readability and modu-
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.
- Introduction of support for associated hosts and networks. - Small change to message format.
- Introduction of support for advanced neighbor sensing through - "Neighbor sensing" changed to "link sensing and neighbor
hysteresis. detection" to improve readability and modularity.
- Modularity between neighbor sensing and topology discovery - Non-core functions moved from the core part of the draft.
emphasized.
Major changes from version 03 to version 04 1.2. OLSR Terminology
- Finalized the generic packet/message format to include fea- The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
tures for scope-limited (diameter-bound) flooding of messages "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
and to handle duplicate messages. document are to be interpreted as described in RFC2119 [5]. Addition-
ally, this doccument uses the following terminology:
- Editorial changes towards language consistency. node
Major changes from version 02 to version 03 A MANET router which implements the Optimized Link State Rout-
ing protocol as specified in this document.
- Introduction of assigned port number for use with OLSR. main address
- The packet format now uses "message length" rather than an The main address of a node, which will be used in OLSR control
offset to the next message. traffic as the "originator address" of all messages emitted by
this node. It is the address of one of its interfaces. If a
node has only one interface, the main address is the address
of that interface.
- Optional section describing how link-layer notifications can neighbor node
be utilized included.
Major changes from version 01 to version 02 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
interface of Y).
- Introduction of a unified packet format for encapsulation of 2-hop neighbor
all messages being exchanged between nodes. This also serves
to facilitate extensions in future versions of the protocol
(i.e. introduction of new protocol messages) without breaking
backwards compatibility.
- Removal of "Power Conservation" from this draft. Power Conser- An node heard by a neighbor.
vation may be considered as an extension to the basic routing
capabilities.
1.2. OLSR Terminology strict 2-hop neighbor
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", a 2-hop neighbor which is not the node itself or a neighbor of
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this the node
document are to be interpreted as described in RFC2119 [5]. The OLSR
protocol uses the following terminology:
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 same message is not already received, and
the time to live field of the message is greater than one. the 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.
node
A MANET router which implements this Optimized Link State
Routing protocol.
interface interface
A network device participating in the MANET (usually a wire- A network device participating in the MANET (usually a wire-
less device). A node may have several interfaces, each inter- less device). A node may have several interfaces, each inter-
face assigned an unique IP address. 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 interfaces (from two different nodes) sus-
ceptible to hear one another (i.e. one may be able to receive ceptible to hear one another (i.e. one may be able to receive
traffic from the other). A node is said to have a link to traffic from the other). A node is said to have a link to
another node when one of its interface has a link to one of another node when one of its interface has a link to one of
the interfaces of the other node. the interfaces of the other node.
neighbor interface
An interface I is a neighbor interface of an interface J if J
can hear I (i.e. it is possible to send traffic from I to J).
sender interface
The sender interface of a control message is the neighbor
interface over which the message has been transmitted.
receiver interface
The receiver interface of a control message is the (local)
interface, over which a control message has been received.
neighbor 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
interface of Y).
2-hop interface
An interface heard by a neighbor.
symmetric link symmetric link
A bi-directional link between two interfaces, i.e. interface I A bi-directional link between two interfaces, i.e. interface I
and interface J where both can hear each other. and interface J where both can hear each other.
asymmetric link
A link between two interfaces I and J, where it is confirmed
that I can hear J but not confirmed if J can hear I.
symmetric neighborhood symmetric neighborhood
The symmetric neighborhood of any node X is the set of nodes The symmetric neighborhood of any node X is the set of nodes
which have at least one symmetric link to X. 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
which don't have a symmetric link to X but have a symmetric
link to the symmetric neighborhood of X.
main address The symmetric 2-hop neighborhood of X is the set of nodes,
excluding X itself, which have a symmetric link to the sym-
metric neighborhood of X.
The main address of a node, which will be used in OLSR control symmetric strict 2-hop neighborhood
traffic as the "originator address" of all messages emitted by
this node. It is the address of one of its interfaces.
1.3. Applicability Section The symmetric 2-hop neighborhood of X is the set of nodes,
excluding X itself and its neighbor, which have a symmetric
link to the symmetric neighborhood of X.
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 "several" nodes rather than being almost exclusively
between a small specific set of nodes. The performance of the proto- between a small specific set of nodes. As a proactive protocol, OLSR
col, compared to a reactive protocol, is even better if these is also suitable for scenarios where the communicating pairs change
[source, destination] pairs change over time [4]. Such changes may over time: no additional control traffic is generated in this situa-
initiate substantial traffic (query flooding) in case of a reactive tion since routes are maintained for all known destinations at all
protocol, but no additional traffic in OLSR, as the routes are main- times.
tained for each known destination all the time.
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 link
state protocol, tailored for mobile ad hoc networks. 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 optimal routes. The minimal set of link state information
required is, that all nodes, selected as MPRs, declare the links to required is, that all nodes, selected as MPRs, MUST declare the links
their MPR selectors. Additional topological information, if present, to their MPR selectors. Additional topological information, if
may be utilized e.g. for redundancy purposes. present, 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 optimiza-
skipping to change at page 9, line 47 skipping to change at page 10, line 50
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 duplicate 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 neighborhood which may retransmit its messages. This set of
selected neighbor nodes is called the "Multipoint Relay" (MPR) set of selected neighbor nodes is called the "Multipoint Relay" (MPR) set of
that node. The neighbors of node N which are *NOT* in its MPR set, that node. The neighbors of node N which are *NOT* in its MPR set,
receive and process broadcast messages but do not retransmit broad- receive and process broadcast messages but do not retransmit broad-
cast messages received from node N. cast messages received from node N.
Each node selects its MPR set among its one hop symmetric neighbors. Each node selects its MPR set from among its one hop symmetric
This set is selected such that it covers (in terms of radio range) neighbors. This set is selected such that it covers (in terms of
all nodes that are two hops away. The MPR set of N, denoted as radio range) all nodes that are two hops away. The MPR set of N,
MPR(N), is then an arbitrary subset of the symmetric neighborhood of denoted as MPR(N), is then an arbitrary subset of the symmetric
N which satisfies the following condition: every node in the symmet- neighborhood of N which satisfies the following condition: every node
ric 2-hop neighborhood of N must have a symmetric link towards in the symmetric strict 2-hop neighborhood of N must have a symmetric
MPR(N). The smaller the MPR set is, the more optimal is the routing link towards MPR(N). The smaller an MPR set, the less control traffic
protocol. [2] gives an analysis and example of MPR selection algo- overhead results from the routing protocol. [2] gives an analysis and
rithms. 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 Selector
set" (MPR selector set) of a node. A node obtains this information set" (MPR selector set) of a node. A node obtains this information
from periodic HELLO messages received from the neighbors. 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. This set can change over time (i.e. when a
node selects another MPR-set) and is indicated by the selector nodes node selects another MPR-set) and is indicated by the selector nodes
in their HELLO messages. in their HELLO messages.
2. Protocol Functioning 2. Protocol Functioning
This section describes the details of the protocol functioning. This This section outlines the overall the protocol functioning.
includes descriptions of the format and contents of the packets being
exchanged by routers and the algorithms (e.g. for packet handling and
routing table calculation).
The "Packet Forwarding" and "Neighbor Sensing" mechanisms may be seen OLSR is modularized into a "core" of functionality, which is always
as a transfer layer for the routing protocol. This provides nodes required for the protocol to operate, and a set of auxiliary func-
tions.
The core specifies, in its own right, a protocol able to provide
routing in a stand-alone MANET.
Each auxiliary function provides additional functionality, which may
be applicable in specific scenarios. E.g. in case a node is providing
connectivity between the MANET and another routing domain.
All auxiliary functions are compatible, to the extend where any
(sub)set of auxiliary functions may be implemented with the core.
Furthermore, the protocol allows heterogeneous nodes, i.e. nodes
which implement different subsets of the auxiliary functions, to
coexist in the network.
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
easy-to-comprehend protocol, and to provide a way of only adding com-
plexity where specific additional functionality is required.
2.1. Core Functioning
The core functionality of OLSR specifies the behavior of a node,
equipped with OLSR interfaces participating in the MANET and running
OLSR as routing protocol. This includes an universal specification of
OLSR protocol messages and their transmission through the network, as
well as link sensing, topology diffusion and route calculation.
The "Link Sensing and Neighbor Detection" mechanism provides nodes
with information about their neighbors and offers an optimized mecha- with information about their neighbors and offers an optimized mecha-
nism for flooding messages through the concept of MPRs. It completely nism for flooding messages through the concept of MPRs. It completely
relies on the exchange of HELLO messages. relies on the exchange of HELLO messages.
The "Topology Discovery" mechanism relies on the "Packet Forwarding" The "Topology Discovery" mechanism relies on the "Packet Forwarding"
and "Neighbor Sensing" mechanisms. A node uses neighbor and MPR and "Link Sensing and Neighbor Discovery" mechanisms. A node uses
information from the "Neighbor Sensing" mechanism in diffusing local neighbor and MPR information from the "Link Sensing" mechanism in
topology information to the larger network. Topology information is diffusing local topology information to the larger network. Topology
diffused through the "Packet Forwarding" mechanism, and relies on TC, information is diffused through the "Packet Forwarding" mechanism,
MID and HNA messages. Resulting from the "Topology Discovery" mecha- and relies on TC messages. Resulting from the "Topology Discovery"
nism is information which allows routing table calculation. mechanism is information which allows routing table calculation.
The key notion for these mechanisms is the MPR relationship. The key notion for these mechanisms is the MPR relationship.
2.1. Packet Format and Forwarding The following table specifies the component of the core functionality
of OLSR, as well as their relations to this document.
Feature | Section
------------------------------+--------------
Packet format and forwarding | 3
Link sensing | 4
Topology discovery | 5
Node configuration | 6
Multiple OLSR interfaces | 7
Multiple interface compliance is needed when:
- a node has multiple interfaces which participate in the OLSR
domain,
- a node exists in a domain where other nodes with multiple OLSR
interfaces are present.
2.2. Auxiliary Functioning
In addition to the core functioning of OLSR, there are situations
where additional functionality is needed. This includes situations
where a node has multiple interfaces, some of which participate in
another routing domain, where the programming interface to the net-
working hardware provides additional information in form of link-
layer notifications and where it is desired to provide redundant
topological information to the network on expense of protocol over-
head.
The following table specifies auxiliary functions and their relation
to this document.
Feature | Section
------------------------------+--------------
Non-OLSR interfaces | 8
Link-layer notifications | 9
Advanced link sensing | 10
Redundant topology | 11
Redundant MPR flooding | 12
3. Packet Format and Forwarding
OLSR communicates using a unified packet format for all data related OLSR communicates using a 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 transmission
over the network. The present draft is presented with IPv4 addresses. over the network. The present draft is presented with IPv4 addresses.
Considerations regarding IPv6 are given in section 4. Considerations regarding IPv6 are given in section 13.
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 table to prevent
transmitting the same message twice) and minimized in the entire net- transmitting the same message twice) and minimized in the entire net-
work through the usage of MPRs as described in later sections. work 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.
2.1.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
assigned by IANA for exclusive usage by the OLSR protocol. assigned by IANA for exclusive usage by the OLSR protocol.
2.1.2. Multiple Interfaces and Main Address 3.2. Main Address
A node may have several wireless interfaces, each of them having a
distinct IP address. OLSR supports such nodes with multiple inter-
faces. For this reason, each node SHOULD choose one of its interface
addresses as its "main address". It is of no importance which address
is chosen, however a node SHOULD always use the same address as its
main address. For example, the smallest interface address may be cho-
sen as the main interface. The main address MUST be used in OLSR con-
trol traffic as the "originator address" of all messages emitted by a
node.
A node must transmit and retransmit all control messages on all For a node with one interface, the main address of a node, as defined
interfaces. The source address in the IP header must contain the IP- in "OLSR Terminology", MUST be set to the address of that interface.
address of the interface where the message is transmitted. This
address will be denoted the "sender interface address".
2.1.3. Packet Format 3.3. Packet Format
The basic layout of any packet in OLSR is as follows (omitting the IP The basic layout of any packet in OLSR is as follows (omitting IP and
and UDP headers): UDP headers):
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Packet Length | Packet Sequence Number | | Packet Length | Packet Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Type | Reserved | Message Size | | Message Type | Vtime | Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator Address | | Originator Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Time To Live | Hop Count | Message Sequence Number | | Time To Live | Hop Count | Message Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
: MESSAGE : : MESSAGE :
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Type | Reserved | Message Size | | Message Type | Vtime | Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator Address | | Originator Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Time To Live | Hop Count | Message Sequence Number | | Time To Live | Hop Count | Message Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
: MESSAGE : : MESSAGE :
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: : : :
(etc) (etc)
2.1.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 at each
any new OLSR packet transmitted. The Packet Sequence Number (PSN) MUST be incremented by one
each time a new OLSR packet is transmitted. "Wrap-around" is
handled as described in section 16.
The sender information for a packet is obtainable from the IP header. The sender information for a packet is obtainable from the IP header.
Any received packet whose "Packet Length" is less or equal to 12
(i.e. the packet contains no messages), MUST be silently dropped.
2.1.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" partition. Message types in the range of 0-127 the "MESSAGE" part. Message types in the range of 0-127 are
are reserved for messages in this draft and in extension reserved for messages in this document and in possible exten-
drafts. sions.
Reserved Vtime
MUST be set to "00000000" to be in compliance with this ver- This field indicates for how long time after reception a node
sion of the draft. must consider the information contained in the message for
valid. The validity time is represented by its mantissa (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
where a is the integer represented by the four highest bits of
Vtime field and b the integer represented by the four lowest
bits of Vtime field. The proposed value of the scaling factor
C is specified in section 15.
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 14, line 20 skipping to change at page 17, line 11
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 is
inserted into the Sequence Number field of the message. The inserted into the Sequence Number field of the message. The
sequence number is increased by 1 (one) for each message orig- sequence number is increased by 1 (one) for each message orig-
inating from the node - "wrap-arounds" are handled as inating from the node. "Wrap-around" is handled as described
described in a later section. Message sequence numbers are in section 16. Message sequence numbers are used to
used to ensure that a given message is not retransmitted more ensure that a given message is not retransmitted more than
than once by any node. once by any node.
2.1.4. Packet Processing and Message Flooding 3.4. Packet Processing and Message Flooding
Upon receiving a basic packet, the protocol parser examines each of Upon receiving a basic packet, a node examines each of the "message
the "message headers". Based on the value of the "Message Type" headers". Based on the value of the "Message Type" field, the node
field, the parser can determine the fate of the message. A node may can determine the fate of the message. A node may receive the same
receive the same message several times. Thus, to avoid re-processing message several times. Thus, to avoid re-processing of some messages
of some messages which were already received and processed, each node which were already received and processed, each node maintains a
maintains a Duplicate table. In this table, the node records informa- Duplicate Table. In this table, the node records information about
tion about the most recently received messages where duplicate pro- the most recently received messages where duplicate processing of a
cessing of a message is to be avoided. For such a message, a node message is to be avoided. For such a message, a node records a
records a "Duplicate Tuple" (D_addr, D_seq_num, D_time), where D_addr "Duplicate Tuple" (D_addr, D_seq_num, D_time), where D_addr is the
is the originator address of the message, D_seq_num is the message originator address of the message, D_seq_num is the message sequence
sequence number of the message and D_time specifies the time at which number of the message and D_time specifies the time at which a tuple
a tuple expires and *MUST* be removed. 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.
Thus, upon receiving a basic packet, a node performs the following Thus, upon receiving a basic packet, a node MUST perform the follow-
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 time to live of the message is less than or equal to
'0' (zero), the message MUST silently be dropped. '0' (zero), the message MUST silently be dropped.
2 If there exists a tuple in the duplicate set, where: 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
packet MUST silently be discarded.
For IPv4 addresses, this implies that packets, where the
Packet Length < 16 MUST silently be discarded.
3 Processing condition:
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 and then the message has already been completely processed
MUST silently be ignored. and MUST not be processed again.
3 Otherwise, if the node implements the Message Type of the mes- 3.2 Otherwise, if the node implements the Message Type of the
sage, the message MUST be processed according to the specifi- message, the message MUST be processed according to the
cations for the message type. specifications for the message type.
4 Otherwise, if the node does not implement the Message Type of 4 Forwarding condition:
the message the message SHOULD be processed according to the
following algorithm:
4.1 If the sender interface address of the message is not 4.1 if there exists a tuple in the duplicate set, where:
detected to be in the symmetric neighborhood of the node,
the message MUST silently be dropped.
4.2 If the sender interface address of the message is D_addr == Originator Address, AND
detected to be in the symmetric neighborhood of the node,
an entry in the duplicate set is recorded with: D_seq_num == Message Sequence Number
then the message has already been considered for forward-
ing and SHOULD NOT be retransmitted again.
4.2 Otherwise:
4.2.1
If the node implements the Message Type of the mes-
sage, the message MUST be considered for forwarding
according to the specifications for the message
type.
4.2.2
Otherwise, if the node does not implement the Mes-
sage Type of the message, the message SHOULD be pro-
cessed according to the default forwarding algorithm
described below.
3.4.1. Default Forwarding Algorithm
The 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 message
MUST silently be dropped.
2 If the sender interface address of the message is detected to
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. D_time = current time + D_HOLD_TIME.
4.3 If the sender interface address is an interface address 3 If the sender interface address is an interface address of a
of a MPR selector of this node and if the time to live of MPR selector of this node and if the time to live of the mes-
the message is greater than '1', the message MUST be for- sage is greater than '1', the message MUST be forwarded
warded according to the following: according to the following:
4.3.1 3.1 The TTL of the message is reduced by one.
The TTL of the message is reduced by one.
4.3.2 3.2 The hop-count of the message is increased by one
The hop-count of the message is increased by one
4.3.3 3.3 The message is broadcasted on all interfaces running
The message is broadcasted on all interfaces OLSR. Notice: The remaining fields of the message header
(Notice: The remaining fields of the message header SHOULD be left unmodified.
SHOULD be left unmodified.)
Notice: known message types are *not* forwarded "blindly" by this 3.4.2. Considerations on Processing and Forwarding
It should be noted that processing and forwarding messages are two
different actions, conditioned by different rules. Processing relates
to using the content of the messages, while forwarding is related to
retransmitting the same message for other nodes of the network.
Notice that this specification includes a description for both the
forwarding and the processing of each known message type. Messages
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. This enables, e.g., a specifying how the message is to be handled and, if necessary,
message type to be specified such that the message can be modified retransmitted. This enables, e.g., a message type to be specified
while in transit (e.g. to reflect the route the message has taken). such that the message can be modified while in transit (e.g. to
Further, it enables that the optimization through the MPRs can be reflect the route the message has taken). Further, it enables that
bypassed: if for some reason classical flooding of a message type is the optimization through the MPRs can be bypassed: if for some reason
required (e.g. to transmit control information over unidirectional classical flooding of a message type is required, the algorithm which
links), the algorithm which specifies how such messages should be specifies how such messages should be handled will simply rebroadcast
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 be able
to maintain compatibility with older implementations. The REQUIRED to maintain compatibility with older implementations. The REQUIRED
message types for OLSR are: message types for the core functionality of OLSR are:
- HELLO-messages, performing the task of neighbor sensing. - HELLO-messages, performing the task of link sensing, neighbor
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 multiple interface decla-
ration.
- HNA-messages, performing the task of associated host and/or
network declaration.
- FRR-messages, performing the task of initiating fast re-rout- - MID-messages, performing the task of declaring the presence of
ing in case of link failure. multiple interfaces on a node.
Extensions may for example be messages enabling power conservation / Other message types include those specified in later sections, as
sleep mode, multicast routing, support for unidirectional links, well as possible future extensions such as for example messages
auto-configuration/address assignment etc. enabling power conservation / sleep mode, multicast routing, support
for unidirectional links, auto-configuration/address assignment etc.
2.1.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, periodic OLSR 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 under-
lying link-layer, this may or may not lead to collisions and hence lying link-layer, this may or may not lead to collisions and hence
skipping to change at page 17, line 41 skipping to change at page 21, line 19
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 It should be noticed that the present draft imposes a minimal rate of
control message emission. However a node MAY send control messages at control message emission. However a node MAY send control messages at
a higher rate (e.g. for better reacting to high mobility). Tuning the a higher rate (e.g. for better reacting to high mobility). Tuning the
rate of control traffic to the actual conditions under which the pro- rate of control traffic to the actual conditions under which the pro-
tocol is to operate is an implementation issue. tocol is to operate is an implementation issue.
2.2. Neighbor Sensing 4. Link Sensing and Neighbor Detection
Each node should detect the neighbor interfaces with which it has a This section describes how a node discovers its immediate topology,
direct and symmetric link. Uncertainties over radio propagation may known as its "neighborhood". This implies detecting the quality of
make some links unidirectional. Consequently, all links MUST be links to neighbor nodes, as well as discovering which nodes are in
checked in both directions in order to be considered valid. the neighborhood and two-hop neighborhood.
To perform neighbor detection, each node broadcasts HELLO messages, Specifically, link sensing and neighbor detection populates the local
containing information about heard neighbor interfaces and their link link information base.
status. The link status may either be "symmetric", "heard" (asymmet-
ric), "MPR" or "lost". "Symmetric" indicates, that the link has been
verified to be bi-directional, i.e. it is possible to transmit data
in both directions. "Heard" indicates that the node can hear HELLO
messages from a neighbor interface, but it is not confirmed that this
neighbor interface is also able to receive messages from the node.
MPR indicates that the sender has selected the node as MPR. A status
of MPR further implies that the link is symmetric. "Lost" indicates
that the link with this neighbor interface is now lost.
HELLO messages are broadcast to all one-hop neighbors and are emitted 4.1. Local Link Information Base
on each MANET interface of the node. They are *not relayed* to fur-
ther nodes.
More precisely, a HELLO message contains for each interface I: The local link information base stores information about neighbors,
links to neighbors, links to 2-hop neighbors, MPRs and MPR selectors.
- a list of neighbor interface addresses, having a symmetric 4.1.1. Link Set
link to interface I;
- a list of neighbor interface addresses, which are "heard" by A node records a "Link Tuple" (L_local_iface_addr, L_neigh-
interface I (for historical reasons, the term "asymmetric" is bor_iface_addr, L_SYM_time, L_ASYM_time, L_time). L_local_iface_addr
used for "heard"); is the (interface) address of the local node (i.e. one endpoint of
the link), L_neighbor_iface_addr is the (interface) address of the
neighbor node (i.e. the other endpoint of the link), L_SYM_time is
the time until which the link is considered symmetric, L_ASYM_time is
the time until which the neighbor interface is considered heard, and
L_time 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
considered lost.
- a list of neighbor interface addresses of neighbors selected This information is used when declaring the neighbor interfaces in
as MPRs, AND having a symmetric link to interface I; the HELLO messages.
- a list of neighbor interface addresses, which have been lost. 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
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
be declared lost.
These lists are computed as described in the HELLO message generation In a node, the set of Link Tuples are denoted the "Link Set".
section.
2.2.1. HELLO Message Format 4.1.2. Neighbor Set
To accommodate the above requirements, as well as to accommodate for A node records a set of "neighbor tuples" (N_neighbor_main_addr,
future extensions, an approach similar to the overall packet format N_status, N_willingness), describing symmetric neighbors. N_neigh-
is taken. Thus the proposed format of a HELLO message is: 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
and 7, and specifies a nodes willingness to carry traffic on behalf
of other nodes.
4.1.3. 2-hop Neighbor Set
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
definition are also symmetric, thereby also MPR) links between its
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
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
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
Set".
4.1.4. MPR Set
A node maintains a set of neighbors which are selected as MPR. Their
main addresses are listed in the so-called MPR Set.
Section 4.6.2 describes how MPRs are selected.
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).
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
*MUST* be removed.
In a node, the set of MPR-selector tuples are denoted the "MPR Selec-
tor Set".
4.2. HELLO Message Format
A common mechanism is employed for populating the local link informa-
tion base, namely periodic exchange of HELLO messages. Thus this sec-
tion describes the general 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
accommodate for future extensions, an approach similar to the overall
packet format is taken. Thus the proposed format of a HELLO 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved | Willingness | # Interfaces | | Reserved | Htime | Willingness |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: . . . :
: :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Type | Interface # | Link Message Size | | Link Code | Reserved | Link Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Interface Address | | Neighbor Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Interface Address | | Neighbor Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: . . . : : . . . :
: : : :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Type | Interface # | Link Message Size | | Link Code | Reserved | Link Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Interface Address | | Neighbor Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Interface Address | | Neighbor 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 the Packet Format and Forwarding section, with the "Mes- described in section 3.4, with the "Message Type" set to
sage Type" set to HELLO_MESSAGE and the TTL field set to 1 (one). 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.
Reserved Reserved
This field is reserved for future usage, and MUST be set to This field must be set to "0000000000000" to be in compliance
"0000000000000000" for compliance with this draft. with this specification.
HTime
This field specifies the HELLO emission interval used by the
node on this particular interface, i.e. the time before the
transmission of the next HELLO (this information is used in
advanced link sensing). The HELLO emission interval is repre-
sented by its mantissa (four highest bits of Htime field) and
by its exponent (four lowest bits of Htime field). In other
words:
HELLO emission interval=C*(1+a/16)*2^b
where a is the integer represented by the four highest bits of
Htime field and b the integer represented by the four lowest
bits of Htime field. The proposed value of the scaling factor
C is specified in section 15.
Willingness Willingness
This field indicates the "willingness" of the sender to act as This field specifies the willingness of a node to carry and
a multipoint relay. The willingness parameter is an integer forward traffic for other nodes.
between 0 and 7. The value 0 is for nodes which should never
forward packets to other destinations (e.g. because their
power supply is critical). The higher the willingness of a
node, the more likely is the node to be selected as MPR by its
neighbors. The value 7 is reserved for nodes which should
always be selected as multipoint relay (e.g. when the node
belongs to a pre-defined backbone). An OLSR router in normal
operation SHOULD have willingness equal to 3.
# Interfaces A node with willingness WILL_NEVER (see section 15.8, for
willingness constants) MUST never be selected as MPR by any
node. A node with willingness WILL_ALWAYS MUST always be
selected as MPR. By default, a node SHOULD advertise a will-
ingness of WILL_DEFAULT.
This field indicates the number of additional MANET interfaces Link Code
(in addition to the main interface) possessed by the node. If
the node has only one interface, this number is 0.
Interface Address This field specifies informations about the link between the
interface of the sender and the following list of neighbor
interfaces. It also specifies informations about the status of
the neighbor.
This field indicates the addresses of additional MANET inter- Link codes, not known by a node, are silently discarded.
faces. The first one will be referenced as interface address
number 1, the second as interface address number 2, and so on.
The main address of the node (whose address is given in the
originator field of the message header) will be referenced as
interface address number 0.
Link Type
This field specifies the type of the link between the inter- Link Message Size
face of the sender, as identified by the interface number, and
the following list of neighbor interfaces. As a minimum, the
following four link types are REQUIRED by OLSR:
- ASYM_LINK, indicating that the links are asymmetric (i.e. The size of the link message, counted in bytes and measured
the neighbor interface is "heard"). from the beginning of the "Link Code" field and until the next
"Link Code" field (or - if there are no more link types - the
end of the message).
- SYM_LINK, indicating that the links are symmetric. Neighbor Address
- MPR_LINK, indicating, that the links are symmetric AND An address of a neighbor node.
that the neighbors have been selected as MPR by the
4.2.1. Link Code as Link Type and Neighbor Type
This document specifies processing only of Link Codes < 16.
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:
7 6 5 4 3 2 1 0
+-------+-------+-------+-------+-------+-------+-------+-------+
| 0 | 0 | 0 | 0 | Neighbor Type | Link Type |
+-------+-------+-------+-------+-------+-------+-------+-------+
The following four "Link Types" are REQUIRED by OLSR:
- UNSPEC_LINK - indicating that no specific information about
the links is given.
- ASYM_LINK - indicating that the links are asymmetric (i.e. the
neighbor interface is "heard").
- SYM_LINK - indicating that the links are symmetric with the
interface.
- LOST_LINK - indicating that the links have been lost.
The following three "Neighbor Types" are REQUIRED by OLSR:
- SYM_NEIGH - indicating that the neighbors have at least one
symmetrical link with this node.
- MPR_NEIGH - indicating that the neighbors have at least one
symmetrical link AND have been been selected as MPR by the
sender. sender.
- LOST_LINK, indicating that the links have been lost. - NOT_NEIGH - indicating that the nodes are either no longer or
have not yet become symmetrical neighbors.
Interface # Note that the implementation should be careful in not confusing Link
Type with Neighbor Type nor the constants (confusing SYM_NEIGH with
SYM_LINK for instance).
This field indicates the number of the interface to which the A link code advertising:
following list of neighbor interfaces corresponds. Number 0
indicates the main interface (whose address is the main
address).
Link Message Size Link Type == SYM_LINK AND
The size of the link message, counted in bytes and measured Neighbor type == NOT_NEIGH
from the beginning of the "Link Type" field and until the next
"Link Type" field (or - if there are no more link types - the
end of the message).
Neighbor Interface Address is invalid, and any links listed as such MUST be silently discarded
without any processing.
An address of a neighbor interface. 4.3. HELLO Message Generation
Neighbor sensing is performed using HELLO message exchange, updating This involves transmitting the Link Set, the Neighbor Set and the MPR
the neighbor sensing information base in each node. Set. In principle, a HELLO message serves three independent tasks:
2.2.2. Neighbor Sensing Information Base - link sensing
The neighbor sensing information base stores information about neigh- - neighbor detection
bor interfaces, 2-hop neighbors, MPRs and MPR selectors.
2.2.2.1. Neighbor Set - MPR selection signaling
For each of its interface I and for each neighbor interface NI, heard Three tasks are all are based on periodic information exchange within
by I, a node records a "Neighbor Tuple" (N_if_id, N_if_addr, a nodes neighborhood, and serve the common purpose of "local topology
N_main_addr, N_willing, N_SYM_time, N_ASYM_time, N_time) where discovery". A HELLO message is therefore generated based on the
N_if_id is the identifier number of the local interface I, N_if_addr information stored in the Local Link Set, the Neighbor Set and the
is the address of the neighbor interface NI, N_main_addr is the main MPR Set from the local link information base.
address of the neighbor possessing NI, N_willing is the willingness
of the neighbor possessing NI, N_SYM_time is the time until which the
link is considered symmetric, N_ASYM_time is the time until which the
neighbor interface is considered heard, and N_time specifies the time
at which this record expires and *MUST* be removed. When N_SYM_time
and N_ASYM_time are expired, the link is considered lost.
This information is used when declaring the neighbor interfaces in A node must perform link sensing on each interface, in order to
the HELLO messages. detect links between the interface and neighbor interfaces. Further-
more, a node must advertise its entire symmetric neighborhood on each
interface in order to perform neighbor detection. Hence, for a given
interface, a HELLO message will contain a list of links on that
interface (with associated link types), as well as a list of the
entire neighborhood (with an associated neighbor types).
N_SYM_time and N_ASYM_time are used to decide the Link Type declared The Vtime field is set such that it corresponds to the value of the
for the neighbor interface. If N_SYM_time is not expired, the link is node's NEIGHB_HOLD_TIME parameter. The Htime field is set such that
declared symmetric. If N_SYM_time is expired but N_ASYM_time is not, it corresponds to the value of the node's HELLO_INTERVAL parameter
the link is declared heard. If both N_SYM_time and N_ASYM_time are (see section 15.3).
expired, the link is declared lost.
In a node, the set of Neighbor Tuples are denoted the "Neighbor Set". The Willingness field is set such that it corresponds to the nodes
willingness to forward traffic on behalf of other nodes (see section
15.8). A node MUST advertise the same willingness on all inter-
faces.
2.2.2.2. 2-hop Neighbor Set The lists of addresses declared in a HELLO message are computed as
follows:
A node records a set of "2-hop tuples" (N_main_addr, N_if_addr, For each tuple in the Link Set, where L_local_iface_addr is the
N_2hop_addr, N_2hop_main_addr, N_time), describing symmetric or MPR interface where the HELLO is to be transmitted, and where L_time >=
links between its neighbors and the symmetric 2-hop neighborhood. current time (i.e. not expired), L_neighbor_iface_addr is advertised
N_main_addr and N_if_addr are the main address and an interface with:
address of a neighbor, N_2hop_addr is an interface address of a 2-hop
neighbor with a symmetric or MPR link to interface, N_2hop_main_addr
is the main address of the 2-hop node,and N_time specifies the time
at which the tuple expires and *MUST* be removed.
This information is gathered from the HELLO messages received by a 1 The Link Type set according to the following:
node from its neighbor nodes. The N_2hop_main_addr is acquired
through the multiple interface association base.
In a node, the set of 2-hop tuples are denoted the "2-hop Neighbor if L_SYM_time >= current time (not expired) AND
Set".
2.2.2.3. MPR Set L_time >= current time (not expired)
A node maintains a set of neighbors which are selected as MPR. Their Link Type = SYM_LINK
main addresses are listed in the so-called MPR Set. The Multipoint
relay selection section describes how MPRs are selected.
2.2.2.4. MPR Selector Set Otherwise, if L_ASYM_time >= current time (not expired)
AND
A node maintains information (obtained from the HELLO messages) about L_SYM_time < current time (expired) AND
the neighbors which have selected this node as a MPR.
Thus, a node records an MPR-selector tuple (MS_if_addr, MS_main_addr, L_time >= current time (not expired)
MS_time). MS_if_addr is the address of an interface of a node which
has selected the node as MPR, MS_main_addr is the main address of the
MPR selector and MS_time specifies the time at which a tuple expires
and *MUST* be removed.
In a node, the set of MPR-selector tuples are denoted the "MPR Selec- Link Type = ASYM_LINK
tor Set".
2.2.3. HELLO Message Generation Otherwise, if L_ASYM_time < current time (expired) AND
The lists of addresses declared in a HELLO message are computed from L_SYM_time < current time (expired) AND
the Neighbor Set as follows:
- for each tuple where: L_time >= current time (not expired)
N_SYM_time < current time (i.e. expired) AND Link Type = LOST_LINK
N_ASYM_time < current time (i.e. expired)
N_if_addr is declared with LOST_LINK Link Type for interface 2 The Neighbor Type is set according to the following:
N_if_id;
- for each tuple where: 2.1 If the main address, corresponding to L_neigh-
bor_iface_addr, is included in the MPR set:
N_SYM_time >= current time (not expired) Neighbor Type = MPR_NEIGH
N_if_addr is declared with MPR_LINK Link Type if N_main_addr
is in the MPR set and SYM_LINK Link Type otherwise;
- for each tuple where: 2.2 Otherwise, if the main address, corresponding to L_neigh-
bor_iface_addr, is included in the neighbor set:
N_SYM_time < current time (expired) AND if N_status == SYM
N_ASYM_time >= current time (not expired),
N_if_addr is declared with ASYM_LINK Link Type. Neighbor Type = SYM_NEIGH
Otherwise, if N_status == NOT_SYM
The list of neighbor interfaces in a HELLO message can be partial Neighbor Type = NOT_NEIGH
(e.g. due to message size limitations, imposed by the network), the
rule being the following: for each interface a neighbor interface is For each tuple in the Neighbor Set, for which no L_neigh-
heard on, its address is cited with corresponding interface id at bor_iface_addr from an associated link tuple has been advertised by
least once within a predetermined refreshing period, REFRESH_INTER- the previous algorithm, N_neighbor_main_addr is advertised with:
VAL. To keep track of fast connectivity change a HELLO message must
be sent at least every HELLO_INTERVAL period, smaller than or equal - Link Type = UNSPEC_LINK
to REFRESH_INTERVAL.
- Neighbor Type set according to the way described above, in step 2
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
interface, the main address, corresponding to L_neighbor_iface_addr
is simply L_neighbor_iface_addr.
The list of neighbors in a HELLO message can be partial (e.g. due to
message size limitations, imposed by the network), the rule being the
following: each neighbor node MUST be cited at least once within a
predetermined refreshing period, REFRESH_INTERVAL: at least once with
the correct "Link Type", and at least once with the correct "Neighbor
Type" (and, as implemented above, preferably both at the same time).
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.
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 package header) can fit
into a single MAC frame. into a single MAC frame.
Each HELLO message generated is broadcast on each MANET interface of Each HELLO message generated is broadcast by the node to its neigh-
the node. bors.
2.2.4. HELLO Message Processing 4.4. Populating the Link Set
In this section, the terms "Originator Address", "Sender Interface", The Link Set is populated with information on links to neighbor
"Receiver Interface", and "Link Interface" are used. They are defined nodes. The process of populating this set is denoted "link sensing"
bellow and illustrated in the following figure: and is performed using HELLO message exchange, updating a local link
information base in each node.
______________ _____________ Each node should detect the links between itself and neighbor nodes.
| J1 |= -- = |I1 | Uncertainties over radio propagation may make some links unidirec-
| Main -> J2 |= = |I2 <- Main | tional. Consequently, all links MUST be checked in both directions in
| J3 |= -- = |I3 | order to be considered valid.
-------------- -------------
|
______________ /
| K1 |=
| Main -> K2 |=
| |
--------------
J1, J2 and J3 are the addresses of local interfaces on node J. Like- A "link" is described by a pair of interfaces: a local and a remote
wise, I1, I2 and I3 are addresses of local interfaces on node I and interface.
K1 and K2 are addresses of local interfaces on node K. There are
symmetric links between J1 and I3 and between J3 and K1.
The three nodes have selected, respectively, J2, I2 and K2 as their For the purpose of link sensing, each neighbor node (more specifi-
"main addresses". I.e. the Originator Address of all OLSR-messages cally, the link to each neighbor) has an associated status of either
sent by node J will have the Originator Address J2. For node I and K, "symmetric" or "asymmetric". "Symmetric" indicates, that the link to
the main addresses will be I2 and K2, respectively that neighbor node has been verified to be bi-directional, i.e. it is
possible to transmit data in both directions. "Asymmetric" indicates
that HELLO messages from the node have been heard (i.e. communication
from the neighbor node is possible), however it is not confirmed that
this node is also able to receive messages (i.e. communication to the
neighbor node is not confirmed).
A HELLO message, sent by node J, is transmitted on all node J's The information, acquired through and used by the link sensing is
interfaces. Received by node I, the following naming conventions accumulated in the link set.
apply:
- The term "Originator Address" is the main address of the node, 4.4.1. HELLO Message Processing
originating a message. In the example above, the Originator
Address of the HELLO is J2.
- The term "Sender Interface" for the HELLO message is the The "Originator Address" of a HELLO message is the (main) address of
interface over which the HELLO was transmitted. In the example the node, which has emitted the message. In the case where only one
above, the Sender Interface Address is J1. 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.
- The term "Receiver Interface" will be used for the interface Upon receiving a HELLO message, a node SHOULD update its Link Set.
which received the HELLO message. In the example above, node Notice, that a HELLO message MUST neither be forwarded nor be
I's "Receiver Interface" for the HELLO generated by node J is recorded in the duplicate table.
I3.
- The term "Link Interface" will be used in a HELLO message to Upon receiving a HELLO message, the "validity time" MUST be computed
designate on which interface (of the sender of a HELLO mes- from the Vtime field of the message header (see section 3.3.2).
sage) a neighbor is detected. In the example above, K1 is Then, the Link Set SHOULD be updated as follows:
listed in the HELLO message of J with Link Interface J3. The
"Link Interface" is calculated based on the Interface # in the
HELLO message. Notice that an interface address may be listed
several times with different Link Interfaces.
Upon receiving a HELLO message, the node SHOULD update the neighbor 1 Upon receiving a HELLO message, if there exists no link tuple
information corresponding to the sender node address (a node may - with
e.g. for security reasons - wish to restrict updating the neighbor-
table, i.e. ignoring HELLO messages from some nodes).
Notice, that a HELLO message MUST neither be forwarded nor be L_neighbor_iface_addr == Source Address
recorded in the duplicate table.
The Neighbor Set should be updated as follows: a new tuple is created with
1 Upon receiving a HELLO message, if there exists no neighbor L_neighbor_iface_addr = Source Address
tuple with
N_if_addr == Sender Interface Address L_local_iface_addr = Address of the interface which
received the HELLO message
and L_SYM_time = current time - 1 (expired)
L_time = current time + validity time
N_if_id == identifier of the Receiver Interface, 2 The tuple (existing or new) with:
a new tuple is created with L_neighbor_iface_addr == Source Address
N_if_addr = Sender Interface Address is then modified as follows:
N_if_id = identifier of the Receiver Interface 2.1 L_ASYM_time = current time + validity time;
N_SYM_time = current time - 1 (expired) 2.2 if the node finds the address of the interface which
received the HELLO message among the addresses listed in
the link message then the tuple is modified as follows:
N_time = current time + NEIGHB_HOLD_TIME if Link Type is equal to LOST_LINK then
2 The tuple (existing or new) with: L_SYM_time = current time - 1 (i.e. expired)
N_if_addr == Sender Interface Address else if Link Type is equal to SYM_LINK or ASYM_LINK
then
and L_SYM_time = current time + validity time,
N_if_id == identifier of the Receiver Interface, L_time = L_SYM_time + NEIGHB_HOLD_TIME
is then modified as follows: 2.3 L_time = max(L_time, L_ASYM_time)
2.1 N_main_addr = Originator Address. 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
the "validity time" advertised in the generated HELLO. This allows
neighbors to detect the link breakage.
2.2 N_willing = Originator Willingness 4.5. Populating the Neighbor Set
2.4 N_time = max (N_time, current time + A node maintains a set of neighbor tuples, based on the link tuples.
NEIGHB_HOLD_TIME); This information is updated according to changes in the Link Set.
2.5 N_ASYM_time = current time + NEIGHB_HOLD_TIME; The Link Set keeps the information about the links, while the Neigh-
bor Set keeps the information about the neighbors. There is a clear
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
nodes. With multiple interface nodes, there might even be several
links between two nodes.
2.6 if the node finds the Receiver Interface Address among In any case, the formal correspondence between links and neighbors is
the addresses listed in the HELLO with: defined as follows:
Link Interface Address == Sender Interface Address, The "associated neighbor tuple" of a link tuple, is, if it
exists, the neighbor tuple such as:
then, the tuple is modified as follows: N_neighbor_main_addr == main address of L_neigh-
bor_iface_addr
if Link Type == LOST_LINK then The "associated link tuples" of a neighbor tuple, are all the
N_SYM_time = current time - 1 (i.e. expired) link tuples, such as the same condition applies:
else: N_neighbor_main_addr == main address of L_neigh-
bor_iface_addr
N_SYM_time = current time + NEIGHB_HOLD_TIME, The Neighbor Set MUST populated by maintaining the proper correspon-
dence between link tuples and associated neighbor tuples, as follows:
N_time = current time + 2 * Creation
NEIGHB_HOLD_TIME.
The rule for setting N_time is the following: a link loosing its sym- Each time a link appears, that is, each time a link tuple is
metry should still be advertised during at least NEIGHB_HOLD_TIME. created, the associated neighbor tuple MUST be created with
This allows neighbors to detect the link breakage. the following values:
The 2-hop Neighbor Set is updated as follows: N_neighbor_main_addr = main address of L_neigh-
bor_iface_addr (from the link tuple)
1 for each 2-hop interface address listed in the HELLO message The N_status MUST then computed as described in the next step
with Link Type SYM_LINK or MPR_LINK, a 2-hop tuple is created
with:
N_main_addr = Originator Address; Update
N_if_addr = Link Interface Address corresponding Each time a link changes, that is, each time the information
to the 2-hop interface address; of a link tuple is modified, the node MUST ensure that the
N_status of the associated neighbor tuple respects the prop-
erty:
N_2hop_addr = the interface address of the 2-hop If the neighbor has any associated link which is a sym-
neighbor; metrical link (i.e. with L_SYM_time >= current time),
then
N_time = current time + 2HOP_HOLD_TIME. N_status is set to SYM
N_2hop_main_addr = the main address of the node, else N_status is set to NOT_SYM
extracted from the multiple interface association infor-
mation base; if no address is available, the interface
address N_if_addr is used.
This tuple may replace an older similar tuple with same Removal
N_if_addr and N_2hop_addr values.
2 For each 2-hop interface address listed in the HELLO message Each time a link is deleted, that is, each time a link tuple
with Link Type LOST_LINK or ASYM_LINK, all the 2-hop tuples is removed, the associated neighbor tuple MUST be removed if
where: it has no longer any associated links.
N_if_addr == Link Interface Address corresponding to the Those rules ensure that there is exactly one associated neighbor
2-hop interface address, tuple for a link tuple, and that every neighbor tuple has at least
one associated link tuple.
and 4.5.1. HELLO Message Processing
N_2hop_addr == the 2-hop interface address
are deleted. 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
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. Likewise, the "will-
ingness" MUST be computed from the Willingness field of the HELLO
message (see section 4.2).
Based on the information obtained from the HELLO messages, each node Upon receiving a HELLO message, a node SHOULD first update its Link
constructs its MPR selector set. Set as described before It SHOULD then update its Neighbor Set as
follows:
Thus, upon receiving a HELLO message, if a node finds one of its - if the Originator Address is the N_neighbor_main_addr from a
interface addresses in a list with a link type of "MPR", it MUST neighbor tuple included in the Neighbor Set:
update the MPR selector set to contain updated information about the
sender of the HELLO message:
1 If there exists no MPR selector tuple with: then, the neighbor tuple SHOULD be updated as follows:
N_willingness = willingness from the HELLO message
MS_if_addr == Link Interface Address 4.6. Populating the 2-hop Neighbor Set
and 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-
tained through periodic exchange of HELLO messages as described in
this section.
MS_main_addr == Originator Address 4.6.1. HELLO Message Processing
2 If there exists no MPR selector tuple with: 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
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.
MS_if_addr == Link Interface Address Upon receiving a HELLO message from a symmetric neighbor, a node
SHOULD update its 2-hop Neighbor Set. Notice, that a HELLO message
MUST neither be forwarded nor be recorded in the duplicate table.
then a new tuple is created with: Upon receiving a HELLO message, the "validity time" MUST be computed
from the Vtime field of the message header (see section 3.3.2).
MS_if_addr = Link Interface Address 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
3 The tuple is then modified as follows: L_SYM_time >= current time (not expired)
MS_main_addr = Originator Address, (in other words: if the Originator Address is included in the Neigh-
bor Set with N_status = SYM) then the 2-hop Neighbor Set SHOULD then
be updated as follows:
MS_time = current time + NEIGHB_HOLD_TIME. 1 for each address (henceforth: 2-hop neighbor address), listed
in the HELLO message with Neighbor Type equal to SYM_NEIGH or
MPR_NEIGH:
Deletion of MPR selector tuples occurs in case of expiration of the 1.1 if 2-hop neighbor address = main address of receiving
timer or in case of link breakage as described in the neighborhood node:
and 2-hop neighborhood changes section.
2.2.5. Multipoint Relay Selection silently discard the 2-hop neighbor address.
MPRs are used to flood control messages from that node into the net- (in other words: a node is not its own 2-hop neighbor).
work while reducing the number of retransmissions that will occur in
a region. Thus, the concept of MPR is an optimization of a classical 1.2 Otherwise, a 2-hop tuple is created with:
N_neighbor_main_addr = Originator Address;
N_2hop_addr = main address of the 2-hop neighbor;
N_time = current time + validity time.
This tuple may replace an older similar tuple with same
N_neighbor_main_addr and N_2hop_addr values.
2 For each 2-hop node listed in the HELLO message with Neighbor
Type equal to NOT_NEIGH, all 2-hop tuples where:
N_neighbor_main_addr == Originator Address AND
N_2hop_addr == main address of the 2-hop neighbor
are deleted.
4.6.2. Populating the MPR set
MPRs are used to flood control messages from a node into the network
while reducing the number of retransmissions that will occur in a
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 neighborhood. The symmetric links with MPRs are
advertised with Link Type MPR_LINK instead of SYM_LINK in HELLO mes- advertised with Link Type MPR_NEIGH instead of SYM_NEIGH in HELLO
sages. 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 2-hop through the neighbors in the MPR-set, can reach all symmetric strict
neighbors. (Notice that a node, a, which is a direct neighbor of 2-hop neighbors. (Notice that a node, a, which is a direct neighbor
another node, b, is not also a 2-hop neighbor of node b). This means of another node, b, is not also a strict 2-hop neighbor of node b).
that the union of the symmetric neighborhoods of the MPR nodes con- This means that the union of the symmetric neighborhoods of the MPR
tains the symmetric 2-hop neighborhood. MPR set recalculation should nodes contains the symmetric strict 2-hop neighborhood. MPR set
occur when changes are detected in the neighborhood or in the 2-hop recalculation should occur when changes are detected in the neighbor-
neighborhood. hood or in the 2-hop neighborhood.
While it is not essential that the MPR set is minimal, it is essen- While it is not essential that the MPR set is minimal, it is essen-
tial that all 2-hop neighbors can be reached through the selected MPR tial that all strict 2-hop neighbors can be reached through the
nodes. A node SHOULD select an MPR set such that any 2-hop neighbor selected MPR nodes. A node SHOULD select an MPR set such that any
is covered by at least MPR_COVERAGE MPR nodes. With MPR_COVERAGE=1 strict 2-hop neighbor is covered by at least one MPR node. This
the overhead of the protocol is kept at a minimum. In presence of ensures that the overhead of the protocol is kept at a minimum.
mobility and link failure, an MPR_COVERAGE=2 could provide a more
redundant connectivity, for example to support a link failure without
re-routing.
Notice that MPR_COVERAGE can be tuned locally without affecting the
consistency of the protocol. For example, a node can set MPR_COVER-
AGE=2 if it observes many changes in its neighbor information base
caused by mobility, while otherwise keeping MPR_COVERAGE=1.
By default, the MPR set can coincide with the entire symmetric neigh- By default, the MPR set can coincide with the entire symmetric neigh-
bor set. This will be the case at network initialization (and will bor set. This will be the case at network initialization (and will
correspond to classic link-state routing). correspond to classic link-state routing).
The following specifies a proposed heuristic for selection of MPRs 4.6.3. MPR Computation
[2] adapted for multiple interfaces support. It constructs an MPR-set
that enables it to reach any symmetrical 2-hop interface (i.e. any The following specifies a proposed heuristic for selection of MPRs.
interface of a 2-hop neighbor having a symmetrical link with a neigh- It constructs an MPR-set that enables a node to reach any node in the
bor). The following terminology will be used in describing this algo- symmetrical strict 2-hop neighborhood through relaying by one MPR
node. The following terminology will be used in describing this algo-
rithm: rithm:
N: N:
The set of neighbors with which there exists a symmetric link. The set of neighbors with which there exists a symmetric link.
N2: N2:
The set made of the main addresses of the 2-hop neighbor set The set made of the nodes in the symmetric 2-hop neighbor set
excluding (i) the nodes only reachable by members of N with excluding (i) the nodes only reachable by members of N with
willingness zero, (ii) all the nodes in N and (iii) the node N_willingness WILL_NEVER, (ii) all the nodes in N and (iii)
performing the computation. the node performing the computation.
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 member
of N), is defined as the number of symmetric neighbors of node of N), is defined as the number of symmetric neighbors of node
y, EXCLUDING all the members of N and EXCLUDING the node per- y, EXCLUDING all the members of N and EXCLUDING the node per-
forming the computation. forming the computation.
Poorly covered node:
A poorly covered node is a node in N2 which is covered by less
than MPR_COVERAGE nodes in N.
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 willing- 1 Start with an MPR set made of all members of N with N_willing-
ness equal to seven 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 Select as MPRs those nodes in N which cover the poorly covered 3 While there exist nodes in N2 which are not covered by at
nodes in N2. The nodes are then removed from N2 for the rest least one node in the MPR set:
of the computation.
4 While there exist nodes in N2 which are not covered by at
least MPR_COVERAGE nodes in the MPR set:
4.1 For each node in N, calculate the reachability, i.e. the 3.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 one node in the MPR set, and which are reachable
reachable through this one hop neighbor; through this one hop neighbor;
4.2 Select as a MPR the node with highest willingness among 3.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 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 a node in the MPR
in the MPR set. set.
5 As an optimization, process each node y in the MPR set in the 4 As an optimization, process each node y in the MPR set in the
increasing order of their willingness. If all nodes in N2 are increasing order of their willingness. If all nodes in N2 are
still covered by at least MPR_COVERAGE nodes in the MPR set still covered by at least one node in the MPR set excluding y
excluding y and willingness of node y is smaller than seven, and N_willingness of node y is smaller than WILL_ALWAYS, then
then node y is removed from the MPR set. node y is removed from the MPR set.
When the MPR set has been computed, all the corresponding main 4.7. Populating the MPR Selector Set
addresses are stored in the MPR Set.
2.2.6. Neighborhood and 2-hop Neighborhood Changes 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
through HELLO messages.
4.7.1. HELLO Message Processing
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,
information from the HELLO message must be recorded in the MPR
Selector Set.
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
then be updated as follows:
1 If there exists no MPR selector tuple with:
MS_main_addr == Originator Address
then a new tuple is created with:
MS_main_addr = Originator Address
3 The tuple is then modified as follows:
MS_time = current time + validity time.
Deletion of MPR selector tuples occurs in case of expiration of the
timer or in case of link breakage as described in the "Neighborhood
and 2-hop Neighborhood Changes".
4.8. Neighborhood and 2-hop Neighborhood Changes
A change in the neighborhood is detected when: A change in the neighborhood is detected when:
- The N_SYM_time field of a neighbor tuple expires. This is con- - The L_SYM_time field of a link tuple expires. This is consid-
sidered as a neighbor loss if it was the last link with a ered as a neighbor loss if it was the last link with a neigh-
neighbor node (on the contrary, a link with an interface may bor node (on the contrary, a link with an interface may break
break while a link with another interface of the neighbor node while a link with another interface of the neighbor node
remains). remains).
- The N_ASYM_time field of a neighbor tuple expires and - A new link tuple is inserted in the Link Set with a non-
N_SYM_time is expired. The link is then considered lost. 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-
- A new neighbor tuple is inserted in the Neighbor Set with a ered as a neighbor appearance if there was previously no link
non-expired N_SYM_time or a tuple with expired N_SYM_time is with the corresponding neighbor node.
modified so that N_SYM_time becomes non-expired. This is con-
sidered as a neighbor appearance if there was previously no
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 the HELLO message processing tuple expires or is deleted according to section 4.6.
section.
The following processing should occur when changes in the neighbor- The following processing occurs when changes in the neighborhood or
hood or the 2-hop neighborhood are detected: the 2-hop neighborhood are detected:
- In case of neighbor loss, all the 2-hop tuples with - In case of neighbor loss, all the 2-hop tuples with N_neigh-
N_main_addr == Main Address of the neighbor are 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 the MPR selector tuples with
MS_main_addr == Main Address of the neighbor are deleted MS_main_addr == Main Address of the neighbor MUST be deleted
- The MPR set is re-calculated when a neighbor appearance or - The MPR set MUST be re-calculated when a neighbor appearance
loss is detected, or when a change in the 2-hop neighborhood or loss is detected, or when a change in the 2-hop neighbor-
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.
2.2.7. Advanced Neighbor Sensing Functioning 5. Topology Discovery
Established links should be as reliable as possible to avoid data The link sensing and neighbor detection part of the protocol basi-
packet loss. To enhance the reliability of the neighbor sensing mech- cally offers, to each node, a list of neighbors with which it can
anism, the following implementation recommendations should be consid- communicate directly and, in combination with the Packet Format and
ered. Forwarding part, an optimized flooding mechanism through MPRs. Based
on this, topology information is disseminated through the network.
The present section describes what part of the information given by
the link sensing and neighbor detection is disseminated to the entire
network and how it is used to construct routes.
Each neighbor tuple in the neighbor set SHOULD, in addition to what Routes are constructed through advertised links and links with neigh-
is described in previous sections, include a N_pending field, a bors. A node must at least disseminate links between itself and the
N_quality field, and a N_LOST_time field. N_pending is a boolean nodes in its MPR-selector set, in order to provide sufficient infor-
value specifying if the link is considered pending (i.e. the link is mation to enable routing.
not considered established). N_quality is a dimensionless number
between 0 and 1 describing the quality of the link. N_LOST_time is a
timer for declaring a link as lost when an established link becomes
pending.
HELLO message generation should consider those new fields as follows: 5.1. TC Message Format
1 if N_LOST_time is not expired, the link is advertised with a The proposed format of a TC message is
link type of LOST_LINK;
2 otherwise, if N_LOST_time is expired and N_pending is set to 0 1 2 3
"true", the link SHOULD NOT be advertised at all; 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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Advertised neighbor Main Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Advertised neighbor Main Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
3 otherwise, if N_LOST_time is expired and N_pending is set to This is sent as the data-portion of the general message format with
"false", the link is advertised as described in the HELLO mes- the "Message Type" set to TC_MESSAGE. The time to live SHOULD be set
sage generation section. 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
in section 15.3.
A node considers that it has a symmetric link for each neighbor tuple Advertised Neighbor Sequence Number (ANSN)
where
1 N_LOST_time is expired, AND A sequence number is associated with the advertised neighbor
set. Every time a node detects a change in its advertised
neighbor set, it increments this sequence number ("Wrap-
around" is handled as described in section 16). This
number is sent in this ANSN field of the TC message to keep
track of the most recent information. When a node receives a
TC message, it can decide on the basis of this Advertised
Neighbor Sequence Number, whether or not the received informa-
tion about the advertised neighbors of the originator node is
more recent than what it already has.
2 N_pending is "false", AND Advertised Neighbor Main Address
3 N_SYM_time is not expired. This field contains the main address of a neighbor node. All
main addresses of the advertised neighbors of the Originator
node are put in the TC message. If the maximum allowed message
size (as imposed by the network) is reached while there are
still advertised neighbor addresses which have not been
inserted into the TC-message, more TC messages will be gener-
ated until the entire advertised neighbor set has been sent.
Extra main addresses of neighbor nodes may be included, if
redundancy is desired.
This should be taken as definition for computing the symmetric neigh- Reserved
borhood when computing the MPR set.
Apart from the above points, what has been described previously does This field is reserved, and MUST be set to "0000000000000000"
not interfere with these advanced neighbor sensing fields in the for compliance with this document.
neighbor tuples. The N_quality, N_pending and N_LOST_time fields are
exclusively updated according to the present section. Advanced neigh-
bor sensing does not modify the function of any other fields in the
neighbor tuples.
This advanced functioning is described as separately as possible to 5.2. Topology Information Base
increase readability.
2.2.7.1. Link Hysteresis 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.
The link between a node and some of its neighbor interfaces might be Thus, for each destination in the network, a "Topology Tuple"
"bad", i.e. from time to time let HELLOs pass through only to fade (T_dest_addr, T_last_addr, T_seq, T_time) is recorded. T_dest_addr is
out immediately after. In this case, the neighbor information base the main address of a node, which may be reached in one hop from the
would contain a bad link for at least NEIGHB_HOLD_TIME. In absence of node with the main address T_last_addr. Typically, T_last_addr is a
link layer notification, such a bad link might affect routing badly. MPR of T_dest_addr. T_seq is a sequence number, and T_time specifies
To cope with such unstable links, the following hysteresis strategy the time at which this tuple expires and *MUST* be removed.
SHOULD be adopted.
For each neighbor interface NI heard by interface I, the N_quality In a node, the set of Topology Tuples are denoted the "Topology Set".
field of the corresponding Neighbor Tuple determines the establish-
ment of the link. The value of N_quality is compared to two thresh-
olds HYST_THRESHOLD_HIGH, HYST_THRESHOLD_LOW, fixed between 0 and 1
and such that HYST_THRESHOLD_HIGH >= HYST_THRESHOLD_LOW.
The N_pending field is set according to the following: 5.3. Advertised Neighbor Set
1 if N_quality > HYST_THRESHOLD_HIGH: 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. If, for some reason, it is
required to distribute redundant TC information, refer to section
11.
N_pending = false The sequence number (ANSN) associated with the advertised neighbor
set is also sent with the list. The ANSN number MUST be incremented
when links are removed from the advertised neighbor set; the ANSN
number SHOULD be incremented when links are added to the advertised
neighbor set.
N_LOST_time = current time - 1 (expired) 5.4. TC Message Generation
2 otherwise, if N_quality < HYST_THRESHOLD_LOW: In order to build the topology information base needed, each node,
which has been selected as MPR, broadcasts Topology Control (TC) mes-
sages. TC messages are flooded to all nodes in the network and take
advantage of MPRs. MPRs enable a better scalability in the distribu-
tion of topology information [1].
N_pending = true 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
TC messages describing the advertised link set of a node MUST be com-
plete within a certain refreshing period (TC_INTERVAL). The informa-
tion diffused in the network by these TC messages will help each node
calculate its routing table.
N_LOST_time = min (N_time, current time + When the advertised link set of a node becomes empty, it SHOULD still
NEIGHB_HOLD_TIME) send (empty) TC-messages during the a duration equal to "validity
time" of its TC-messages to invalidate the previous TC-messages. It
SHOULD then stop sending TC-messages until some node is inserted in
its advertised link set.
(the link is then considered as lost according to the A node MAY transmit additional TC-messages to increase its reactive-
Neighborhood and 2-hop neighborhood changes section and ness to link failures. When a change to the MPR selector set is
this may produce a neighbor loss). detected and this change can be attributed to a link failure, a TC-
message SHOULD be transmitted after a shorter interval than TC_INTER-
VAL.
3 otherwise, if HYST_THRESHOLD_LOW <= N_quality <= HYST_THRESH- 5.5. TC Message Forwarding
OLD_HIGH:
N_pending and N_LOST_time remain unchanged. TC messages are broadcasted and retransmitted by the MPRs in order to
diffuse the messages in the entire network. TC messages MUST be
forwarded according to the "default forwarding algorithm".
The condition for considering a link established is thus stricter 5.6. TC Message Processing
than the condition for loosing it.
As a basic implementation requirement, an estimation of the link Upon receiving a TC message, the "validity time" MUST be computed
quality must be maintained and stored in the N_quality field. If some from the Vtime field of the message header (see section 3.3.2).
measure of the signal/noise level on a received message is available The topology set SHOULD then be updated as follows (using section
(e.g. as a link layer notification), then it can be used as estima- 16 for comparison of ANSN):
tion after normalization.
If no signal/noise information is available from the link layer, an 1 If the sender interface (NB: not originator) of this message
algorithm such as the following can be utilized. The algorithm is is not in the symmetric neighborhood of this node, the message
parameterized by a scaling parameter HYST_SCALING which is a number MUST be discarded.
fixed between 0 and 1. For each neighbor interface NI heard by inter-
face I, the first time NI is heard by I, N_quality is set to
HYST_SCALING (N_pending is set to true and N_LOST_time to current
time - 1).
A tuple is updated according to two rules. Every time an OLSR packet 2 If there exist some tuple in the topology set where:
emitted by NI is received by I, the stability rule is applied:
N_quality = (1-HYST_SCALING)*N_quality + HYST_SCALING. T_last_addr == originator address AND
When an OLSR packet emitted by NI is lost by I, the instability T_seq > ANSN,
rule is applied:
N_quality = (1-HYST_SCALING)*N_quality. then further processing of this TC message MUST NOT be per-
formed and the message MUST be silently discarded (case: mes-
sage received out of order).
The loss of OLSR packet is detected by tracking the missing Packet 3 All tuples in the topology set where:
Sequence Numbers on a per interface basis and by long period of
silence. If no HELLO message has been received for a HELLO_INTERVAL
period, a loss of HELLO message is detected.
2.2.7.2. Optional Link layer notification T_last_addr == originator address AND
OLSR is designed not to impose or expect any specific information T_seq < ANSN
from the link layer. However, if information from the link-layer is
available, a node MAY use this as described in this section.
If link layer information describing connectivity to neighboring MUST be removed from the topology set.
nodes is available (i.e. loss of connectivity such as through absence
of a link layer acknowledgment), this information is used in addition
to the information from the HELLO-messages to maintain the neighbor
information base and the MPR selector set.
Thus, upon receiving a link-layer notification that the link between 4 For each of the advertised neighbor main address received in
a node and a neighbor interface is broken, the following actions are the TC message:
taken with respect to neighbor sensing:
1 if the link to a neighboring symmetric or asymmetric interface 4.1 If there exist some tuple in the topology set where:
is broken, the corresponding neighbor tuple is modified:
N_LOST_time and N_time are set to current time +
NEIGHB_HOLD_TIME.
2 this is considered as a link loss and the appropriate process- T_dest_addr == advertised neighbor main address, AND
ing described in the neighborhood and 2-hop neighborhood
changes section should be performed.
2.3. Topology Discovery T_last_addr == originator address,
The Neighbor Sensing part of the protocol basically offers to each then the holding time of that tuple MUST be set to:
node a list of neighbors with which it can communicate directly and
an optimized flooding mechanism through MPRs. Based on this mecha-
nism, topology information is disseminated through the network. The
present section describes what part of the information given by the
Neighbor Sensing is disseminated and how it is used to construct
routes.
Routes are constructed through advertised links and links with neigh- T_time = current time + validity time.
bors. A node must at least disseminate its MPR-selector set, in order
to provide sufficient information to enable routing. If a node has
multiple interfaces, it must also disseminate the list of its inter-
face addresses.
2.3.1. TC Message Format 4.2 Otherwise, a new tuple MUST be recorded in the topology
set where:
The proposed format of a TC message is T_dest_addr = advertised neighbor main address,
0 1 2 3 T_last_addr = originator address,
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| MSSN | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Advertized neighbor Main Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Advertized neighbor Main Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This is sent as the data-portion of the general message format with T_seq = ANSN,
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 net-
work.
MPR Selector Sequence Number (MSSN) T_time = current time + validity time.
A sequence number is associated with the advertized neighbor 5.7. Routing Table Calculation
set. Every time a node detects a change in its advertized
neighbor set, it increments this sequence number. This number
is sent in this MSSN field of the TC message to keep track of
the most recent information. When a node receives a TC mes-
sage, it can decide on the basis of this MPR Selector Sequence
Number, whether or not the received information about the MPR
selectors of the originator node is more recent than what it
already has.
Advertized Neighbor Main Address Each node maintains a routing table which allows it to route data,
destined for the other nodes in the network. The routing table is
based on the information contained in the link set and the topology
set. Therefore, if any of these sets are changed, the routing table
is re-calculated to update the route information about each destina-
tion in the network. The route entries are recorded in the routing
table in the following format:
This field contains the main address of a neighbor node. All 1. R_dest_addr R_next_addr R_dist R_iface_addr
main addresses of the MPR selectors of the Originator node are 2. R_dest_addr R_next_addr R_dist R_iface_addr
put in the TC message. If the maximum allowed message size (as 3. ,, ,, ,, ,,
imposed by the network) is reached while there are still MPR
selector addresses which have not been inserted into the TC-
message, more TC messages will be generated until the entire
MPR selector set has been sent. Extra main addresses of neigh-
bor nodes may be included, if redundancy is desired.
Reserved 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
R_dest_addr is estimated to be R_dist hops away from the local node,
and that the symmetric neighbor node with interface address
R_next_addr is the next hop node in the route to R_dest_addr, and
this one hop is reachable through the local interface R_iface_addr.
Entries are recorded in the table for each destination in the network
for which the route is known. All the destinations for which the
route is broken or partially known are not entered in the table.
This field is reserved for future usage, and MUST be set to The routing table is updated when a change is detected in the neigh-
"0000000000000000" for compliance with this draft. bor information base and the topology set (and also the Multiple
Interface Association Information Base, section 7.3.1, and the
Host and Network Association Information Base, section 8,
if applicable). More precisely, the routing table is re-calculated in
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-
erate or trigger any messages to be transmitted, neither in the net-
work, nor in the one-hop neighborhood.
2.3.2. Topology Information Base 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
any symmetric neighbor of X (with Link Type equal to SYM_LINK) 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.
Each node in the network maintains topological information about the The following procedure is given as an example to calculate (or re-
network. This information is acquired from TC-messages and is used calculate) the routing table :
for routing table calculations.
Thus, for each destination in the network, a "Topology Tuple" 1 All the entries from the routing table are removed.
(T_dest, T_last, T_seq, T_time) is recorded. T_dest is the main
address of a node, which may be reached in one hop from the node with
the main address T_last. Typically, T_last is a MPR of T_dest. 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". 2 The new routing entries are added starting with the symmetric
neighbors (h=1) as the destination nodes. I.e. for each link
tuple in the link set where:
2.3.3. Advertized Neighbor Set L_SYM_time >= current time
A TC message is sent by a node in the network to declare a set of (there is a symmetric link to the neighbor), a new routing
links, called the advertized neighbor set, which MUST include at entry is recorded in the routing table with:
least the links to all nodes of its MPR Selector set, i.e., the
neighbors which have selected the sender node as a MPR.
The sequence number (MSSN) associated with the advertized neighbor R_dest_addr = main address of the neighbor with inter-
set is also sent with the list. The MSSN number MUST be incremented face L_neighbor_iface_addr;
when links are removed from the advertized neighbor set; the MSSN
number SHOULD be incremented when links are added to the advertized
neighbor set.
In order to provide redundancy to the topology information base, the R_next_addr = L_neighbor_iface_addr;
advertized neighbor set of a node can contain links to neighbor nodes
which are not in the MPR selector set of the node. The advertized
neighbor set can be the whole neighbor set of the node. In this case
the nodes receiving the TC message will get the knowledge of all the
adjacent links of the sender node. The advertized neighbor set can be
built according to the following rule based on a local parameter
called TC_REDUNDANCY.
1 if the TC_REDUNDANCY parameter of the node is zero, then its R_dist = 1;
advertized neighbor set is limited to the MPR selector set.
2 If the TC_REDUNDANCY parameter of the node is one, then its R_iface_addr = L_local_iface_addr of the entry.
advertized neighbor set is the union of its MPR set and its
MPR selector set.
3 If the TC_REDUNDANCY parameter of the node is two, then its If in the above, R_dest_addr is distinct from R_next, another
advertized neighbor set is its neighbor set. new routing entry with MUST be added, with:
A node with willingness equal to zero SHOULD have TC_REDUNDANCY also R_dest_addr = L_neighbor_iface_addr;
equal to zero.
2.3.4. TC Message Generation R_next_addr = L_neighbor_iface_addr;
In order to build the topology information base needed, each node, R_dist = 1;
which has been selected as MPR, broadcasts Topology Control (TC) mes-
sages. TC messages are flooded to all nodes in the network and take
advantage of MPRs. MPRs enable a better scalability in the distribu-
tion of topology information [1].
The list of addresses can be partial in each TC message (e.g. due to R_iface_addr = L_local_iface_addr.
message size limitations, imposed by the network), but parsing of all
TC messages describing the advertized neighbor set of a node MUST be
complete within a certain refreshing period (TC_INTERVAL). The infor-
mation diffused in the network by these TC messages will help each
node calculate its routing table.
A node which has an empty advertized neighbor set may not generate 3 The new route entries for the destination nodes h+1 hops away
any TC message. Indeed, when its advertized neighbor set becomes are recorded in the routing table. The following procedure
empty, it SHOULD still send (empty) TC-messages during TOP_HOLD_TIME MUST be executed for each value of h, starting with h=1 and
to invalidate the previous TC-messages. It MAY then stop sending TC- incrementing it by 1 each time. The execution will stop if no
messages until some node is inserted in its advertized neighbor set. new entry is recorded in an iteration.
A node MAY transmit additional TC-messages to increase its reactive- 3.1 For each topology entry in the topology table, if its
ness to link failures. I.e. when a change to the MPR selector set is T_dest_addr does not correspond to R_dest_addr of any
detected and this change can be attributed to a link failure, a TC- route entry in the routing table AND its T_last_addr cor-
message SHOULD be transmitted after a shorter interval than TC_INTER- responds to R_dest_addr of a route entry whose R_dist is
VAL. equal to h, then a new route entry MUST be recorded in
the routing table (if it does not already exist) where:
2.3.5. TC Message Processing R_dest_addr = T_dest_addr;
TC messages are broadcasted and retransmitted by the MPRs in order to R_next_addr = R_next_addr of the recorded route
diffuse the messages in the entire network. entry whose R_dest_addr == T_last_addr
In this section, the term "originator" is used to designate the node R_dist = h+1; and
from which the message originally originated, while the term "sender"
is used to designate the node from which the message was received
(i.e. the "last hop" of the message).
The tuples in the topology set are recorded with the topology infor- R_iface_addr = R_iface_addr of the recorded route
mation that is exchanged through TC messages, according to the fol- entry whose R_dest_addr == T_last_addr.
lowing algorithm:
1 If the sender interface (NB: not originator) of this message 3.2 Several topology entries may be used to select a next hop
is not in the symmetric neighborhood of this node, the message R_next_addr for reaching the node R_dest_addr. When h=1,
is discarded. ties should be broken such that nodes with highest will-
ingness and MPR selectors are preferred as next hop.
2 A tuple is inserted into the duplicate table to prevent it If the MPR set has changed, a TC message containing the new MPR
from being processed again with: selector set SHOULD be generated.
D_addr = originator address 6. Node Configuration
D_seq_num = Message Sequence This section outlines how a node should be configured, in order to
operate in an OLSR manet.
D_time = current time + D_HOLD_TIME. 6.1. Address Assignment
3 If there exist some tuple in the topology set where: The nodes in the MANET network SHOULD be assigned addresses within a
defined address sequence. I.e., the nodes in the MANET SHOULD be
addressable through a network address and a netmask.
T_last == originator address AND Likewise, the nodes in each associated network SHOULD be assigned
addresses from a defined address sequence, distinct from that being
used in the MANET.
T_seq > MSSN, 6.2. Routing Configuration
then no further processing of this TC message is performed and Any MANET node with associated networks or hosts SHOULD be configured
the message is silently discarded (case: message received out such that it has routes set up to the interfaces with associated
of order). hosts or network.
4 All tuples in the topology set where: 6.3. Data Packet Forwarding
T_last == originator address AND OLSR itself does not perform packet forwarding. Rather, it maintains
the routing table in the underlying operating system, which is
assumed to be forwarding packets as specified in RFC1812.
T_seq < MSSN 7. Multiple OLSR Interfaces
are removed from the topology set. 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.
5 For each of the advertized neighbor main address received in A node with only a single OLSR interface, which wishes to participate
the TC message: in a network of nodes with multiple OLSR interfaces SHOULD implement
the provisions described in section #REF:midmf and 7.7.
5.1 If there exist some tuple in the topology set where: For nodes with multiple OLSR interfaces, participating in the OLSR
routing domain, the provisions in this section MUST be applied.
T_dest == advertized neighbor main address, AND 7.1. Terminology
T_last == originator address, For the purpose of Multiple OLSR Interfaces, the following terminol-
ogy is introduced or refined:
then the holding time of that tuple is set to: Multiple Interface Node
T_time = current time + TOP_HOLD_TIME. A node which has multiple interfaces, participating in an
OLSR routing domain.
5.2 Otherwise, a new tuple is recorded in the topology set Single Interface Node
where:
T_dest = advertized neighbor main address, A node which has a single interface, participating in an
OLSR routing domain.
T_last = originator address, 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.
T_seq = MSSN, Main Address
T_time = current time + TOP_HOLD_TIME. 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.
6 If the sender address is an interface address of a MPR selec- A multiple interface node MUST choose one of its inter-
tor of this node and if the time to live of the message is face addresses as its "main address". It is of no impor-
greater than '1', the message MUST be forwarded according to tance which address is chosen, however a node SHOULD
the following: always use the same address as its main address.
6.1 The TTL of the message is reduced by one. 7.2. Multiple Interface Functioning
6.2 The hop-count of the message is increased by one 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.
6.3 The message is broadcasted on all interfaces (Notice: The This section outlines the few additional provisions which must be
remaining fields of the message header SHOULD be left made to accommodate for multiple interfaces in OLSR.
unmodified.)
2.3.6. Multiple Interface Association 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 Each node in the network maintains interface information about the
other nodes in the network. This information acquired from MID-mes- other nodes in the network. This information acquired from MID-mes-
sages, emitted by nodes with multiple interfaces participating in the sages, emitted by nodes with multiple interfaces participating in the
MANET, and is used for routing table calculations. MANET, and is used for routing table calculations.
2.3.6.1. Multiple Interface Association Information Base 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" For each destination in the network, "Interface association Tuples"
(I_if_addr, I_main_addr, I_time) are recorded. I_if_addr is an inter- (I_iface_addr, I_main_addr, I_time) are recorded. I_iface_addr is an
face address of a node, I_main_addr is the main address of this node. interface address of a node, I_main_addr is the main address of this
I_time specifies the time at which this tuple expires and *MUST* be node. I_time specifies the time at which this tuple expires and
removed. *MUST* be removed.
In a node, the set of Interface association Tuples is denoted the In a node, the set of Interface association Tuples is denoted the
"Interface association Set". "Interface association Set".
2.3.6.2. MID Message Format 7.3.2. MID Message Format
The proposed format of a MID message is The proposed format of a MID 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Interface Address | | Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Interface Address | | Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... | | ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This is sent as the data-portion of the general message format with This is sent as the data-portion of the general packet format
the "Message Type" set to MID_MESSAGE. The time to live SHOULD be described in section 3.4, with the "Message Type" set to
set to 255 (maximum value) to diffuse the message into the entire MID_MESSAGE. The time to live SHOULD be set to 255 (maximum value) to
network. 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 Interface Address
This field contains the address of an interface of the node This field contains the address of an interface of the node
other than its main address (already indicated in the origina- other than its main address (which already indicated in the
tor address). All interface addresses other than the main originator address).
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 interface addresses which
have not been inserted into the MID-message, more MID messages
are generated until the entire interface addresses set has
been sent.
2.3.6.3. MID Message Generation 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.
In order to build the interface association information base, each 7.3.3. MID Message Generation
node with multiple interfaces broadcast Multiple Interface Declara-
tion (MID) messages. MID messages are flooded to all nodes in the
network and take advantage of MPRs.
A MID message is sent by a node in the network to declare its multi- 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 ple interfaces (if any). I.e., the MID message contains the list of
interface addresses which are associated to its main address. The interface addresses which are associated to its main address. The
list of addresses can be partial in each TC message (e.g. due to mes- list of addresses can be partial in each MID message (e.g. due to
sage size limitations, imposed by the network), but parsing of all message size limitations, imposed by the network), but parsing of all
MID messages describing a nodes interface set MUST be complete within MID messages describing the interface set from a node MUST be com-
a certain refreshing period (MID_INTERVAL). The information diffused plete within a certain refreshing period (MID_INTERVAL). The informa-
in the network by these MID messages will help each node to calculate tion diffused in the network by these MID messages will help each
its routing table. A node which has only a single interface address node to calculate its routing table. A node which has only a single
participating in the MANET (i.e. running OLSR) and this address is interface address participating in the MANET (i.e. running OLSR),
its main address, MUST NOT generate any MID message. MUST NOT generate any MID message.
A node with more interfaces, where only one is participating in the 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 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. as well as to a MANET) MUST NOT generate any MID messages.
2.3.6.4. MID Message Processing 7.3.4. MID Message Forwarding
MID messages are broadcasted and retransmitted by the MPRs in order MID messages are broadcasted and retransmitted by the MPRs in order
to diffuse the messages in the entire network. 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.
In this section, the term "originator" is used to designate the node 7.3.5. MID Message Processing
from which the message originally originated, while the term "sender"
is used to designate the node from which the message was received
(i.e. the "last hop" of the message).
The tuples in the multiple interface association set are recorded The tuples in the multiple interface association set are recorded
with the information that is exchanged through MID messages, follow- with the information that is exchanged through MID messages.
ing the following algorithm:
1 If the sender (NB: not originator) of this message is not in Upon receiving a MID message, the "validity time" MUST be computed
the symmetric neighborhood of this node, the message is dis- from the Vtime field of the message header (as described in the sec-
carded. tion 4.2). The Multiple Interface Association Informa-
tion Base SHOULD then be updated as follows:
2 A tuple is inserted into the duplicate table to prevent it For each interface address listed in the MID message:
from being processed again with:
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_addr = originator address
D_seq_num = Message Sequence 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. D_time = current time + D_HOLD_TIME.
3 For each of the interface address received in the MID message: The receiving interface address is added to D_inter-
face_list.
3.1 If there exist some tuple in the interface association D_retransmitted is set to true if and only if the message
set where: will be retransmitted according to step 4.
I_if_addr == interface address, AND Otherwise an entry in the duplicate set is recorded with:
I_main_addr == originator address, D_addr = originator address
then the holding time of that tuple is set to: D_seq_num = Message Sequence Number
I_time = current time + MID_HOLD_TIME. D_time = current time + D_HOLD_TIME.
3.2 Otherwise, a new tuple is recorded in the interface asso- D_interface_list contains the receiving interface
ciation set where: address.
I_if_addr = interface address, D_retransmitted is set to true if and only if the message
will be retransmitted according to step 4.
I_main_addr = originator address, If, and only if, according to step 4, the message must be retransmit-
ted then the following steps are followed:
I_time = current time + MID_HOLD_TIME. 5 The TTL of the message is reduced by one.
4 If the sender address is an interface address of a MPR selec- 6 The hop-count of the message is increased by one
tor of this node and if the time to live of the message is
greater than '1', the message MUST be forwarded according to
the following:
4.1 The TTL of the message is reduced by one. 7 The message is broadcasted on all interfaces (Notice: The
remaining fields of the message header SHOULD be left unmodi-
fied.)
4.2 The hop-count of the message is increased by one 8. Non OLSR Interfaces
4.3 The message is broadcasted on all interfaces (Notice: The A node MAY be equipped with multiple interfaces, some of which do not
remaining fields of the message header SHOULD be left participate in the OLSR manet. These non-OLSR interfaces may be point
unmodified.) to point connections to other singular hosts or may connect to sepa-
rate networks.
2.3.7. Associated Networks and Hosts 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
route information to the OLSR manet.
A node MAY provide access to a set of associated hosts. I.e., a node Injecting routing information from the OLSR manet to non-OLSR inter-
may act as a "gateway" between the MANET and a number of associated faces is outside the scope of this specification. It should be clear,
hosts and/or subnets, not running OLSR and thus not participating in however, that the routing information for the OLSR manet can be
the MANET. Thus, a node SHOULD be able to inject routing information extracted from the topology table (see section 5.2) or directly
describing these associated hosts or networks into MANET, as SHOULD from the routing table of OLSR, and must be injected onto the non-
all nodes be capable of interpreting such information. OLSR interfaces following whatever mechanism (routing protocol,
static configuration etc.) is provided on these interfaces.
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
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", described previously. Where, in the "Multiple Interface Asso- faces", where all the interfaces are participating in the MANET
ciations", all the described interfaces were participating in the through running the OLSR protocol. Multiple interfaces participating
MANET through running the OLSR protocol, this section addresses the in the OLSR manet is described in section 7.
interfaces which do not participate. This is, e.g., the case where a
node has both a wireless interface (participating in the MANET) and a
wired interface, through which a number of hosts statically connect
(to the nodes in the MANET).
To accomplish this, a node, to which there are associated hosts In order to provide this capability of injecting external routing
and/or networks, periodically issues an Host and Network Association information into an OLSR manet, a node with such non-MANET interfaces
(HNA) message, containing sufficient information for the recipients periodically issues an Host and Network Association (HNA) message,
to construct an appropriate routing table. containing sufficient information for the recipients to construct an
appropriate routing table.
2.3.7.1. HNA Message Format 8.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 42, line 45 skipping to change at page 56, line 18
| 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 and the TTL field set to 255. "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-
tion 15.3.
It should be noticed, that the HNA-message can be considered as a It should be noticed, that the HNA-message can be considered as a
"generalized version" of the TC-message: the originator of both the "generalized version" of the TC-message: the originator of both the
HNA and TC messages announce "reachability" to some other host(s). In HNA- and TC-messages announce "reachability" to some other host(s).
the TC-message, no netmask is required, since all reachability is In the TC-message, no netmask is required, since all reachability is
announced on a per-host basis. In HNA-messages, announcing reachabil- announced on a per-host basis. In HNA-messages, announcing reachabil-
ity to an address sequence through a network- and netmask address is ity to an address sequence through a network- and netmask address is
typically preferred over announcing reachability to individual host typically preferred over announcing reachability to individual host
addresses. 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.
2.3.7.2. Host and Network Association Information Base 8.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" (GW_main_addr, NET_addr, NET_mask, GS_time), where tuples" (A_gateway_addr, A_network_addr, A_netmask, A_time), where
GW_main_addr is the main address of the gateway, NET_addr and A_gateway_addr is the address of a OLSR interface of the gateway,
NET_mask specifies the network address and netmask of a network, A_network_addr and A_netmask specifies the network address and net-
reachable through this gateway, and GS_time specifies the time at mask of a network, reachable through this gateway, and A_time speci-
which this tuple expires and hence *MUST* be removed. fies the time at which this tuple expires and hence *MUST* be
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".
2.3.7.3. HNA Message Generation 8.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 and of (network address, netmask) corresponding to the connected hosts
networks. HNA-messages SHOULD be transmitted periodically every and networks. HNA-messages SHOULD be transmitted periodically every
HNA_INTERVAL. HNA_INTERVAL. The Vtime is set accordingly to the value of
HNA_HOLD_TIME, as specified in section 15.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.
2.3.7.4. HNA Message Processing 8.4. HNA Message Forwarding
In this section, the term "originator address" is used to designate
the main address of the node which originally issued the HNA-message.
Upon receiving a HNA-message, the node performs the following:
1 An entry in the duplicate set is recorded for this message
with:
D_addr = originator address
D_seq_num = Message Sequence Number
D_time = current time + D_HOLD_TIME.
2 For each (network address, netmask) pair in the message:
2.1 if an entry in the association set already exists, where:
GW_main_addr == originator address
NET_addr == network address
NET_mask == netmask
then the holding time for that tuple is set to: Upon receiving a HNA message, and thus following the rules of section
3, in this version of the specification, the message MUST be
forwarded according to section 3.4.
GW_time = current time + GW_HOLDING_TIME 8.5. HNA Message Processing
2.2 otherwise, a new tuple is recorded with: In this section, the term "originator address" is used to designate
the main address on the OLSR manet of the node which originally
issued the HNA-message.
GW_main_addr == originator address Upon processing a HNA-message, the "validity time" MUST be computed
from the Vtime field of the message header (see section 3.3.2).
The association base SHOULD then be updated as follows:
NET_addr == network address 1 For each (network address, netmask) pair in the message:
NET_mask == netmask 1.1 if an entry in the association set already exists, where:
GW_time = current time + GW_HOLDING_TIME A_gateway_addr == originator address
3 If the sender address is an interface address of a MPR selec- A_network_addr == network address
tor of this node and if the time to live of the message is
greater than '1', the message MUST be forwarded according to
the following:
3.1 The TTL of the message is reduced by one. A_netmask == netmask
3.2 The hop-count of the message is increased by one then the holding time for that tuple MUST be set to:
3.3 The message is broadcasted on all interfaces (Notice: The
remaining fields of the message header SHOULD be left
unmodified.)
2.3.8. Routing Table Calculation A_time = current time + validity time
Each node maintains a routing table which allows it to route data, 1.2 otherwise, a new tuple MUST be recorded with:
destined for the other nodes in the network. The routing table is
based on the information contained in the neighbor sensing informa-
tion base, the interface association set, the topology set and the
host and network association set. Therefore, if any of these tables
are changed, the routing table is re-calculated to update the route
information about each destination in the network. The route entries
are recorded in the routing table in the following format:
1. R_dest R_next R_dist R_if_id A_gateway_addr = originator address
2. R_dest R_next R_dist R_if_id
3. ,, ,, ,,
Each entry in the table consists of R_dest, R_next, R_dist, and A_network_addr = network address
R_if_id which specifies that the node identified by R_dest is esti-
mated to be R_dist hops away from the local node, and that the sym-
metric neighbor node with interface address R_next is the next hop
node in the route to R_dest, and this one hop is reachable through
the local interface
R_if_id. Entries are recorded in the table for each destination in
the network for which the route is known. All the destinations for
which the route is broken or partially known are not entered in the
table.
This routing table is updated when a change is detected in the neigh- A_netmask = netmask
bor information base, the interface association set or the topology
set. More precisely, it is re-calculated in case of neighbor appear-
ance or loss, or when a topology tuple is created or removed. The
update of this routing information does not generate or trigger any
messages to be transmitted, neither in the network, nor in the one-
hop neighborhood.
To construct the routing table of node X, a shortest path algorithm A_time = current time + validity time
is run on the directed graph containing the arcs X -> Y where Y is
any symmetric neighbor of X (with Link Type SYM_LINK or MPR_LINK) and
the arcs U -> V where there exists an entry in the topology set with
V as T_dest and U as T_last.
The following procedure is given as an example to calculate (or re- 8.6. Routing Table Calculation
calculate) the routing table :
1 All the entries from the routing table are removed. In addition to the routing table computation as described in section
5.7, the host and network association set MUST be added as
follows:
2 The new routing entries are added starting with the symmetric 1 For each tuple in the routing set, an entry in the routing
neighbors (h=1) as the destination nodes. I.e. for each neigh- table MUST be recorded, with:
bor tuple in the neighbor set where:
N_LOST_time < current time AND R_dest_addr = A_network_addr/A_netmask
N_pending == false AND R_next_addr = the next hop on the path from the node
to A_gateway_addr
N_SYM_time >= current time R_dist = dist to A_gateway_addr
(there is a symmetric link to the neighbor), a new routing R_next_addr and R_iface_addr MUST be set to the same val-
entry is recorded in the routing table with: ues as the tuple from the routing set with R_dest_addr ==
A_gateway_addr.
R_dest = N_main_addr of the neighbor; 9. Link Layer Notification
R_next = N_if_addr of the neighbor interface; OLSR is designed not to impose or expect any specific information
from the link layer. However, if information from the link-layer is
available, a node MAY use this as described in this section.
R_dist = 1; If link layer information describing connectivity to neighboring
nodes is available (i.e. loss of connectivity such as through absence
of a link layer acknowledgment), this information is used in addition
to the information from the HELLO-messages to maintain the neighbor
information base and the MPR selector set.
R_if_id = N_if_id of the entry. Thus, upon receiving a link-layer notification that the link between
a node and a neighbor interface is broken, the following actions are
taken with respect to link sensing:
If N_if_addr is distinct from N_main_addr, another new routing Each link tuple in the local link set SHOULD, in addition to what is
entry with is added, with: described in section 4.1, include a L_LOST_LINK_time field.
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
what is reccomended in section 10.3, thus link hysteresis
and link layer notifications can coexist).
R_dest = N_main_addr; HELLO message generation should consider those new fields as follows:
R_next = N_if_addr; 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 ;
R_dist = 1; 1 if the link to a neighboring symmetric or asymmetric interface
is broken, the corresponding link tuple is modified:
L_LOST_LINK_time and L_time are set to current time +
NEIGHB_HOLD_TIME.
R_if_id = N_if_id. 2 this is considered as a link loss and the appropriate process-
ing described in section 4.8 should be performed.
3 The new route entries for the destination nodes h+1 hops away 10. Link Hysteresis
are recorded in the routing table. The following procedure is
executed for each value of h, starting with h=1 and increment-
ing it by 1 each time. The execution will stop if no new entry
is recorded in an iteration.
3.1 For each topology entry in the topology table, if its Established links should be as reliable as possible to avoid data
T_dest does not correspond to R_dest of any route entry packet loss. To enhance the reliability of the link sensing mecha-
in the routing table AND its T_last corresponds to R_dest nism, the following implementation recommendations should be consid-
of a route entry whose R_dist is equal to h, then a new ered.
route entry is recorded in the routing table (if it does
not already exist) where:
R_dest = T_dest; 10.1. Local Link Set
R_next = R_next of the recorded route entry whose Each link tuple in the local link set SHOULD, in addition to what is
R_dest == T_last described in section 4.1, include a L_link_pending field, a
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.
the link is not considered established). L_link_quality is a dimen-
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
established link becomes pending.
R_dist = h+1; and 10.2. Hello Message Generation
R_if_id = R_if_id of the recorded route entry whose HELLO message generation should consider those new fields as follows:
R_dest == T_last.
3.2 Several topology entries may be used to select a next hop 1 if L_LOST_LINK_time is not expired, the link is advertised
R_next for reaching the node R_dest. When h=1, ties with a link type of LOST_LINK and neighbor type NOT_NEIGH ;
should be broken such that nodes with highest willingness
and MPR selectors are preferred as next hop.
The routing table is further completed by using the multiple inter- 2 otherwise, if L_LOST_LINK_time is expired and L_link_pending
face association set: is set to "true", the link SHOULD NOT be advertised at all;
1 For each entry in the multiple interface association base for 3 otherwise, if L_LOST_LINK_time is expired and L_link_pending
which there exists a routing entry such that: is set to "false", the link is advertised as described previ-
ously in section 4.
R_dest == I_main_addr (of the multiple interface inter- A node considers that it has a symmetric link for each link tuple
face association entry) where
a route entry is created in the routing table with: 1 L_LOST_LINK_time is expired, AND
R_dest = I_if_addr (of the multiple interface associa- 2 L_link_pending is "false", AND
tion entry)
R_next = R_next (of the recorded route entry) 3 L_SYM_time is not expired.
R_dist = R_dist (of the recorded route entry) This should be taken as definition for computing the symmetric neigh-
borhood when computing the MPR set. This should also be taken as the
definition of "the symmetric neighbors" in the first steps of the
routing table calculation.
R_if_id = R_if_id (of the recorded route entry). Apart from the above points, what has been described previously does
not interfere with these advanced link sensing fields in the link
tuples. The L_link_quality, L_link_pending and L_LOST_LINK_time
fields are exclusively updated according to the present section. This
section does not modify the function of any other fields in the link
tuples.
The routing table is finally completed by using the host and network 10.3. Hysteresis Strategy
association set:
1 For each tuple in the host and network association set, record The link between a node and some of its neighbor interfaces might be
an entry in the routing table, with: "bad", i.e. from time to time let HELLOs pass through only to fade
out immediately after. In this case, the neighbor information base
would contain a bad link for at least NEIGHB_HOLD_TIME. In absence of
link layer notification, such a bad link might affect routing badly.
To cope with such unstable links, the following hysteresis strategy
SHOULD be adopted.
R_dest = NET_addr/NET_mask For each neighbor interface NI heard by interface I, the L_link_qual-
ity field of the corresponding Link Tuple determines the establish-
ment of the link. The value of L_link_quality is compared to two
thresholds HYST_THRESHOLD_HIGH, HYST_THRESHOLD_LOW, fixed between 0
and 1 and such that HYST_THRESHOLD_HIGH >= HYST_THRESHOLD_LOW.
R_next = the next hop on the path from the node to The L_link_pending field is set according to the following:
GW_main_addr
R_dist = dist to GW_main_addr 1 if L_link_quality > HYST_THRESHOLD_HIGH:
R_next and R_if_id are set to the same values as the L_link_pending = false
tuple from the routing set with R_dest == GW_main_addr.
2.3.9. Advanced Topology Discovery Functioning L_LOST_LINK_time = current time - 1 (expired)
Due to mobility, some links of the broadcasted topology may fail. 2 otherwise, if L_link_quality < HYST_THRESHOLD_LOW:
Additional messages may be sent to recover quickly. Ideally the load
of control messages should increase smoothly with mobility. This sec-
tion describes how this may be achieved in OLSR.
2.3.9.1. Reaction to Link Failure with a MPR Selector L_link_pending = true
Detection of a link failure between a node and one of its MPR selec- L_LOST_LINK_time = min (L_time, current time +
tors through a link-layer notification may trigger additional TC-mes- NEIGHB_HOLD_TIME)
sages to increase the protocol reactiveness to link failures. I.e.
when a change to the MPR selector set is detected and this change can
be attributed to a link failure, an additional TC-message MAY be
transmitted.
More precisely, if a link failure appears to be a neighbor loss with (the link is then considered as lost according to section
a neighbor, which has selected this node as MPR, the MPR selector set 4.8 and this may produce a neighbor loss).
is updated (MSSN is thus incremented) and a TC message MAY be gener-
ated. Moreover if it appears that data traffic was flowing through
this link, a TC message SHOULD be generated. Notice, that a node may
be aware of data traffic flowing to the lost neighbor in case of a
link layer notification coming from a missing acknowledgement or when
statistics about packet forwarding are given by the IP stack.
2.3.9.2. Advanced Fast Re-routing Mechanism 3 otherwise, if HYST_THRESHOLD_LOW <= L_link_quality <=
HYST_THRESHOLD_HIGH:
When a link breaks, information stored in the neighbor sensing infor- L_link_pending and L_LOST_LINK_time remain unchanged.
mation base may be used to compute an alternative route immediately
if necessary.
If there exists a N_2hop_address listed in the 2-hop neighbor set, The condition for considering a link established is thus stricter
and for which no route exists, a route entry is created in the rout- than the condition for loosing it.
ing table with:
R_dest = N_2hop_address As a basic implementation requirement, an estimation of the link
quality must be maintained and stored in the L_link_quality field. If
some measure of the signal/noise level on a received message is
available (e.g. as a link layer notification), then it can be used as
estimation after normalization.
R_next = R_next of the recorded route entry whose R_dest is If no signal/noise information is available from the link layer, an
equal to N_main_addr of the corresponding 2-hop tuple algorithm such as the following can be utilized (it is an exponen-
tially smoothed moving average of the transmission success rate).
The algorithm is parameterized by a scaling parameter HYST_SCALING
which is a number fixed between 0 and 1. For each neighbor interface
NI heard by interface I, the first time NI is heard by I,
L_link_quality is set to HYST_SCALING (L_link_pending is set to true
and L_LOST_LINK_time to current time - 1).
R_dist = 2 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:
R_if_id = R_if_id of the recorded route entry whose R_dest is L_link_quality = (1-HYST_SCALING)*L_link_quality + HYST_SCAL-
equal to N_main_addr of the corresponding 2-hop tuple. ING.
If an entry in the multiple interface association base records a main When an OLSR packet emitted by NI is lost by I, the instability
address I_main_addr reporting an interface I_if_addr = rule is applied:
N_2hop_address, then R_dest is set to I_main_addr instead of
N_2hop_address.
If the two hop neighbor allows to reach other nodes at distance L_link_quality = (1-HYST_SCALING)*L_link_quality.
greater than 2 according to the topology set then other entries may
be added in the routing table with same R_next for these nodes.
The routing table is finally completed using the multiple interface The loss of OLSR packet is detected by tracking the missing Packet
association set and the host and network association set as described Sequence Numbers on a per interface basis and by long period of
in the routing table calculation section. silence. If no OLSR packet has been received on interface I from
interface NI during hello emission interval of interface NI (computed
from the Htime field in the last hello message received from NI), a
loss of an OLSR packet is detected.
To allow other nodes to benefit from the alternative route, the node 11. Distributing Redundant Topology Information
MAY trigger a fast re-routing event by generating a FRR message.
2.3.9.2.1. FRR Message Format In order to provide redundancy to topology information base, the
advertised link set of a node can contain links to neighbor nodes
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
receiving the TC message will get the knowledge of all the adjacent
links of the sender node. The advertised link set can be built
according to the following rule based on a local parameter called
TC_REDUNDANCY parameter.
The proposed format of a FRR message is 11.1. TC_REDUNDANCY Parameter
0 1 2 3 The parameter TC_REDUNDANCY specifies, for the local node, the amount
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 of information that is included in the TC messages. The parameter is
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ interpreted as follows:
| Next Hop Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Two Hop Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Two Hop Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This is sent as the data-portion of the general message format with - if the TC_REDUNDANCY parameter of the node is 0, then its
the "Message Type" set to FRR_MESSAGE. The time to live SHOULD be advertised link set is limited to the MPR selector set (as
set to 1, ensuring that the message is only received by one-hop described in section 4.6.2),
neighbors.
Next Hop Address - if the TC_REDUNDANCY parameter of the node is 1, then its
advertised set is the union of its MPR set and its MPR selec-
tor set,
This field contains the main address of a node which is used - if the TC_REDUNDANCY parameter of the node is 2, then its
as next hop by the Originator for reaching all the nodes iden- advertised set is neighbor set (full link-state information is
tified by the Two Hop Address fields. diffused).
Two Hop Address A node with willingness equal to zero SHOULD have TC_REDUNDANCY also
equal to zero.
This field contain the main address of a 2-hop neighbor of the 12. MPR Redundancy
Originator of the message.
2.3.9.2.2. FRR Message Generation 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
be as small as possible, in order to reduce protocol overhead. The
criteria for selecting MPRs being, that all strict 2-hop nodes must
be reachable through, at least, one MPR node. Redundancy of the MPR
set affects the overhead through affecting the amount of links being
advertised, the amount of nodes advertising links to the MPR selector
and the efficiency of the MPR flooding mechanism. On the other hand,
redundancy in the MPR set ensures that reachability for a node is
advertised by more nodes, thus additional links are diffused to the
network.
When the fast re-routing mechanism allows to reach 2-hop neighbors While, in general, a minimal MPR set provides the least overhead,
through a neighbor which is not recorded as MPR of them in the topol- there are situations in which overhead can be traded off for other
ogy set, the node MAY inform this next hop by generating a FRR Mes- benefits. E.g. a node can may decide to increase its MPR coverage if
sage with Next Hop Address containing the main address of this next it observes many changes in its neighbor information base caused by
hop and listing the main addresses of these 2-hop neighbors. mobility, while otherwise keeping a low MPR coverage.
If some information allows to deduce that some data traffic flows 12.1. MPR_COVERAGE Parameter
through the node to some of these 2-hop neighbors, such a FRR Message
SHOULD be generated. This can be the case if such a 2-hop neighbor
was previously a neighbor and a link layer notification of a missing
acknowledgment has been received or statistics about packet forward-
ing are provided by the IP stack. Otherwise, an FFR-message MAY be
generated.
2.3.9.2.3. FRR Message Processing 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
covered. MPR_COVERAGE=1 specifies that the overhead of the protocol
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
possible, a node selects its MPR set such that all strict 2-hop nodes
are reachable through at least m MPR nodes.
Upon reception of a FRR message a node performs the following: Notice that MPR_COVERAGE can be tuned locally without affecting the
consistency of the protocol. I.e. nodes in a network may operate with
different values of MPR_COVERAGE.
1 If the Next Hop Address field is not the main address of the 12.2. MPR Computation
node, the message is dropped.
2 For each Two Hop Address listed in the FRR Message for which Using MPR coverage, the MPR selection heuristics is extended from
there exists a neighbor tuple with N_main_addr = the Two Hop that described in the section 4.6.3 by one definition:
Address and for which there exists no tuple in the MPR selec-
tor set with MS_main_addr = the Two Hop Address, a new tuple
is inserted with:
MS_main_addr = the Two Hop Address Poorly covered node:
MS_if_addr = N_if_addr of the corresponding neighbor A poorly covered node is a node in N2 which is covered by less
tuple than MPR_COVERAGE nodes in N.
MS_time = current time + 2HOP_HOLD_TIME. The proposed heuristic for selecting MPRs is then as follows:
If the MPR set has changed and a TC message containing the new MPR 1 Start with an MPR set made of all members of N with willing-
selector set SHOULD be generated. ness equal to WILL_ALWAYS
3. Node Configuration 2 Calculate D(y), where y is a member of N, for all nodes in N.
3.1. Address Assignment 3 Select as MPRs those nodes in N which cover the poorly covered
nodes in N2. The nodes are then removed from N2 for the rest
of the computation.
The nodes in the MANET network SHOULD be assigned addresses within a 4 While there exist nodes in N2 which are not covered by at
defined address sequence. I.e., the nodes in the MANET SHOULD be least MPR_COVERAGE nodes in the MPR set:
addressable through a network address and a netmask.
Likewise, the nodes in each associated network SHOULD be assigned 4.1 For each node in N, calculate the reachability, i.e. the
addresses from a defined address sequence, distinct from that being number of nodes in N2 which are not yet covered by at
used in the MANET. least MPR_COVERAGE nodes in the MPR set, and which are
reachable through this one hop neighbor;
3.2. Routing Configuration 4.2 Select as a MPR the node with highest willingness among
the nodes in N with non-zero reachability. In case of
multiple choice select the node which provides reachabil-
ity to the maximum number of nodes in N2. In case of
multiple nodes providing the same amount of reachability,
select the node as MPR whose D(y) is greater. Remove the
nodes from N2 which are now covered by MPR_COVERAGE nodes
in the MPR set.
Any MANET node with associated networks or hosts SHOULD 5 As an optimization, process each node y in the MPR set in the
be configured such that it has routes set up to the interfaces with increasing order of their willingness. If all nodes in N2 are
associated hosts or network. still covered by at least MPR_COVERAGE nodes in the MPR set
excluding y and willingness of node y is smaller than
WILL_ALWAYS, then node y is removed from the MPR set.
3.3. Data Packet Forwarding When the MPR set has been computed, all the corresponding main
addresses are stored in the MPR Set.
OLSR itself does not perform packet forwarding. Rather, it maintains Notice, that for MPR_COVERAGE=1, this heuristics is identical to the
the routing table in the underlying operating system, which is heuristics specified in the section 4.6.3.
assumed to be forwarding packets as specified in RFC1812.
4. IPv6 Considerations 13. IPv6 Considerations
All the operations and parameters described in this document used by 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- 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 sion 6. However, to operate with IP version 6, the only required
change is to replace the IPv4 addresses with Ipv6 address. change is to replace the IPv4 addresses with IPv6 address.
5. Security Considerations 14. Security Considerations
Currently, OLSR does not specify any security measures. However as a Currently, OLSR does not specify any security measures. However as a
proactive routing protocol, it makes a target for various attacks. proactive routing protocol, it makes a target for various attacks.
The various possible vulnerability are discussed in this section. The various possible vulnerability are discussed in this section.
5.1. Confidentiality 14.1. Confidentiality
Being a proactive protocol, OLSR periodically diffuses topological Being a proactive protocol, OLSR periodically diffuses topological
information. Hence, if used in an unprotected wireless network, the information. Hence, if used in an unprotected wireless network, the
network topology is revealed to anyone who listens to OLSR control network topology is revealed to anyone who listens to OLSR control
messages. messages.
In situations where the confidentiality of the network topology is of In situations where the confidentiality of the network topology is of
importance, regular cryptographic techniques can be applied to ensure importance, regular cryptographic techniques can be applied to ensure
that control traffic can be read and interpreted by only those autho- that control traffic can be read and interpreted by only those autho-
rized to do so. rized to do so.
5.2. Integrity 14.2. Integrity
In OLSR, each node is injecting topological information into the net- In OLSR, each node is injecting topological information into the net-
work through transmitting HELLO messages and, for some nodes, TC mes- work through transmitting HELLO messages and, for some nodes, TC mes-
sages. If some nodes for some reason, malicious or malfunction, sages. If some nodes for some reason, malicious or malfunction,
injects invalid control traffic, network integrity may be compro- injects invalid control traffic, network integrity may be compro-
mised. mised.
Different such situations may occur: Different such situations may occur:
1 a node generates TC messages, adverticing links to non-neigh- 1 a node generates TC (or HNA) messages, advertising links to
bor nodes: non-neighbor nodes:
2 a node generates TC messages, pretending to be another node, 2 a node generates TC (or HNA) messages, pretending to be
another node,
3 a node generate HELLO messages, adverticing non-neighbor 3 a node generate HELLO messages, advertising non-neighbor
nodes, nodes,
4 a node generate HELLO messages, pretending to be another node. 4 a node generate HELLO messages, pretending to be another node.
5 a node forwards broadcast control messages unaltered, but does 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 not forward unicast data traffic
Authenticated signatures on control messages (for situation 2 and 4) Authenticated signatures on control messages (for situation 2, 4 and
and on the individual links announced in the control messages (for 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- situation 1 and 3) may be used as a countermeasure. However to pre-
vent nodes from repeating old (and correctly authenticated) informa- vent nodes from repeating old (and correctly authenticated) informa-
tion temporal information is required, allowing a node to positively tion temporal information is required, allowing a node to positively
identify such delayed messages. identify such delayed messages.
Signatures and other required security information may be transmitted Signatures and other required security information may be transmitted
as a separate OLSR message type, thereby allowing that "secured" and as a separate OLSR message type, thereby allowing that "secured" and
"unsecured" nodes can coexist in the same network, if desired. "unsecured" nodes can coexist in the same network, if desired.
6. Proposed Values for the Constants 14.3. Interaction with External Routing Domains
OLSR does, through the HNA messages specified in section 8,
provide a basic mechanism for injecting external routing information
to the OLSR domain. Section 8 also specifies that routing
information can be extracted from the topology 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 14.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.
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
domain to an OLSR routed manet is to assign an IP sequence (under the
authority of the nodes/gateways connecting the manet with the exiting
routing domain) exclusively to the OLSR manet, and to configure the
gateways statically to advertise routes to that IP sequence to nodes
in the existing routing domain.
15. 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
The proposed constant for C is the following:
C = 1/16 seconds (equal to 0.0625 seconds)
C is a scaling factor for the "validity time" calculation ("Vtime"
and "Htime" fields in message headers, see section 15.3).
The "validity time" advertisement is designed such that nodes in a
network may have different and individually tuneable emmision inter-
vals, while still interoperate fully. For protocol functionning and
interoperability to work:
- the advertised holding time MUST always be greater than the
refresh interval of the advertised information. Moreover, it
is recommended that the relation between the interval (from
section 15.2), and the hold time is kept as specified
in section 15.3, to allow for reasonable packet loss.
- the constant C SHOULD be set to the suggested value. In order
to achieve interoperability, C MUST be the same on all nodes.
- the emission intervals (section 15.2), along with the
advertised holding times (subject to the above constraints)
MAY be selected on a per node basis.
15.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
NEIGHB_HOLD_TIME = 3 x HELLO_INTERVAL 15.3. Holding Time
2HOP_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 D_TIME = 30 seconds
I_TIME = 3 x MID_INTERVAL MID_HOLD_TIME = 3 x MID_INTERVAL
GW_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
Htime in the HELLO message (see section 4.2) are the
fields which hold information about the above values in mantissa and
exponent format (rounded up). In other words:
value = C*(1+a/16)*2^b
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.
Given one of the above holding times, one way to compute the man-
tissa/exponent representation of a number T (of seconds) is the fol-
lowing:
- find the biggest integer 'b' such as: T/C > 2^b
- compute the expression 16*(T/(C*(2^b))-1), which may not be a
integer, and round it up. The result gives 'a'
- 'a' and 'b' should now be integers between 0 and 15, and the
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
HELLO_MESSAGE = 1 HELLO_MESSAGE = 1
TC_MESSAGE = 2 TC_MESSAGE = 2
MID_MESSAGE = 3 MID_MESSAGE = 3
HNA_MESSAGE = 4 HNA_MESSAGE = 4
FRR_MESSAGE = 5
15.5. Link Types
UNSPEC_LINK = 0
ASYM_LINK = 1 ASYM_LINK = 1
SYM_LINK = 2 SYM_LINK = 2
MPR_LINK = 3 LOST_LINK = 3
LOST_LINK = 4 15.6. Neighbor Types
NOT_NEIGH = 0
SYM_NEIGH = 1
MPR_NEIGH = 2
15.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
WILL_NEVER = 0
WILL_LOW = 1
WILL_DEFAULT = 3
WILL_HIGH = 6
WILL_ALWAYS = 7
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
behalf of other nodes. Nodes will, by default, have a willingness
WILL_DEFAULT. WILL_NEVER indicates a node which does not wish to
carry traffic for other nodes, e.g. due to ressource constraints
(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.
due to ressource abundance (e.g. permanent power supply, high-capac-
ity interfaces to other nodes).
A node may dynamically change its willingness as its conditions
change.
One possible application would, for example, be for a node, connected
to a permanent power supply and with fully charged batteries, to
advertise a willingness of WILL_ALWAYS. Upon being disconnected from
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
capacity is drained, the willingness would be further reduced. First
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
node does no longer support carrying forigen traffic.
15.9. Misc. Constants
TC_REDUNDANCY = 0
MPR COVERAGE = 1 MPR COVERAGE = 1
MAXJITTER = HELLO_INTERVAL / 4 MAXJITTER = HELLO_INTERVAL / 4
7. Sequence Numbers 16. 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 with
a limited number of bits for representing sequence numbers, wrap- a limited number of bits for representing sequence numbers, wrap-
arounds (that the sequence number is incremented from the maximum around (that the sequence number is incremented from the maximum pos-
possible value to zero) will occur. To prevent this from interfering sible 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.
8. Acknowledgments 17. Acknowledgments
The authors would like to thank Joseph Macker and his team The authors would like to thank Joseph Macker and his team
<macker@itd.nrl.navy.mil> for their valuable suggestions on the <macker@itd.nrl.navy.mil> for their valuable suggestions on the
advanced neighbor sensing mechanism. advanced neighbor sensing mechanism.
The authors would also like to thank Christopher Dearlove The authors would also like to thank Christopher Dearlove
<chris.dearlove@baesystems.com> for valueable input on the MPR selec- <chris.dearlove@baesystems.com> for valuable input on the MPR selec-
tion heuristics. tion heuristics.
9. Authors' Addresses 18. Authors' Addresses
Cedric Adjih Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le
Chesnay Cedex, France Phone: +33 1 3963 5215 Email:
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:
Philippe.Jacquet@inria.fr Philippe.Jacquet@inria.fr
Anis Laouiti Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le Anis Laouiti Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le
Chesnay Cedex, France Phone: +33 1 3963 508832 Email: Chesnay Cedex, France Phone: +33 1 3963 508832 Email:
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-
skipping to change at line 2480 skipping to change at page 72, line 27
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 Avaz Networks 5-A Constitution Avenue Islamabad, Pakistan
Phone: +92-51-2826160 Email: qayyum@avaznet.com Phone: +92-51-2826160 Email: qayyum@avaznet.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
10. References 19. References
1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing relia- 1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing relia-
bility in cable free radio LANs: Low level forwarding in HIPERLAN. bility in cable free radio LANs: Low level forwarding in HIPERLAN.
Wireless Personal Communications, 1996 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 efficient
technique for flooding in mobile wireless networks. 35th Annual technique for flooding in mobile wireless networks. 35th Annual
Hawaii International Conference on System Sciences (HICSS'2001). 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 type
skipping to change at line 2503 skipping to change at line 3193
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 Optimized
Link State Routing Protocol, Evaluation through Experiments and Link State Routing Protocol, Evaluation through Experiments and
Simulation. IEEE Symposium on "Wireless Personal Mobile Communica- Simulation. IEEE Symposium on "Wireless Personal Mobile Communica-
tions", september 2001. tions", 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 and L.
Viennot. Optimized Link State Routing Protocol. IEEE INMIC Pakistan Viennot. Optimized Link State Routing Protocol. IEEE INMIC Pakistan
2001. 2001.
 End of changes. 

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