Ipv4 netmask in HNa section fixed
[olsrd.git] / README-Link-Quality.html
1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
2 <HTML>
3   <HEAD>
4     <TITLE>olsrd Link Quality Extensions</TITLE>
5
6     <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
7
8     <STYLE TYPE="text/css">
9       body {
10         font-family: verdana,arial,sans-serif;
11         font-size: 10pt;
12         background-color: #ffffff;
13         color: #000000;
14       }
15
16       :link { color: #123e80 }
17       :visited { color: #123e80 }
18       :active { color: #123e80 }
19     </STYLE>
20   </HEAD>
21
22   <BODY>
23     <H2>olsrd Link Quality Extensions</H2>
24
25     <P>
26       $Id: README-Link-Quality.html,v 1.1 2004/12/05 20:37:18 tlopatic Exp $
27     </P>
28
29     <H3>Credits</H3>
30
31     <P>
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> and
35       <A HREF="http://www.freifunk.net">freifunk.net</A>.
36       Any implementation bugs are nevertheless solely Thomas's fault,
37       though.
38     </P>
39
40     <P>
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
44       you!
45     </P>
46       
47     <H3>Theory</H3>
48
49     <P>
50       Release 0.4.8 of olsrd offers an experimental implementation of
51       an ETX-like metric. When calculating a routing table for us,
52       pure RFC-compliant OLSR simply minimizes the number of hops
53       between ourselves and the other nodes in the MANET, even if this
54       means that a route via a single very bad link will be preferred
55       to a route via two excellent links, although the latter would
56       probably have been the better choice.
57     </P>
58
59     <P>
60       To solve this problem, we have to teach olsrd how to tell good
61       links from bad links. We have done so by measuring the packet
62       loss for OLSR packets that we receive from our neighbors. As we
63       periodically receive HELLO messages from our neighbors (by
64       default every 2 seconds), we have enough packets to determine
65       the packet loss for packets that each of our neighbors sends to
66       us.
67     </P>
68
69     <P>
70       If, for example, 3 out of 10 packets are lost on their way from
71       our neighbor to ourselves, we have a packet loss of 3/10 = 0.3 =
72       30%. At the same time 7 of the 10 packets that the neighbor sent
73       went through. Hence, the probability for a successful packet
74       transmission from this neighbor to ourselves is 7/10 = 0.7 =
75       70%. This probability is what we call the <EM>Link
76       Quality</EM>. So the Link Quality says how good a given link
77       between a neighbor and ourselves is in the direction from the
78       neighbor to ourselves. It does so by saying how likely it is
79       that a packet that we send is successfully received by our
80       neighbor.
81     </P>
82
83     <P>
84       However, it is also important to know the quality of the link in
85       the opposite direction, i.e. how many of the packets that we
86       send out are received by each of our neighbors. So, we are not
87       only interested in the Link Quality of a given link, but also in
88       the corresponding neighbor's idea of the Link Quality. That's
89       what we call the <EM>Neighbor Link Quality</EM>. The Neighbor
90       Link Quality says how good a given link between a neighbor and
91       ourselves is in the direction from ourselves to the neighbor.
92     </P>
93
94     <P>
95       The Link Quality and the Neighbor Link Quality are values
96       between 0 and 1 or, which is equivalent, between 0 and
97       100%. They represent the probability that a packet that our
98       neighbor sends actually makes it to us (Link Quality) and that
99       a packet that we send actually makes it to our neighbor
100       (Neighbor Link Quality).
101     </P>
102
103     <P>
104       Let's now look at the probability for a successful packet round
105       trip, i.e. the probability that we successfully send a packet to
106       our neighbor and, on receiving it, our neighbor successfully
107       replies with a response packet. For a successful round trip both
108       packets must get through, the packet that we've sent and the
109       response packet that our neighbor has sent. So, the success
110       probability is NLQ x LQ, where NLQ is the Neighbor Link Quality
111       of the link and LQ is its link quality. For example, if we have
112       a NLQ of 60% and a LQ of 70%, the probability of a successful
113       round trip is 60% x 70% = 0.6 x 0.7 = 0.42 = 42%.
114     </P>
115
116     <P>
117       In wireless networks each recipient of a packet acknowledges
118       packet reception by sending back an acknowledgment packet to
119       the sender. So, when does a retransmission of a packet happen? 
120       It happens, if the sender does not receive an
121       acknowledgment. And in which cases does the sender not receive
122       an acknowledgment? If either the packet that it sent is lost or
123       if the corresponding acknowledgment packet is lost. So, what is
124       the probability for a retransmission to <EM>not</EM> take place? 
125       Well, as the sender's packet has to get through in one direction
126       and the recipient's acknowledgment has to get through in the
127       opposite direction, too, this is exactly the probability for a
128       successful packet round trip, i.e. NLQ x LQ.
129     </P>
130
131     <P>
132       We can now answer the question of how many transmission attempts
133       it will typically take to get a packet from us to a neighbor or
134       from the neighbor to us. It is 1 / (NLQ x LQ). So, in the above
135       case of NLQ x LQ = 42%, we expect on average 1 / 0.42 = 2.38
136       transmission attempts for a packet until it gets through.
137     </P>
138
139     <P>
140       Note that this number is valid for both directions of the link,
141       as in both cases we have to look at the probability for a
142       successful packet round trip. For packets that we send to our
143       neighbor, the packet goes from us to the neighbor and the
144       acknowledgment travels the other way around. For packets that
145       our neighbor sends to us, the packet goes from the neighbor to
146       us and the acknowledgment travels from us to the neighbor. In
147       both cases a packet is sent in each direction and retransmission
148       occurs if either packet is lost.
149     </P>
150
151     <P>
152       The value 1 / (NLQ x LQ) is called the <EM>Expected Transmission
153       Count</EM> or <EM>ETX</EM>. For those interested in a more
154       in-depth discussion, there's a scientific paper on it, just
155       goggle for "expected transmission count".
156     </P>
157
158     <P>
159       Let's assume that we have a route from ourselves via two nodes A
160       and B to a node C. What is the ETX for the total route, i.e. how
161       often is our packet retransmitted on its way from us to C? Well,
162       we know how many attempts we need on average to successfully
163       transmit a packet from us to A. Let's call this value ETX1. So,
164       we already have ETX1 attempts just to reach A. The packet would
165       then take an additional number of attempts to hop from A to
166       B. Let's call this second value ETX2. Finally, a further number
167       of attempts is required to hop from B to C. Let's call this
168       third value ETX3. Let's now have a look at the total number of
169       transmissions that have happened to get our packet from us to
170       C. This number is simply ETX1 + ETX2 + ETX3.
171     </P>
172
173     <H3>Protocol</H3>
174
175     <P>
176       In order to calculate the ETX for a link to a neighbor, we need
177       to know the neighbor's idea of the link quality, i.e. the NLQ,
178       as we can only determine the LQ ourselves, but we want to know
179       ETX = 1 / (NLQ * LQ). So the link quality extensions to olsrd
180       introduce a new kind of HELLO messages, which we call <EM>LQ
181       HELLO</EM> messages. For each link listed in such a message, the
182       originator of the messages also tells us the link quality. So,
183       each neighbor puts the LQ values that it has determined in the
184       message, which from our perspective are NLQ values. So, owing to
185       the LQ HELLOs we now have all the information to calculate the
186       ETX for each link between ourselves and one of our neighbors.
187     </P>
188
189     <P>
190       Let's again have a look at the total number of transmissions
191       required for a route that consists of more than one hop,
192       i.e. that is not a route to one of our neighbors. If we stick
193       with the above example, we know ETX1 from the LQ HELLOs. But how
194       do we learn ETX2 and ETX3? For this the link quality extensions
195       to olsrd introduce a new kind of TC messages. TC messages are
196       used in OLSR to tell the world, i.e. all other nodes in the
197       MANET, which neighbors we have. We have extended TC messages to
198       additionally carry information on how good the links to our
199       neighbors are. We call this extended variant of TCs,
200       analogously to LQ HELLOS, <EM>LQ TC</EM> messages.
201     </P>
202
203     <P>
204       So, with LQ HELLO messages we find out which neighbors we have
205       and how good our links to them are and with LQ TC messages, we
206       share this knowledge with all other nodes and all other nodes
207       share their knowledge with us.
208     </P>
209
210     <P>
211       In this way each node in the network ends up knowing which links
212       each other node in the MANET has and how good they are. Well,
213       actually, it's a bit more complex than that, because of an
214       optimization called multi-point relaying. But this is beyond the
215       scope of this introductory text.
216     </P>
217
218     <H3>Warning</H3>
219
220     <P>
221       LQ HELLO messages and LQ TC messages are not compatible with
222       RFC-compliant HELLO and TC messages. So make sure that you
223       either switch <EM>all</EM> nodes of your network to link quality
224       or <EM>none</EM> of your nodes. A mixed configuration will
225       probably result in an unpredictable mess.
226     </P>
227
228     <H3>Practice</H3>
229
230     <H4>New Configuration Parameters</H4>
231
232     <P>
233       Let's now have a look at how we would use the link quality
234       extensions. The configuration parameter that controls link
235       quality is <EM>LinkQualityLevel</EM>, as it sets the level to
236       which link quality is used, i.e. for which purposes olsrd looks
237       at the link quality information.
238     </P>
239     <UL>
240       <LI>
241         <P>
242           Setting this parameter to 0 disables the link quality
243           extensions. olsrd then works in exactly the same way as
244           before, i.e. it is RFC-compliant, uses HELLO and TC
245           messages, and calculates routes by minimizing the hop count.
246         </P>
247       </LI>
248       <LI>
249         <P>
250           Setting this parameter to 1 enable the link quality
251           extensions and tells olsrd to select MPRs based on the link
252           quality information. A neighbor is selected as an MPR, if
253           it has the best route to any 2-hop neighbor. Suppose that
254           ETX1 is the expected number of transmissions between us and
255           a neighbor N and that ETX2 is the expected number of
256           transmissions between N and a two-hop neighbor N2. For each
257           of our two-hop neighbors we then select the neighbor N as
258           an MPR that results in the lowest possible total ETX of ETX1
259           + ETX2.
260         </P>
261       </LI>
262       <LI>
263         <P>
264           Setting this parameter to 2 not only selects MPRs based on
265           the link quality but also considers link quality information
266           when calculating the routing table. For a given destination
267           node D we select the route that has the minimal total ETX of
268           ETX1 + ETX2 + ... + ETXn, where ETX1 is the expected number
269           of transmissions from us to our neighbor, ETX2 is the
270           expected number of transmissions from our neighbor to the
271           next node, and ETXn is the expected number of transmissions
272           from our destination's neighbor to the destination. This is
273           the recommended setting.
274         </P>
275       </LI>
276     </UL>
277
278     <P>
279       <B>IMPORTANT:</B> Remember to set <EM>all</EM> nodes of your
280       MANET to the same link quality level. Even if levels 2 and 3 use
281       the same kind of messages, i.e. LQ HELLOs and LQ TCs, they use a
282       different algorithm for calculating the routing table. This can
283       also mess up your routing!
284     </P>
285
286     <P>
287       The second configuration parameter related to link quality is
288       <EM>LinkQualityWinSize</EM>. When determining the packet loss of
289       the packets received from a neighbor, olsrd only looks at the
290       <EM>n</EM> most recent packets. By default <EM>n</EM> is set to
291       10, so olsrd looks at the ten most recent packets received (or
292       not received) from a neighbor and then determines the packet
293       loss. Let's assume that of the 10 packets we have received 7,
294       then we have missed 3, which corresponds to a packet loss of
295       3/10 = 0.3 = 30%. The corresponding Link Quality is 7/10 = 0.7 =
296       70%.
297     </P>
298
299     <P>
300       Let's have a look at what the default value means. Let's for the
301       moment only think of LQ HELLO messages and neglect other message
302       types. By default LQ HELLOs are sent every 2 seconds. So, we
303       calculate the packet loss over the past 20 seconds. So, changes
304       in the link quality are accounted for relatively fast. For
305       longer intervals just increase this value.
306     </P>
307
308     <H4>Old Configuration Parameters</H4>
309
310     <P>
311       The link quality extensions do not work very well with
312       hysteresis. Hysteresis basically acts as a sort of barrier that
313       only links that are "good enough" can cross. If a link is too
314       flaky, hysteresis will make olsrd consider the link as
315       non-existent. So, this is a binary thing. Either a link is able
316       to cross the barrier, or it is not. There's nothing in
317       between. However, we want olsrd to consider <EM>every</EM> link
318       there is, without any barrier, because then we can leave it to
319       the link quality extensions to judge how good the link actually
320       is and how much we trust the link.
321     </P>
322
323     <P>
324       If a link with an ETX value of 50 is the only way of
325       reaching a node, then we want to use this link, as there is no
326       better way.
327     </P>
328
329     <P>
330       In addition, in contrast to only saying "good enough" or "not
331       good enough" like hysteresis, the link quality extensions offer
332       a much more detailed view of the world by saying something like
333       "75% good enough, 25% not good enough".
334     </P>
335
336     <P>
337       The second mechanism that could interfere with the link quality
338       extensions is the link detection scheme. By default, if olsrd
339       misses three (LQ) HELLO messages in a row from a neighbor, the
340       link is considered broken. However, we'd prefer the link to just
341       expose a lower quality. So, setting the HELLO validity time to
342       the HELLO interval multiplied by the link quality window size is
343       probably a good rule of thumb. In this way the link will be
344       removed not before the link quality extensions have had enough
345       time to gradually reduce the link quality to zero.
346     </P>
347
348     <H4>Sample Configuration</H4>
349
350     <P>
351       A minimal configuration that leaves everything at the default
352       and just makes the changes required for the link quality
353       extension to work properly could look as follows. Note the
354       <EM>ClearScreen</EM> directive that causes the screen to be
355       cleared before updated debug information is printed. This makes
356       the debug output more readable in many cases.
357     </P>
358
359     <PRE>
360 DebugLevel              2
361 ClearScreen             yes
362 LinkQualityLevel        2
363 LinkQualityWinSize      10
364 UseHysteresis           no
365
366 Interface "if03"
367 {
368   HelloInterval         2.0
369   HelloValidityTime     20.0
370 }
371     </PRE>
372
373     <H3>Debug Output</H3>
374     
375     <P>
376       0.4.8 also introduces significant changes in the debug
377       output. Let's have a look at what happens at debug level 2, which
378       is the recommended default for the link quality extensions.
379     </P>
380
381     <PRE>
382 --- 14:28:56.80 ---------------------------------------------------- LINKS
383
384 IP address       hyst   LQ     lost   total  NLQ    ETX
385 192.168.0.1      0.000  1.000  0      10     1.000  1.00
386     </PRE>
387
388     <P>
389       This table contains the links to our neighbors. It contains the
390       following columns.
391     </P>
392
393     <UL>
394       <LI>
395         <P>
396           <EM>IP address</EM> - the IP address of the interface via
397           which we have contact to the neighbor.
398         </P>
399       </LI>
400       <LI>
401         <P>
402           <EM>hyst</EM> - the current hysteresis value for this link.
403         </P>
404       </LI>
405       <LI>
406         <P>
407           <EM>LQ</EM> - the quality of the link determined at our
408           end. This is what we have previously called the Link
409           Quality.
410         </P>
411       </LI>
412       <LI>
413         <P>
414           <EM>lost</EM> - the number of lost packets among the
415           <EM>n</EM> packets most recently sent by our neighbor via
416           this link. <EM>n</EM> is the link quality window size.
417         </P>
418       </LI>
419       <LI>
420         <P>
421           <EM>total</EM> - the total number of packets received up to
422           now. This value starts at 0 immediately after a link has
423           come to life and then counts each packet. It is capped at
424           the link quality window size.
425         </P>
426       </LI>
427       <LI>
428         <P>
429           <EM>NLQ</EM> - this is our neighbor's view of the link
430           quality. Previously we have called this the Neighbor Link
431           Quality. This value is extracted from LQ HELLO messages
432           received from our neighbors. NB: If a neighbor stops
433           sending packets completely, we do not have any means of
434           updating this value. However, in this case the LQ value will
435           decrease and the link thus be detected as becoming worse.
436         </P>
437       </LI>
438       <LI>
439         <P>
440           <EM>ETX</EM> - this is the ETX for this link, i.e. 1 / (NLQ
441           x LQ).
442         </P>
443       </LI>
444     </UL>
445
446     <PRE>
447 --- 14:28:56.80 ------------------------------------------------ NEIGHBORS
448
449 IP address       LQ     NLQ    SYM   MPR   MPRS  will
450 10.0.0.6         1.000  1.000  YES   YES   NO    6
451     </PRE>
452
453     <P>
454       This table contains a list of all our neighbors. It is closely
455       related to the link table in that we are connected to a
456       neighbor via one or more links. The table has the following
457       columns.
458     </P>
459       
460     <UL>
461       <LI>
462         <P>
463           <EM>IP address</EM> - the main IP address of the neighbor.
464         </P>
465       </LI>
466       <LI>
467         <P>
468           <EM>LQ</EM> and <EM>NLQ</EM> - the LQ and NLQ values of the
469           best link that we have with this neighbor. (In
470           multi-interface configurations we can have more than one
471           link with a neighbor.)
472         </P>
473       </LI>
474       <LI>
475         <P>
476           <EM>SYM</EM> - this states whether the link to this
477           neighbor is considered symmetric by olsrd's link detection
478           mechanism.
479         </P>
480       </LI>
481       <LI>
482         <P>
483           <EM>MPR</EM> (multi-point relay) - this indicates whether we
484           have selected this neighbor to act as an MPR for us.
485         </P>
486       </LI>
487       <LI>
488         <P>
489           <EM>MPRS</EM> (multi-point relay selector) - this indicates
490           whether the neighbor node has selected us to act as an MPR
491           for it.
492         </P>
493       </LI>
494       <LI>
495         <P>
496           <EM>will</EM> - the neighbor's willingness.
497         </P>
498       </LI>
499     </UL>
500
501     <PRE>
502 --- 14:28:56.80 ------------------------------------------------- TOPOLOGY
503
504 Source IP addr   Dest IP addr     LQ     ILQ    ETX
505 10.0.0.6         192.168.0.2      1.000  1.000  1.00
506 10.0.0.6         10.0.0.5         1.000  1.000  1.00
507     </PRE>
508
509     <P>
510       This table displays the topology information that olsrd has
511       gathered from LQ TC messages. It states which nodes in the
512       network report links to which other nodes and which quality
513       these links have. So, it's olsrd's view of the world beyond its
514       immediate neighbor nodes, i.e. its view of the nodes that it
515       cannot reach directly. This table has the following columns.
516     </P>
517
518     <UL>
519       <LI>
520         <P>
521           <EM>Source IP addr</EM> - the node that reports a link.
522         </P>
523       </LI>
524       <LI>
525         <P>
526           <EM>Dest IP addr</EM> - the node to which the source node
527           reports the link.
528         </P>
529       </LI>
530       <LI>
531         <P>
532           <EM>LQ</EM> (link quality) - the quality of the link as
533           determined by the source node. For the source node this is
534           the Link Quality. For the destination node this is the
535           Neighbor Link Quality.
536         </P>
537       </LI>
538       <LI>
539         <P>
540           <EM>ILQ</EM> (inverse link quality) - the quality of the
541           link as determined by the destination node. For the source
542           node this is the Neighbor Link Quality. For the destination
543           node this is the Link Quality. We just did not want to name
544           it "NLQ", as we use NLQ only for the link quality reported
545           by our neighbors. But functionally this is equivalent to
546           the NLQ we know from the link and neighbor tables.
547         </P>
548       </LI>
549       <LI>
550         <P>
551           <EM>ETX</EM> - the ETX value for this link, calculated by
552           ETX = 1 / (ILQ x LQ).
553         </P>
554       </LI>
555     </UL>
556
557     <PRE>
558 --- 14:28:56.80 ------------------------------------------------- DIJKSTRA
559
560 10.0.0.6:1.00 (one-hop)
561 10.0.0.5:2.00 <- 10.0.0.6:1.00 (one-hop)
562     </PRE>
563
564     <P>
565       This table displays the best routes that olsrd could find for
566       each destination that it knows about. The leftmost IP address
567       given on each line is the destination of a route. The remaining
568       IP addresses in a line specify the nodes on the route between
569       ourselves and the destination address. Moving from the
570       destination address to the right, address by address, moves us
571       closer from the destination to ourselves, hop by hop.
572     </P>
573
574     <P>
575       In the above case we see routes to two nodes, 10.0.0.6 and
576       10.0.0.5. In the first line, there aren't any intermediate nodes
577       between us and the destination, the destination address is the
578       only IP address in this line. In the second line we have one
579       intermediate node, 10.0.0.6. So, the second line describes a
580       route to 10.0.0.5 via 10.0.0.6.
581     </P>
582
583     <P>
584       The number after the colon following an IP address in the table
585       is the total ETX of the route up to this IP address, i.e. the
586       sum of the ETX values of all hops between ourselves and this IP
587       address.
588     </P>
589
590     <P>
591       In the above example the first line represents a path with an
592       ETX value of 1.00 to 10.0.0.6. As we've seen in the neighbor
593       table above 10.0.0.6 is our neighbor, so the route to it
594       consists only of a single hop, which has an ETX of 1.00, hence
595       the 1.00 in this line.
596     </P>
597
598     <P>
599       In the second line, 10.0.0.5 is not a neighbor of ours. However,
600       10.0.0.6 is and from the topology table above we can tell that
601       10.0.0.6 reports a link to 10.0.0.5. So, we can reach 10.0.0.5
602       via 10.0.0.6. This is what this line says. Remember that each
603       line represents a route by first giving the IP address of the
604       destination (10.0.0.5) and that moving to the right means moving
605       towards ourselves until one of our (one-hop) neighbor is
606       reached. If we move from 10.0.0.5 to the right, we find
607       10.0.0.6, which is our (one-hop) neighbor. So we have a route.
608     </P>
609     
610     <P>
611       If we would like to know which path a packet takes that we send
612       to 10.0.0.5, we have to read the line backwards. We then see
613       that the packet first travels to our (one-hop) neighbor 10.0.0.6
614       via a link that has an ETX of 1.00 (which we can confirm by
615       looking at the neighbor table above). From there it is forwarded
616       to 10.0.0.5 via another link that also has an ETX of 1.00 (which
617       we can confirm by means of the topology table above), resulting
618       in a total ETX of 1.00 + 1.00 = 2.00, which is the number that
619       follows 10.0.0.5. Remember that the ETX value given for an IP
620       address is the cumulative ETX for the complete route up to this
621       IP address.
622     </P>
623
624     <P>
625       If olsrd is able to find a route between us and the destination,
626       the last IP address in the line is one of our neighbors. In this
627       case, "(one-hop)" is appended to the line to illustrate that the
628       last IP address is one of our (one-hop) neighbors. However,
629       let's assume that we've just switched on olsrd. In this case, it
630       does not know about all links in the network, yet, as it hasn't
631       received LQ TC messages from all nodes. So, it may know that a
632       node exists (as it has already received LQ TC messages from it)
633       but it does not necessarily know how to reach it (as it may not
634       have received LQ TC messages from nodes between it and
635       ourselves, yet). In this case the last IP address is the last
636       node that is reachable from the destination and the line ends
637       with the word "FAILED".
638     </P>
639
640     <P>
641       The same is true for neighbors to which we do not have a
642       symmetric link. We know that they're there, but we do not have a
643       link to them, hence olsrd cannot find a route, which results in
644       "FAILED".
645     </P>
646
647     <H3>Remarks</H3>
648
649     <P>
650       If you have any questions on using olsrd or if you would like to
651       know more about the link quality extension, it's probably best
652       to subscribe to the mailing lists and ask your question
653       there. Information on the mailing lists is available at
654       <A HREF="http://www.olsr.org">http://www.olsr.org</A>.
655     </P>
656
657   </BODY>
658 </HTML>