010854938131c2e07e5be1a7351296c7c338705d
[olsrd.git] / README-Olsr-Extensions
1 =======================================================
2       OLSRd (version 0.5.7.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 tunnels was written by Markus Kittenberg
32 and Henning Rogge, but were used by BATMAN before OLSRd.
33
34
35     2.) Link quality algorithm
36 **********************************
37
38 Concept:
39 --------
40
41 OLSRd (since version 0.5.6) use a dimensionless integer value for a
42 representation of the 'cost' of each link. There are multiple LQ-Plugins,
43 each of them calculating a cost for the links of the router. At the moment
44 (version 0.5.7.0) all lq_plugins are using an ETX-metric (expected
45 transmission count).
46
47 Each link is described by a LQ (link quality) and a NLQ (neighbor link
48 quality) value, which describe the quality towards the router (LQ) and
49 towards the neighbor (NLQ). Both LQ and NLQ can be a value between 0 and 1.
50 The total cost of the link is calculated as ETX - 1.0/(LQ * NLQ). The
51 ETX value of a link could be considered as the number of retransmissions
52 necessary to deliver the packet to the target. ETX 1.0 mean a perfect
53 link without packet loss.
54
55 OLSRd chooses the route towards a target by using the path with the
56 smallest sum of link costs.
57
58 Configuration:
59 --------------
60
61 The link quality system is activated by setting the config variable
62 "LinkQualityLevel" to 2.
63
64 You can use the "LinkQualityAlgorithm" parameter to choose the current
65 link quality algorithm in the config file. Some embedded OLSRd versions
66 are only compiled with one plugin (mostly etx_ff), so don't use the
67 configuration option with this agents.
68
69 There are four different link quality algorithms in OLSRd 0.5.7.0, two
70 current Freifunk ETX implementations and two legacy implementations.
71
72 LinkQuality-Algorithm "etx_ff":
73 -------------------------------
74
75 "Etx_ff" (etx freifunk) is the current default lq algorithm for OLSRd.
76 It uses the sequence number of the OLSR packages (which are link specific)
77 to determine the current loss rate. Etx_ff includes a hysteresis
78 mechanism to suppress small fluctuations of the LQ and NLQ value. If
79 no packages are received from a certain neighbor at all, a timer begins
80 to lower the calculated LQ value until the next package is received or
81 the link is dropped.
82 Etx_ff only uses integer arithmetic, so it performs well on embedded
83 hardware having no FPU.
84
85 The message format of etx_ff is compatible with etx_fpm and etx_float.
86
87 LinkQuality-Algorithm "etx_ffeth"
88 --------------------------------
89
90 "Etx_ffeth" is an experimental and INCOMPATIBLE extension of etx_ff.
91 The problem with etx_ff, etx_float and etx_fpm is that they calculate
92 ethernet links with the same cost as a wireless link without packet loss
93 (ETX 1.0) because the encoding of etx_ff cannot encode link costs
94 lower than 1.0. This means OLSRd prefers a single wireless link with
95 some loss (e.g. ETX 1.5) over a two hop route with one ethernet link
96 (ETX 1.0) and one perfect wireless link (ETX 1.0).
97
98 "Etx_ffeth" tries to work around this problem by introducing a special
99 LQ encoding for the value ETX 0.1, which is only used for ethernet
100 links without packet loss. Because of the different encoding etx_ffeth
101 is not compatible with etx_ff, etx_fpm or etx_float. These three
102 implementations detect etx_ffeth nodes with LQ 0 (ETX infinite).
103
104 etx_ffeth only use integer arithmetic, so it performs well on embedded
105 hardware.
106
107 Legacy LinkQuality-Algorithm "etx_float"
108 ----------------------------------------
109
110 "Etx_float" calculates the ETX value by using exponential aging (with
111 a configurable aging parameter) on the incoming (or lost) Hellos.
112 It's easier to understand than etx_ff, but the results are not as
113 good as in etx_ff, because it cannot use the TC messages for link
114 quality calculation.
115 Etx_float uses floating point math, so it might use more CPU on embedded
116 hardware.
117
118 The message format of etx_float is compatible with etx_fpm and etx_ff.
119
120 Legacy LinkQuality-Algorithm "etx_fpm"
121 --------------------------------------
122
123 "Etx_fpm" is a fixed point math implementation of etx_float. It
124 calculates the same link qualities as etx_float, but is much faster
125 on embedded hardware.
126
127 The message format of etx_fpm is compatible with etx_float and etx_ff.
128
129
130     3.) Fisheye
131 *******************
132
133 Normally OLSR floods all topology control (TC) messages to all
134 routes in the mesh, which can create a lot of overhead for large
135 meshs with hundreds of routers. Reducing the rate of TCs can reduce
136 this overhead, but delay route changes and correction of errors
137 in the routing tables.
138
139 The Fisheye (sometimes called Hazy Sighted Link State Routing)
140 mechanism implements a strategy to reach a compromise between
141 this two problems. When activated only every 8th TC is send
142 to all mesh nodes. Most TCs are given a reduced TTL (time to live)
143 and are only transmitted to the neighborhood of the router.
144
145 The current sequence of TTLs with active fisheye mechanism is
146 2, 8, 2, 16, 2, 8, 2 and 255 (maximum TTL).
147
148 The problem with Fisheye is that it introduce artifical borders
149 for flooding TCs, which can theoretically lead to inconsistent routes
150 and routing loops at the border of the fisheye circles. In practice
151 fisheye seems to work well enough that it is a mandatory feature
152 for most larger Freifunk meshs.
153
154
155     4.) NIIT (ipv4 over ipv6 traffic)
156 *****************************************
157 (see https://dev.dd19.de/cgi-bin/gitweb.cgi?p=niit.git;a=summary)
158
159 NIIT is a special linux kernel device that allows easy transmission
160 of IPv4 unicast traffic through an IPv6 network. Since OLSRd 0.5.7.0
161 there is integrated support for NIIT in the routing daemon, so
162 setting up IPv4 traffic over IPv6 OLSR meshs is very easy. Instead
163 of creating routes and tunnels by hand all the administrator of a
164 router has to do is to set up his own IPv4 targets as "IPv4-mapped"
165 IPv6 HNAs.
166
167 Example configurations:
168 - connect a local 192.168.1.0/8 net to the mesh
169
170 HNA6 {
171   0::ffff:C0A8:01:00 120
172 }
173
174 - announce an IPv4 internet gateway
175
176 HNA6 {
177   0::ffff:0:0 96
178 }
179
180
181     5.) Smart gateways (asymmetric gateway tunnels)
182 *******************************************************
183
184 The smartgateway mechanism was written by Markus Kittenberg and
185 Henning Rogge to allow an OLSR user to directly choose their default
186 internet gateway instead of relying on the hop by hop decisions on
187 the way to the gateway. OLSRd 0.5.7.0 can create an IPIP tunnel
188 to the gateways OLSRd address to sidestep the same nasty effects
189 described in the Nat-Threshold section.
190
191 The smartgateway code can be split into two sections, one is
192 responsible for announcing the existence of a smartgateway uplink
193 and one on the client nodes to choose an uplink and create the
194 tunnel to the gateway. It use a modified (but backward compatible)
195 special HNA to signal the gateways to the clients. The clients can
196 use a plugin (or the integrated default code) to choose one of the
197 available gateways and change it if necessary. 
198
199 The smartgateway system is setup by several configuration parameters,
200 most of them with a sane default setting. The whole system can be
201 switched on/off by the following parameter:
202
203 SmartGateway <yes/no>
204
205 All other parameters will be ignored if SmartGateway is set to "no"
206 (the default is "yes").
207
208 On the client side there is a single additional parameter which
209 controls if you want to allow the selection of an outgoing ipv4
210 gateway with NAT (network address translation).
211
212 SmartGatewayAllowNAT <yes/no>
213
214 The uplink side of the smartgateway code has four parameters to
215 set up the type of the uplink.
216
217 SmartGatewayUplink defines which kind of uplink is exported to the
218 other mesh nodes. The existence of the uplink is detected by looking
219 for a local HNA of 0.0.0.0/0, ::ffff:0:0/96 or 2000::/3. The default
220 setting is "both".
221 SmartGatewayUplinkNAT defines if the ipv4 part of the uplink use NAT.
222 The default of this setting is "yes".
223 SmartGatewaySpeed sets the uplink and downlink speed of the gateway,
224 which could be used by a plugin to choose the right gateway for a
225 client. The default is 128/1024 kbit/s.
226 The final parameter SmartGatewayPrefix can be used to signal the
227 external IPv6 prefix of the uplink to the clients. This might allow
228 a client to change it's local IPv6 address to use the IPv6 gateway
229 without any kind of address translation. The maximum prefix length
230 is 64 bits, the default is ::/0 (no prefix).
231
232 SmartGatewayUplink <none/ipv4/ipv6/both>
233 SmartGatewayUplinkNAT <yes/no>
234 SmartGatewaySpeed <uplink> <downlink>
235 SmartGatewayPrefix <prefix>
236
237
238     6.) NatThreshold
239 ************************
240
241 The NatThreshold option was introduced by Sven Ola to suppress a very
242 annoying problem with OLSRd, switching default gateways. If a router
243 is located between two internet gateways with similar path costs the
244 default route (0.0.0.0/0) will constantly switch between the two
245 gateways because of normal fluctuations of the link metrics. Each
246 change will terminate all connected sessions (tcp and http), which will
247 make using the internet rather painful.
248
249 NatThreshold tries to help by introducing a hysteresis factor for
250 choosing the route to the default gateway. Only if the new gateway has
251 a lower cost than the current gateways path cost multiplied by
252 NatThreshold the node will switch the gateway. Practical experience
253 shows that this leads to much better quality of default gateway
254 selection, even if (in theory) a small NatThreshold together with
255 Fisheye can lead to a persistent routing loop.
256
257 The introduction of smart gateways should make NatThreshold not
258 necessary anymore.