Forth Estuary Experimental Data Network
Most of what can be achieved via FEEDNET is courtesy of open source software. The sheer hard work, altruism and inventiveness of all open source authors is gratefully acknowledged here.
ETX and Link Quality - What does it mean ?
These are a measure of packet loss. 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 on it, just goggle for "expected transmission count".
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. Protocol
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 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 NET 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.