participate in the OLSR MANET. These non OLSR interfaces may be
point to point connections to other singular hosts or may connect to
separate networks.
In order to provide connectivity from the OLSR MANET interface(s) to
these non OLSR interface(s), a node SHOULD be able to inject external
route information to the OLSR MANET.
Injecting routing information from the OLSR MANET to non OLSR
interfaces is outside the scope of this specification. It should be
clear, however, that the routing information for the OLSR MANET can
be extracted from the topology table (see section 4.4) or directly
from the routing table of OLSR, and SHOULD be injected onto the non
OLSR interfaces following whatever mechanism (routing protocol,
static configuration etc.) is provided on these interfaces.
An example of such a situation could be where a node is equipped with
a fixed network (e.g., an Ethernet) connecting to a larger network as
well as a wireless network interface running OLSR.
Notice that this is a different case from that of "multiple
interfaces", where all the interfaces are participating in the MANET
through running the OLSR protocol.
In order to provide this capability of injecting external routing
information into an OLSR MANET, a node with such non-MANET interfaces
periodically issues a Host and Network Association (HNA) message,
containing sufficient information for the recipients to construct an
appropriate routing table.
12.1. HNA Message Format
The proposed format of an HNA-message is:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Network Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Netmask |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Network Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Netmask |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This is sent as the data part of the general packet format with the
"Message Type" set to HNA_MESSAGE, the TTL field set to 255 and Vtime
set accordingly to the value of HNA_HOLD_TIME, as specified in
section 18.3.
Network Address
The network address of the associated network
Netmask
The netmask, corresponding to the network address immediately
above.
12.2. Host and Network Association Information Base
Each node maintains information concerning which nodes may act as
"gateways" to associated hosts and networks by recording "association
tuples" (A_gateway_addr, A_network_addr, A_netmask, A_time), where
A_gateway_addr is the address of an OLSR interface of the gateway,
A_network_addr and A_netmask specify the network address and netmask
of a network, reachable through this gateway, and A_time specifies
the time at which this tuple expires and hence *MUST* be removed.
The set of all association tuples in a node is called the
"association set".
It should be noticed, that the HNA-message can be considered as a
"generalized version" of the TC-message: the originator of both the
HNA- and TC-messages announce "reachability" to some other host(s).
In the TC-message, no netmask is required, since all reachability is
announced on a per-host basis. In HNA-messages, announcing
reachability to an address sequence through a network- and netmask
address is typically preferred over announcing reachability to
individual host addresses.
An important difference between TC- and HNA-messages is, that a TC
message may have a canceling effect on previous information (if the
ANSN is incremented), whereas information in HNA-messages is removed
only upon expiration.
12.3. HNA Message Generation
A node with associated hosts and/or networks SHOULD periodically
generate a Host and Network Association (HNA) message, containing
pairs of (network address, netmask) corresponding to the connected
hosts and networks. HNA-messages SHOULD be transmitted periodically
every HNA_INTERVAL. The Vtime is set accordingly to the value of
HNA_HOLD_TIME, as specified in section 18.3.
A node without any associated hosts and/or networks SHOULD NOT
generate HNA-messages.
12.4. HNA Message Forwarding
Upon receiving a HNA message, and thus following the rules of section
3, in this version of the specification, the message MUST be
forwarded according to section 3.4.
12.5. HNA Message Processing
In this section, the term "originator address" is used to designate
the main address on the OLSR MANET of the node which originally
issued the HNA-message.
Upon processing a HNA-message, the "validity time" MUST be computed
from the Vtime field of the message header (see section 3.3.2). The
association 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 Otherwise, for each (network address, netmask) pair in the
message:
2.1 if an entry in the association set already exists, where:
A_gateway_addr == originator address
A_network_addr == network address
A_netmask == netmask
then the holding time for that tuple MUST be set to:
A_time = current time + validity time
2.2 otherwise, a new tuple MUST be recorded with:
A_gateway_addr = originator address
A_network_addr = network address
A_netmask = netmask
A_time = current time + validity time
12.6. Routing Table Calculation
In addition to the routing table computation as described in section
10, the host and network association set MUST be added as follows:
For each tuple in the association set,
1 If there is no entry in the routing table with:
R_dest_addr == A_network_addr/A_netmask
then a new routing entry is created.
2 If a new routing entry was created at the previous step, or
else if there existed one with:
R_dest_addr == A_network_addr/A_netmask
R_dist > dist to A_gateway_addr of
current association set tuple,
then the routing entry is modified as follows:
R_dest_addr = A_network_addr/A_netmask
R_next_addr = the next hop on the path
from the node to A_gateway_addr
R_dist = dist to A_gateway_addr
R_next_addr and R_iface_addr MUST be set to the same
values as the tuple from the routing set with R_dest_addr
== A_gateway_addr.
12.7. Interoperability Considerations
Nodes, which do not implement support for non OLSR interfaces, can
coexist in a network with nodes which do implement support for non
OLSR interfaces: the generic packet format and message forwarding
(section 3) ensures that HNA messages are correctly forwarded by all
nodes. Nodes which implement support for non OLSR interfaces may
thus transmit and process HNA messages according to this section.
Nodes, which do not implement support for non OLSR interfaces can not
take advantage of the functionality specified in this section,
however they will forward HNA messages correctly, as specified in
section 3.
13. Link Layer Notification
OLSR is designed not to impose or expect any specific information
from the link layer. However, if information from the link-layer
describing link breakage is available, a node MAY use this as
described in this section.
If link layer information describing connectivity to neighboring
nodes is available (i.e., loss of connectivity such as through
absence of a link layer acknowledgment), this information is used in
addition to the information from the HELLO-messages to maintain the
neighbor information base and the MPR selector set.
Thus, upon receiving a link-layer notification that the link between
a node and a neighbor interface is broken, the following actions are
taken with respect to link sensing:
Each link tuple in the local link set SHOULD, in addition to what is
described in section 4.2, include a L_LOST_LINK_time field.
L_LOST_LINK_time is a timer for declaring a link as lost when an
established link becomes pending. (Notice, that this is a subset of
what is recommended in section 14, thus link hysteresis and link
layer notifications can coexist).
HELLO message generation should consider those new fields as follows:
1 if L_LOST_LINK_time is not expired, the link is advertised
with a link type of LOST_LINK. In addition, it is not
considered as a symmetric link in the updates of the
associated neighbor tuple (see section 8.1).
2 if the link to a neighboring symmetric or asymmetric interface
is broken, the corresponding link tuple is modified:
L_LOST_LINK_time and L_time are set to current time +
NEIGHB_HOLD_TIME.
3 this is considered as a link loss and the appropriate
processing described in section 8.5 should be
performed.
13.1. Interoperability Considerations
Link layer notifications provide, for a node, an additional criterion
by which a node may determine if a link to a neighbor node is lost.
Once a link is detected as lost, it is advertised, in accordance with
the provisions described in the previous sections of this
specification.
14. Link Hysteresis
Established links should be as reliable as possible to avoid data
packet loss. This implies that link sensing should be robust against
bursty loss or transient connectivity between nodes. Hence, to
enhance the robustness of the link sensing mechanism, the following
implementation recommendations SHOULD be considered.
14.1. Local Link Set
Each link tuple in the local link set SHOULD, in addition to what is
described in section 4.2, include a L_link_pending field, a
L_link_quality field, and a L_LOST_LINK_time field. L_link_pending
is a boolean value specifying if the link is considered pending
(i.e., the link is not considered established). L_link_quality is a
dimensionless number between 0 and 1 describing the quality of the
link. L_LOST_LINK_time is a timer for declaring a link as lost when
an established link becomes pending.
14.2. Hello Message Generation
HELLO message generation should consider those new fields as follows:
1 if L_LOST_LINK_time is not expired, the link is advertised
with a link type of LOST_LINK.
2 otherwise, if L_LOST_LINK_time is expired and L_link_pending
is set to "true", the link SHOULD NOT be advertised at all;
3 otherwise, if L_LOST_LINK_time is expired and L_link_pending
is set to "false", the link is advertised as described
previously in section 6.
A node considers that it has a symmetric link for each link tuple
where:
1 L_LOST_LINK_time is expired, AND
2 L_link_pending is "false", AND
3 L_SYM_time is not expired.
This definition for "symmetric link" SHOULD be used in updating the
associated neighbor tuple (see section 8.1) for computing the
N_status of a neighbor node. This definition SHOULD thereby also be
used as basis for the symmetric neighborhood when computing the MPR
set, as well as for "the symmetric neighbors" in the first steps of
the routing table calculation.
Apart from the above, what has been described previously does not
interfere with the advanced link sensing fields in the link tuples.
The L_link_quality, L_link_pending and L_LOST_LINK_time fields are
exclusively updated according to the present section. This section
does not modify the function of any other fields in the link tuples.
14.3. Hysteresis Strategy
The link between a node and some of its neighbor interfaces might be
"bad", i.e., from time to time let HELLOs pass through only to fade
out immediately after. In this case, the neighbor information base
would contain a bad link for at least "validity time". The following
hysteresis strategy SHOULD be adopted to counter this situation.
For each neighbor interface NI heard by interface I, the
L_link_quality field of the corresponding Link Tuple determines the
establishment of the link. The value of L_link_quality is compared
to two thresholds HYST_THRESHOLD_HIGH, HYST_THRESHOLD_LOW, fixed
between 0 and 1 and such that HYST_THRESHOLD_HIGH >=
HYST_THRESHOLD_LOW.
The L_link_pending field is set according to the following:
1 if L_link_quality > HYST_THRESHOLD_HIGH:
L_link_pending = false
L_LOST_LINK_time = current time - 1 (expired)
2 otherwise, if L_link_quality < HYST_THRESHOLD_LOW:
L_link_pending = true
L_LOST_LINK_time = min (L_time, current time +
NEIGHB_HOLD_TIME)
(the link is then considered as lost according to section
8.5 and this may produce a neighbor loss).
3 otherwise, if HYST_THRESHOLD_LOW <= L_link_quality
<= HYST_THRESHOLD_HIGH:
L_link_pending and L_LOST_LINK_time remain unchanged.
The condition for considering a link established is thus stricter
than the condition for dropping a link. Notice thus, that a link can
be dropped based on either timer expiration (as described in section
7) or on L_link_quality dropping below HYST_THRESHOLD_LOW.
Also notice, that even if a link is not considered as established by
the link hysteresis, the link tuples are still updated for each
received HELLO message (as described in section 7). Specifically,
this implies that, regardless of whether or not the link hysteresis
considers a link as "established", tuples in the link set do not
expire except as determined by the L_time field of the link tuples.
As a basic implementation requirement, an estimation of the link
quality must be maintained and stored in the L_link_quality field.
If some measure of the signal/noise level on a received message is
available (e.g., as a link layer notification), then it can be used
as estimation after normalization.
If no signal/noise information or other link quality information is
available from the link layer, an algorithm such as the following can
be utilized (it is an exponentially smoothed moving average of the
transmission success rate). The algorithm is parameterized by a
scaling parameter HYST_SCALING which is a number fixed between 0 and
1. For each neighbor interface NI heard by interface I, the first
time NI is heard by I, L_link_quality is set to HYST_SCALING
(L_link_pending is set to true and L_LOST_LINK_time to current time -
1).
A tuple is updated according to two rules. Every time an OLSR packet
emitted by NI is received by I, the stability rule is applied:
L_link_quality = (1-HYST_SCALING)*L_link_quality
+ HYST_SCALING.
When an OLSR packet emitted by NI is lost by I, the instability
rule is applied:
L_link_quality = (1-HYST_SCALING)*L_link_quality.
The loss of OLSR packet is detected by tracking the missing Packet
Sequence Numbers on a per interface basis and by "long period of
silence" from a node. A "long period of silence may be detected
thus: if no OLSR packet has been received on interface I from
interface NI during HELLO emission interval of interface NI (computed
from the Htime field in the last HELLO message received from NI), a
loss of an OLSR packet is detected.
14.4. Interoperability Considerations
Link hysteresis determines, for a node, the criteria at which a link
to a neighbor node is accepted or rejected. Nodes in a network may
have different criteria, according to the nature of the media over
which they are communicating. Once a link is accepted, it is
advertised, in accordance with the provisions described in the
previous sections of this specification.
15. Redundant Topology Information
In order to provide redundancy to topology information base, the
advertised link set of a node MAY contain links to neighbor nodes
which are not in MPR selector set of the node. The advertised link
set MAY contain links to the whole neighbor set of the node. The
minimal set of links that any node MUST advertise in its TC messages
is the links to its MPR selectors. The advertised link set can be
built according to the following rule based on a local parameter
called TC_REDUNDANCY parameter.
15.1. TC_REDUNDANCY Parameter
The parameter TC_REDUNDANCY specifies, for the local node, the amount
of information that MAY be included in the TC messages. The
parameter SHOULD be interpreted as follows:
- if the TC_REDUNDANCY parameter of the node is 0, then the
advertised link set of the node is limited to the MPR
selector set (as described in section 8.3),
- if the TC_REDUNDANCY parameter of the node is 1, then the
advertised link set of the node is the union of its MPR set
and its MPR selector set,
- if the TC_REDUNDANCY parameter of the node is 2, then the
advertised link set of the node is the full neighbor link set.
A node with willingness equal to WILL_NEVER SHOULD have TC_REDUNDANCY
also equal to zero.
15.2. Interoperability Considerations
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. This is sufficient
information to ensure that routes can be computed in accordance with
section 10.
The provisions in this section specifies how additional information
may be declared, as specified through a TC_REDUNDANCY parameter.
TC_REDUNDANCY = 0 implies that the information declared corresponds
exactly to the MPR Selector set, identical to section 9. Other
values of TC_REDUNDANCY specifies additional information to be
declared, i.e., the contents of the MPR Selector set is always
declared. Thus, nodes with different values of TC_REDUNDANCY may
coexist in a network: control messages are carried by all nodes in
accordance with section 3, and all nodes will receive at least the
link-state information required to construct routes as described in
section 10.
16. MPR Redundancy
MPR redundancy specifies the ability for a node to select redundant
MPRs. Section 4.5 specifies that a node should select its MPR set to
be as small as possible, in order to reduce protocol overhead. The
criteria for selecting MPRs is, that all strict 2-hop nodes must be
reachable through, at least, one MPR node. Redundancy of the MPR set
affects the overhead through affecting the amount of links being
advertised, the amount of nodes advertising links and the efficiency
of the MPR flooding mechanism. On the other hand, redundancy in the
MPR set ensures that reachability for a node is advertised by more
nodes, thus additional links are diffused to the network.
While, in general, a minimal MPR set provides the least overhead,
there are situations in which overhead can be traded off for other
benefits. For example, a node may decide to increase its MPR
coverage if it observes many changes in its neighbor information base
caused by mobility, while otherwise keeping a low MPR coverage.
16.1. MPR_COVERAGE Parameter
The MPR coverage is defined by a single local parameter,
MPR_COVERAGE, specifying by how many MPR nodes any strict 2-hop node
should be covered. MPR_COVERAGE=1 specifies that the overhead of the
protocol is kept at a minimum and causes the MPR selection to operate
as described in section 8.3.1. MPR_COVERAGE=m ensures that, if
possible, a node selects its MPR set such that all strict 2-hop nodes
for an interface are reachable through at least m MPR nodes on that
interface. MPR_COVERAGE can assume any integer value > 0. 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.
Notice that MPR_COVERAGE can be tuned locally without affecting the
consistency of the protocol. For example, nodes in a network may
operate with different values of MPR_COVERAGE.
16.2. MPR Computation
Using MPR coverage, the MPR selection heuristics is extended from
that described in the section 8.3.1 by one definition:
Poorly covered node:
A poorly covered node is a node in N2 which is covered by less
than MPR_COVERAGE nodes in N.
The proposed heuristic for selecting MPRs is then as follows:
1 Start with an MPR set made of all members of N with
willingness equal to WILL_ALWAYS
2 Calculate D(y), where y is a member of N, for all nodes in N.
3 Select as MPRs those nodes in N which cover the poorly covered
nodes in N2. The nodes are then removed from N2 for the rest
of the computation.
4 While there exist nodes in N2 which are not covered by at
least MPR_COVERAGE nodes 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 MPR_COVERAGE nodes in the MPR set, and
which are reachable through this 1-hop neighbor;
4.2 Select as a MPR the node with highest willingness among
the nodes in N with non-zero reachability. In case of