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