[OLSR-users] Metrics

[Thomas Lopatic]

Hi Stefan,

Thanks for sharing your thoughts. Bruno and I had a discussion on this 
very topic two weeks ago. We thought, hey, let's quickly refactor olsrd 
a bit, create a central function that maps a variety of input parameters 
(e.g. packet loss, bandwidth, willingness, etc.) to a single output 
parameter (the metric), and broadcast the metric in lieu of the 
individual input parameters over the network. This would give each node 
the freedom to calculate the metric using its own personal algorithm. 
However, a few questions arose and we're at the moment not sure how to 
handle them, so we postponed the idea of having a central function that 
calculates the metric.

1. Let's assume that we look at a path from node A to node B via 
intermediate nodes and that we want to know the total metric of the path 
in order to minimize it to find the best path. Then there are three 
different kinds of metrics:

- additive metrics (e.g. round-trip time - the total round trip time is 
the sum of the round trip times for the individual hops),

- multiplicative metrics (e.g. the probability that a packet makes it 
from A to B - the total probability is the product of the probabilities 
for the individual hops), and

- minimum metrics (e.g. bandwidth - the bandwidth for transmissions from 
A to B is the minmum of the bandwidths of the intermediate hops).

I do not know whether it is a good idea to throw all these different 
metrics together into a single value. Currently we use ETX, which is 
additive (the total number of required retransmissions is the sum of the 
numbers of required retransmissions at each hop). So, our Dijkstra 
implementation minimizes additive edge weights. The question now is 
whether there is a way of converting multiplicative metrics and minimum 
metrics into additive metrics in a meaningful way.

Or am I missing something here?

2. For ETX we need the packet loss in both directions of a link. Our 
neighbour node has to supply us with the packet loss that it determines 
and we have to supply the packet loss that we determine to our neighbour 
node. Only then can we both calculate the ETX value, which is 1 / (our 
packet loss x our neighbour's packet loss). So, in this case we could 
not simply use the "we calculate a metric and broadcast it instead of 
the link quality" paradigm, as we need our neighbour's link quality 
information to calculate the metric.

3. With ETX, links are always symmetric, i.e. there is a single metric 
that is valid for both directions. But what if node A announces "my link 
to B has metric X" and B at the same time announces "my link to A has 
metric Y", with Y being different from X? Does it make sense to have 
asymmetric links, i.e. links with two metrics, one metric for each 
direction? After all, transmitted packets are acknowledged in 802.11, so 
  looking at both directions seems like a natural choice.

Let me quickly outline the way in which the link quality information is 
used in olsrd, as a basis for further discussion.

* HELLO packets not only contain a list of neighbours that the sender of 
the HELLO sees, but also two bytes that represent the packet loss of the 
link between the sender and the neighour, one byte for packets sent from 
the sender to the neighour and one byte for the inverse direction.

* We use this information to learn the packet loss determined by our 
neighbour (i.e. for packets sent from us to it). We then combine this 
information with the packet loss that we've determined ourselves for the 
opposite direction and calculate the ETX value.

* We also use this information for MPR selection. For each two-hop 
neighbour N2 we find the neighbour N via which we get the best link to 
N2. For this we calculate the ETX value between us and a candidate N, 
calculate the ETX value between the candidate N and N2, and add them. 
The best candidate N is then selected as one of our MPRs and we continue 
this process for all other two-hop neighbours N2. All the information 
the we need for this can be gained from HELLO messages, as they contain 
link quality information for all neighbours that our neighbour sees - 
which are our two-hop neighbours.

* As HELLO messages only tell us what our two-hop neighbourhood looks 
like, we have also changed the TC messages. They now do not only contain 
a list of neighbours that the originator of a TC message sees, but also 
two bytes that characterise the packet loss of the advertised link in 
both directions. It looks like it would be possible to easily migrate TC 
messages from this "announce the link quality information" scheme to an 
"announce a metric for this link" scheme.

Now that we have a parser based on flex/bison, it should be pretty 
simple to come up with a "Metric" configuration directive like the 
following.

Metric 1 / (LinkQuality * InverseLinkQuality) + (1 - Willingness / 7)

So, "LinkQuality", "InverseLinkQuality", and "Willingness" would be 
predefined variables, which the "Metric" directive would combine into a 
single value to be used as the metric.

So, I think all this basically boils down to:

* Yes, it would be nice to be able to manipulate the link quality for a 
given link between us and a neighbour.

* Can we do it? Do asymmetric metrics make any sense?

* How can we do it? We currently need the "raw" link quality values at 
least in the HELLO messages.

I think that the biggest problem is that you need a pretty big testbed 
to test any modification to the employed metric. However, each 
modification has the potential of completely breaking an existing mesh, 
if the new metric turns out to be unsuitable.

However, an initial hack to address this issue could be to introduce a 
kind of "Multiplier" per-interface configuration parameter with which 
the the detected packet loss is multiplied. This would enable us to make 
a link via a given interface to a given neighbour better or worse as 
"normal".

I think that this metric business is pretty touchy. And I think that we 
should definitely discuss the various options that we have, but we 
should also be very careful before we introduce any custom changes to 
something relatively proven as ETX. However, if we've come up with 
something that looks okay, I'll be more than happy to contribute to 
implementing it in olsrd.

Let me know what you think.

-Thomas