[OLSR-users] Link quality extension to olsrd

[Thomas Lopatic]

Hi there,

The CVS version of olsrd now contains code that implements the 
calculation of routes based on the quality of the links between the 
individual nodes. I'd be interested in getting feedback on this feature 
before we get 0.4.8 ready. I'd like the code to get some testing as it 
probably still contains numerous bugs.

Let me quickly give you an overview of how the link quality code works.

 >>> Packet loss detection

* We look at the sequence numbers of OLSR packets received from our 
neighbours to detect lost packets. We then calculate how many of the 
past 10 packets that each of our neighbours sent us actually made it to 
us. In this way we're able to calculate the packet loss for each 
neighbour. Note that measuring the packet loss in this way at our end of 
the link only yields the packet loss in one direction of the link, i.e. 
for the packets sent by our neighbours to us. The packet loss in the 
opposite direction is not determined by this mechanism and may be 
completely different.

* To get an idea of the packet loss in both directions of a link, we 
additionally need our neighbours to tell to us the packet loss at their 
end of the link, i.e. the packet loss for packets sent by us to our 
neighbours. For this we use "LQ_HELLO" messages.

* As you know, in OLSR we periodically exchange HELLO message with our 
neighbours. The link quality extension replaces standard HELLO messages 
by a new type of HELLO message, which we call LQ_HELLO (LQ = link 
quality). LQ_HELLOs are HELLOs plus room for packet loss information. 
When sending out LQ_HELLOs we insert the packet loss that we have 
determined for our end of each link with a neighbour. So, each of our 
neighbours gets to know the packet loss at our end of the link.

* Our neighbours now have (a) the packet loss that they've calculated 
themselves (for packets sent by us to them) and (b) the packet loss 
received from us in the LQ_HELLOs (for the opposite direction of the 
link, i.e. for packets sent from them to us). So, they now have the 
packet loss for both ends of the link, i.e. for packet transmission in 
both directions via the link.

* As our neighbours also send LQ_HELLOs, we learn the packet loss for 
transmissions from us to them. So, we now also have the packet loss for 
both ends of the link, i.e. for packet transmission in both directions 
via the link.

 >>> Link quality

* We now transform the packet loss for one link direction into the 
probability that a packet sent via the link into this direction 
successfully gets through the link. This is our link quality. The link 
quality is a value between 0.0 (the probability is 0 percent, no packets 
get through) and 1.0 (the probability is 100 percent, all packets get 
through). So, each link has two link qualities, one for each direction.

 >>> Routing

* To create a routing table, every node needs to know the neighbours of 
each other node. A node reports its neighbours to everybody else by 
sending out TC messages, which are then spread throughout the mobile 
network. The link quality extension replaces standard TC messages by a 
new type of TC message, which we call LQ_TC. LQ_TCs are TCs plus room 
for link quality information. With LQ_TCs a node not only reports who 
its neighbours are, but also the link qualities at both ends of each 
link with a neighbour, i.e. the link quality in both directions for each 
link.

* Let's assume that we have a path from node A to node C via node B. 
Let's assume that the link quality for packets sent from A to B is LQ1 
and the link quality for packets sent from B to C is LQ2. The total link 
quality of the whole path is then LQ1 * LQ2. If, for example, 50% of the 
packets from A to B get through, and 90% of the packets from B to C get 
through, then in total 50% * 90% = 0.5 * 0.9 = 0.45 = 45% of the packets 
make it the whole way from A to C.

* When creating a routing table we chose the path between us and a 
destination node that has the best total link quality TLQ = LQ1 * LQ2 * 
... * LQn, where the LQx values are the individual qualities of the 
links between the hops between us and the destination node. In this way 
the probability that a packet actually gets through from us to a 
destination node is maximized.

 >>> MPRs

* As you know, in OLSR we select multi-point relays (MPRs) from among 
our neighbours, which aid us in distributing our messages, e.g. our 
LQ_TCs, throughout the network. MPRs receive our messages and 
re-broadcast them. So, if we do not see a node X but one of our MPRs 
does, then the MPR will receive a message from us and X will see it once 
the MPR re-broadcasts it. Hence it is desireable that the path between 
us and X has good total quality.

* From the LQ_HELLO messages we can also find out how well our 
neighbours are connected to their neighbours. So, let's again assume 
that we do not see a node X, but two of our neighbours, N1 and N2, see 
X. We now determine the total link quality of the path via N1 to X and 
of the path via N2 to X. If the former is better, we make N1 an MPR. If 
the latter is better, we select N2 as an MPR. So, we make sure that we 
use the path with the highest qualities when reaching nodes (like X) 
that are two hops away from us, i.e. not reachable directly but via one 
of our neighbours.

 >>> Using link quality in olsrd

* The configuration file now supports has a new option to set the level 
of link quality support. The option is named "LinkQualityLevel".

* "LinkQualityLevel 0" means that the link quality extension is 
completely switched off. olsrd then behaves in exactly the same way as 
before the link quality extension existed, i.e. HELLO messages and TC 
messages are used, etc.

* "LinkQualityLevel 1" means that the link quality extension is enabled. 
LQ_HELLOs are used instead of HELLOs and LQ_TCs are used instead of TCs. 
Nodes with enabled link quality extension DO NOT WORK with nodes that 
have the link quality extension disabled. The former use LQ_HELLOs and 
LQ_TCs, whereas the latter work with ordinary HELLOs and TCs. So, 
setting this configuration file option to a non-zero value BREAKS 
COMPATIBILITY with the OLSR specification. Setting this option to 1 
tells olsrd to use the link quality information only for MPR selection 
but not for routing.

* "LinkQualitylevel 2" means that olsrd does the same as for 
"LinkQualityLevel 1", but it additionally tells olsrd to take into 
account the link qualities also when creating the routing table.

* Make sure that you use the same "LinkQualityLevel" settings on all 
nodes in your network. Nodes which have this option set to 0 will not 
work at all with nodes that have this option set to 1 or 2. And nodes 
that have this option set to 1 will probably not work with nodes that 
have this option set to 2, as the former only select their MPRs based on 
the link quality (but calculate their routing table based on the 
conventional hop-count method) and the latter calculate their routing 
table based on link qualities. This will yield different routing tables 
on different nodes.

If you feel like it, I'd be happy to hear about your experiences with 
the link quality extension. Unfortunately I'll be traveling until Sunday 
and I'll probably not have e-mail access very often. When I am back I'll 
be happy to track down bugs, through.

-Thomas