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.
4. Information Repositories
Through the exchange of OLSR control messages, each node accumulates
information about the network. This information is stored according
to the descriptions in this section.
4.1. Multiple Interface Association Information Base
For each destination in the network, "Interface Association Tuples"
(I_iface_addr, I_main_addr, I_time) are recorded. I_iface_addr is an
interface address of a node, I_main_addr is the main address of this
node. I_time specifies the time at which this tuple expires and
*MUST* be removed.
In a node, the set of Interface Association Tuples is denoted the
"Interface Association Set".
4.2. Link Sensing: Local Link Information Base
The local link information base stores information about links to
neighbors.
4.2.1. Link Set
A node records a set of "Link Tuples" (L_local_iface_addr,
L_neighbor_iface_addr, L_SYM_time, L_ASYM_time, L_time).
L_local_iface_addr is the interface address of the local node (i.e.,
one endpoint of 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.
This information is used when declaring the neighbor interfaces in
the HELLO messages.
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
asymmetric. If both L_SYM_time and L_ASYM_time are expired, the link
MUST be declared lost.
In a node, the set of Link Tuples are denoted the "Link Set".
4.3. Neighbor Detection: Neighborhood Information Base
The neighborhood information base stores information about neighbors,
2-hop neighbors, MPRs and MPR selectors.
4.3.1. Neighbor Set
A node records a set of "neighbor tuples" (N_neighbor_main_addr,
N_status, N_willingness), describing neighbors. N_neighbor_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 the node’s willingness to carry traffic on behalf of other
nodes.
4.3.2. 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.
In a node, the set of 2-hop tuples are denoted the "2-hop Neighbor
Set".
4.3.3. MPR Set
A node maintains a set of neighbors which are selected as MPR. Their
main addresses are listed in the MPR Set.
4.3.4. MPR Selector Set
A node records a set of MPR-selector tuples (MS_main_addr, MS_time),
describing the neighbors which have selected this node as a MPR.
MS_main_addr is the main address of a node, which has selected this
node as MPR. MS_time specifies the time at which the tuple expires
and *MUST* be removed.
In a node, the set of MPR-selector tuples are denoted the "MPR
Selector Set".
4.4. Topology Information Base
Each node in the network maintains topology information about the
network. This information is acquired from TC-messages and is used
for routing table calculations.
Thus, for each destination in the network, at least one "Topology
Tuple" (T_dest_addr, T_last_addr, T_seq, T_time) is recorded.
T_dest_addr is the main address of a node, which may be reached in
one hop from the node with the main address T_last_addr. Typically,
T_last_addr is a MPR of T_dest_addr. T_seq is a sequence number, and
T_time specifies the time at which this tuple expires and *MUST* be
removed.
In a node, the set of Topology Tuples are denoted the "Topology Set".
5. Main Addresses and Multiple Interfaces
For single OLSR interface nodes, the relationship between an OLSR
interface address and the corresponding main address is trivial: the
main address is the OLSR interface address. For multiple OLSR
interface nodes, the relationship between OLSR interface addresses
and main addresses is defined through the exchange of Multiple
Interface Declaration (MID) messages. This section describes how MID
messages are exchanged and processed.
Each node with multiple interfaces MUST announce, periodically,
information describing its interface configuration to other nodes in
the network. This is accomplished through flooding a Multiple
Interface Declaration message to all nodes in the network through the
MPR flooding mechanism.
Each node in the network maintains interface information about the
other nodes in the network. This information acquired from MID
messages, emitted by nodes with multiple interfaces participating in
the MANET, and is used for routing table calculations.
Specifically, multiple interface declaration associates multiple
interfaces to a node (and to a main address) through populating the
multiple interface association base in each node.
5.1. MID Message Format
The proposed format of a MID message is as follows:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| OLSR Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| OLSR Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This is sent as the data-portion of the general packet format
described in section 3.4, with the "Message Type" set to MID_MESSAGE.
The time to live SHOULD be set to 255 (maximum value) to diffuse the
message into the entire network and Vtime set accordingly to the
value of MID_HOLD_TIME, as specified in section 18.3.
OLSR Interface Address
This field contains the address of an OLSR interface of the
node, excluding the nodes main address (which already
indicated in the originator address).
All interface addresses other than the main address of the originator
node are put in the MID message. If the maximum allowed message size
(as imposed by the network) is reached while there are still
interface addresses which have not been inserted into the MIDmessage,
more MID messages are generated until the entire interface addresses
set has been sent.
5.2. MID Message Generation
A MID message is sent by a node in the network to declare its
multiple interfaces (if any). I.e., the MID message contains the
list of interface addresses which are associated to its main address.
The list of addresses can be partial in each MID message (e.g., due
to message size limitations, imposed by the network), but parsing of
all MID messages describing the interface set from a node MUST be
complete within a certain refreshing period (MID_INTERVAL). The
information diffused in the network by these MID messages will help
each node to calculate its routing table. A node which has only a
single interface address participating in the MANET (i.e., running
OLSR), MUST NOT generate any MID message.
A node with several interfaces, where only one is participating in
the MANET and running OLSR (e.g., a node is connected to a wired
network as well as to a MANET) MUST NOT generate any MID messages.
A node with several interfaces, where more than one is participating
in the MANET and running OLSR MUST generate MID messages as
specified.
5.3. MID Message Forwarding
MID messages are broadcast and retransmitted by the MPRs in order to
diffuse the messages in the entire network. The "default forwarding
algorithm" (described in section 3.4) MUST be used for forwarding of
MID messages.
5.4. MID Message Processing
The tuples in the multiple interface association set are recorded
with the information that is exchanged through MID messages.
Upon receiving a MID message, the "validity time" MUST be computed
from the Vtime field of the message header (as described in section
3.3.2). The Multiple Interface Association Information Base SHOULD
then be updated as follows:
1 If the sender interface (NB: not originator) of this message
is not in the symmetric 1-hop neighborhood of this node, the
message MUST be discarded.
2 For each interface address listed in the MID message:
2.1 If there exist some tuple in the interface association
set where:
I_iface_addr == interface address, AND
I_main_addr == originator address,
then the holding time of that tuple is set to:
I_time = current time + validity time.
2.2 Otherwise, a new tuple is recorded in the interface
association set where:
I_iface_addr = interface address,
I_main_addr = originator address,
I_time = current time + validity time.
5.5. Resolving a Main Address from an Interface Address
In general, the only part of OLSR requiring use of "interface
addresses" is link sensing. The remaining parts of OLSR operate on
nodes, uniquely identified by their "main addresses" (effectively,
the main address of a node is its "node id" - which for convenience
corresponds to the address of one of its interfaces). In a network
with only single interface nodes, the main address of a node will, by
definition, be equal to the interface address of the node. In
networks with multiple interface nodes operating within a common OLSR
area, it is required to be able to map any interface address to the
corresponding main address.
The exchange of MID messages provides a way in which interface
information is acquired by nodes in the network. This permits
identification of a node’s "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
interface address itself.
6. HELLO Message Format and Generation
A common mechanism is employed for populating the local link
information base and the neighborhood information base, namely
periodic exchange of HELLO messages. Thus this section describes the
general HELLO message mechanism, followed by a description of link
sensing and topology detection, respectively.
6.1. HELLO Message Format
To accommodate for link sensing, neighborhood detection and MPR
selection signalling, 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 as follows:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved | Htime | Willingness |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Code | Reserved | Link Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: . . . :
: :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Code | Reserved | Link Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: :
: :
(etc.)
This is sent as the data-portion of the general packet format
described in section 3.4, with the "Message Type" set to
HELLO_MESSAGE, the TTL field set to 1 (one) and Vtime set accordingly
to the value of NEIGHB_HOLD_TIME, specified in section 18.3.
Reserved
This field must be set to "0000000000000" to be in compliance
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 may be used in
advanced link sensing, see section 14). The HELLO emission
interval is represented 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 [in seconds]
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 18.
Willingness
This field specifies the willingness of a node to carry and
forward traffic for other nodes.
A node with willingness WILL_NEVER (see section 18.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
willingness of WILL_DEFAULT.
Link Code
This field specifies information about the link between the
interface of the sender and the following list of neighbor
interfaces. It also specifies information about the status of
the neighbor.
Link codes, not known by a node, are silently discarded.
Link Message Size
The size of the link message, counted in bytes and measured
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).
Neighbor Interface Address
The address of an interface of a neighbor node.
6.1.1. Link Code as Link Type and Neighbor Type
This document only specifies processing of Link Codes < 16.
If the Link Code value is less than or equal to 15, then it MUST be
interpreted 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 |
+-------+-------+-------+-------+-------+-------+-------+-------+