Rename 'struct interface' to 'struct interface_olsr'
[olsrd.git] / README-Olsr-Extensions
1 =====================================================
2       OLSRd (version 0.6.0) protocol extensions
3 =====================================================
4
5 1.) Credits
6 2.) Link quality algorithms
7 3.) Fisheye
8 4.) NIIT (ipv4 over ipv6 traffic)
9 5.) Smart gateways (asymmetric gateway tunnels)
10 6.) NatThreshold
11
12 NIIT and Smart gateways are only supported for Linux at the moment.
13
14     1.) Credits:
15 ********************
16
17 The concept of ETX (Expected Transmission Count) has been developed by
18 Douglas S. J. De Couto at the Massachusetts Institute of Technology
19 (see http://en.wikipedia.org/wiki/Expected_Transmission_Count).
20
21 The original ETX design has been done by the Berlin Freifunk Network
22 (see www.freifunk.net and www.c-base.org), the code and message format
23 was coded by Thomas Lopatic.
24
25 Fisheye was implemented by Thomas Lopatic in 2005.
26
27 The LQ-Plugin rewrite was done by Henning Rogge in 2008.
28
29 The NIIT kernel module was written by lynxis in 2009.
30
31 The asymmetric gateway tunnel functionality was written by Markus Kittenberger
32 and Henning Rogge, but the concept was used by B.A.T.M.A.N before OLSRd.
33
34
35
36     2.) Link quality algorithm
37 **********************************
38
39 Concept:
40 --------
41
42 OLSRd (since version 0.5.6) uses a dimension-less integer value as a
43 representation of the 'cost' of each link. This is often called Link Quality
44 (LQ for short). There are multiple LQ plugins, each of them calculating a cost
45 for the links of the router. At the moment (version 0.6.0) all LQ plugins are
46 using an ETX-metric (Expected Transmission Count) but other metrics would be
47 possible and imaginable, such as MIC [0], etc.
48
49
50 Each link is described by an LQ/NLQ (Link Quality/Neighbor Link Quality) value
51 pair, which describe the quality towards the router (LQ) and towards the
52 neighbor (NLQ). Both LQ and NLQ can be values between 0 and 1. The total cost
53 of the link is calculated as ETX = 1.0/(LQ * NLQ). The ETX value of a link can
54 be seen as the number of retransmissions necessary to deliver the packet to the
55 target. ETX 1.0 mean a perfect link without packet loss.
56
57        A                  B
58      +---+              +---+
59      |   |  <--- LQ --- |   |
60      |   |  ---- NLQ -->|   |
61      +---+              +---+
62
63 Note that the LQ and NLQ are always as seen from one nodes' perspective: the LQ
64 of node B towards A is the percentage of packets that B can transmit to A.
65 Hence, in the OLSR ETX implementation, B has to tell A it's LQ.
66
67 OLSRd chooses the path towards a target by selecting the path segments with the
68 smallest sum of link costs. In other words:
69
70    best_path(A,B) = minimum_sum({set of all paths between A and B})
71
72
73 Configuration:
74 --------------
75
76 The link quality system is activated by setting the configuration variable
77 "LinkQualityLevel" to 2.
78
79 You can use the "LinkQualityAlgorithm" parameter to choose the current
80 link quality algorithm in the configuration file. Some embedded OLSRd versions
81 are only compiled with one plugin (mostly etx_ff), so don't use the
82 configuration option with these agents.
83
84 There are four different link quality algorithms in OLSRd 0.6.0, two
85 current Funkfeuer/Freifunk ETX implementations and two legacy implementations.
86
87 LinkQuality-Algorithm "etx_ff":
88 -------------------------------
89
90 "Etx_ff" (ETX Funkfeuer/Freifunk) is the current default LQ algorithm for OLSRd.
91 It uses the sequence number of the OLSR packets (which are link specific)
92 to determine the current packet loss rate. Etx_ff includes a hysteresis
93 mechanism to suppress small fluctuations of the LQ and NLQ values. If
94 no packets are received from a certain neighbor at all, a timer begins
95 to lower the calculated LQ value until the next packet is received or
96 the link is dropped.
97 Etx_ff uses only integer arithmetic, so it performs well on embedded
98 hardware having no FPU.
99
100 The message format of etx_ff is compatible with etx_fpm and etx_float.
101
102
103 LinkQuality-Algorithm "etx_ffeth"
104 --------------------------------
105
106 "Etx_ffeth" is an experimental and INCOMPATIBLE extension of etx_ff (meaning it
107 is not interoperable with etx_ff nodes).  The problem with etx_ff, etx_float
108 and etx_fpm is that they calculate Ethernet links with the same cost as a
109 wireless link without packet loss (ETX=1.0) because the encoding of etx_ff
110 cannot encode link costs lower than 1.0. This means OLSRd prefers a single
111 wireless link with some loss (e.g. ETX=1.5) over a two hop route with one
112 Ethernet link (ETX=1.0) and one perfect wireless link (ETX=1.0) *even though*
113 the 2 hop path would be better!
114
115 "Etx_ffeth" tries to work around this problem by introducing a special
116 LQ encoding value ETX=0.1, which is only used for Ethernet
117 links without packet loss. Because of the different encoding, etx_ffeth
118 is not compatible with etx_ff, etx_fpm or etx_float. These three
119 implementations detect etx_ffeth nodes with LQ 0 (ETX infinite).
120
121 etx_ffeth uses only integer arithmetic, so it performs well on embedded
122 hardware.
123
124 All Ethernet interfaces must be marked with "mode ether"
125 (see olsrd.conf.default.full) in their interface configuration to get any
126 useful advantage of etxff_eth.
127
128 At the time of this writing, etx_ffeth is the preferred metric for building new
129 mesh networks which include links over LAN cables (such as daisy chained
130 Linksys routers).
131
132
133 Legacy LinkQuality-Algorithm "etx_float"
134 ----------------------------------------
135
136 "Etx_float" calculates the ETX value by using exponential aging (with
137 a configurable aging parameter) on the incoming (or lost) Hellos.
138 It is easier to understand than etx_ff, but the results are not as
139 good as with etx_ff, since it cannot use the TC messages for link
140 quality calculation.
141 Etx_float uses floating point math, so it might use more CPU on embedded
142 hardware.
143
144 The message format of etx_float is compatible with etx_fpm and etx_ff.
145
146
147 Legacy LinkQuality-Algorithm "etx_fpm"
148 --------------------------------------
149
150 "Etx_fpm" is a fixed point math implementation of etx_float. It
151 calculates the same link qualities as etx_float, but is much faster
152 on embedded hardware.
153
154 The message format of etx_fpm is compatible with etx_float and etx_ff.
155
156
157 Building your own LinkQuality Algorithm
158 ----------------------------------------
159
160 With the supplied samples OLSRd can be easily extended to support different
161 metrics. Please take a look at src/lq_plugin*.[ch] for inspiration and get in
162 contact with us on the OLSR development mailing list in case you plan to
163 implement a new metric.
164
165
166
167     3.) Fisheye
168 *******************
169
170 Normally OLSR floods all topology control (TC) messages to all
171 routes in the mesh, which can create a lot of overhead for large
172 meshes with hundreds of routers. Reducing the rate of TCs can reduce
173 this overhead, but delay route changes and correction of errors
174 in the routing tables.
175
176 The Fisheye (sometimes called Hazy Sighted Link State Routing [1])
177 mechanism implements a strategy to reach a compromise between
178 these two problems. When activated only every 8th TC is send
179 to all mesh nodes. Most TCs are given a reduced TTL (time to live)
180 and are only transmitted to the neighborhood of the router.
181
182 The current sequence of TTLs with active Fisheye mechanism is
183 2, 8, 2, 16, 2, 8, 2 and 255 (maximum TTL).
184
185 The problem with Fisheye is that it introduces artificial borders
186 for flooding TCs, which can theoretically lead to inconsistent routes
187 and routing loops at the border of the Fisheye circles. In practice
188 Fisheye seems to work well enough that it is a mandatory feature
189 for most larger Funkfeuer/Freifunk meshes.
190
191
192     4.) NIIT (ipv4 over ipv6 traffic)
193 *****************************************
194 (see https://dev.dd19.de/cgi-bin/gitweb.cgi?p=niit.git;a=summary)
195
196 NIIT is a special Linux kernel device that allows easy transmission of IPv4
197 unicast traffic through an IPv6 network. Since version 0.6.0 OLSRd has
198 integrated support for NIIT in the routing daemon. So setting up IPv4 traffic
199 over IPv6 OLSR meshes is very easy. Instead of creating routes and tunnels by
200 hand all the administrator of a router needs to do is to, is to set up his own
201 IPv4 targets as "IPv4-mapped" IPv6 HNAs.
202
203 Example configurations:
204 - connect a local 192.168.1.0/8 net to the mesh
205
206 HNA6 {
207   0::ffff:C0A8:01:00 120
208 }
209
210 - announce an IPv4 Internet gateway
211
212 HNA6 {
213   0::ffff:0:0 96
214 }
215
216
217 More information on NIIT can be found at: http://wiki.freifunk.net/Niit
218 (German)
219
220
221     5.) Smart gateways (asymmetric gateway tunnels)
222 *******************************************************
223
224     5.1) Introduction
225
226 The smart gateway mechanism was written by Markus Kittenberger and
227 Henning Rogge to allow an OLSR user to directly choose their default
228 Internet gateway instead of relying on the hop by hop decisions on
229 the way to the gateway. OLSRd 0.6.0 can create an IPIP tunnel
230 to the gateway's OLSRd address to side-step the same nasty effects
231 described in the NAT-Threshold section.
232
233 The smart gateway code can be split into two sections, one is
234 responsible for announcing the existence of a smart gateway uplink
235 and one (on the client nodes) to choose an uplink and create the
236 tunnel to the gateway. The announcing code uses a modified (but
237 backward compatible) special HNA to signal the gateways to the
238 clients. The clients can use a plugin (or the integrated default
239 code) to choose one of the available gateways and change it if
240 necessary.
241
242 The smart gateway system is setup by several configuration parameters,
243 most of them with a sane default setting. The whole system can be
244 switched on/off by the following parameter:
245
246 SmartGateway <yes/no>
247
248 All other parameters will be ignored if SmartGateway is set to "no"
249 (the default is "no").
250
251
252     5.2) Client Side
253
254 1- SmartGatewayUseCount controls the maximum number of gateways that can be
255    in use at any given time. A setting higher than 1 is used to mitigate the
256    effects of breaking connections (due to the selection of a new gateway) on
257    a dynamic network.
258    The default setting is 1.
259 2- SmartGatewayTakeDownPercentage determines the take-down percentage for a
260    non-current smart gateway tunnel. If the cost of the current smart gateway
261    tunnel is less than this percentage of the cost of the non-current smart
262    gateway tunnel, then the non-current smart gateway tunnel is taken down
263    because it is then presumed to be 'too expensive'.
264    This setting is only relevant when SmartGatewayUseCount is larger than 1;
265    a value of 0 will result in the tunnels not being taken down proactively,
266    only when a new tunnel is created while then are already
267    'SmartGatewayUseCount' tunnels.
268    The default setting is 0.
269 3- SmartGatewayPolicyRoutingScript controls the policy routing script that is
270    executed during startup and shutdown of olsrd. The script is only executed
271    when SmartGatewayUseCount is set to a value larger than 1. The script must
272    setup policy routing rules such that multi-gateway mode works. A reference
273    script is included.
274    The default setting is <not set>.
275 4- SmartGatewayEgressInterfaces determines the egress interfaces that are part
276    of the multi-gateway setup and therefore only relevant when
277    SmartGatewayUseCount is larger than 1 (in which case it must be explicitly
278    set). This setting can contain multiple interfaces, for example
279      SmartGatewayEgressInterfaces "eth0" "eth1" "ppp0"
280    The default setting is <not set>.
281 5- SmartGatewayTablesOffset and SmartGatewayRulesOffset determine the ranges of
282    policy routing rule markings that are used in a multi-gateway setup (see the
283    policy routing script for an explanation).
284    The default settings are 90 and 0 respectively. The value of 0 for
285    SmartGatewayRulesOffset will automatically align the table and rule numbers
286    for the server tunnel, egress interfaces and gateway tunnel interfaces.
287 6- SmartGatewayAllowNAT controls whether you want to allow the selection
288    of an outgoing ipv4 gateway with NAT (Network Address Translation).
289    The default setting is "yes".
290 7- SmartGatewayPeriod determines the period (in milliseconds) on which
291    a new smart gateway selection is performed.
292    The default setting is 10000 milliseconds.
293 8- SmartGatewayStableCount determines the number of times the same new gateway
294    must be chosen before that new smart gateway is actually selected.
295    The default setting is 6.
296 9- SmartGatewayThreshold (percentage) controls whether you want to allow
297    re-selection of a new outgoing gateway if its routing cost is lower or equal
298    to the configured percentage of the routing cost of the current gateway.
299    The default setting is 0, which disables it.
300 10-SmartGatewayWeightExitLinkUp, SmartGatewayWeightExitLinkDown,
301    SmartGatewayWeightEtx and SmartGatewayDividerEtx control the weighing
302    of gateway bandwidth and ETX costs.
303
304    If SmartGatewayDividerEtx is zero then no weighing is performed (classical
305    behaviour). Classical behaviour only takes ETX costs into account when
306    choosing a gateway (select the 'nearest' gateway).
307
308    The weighing also takes the gateway bandwidths into account (select the
309    'nearest fat pipe' gateway).
310
311    Gateways that have zero bandwidth for either their uplink or downlink are
312    ignored.
313
314    * The Weighing Process
315    ======================
316
317      ** Configuration Parameters
318      ===========================
319      SmartGatewayWeightExitLinkUp   = gateway exit link uplink weight
320      SmartGatewayWeightExitLinkDown = gateway exit link downlink weight
321      SmartGatewayWeightEtx          = ETX path cost weight
322      SmartGatewayDividerEtx         = ETX path cost divider
323
324      ** Gateway Parameters
325      ===========================
326      gw->uplink   (Mbps)            = gateway exit link uplink  , in Mbps
327      gw->downlink (Mbps)            = gateway exit link downlink, in Mbps
328
329      ** Weighing Formula
330      ===================
331                           SmartGatewayWeightExitLinkUp
332      path_cost_weighed =  ---------------------------- +
333                                 gw->uplink (Mbps)
334
335                           SmartGatewayWeightExitLinkDown
336                           ------------------------------ +
337                                 gw->downlink (Mbps)
338
339                            SmartGatewayWeightEtx
340                           ---------------------- * path_cost
341                           SmartGatewayDividerEtx
342
343      ** Recommended Configuration Parameter Settings
344      ===============================================
345      (assuming LinkQualityAlgorithm "etx_ffeth")
346
347      SmartGatewayWeightExitLinkUp   = 1    (default is 1)
348      SmartGatewayWeightExitLinkDown = 1    (default is 1)
349      SmartGatewayWeightEtx          = 1    (default is 1)
350      SmartGatewayDividerEtx         = 4096 (default is 0)
351
352
353     5.3) Uplink Side
354
355 1- SmartGatewayUplink defines which kind of uplink is exported to the
356    other mesh nodes. The existence of the uplink is detected by looking
357    for a local HNA of 0.0.0.0/0, ::ffff:0:0/96 or 2000::/3. The default
358    setting is "both".
359 2- SmartGatewayUplinkNAT defines if the ipv4 part of the uplink uses NAT.
360    The default of this setting is "yes".
361 3- SmartGatewaySpeed sets the uplink and downlink speed of the gateway,
362    which could be used by a plugin to choose the right gateway for a
363    client. The default is 128/1024 kbit/s.
364 4- SmartGatewayPrefix can be used to signal the external IPv6 prefix of
365    the uplink to the clients. This might allow a client to change it's
366    local IPv6 address to use the IPv6 gateway without any kind of address
367    translation. The maximum prefix length is 64 bits,
368    the default is ::/0 (no prefix).
369 5- SmartGatewayAlwaysRemoveServerTunnel can be used to signal that the
370    server tunnel must always be removed on shutdown, irrespective of the
371    interface up/down state during startup.
372
373
374     5.4) Architecture & Notes
375
376 On the smart gateway server (the OLSR instance announcing 'Internet here!' via
377 HNA 0/0 or similar) the implicit tunl0 interface is used to forward incoming
378 packets originating on smart gateway clients to the Internet route. This may be
379 protected by the sysctl rp_filter setting. Note, that at least with RedHat
380 kernel 2.6.18, the net.ipv4.conf.tunl0.rp_filter sysctl file is not present
381 after loading the "ipip" kernel module, which prevents OLSRd from switching off
382 the filter. As a workaround, add an "ip addr add 0.0.0.0/32 dev tunl0" after
383 the "modprobe ipip" line in your OLSRd startup script.
384
385 While the smart gateway function does a fine job on stand-alone PCs, system
386 builders should keep in mind the following facts when setting up routing,
387 firewalls and gateways:
388
389 a) The smart gateway tunnel communicates asymmetrically. An IP packet destined
390    for an Internet server is sent via the IPIP tunnel but returned via the
391    standard OLSRd host route.
392
393 b) On the smart gateway server, you should double check your firewall rules and
394    rp_filter defaults. While it's normally not possible to simply encapsulate
395    (for example) a "telnet 127.0.0.1" into IPIP and sent that to the smart
396    gateway server, your specific configuration may open up such attack vectors
397    for an intruder.
398
399 c) Do not forget to open up the firewall for tunl0->Internet traffic and (if
400    required to NAT/MASQUERADE) this communication path.
401
402 d) While the smart gateway server does not use special routing, the smart
403    gateway client inserts policy routing rules for it's function. By using the
404    default configuration, the OLSRd standard default route is maintained in
405    table 223 and the OLSRd smart gateway default route in table 224. Both
406    tables are examined only, if you do not have a default route in the main
407    table (visible with "ip route ls"). Use "ip route ls table 223" or
408    "ip route ls table 224" for debugging/monitoring. You may also activate the
409    txtinfo plugin and do a "wget -O - http://localhost:2006/gateway".
410
411 e) For a standalone client (a notebook user running OLSRd in order to browse)
412    the lowered IPIP tunnel MTU is no problem. If you do proxy routing, e.g. for
413    attached LAN clients without OLSRd, you may want MSS-clamping for the tunnel
414    interface created by OLSRd. Because OLSRd uses an arbitrary name for the
415    tunnel interface (e.g. tnl_7c41c668) you may want to include a wildcard
416    iptables rule. Example:
417      iptables -A FORWARD -o tnl_+ -p tcp --tcp-flags SYN,RST SYN \
418               -j TCPMSS --clamp-mss-to-pmtu
419
420 Furthermore (or alternatively) you might consider (on your gateway nodes)
421 clamping all traffic leaving your mesh to your ipip mtu (regardless if the
422 traffic comes out of the smart gateway tunnel or not!). Example:
423   iptables -A FORWARD -o [your_gateway_interface] -p tcp \
424            --tcp-flags SYN,RST SYN -j TCPMSS --set-mss 1480
425
426 Especially as during OLSRd startup, before an smart gateway is chosen (which is
427 delayed), new connections would use a larger MSS than the smart gateway tunnel
428 can handle. So the approach to clamp on the gateways should give better results.
429
430 But if you don't NAT on your gateways (but want to use smart gateway for some
431 special reason), you would have to do this on ALL gateways (even on gateways
432 that do not provide the smart gateway functionality!).
433
434
435     6.) NatThreshold
436 ************************
437
438 The NatThreshold option was introduced by Sven Ola to suppress a very annoying
439 problem with OLSRd, switching default gateways. If a router is located between
440 two Internet gateways with similar path costs the default route (0.0.0.0/0)
441 will constantly switch between the two gateways due to normal fluctuations of
442 the link metrics. Whenever OLSRd decides that the other NAT gateway is
443 "better", then switching to this new gateway will result in termination of all
444 connected sessions (TCP and HTTP).
445 The user experience will be rather painful and users will experience hanging
446 SSH and HTTP sessions (or anything using TCP).
447
448 NatThreshold tries to help by introducing a hysteresis factor for
449 choosing the route to the default gateway. Only if the new gateway has
450 a lower cost than the current gateways path cost multiplied by
451 NatThreshold the node will switch the gateway.
452 In short:
453
454   if (cost(new_gateway) < cost(current_gw)*NatThreshold)) {
455         switch_gateway();
456   }
457
458
459 Practical experience shows that this leads to much better quality of default
460 gateway selection, even if (in theory) a small NatThreshold together with
461 Fisheye can lead to  persistent routing loops.
462 Please note that even with NatThreshold enabled, some users will still
463 experience gateway switching. However, most users will not.
464
465 Smart Gateways can replace NatThreshold all together because they allow sending
466 traffic directly to a gateway circumventing the problems described above which
467 stem from a hop-by-hop routing approach
468
469
470
471      7.) References
472 ************************
473 [0] MIC Metric: "Designing Routing Metrics for Mesh Networks",
474         Yaling Yang, Jun Wang, Robin Kravets
475         http://www.cs.ucdavis.edu/~prasant/WIMESH/p6.pdf
476
477 [1] "Making link-state routing scale for ad hoc networks",
478         Cesar A. Santivanez, Ram Ramanathan, Ioannis Stavrakakis
479         http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.5940