1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
4 <TITLE>olsrd Link Quality Extensions</TITLE>
6 <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
8 <STYLE TYPE="text/css">
10 font-family: verdana,arial,sans-serif;
12 background-color: #ffffff;
16 :link { color: #123e80 }
17 :visited { color: #123e80 }
18 :active { color: #123e80 }
23 <H2>olsrd Link Quality Extensions</H2>
26 $Id: README-Link-Quality.html,v 1.3 2005/02/15 18:22:19 tlopatic Exp $
32 The way in which the ETX metric is applied to OLSR owes its
33 existence to ideas conceived by the wonderful folks at
34 <A HREF="http://www.c-base.org">c-base</A>
36 <A HREF="http://www.freifunk.net">freifunk.net</A>.
37 Any implementation bugs are solely Thomas's fault, though.
41 Guys, also thanks a lot for your hospitality, for your valuable
42 input, for being brave enough to test early releases of olsrd,
43 for supplying a great testbed in Berlin, and for being
52 0.4.9 - Documented the <EM>LinkQualityMult</EM>
53 configuration directive.
61 Release 0.4.8 of olsrd offers an experimental implementation of
62 an ETX-like metric. When calculating a routing table for us,
63 pure RFC-compliant OLSR simply minimizes the number of hops
64 between ourselves and the other nodes in the MANET, even if this
65 means that a route via a single very bad link will be preferred
66 to a route via two excellent links, although the latter would
67 probably have been the better choice.
71 To solve this problem, we have to teach olsrd how to tell good
72 links from bad links. We have done so by measuring the packet
73 loss for OLSR packets that we receive from our neighbors. As we
74 periodically receive HELLO messages from our neighbors (by
75 default every 2 seconds), we have enough packets to determine
76 the packet loss for packets that each of our neighbors sends to
81 If, for example, 3 out of 10 packets are lost on their way from
82 our neighbor to ourselves, we have a packet loss of 3/10 = 0.3 =
83 30%. At the same time 7 of the 10 packets that the neighbor sent
84 went through. Hence, the probability for a successful packet
85 transmission from this neighbor to ourselves is 7/10 = 0.7 =
86 70%. This probability is what we call the <EM>Link
87 Quality</EM>. So the Link Quality says how good a given link
88 between a neighbor and ourselves is in the direction from the
89 neighbor to ourselves. It does so by saying how likely it is
90 that a packet that we send is successfully received by our
95 However, it is also important to know the quality of the link in
96 the opposite direction, i.e. how many of the packets that we
97 send out are received by each of our neighbors. So, we are not
98 only interested in the Link Quality of a given link, but also in
99 the corresponding neighbor's idea of the Link Quality. That's
100 what we call the <EM>Neighbor Link Quality</EM>. The Neighbor
101 Link Quality says how good a given link between a neighbor and
102 ourselves is in the direction from ourselves to the neighbor.
106 The Link Quality and the Neighbor Link Quality are values
107 between 0 and 1 or, which is equivalent, between 0 and
108 100%. They represent the probability that a packet that our
109 neighbor sends actually makes it to us (Link Quality) and that
110 a packet that we send actually makes it to our neighbor
111 (Neighbor Link Quality).
115 Let's now look at the probability for a successful packet round
116 trip, i.e. the probability that we successfully send a packet to
117 our neighbor and, on receiving it, our neighbor successfully
118 replies with a response packet. For a successful round trip both
119 packets must get through, the packet that we've sent and the
120 response packet that our neighbor has sent. So, the success
121 probability is NLQ x LQ, where NLQ is the Neighbor Link Quality
122 of the link and LQ is its link quality. For example, if we have
123 a NLQ of 60% and a LQ of 70%, the probability of a successful
124 round trip is 60% x 70% = 0.6 x 0.7 = 0.42 = 42%.
128 In wireless networks each recipient of a packet acknowledges
129 packet reception by sending back an acknowledgment packet to
130 the sender. So, when does a retransmission of a packet happen?
131 It happens, if the sender does not receive an
132 acknowledgment. And in which cases does the sender not receive
133 an acknowledgment? If either the packet that it sent is lost or
134 if the corresponding acknowledgment packet is lost. So, what is
135 the probability for a retransmission to <EM>not</EM> take place?
136 Well, as the sender's packet has to get through in one direction
137 and the recipient's acknowledgment has to get through in the
138 opposite direction, too, this is exactly the probability for a
139 successful packet round trip, i.e. NLQ x LQ.
143 We can now answer the question of how many transmission attempts
144 it will typically take to get a packet from us to a neighbor or
145 from the neighbor to us. It is 1 / (NLQ x LQ). So, in the above
146 case of NLQ x LQ = 42%, we expect on average 1 / 0.42 = 2.38
147 transmission attempts for a packet until it gets through.
151 Note that this number is valid for both directions of the link,
152 as in both cases we have to look at the probability for a
153 successful packet round trip. For packets that we send to our
154 neighbor, the packet goes from us to the neighbor and the
155 acknowledgment travels the other way around. For packets that
156 our neighbor sends to us, the packet goes from the neighbor to
157 us and the acknowledgment travels from us to the neighbor. In
158 both cases a packet is sent in each direction and retransmission
159 occurs if either packet is lost.
163 The value 1 / (NLQ x LQ) is called the <EM>Expected Transmission
164 Count</EM> or <EM>ETX</EM>. For those interested in a more
165 in-depth discussion, there's a scientific paper on it, just
166 goggle for "expected transmission count".
170 Let's assume that we have a route from ourselves via two nodes A
171 and B to a node C. What is the ETX for the total route, i.e. how
172 often is our packet retransmitted on its way from us to C? Well,
173 we know how many attempts we need on average to successfully
174 transmit a packet from us to A. Let's call this value ETX1. So,
175 we already have ETX1 attempts just to reach A. The packet would
176 then take an additional number of attempts to hop from A to
177 B. Let's call this second value ETX2. Finally, a further number
178 of attempts is required to hop from B to C. Let's call this
179 third value ETX3. Let's now have a look at the total number of
180 transmissions that have happened to get our packet from us to
181 C. This number is simply ETX1 + ETX2 + ETX3.
187 In order to calculate the ETX for a link to a neighbor, we need
188 to know the neighbor's idea of the link quality, i.e. the NLQ,
189 as we can only determine the LQ ourselves, but we want to know
190 ETX = 1 / (NLQ * LQ). So the link quality extensions to olsrd
191 introduce a new kind of HELLO messages, which we call <EM>LQ
192 HELLO</EM> messages. For each link listed in such a message, the
193 originator of the messages also tells us the link quality. So,
194 each neighbor puts the LQ values that it has determined in the
195 message, which from our perspective are NLQ values. So, owing to
196 the LQ HELLOs we now have all the information to calculate the
197 ETX for each link between ourselves and one of our neighbors.
201 Let's again have a look at the total number of transmissions
202 required for a route that consists of more than one hop,
203 i.e. that is not a route to one of our neighbors. If we stick
204 with the above example, we know ETX1 from the LQ HELLOs. But how
205 do we learn ETX2 and ETX3? For this the link quality extensions
206 to olsrd introduce a new kind of TC messages. TC messages are
207 used in OLSR to tell the world, i.e. all other nodes in the
208 MANET, which neighbors we have. We have extended TC messages to
209 additionally carry information on how good the links to our
210 neighbors are. We call this extended variant of TCs,
211 analogously to LQ HELLOS, <EM>LQ TC</EM> messages.
215 So, with LQ HELLO messages we find out which neighbors we have
216 and how good our links to them are and with LQ TC messages, we
217 share this knowledge with all other nodes and all other nodes
218 share their knowledge with us.
222 In this way each node in the network ends up knowing which links
223 each other node in the MANET has and how good they are. Well,
224 actually, it's a bit more complex than that, because of an
225 optimization called multi-point relaying. But this is beyond the
226 scope of this introductory text.
232 LQ HELLO messages and LQ TC messages are not compatible with
233 RFC-compliant HELLO and TC messages. So make sure that you
234 either switch <EM>all</EM> nodes of your network to link quality
235 or <EM>none</EM> of your nodes. A mixed configuration will
236 probably result in an unpredictable mess.
241 <H4>New Configuration Parameters</H4>
243 <H5>LinkQualityLevel</H5>
246 Let's now have a look at how we would use the link quality
247 extensions. The configuration parameter that controls link
248 quality is <EM>LinkQualityLevel</EM>, as it sets the level to
249 which link quality is used, i.e. for which purposes olsrd looks
250 at the link quality information.
255 Setting this parameter to 0 disables the link quality
256 extensions. olsrd then works in exactly the same way as
257 before, i.e. it is RFC-compliant, uses HELLO and TC
258 messages, and calculates routes by minimizing the hop count.
263 Setting this parameter to 1 enable the link quality
264 extensions and tells olsrd to select MPRs based on the link
265 quality information. A neighbor is selected as an MPR, if
266 it has the best route to any 2-hop neighbor. Suppose that
267 ETX1 is the expected number of transmissions between us and
268 a neighbor N and that ETX2 is the expected number of
269 transmissions between N and a two-hop neighbor N2. For each
270 of our two-hop neighbors we then select the neighbor N as
271 an MPR that results in the lowest possible total ETX of ETX1
277 Setting this parameter to 2 not only selects MPRs based on
278 the link quality but also considers link quality information
279 when calculating the routing table. For a given destination
280 node D we select the route that has the minimal total ETX of
281 ETX1 + ETX2 + ... + ETXn, where ETX1 is the expected number
282 of transmissions from us to our neighbor, ETX2 is the
283 expected number of transmissions from our neighbor to the
284 next node, and ETXn is the expected number of transmissions
285 from our destination's neighbor to the destination. This is
286 the recommended setting.
292 <B>IMPORTANT:</B> Remember to set <EM>all</EM> nodes of your
293 MANET to the same link quality level. Even if levels 2 and 3 use
294 the same kind of messages, i.e. LQ HELLOs and LQ TCs, they use a
295 different algorithm for calculating the routing table. This can
296 also mess up your routing!
299 <H5>LinkQualityWinSize</H5>
302 The second configuration parameter related to link quality is
303 <EM>LinkQualityWinSize</EM>. When determining the packet loss of
304 the packets received from a neighbor, olsrd only looks at the
305 <EM>n</EM> most recent packets. By default <EM>n</EM> is set to
306 10, so olsrd looks at the ten most recent packets received (or
307 not received) from a neighbor and then determines the packet
308 loss. Let's assume that of the 10 packets we have received 7,
309 then we have missed 3, which corresponds to a packet loss of
310 3/10 = 0.3 = 30%. The corresponding Link Quality is 7/10 = 0.7 =
315 Let's have a look at what the default value means. Let's for the
316 moment only think of LQ HELLO messages and neglect other message
317 types. By default LQ HELLOs are sent every 2 seconds. So, we
318 calculate the packet loss over the past 20 seconds. So, changes
319 in the link quality are accounted for relatively fast. For
320 longer intervals just increase this value.
323 <H5>LinkQualityMult</H5>
326 Version 0.4.9 supports a third configuration parameter,
327 <EM>LinkQualityMult</EM>. This is a per-interface parameter, so
328 it may only appear in an interface configuration block. This
329 parameter can be used to alter the LQ values that we announce,
330 which will then result in an altered ETX for links between us
331 and our neighbors - remember that ETX = 1 / (NLQ x LQ).
335 The idea is to enable us to make certain links that we have
336 artificially appear better or worse than they actually are. In
337 this way we can manually affect the routing decisions made by
342 The <EM>LinkQualityMult</EM> parameter is followed by an IP
343 address and a number, the multiplier. The IP address specifies
344 the IP address of the neighbor interface address of the link
345 that we want to manipulate. The LQ values that we determine for
346 this link are then multiplied by the given multiplier.
350 If the word <EM>default</EM> is specified in lieu of an IP
351 address, then this multiplier applies to all links via the
352 interface that we're configuring. Note, however, that a
353 multiplier linked to a real IP address has priority over the
354 default multiplier. So, we're looking for the most specific
358 <H4>Old Configuration Parameters</H4>
361 The link quality extensions do not work very well with
362 hysteresis. Hysteresis basically acts as a sort of barrier that
363 only links that are "good enough" can cross. If a link is too
364 flaky, hysteresis will make olsrd consider the link as
365 non-existent. So, this is a binary thing. Either a link is able
366 to cross the barrier, or it is not. There's nothing in
367 between. However, we want olsrd to consider <EM>every</EM> link
368 there is, without any barrier, because then we can leave it to
369 the link quality extensions to judge how good the link actually
370 is and how much we trust the link.
374 If a link with an ETX value of 50 is the only way of
375 reaching a node, then we want to use this link, as there is no
380 In addition, in contrast to only saying "good enough" or "not
381 good enough" like hysteresis, the link quality extensions offer
382 a much more detailed view of the world by saying something like
383 "75% good enough, 25% not good enough".
387 The second mechanism that could interfere with the link quality
388 extensions is the link detection scheme. By default, if olsrd
389 misses three (LQ) HELLO messages in a row from a neighbor, the
390 link is considered broken. However, we'd prefer the link to just
391 expose a lower quality. So, setting the HELLO validity time to
392 the HELLO interval multiplied by the link quality window size is
393 probably a good rule of thumb. In this way the link will be
394 removed not before the link quality extensions have had enough
395 time to gradually reduce the link quality to zero.
398 <H4>Sample Configuration</H4>
401 A minimal configuration that leaves everything at the default
402 and just makes the changes required for the link quality
403 extension to work properly could look as follows. Note the
404 <EM>ClearScreen</EM> directive that causes the screen to be
405 cleared before updated debug information is printed. This makes
406 the debug output more readable in many cases.
413 LinkQualityWinSize 10
419 HelloValidityTime 20.0
424 Let's assume that we would like to use the
425 <EM>LinkQualityMult</EM> directive to multiply the LQ value that
426 we report for the link between our local interface <EM>if03</EM>
427 and an interface of one of our neighbors that has an IP address
428 of 192.168.0.1. Say, we'd like to multiply the LQ value by
429 0.5. We would then simply add the following line to the
430 <EM>Interface</EM> section of the above configuration file.
434 LinkQualityMult 192.168.0.1 0.5
438 Suppose that we would further like to multiply the LQ values
439 that we report for all other links between our local interface
440 <EM>if03</EM> and a neighbor interface by 0.8. We would then
441 add a second, default <EM>LinkQualityMult</EM> statement and we
442 would end up with the following two lines.
446 LinkQualityMult 192.168.0.1 0.5
447 LinkQualityMult default 0.8
451 For the link to 192.168.0.1 the first line would have precedence
452 over the second (default) line and 0.5 would be used as the
453 multiplier. For all other links the default multiplier of 0.8
454 would be used, as there isn't any better match.
457 <H3>Debug Output</H3>
460 0.4.8 also introduces significant changes in the debug
461 output. Let's have a look at what happens at debug level 2, which
462 is the recommended default for the link quality extensions.
466 --- 14:28:56.80 ---------------------------------------------------- LINKS
468 IP address hyst LQ lost total NLQ ETX
469 192.168.0.1 0.000 1.000 0 10 1.000 1.00
473 This table contains the links to our neighbors. It contains the
480 <EM>IP address</EM> - the IP address of the interface via
481 which we have contact to the neighbor.
486 <EM>hyst</EM> - the current hysteresis value for this link.
491 <EM>LQ</EM> - the quality of the link determined at our
492 end. This is what we have previously called the Link
498 <EM>lost</EM> - the number of lost packets among the
499 <EM>n</EM> packets most recently sent by our neighbor via
500 this link. <EM>n</EM> is the link quality window size.
505 <EM>total</EM> - the total number of packets received up to
506 now. This value starts at 0 immediately after a link has
507 come to life and then counts each packet. It is capped at
508 the link quality window size.
513 <EM>NLQ</EM> - this is our neighbor's view of the link
514 quality. Previously we have called this the Neighbor Link
515 Quality. This value is extracted from LQ HELLO messages
516 received from our neighbors. NB: If a neighbor stops
517 sending packets completely, we do not have any means of
518 updating this value. However, in this case the LQ value will
519 decrease and the link thus be detected as becoming worse.
524 <EM>ETX</EM> - this is the ETX for this link, i.e. 1 / (NLQ
531 --- 14:28:56.80 ------------------------------------------------ NEIGHBORS
533 IP address LQ NLQ SYM MPR MPRS will
534 10.0.0.6 1.000 1.000 YES YES NO 6
538 This table contains a list of all our neighbors. It is closely
539 related to the link table in that we are connected to a
540 neighbor via one or more links. The table has the following
547 <EM>IP address</EM> - the main IP address of the neighbor.
552 <EM>LQ</EM> and <EM>NLQ</EM> - the LQ and NLQ values of the
553 best link that we have with this neighbor. (In
554 multi-interface configurations we can have more than one
555 link with a neighbor.)
560 <EM>SYM</EM> - this states whether the link to this
561 neighbor is considered symmetric by olsrd's link detection
567 <EM>MPR</EM> (multi-point relay) - this indicates whether we
568 have selected this neighbor to act as an MPR for us.
573 <EM>MPRS</EM> (multi-point relay selector) - this indicates
574 whether the neighbor node has selected us to act as an MPR
580 <EM>will</EM> - the neighbor's willingness.
586 --- 14:28:56.80 ------------------------------------------------- TOPOLOGY
588 Source IP addr Dest IP addr LQ ILQ ETX
589 10.0.0.6 192.168.0.2 1.000 1.000 1.00
590 10.0.0.6 10.0.0.5 1.000 1.000 1.00
594 This table displays the topology information that olsrd has
595 gathered from LQ TC messages. It states which nodes in the
596 network report links to which other nodes and which quality
597 these links have. So, it's olsrd's view of the world beyond its
598 immediate neighbor nodes, i.e. its view of the nodes that it
599 cannot reach directly. This table has the following columns.
605 <EM>Source IP addr</EM> - the node that reports a link.
610 <EM>Dest IP addr</EM> - the node to which the source node
616 <EM>LQ</EM> (link quality) - the quality of the link as
617 determined by the source node. For the source node this is
618 the Link Quality. For the destination node this is the
619 Neighbor Link Quality.
624 <EM>ILQ</EM> (inverse link quality) - the quality of the
625 link as determined by the destination node. For the source
626 node this is the Neighbor Link Quality. For the destination
627 node this is the Link Quality. We just did not want to name
628 it "NLQ", as we use NLQ only for the link quality reported
629 by our neighbors. But functionally this is equivalent to
630 the NLQ we know from the link and neighbor tables.
635 <EM>ETX</EM> - the ETX value for this link, calculated by
636 ETX = 1 / (ILQ x LQ).
642 --- 14:28:56.80 ------------------------------------------------- DIJKSTRA
644 10.0.0.6:1.00 (one-hop)
645 10.0.0.5:2.00 <- 10.0.0.6:1.00 (one-hop)
649 This table displays the best routes that olsrd could find for
650 each destination that it knows about. The leftmost IP address
651 given on each line is the destination of a route. The remaining
652 IP addresses in a line specify the nodes on the route between
653 ourselves and the destination address. Moving from the
654 destination address to the right, address by address, moves us
655 closer from the destination to ourselves, hop by hop.
659 In the above case we see routes to two nodes, 10.0.0.6 and
660 10.0.0.5. In the first line, there aren't any intermediate nodes
661 between us and the destination, the destination address is the
662 only IP address in this line. In the second line we have one
663 intermediate node, 10.0.0.6. So, the second line describes a
664 route to 10.0.0.5 via 10.0.0.6.
668 The number after the colon following an IP address in the table
669 is the total ETX of the route up to this IP address, i.e. the
670 sum of the ETX values of all hops between ourselves and this IP
675 In the above example the first line represents a path with an
676 ETX value of 1.00 to 10.0.0.6. As we've seen in the neighbor
677 table above 10.0.0.6 is our neighbor, so the route to it
678 consists only of a single hop, which has an ETX of 1.00, hence
679 the 1.00 in this line.
683 In the second line, 10.0.0.5 is not a neighbor of ours. However,
684 10.0.0.6 is and from the topology table above we can tell that
685 10.0.0.6 reports a link to 10.0.0.5. So, we can reach 10.0.0.5
686 via 10.0.0.6. This is what this line says. Remember that each
687 line represents a route by first giving the IP address of the
688 destination (10.0.0.5) and that moving to the right means moving
689 towards ourselves until one of our (one-hop) neighbor is
690 reached. If we move from 10.0.0.5 to the right, we find
691 10.0.0.6, which is our (one-hop) neighbor. So we have a route.
695 If we would like to know which path a packet takes that we send
696 to 10.0.0.5, we have to read the line backwards. We then see
697 that the packet first travels to our (one-hop) neighbor 10.0.0.6
698 via a link that has an ETX of 1.00 (which we can confirm by
699 looking at the neighbor table above). From there it is forwarded
700 to 10.0.0.5 via another link that also has an ETX of 1.00 (which
701 we can confirm by means of the topology table above), resulting
702 in a total ETX of 1.00 + 1.00 = 2.00, which is the number that
703 follows 10.0.0.5. Remember that the ETX value given for an IP
704 address is the cumulative ETX for the complete route up to this
709 If olsrd is able to find a route between us and the destination,
710 the last IP address in the line is one of our neighbors. In this
711 case, "(one-hop)" is appended to the line to illustrate that the
712 last IP address is one of our (one-hop) neighbors. However,
713 let's assume that we've just switched on olsrd. In this case, it
714 does not know about all links in the network, yet, as it hasn't
715 received LQ TC messages from all nodes. So, it may know that a
716 node exists (as it has already received LQ TC messages from it)
717 but it does not necessarily know how to reach it (as it may not
718 have received LQ TC messages from nodes between it and
719 ourselves, yet). In this case the last IP address is the last
720 node that is reachable from the destination and the line ends
721 with the word "FAILED".
725 The same is true for neighbors to which we do not have a
726 symmetric link. We know that they're there, but we do not have a
727 link to them, hence olsrd cannot find a route, which results in
734 If you have any questions on using olsrd or if you would like to
735 know more about the link quality extension, it's probably best
736 to subscribe to the mailing lists and ask your question
737 there. Information on the mailing lists is available at
738 <A HREF="http://www.olsr.org">http://www.olsr.org</A>.
Repositories / olsrd.git / blob