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 selected as MPR by the sender.
- NOT_NEIGH - indicating that the nodes are either no longer or
have not yet become symmetric neighbors.
Note that an implementation should be careful in confusing neither
Link Type with Neighbor Type nor the constants (confusing SYM_NEIGH
with SYM_LINK for instance).
A link code advertising:
Link Type == SYM_LINK AND
Neighbor Type == NOT_NEIGH
is invalid, and any links advertised as such MUST be silently
discarded without any processing.
Likewise a Neighbor Type field advertising a numerical value which is
not one of the constants SYM_NEIGH, MPR_NEIGH, NOT_NEIGH, is invalid,
and any links advertised as such MUST be silently discarded without
any processing.
6.2. HELLO Message Generation
This involves transmitting the Link Set, the Neighbor Set and the MPR
Set. In principle, a HELLO message serves three independent tasks:
- link sensing
- neighbor detection
- MPR selection signaling
Three tasks are all are based on periodic information exchange within
a nodes neighborhood, and serve the common purpose of "local topology
discovery". A HELLO message is therefore generated based on the
information stored in the Local Link Set, the Neighbor Set and the
MPR Set from the local link information base.
A node must perform link sensing on each interface, in order to
detect links between the interface and neighbor interfaces.
Furthermore, a node must advertise its entire symmetric 1-hop
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).
The Vtime field is set such that it corresponds to the value of the
node’s NEIGHB_HOLD_TIME parameter. The Htime field is set such that
it corresponds to the value of the node’s HELLO_INTERVAL parameter
(see section 18.3).
The Willingness field is set such that it corresponds to the node’s
willingness to forward traffic on behalf of other nodes (see section
18.8). A node MUST advertise the same willingness on all interfaces.
The lists of addresses declared in a HELLO message is a list of
neighbor interface addresses computed as follows:
For each tuple in the Link Set, where L_local_iface_addr is the
interface where the HELLO is to be transmitted, and where L_time >=
current time (i.e., not expired), L_neighbor_iface_addr is advertised
with:
1 The Link Type set according to the following:
1.1 if L_SYM_time >= current time (not expired)
Link Type = SYM_LINK
1.2 Otherwise, if L_ASYM_time >= current time (not expired)
AND
L_SYM_time < current time (expired)
Link Type = ASYM_LINK
1.3 Otherwise, if L_ASYM_time < current time (expired) AND
L_SYM_time < current time (expired)
Link Type = LOST_LINK
2 The Neighbor Type is set according to the following:
2.1 If the main address, corresponding to
L_neighbor_iface_addr, is included in the MPR set:
Neighbor Type = MPR_NEIGH
2.2 Otherwise, if the main address, corresponding to
L_neighbor_iface_addr, is included in the neighbor set:
2.2.1
if N_status == SYM
Neighbor Type = SYM_NEIGH
2.2.2
Otherwise, if N_status == NOT_SYM
Neighbor Type = NOT_NEIGH
For each tuple in the Neighbor Set, for which no
L_neighbor_iface_addr from an associated link tuple has been
advertised by the previous algorithm, N_neighbor_main_addr is
advertised with:
- Link Type = UNSPEC_LINK,
- Neighbor Type set as described in step 2 above
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.
A HELLO message can be partial (e.g., due to message size
limitations, imposed by the network), the rule being the following,
on each interface: each link and each neighbor node MUST be cited at
least once within a predetermined refreshing period,
REFRESH_INTERVAL. 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
is desirable that a message (plus the generic packet header) can fit
into a single MAC frame.
6.3. HELLO Message Forwarding
Each HELLO message generated is broadcast by the node on one
interface to its neighbors (i.e. the interface for which the HELLO
was generated). HELLO messages MUST never be forwarded.
6.4. HELLO Message Processing
A node processes incoming HELLO messages for the purpose of
conducting link sensing (detailed in section 7), neighbor detection
and MPR selector set population (detailed in section 8)
7. Link Sensing
Link sensing populates the local link information base. Link sensing
is exclusively concerned with OLSR interface addresses and the
ability to exchange packets between such OLSR interfaces.
The mechanism for link sensing is the periodic exchange of HELLO
messages.
7.1. Populating the Link Set
The Link Set is populated with information on links to neighbor
nodes. The process of populating this set is denoted "link sensing"
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.
Uncertainties over radio propagation may make some links
unidirectional. Consequently, all links MUST be checked in both
directions in order to be considered valid.
A "link" is described by a pair of interfaces: a local and a remote
interface.
For the purpose of link sensing, each neighbor node (more
specifically, the link to each neighbor) has an associated status of
either "symmetric" or "asymmetric". "Symmetric" indicates, that the
link to 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).
The information, acquired through and used by the link sensing, is
accumulated in the link set.
7.1.1. HELLO Message Processing
The "Originator Address" of a HELLO message is the main address of
the node, which has emitted the message.
Upon receiving a HELLO message, a node SHOULD update its Link Set.
Notice, that a HELLO message MUST neither be forwarded nor be
recorded in the duplicate set.
Upon receiving a HELLO message, the "validity time" MUST be computed
from the Vtime field of the message header (see section 3.3.2).
Then, the Link Set SHOULD be updated as follows:
1 Upon receiving a HELLO message, if there exists no link tuple
with
L_neighbor_iface_addr == Source Address
a new tuple is created with
L_neighbor_iface_addr = Source Address
L_local_iface_addr = Address of the interface
which received the
HELLO message
L_SYM_time = current time - 1 (expired)
L_time = current time + validity time
2 The tuple (existing or new) with:
L_neighbor_iface_addr == Source Address
is then modified as follows:
2.1 L_ASYM_time = current time + validity time;
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:
2.2.1
if Link Type is equal to LOST_LINK then
L_SYM_time = current time - 1 (i.e., expired)
2.2.2
else if Link Type is equal to SYM_LINK or ASYM_LINK
then
L_SYM_time = current time + validity time,
L_time = L_SYM_time + NEIGHB_HOLD_TIME
2.3 L_time = max(L_time, L_ASYM_time)
The above rule for setting L_time is the following: a link losing its
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.
8. Neighbor Detection
Neighbor detection populates the neighborhood information base and
concerns itself with nodes and node main addresses. The relationship
between OLSR interface addresses and main addresses is described in
section 5.
The mechanism for neighbor detection is the periodic exchange of
HELLO messages.
8.1. Populating the Neighbor Set
A node maintains a set of neighbor tuples, based on the link tuples.
This information is updated according to changes in the Link Set.
The Link Set keeps the information about the links, while the
Neighbor Set keeps the information about the neighbors. There is a
clear association between those two sets, since a node is a neighbor
of another node if and only if there is at least one link between the
two nodes.
In any case, the formal correspondence between links and neighbors is
defined as follows:
The "associated neighbor tuple" of a link tuple, is, if it
exists, the neighbor tuple where:
N_neighbor_main_addr == main address of
L_neighbor_iface_addr
The "associated link tuples" of a neighbor tuple, are all the
link tuples, where:
N_neighbor_main_addr == main address of
L_neighbor_iface_addr
The Neighbor Set MUST be populated by maintaining the proper
correspondence between link tuples and associated neighbor tuples, as
follows:
Creation
Each time a link appears, that is, each time a link tuple is
created, the associated neighbor tuple MUST be created, if it
doesn’t already exist, with the following values:
N_neighbor_main_addr = main address of
L_neighbor_iface_addr
(from the link tuple)
In any case, the N_status MUST then be computed as described
in the next step
Update
Each time a link changes, that is, each time the information
of a link tuple is modified, the node MUST ensure that the
N_status of the associated neighbor tuple respects the
property:
If the neighbor has any associated link tuple which
indicates a symmetric link (i.e., with L_SYM_time >=
current time), then
N_status is set to SYM
else N_status is set to NOT_SYM
Removal
Each time a link is deleted, that is, each time a link tuple
is removed, the associated neighbor tuple MUST be removed if
it has no longer any associated link tuples.
These rules ensure that there is exactly one associated neighbor
tuple for a link tuple, and that every neighbor tuple has at least
one associated link tuple.
8.1.1. HELLO Message Processing
The "Originator Address" of a HELLO message is the main address of
the node, which has emitted the message. Likewise, the "willingness"
MUST be computed from the Willingness field of the HELLO message (see
section 6.1).
Upon receiving a HELLO message, a node SHOULD first update its Link
Set as described before. It SHOULD then update its Neighbor Set as
follows:
- if the Originator Address is the N_neighbor_main_addr from a
neighbor tuple included in the Neighbor Set:
then, the neighbor tuple SHOULD be updated as follows:
N_willingness = willingness from the HELLO message
8.2. Populating the 2-hop Neighbor Set
The 2-hop neighbor set describes the set of nodes which have a
symmetric link to a symmetric neighbor. This information set is
maintained through periodic exchange of HELLO messages as described
in this section.
8.2.1. HELLO Message Processing
The "Originator Address" of a HELLO message is the main address of
the node, which has emitted the message.
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 set.
Upon receiving a HELLO message, the "validity time" MUST be computed
from the Vtime field of the message header (see section 3.3.2).
If the Originator Address is the main address of a
L_neighbor_iface_addr from a link tuple included in the Link Set with
L_SYM_time >= current time (not expired)
(in other words: if the Originator Address is a symmetric neighbor)
then the 2-hop Neighbor Set SHOULD be updated as follows:
1 for each address (henceforth: 2-hop neighbor address), listed
in the HELLO message with Neighbor Type equal to SYM_NEIGH or
MPR_NEIGH:
1.1 if the main address of the 2-hop neighbor address = main
address of the receiving node:
silently discard the 2-hop neighbor address.
(in other words: a node is not its own 2-hop neighbor).
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.
8.3. 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.
Each node in the network selects, independently, its own set of MPRs
among its symmetric 1-hop neighborhood. The symmetric links with
MPRs are advertised with Link Type MPR_NEIGH instead of SYM_NEIGH in
HELLO messages.
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. (Notice that a node, a, which is a direct neighbor
of another node, b, is not also a strict 2-hop neighbor of node b).
This means that the union of the symmetric 1-hop neighborhoods of the
MPR nodes contains the symmetric strict 2-hop neighborhood. MPR set
recalculation should occur when changes are detected in the symmetric
neighborhood or in the symmetric strict 2-hop neighborhood.
MPRs are computed per interface, the union of the MPR sets of each
interface make up the MPR set for the node.
While it is not essential that the MPR set is minimal, it is
essential that all strict 2-hop neighbors can be reached through the
selected MPR nodes. A node SHOULD select an MPR set such that any
strict 2-hop neighbor is covered by at least one MPR node. Keeping
the MPR set small ensures that the overhead of the protocol is kept
at a minimum.
The MPR set can coincide with the entire symmetric neighbor set.
This could be the case at network initialization (and will correspond
to classic link-state routing).
8.3.1. MPR Computation
The following specifies a proposed heuristic for selection of MPRs.
It constructs an MPR-set that enables a node to reach any node in the
symmetrical strict 2-hop neighborhood through relaying by one MPR
node with willingness different from WILL_NEVER. The heuristic MUST
be applied per interface, I. The MPR set for a node is the union of
the MPR sets found for each interface. The following terminology
will be used in describing the heuristics:
neighbor of an interface
a node is a "neighbor of an interface" if the interface
(on the local node) has a link to any one interface of
the neighbor node.
2-hop neighbors reachable from an interface
the list of 2-hop neighbors of the node that can be
reached from neighbors of this interface.
MPR set of an interface
a (sub)set of the neighbors of an interface with a
willingness different from WILL_NEVER, selected such that
through these selected nodes, all strict 2-hop neighbors
reachable from that interface are reachable.
N:
N is the subset of neighbors of the node, which are
neighbor of the interface I.
N2:
The set of 2-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.
D(y):
The degree of a 1-hop neighbor node y (where y is a
member of N), is defined as the number of symmetric
neighbors of node y, EXCLUDING all the members of N and
EXCLUDING the node performing the computation.
The proposed heuristic is as follows:
1 Start with an MPR set made of all members of N with
N_willingness equal to WILL_ALWAYS
2 Calculate D(y), where y is a member of N, for all nodes in N.
3 Add to the MPR set those nodes in N, which are the *only*
nodes to provide reachability to a node in N2. For example,
if node b in N2 can be reached only through a symmetric link
to node a in N, then add node a to the MPR set. Remove the
nodes from N2 which are now covered by a node in the MPR set.
4 While there exist nodes in N2 which are not covered by at
least one node in the MPR set:
4.1 For each node in N, calculate the reachability, i.e., the
number of nodes in N2 which are not yet covered by at
least one node in the MPR set, and which are reachable
through this 1-hop neighbor;
4.2 Select as a MPR the node with highest N_willingness among
the nodes in N with non-zero reachability. In case of
multiple choice select the node which provides
reachability to the maximum number of nodes in N2. In
case of multiple nodes providing the same amount of