reachability, select the node as MPR whose D(y) is
greater. Remove the nodes from N2 which are now covered
by a node in the MPR set.
5 A node’s MPR set is generated from the union of the MPR sets
for each interface. As an optimization, process each node, y,
in the MPR set in increasing order of N_willingness. If all
nodes in N2 are still covered by at least one node in the MPR
set excluding node y, and if N_willingness of node y is
smaller than WILL_ALWAYS, then node y MAY be removed from the
MPR set.
Other algorithms, as well as improvements over this algorithm, are
possible. For example, assume that in a multiple-interface scenario
there exists more than one link between nodes ’a’ and ’b’. If node
’a’ has selected node ’b’ as MPR for one of its interfaces, then node
’b’ can be selected as MPR without additional performance loss by any
other interfaces on node ’a’.
8.4. Populating the MPR Selector Set
The MPR selector set of a node, n, is populated by the main addresses
of the nodes which have selected n as MPR. MPR selection is signaled
through HELLO messages.
8.4.1. HELLO Message Processing
Upon receiving a HELLO message, if a node finds one of its own
interface addresses in the list with a Neighbor Type equal to
MPR_NEIGH, information from the HELLO message must be recorded in the
MPR Selector Set.
The "validity time" MUST be computed from the Vtime field of the
message header (see section 3.3.2). The MPR Selector Set SHOULD then
be updated as follows:
1 If there exists no MPR selector tuple with:
MS_main_addr == Originator Address
then a new tuple is created with:
MS_main_addr = Originator Address
2 The tuple (new or otherwise) with
MS_main_addr == Originator Address
is then modified as follows:
MS_time = current time + validity time.
Deletion of MPR selector tuples occurs in case of expiration of the
timer or in case of link breakage as described in the "Neighborhood
and 2-hop Neighborhood Changes".
8.5. Neighborhood and 2-hop Neighborhood Changes
A change in the neighborhood is detected when:
- The L_SYM_time field of a link tuple expires. This is
considered as a neighbor loss if the link described by the
expired tuple was the last link with a neighbor node (on the
contrary, a link with an interface may break while a link with
another interface of the neighbor node remains without being
observed as a neighborhood change).
- A new link tuple is inserted in the Link Set with a non
expired L_SYM_time or a tuple with expired L_SYM_time is
modified so that L_SYM_time becomes non-expired. This is
considered as a neighbor appearance if there was previously no
link tuple describing a link with the corresponding neighbor
node.
A change in the 2-hop neighborhood is detected when a 2-hop neighbor
tuple expires or is deleted according to section 8.2.
The following processing occurs when changes in the neighborhood or
the 2-hop neighborhood are detected:
- In case of neighbor loss, all 2-hop tuples with
N_neighbor_main_addr == Main Address of the neighbor MUST be
deleted.
- In case of neighbor loss, all MPR selector tuples with
MS_main_addr == Main Address of the neighbor MUST be deleted
- The MPR set MUST be re-calculated when a neighbor appearance
or loss is detected, or when a change in the 2-hop
neighborhood is detected.
- An additional HELLO message MAY be sent when the MPR set
changes.
9. Topology Discovery
The link sensing and neighbor detection part of the protocol
basically offers, to each node, a list of neighbors with which it can
communicate directly and, in combination with the Packet Format and
Forwarding part, an optimized flooding mechanism through MPRs. Based
on this, topology information is disseminated through the network.
The present section describes which part of the information given by
the link sensing and neighbor detection is disseminated to the entire
network and how it is used to construct routes.
Routes are constructed through advertised links and links with
neighbors. A node must at least disseminate links between itself and
the nodes in its MPR-selector set, in order to provide sufficient
information to enable routing.
9.1. TC Message Format
The proposed format of a TC 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ANSN | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Advertised Neighbor Main Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Advertised Neighbor Main Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This is sent as the data-portion of the general message format with
the "Message Type" set to TC_MESSAGE. The time to live SHOULD be set
to 255 (maximum value) to diffuse the message into the entire network
and Vtime set accordingly to the value of TOP_HOLD_TIME, as specified
in section 18.3.
Advertised Neighbor Sequence Number (ANSN)
A sequence number is associated with the advertised neighbor
set. Every time a node detects a change in its advertised
neighbor set, it increments this sequence number ("Wraparound"
is handled as described in section 19). This number is sent
in this ANSN field of the TC message to keep track of the most
recent information. When a node receives a TC message, it can
decide on the basis of this Advertised Neighbor Sequence
Number, whether or not the received information about the
advertised neighbors of the originator node is more recent
than what it already has.
Advertised Neighbor Main Address
This field contains the main address of a neighbor node. All
main addresses of the advertised neighbors of the Originator
node are put in the TC message. If the maximum allowed
message size (as imposed by the network) is reached while
there are still advertised neighbor addresses which have not
been inserted into the TC-message, more TC messages will be
generated until the entire advertised neighbor set has been
sent. Extra main addresses of neighbor nodes may be included,
if redundancy is desired.
Reserved
This field is reserved, and MUST be set to "0000000000000000"
for compliance with this document.
9.2. Advertised Neighbor Set
A TC message is sent by a node in the network to declare a set of
links, called advertised link set which MUST include at least the
links to all nodes of its MPR Selector set, i.e., the neighbors which
have selected the sender node as a MPR.
If, for some reason, it is required to distribute redundant TC
information, refer to section 15.
The sequence number (ANSN) associated with the advertised neighbor
set is also sent with the list. The ANSN number MUST be incremented
when links are removed from the advertised neighbor set; the ANSN
number SHOULD be incremented when links are added to the advertised
neighbor set.
9.3. TC Message Generation
In order to build the topology information base, each node, which has
been selected as MPR, broadcasts Topology Control (TC) messages. TC
messages are flooded to all nodes in the network and take advantage
of MPRs. MPRs enable a better scalability in the distribution of
topology information [1].
The list of addresses can be partial in each TC message (e.g., due to
message size limitations, imposed by the network), but parsing of all
TC messages describing the advertised link set of a node MUST be
complete within a certain refreshing period (TC_INTERVAL). The
information diffused in the network by these TC messages will help
each node calculate its routing table.
When the advertised link set of a node becomes empty, this node
SHOULD still send (empty) TC-messages during the a duration equal to
the "validity time" (typically, this will be equal to TOP_HOLD_TIME)
of its previously emitted TC-messages, in order to invalidate the
previous TC-messages. It SHOULD then stop sending TC-messages until
some node is inserted in its advertised link set.
A node MAY transmit additional TC-messages to increase its
reactiveness to link failures. When a change to the MPR selector set
is detected and this change can be attributed to a link failure, a
TC-message SHOULD be transmitted after an interval shorter than
TC_INTERVAL.
9.4. TC Message Forwarding
TC messages are broadcast and retransmitted by the MPRs in order to
diffuse the messages in the entire network. TC messages MUST be
forwarded according to the "default forwarding algorithm" (described
in section 3.4).
9.5. TC Message Processing
Upon receiving a TC message, the "validity time" MUST be computed
from the Vtime field of the message header (see section 3.3.2). The
topology set SHOULD then be updated as follows (using section 19 for
comparison of ANSN):
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 If there exist some tuple in the topology set where:
T_last_addr == originator address AND
T_seq > ANSN,
then further processing of this TC message MUST NOT be
performed and the message MUST be silently discarded (case:
message received out of order).
3 All tuples in the topology set where:
T_last_addr == originator address AND
T_seq < ANSN
MUST be removed from the topology set.
4 For each of the advertised neighbor main address received in
the TC message:
4.1 If there exist some tuple in the topology set where:
T_dest_addr == advertised neighbor main address, AND
T_last_addr == originator address,
then the holding time of that tuple MUST be set to:
T_time = current time + validity time.
4.2 Otherwise, a new tuple MUST be recorded in the topology
set where:
T_dest_addr = advertised neighbor main address,
T_last_addr = originator address,
T_seq = ANSN,
T_time = current time + validity time.
10. Routing Table Calculation
Each node maintains a routing table which allows it to route data,
destined for the other nodes in the network. The routing table is
based on the information contained in the local link information base
and the topology set. Therefore, if any of these sets are changed,
the routing table is recalculated to update the route information
about each destination in the network. The route entries are
recorded in the routing table in the following format:
1. R_dest_addr R_next_addr R_dist R_iface_addr
2. R_dest_addr R_next_addr R_dist R_iface_addr
3. ,, ,, ,, ,,
Each entry in the table consists of R_dest_addr, R_next_addr, R_dist,
and R_iface_addr. Such entry specifies that the node identified by
R_dest_addr is estimated to be R_dist hops away from the local node,
that the symmetric neighbor node with interface address R_next_addr
is the next hop node in the route to R_dest_addr, and that this
symmetric neighbor node is reachable through the local interface with
the address R_iface_addr. Entries are recorded in the routing table
for each destination in the network for which a route is known. All
the destinations, for which a route is broken or only partially
known, are not recorded in the table.
More precisely, the routing table is updated when a change is
detected in either:
- the link set,
- the neighbor set,
- the 2-hop neighbor set,
- the topology set,
- the Multiple Interface Association Information Base,
More precisely, the routing table is recalculated in case of neighbor
appearance or loss, when a 2-hop tuple is created or removed, when a
topology tuple is created or removed or when multiple interface
association information changes. The update of this routing
information does not generate or trigger any messages to be
transmitted, neither in the network, nor in the 1-hop neighborhood.
To construct the routing table of node X, a shortest path algorithm
is run on the directed graph containing the arcs X -> Y where Y is
any symmetric neighbor of X (with Neighbor Type equal to SYM), the
arcs Y -> Z where Y is a neighbor node with willingness different of
WILL_NEVER and there exists an entry in the 2-hop Neighbor set with Y
as N_neighbor_main_addr and Z as N_2hop_addr, and the arcs U -> V,
where there exists an entry in the topology set with V as T_dest_addr
and U as T_last_addr.
The following procedure is given as an example to calculate (or
recalculate) the routing table:
1 All the entries from the routing table are removed.
2 The new routing entries are added starting with the
symmetric neighbors (h=1) as the destination nodes. Thus, for
each neighbor tuple in the neighbor set where:
N_status = SYM
(there is a symmetric link to the neighbor), and for each
associated link tuple of the neighbor node such that L_time >=
current time, a new routing entry is recorded in the routing
table with:
R_dest_addr = L_neighbor_iface_addr, of the
associated link tuple;
R_next_addr = L_neighbor_iface_addr, of the
associated link tuple;
R_dist = 1;
R_iface_addr = L_local_iface_addr of the
associated link tuple.
If in the above, no R_dest_addr is equal to the main address
of the neighbor, then another new routing entry with MUST be
added, with:
R_dest_addr = main address of the neighbor;
R_next_addr = L_neighbor_iface_addr of one of the
associated link tuple with L_time >=
current time;
R_dist = 1;
R_iface_addr = L_local_iface_addr of the
associated link tuple.
3 for each node in N2, i.e., a 2-hop neighbor which is not a
neighbor node or the node itself, and such that there exist at
least one entry in the 2-hop neighbor set where
N_neighbor_main_addr correspond to a neighbor node with
willingness different of WILL_NEVER, one selects one 2-hop
tuple and creates one entry in the routing table with:
R_dest_addr = the main address of the 2-hop neighbor;
R_next_addr = the R_next_addr of the entry in the
routing table with:
R_dest_addr == N_neighbor_main_addr
of the 2-hop tuple;
R_dist = 2;
R_iface_addr = the R_iface_addr of the entry in the
routing table with:
R_dest_addr == N_neighbor_main_addr
of the 2-hop tuple;
3 The new route entries for the destination nodes h+1 hops away
are recorded in the routing table. The following procedure
MUST be executed for each value of h, starting with h=2 and
incrementing it by 1 each time. The execution will stop if no
new entry is recorded in an iteration.
3.1 For each topology entry in the topology table, if its
T_dest_addr does not correspond to R_dest_addr of any
route entry in the routing table AND its T_last_addr
corresponds to R_dest_addr of a route entry whose R_dist
is equal to h, then a new route entry MUST be recorded in
the routing table (if it does not already exist) where:
R_dest_addr = T_dest_addr;
R_next_addr = R_next_addr of the recorded
route entry where:
R_dest_addr == T_last_addr
R_dist = h+1; and
R_iface_addr = R_iface_addr of the recorded
route entry where:
R_dest_addr == T_last_addr.
3.2 Several topology entries may be used to select a next hop
R_next_addr for reaching the node R_dest_addr. When h=1,
ties should be broken such that nodes with highest
willingness and MPR selectors are preferred as next hop.
4 For each entry in the multiple interface association base
where there exists a routing entry such that:
R_dest_addr == I_main_addr (of the multiple interface
association entry)
AND there is no routing entry such that:
R_dest_addr == I_iface_addr
then a route entry is created in the routing table with:
R_dest_addr = I_iface_addr (of the multiple interface
association entry)
R_next_addr = R_next_addr (of the recorded
route entry)
R_dist = R_dist (of the recorded
route entry)
R_iface_addr = R_iface_addr (of the recorded
route entry).
11. Node Configuration
This section outlines how a node should be configured, in order to
operate in an OLSR MANET.
11.1. Address Assignment
The nodes in the MANET network SHOULD be assigned addresses within a
defined address sequence, i.e., the nodes in the MANET SHOULD be
addressable through a network address and a netmask.
Likewise, the nodes in each associated network SHOULD be assigned
addresses from a defined address sequence, distinct from that being
used in the MANET.
11.2. Routing Configuration
Any MANET node with associated networks or hosts SHOULD be configured
such that it has routes set up to the interfaces with associated
hosts or network.
11.3. Data Packet Forwarding
OLSR itself does not perform packet forwarding. Rather, it maintains
the routing table in the underlying operating system, which is
assumed to be forwarding packets as specified in RFC1812.
12. Non OLSR Interfaces
A node MAY be equipped with multiple interfaces, some of which do not