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>
31 The way in which the ETX metric is applied to OLSR owes its
32 existence to ideas conceived by the wonderful folks at
33 <A HREF="http://www.c-base.org">c-base</A>
35 <A HREF="http://www.freifunk.net">freifunk.net</A>.
36 Any implementation bugs are solely Thomas's fault, though.
40 Guys, also thanks a lot for your hospitality, for your valuable
41 input, for being brave enough to test early releases of olsrd,
42 for supplying a great testbed in Berlin, and for being
51 0.4.9 - Documented the <EM>LinkQualityMult</EM>
52 configuration directive.
60 Release 0.4.8 of olsrd offers an experimental implementation of
61 an ETX-like metric. When calculating a routing table for us,
62 pure RFC-compliant OLSR simply minimizes the number of hops
63 between ourselves and the other nodes in the MANET, even if this
64 means that a route via a single very bad link will be preferred
65 to a route via two excellent links, although the latter would
66 probably have been the better choice.
70 To solve this problem, we have to teach olsrd how to tell good
71 links from bad links. We have done so by measuring the packet
72 loss for OLSR packets that we receive from our neighbors. As we
73 periodically receive HELLO messages from our neighbors (by
74 default every 2 seconds), we have enough packets to determine
75 the packet loss for packets that each of our neighbors sends to
80 If, for example, 3 out of 10 packets are lost on their way from
81 our neighbor to ourselves, we have a packet loss of 3/10 = 0.3 =
82 30%. At the same time 7 of the 10 packets that the neighbor sent
83 went through. Hence, the probability for a successful packet
84 transmission from this neighbor to ourselves is 7/10 = 0.7 =
85 70%. This probability is what we call the <EM>Link
86 Quality</EM>. So the Link Quality says how good a given link
87 between a neighbor and ourselves is in the direction from the
88 neighbor to ourselves. It does so by saying how likely it is
89 that a packet that we send is successfully received by our
94 However, it is also important to know the quality of the link in
95 the opposite direction, i.e. how many of the packets that we
96 send out are received by each of our neighbors. So, we are not
97 only interested in the Link Quality of a given link, but also in
98 the corresponding neighbor's idea of the Link Quality. That's
99 what we call the <EM>Neighbor Link Quality</EM>. The Neighbor
100 Link Quality says how good a given link between a neighbor and
101 ourselves is in the direction from ourselves to the neighbor.
105 The Link Quality and the Neighbor Link Quality are values
106 between 0 and 1 or, which is equivalent, between 0 and
107 100%. They represent the probability that a packet that our
108 neighbor sends actually makes it to us (Link Quality) and that
109 a packet that we send actually makes it to our neighbor
110 (Neighbor Link Quality).
114 Let's now look at the probability for a successful packet round
115 trip, i.e. the probability that we successfully send a packet to
116 our neighbor and, on receiving it, our neighbor successfully
117 replies with a response packet. For a successful round trip both
118 packets must get through, the packet that we've sent and the
119 response packet that our neighbor has sent. So, the success
120 probability is NLQ x LQ, where NLQ is the Neighbor Link Quality
121 of the link and LQ is its link quality. For example, if we have
122 a NLQ of 60% and a LQ of 70%, the probability of a successful
123 round trip is 60% x 70% = 0.6 x 0.7 = 0.42 = 42%.
127 In wireless networks each recipient of a packet acknowledges
128 packet reception by sending back an acknowledgment packet to
129 the sender. So, when does a retransmission of a packet happen?
130 It happens, if the sender does not receive an
131 acknowledgment. And in which cases does the sender not receive
132 an acknowledgment? If either the packet that it sent is lost or
133 if the corresponding acknowledgment packet is lost. So, what is
134 the probability for a retransmission to <EM>not</EM> take place?
135 Well, as the sender's packet has to get through in one direction
136 and the recipient's acknowledgment has to get through in the
137 opposite direction, too, this is exactly the probability for a
138 successful packet round trip, i.e. NLQ x LQ.
142 We can now answer the question of how many transmission attempts
143 it will typically take to get a packet from us to a neighbor or
144 from the neighbor to us. It is 1 / (NLQ x LQ). So, in the above
145 case of NLQ x LQ = 42%, we expect on average 1 / 0.42 = 2.38
146 transmission attempts for a packet until it gets through.
150 Note that this number is valid for both directions of the link,
151 as in both cases we have to look at the probability for a
152 successful packet round trip. For packets that we send to our
153 neighbor, the packet goes from us to the neighbor and the
154 acknowledgment travels the other way around. For packets that
155 our neighbor sends to us, the packet goes from the neighbor to
156 us and the acknowledgment travels from us to the neighbor. In
157 both cases a packet is sent in each direction and retransmission
158 occurs if either packet is lost.
162 The value 1 / (NLQ x LQ) is called the <EM>Expected Transmission
163 Count</EM> or <EM>ETX</EM>. For those interested in a more
164 in-depth discussion, there's a
165 <a href="http://pdos.csail.mit.edu/papers/grid:mobicom03/">
166 scientific paper</a> by the people who invented all this, and
167 for those who would like to know still more, there's
168 <a href="http://pdos.csail.mit.edu/papers/grid:decouto-phd/thesis.pdf">
169 Doug's PhD</a> thesis.
173 Let's assume that we have a route from ourselves via two nodes A
174 and B to a node C. What is the ETX for the total route, i.e. how
175 often is our packet retransmitted on its way from us to C? Well,
176 we know how many attempts we need on average to successfully
177 transmit a packet from us to A. Let's call this value ETX1. So,
178 we already have ETX1 attempts just to reach A. The packet would
179 then take an additional number of attempts to hop from A to
180 B. Let's call this second value ETX2. Finally, a further number
181 of attempts is required to hop from B to C. Let's call this
182 third value ETX3. Let's now have a look at the total number of
183 transmissions that have happened to get our packet from us to
184 C. This number is simply ETX1 + ETX2 + ETX3.
190 In order to calculate the ETX for a link to a neighbor, we need
191 to know the neighbor's idea of the link quality, i.e. the NLQ,
192 as we can only determine the LQ ourselves, but we want to know
193 ETX = 1 / (NLQ * LQ). So the link quality extensions to olsrd
194 introduce a new kind of HELLO messages, which we call <EM>LQ
195 HELLO</EM> messages. For each link listed in such a message, the
196 originator of the messages also tells us the link quality. So,
197 each neighbor puts the LQ values that it has determined in the
198 message, which from our perspective are NLQ values. So, owing to
199 the LQ HELLOs we now have all the information to calculate the
200 ETX for each link between ourselves and one of our neighbors.
204 Let's again have a look at the total number of transmissions
205 required for a route that consists of more than one hop,
206 i.e. that is not a route to one of our neighbors. If we stick
207 with the above example, we know ETX1 from the LQ HELLOs. But how
208 do we learn ETX2 and ETX3? For this the link quality extensions
209 to olsrd introduce a new kind of TC messages. TC messages are
210 used in OLSR to tell the world, i.e. all other nodes in the
211 MANET, which neighbors we have. We have extended TC messages to
212 additionally carry information on how good the links to our
213 neighbors are. We call this extended variant of TCs,
214 analogously to LQ HELLOS, <EM>LQ TC</EM> messages.
218 So, with LQ HELLO messages we find out which neighbors we have
219 and how good our links to them are and with LQ TC messages, we
220 share this knowledge with all other nodes and all other nodes
221 share their knowledge with us.
225 In this way each node in the network ends up knowing which links
226 each other node in the MANET has and how good they are. Well,
227 actually, it's a bit more complex than that, because of an
228 optimization called multi-point relaying. But this is beyond the
229 scope of this introductory text.
235 LQ HELLO messages and LQ TC messages are not compatible with
236 RFC-compliant HELLO and TC messages. So make sure that you
237 either switch <EM>all</EM> nodes of your network to link quality
238 or <EM>none</EM> of your nodes. A mixed configuration will
239 probably result in an unpredictable mess.
244 <H4>New Configuration Parameters</H4>
246 <H5>LinkQualityLevel</H5>
249 Let's now have a look at how we would use the link quality
250 extensions. The configuration parameter that controls link
251 quality is <EM>LinkQualityLevel</EM>, as it sets the level to
252 which link quality is used, i.e. for which purposes olsrd looks
253 at the link quality information.
258 Setting this parameter to 0 disables the link quality
259 extensions. olsrd then works in exactly the same way as
260 before, i.e. it is RFC-compliant, uses HELLO and TC
261 messages, and calculates routes by minimizing the hop count.
266 Setting this parameter to 1 enable the link quality
267 extensions and tells olsrd to select MPRs based on the link
268 quality information. A neighbor is selected as an MPR, if
269 it has the best route to any 2-hop neighbor. Suppose that
270 ETX1 is the expected number of transmissions between us and
271 a neighbor N and that ETX2 is the expected number of
272 transmissions between N and a two-hop neighbor N2. For each
273 of our two-hop neighbors we then select the neighbor N as
274 an MPR that results in the lowest possible total ETX of ETX1
280 Setting this parameter to 2 not only selects MPRs based on
281 the link quality but also considers link quality information
282 when calculating the routing table. For a given destination
283 node D we select the route that has the minimal total ETX of
284 ETX1 + ETX2 + ... + ETXn, where ETX1 is the expected number
285 of transmissions from us to our neighbor, ETX2 is the
286 expected number of transmissions from our neighbor to the
287 next node, and ETXn is the expected number of transmissions
288 from our destination's neighbor to the destination. This is
289 the recommended setting.
295 <B>IMPORTANT:</B> Remember to set <EM>all</EM> nodes of your
296 MANET to the same link quality level. Even if levels 2 and 3 use
297 the same kind of messages, i.e. LQ HELLOs and LQ TCs, they use a
298 different algorithm for calculating the routing table. This can
299 also mess up your routing!
302 <H5>LinkQualityWinSize</H5>
305 The second configuration parameter related to link quality is
306 <EM>LinkQualityWinSize</EM>. When determining the packet loss of
307 the packets received from a neighbor, olsrd only looks at the
308 <EM>n</EM> most recent packets. By default <EM>n</EM> is set to
309 10, so olsrd looks at the ten most recent packets received (or
310 not received) from a neighbor and then determines the packet
311 loss. Let's assume that of the 10 packets we have received 7,
312 then we have missed 3, which corresponds to a packet loss of
313 3/10 = 0.3 = 30%. The corresponding Link Quality is 7/10 = 0.7 =
318 Let's have a look at what the default value means. Let's for the
319 moment only think of LQ HELLO messages and neglect other message
320 types. By default LQ HELLOs are sent every 2 seconds. So, we
321 calculate the packet loss over the past 20 seconds. So, changes
322 in the link quality are accounted for relatively fast. For
323 longer intervals just increase this value.
326 <H5>LinkQualityMult</H5>
329 Version 0.4.9 supports a third configuration parameter,
330 <EM>LinkQualityMult</EM>. This is a per-interface parameter, so
331 it may only appear in an interface configuration block. This
332 parameter can be used to alter the LQ values that we announce,
333 which will then result in an altered ETX for links between us
334 and our neighbors - remember that ETX = 1 / (NLQ x LQ).
338 The idea is to enable us to make certain links that we have
339 artificially appear better or worse than they actually are. In
340 this way we can manually affect the routing decisions made by
345 The <EM>LinkQualityMult</EM> parameter is followed by an IP
346 address and a number, the multiplier. The IP address specifies
347 the IP address of the neighbor interface address of the link
348 that we want to manipulate. The LQ values that we determine for
349 this link are then multiplied by the given multiplier.
353 If the word <EM>default</EM> is specified in lieu of an IP
354 address, then this multiplier applies to all links via the
355 interface that we're configuring. Note, however, that a
356 multiplier linked to a real IP address has priority over the
357 default multiplier. So, we're looking for the most specific
361 <H4>Old Configuration Parameters</H4>
364 The link quality extensions do not work very well with
365 hysteresis. Hysteresis basically acts as a sort of barrier that
366 only links that are "good enough" can cross. If a link is too
367 flaky, hysteresis will make olsrd consider the link as
368 non-existent. So, this is a binary thing. Either a link is able
369 to cross the barrier, or it is not. There's nothing in
370 between. However, we want olsrd to consider <EM>every</EM> link
371 there is, without any barrier, because then we can leave it to
372 the link quality extensions to judge how good the link actually
373 is and how much we trust the link.
377 If a link with an ETX value of 50 is the only way of
378 reaching a node, then we want to use this link, as there is no
383 In addition, in contrast to only saying "good enough" or "not
384 good enough" like hysteresis, the link quality extensions offer
385 a much more detailed view of the world by saying something like
386 "75% good enough, 25% not good enough".
390 The second mechanism that could interfere with the link quality
391 extensions is the link detection scheme. By default, if olsrd
392 misses three (LQ) HELLO messages in a row from a neighbor, the
393 link is considered broken. However, we'd prefer the link to just
394 expose a lower quality. So, setting the HELLO validity time to
395 the HELLO interval multiplied by the link quality window size is
396 probably a good rule of thumb. In this way the link will be
397 removed not before the link quality extensions have had enough
398 time to gradually reduce the link quality to zero.
401 <H4>Sample Configuration</H4>
404 A minimal configuration that leaves everything at the default
405 and just makes the changes required for the link quality
406 extension to work properly could look as follows. Note the
407 <EM>ClearScreen</EM> directive that causes the screen to be
408 cleared before updated debug information is printed. This makes
409 the debug output more readable in many cases.
416 LinkQualityWinSize 12
422 HelloValidityTime 20.0
427 Let's assume that we would like to use the
428 <EM>LinkQualityMult</EM> directive to multiply the LQ value that
429 we report for the link between our local interface <EM>if03</EM>
430 and an interface of one of our neighbors that has an IP address
431 of 192.168.0.1. Say, we'd like to multiply the LQ value by
432 0.5. We would then simply add the following line to the
433 <EM>Interface</EM> section of the above configuration file.
437 LinkQualityMult 192.168.0.1 0.5
441 Suppose that we would further like to multiply the LQ values
442 that we report for all other links between our local interface
443 <EM>if03</EM> and a neighbor interface by 0.8. We would then
444 add a second, default <EM>LinkQualityMult</EM> statement and we
445 would end up with the following two lines.
449 LinkQualityMult 192.168.0.1 0.5
450 LinkQualityMult default 0.8
454 For the link to 192.168.0.1 the first line would have precedence
455 over the second (default) line and 0.5 would be used as the
456 multiplier. For all other links the default multiplier of 0.8
457 would be used, as there isn't any better match.
460 <H3>Debug Output</H3>
463 0.4.8 also introduces significant changes in the debug
464 output. Let's have a look at what happens at debug level 2, which
465 is the recommended default for the link quality extensions.
469 --- 14:28:56.80 ---------------------------------------------------- LINKS
471 IP address hyst LQ lost total NLQ ETX
472 192.168.0.1 0.000 1.000 0 10 1.000 1.00
476 This table contains the links to our neighbors. It contains the
483 <EM>IP address</EM> - the IP address of the interface via
484 which we have contact to the neighbor.
489 <EM>hyst</EM> - the current hysteresis value for this link.
494 <EM>LQ</EM> - the quality of the link determined at our
495 end. This is what we have previously called the Link
501 <EM>lost</EM> - the number of lost packets among the
502 <EM>n</EM> packets most recently sent by our neighbor via
503 this link. <EM>n</EM> is the link quality window size.
508 <EM>total</EM> - the total number of packets received up to
509 now. This value starts at 0 immediately after a link has
510 come to life and then counts each packet. It is capped at
511 the link quality window size.
516 <EM>NLQ</EM> - this is our neighbor's view of the link
517 quality. Previously we have called this the Neighbor Link
518 Quality. This value is extracted from LQ HELLO messages
519 received from our neighbors. NB: If a neighbor stops
520 sending packets completely, we do not have any means of
521 updating this value. However, in this case the LQ value will
522 decrease and the link thus be detected as becoming worse.
527 <EM>ETX</EM> - this is the ETX for this link, i.e. 1 / (NLQ
534 --- 14:28:56.80 ------------------------------------------------ NEIGHBORS
536 IP address LQ NLQ SYM MPR MPRS will
537 10.0.0.6 1.000 1.000 YES YES NO 6
541 This table contains a list of all our neighbors. It is closely
542 related to the link table in that we are connected to a
543 neighbor via one or more links. The table has the following
550 <EM>IP address</EM> - the main IP address of the neighbor.
555 <EM>LQ</EM> and <EM>NLQ</EM> - the LQ and NLQ values of the
556 best link that we have with this neighbor. (In
557 multi-interface configurations we can have more than one
558 link with a neighbor.)
563 <EM>SYM</EM> - this states whether the link to this
564 neighbor is considered symmetric by olsrd's link detection
570 <EM>MPR</EM> (multi-point relay) - this indicates whether we
571 have selected this neighbor to act as an MPR for us.
576 <EM>MPRS</EM> (multi-point relay selector) - this indicates
577 whether the neighbor node has selected us to act as an MPR
583 <EM>will</EM> - the neighbor's willingness.
589 --- 14:28:56.80 ------------------------------------------------- TOPOLOGY
591 Source IP addr Dest IP addr LQ ILQ ETX
592 10.0.0.6 192.168.0.2 1.000 1.000 1.00
593 10.0.0.6 10.0.0.5 1.000 1.000 1.00
597 This table displays the topology information that olsrd has
598 gathered from LQ TC messages. It states which nodes in the
599 network report links to which other nodes and which quality
600 these links have. So, it's olsrd's view of the world beyond its
601 immediate neighbor nodes, i.e. its view of the nodes that it
602 cannot reach directly. This table has the following columns.
608 <EM>Source IP addr</EM> - the node that reports a link.
613 <EM>Dest IP addr</EM> - the node to which the source node
619 <EM>LQ</EM> (link quality) - the quality of the link as
620 determined by the source node. For the source node this is
621 the Link Quality. For the destination node this is the
622 Neighbor Link Quality.
627 <EM>ILQ</EM> (inverse link quality) - the quality of the
628 link as determined by the destination node. For the source
629 node this is the Neighbor Link Quality. For the destination
630 node this is the Link Quality. We just did not want to name
631 it "NLQ", as we use NLQ only for the link quality reported
632 by our neighbors. But functionally this is equivalent to
633 the NLQ we know from the link and neighbor tables.
638 <EM>ETX</EM> - the ETX value for this link, calculated by
639 ETX = 1 / (ILQ x LQ).
645 --- 14:28:56.80 ------------------------------------------------- DIJKSTRA
647 10.0.0.6:1.00 (one-hop)
648 10.0.0.5:2.00 <- 10.0.0.6:1.00 (one-hop)
652 This table displays the best routes that olsrd could find for
653 each destination that it knows about. The leftmost IP address
654 given on each line is the destination of a route. The remaining
655 IP addresses in a line specify the nodes on the route between
656 ourselves and the destination address. Moving from the
657 destination address to the right, address by address, moves us
658 closer from the destination to ourselves, hop by hop.
662 In the above case we see routes to two nodes, 10.0.0.6 and
663 10.0.0.5. In the first line, there aren't any intermediate nodes
664 between us and the destination, the destination address is the
665 only IP address in this line. In the second line we have one
666 intermediate node, 10.0.0.6. So, the second line describes a
667 route to 10.0.0.5 via 10.0.0.6.
671 The number after the colon following an IP address in the table
672 is the total ETX of the route up to this IP address, i.e. the
673 sum of the ETX values of all hops between ourselves and this IP
678 In the above example the first line represents a path with an
679 ETX value of 1.00 to 10.0.0.6. As we've seen in the neighbor
680 table above 10.0.0.6 is our neighbor, so the route to it
681 consists only of a single hop, which has an ETX of 1.00, hence
682 the 1.00 in this line.
686 In the second line, 10.0.0.5 is not a neighbor of ours. However,
687 10.0.0.6 is and from the topology table above we can tell that
688 10.0.0.6 reports a link to 10.0.0.5. So, we can reach 10.0.0.5
689 via 10.0.0.6. This is what this line says. Remember that each
690 line represents a route by first giving the IP address of the
691 destination (10.0.0.5) and that moving to the right means moving
692 towards ourselves until one of our (one-hop) neighbor is
693 reached. If we move from 10.0.0.5 to the right, we find
694 10.0.0.6, which is our (one-hop) neighbor. So we have a route.
698 If we would like to know which path a packet takes that we send
699 to 10.0.0.5, we have to read the line backwards. We then see
700 that the packet first travels to our (one-hop) neighbor 10.0.0.6
701 via a link that has an ETX of 1.00 (which we can confirm by
702 looking at the neighbor table above). From there it is forwarded
703 to 10.0.0.5 via another link that also has an ETX of 1.00 (which
704 we can confirm by means of the topology table above), resulting
705 in a total ETX of 1.00 + 1.00 = 2.00, which is the number that
706 follows 10.0.0.5. Remember that the ETX value given for an IP
707 address is the cumulative ETX for the complete route up to this
712 If olsrd is able to find a route between us and the destination,
713 the last IP address in the line is one of our neighbors. In this
714 case, "(one-hop)" is appended to the line to illustrate that the
715 last IP address is one of our (one-hop) neighbors. However,
716 let's assume that we've just switched on olsrd. In this case, it
717 does not know about all links in the network, yet, as it hasn't
718 received LQ TC messages from all nodes. So, it may know that a
719 node exists (as it has already received LQ TC messages from it)
720 but it does not necessarily know how to reach it (as it may not
721 have received LQ TC messages from nodes between it and
722 ourselves, yet). In this case the last IP address is the last
723 node that is reachable from the destination and the line ends
724 with the word "FAILED".
728 The same is true for neighbors to which we do not have a
729 symmetric link. We know that they're there, but we do not have a
730 link to them, hence olsrd cannot find a route, which results in
737 If you have any questions on using olsrd or if you would like to
738 know more about the link quality extension, it's probably best
739 to subscribe to the mailing lists and ask your question
740 there. Information on the mailing lists is available at
741 <A HREF="http://www.olsr.org">http://www.olsr.org</A>.
Repositories / olsrd.git / blob