The way in which the ETX metric is applied to OLSR owes its existence to ideas conceived by the wonderful folks at c-base and freifunk.net. Any implementation bugs are solely Thomas's fault, though.
Guys, also thanks a lot for your hospitality, for your valuable input, for being brave enough to test early releases of olsrd, for supplying a great testbed in Berlin, and for being you!
0.4.9 - Documented the LinkQualityMult configuration directive.
Release 0.4.8 of olsrd offers an experimental implementation of an ETX-like metric. When calculating a routing table for us, pure RFC-compliant OLSR simply minimizes the number of hops between ourselves and the other nodes in the MANET, even if this means that a route via a single very bad link will be preferred to a route via two excellent links, although the latter would probably have been the better choice.
To solve this problem, we have to teach olsrd how to tell good links from bad links. We have done so by measuring the packet loss for OLSR packets that we receive from our neighbors. As we periodically receive HELLO messages from our neighbors (by default every 2 seconds), we have enough packets to determine the packet loss for packets that each of our neighbors sends to us.
If, for example, 3 out of 10 packets are lost on their way from our neighbor to ourselves, we have a packet loss of 3/10 = 0.3 = 30%. At the same time 7 of the 10 packets that the neighbor sent went through. Hence, the probability for a successful packet transmission from this neighbor to ourselves is 7/10 = 0.7 = 70%. This probability is what we call the Link Quality. So the Link Quality says how good a given link between a neighbor and ourselves is in the direction from the neighbor to ourselves. It does so by saying how likely it is that a packet that we send is successfully received by our neighbor.
However, it is also important to know the quality of the link in the opposite direction, i.e. how many of the packets that we send out are received by each of our neighbors. So, we are not only interested in the Link Quality of a given link, but also in the corresponding neighbor's idea of the Link Quality. That's what we call the Neighbor Link Quality. The Neighbor Link Quality says how good a given link between a neighbor and ourselves is in the direction from ourselves to the neighbor.
The Link Quality and the Neighbor Link Quality are values between 0 and 1 or, which is equivalent, between 0 and 100%. They represent the probability that a packet that our neighbor sends actually makes it to us (Link Quality) and that a packet that we send actually makes it to our neighbor (Neighbor Link Quality).
Let's now look at the probability for a successful packet round trip, i.e. the probability that we successfully send a packet to our neighbor and, on receiving it, our neighbor successfully replies with a response packet. For a successful round trip both packets must get through, the packet that we've sent and the response packet that our neighbor has sent. So, the success probability is NLQ x LQ, where NLQ is the Neighbor Link Quality of the link and LQ is its link quality. For example, if we have a NLQ of 60% and a LQ of 70%, the probability of a successful round trip is 60% x 70% = 0.6 x 0.7 = 0.42 = 42%.
In wireless networks each recipient of a packet acknowledges packet reception by sending back an acknowledgment packet to the sender. So, when does a retransmission of a packet happen? It happens, if the sender does not receive an acknowledgment. And in which cases does the sender not receive an acknowledgment? If either the packet that it sent is lost or if the corresponding acknowledgment packet is lost. So, what is the probability for a retransmission to not take place? Well, as the sender's packet has to get through in one direction and the recipient's acknowledgment has to get through in the opposite direction, too, this is exactly the probability for a successful packet round trip, i.e. NLQ x LQ.
We can now answer the question of how many transmission attempts it will typically take to get a packet from us to a neighbor or from the neighbor to us. It is 1 / (NLQ x LQ). So, in the above case of NLQ x LQ = 42%, we expect on average 1 / 0.42 = 2.38 transmission attempts for a packet until it gets through.
Note that this number is valid for both directions of the link, as in both cases we have to look at the probability for a successful packet round trip. For packets that we send to our neighbor, the packet goes from us to the neighbor and the acknowledgment travels the other way around. For packets that our neighbor sends to us, the packet goes from the neighbor to us and the acknowledgment travels from us to the neighbor. In both cases a packet is sent in each direction and retransmission occurs if either packet is lost.
The value 1 / (NLQ x LQ) is called the Expected Transmission Count or ETX. For those interested in a more in-depth discussion, there's a scientific paper by the people who invented all this, and for those who would like to know still more, there's Doug's PhD thesis.
Let's assume that we have a route from ourselves via two nodes A and B to a node C. What is the ETX for the total route, i.e. how often is our packet retransmitted on its way from us to C? Well, we know how many attempts we need on average to successfully transmit a packet from us to A. Let's call this value ETX1. So, we already have ETX1 attempts just to reach A. The packet would then take an additional number of attempts to hop from A to B. Let's call this second value ETX2. Finally, a further number of attempts is required to hop from B to C. Let's call this third value ETX3. Let's now have a look at the total number of transmissions that have happened to get our packet from us to C. This number is simply ETX1 + ETX2 + ETX3.
In order to calculate the ETX for a link to a neighbor, we need to know the neighbor's idea of the link quality, i.e. the NLQ, as we can only determine the LQ ourselves, but we want to know ETX = 1 / (NLQ * LQ). So the link quality extensions to olsrd introduce a new kind of HELLO messages, which we call LQ HELLO messages. For each link listed in such a message, the originator of the messages also tells us the link quality. So, each neighbor puts the LQ values that it has determined in the message, which from our perspective are NLQ values. So, owing to the LQ HELLOs we now have all the information to calculate the ETX for each link between ourselves and one of our neighbors.
Let's again have a look at the total number of transmissions required for a route that consists of more than one hop, i.e. that is not a route to one of our neighbors. If we stick with the above example, we know ETX1 from the LQ HELLOs. But how do we learn ETX2 and ETX3? For this the link quality extensions to olsrd introduce a new kind of TC messages. TC messages are used in OLSR to tell the world, i.e. all other nodes in the MANET, which neighbors we have. We have extended TC messages to additionally carry information on how good the links to our neighbors are. We call this extended variant of TCs, analogously to LQ HELLOS, LQ TC messages.
So, with LQ HELLO messages we find out which neighbors we have and how good our links to them are and with LQ TC messages, we share this knowledge with all other nodes and all other nodes share their knowledge with us.
In this way each node in the network ends up knowing which links each other node in the MANET has and how good they are. Well, actually, it's a bit more complex than that, because of an optimization called multi-point relaying. But this is beyond the scope of this introductory text.
LQ HELLO messages and LQ TC messages are not compatible with RFC-compliant HELLO and TC messages. So make sure that you either switch all nodes of your network to link quality or none of your nodes. A mixed configuration will probably result in an unpredictable mess.
Let's now have a look at how we would use the link quality extensions. The configuration parameter that controls link quality is LinkQualityLevel, as it sets the level to which link quality is used, i.e. for which purposes olsrd looks at the link quality information.
Setting this parameter to 0 disables the link quality extensions. olsrd then works in exactly the same way as before, i.e. it is RFC-compliant, uses HELLO and TC messages, and calculates routes by minimizing the hop count.
Setting this parameter to 1 enable the link quality extensions and tells olsrd to select MPRs based on the link quality information. A neighbor is selected as an MPR, if it has the best route to any 2-hop neighbor. Suppose that ETX1 is the expected number of transmissions between us and a neighbor N and that ETX2 is the expected number of transmissions between N and a two-hop neighbor N2. For each of our two-hop neighbors we then select the neighbor N as an MPR that results in the lowest possible total ETX of ETX1 + ETX2.
Setting this parameter to 2 not only selects MPRs based on the link quality but also considers link quality information when calculating the routing table. For a given destination node D we select the route that has the minimal total ETX of ETX1 + ETX2 + ... + ETXn, where ETX1 is the expected number of transmissions from us to our neighbor, ETX2 is the expected number of transmissions from our neighbor to the next node, and ETXn is the expected number of transmissions from our destination's neighbor to the destination. This is the recommended setting.
IMPORTANT: Remember to set all nodes of your MANET to the same link quality level. Even if levels 2 and 3 use the same kind of messages, i.e. LQ HELLOs and LQ TCs, they use a different algorithm for calculating the routing table. This can also mess up your routing!
The second configuration parameter related to link quality is LinkQualityWinSize. When determining the packet loss of the packets received from a neighbor, olsrd only looks at the n most recent packets. By default n is set to 10, so olsrd looks at the ten most recent packets received (or not received) from a neighbor and then determines the packet loss. Let's assume that of the 10 packets we have received 7, then we have missed 3, which corresponds to a packet loss of 3/10 = 0.3 = 30%. The corresponding Link Quality is 7/10 = 0.7 = 70%.
Let's have a look at what the default value means. Let's for the moment only think of LQ HELLO messages and neglect other message types. By default LQ HELLOs are sent every 2 seconds. So, we calculate the packet loss over the past 20 seconds. So, changes in the link quality are accounted for relatively fast. For longer intervals just increase this value.
Version 0.4.9 supports a third configuration parameter, LinkQualityMult. This is a per-interface parameter, so it may only appear in an interface configuration block. This parameter can be used to alter the LQ values that we announce, which will then result in an altered ETX for links between us and our neighbors - remember that ETX = 1 / (NLQ x LQ).
The idea is to enable us to make certain links that we have artificially appear better or worse than they actually are. In this way we can manually affect the routing decisions made by the OLSR network.
The LinkQualityMult parameter is followed by an IP address and a number, the multiplier. The IP address specifies the IP address of the neighbor interface address of the link that we want to manipulate. The LQ values that we determine for this link are then multiplied by the given multiplier.
If the word default