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