RFC 3626
Optimized Link State Routing Protocol (OLSR)
Network Working Group T. Clausen, Ed. Request for Comments: 3626 P. Jacquet, Ed. Category: Experimental Project Hipercom, INRIA October 2003 Optimized Link State Routing Protocol (OLSR) Status of this Memo This memo defines an Experimental Protocol for the Internet community. It does not specify an Internet standard of any kind. Discussion and suggestions for improvement are requested. Distribution of this memo is unlimited. Copyright Notice Copyright (C) The Internet Society (2003). All Rights Reserved.Abstract
This document describes the Optimized Link State Routing (OLSR) protocol for mobile ad hoc networks. The protocol is an optimization of the classical link state algorithm tailored to the requirements of a mobile wireless LAN. The key concept used in the protocol is that of multipoint relays (MPRs). MPRs are selected nodes which forward broadcast messages during the flooding process. This technique substantially reduces the message overhead as compared to a classical flooding mechanism, where every node retransmits each 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 second optimization is achieved by minimizing the number of control messages flooded in the network. As a third optimization, an MPR node may chose to report only links between itself and its MPR selectors. Hence, as contrary to the classic link state algorithm, partial link state information is distributed in the network. This information is then used for route calculation. OLSR provides optimal routes (in terms of number of hops). The protocol is particularly suitable for large and dense networks as the technique of MPRs works well in this context.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1. OLSR Terminology. . . . . . . . . . . . . . . . . . . . 5 1.2. Applicability. . . . . . . . . . . . . . . . . . . . . . 7 1.3. Protocol Overview . . . . . . . . . . . . . . . . . . . 8 1.4. Multipoint Relays . . . . . . . . . . . . . . . . . . . 9 2. Protocol Functioning . . . . . . . . . . . . . . . . . . . . 9 2.1. Core Functioning . . . . . . . . . . . . . . . . . . . 10 2.2. Auxiliary Functioning . . . . . . . . . . . . . . . . . 12 3. Packet Format and Forwarding . . . . . . . . . . . . . . . . 13 3.1. Protocol and Port Number. . . . . . . . . . . . . . . . 13 3.2. Main Address . . . . . . . . . . . . . . . . . . . . . 13 3.3. Packet Format . . . . . . . . . . . . . . . . . . . . . 14 3.3.1. Packet Header . . . . . . . . . . . . . . . . . . 14 3.3.2. Message Header . . . . . . . . . . . . . . . . . 15 3.4. Packet Processing and Message Flooding . . . . . . . . . 16 3.4.1. Default Forwarding Algorithm. . . . . . . . . . . 18 3.4.2. Considerations on Processing and Forwarding . . . 20 3.5. Message Emission and Jitter. . . . . . . . . . . . . . . 21 4. Information Repositories . . . . . . . . . . . . . . . . . . 22 4.1. Multiple Interface Association Information Base . . . . 22 4.2. Link sensing: Local Link Information Base. . . . . . . . 22 4.2.1. Link Set. . . . . . . . . . . . . . . . . . . . . 22 4.3. Neighbor Detection: Neighborhood Information Base. . . . 23 4.3.1. Neighbor Set. . . . . . . . . . . . . . . . . . . 23 4.3.2. 2-hop Neighbor Set. . . . . . . . . . . . . . . . 23 4.3.3. MPR Set . . . . . . . . . . . . . . . . . . . . . 23 4.3.4. MPR Selector Set. . . . . . . . . . . . . . . . . 23 4.4. Topology Information Base . . . . . . . . . . . . . . . 24 5. Main Addresses and Multiple Interfaces . . . . . . . . . . . 24 5.1. MID Message Format . . . . . . . . . . . . . . . . . . . 25 5.2. MID Message Generation . . . . . . . . . . . . . . . . . 25 5.3. MID Message Forwarding . . . . . . . . . . . . . . . . . 26 5.4. MID Message Processing . . . . . . . . . . . . . . . . . 26 5.5. Resolving a Main Address from an Interface Address . . . 27 6. HELLO Message Format and Generation . . . . . . . . . . . . . 27 6.1. HELLO Message Format . . . . . . . . . . . . . . . . . . 27 6.1.1. Link Code as Link Type and Neighbor Type. . . . . 29 6.2. HELLO Message Generation . . . . . . . . . . . . . . . . 30 6.3. HELLO Message Forwarding . . . . . . . . . . . . . . . . 33 6.4. HELLO Message Processing . . . . . . . . . . . . . . . . 33 7. Link Sensing . . . . . . . . . . . . . . . . . . . . . . . . 33 7.1. Populating the Link Set . . . . . . . . . . . . . . . . 33 7.1.1. HELLO Message Processing . . . . . . . . . . . . 34 8. Neighbor Detection . . . . . . . . . . . . . . . . . . . . . 35 8.1. Populating the Neighbor Set . . . . . . . . . . . . . . . 35 8.1.1. HELLO Message Processing . . . . . . . . . . . . 37
8.2. Populating the 2-hop Neighbor Set. . . . . . . . . . . . 37
8.2.1. HELLO Message Processing. . . . . . . . . . . . . 37
8.3. Populating the MPR set . . . . . . . . . . . . . . . . . 38
8.3.1. MPR Computation . . . . . . . . . . . . . . . . . 39
8.4. Populating the MPR Selector Set. . . . . . . . . . . . . 41
8.4.1. HELLO Message Processing. . . . . . . . . . . . . 41
8.5. Neighborhood and 2-hop Neighborhood Changes. . . . . . . 42
9. Topology Discovery . . . . . . . . . . . . . . . . . . . . . 43
9.1. TC Message Format. . . . . . . . . . . . . . . . . . . . 43
9.2. Advertised Neighbor Set. . . . . . . . . . . . . . . . . 44
9.3. TC Message Generation. . . . . . . . . . . . . . . . . . 45
9.4. TC Message Forwarding. . . . . . . . . . . . . . . . . . 45
9.5. TC Message Processing. . . . . . . . . . . . . . . . . . 45
10. Routing Table Calculation . . . . . . . . . . . . . . . . . . 47
11. Node Configuration. . . . . . . . . . . . . . . . . . . . . . 50
11.1. Address Assignment. . . . . . . . . . . . . . . . . . . 50
11.2. Routing Configuration . . . . . . . . . . . . . . . . . 51
11.3. Data Packet Forwarding. . . . . . . . . . . . . . . . . 51
12. Non OLSR Interfaces . . . . . . . . . . . . . . . . . . . . . 51
12.1. HNA Message Format. . . . . . . . . . . . . . . . . . . 52
12.2. Host and Network Association Information Base . . . . . 52
12.3. HNA Message Generation. . . . . . . . . . . . . . . . . 53
12.4. HNA Message Forwarding. . . . . . . . . . . . . . . . . 53
12.5. HNA Message Processing. . . . . . . . . . . . . . . . . 53
12.6. Routing Table Calculation . . . . . . . . . . . . . . . 54
12.7. Interoperability Considerations . . . . . . . . . . . . 55
13. Link Layer Notification . . . . . . . . . . . . . . . . . . . 55
13.1. Interoperability Considerations . . . . . . . . . . . . 56
14. Link Hysteresis . . . . . . . . . . . . . . . . . . . . . . . 56
14.1. Local Link Set . . . . . . . . . . . . . . . . . . . . 56
14.2. Hello Message Generation . . . . . . . . . . . . . . . 57
14.3. Hysteresis Strategy . . . . . . . . . . . . . . . . . . 57
14.4. Interoperability Considerations . . . . . . . . . . . . 59
15. Redundant Topology Information. . . . . . . . . . . . . . . . 59
15.1. TC_REDUNDANCY Parameter . . . . . . . . . . . . . . . . 60
15.2. Interoperability Considerations . . . . . . . . . . . . 60
16. MPR Redundancy. . . . . . . . . . . . . . . . . . . . . . . . 60
16.1. MPR_COVERAGE Parameter. . . . . . . . . . . . . . . . . 61
16.2. MPR Computation . . . . . . . . . . . . . . . . . . . . 61
16.3. Interoperability Considerations . . . . . . . . . . . . 62
17. IPv6 Considerations . . . . . . . . . . . . . . . . . . . . . 63
18. Proposed Values for Constants . . . . . . . . . . . . . . . . 63
18.1. Setting emission interval and holding times . . . . . . 63
18.2. Emission Interval . . . . . . . . . . . . . . . . . . . 64
18.3. Holding time . . . . . . . . . . . . . . . . . . . . . 64
18.4. Message Types . . . . . . . . . . . . . . . . . . . . . 65
18.5. Link Types. . . . . . . . . . . . . . . . . . . . . . . 65
18.6. Neighbor Types . . . . . . . . . . . . . . . . . . . . 65
18.7. Link Hysteresis . . . . . . . . . . . . . . . . . . . . 66
18.8. Willingness . . . . . . . . . . . . . . . . . . . . . . 66
18.9. Misc. Constants . . . . . . . . . . . . . . . . . . . . 67
19. Sequence Numbers. . . . . . . . . . . . . . . . . . . . . . . 67
20. Security Considerations . . . . . . . . . . . . . . . . . . . 67
20.1. Confidentiality . . . . . . . . . . . . . . . . . . . . 67
20.2. Integrity . . . . . . . . . . . . . . . . . . . . . . . 68
20.3. Interaction with External Routing Domains . . . . . . . 69
20.4. Node Identity . . . . . . . . . . . . . . . . . . . . . 70
21. Flow and congestion control . . . . . . . . . . . . . . . . . 70
22. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 70
23. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 71
24. Contributors. . . . . . . . . . . . . . . . . . . . . . . . . 71
25. References. . . . . . . . . . . . . . . . . . . . . . . . . . 73
26. Authors' Addresses. . . . . . . . . . . . . . . . . . . . . . 74
27. Full Copyright Statement. . . . . . . . . . . . . . . . . . . 75
1. Introduction
The Optimized Link State Routing Protocol (OLSR) is developed for
mobile ad hoc networks. It operates as a table driven, proactive
protocol, i.e., exchanges topology information with other nodes of
the network regularly. Each node selects a set of its neighbor nodes
as "multipoint relays" (MPR). In OLSR, only nodes, selected as such
MPRs, are responsible for forwarding control traffic, intended for
diffusion into the entire network. MPRs provide an efficient
mechanism for flooding control traffic by reducing the number of
transmissions required.
Nodes, selected as MPRs, also have a special responsibility when
declaring link state information in the network. Indeed, the only
requirement for OLSR to provide shortest path routes to all
destinations is that MPR nodes declare link-state information for
their MPR selectors. Additional available link-state information may
be utilized, e.g., for redundancy.
Nodes which have been selected as multipoint relays by some neighbor
node(s) announce this information periodically in their control
messages. Thereby a node announces to the network, that it has
reachability to the nodes which have selected it as an MPR. In route
calculation, the MPRs are used to form the route from a given node to
any destination in the network. Furthermore, the protocol uses the
MPRs to facilitate efficient flooding of control messages in the
network.
A node selects MPRs from among its one hop neighbors with
"symmetric", i.e., bi-directional, linkages. Therefore, selecting
the route through MPRs automatically avoids the problems associated
with data packet transfer over uni-directional links (such as the problem of not getting link-layer acknowledgments for data packets at each hop, for link-layers employing this technique for unicast traffic). OLSR is developed to work independently from other protocols. Likewise, OLSR makes no assumptions about the underlying link-layer. OLSR inherits the concept of forwarding and relaying from HIPERLAN (a MAC layer protocol) which is standardized by ETSI [3]. The protocol is developed in the IPANEMA project (part of the Euclid program) and in the PRIMA project (part of the RNRT program).1.1. OLSR Terminology
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC2119 [5]. Additionally, this document uses the following terminology: node A MANET router which implements the Optimized Link State Routing protocol as specified in this document. OLSR interface A network device participating in a MANET running OLSR. A node may have several OLSR interfaces, each interface assigned an unique IP address. non OLSR interface A network device, not participating in a MANET running OLSR. A node may have several non OLSR interfaces (wireless and/or wired). Routing information from these interfaces MAY be injected into the OLSR routing domain. single OLSR interface node A node which has a single OLSR interface, participating in an OLSR routing domain. multiple OLSR interface node A node which has multiple OLSR interfaces, participating in an OLSR routing domain.
main address
The main address of a node, which will be used in OLSR control
traffic as the "originator address" of all messages emitted by
this node. It is the address of one of the OLSR interfaces of
the node.
A single OLSR interface node MUST use the address of its only
OLSR interface as the main address.
A multiple OLSR interface node MUST choose one of its OLSR
interface addresses as its "main address" (equivalent of
"router ID" or "node identifier"). It is of no importance
which address is chosen, however a node SHOULD always use the
same address as its main address.
neighbor node
A node X is a neighbor node of node Y if node Y can hear node X
(i.e., a link exists between an OLSR interface on node X and an
OLSR interface on Y).
2-hop neighbor
A node heard by a neighbor.
strict 2-hop neighbor
a 2-hop neighbor which is not the node itself or a neighbor of
the node, and in addition is a neighbor of a neighbor, with
willingness different from WILL_NEVER, of the node.
multipoint relay (MPR)
A node which is selected by its 1-hop neighbor, node X, to
"re-transmit" all the broadcast messages that it receives from
X, provided that the message is not a duplicate, and that the
time to live field of the message is greater than one.
multipoint relay selector (MPR selector, MS)
A node which has selected its 1-hop neighbor, node X, as its
multipoint relay, will be called a multipoint relay selector of
node X.
link
A link is a pair of OLSR interfaces (from two different nodes)
susceptible 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 another node when one of its interface has a link to one of
the interfaces of the other node.
symmetric link
A verified bi-directional link between two OLSR interfaces.
asymmetric link
A link between two OLSR interfaces, verified in only one
direction.
symmetric 1-hop neighborhood
The symmetric 1-hop neighborhood of any node X is the set of
nodes which have at least one symmetric link to X.
symmetric 2-hop neighborhood
The symmetric 2-hop neighborhood of X is the set of nodes,
excluding X itself, which have a symmetric link to the
symmetric 1-hop neighborhood of X.
symmetric strict 2-hop neighborhood
The symmetric strict 2-hop neighborhood of X is the set of
nodes, excluding X itself and its neighbors, which have a
symmetric link to some symmetric 1-hop neighbor, with
willingness different of WILL_NEVER, of X.
1.2. Applicability
OLSR is a proactive routing protocol for mobile ad-hoc networks
(MANETs) [1], [2]. It is well suited to large and dense mobile
networks, as the optimization achieved using the MPRs works well in
this context. The larger and more dense a network, the more
optimization can be achieved as compared to the classic link state
algorithm. OLSR uses hop-by-hop routing, i.e., each node uses its
local information to route packets.
OLSR is well suited for networks, where the traffic is random and
sporadic between a larger set of nodes rather than being almost
exclusively between a small specific set of nodes. As a proactive
protocol, OLSR is also suitable for scenarios where the communicating pairs change over time: no additional control traffic is generated in this situation since routes are maintained for all known destinations at all times.1.3. Protocol Overview
OLSR is a proactive routing protocol for mobile ad hoc networks. The protocol inherits the stability of a link state algorithm and has the advantage of having routes immediately available when needed due to its proactive nature. OLSR is an optimization over the classical link state protocol, tailored for mobile ad hoc networks. OLSR minimizes the overhead from flooding of control traffic by using only selected nodes, called MPRs, to retransmit control messages. This technique significantly reduces the number of retransmissions required to flood a message to all nodes in the network. Secondly, OLSR requires only partial link state to be flooded in order to provide shortest path routes. The minimal set of link state information required is, that all nodes, selected as MPRs, MUST declare the links to their MPR selectors. Additional topological information, if present, MAY be utilized e.g., for redundancy purposes. OLSR MAY optimize the reactivity to topological changes by reducing the maximum time interval for periodic control message transmission. Furthermore, as OLSR continuously maintains routes to all destinations in the network, the protocol is beneficial for traffic patterns where a large subset of nodes are communicating with another large subset of nodes, and where the [source, destination] pairs are changing over time. The protocol is particularly suited for large and dense networks, as the optimization done using MPRs works well in this context. The larger and more dense a network, the more optimization can be achieved as compared to the classic link state algorithm. OLSR is designed to work in a completely distributed manner and does not depend on any central entity. The protocol does NOT REQUIRE reliable transmission of control messages: each node sends control messages periodically, and can therefore sustain a reasonable loss of some such messages. Such losses occur frequently in radio networks due to collisions or other transmission problems. Also, OLSR does not require sequenced delivery of messages. Each control message contains a sequence number which is incremented for each message. Thus the recipient of a control message can, if required, easily identify which information is more recent - even if messages have been re-ordered while in transmission.
Furthermore, OLSR provides support for protocol extensions such as sleep mode operation, multicast-routing etc. Such extensions may be introduced as additions to the protocol without breaking backwards compatibility with earlier versions. OLSR does not require any changes to the format of IP packets. Thus any existing IP stack can be used as is: the protocol only interacts with routing table management.1.4. Multipoint Relays
The idea of multipoint relays is to minimize the overhead of flooding messages in the network by reducing redundant retransmissions in the same region. Each node in the network selects a set of nodes in its symmetric 1-hop neighborhood which may retransmit its messages. This 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, receive and process broadcast messages but do not retransmit broadcast messages received from node N. Each node selects its MPR set from among its 1-hop symmetric neighbors. This set is selected such that it covers (in terms of radio range) all symmetric strict 2-hop nodes. The MPR set of N, denoted as MPR(N), is then an arbitrary subset of the symmetric 1-hop neighborhood of N which satisfies the following condition: every node in the symmetric strict 2-hop neighborhood of N must have a symmetric link towards MPR(N). The smaller a MPR set, the less control traffic overhead results from the routing protocol. [2] gives an analysis and example of MPR selection algorithms. Each node maintains information about the set of neighbors that have selected it as MPR. This set is called the "Multipoint Relay Selector set" (MPR selector set) of a node. A node obtains this information from periodic HELLO messages received from the neighbors. 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 retransmitted by node N, if N has not received it yet. This set can change over time (i.e., when a node selects another MPR-set) and is indicated by the selector nodes in their HELLO messages.2. Protocol Functioning
This section outlines the overall protocol functioning. OLSR is modularized into a "core" of functionality, which is always required for the protocol to operate, and a set of auxiliary functions.
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 extent 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 functionality and a set of auxiliary functions is to provide a simple and easy-to-comprehend protocol, and to provide a way of only adding complexity 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 a universal specification of OLSR protocol messages and their transmission through the network, as well as link sensing, topology diffusion and route calculation. Specifically, the core is made up from the following components: Packet Format and Forwarding A universal specification of the packet format and an optimized flooding mechanism serves as the transport mechanism for all OLSR control traffic. Link Sensing Link Sensing is accomplished through periodic emission of HELLO messages over the interfaces through which connectivity is checked. A separate HELLO message is generated for each interface and emitted in correspondence with the provisions in section 7. Resulting from Link Sensing is a local link set, describing links between "local interfaces" and "remote interfaces" - i.e., interfaces on neighbor nodes.
If sufficient information is provided by the link-layer, this
may be utilized to populate the local link set instead of HELLO
message exchange.
Neighbor detection
Given a network with only single interface nodes, a node may
deduct the neighbor set directly from the information exchanged
as part of link sensing: the "main address" of a single
interface node is, by definition, the address of the only
interface on that node.
In a network with multiple interface nodes, additional
information is required in order to map interface addresses to
main addresses (and, thereby, to nodes). This additional
information is acquired through multiple interface declaration
(MID) messages, described in section 5.
MPR Selection and MPR Signaling
The objective of MPR selection is for a node to select a subset
of its neighbors such that a broadcast message, retransmitted
by these selected neighbors, will be received by all nodes 2
hops away. The MPR set of a node is computed such that it, for
each interface, satisfies this condition. The information
required to perform this calculation is acquired through the
periodic exchange of HELLO messages, as described in section 6.
MPR selection procedures are detailed in section 8.3.
MPR signaling is provided in correspondence with the provisions
in the section 6.
Topology Control Message Diffusion
Topology Control messages are diffused with the purpose of
providing each node in the network with sufficient link-state
information to allow route calculation. Topology Control
messages are diffused in correspondence with the provisions in
section 9.
Route Calculation
Given the link state information acquired through periodic
message exchange, as well as the interface configuration of the
nodes, the routing table for each node can be computed. This
is detailed in section 10.
The key notion for these mechanisms is the MPR relationship.
The 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
Information repositories | 4
Main addr and multiple if. | 5
Hello messages | 6
Link sensing | 7
Neighbor detection | 8
Topology discovery | 9
Routing table computation | 10
Node configuration | 11
2.2. Auxiliary Functioning
In addition to the core functioning of OLSR, there are situations
where additional functionality is desired. This includes situations
where a node has multiple interfaces, some of which participate in
another routing domain, where the programming interface to the
networking 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
overhead.
The following table specifies auxiliary functions and their relation
to this document.
Feature | Section
------------------------------+--------------
Non-OLSR interfaces | 12
Link-layer notifications | 13
Advanced link sensing | 14
Redundant topology | 15
Redundant MPR flooding | 16
The interpretation of the above table is as follows: if the feature
listed is required, it SHOULD be provided as specified in the
corresponding section.
3. Packet Format and Forwarding
OLSR communicates using a unified packet format for all data related to the protocol. The purpose of this is to facilitate extensibility of the protocol without breaking backwards compatibility. This also provides an easy way of piggybacking different "types" of information into a single transmission, and thus for a given implementation to optimize towards utilizing the maximal frame-size, provided by the network. These packets are embedded in UDP datagrams for transmission over the network. The present document is presented with IPv4 addresses. Considerations regarding IPv6 are given in section 17. Each packet encapsulates one or more messages. The messages share a common header format, which enables nodes to correctly accept and (if applicable) retransmit messages of an unknown type. 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 the originator of the message. Thus transmitting a message to the neighborhood of a node is just a special case of flooding. When flooding any control message, duplicate retransmissions will be eliminated locally (i.e., each node maintains a duplicate set to prevent transmitting the same OLSR control message twice) and minimized in the entire network through the usage of MPRs as described in later sections. Furthermore, a node can examine the header of a message to obtain information on the distance (in terms of number of hops) to the originator of the message. This feature may be useful in situations where, e.g., the time information from a received control messages stored in a node depends on the distance to the originator.3.1. Protocol and Port Number
Packets in OLSR are communicated using UDP. Port 698 has been assigned by IANA for exclusive usage by the OLSR protocol.3.2. Main Address
For a node with one interface, the main address of a node, as defined in "OLSR Terminology", MUST be set to the address of that interface.
3.3. Packet Format
The basic layout of any packet in OLSR is as follows (omitting IP and UDP headers): 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Packet Length | Packet Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message Type | Vtime | Message Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Time To Live | Hop Count | Message Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | : MESSAGE : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message Type | Vtime | Message Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Time To Live | Hop Count | Message Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | : MESSAGE : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : : (etc.)3.3.1. Packet Header
Packet Length The length (in bytes) of the packet Packet Sequence Number 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 19. A separate Packet Sequence Number is maintained for each interface such that packets transmitted over an interface are sequentially enumerated.
The IP address of the interface over which a packet was transmitted is obtainable from the IP header of the packet. If the packet contains no messages (i.e., the Packet Length is less than or equal to the size of the packet header), the packet MUST silently be discarded. For IPv4 addresses, this implies that packets, where the Packet Length < 16 MUST silently be discarded.3.3.2. Message Header
Message Type This field indicates which type of message is to be found in the "MESSAGE" part. Message types in the range of 0-127 are reserved for messages in this document and in possible extensions. Vtime This field indicates for how long time after reception a node MUST consider the information contained in the message as valid, unless a more recent update to the information is received. 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 [in seconds] 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 18. Message Size This gives the size of this message, counted in bytes and measured from the beginning of the "Message Type" field and until the beginning of the next "Message Type" field (or - if there are no following messages - until the end of the packet). Originator Address This field contains the main address of the node, which has originally generated this message. This field SHOULD NOT be confused with the source address from the IP header, which is changed each time to the address of the intermediate interface
which is re-transmitting this message. The Originator Address
field MUST *NEVER* be changed in retransmissions.
Time To Live
This field contains the maximum number of hops a message will
be transmitted. Before a message is retransmitted, the Time To
Live MUST be decremented by 1. When a node receives a message
with a Time To Live equal to 0 or 1, the message MUST NOT be
retransmitted under any circumstances. Normally, a node would
not receive a message with a TTL of zero.
Thus, by setting this field, the originator of a message can
limit the flooding radius.
Hop Count
This field contains the number of hops a message has attained.
Before a message is retransmitted, the Hop Count MUST be
incremented by 1.
Initially, this is set to '0' by the originator of the message.
Message Sequence Number
While generating a message, the "originator" node will assign a
unique identification number to each message. This number is
inserted into the Sequence Number field of the message. The
sequence number is increased by 1 (one) for each message
originating from the node. "Wrap-around" is handled as
described in section 19. Message sequence numbers are used to
ensure that a given message is not retransmitted more than once
by any node.
3.4. Packet Processing and Message Flooding
Upon receiving a basic packet, a node examines each of the "message
headers". Based on the value of the "Message Type" field, the node
can determine the fate of the message. A node may receive the same
message several times. Thus, to avoid re-processing of some messages
which were already received and processed, each node maintains a
Duplicate Set. In this set, the node records information about the
most recently received messages where duplicate processing of a
message is to be avoided. For such a message, a node records a
"Duplicate Tuple" (D_addr, D_seq_num, D_retransmitted, D_iface_list,
D_time), where D_addr is the originator address of the message,
D_seq_num is the message sequence number of the message,
D_retransmitted is a boolean indicating whether the message has been
already retransmitted, D_iface_list is a list of the addresses of the
interfaces on which the message has been received and D_time
specifies the time at which a tuple expires and *MUST* be removed.
In a node, the set of Duplicate Tuples are denoted the "Duplicate
set".
In this section, the term "Originator Address" will be used for the
main address of the node which sent the message. The term "Sender
Interface Address" will be used for the sender address (given in the
IP header of the packet containing the message) of the interface
which sent the message. The term "Receiving Interface Address" will
be used for the address of the interface of the node which received
the message.
Thus, upon receiving a basic packet, a node MUST perform the
following tasks for each encapsulated message:
1 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.
2 If the time to live of the message is less than or equal to
'0' (zero), or if the message was sent by the receiving node
(i.e., the Originator Address of the message is the main
address of the receiving node): the message MUST silently be
dropped.
3 Processing condition:
3.1 if there exists a tuple in the duplicate set, where:
D_addr == Originator Address, AND
D_seq_num == Message Sequence Number
then the message has already been completely processed
and MUST not be processed again.
3.2 Otherwise, if the node implements the Message Type of the
message, the message MUST be processed according to the
specifications for the message type.
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 receiving interface (address) is
in D_iface_list
then the message has already been considered for
forwarding and SHOULD NOT be retransmitted again.
4.2 Otherwise:
4.2.1
If the node implements the Message Type of the
message, 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
Message Type of the message, the message SHOULD
be processed 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 1-hop neighborhood of the node, the
forwarding algorithm MUST silently stop here (and the message
MUST NOT be forwarded).
2 If there exists a tuple in the duplicate set where:
D_addr == Originator Address
D_seq_num == Message Sequence Number
Then the message will be further considered for forwarding if
and only if:
D_retransmitted is false, AND
the (address of the) interface which received the message
is not included among the addresses in D_iface_list
3 Otherwise, if such an entry doesn't exist, the message is
further considered for forwarding.
If after those steps, the message is not considered for forwarding,
then the processing of this section stops (i.e., steps 4 to 8 are
ignored), otherwise, if it is still considered for forwarding then
the following algorithm is used:
4 If the sender interface address is an interface address of a
MPR selector of this node and if the time to live of the
message is greater than '1', the message MUST be retransmitted
(as described later in steps 6 to 8).
5 If an entry in the duplicate set exists, with same Originator
Address, and same Message Sequence Number, the entry is
updated as follows:
D_time = current time + DUP_HOLD_TIME.
The receiving interface (address) is added to
D_iface_list.
D_retransmitted is set to true if and only if the message
will be retransmitted according to step 4.
Otherwise an entry in the duplicate set is recorded with:
D_addr = Originator Address
D_seq_num = Message Sequence Number
D_time = current time + DUP_HOLD_TIME.
D_iface_list contains the receiving interface address.
D_retransmitted is set to true if and only if the message
will be retransmitted according to step 4.
If, and only if, according to step 4, the message must be
retransmitted then:
6 The TTL of the message is reduced by one.
7 The hop-count of the message is increased by one
8 The message is broadcast on all interfaces (Notice: The
remaining fields of the message header SHOULD be left
unmodified.)
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
forwarded, known, message) is the responsibility of the algorithm
specifying how the message is to be handled and, if necessary,
retransmitted. This enables a message type to be specified such that
the message can be modified while in transit (e.g., to reflect the
route the message has taken). It also enables bypassing of the MPR
flooding mechanism if for some reason classical flooding of a message
type is required, the algorithm which specifies how such messages
should be handled will simply rebroadcast the message, regardless of
MPRs.
By defining a set of message types, which MUST be recognized by all
implementations of OLSR, it will be possible to extend the protocol
through introduction of additional message types, while still being
able to maintain compatibility with older implementations. The
REQUIRED message types for the core functionality of OLSR are:
- HELLO-messages, performing the task of link sensing, neighbor
detection and MPR signaling,
- TC-messages, performing the task of topology declaration
(advertisement of link states).
- MID-messages, performing the task of declaring the presence of
multiple interfaces on a node.
Other message types include those specified in later sections, as
well as possible future extensions such as messages enabling power
conservation / sleep mode, multicast routing, support for
unidirectional links, auto-configuration/address assignment etc.
3.5. Message Emission and Jitter
As a basic implementation requirement, synchronization of control messages SHOULD be avoided. As a consequence, OLSR control messages SHOULD be emitted such that they avoid synchronization. Emission of control traffic from neighboring nodes may, for various reasons (mainly timer interactions with packet processing), become synchronized such that several neighbor nodes attempt to transmit control traffic simultaneously. Depending on the nature of the underlying link-layer, this may or may not lead to collisions and hence message loss - possibly loss of several subsequent messages of the same type. To avoid such synchronizations, the following simple strategy for emitting control messages is proposed. A node SHOULD add an amount of jitter to the interval at which messages are generated. The jitter must be a random value for each message generated. Thus, for a node utilizing jitter: Actual message interval = MESSAGE_INTERVAL - jitter Where jitter is a value, randomly selected from the interval [0,MAXJITTER] and MESSAGE_INTERVAL is the value of the message interval specified for the message being emitted (e.g., HELLO_INTERVAL for HELLO messages, TC_INTERVAL for TC-messages etc.). Jitter SHOULD also be introduced when forwarding messages. The following simple strategy may be adopted: when a message is to be forwarded by a node, it should be kept in the node during a short period of time : Keep message period = jitter Where jitter is a random value in [0,MAXJITTER]. Notice that when the node sends a control message, the opportunity to piggyback other messages (before their keeping period is expired) may be taken to reduce the number of packet transmissions. Notice, that a minimal rate of control messages is imposed. A node MAY send control messages at a higher rate, if beneficial for a specific deployment.