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.5 2007/09/06 11:45:09 bernd67 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
166 <a href="http://pdos.csail.mit.edu/papers/grid:mobicom03/">
167 scientific paper</a> by the people who invented all this, and
168 for those who would like to know still more, there's
169 <a href="http://pdos.csail.mit.edu/papers/grid:decouto-phd/thesis.pdf">
170 Doug's PhD</a> thesis.
174 Let's assume that we have a route from ourselves via two nodes A
175 and B to a node C. What is the ETX for the total route, i.e. how
176 often is our packet retransmitted on its way from us to C? Well,
177 we know how many attempts we need on average to successfully
178 transmit a packet from us to A. Let's call this value ETX1. So,
179 we already have ETX1 attempts just to reach A. The packet would
180 then take an additional number of attempts to hop from A to
181 B. Let's call this second value ETX2. Finally, a further number
182 of attempts is required to hop from B to C. Let's call this
183 third value ETX3. Let's now have a look at the total number of
184 transmissions that have happened to get our packet from us to
185 C. This number is simply ETX1 + ETX2 + ETX3.
191 In order to calculate the ETX for a link to a neighbor, we need
192 to know the neighbor's idea of the link quality, i.e. the NLQ,
193 as we can only determine the LQ ourselves, but we want to know
194 ETX = 1 / (NLQ * LQ). So the link quality extensions to olsrd
195 introduce a new kind of HELLO messages, which we call <EM>LQ
196 HELLO</EM> messages. For each link listed in such a message, the
197 originator of the messages also tells us the link quality. So,
198 each neighbor puts the LQ values that it has determined in the
199 message, which from our perspective are NLQ values. So, owing to
200 the LQ HELLOs we now have all the information to calculate the
201 ETX for each link between ourselves and one of our neighbors.
205 Let's again have a look at the total number of transmissions
206 required for a route that consists of more than one hop,
207 i.e. that is not a route to one of our neighbors. If we stick
208 with the above example, we know ETX1 from the LQ HELLOs. But how
209 do we learn ETX2 and ETX3? For this the link quality extensions
210 to olsrd introduce a new kind of TC messages. TC messages are
211 used in OLSR to tell the world, i.e. all other nodes in the
212 MANET, which neighbors we have. We have extended TC messages to
213 additionally carry information on how good the links to our
214 neighbors are. We call this extended variant of TCs,
215 analogously to LQ HELLOS, <EM>LQ TC</EM> messages.
219 So, with LQ HELLO messages we find out which neighbors we have
220 and how good our links to them are and with LQ TC messages, we
221 share this knowledge with all other nodes and all other nodes
222 share their knowledge with us.
226 In this way each node in the network ends up knowing which links
227 each other node in the MANET has and how good they are. Well,
228 actually, it's a bit more complex than that, because of an
229 optimization called multi-point relaying. But this is beyond the
230 scope of this introductory text.
236 LQ HELLO messages and LQ TC messages are not compatible with
237 RFC-compliant HELLO and TC messages. So make sure that you
238 either switch <EM>all</EM> nodes of your network to link quality
239 or <EM>none</EM> of your nodes. A mixed configuration will
240 probably result in an unpredictable mess.
245 <H4>New Configuration Parameters</H4>
247 <H5>LinkQualityLevel</H5>
250 Let's now have a look at how we would use the link quality
251 extensions. The configuration parameter that controls link
252 quality is <EM>LinkQualityLevel</EM>, as it sets the level to
253 which link quality is used, i.e. for which purposes olsrd looks
254 at the link quality information.
259 Setting this parameter to 0 disables the link quality
260 extensions. olsrd then works in exactly the same way as
261 before, i.e. it is RFC-compliant, uses HELLO and TC
262 messages, and calculates routes by minimizing the hop count.
267 Setting this parameter to 1 enable the link quality
268 extensions and tells olsrd to select MPRs based on the link
269 quality information. A neighbor is selected as an MPR, if
270 it has the best route to any 2-hop neighbor. Suppose that
271 ETX1 is the expected number of transmissions between us and
272 a neighbor N and that ETX2 is the expected number of
273 transmissions between N and a two-hop neighbor N2. For each
274 of our two-hop neighbors we then select the neighbor N as
275 an MPR that results in the lowest possible total ETX of ETX1
281 Setting this parameter to 2 not only selects MPRs based on
282 the link quality but also considers link quality information
283 when calculating the routing table. For a given destination
284 node D we select the route that has the minimal total ETX of
285 ETX1 + ETX2 + ... + ETXn, where ETX1 is the expected number
286 of transmissions from us to our neighbor, ETX2 is the
287 expected number of transmissions from our neighbor to the
288 next node, and ETXn is the expected number of transmissions
289 from our destination's neighbor to the destination. This is
290 the recommended setting.
296 <B>IMPORTANT:</B> Remember to set <EM>all</EM> nodes of your
297 MANET to the same link quality level. Even if levels 2 and 3 use
298 the same kind of messages, i.e. LQ HELLOs and LQ TCs, they use a
299 different algorithm for calculating the routing table. This can
300 also mess up your routing!
303 <H5>LinkQualityWinSize</H5>
306 The second configuration parameter related to link quality is
307 <EM>LinkQualityWinSize</EM>. When determining the packet loss of
308 the packets received from a neighbor, olsrd only looks at the
309 <EM>n</EM> most recent packets. By default <EM>n</EM> is set to
310 10, so olsrd looks at the ten most recent packets received (or
311 not received) from a neighbor and then determines the packet
312 loss. Let's assume that of the 10 packets we have received 7,
313 then we have missed 3, which corresponds to a packet loss of
314 3/10 = 0.3 = 30%. The corresponding Link Quality is 7/10 = 0.7 =
319 Let's have a look at what the default value means. Let's for the
320 moment only think of LQ HELLO messages and neglect other message
321 types. By default LQ HELLOs are sent every 2 seconds. So, we
322 calculate the packet loss over the past 20 seconds. So, changes
323 in the link quality are accounted for relatively fast. For
324 longer intervals just increase this value.
327 <H5>LinkQualityMult</H5>
330 Version 0.4.9 supports a third configuration parameter,
331 <EM>LinkQualityMult</EM>. This is a per-interface parameter, so
332 it may only appear in an interface configuration block. This
333 parameter can be used to alter the LQ values that we announce,
334 which will then result in an altered ETX for links between us
335 and our neighbors - remember that ETX = 1 / (NLQ x LQ).
339 The idea is to enable us to make certain links that we have
340 artificially appear better or worse than they actually are. In
341 this way we can manually affect the routing decisions made by
346 The <EM>LinkQualityMult</EM> parameter is followed by an IP
347 address and a number, the multiplier. The IP address specifies
348 the IP address of the neighbor interface address of the link
349 that we want to manipulate. The LQ values that we determine for
350 this link are then multiplied by the given multiplier.
354 If the word <EM>default</EM> is specified in lieu of an IP
355 address, then this multiplier applies to all links via the
356 interface that we're configuring. Note, however, that a
357 multiplier linked to a real IP address has priority over the
358 default multiplier. So, we're looking for the most specific
362 <H4>Old Configuration Parameters</H4>
365 The link quality extensions do not work very well with
366 hysteresis. Hysteresis basically acts as a sort of barrier that
367 only links that are "good enough" can cross. If a link is too
368 flaky, hysteresis will make olsrd consider the link as
369 non-existent. So, this is a binary thing. Either a link is able
370 to cross the barrier, or it is not. There's nothing in
371 between. However, we want olsrd to consider <EM>every</EM> link
372 there is, without any barrier, because then we can leave it to
373 the link quality extensions to judge how good the link actually
374 is and how much we trust the link.
378 If a link with an ETX value of 50 is the only way of
379 reaching a node, then we want to use this link, as there is no
384 In addition, in contrast to only saying "good enough" or "not
385 good enough" like hysteresis, the link quality extensions offer
386 a much more detailed view of the world by saying something like
387 "75% good enough, 25% not good enough".
391 The second mechanism that could interfere with the link quality
392 extensions is the link detection scheme. By default, if olsrd
393 misses three (LQ) HELLO messages in a row from a neighbor, the
394 link is considered broken. However, we'd prefer the link to just
395 expose a lower quality. So, setting the HELLO validity time to
396 the HELLO interval multiplied by the link quality window size is
397 probably a good rule of thumb. In this way the link will be
398 removed not before the link quality extensions have had enough
399 time to gradually reduce the link quality to zero.
402 <H4>Sample Configuration</H4>
405 A minimal configuration that leaves everything at the default
406 and just makes the changes required for the link quality
407 extension to work properly could look as follows. Note the
408 <EM>ClearScreen</EM> directive that causes the screen to be
409 cleared before updated debug information is printed. This makes
410 the debug output more readable in many cases.
417 LinkQualityWinSize 12
423 HelloValidityTime 20.0
428 Let's assume that we would like to use the
429 <EM>LinkQualityMult</EM> directive to multiply the LQ value that
430 we report for the link between our local interface <EM>if03</EM>
431 and an interface of one of our neighbors that has an IP address
432 of 192.168.0.1. Say, we'd like to multiply the LQ value by
433 0.5. We would then simply add the following line to the
434 <EM>Interface</EM> section of the above configuration file.
438 LinkQualityMult 192.168.0.1 0.5
442 Suppose that we would further like to multiply the LQ values
443 that we report for all other links between our local interface
444 <EM>if03</EM> and a neighbor interface by 0.8. We would then
445 add a second, default <EM>LinkQualityMult</EM> statement and we
446 would end up with the following two lines.
450 LinkQualityMult 192.168.0.1 0.5
451 LinkQualityMult default 0.8
455 For the link to 192.168.0.1 the first line would have precedence
456 over the second (default) line and 0.5 would be used as the
457 multiplier. For all other links the default multiplier of 0.8
458 would be used, as there isn't any better match.
461 <H3>Debug Output</H3>
464 0.4.8 also introduces significant changes in the debug
465 output. Let's have a look at what happens at debug level 2, which
466 is the recommended default for the link quality extensions.
470 --- 14:28:56.80 ---------------------------------------------------- LINKS
472 IP address hyst LQ lost total NLQ ETX
473 192.168.0.1 0.000 1.000 0 10 1.000 1.00
477 This table contains the links to our neighbors. It contains the
484 <EM>IP address</EM> - the IP address of the interface via
485 which we have contact to the neighbor.
490 <EM>hyst</EM> - the current hysteresis value for this link.
495 <EM>LQ</EM> - the quality of the link determined at our
496 end. This is what we have previously called the Link
502 <EM>lost</EM> - the number of lost packets among the
503 <EM>n</EM> packets most recently sent by our neighbor via
504 this link. <EM>n</EM> is the link quality window size.
509 <EM>total</EM> - the total number of packets received up to
510 now. This value starts at 0 immediately after a link has
511 come to life and then counts each packet. It is capped at
512 the link quality window size.
517 <EM>NLQ</EM> - this is our neighbor's view of the link
518 quality. Previously we have called this the Neighbor Link
519 Quality. This value is extracted from LQ HELLO messages
520 received from our neighbors. NB: If a neighbor stops
521 sending packets completely, we do not have any means of
522 updating this value. However, in this case the LQ value will
523 decrease and the link thus be detected as becoming worse.
528 <EM>ETX</EM> - this is the ETX for this link, i.e. 1 / (NLQ
535 --- 14:28:56.80 ------------------------------------------------ NEIGHBORS
537 IP address LQ NLQ SYM MPR MPRS will
538 10.0.0.6 1.000 1.000 YES YES NO 6
542 This table contains a list of all our neighbors. It is closely
543 related to the link table in that we are connected to a
544 neighbor via one or more links. The table has the following
551 <EM>IP address</EM> - the main IP address of the neighbor.
556 <EM>LQ</EM> and <EM>NLQ</EM> - the LQ and NLQ values of the
557 best link that we have with this neighbor. (In
558 multi-interface configurations we can have more than one
559 link with a neighbor.)
564 <EM>SYM</EM> - this states whether the link to this
565 neighbor is considered symmetric by olsrd's link detection
571 <EM>MPR</EM> (multi-point relay) - this indicates whether we
572 have selected this neighbor to act as an MPR for us.
577 <EM>MPRS</EM> (multi-point relay selector) - this indicates
578 whether the neighbor node has selected us to act as an MPR
584 <EM>will</EM> - the neighbor's willingness.
590 --- 14:28:56.80 ------------------------------------------------- TOPOLOGY
592 Source IP addr Dest IP addr LQ ILQ ETX
593 10.0.0.6 192.168.0.2 1.000 1.000 1.00
594 10.0.0.6 10.0.0.5 1.000 1.000 1.00
598 This table displays the topology information that olsrd has
599 gathered from LQ TC messages. It states which nodes in the
600 network report links to which other nodes and which quality
601 these links have. So, it's olsrd's view of the world beyond its
602 immediate neighbor nodes, i.e. its view of the nodes that it
603 cannot reach directly. This table has the following columns.
609 <EM>Source IP addr</EM> - the node that reports a link.
614 <EM>Dest IP addr</EM> - the node to which the source node
620 <EM>LQ</EM> (link quality) - the quality of the link as
621 determined by the source node. For the source node this is
622 the Link Quality. For the destination node this is the
623 Neighbor Link Quality.
628 <EM>ILQ</EM> (inverse link quality) - the quality of the
629 link as determined by the destination node. For the source
630 node this is the Neighbor Link Quality. For the destination
631 node this is the Link Quality. We just did not want to name
632 it "NLQ", as we use NLQ only for the link quality reported
633 by our neighbors. But functionally this is equivalent to
634 the NLQ we know from the link and neighbor tables.
639 <EM>ETX</EM> - the ETX value for this link, calculated by
640 ETX = 1 / (ILQ x LQ).
646 --- 14:28:56.80 ------------------------------------------------- DIJKSTRA
648 10.0.0.6:1.00 (one-hop)
649 10.0.0.5:2.00 <- 10.0.0.6:1.00 (one-hop)
653 This table displays the best routes that olsrd could find for
654 each destination that it knows about. The leftmost IP address
655 given on each line is the destination of a route. The remaining
656 IP addresses in a line specify the nodes on the route between
657 ourselves and the destination address. Moving from the
658 destination address to the right, address by address, moves us
659 closer from the destination to ourselves, hop by hop.
663 In the above case we see routes to two nodes, 10.0.0.6 and
664 10.0.0.5. In the first line, there aren't any intermediate nodes
665 between us and the destination, the destination address is the
666 only IP address in this line. In the second line we have one
667 intermediate node, 10.0.0.6. So, the second line describes a
668 route to 10.0.0.5 via 10.0.0.6.
672 The number after the colon following an IP address in the table
673 is the total ETX of the route up to this IP address, i.e. the
674 sum of the ETX values of all hops between ourselves and this IP
679 In the above example the first line represents a path with an
680 ETX value of 1.00 to 10.0.0.6. As we've seen in the neighbor
681 table above 10.0.0.6 is our neighbor, so the route to it
682 consists only of a single hop, which has an ETX of 1.00, hence
683 the 1.00 in this line.
687 In the second line, 10.0.0.5 is not a neighbor of ours. However,
688 10.0.0.6 is and from the topology table above we can tell that
689 10.0.0.6 reports a link to 10.0.0.5. So, we can reach 10.0.0.5
690 via 10.0.0.6. This is what this line says. Remember that each
691 line represents a route by first giving the IP address of the
692 destination (10.0.0.5) and that moving to the right means moving
693 towards ourselves until one of our (one-hop) neighbor is
694 reached. If we move from 10.0.0.5 to the right, we find
695 10.0.0.6, which is our (one-hop) neighbor. So we have a route.
699 If we would like to know which path a packet takes that we send
700 to 10.0.0.5, we have to read the line backwards. We then see
701 that the packet first travels to our (one-hop) neighbor 10.0.0.6
702 via a link that has an ETX of 1.00 (which we can confirm by
703 looking at the neighbor table above). From there it is forwarded
704 to 10.0.0.5 via another link that also has an ETX of 1.00 (which
705 we can confirm by means of the topology table above), resulting
706 in a total ETX of 1.00 + 1.00 = 2.00, which is the number that
707 follows 10.0.0.5. Remember that the ETX value given for an IP
708 address is the cumulative ETX for the complete route up to this
713 If olsrd is able to find a route between us and the destination,
714 the last IP address in the line is one of our neighbors. In this
715 case, "(one-hop)" is appended to the line to illustrate that the
716 last IP address is one of our (one-hop) neighbors. However,
717 let's assume that we've just switched on olsrd. In this case, it
718 does not know about all links in the network, yet, as it hasn't
719 received LQ TC messages from all nodes. So, it may know that a
720 node exists (as it has already received LQ TC messages from it)
721 but it does not necessarily know how to reach it (as it may not
722 have received LQ TC messages from nodes between it and
723 ourselves, yet). In this case the last IP address is the last
724 node that is reachable from the destination and the line ends
725 with the word "FAILED".
729 The same is true for neighbors to which we do not have a
730 symmetric link. We know that they're there, but we do not have a
731 link to them, hence olsrd cannot find a route, which results in
738 If you have any questions on using olsrd or if you would like to
739 know more about the link quality extension, it's probably best
740 to subscribe to the mailing lists and ask your question
741 there. Information on the mailing lists is available at
742 <A HREF="http://www.olsr.org">http://www.olsr.org</A>.
Repositories / olsrd.git / blob