Addons to readme regarding smartgw
[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 tunnels was written by Markus Kittenberg
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) use a dimensionless integer value for 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 others would be possible
47 and imaginable, such as MIC [0], etc.
48
49
50 Each link is described by a LQ (link quality) and a NLQ (neighbor link quality)
51 value, which describe the quality towards the router (LQ) and towards the
52 neighbor (neighbor link quality, NLQ). Both LQ and NLQ can be a value between 0
53 and 1.  The total cost of the link is calculated as ETX = 1.0/(LQ * NLQ). The
54 ETX value of a link can be seen as the number of retransmissions necessary to
55 deliver the packet to the target. ETX 1.0 mean a perfect link without packet
56 loss.
57
58      +---+              +---+
59      | A |  <--- LQ --- | B |
60      +---+  ---- NLQ -->+---+
61
62 Note that the LQ and NLQ are always seen as from one nodes' perspective: the LQ
63 of node A towards B is the percentage of packets that A can transmit to B.
64 Hence, in the OLSR ETX implementation, B has to tell A it's LQ.
65
66 OLSRd chooses the path towards a target by selecting the path segments with the
67 smallest sum of link costs. In other words:
68
69    best_path(A,B) = minimum_sum({set of all paths between A and B})
70
71
72 Configuration:
73 --------------
74
75 The link quality system is activated by setting the config variable
76 "LinkQualityLevel" to 2.
77
78 You can use the "LinkQualityAlgorithm" parameter to choose the current
79 link quality algorithm in the config file. Some embedded OLSRd versions
80 are only compiled with one plugin (mostly etx_ff), so don't use the
81 configuration option with these agents.
82
83 There are four different link quality algorithms in OLSRd 0.6.0, two
84 current Funkfeuer/Freifunk ETX implementations and two legacy implementations.
85
86 LinkQuality-Algorithm "etx_ff":
87 -------------------------------
88
89 "Etx_ff" (ETX Funkfeuer/Freifunk) is the current default LQ algorithm for OLSRd.
90 It uses the sequence number of the OLSR packages (which are link specific)
91 to determine the current packet loss rate. Etx_ff includes a hysteresis
92 mechanism to suppress small fluctuations of the LQ and NLQ value. If
93 no packages are received from a certain neighbor at all, a timer begins
94 to lower the calculated LQ value until the next package is received or
95 the link is dropped.
96 Etx_ff only uses integer arithmetic, so it performs well on embedded
97 hardware having no FPU.
98
99 The message format of etx_ff is compatible with etx_fpm and etx_float.
100
101
102 LinkQuality-Algorithm "etx_ffeth"
103 --------------------------------
104
105 "Etx_ffeth" is an experimental and INCOMPATIBLE extension of etx_ff (meaning it
106 will not interoperate with etx_ff nodes).  The problem with etx_ff, etx_float
107 and etx_fpm is that they calculate ethernet links with the same cost as a
108 wireless link without packet loss (ETX 1.0) because the encoding of etx_ff
109 cannot encode link costs lower than 1.0. This means OLSRd prefers a single
110 wireless link with some loss (e.g. ETX 1.5) over a two hop route with one
111 ethernet link (ETX 1.0) and one perfect wireless link (ETX 1.0) *even though*
112 the latter path would be better!
113
114 "Etx_ffeth" tries to work around this problem by introducing a special
115 LQ encoding for the value ETX 0.1, which is only used for ethernet
116 links without packet loss. Because of the different encoding etx_ffeth
117 is not compatible with etx_ff, etx_fpm or etx_float. These three
118 implementations detect etx_ffeth nodes with LQ 0 (ETX infinite).
119
120 etx_ffeth only use integer arithmetic, so it performs well on embedded
121 hardware.
122
123 At the time of this writing, etx_ffeth is the prefered metric for building new
124 mesh networks which include links over LAN cables (such as daisy chained
125 linksys routers).
126
127
128 Legacy LinkQuality-Algorithm "etx_float"
129 ----------------------------------------
130
131 "Etx_float" calculates the ETX value by using exponential aging (with
132 a configurable aging parameter) on the incoming (or lost) Hellos.
133 It is easier to understand than etx_ff, but the results are not as
134 good as in etx_ff, since it cannot use the TC messages for link
135 quality calculation.
136 Etx_float uses floating point math, so it might use more CPU on embedded
137 hardware.
138
139 The message format of etx_float is compatible with etx_fpm and etx_ff.
140
141
142 Legacy LinkQuality-Algorithm "etx_fpm"
143 --------------------------------------
144
145 "Etx_fpm" is a fixed point math implementation of etx_float. It
146 calculates the same link qualities as etx_float, but is much faster
147 on embedded hardware.
148
149 The message format of etx_fpm is compatible with etx_float and etx_ff.
150
151
152 Building your own LinkQuality Algorithm
153 ---------------------------------------- 
154
155 With the supplied samples OLSRd can be easily extended to support different
156 metrics. Please take a look at src/lq_plugin*.[ch] for inspiration and get in
157 contact with us on the OLSR development mailing list in case you plan to
158 implement a new metric.
159
160
161
162     3.) Fisheye
163 *******************
164
165 Normally OLSR floods all topology control (TC) messages to all
166 routes in the mesh, which can create a lot of overhead for large
167 meshs with hundreds of routers. Reducing the rate of TCs can reduce
168 this overhead, but delay route changes and correction of errors
169 in the routing tables.
170
171 The Fisheye (sometimes called Hazy Sighted Link State Routing [1])
172 mechanism implements a strategy to reach a compromise between
173 these two problems. When activated only every 8th TC is send
174 to all mesh nodes. Most TCs are given a reduced TTL (time to live)
175 and are only transmitted to the neighborhood of the router.
176
177 The current sequence of TTLs with active fisheye mechanism is
178 2, 8, 2, 16, 2, 8, 2 and 255 (maximum TTL).
179
180 The problem with Fisheye is that it introduces artifical borders
181 for flooding TCs, which can theoretically lead to inconsistent routes
182 and routing loops at the border of the fisheye circles. In practice
183 fisheye seems to work well enough that it is a mandatory feature
184 for most larger Funkfeuer/Freifunk meshs.
185
186
187     4.) NIIT (ipv4 over ipv6 traffic)
188 *****************************************
189 (see https://dev.dd19.de/cgi-bin/gitweb.cgi?p=niit.git;a=summary)
190
191 NIIT is a special linux kernel device that allows easy transmission of IPv4
192 unicast traffic through an IPv6 network. Since version 0.6.0 OLSRd has
193 integrated support for NIIT in the routing daemon. So setting up IPv4 traffic
194 over IPv6 OLSR meshs is very easy. Instead of creating routes and tunnels by
195 hand all the administrator of a router needs to do is to, is to set up his own
196 IPv4 targets as "IPv4-mapped" IPv6 HNAs.
197
198 Example configurations:
199 - connect a local 192.168.1.0/8 net to the mesh
200
201 HNA6 {
202   0::ffff:C0A8:01:00 120
203 }
204
205 - announce an IPv4 internet gateway
206
207 HNA6 {
208   0::ffff:0:0 96
209 }
210
211
212 More information on NIIT can be found at: http://wiki.freifunk.net/Niit
213 (german)
214
215
216     5.) Smart gateways (asymmetric gateway tunnels)
217 *******************************************************
218
219 The smartgateway mechanism was written by Markus Kittenberg and
220 Henning Rogge to allow an OLSR user to directly choose their default
221 internet gateway instead of relying on the hop by hop decisions on
222 the way to the gateway. OLSRd 0.6.0 can create an IPIP tunnel
223 to the gateways OLSRd address to sidestep the same nasty effects
224 described in the Nat-Threshold section.
225
226 The smartgateway code can be split into two sections, one is
227 responsible for announcing the existence of a smartgateway uplink
228 and one on the client nodes to choose an uplink and create the
229 tunnel to the gateway. It use a modified (but backward compatible)
230 special HNA to signal the gateways to the clients. The clients can
231 use a plugin (or the integrated default code) to choose one of the
232 available gateways and change it if necessary. 
233
234 The smartgateway system is setup by several configuration parameters,
235 most of them with a sane default setting. The whole system can be
236 switched on/off by the following parameter:
237
238 SmartGateway <yes/no>
239
240 All other parameters will be ignored if SmartGateway is set to "no"
241 (the default is "yes").
242
243 On the client side there is a single additional parameter which
244 controls if you want to allow the selection of an outgoing ipv4
245 gateway with NAT (network address translation).
246
247 SmartGatewayAllowNAT <yes/no>
248
249 The uplink side of the smartgateway code has four parameters to
250 set up the type of the uplink.
251
252 SmartGatewayUplink defines which kind of uplink is exported to the
253 other mesh nodes. The existence of the uplink is detected by looking
254 for a local HNA of 0.0.0.0/0, ::ffff:0:0/96 or 2000::/3. The default
255 setting is "both".
256 SmartGatewayUplinkNAT defines if the ipv4 part of the uplink use NAT.
257 The default of this setting is "yes".
258 SmartGatewaySpeed sets the uplink and downlink speed of the gateway,
259 which could be used by a plugin to choose the right gateway for a
260 client. The default is 128/1024 kbit/s.
261 The final parameter SmartGatewayPrefix can be used to signal the
262 external IPv6 prefix of the uplink to the clients. This might allow
263 a client to change it's local IPv6 address to use the IPv6 gateway
264 without any kind of address translation. The maximum prefix length
265 is 64 bits, the default is ::/0 (no prefix).
266
267 SmartGatewayUplink <none/ipv4/ipv6/both>
268 SmartGatewayUplinkNAT <yes/no>
269 SmartGatewaySpeed <uplink> <downlink>
270 SmartGatewayPrefix <prefix>
271
272 On the SmartGW server (the OLSR instance anncouning 'Internet here!' via
273 HNA0/0 or similar) the implicit tunl0 interface is used to forward  incoming 
274 packets originated by SmartGW clients to the internet route. This may be 
275 protected by the sysctl rp_filter setting. Note, that at least with RedHat kernel 
276 2.6.18, the net.ipv4.conf.tunl0.rp_filter sysctl file is not present after 
277 loading the "ipip" kernel module. Which prevents OLSRD from switching off the 
278 filter. As a workaround, add an "ip addr add 0.0.0.0/32 dev tunl0" after 
279 the "modprobe ipip" line in your OLSRD startup script. 
280
281 While the SmartGW function does a fine job on stand-alone PCs, system builders 
282 should keep in mind the following facts when setting up routing, firewalls 
283 and gateways:
284
285 a) The SmartGW tunnel communicates asymmetrically. An IP packet destinned to 
286 an Internet server is sent via the IPIP tunnel but returned via the standard 
287 OLSRD host route.
288
289 b) On the SmartGW server, you should double check your firewall rules and 
290 rp_filter defaults. While it's normally not possible to simply encap e.g. 
291 a "telnet 127.0.0.1" into IPIP and sent that to the SmartGW server, your 
292 specific configuration may open up other attack vectors for an intruder.
293
294 c) Do not forget to un-firewall tunl0->internet and (if required to 
295 NAT/MASQUERADE) this communication path.
296
297 d) While the SmartGW server does not use special routing, the SmartGW client
298 inserts policy routing rules for it's function. By using the default configuration,
299 the OLSRD standard default route is maintained in table 223 and the OLSRD SmartGW 
300 default route in table 224. Both tables are examined only, if you do not have
301 a default route in the main table (visible with "ip route ls"). Use "ip route ls
302 table 223" or "ip route ls table 224" for debugging/monitoring. You may also
303 activate the txtinfo plugin and "wget -O - http://localhost:2006/gateway".
304
305 e) For the stand-alone client (Notebook user running OLSRD in order to browse) 
306 the lowered IPIP tunnel MTU is no problem. If you do proxy routing, e.g. for 
307 attached LAN clients without OLSRD, you may want MSS-clamping for the tunnel 
308 interface created by OLSRD. Because OLSRD uses an arbitrary name for the tunnel
309 iface (e.g. tnl_7c41c668) you may want to include a wildcard iptables rule. Example:
310 iptables -A FORWARD -o tnl_+ -p tcp --tcp-flags SYN,RST SYN -j TCPMSS --clamp-mss-to-pmtu
311
312     6.) NatThreshold
313 ************************
314
315 The NatThreshold option was introduced by Sven Ola to suppress a very annoying
316 problem with OLSRd, switching default gateways. If a router is located between
317 two internet gateways with similar path costs the default route (0.0.0.0/0)
318 will constantly switch between the two gateways due to normal fluctuations of
319 the link metrics. Whenever OLSRd decides that the other NAT gateway is
320 "better", then switching to this new gateway will result in termination of all
321 connected sessions (TCP and HTTP). 
322 The user experience will be rather painful and users will experience hanging
323 SSH and HTTP sessions (or anything using TCP).
324
325 NatThreshold tries to help by introducing a hysteresis factor for
326 choosing the route to the default gateway. Only if the new gateway has
327 a lower cost than the current gateways path cost multiplied by
328 NatThreshold the node will switch the gateway. 
329 In short:
330
331   if (cost(new_gateway) < cost(current_gw)*NatThreshold)) {
332         switch_gateway();
333   }
334
335
336 Practical experience shows that this leads to much better quality of default
337 gateway selection, even if (in theory) a small NatThreshold together with
338 Fisheye can lead to  persistent routing loops.
339 Please note that even with NatThreshold enabled, some users will still experience
340 gateway switching. However, most users will not.
341
342 Smart Gateways can replace NatThreshold all together because they allow sending
343 traffic directly to a gateway circumventing the problems described above which
344 stem from a hop-by-hop routing approach 
345
346
347
348      7.) References
349 ************************
350 [0] MIC Metric: "Designing Routing Metrics for Mesh Networks", 
351         Yaling Yang, Jun Wang, Robin Kravets
352         http://www.cs.ucdavis.edu/~prasant/WIMESH/p6.pdf
353
354 [1] "Making link-state routing scale for ad hoc networks",
355         Cesar A. Santivanez, Ram Ramanathan, Ioannis Stavrakakis
356         http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.5940