Merge branch 'PolynomialDivision-feature/add_workflow'

[olsrd.git] / README-Olsr-Extensions

=====================================================
      OLSRd (version 0.6.0) protocol extensions
=====================================================

1.) Credits
2.) Link quality algorithms
3.) Fisheye
4.) NIIT (ipv4 over ipv6 traffic)
5.) Smart gateways (asymmetric gateway tunnels)
6.) NatThreshold

NIIT and Smart gateways are only supported for Linux at the moment.

    1.) Credits:
********************

The concept of ETX (Expected Transmission Count) has been developed by
Douglas S. J. De Couto at the Massachusetts Institute of Technology
(see http://en.wikipedia.org/wiki/Expected_Transmission_Count).

The original ETX design has been done by the Berlin Freifunk Network
(see www.freifunk.net and www.c-base.org), the code and message format
was coded by Thomas Lopatic.

Fisheye was implemented by Thomas Lopatic in 2005.

The LQ-Plugin rewrite was done by Henning Rogge in 2008.

The NIIT kernel module was written by lynxis in 2009.

The asymmetric gateway tunnel functionality was written by Markus Kittenberger
and Henning Rogge, but the concept was used by B.A.T.M.A.N before OLSRd.



    2.) Link quality algorithm
**********************************

Concept:
--------

OLSRd (since version 0.5.6) uses a dimension-less integer value as a
representation of the 'cost' of each link. This is often called Link Quality
(LQ for short). There are multiple LQ plugins, each of them calculating a cost
for the links of the router. At the moment (version 0.6.0) all LQ plugins are
using an ETX-metric (Expected Transmission Count) but other metrics would be
possible and imaginable, such as MIC [0], etc.


Each link is described by an LQ/NLQ (Link Quality/Neighbor Link Quality) value
pair, which describe the quality towards the router (LQ) and towards the
neighbor (NLQ). Both LQ and NLQ can be values between 0 and 1. The total cost
of the link is calculated as ETX = 1.0/(LQ * NLQ). The ETX value of a link can
be seen as the number of retransmissions necessary to deliver the packet to the
target. ETX 1.0 mean a perfect link without packet loss.

       A                  B
     +---+              +---+
     |   |  <--- LQ --- |   |
     |   |  ---- NLQ -->|   |
     +---+              +---+

Note that the LQ and NLQ are always as seen from one nodes' perspective: the LQ
of node B towards A is the percentage of packets that B can transmit to A.
Hence, in the OLSR ETX implementation, B has to tell A it's LQ.

OLSRd chooses the path towards a target by selecting the path segments with the
smallest sum of link costs. In other words:

   best_path(A,B) = minimum_sum({set of all paths between A and B})


Configuration:
--------------

The link quality system is activated by setting the configuration variable
"LinkQualityLevel" to 2.

You can use the "LinkQualityAlgorithm" parameter to choose the current
link quality algorithm in the configuration file. Some embedded OLSRd versions
are only compiled with one plugin (mostly etx_ff), so don't use the
configuration option with these agents.

There are four different link quality algorithms in OLSRd 0.6.0, two
current Funkfeuer/Freifunk ETX implementations and two legacy implementations.

LinkQuality-Algorithm "etx_ff":
-------------------------------

"Etx_ff" (ETX Funkfeuer/Freifunk) is the current default LQ algorithm for OLSRd.
It uses the sequence number of the OLSR packets (which are link specific)
to determine the current packet loss rate. Etx_ff includes a hysteresis
mechanism to suppress small fluctuations of the LQ and NLQ values. If
no packets are received from a certain neighbor at all, a timer begins
to lower the calculated LQ value until the next packet is received or
the link is dropped.
Etx_ff uses only integer arithmetic, so it performs well on embedded
hardware having no FPU.

The message format of etx_ff is compatible with etx_fpm and etx_float.


LinkQuality-Algorithm "etx_ffeth"
--------------------------------

"Etx_ffeth" is an experimental and INCOMPATIBLE extension of etx_ff (meaning it
is not interoperable with etx_ff nodes).  The problem with etx_ff, etx_float
and etx_fpm is that they calculate Ethernet links with the same cost as a
wireless link without packet loss (ETX=1.0) because the encoding of etx_ff
cannot encode link costs lower than 1.0. This means OLSRd prefers a single
wireless link with some loss (e.g. ETX=1.5) over a two hop route with one
Ethernet link (ETX=1.0) and one perfect wireless link (ETX=1.0) *even though*
the 2 hop path would be better!

"Etx_ffeth" tries to work around this problem by introducing a special
LQ encoding value ETX=0.1, which is only used for Ethernet
links without packet loss. Because of the different encoding, etx_ffeth
is not compatible with etx_ff, etx_fpm or etx_float. These three
implementations detect etx_ffeth nodes with LQ 0 (ETX infinite).

etx_ffeth uses only integer arithmetic, so it performs well on embedded
hardware.

All Ethernet interfaces must be marked with "mode ether"
(see olsrd.conf.default.full) in their interface configuration to get any
useful advantage of etxff_eth.

At the time of this writing, etx_ffeth is the preferred metric for building new
mesh networks which include links over LAN cables (such as daisy chained
Linksys routers).


Legacy LinkQuality-Algorithm "etx_float"
----------------------------------------

"Etx_float" calculates the ETX value by using exponential aging (with
a configurable aging parameter) on the incoming (or lost) Hellos.
It is easier to understand than etx_ff, but the results are not as
good as with etx_ff, since it cannot use the TC messages for link
quality calculation.
Etx_float uses floating point math, so it might use more CPU on embedded
hardware.

The message format of etx_float is compatible with etx_fpm and etx_ff.


Legacy LinkQuality-Algorithm "etx_fpm"
--------------------------------------

"Etx_fpm" is a fixed point math implementation of etx_float. It
calculates the same link qualities as etx_float, but is much faster
on embedded hardware.

The message format of etx_fpm is compatible with etx_float and etx_ff.


Building your own LinkQuality Algorithm
----------------------------------------

With the supplied samples OLSRd can be easily extended to support different
metrics. Please take a look at src/lq_plugin*.[ch] for inspiration and get in
contact with us on the OLSR development mailing list in case you plan to
implement a new metric.



    3.) Fisheye
*******************

Normally OLSR floods all topology control (TC) messages to all
routes in the mesh, which can create a lot of overhead for large
meshes with hundreds of routers. Reducing the rate of TCs can reduce
this overhead, but delay route changes and correction of errors
in the routing tables.

The Fisheye (sometimes called Hazy Sighted Link State Routing [1])
mechanism implements a strategy to reach a compromise between
these two problems. When activated only every 8th TC is send
to all mesh nodes. Most TCs are given a reduced TTL (time to live)
and are only transmitted to the neighborhood of the router.

The current sequence of TTLs with active Fisheye mechanism is
2, 8, 2, 16, 2, 8, 2 and 255 (maximum TTL).

The problem with Fisheye is that it introduces artificial borders
for flooding TCs, which can theoretically lead to inconsistent routes
and routing loops at the border of the Fisheye circles. In practice
Fisheye seems to work well enough that it is a mandatory feature
for most larger Funkfeuer/Freifunk meshes.


    4.) NIIT (ipv4 over ipv6 traffic)
*****************************************
(see https://dev.dd19.de/cgi-bin/gitweb.cgi?p=niit.git;a=summary)

NIIT is a special Linux kernel device that allows easy transmission of IPv4
unicast traffic through an IPv6 network. Since version 0.6.0 OLSRd has
integrated support for NIIT in the routing daemon. So setting up IPv4 traffic
over IPv6 OLSR meshes is very easy. Instead of creating routes and tunnels by
hand all the administrator of a router needs to do is to, is to set up his own
IPv4 targets as "IPv4-mapped" IPv6 HNAs.

Example configurations:
- connect a local 192.168.1.0/8 net to the mesh

HNA6 {
  0::ffff:C0A8:01:00 120
}

- announce an IPv4 Internet gateway

HNA6 {
  0::ffff:0:0 96
}


More information on NIIT can be found at: http://wiki.freifunk.net/Niit
(German)


    5.) Smart gateways (asymmetric gateway tunnels)
*******************************************************

    5.1) Introduction

The smart gateway mechanism was written by Markus Kittenberger and
Henning Rogge to allow an OLSR user to directly choose their default
Internet gateway instead of relying on the hop by hop decisions on
the way to the gateway. OLSRd 0.6.0 can create an IPIP tunnel
to the gateway's OLSRd address to side-step the same nasty effects
described in the NAT-Threshold section.

The smart gateway code can be split into two sections, one is
responsible for announcing the existence of a smart gateway uplink
and one (on the client nodes) to choose an uplink and create the
tunnel to the gateway. The announcing code uses a modified (but
backward compatible) special HNA to signal the gateways to the
clients. The clients can use a plugin (or the integrated default
code) to choose one of the available gateways and change it if
necessary.

The smart gateway system is setup by several configuration parameters,
most of them with a sane default setting. The whole system can be
switched on/off by the following parameter:

SmartGateway <yes/no>

All other parameters will be ignored if SmartGateway is set to "no"
(the default is "no").


    5.2) Client Side

1- SmartGatewayUseCount controls the maximum number of gateways that can be
   in use at any given time. A setting higher than 1 is used to mitigate the
   effects of breaking connections (due to the selection of a new gateway) on
   a dynamic network.
   The default setting is 1.
2- SmartGatewayInstanceId is the olsrd instance id, which is needed for proper
   cleanup of multi-gateway iptables and ip rules when running multiple olsrd
   instances on a node. This setting MUST be configured when the multi-gateway
   mode is enabled and must be unique between the olsrd instances running on
   the node. It may not contain whitespace and may not be empty.
   The default setting is <not set>.
3- SmartGatewayTakeDownPercentage determines the take-down percentage for a
   non-current smart gateway tunnel. If the cost of the current smart gateway
   tunnel is less than this percentage of the cost of the non-current smart
   gateway tunnel, then the non-current smart gateway tunnel is taken down
   because it is then presumed to be 'too expensive'.
   This setting is only relevant when SmartGatewayUseCount is larger than 1;
   a value of 0 will result in the tunnels not being taken down proactively,
   only when a new tunnel is created while then are already
   'SmartGatewayUseCount' tunnels.
   The default setting is 0.
4- SmartGatewayPolicyRoutingScript controls the policy routing script that is
   executed during startup and shutdown of olsrd. The script is only executed
   when SmartGatewayUseCount is set to a value larger than 1. The script must
   setup policy routing rules such that multi-gateway mode works. A reference
   script is included.
   The default setting is <not set>.
5- SmartGatewayEgressInterfaces determines the egress interfaces that are part
   of the multi-gateway setup and therefore only relevant when
   SmartGatewayUseCount is larger than 1 (in which case it must be explicitly
   set). This setting can contain multiple interfaces, for example
     SmartGatewayEgressInterfaces "eth0" "eth1" "ppp0"
   The default setting is <not set>.
6- SmartGatewayEgressFile declares the file that contains the bandwidth
   parameters of the egress interfaces declared by SmartGatewayEgressInterfaces.
   Every line in the file declares bandwidth parameters of an egress interface,
   with the format:
     # this is a comment
     interface=requireNetwork,requireGateway,upstream,downstream,pathcost,network/prefix,gateway
   Only the requireNetwork, requireGateway, upstream and downstream fields are
   mandatory, the other fields are optional. An empty field signifies that its
   default should be used.
   The field defaults are:
     requireNetwork     = 1 (true)
     requireGateway     = 1 (true)
     upstream           = 0 (Kbps)
     downstream         = 0 (Kbps)
     pathcost           = 0 (dimensionless, 1024 is equivalent to 1 hop)
     network/prefix     = no default / not set
                          - network is an IP address
                          - prefix is a number in the range [0, 24] for IPv4
                            and in the range [0, 128] for IPv6
     gateway            = no default / not set (IP address)
   Note that when an interface needs a gateway to properly transport traffic
   then the gateway IP address field MUST be set AND requireGateway MUST be
   non-zero; doing otherwise will result in non-functional routes being
   programmed. When an interface doesn't  need a gateway (for example a PPP
   interface) then the gateway IP address field MUST be left empty AND
   requireGateway MUST be set to zero.
   Also note that when an interface has an attached network (like an Ethernet
   interface, but not like a PPP interface) then the network/prefix field MUST
   be set AND requireNetwork MUST be non-zero in order for a network route to
   be programmed.
   The default setting is "/var/run/olsrd-sgw-egress.conf".
7- SmartGatewayEgressFilePeriod determines the period (in milliseconds) on which
   the SmartGatewayEgressFile is checked for changes and processed if changed.
   The default setting is 5000.
8- SmartGatewayStatusFile declares the file that is written by olsrd to contain
   the status of the smart gateways and is only relevant when
   SmartGatewayUseCount is larger than 1.
   The default setting is <not set>
9- SmartGatewayTablesOffset and SmartGatewayRulesOffset determine the ranges of
   policy routing rule markings that are used in a multi-gateway setup (see the
   policy routing script for an explanation).
   The default settings are 90 and 0 respectively. The value of 0 for
   SmartGatewayRulesOffset will automatically align the table and rule numbers
   for the server tunnel, egress interfaces and gateway tunnel interfaces.
10-SmartGatewayAllowNAT controls whether you want to allow the selection
   of an outgoing ipv4 gateway with NAT (Network Address Translation).
   The default setting is "yes".
11-SmartGatewayPeriod determines the period (in milliseconds) on which
   a new smart gateway selection is performed.
   The default setting is 10000 milliseconds.
12-SmartGatewayStableCount determines the number of times the same new gateway
   must be chosen before that new smart gateway is actually selected.
   The default setting is 6.
13-SmartGatewayThreshold (percentage) controls whether you want to allow
   re-selection of a new outgoing gateway if its routing cost is lower or equal
   to the configured percentage of the routing cost of the current gateway.
   The default setting is 0, which disables it.
14-SmartGatewayWeightExitLinkUp, SmartGatewayWeightExitLinkDown,
   SmartGatewayWeightEtx and SmartGatewayDividerEtx control the weighing
   of gateway bandwidth and ETX costs.
15-SmartGatewayMaxCostMaxEtx: When a node advertises the maximum bandwidth
   and its ETX is below the value of this setting then the resulting gateway
   costs are equal to the ETX, otherwise the normal calculation of the
   gateway costs applies (default is 2560).

   If SmartGatewayDividerEtx is zero then no weighing is performed (classical
   behaviour). Classical behaviour only takes ETX costs into account when
   choosing a gateway (select the 'nearest' gateway).

   The weighing also takes the gateway bandwidths into account (select the
   'nearest fat pipe' gateway).

   Gateways that have zero bandwidth for either their uplink or downlink are
   ignored.

   * The Weighing Process
   ======================

     ** Configuration Parameters
     ===========================
     SmartGatewayWeightExitLinkUp   = gateway exit link uplink weight
     SmartGatewayWeightExitLinkDown = gateway exit link downlink weight
     SmartGatewayWeightEtx          = ETX path cost weight
     SmartGatewayDividerEtx         = ETX path cost divider

     ** Gateway Parameters
     ===========================
     gw->uplink   (Mbps)            = gateway exit link uplink  , in Mbps
     gw->downlink (Mbps)            = gateway exit link downlink, in Mbps

     ** Weighing Formula
     ===================
                          SmartGatewayWeightExitLinkUp
     path_cost_weighed =  ---------------------------- +
                                gw->uplink (Mbps)

                          SmartGatewayWeightExitLinkDown
                          ------------------------------ +
                                gw->downlink (Mbps)

                           SmartGatewayWeightEtx
                          ---------------------- * path_cost
                          SmartGatewayDividerEtx

     ** Recommended Configuration Parameter Settings
     ===============================================
     (assuming LinkQualityAlgorithm "etx_ffeth")

     SmartGatewayWeightExitLinkUp   = 1    (default is 1)
     SmartGatewayWeightExitLinkDown = 1    (default is 1)
     SmartGatewayWeightEtx          = 1    (default is 1)
     SmartGatewayDividerEtx         = 4096 (default is 0)


    5.3) Uplink Side

1- SmartGatewayUplink defines which kind of uplink is exported to the
   other mesh nodes. The existence of the uplink is detected by looking
   for a local HNA of 0.0.0.0/0, ::ffff:0:0/96 or 2000::/3. The default
   setting is "both".
2- SmartGatewayUplinkNAT defines if the ipv4 part of the uplink uses NAT.
   The default of this setting is "yes".
3- SmartGatewaySpeed sets the uplink and downlink speed of the gateway,
   which could be used by a plugin to choose the right gateway for a
   client. The default is 128/1024 kbit/s.
4- SmartGatewayPrefix can be used to signal the external IPv6 prefix of
   the uplink to the clients. This might allow a client to change it's
   local IPv6 address to use the IPv6 gateway without any kind of address
   translation. The maximum prefix length is 64 bits,
   the default is ::/0 (no prefix).
5- SmartGatewayAlwaysRemoveServerTunnel can be used to signal that the
   server tunnel must always be removed on shutdown, irrespective of the
   interface up/down state during startup.


    5.4) Architecture & Notes

On the smart gateway server (the OLSR instance announcing 'Internet here!' via
HNA 0/0 or similar) the implicit tunl0 interface is used to forward incoming
packets originating on smart gateway clients to the Internet route. This may be
protected by the sysctl rp_filter setting. Note, that at least with RedHat
kernel 2.6.18, the net.ipv4.conf.tunl0.rp_filter sysctl file is not present
after loading the "ipip" kernel module, which prevents OLSRd from switching off
the filter. As a workaround, add an "ip addr add 0.0.0.0/32 dev tunl0" after
the "modprobe ipip" line in your OLSRd startup script.

While the smart gateway function does a fine job on stand-alone PCs, system
builders should keep in mind the following facts when setting up routing,
firewalls and gateways:

a) The smart gateway tunnel communicates asymmetrically. An IP packet destined
   for an Internet server is sent via the IPIP tunnel but returned via the
   standard OLSRd host route.

b) On the smart gateway server, you should double check your firewall rules and
   rp_filter defaults. While it's normally not possible to simply encapsulate
   (for example) a "telnet 127.0.0.1" into IPIP and sent that to the smart
   gateway server, your specific configuration may open up such attack vectors
   for an intruder.

c) Do not forget to open up the firewall for tunl0->Internet traffic and (if
   required to NAT/MASQUERADE) this communication path.

d) While the smart gateway server does not use special routing, the smart
   gateway client inserts policy routing rules for it's function. By using the
   default configuration, the OLSRd standard default route is maintained in
   table 223 and the OLSRd smart gateway default route in table 224. Both
   tables are examined only, if you do not have a default route in the main
   table (visible with "ip route ls"). Use "ip route ls table 223" or
   "ip route ls table 224" for debugging/monitoring. You may also activate the
   txtinfo plugin and do a "wget -O - http://localhost:2006/gateway".

e) For a standalone client (a notebook user running OLSRd in order to browse)
   the lowered IPIP tunnel MTU is no problem. If you do proxy routing, e.g. for
   attached LAN clients without OLSRd, you may want MSS-clamping for the tunnel
   interface created by OLSRd. Because OLSRd uses an arbitrary name for the
   tunnel interface (e.g. tnl_7c41c668) you may want to include a wildcard
   iptables rule. Example:
     iptables -w -A FORWARD -o tnl_+ -p tcp --tcp-flags SYN,RST SYN \
              -j TCPMSS --clamp-mss-to-pmtu

Furthermore (or alternatively) you might consider (on your gateway nodes)
clamping all traffic leaving your mesh to your ipip mtu (regardless if the
traffic comes out of the smart gateway tunnel or not!). Example:
  iptables -w -A FORWARD -o [your_gateway_interface] -p tcp \
           --tcp-flags SYN,RST SYN -j TCPMSS --set-mss 1480

Especially as during OLSRd startup, before an smart gateway is chosen (which is
delayed), new connections would use a larger MSS than the smart gateway tunnel
can handle. So the approach to clamp on the gateways should give better results.

But if you don't NAT on your gateways (but want to use smart gateway for some
special reason), you would have to do this on ALL gateways (even on gateways
that do not provide the smart gateway functionality!).


    6.) NatThreshold
************************

The NatThreshold option was introduced by Sven Ola to suppress a very annoying
problem with OLSRd, switching default gateways. If a router is located between
two Internet gateways with similar path costs the default route (0.0.0.0/0)
will constantly switch between the two gateways due to normal fluctuations of
the link metrics. Whenever OLSRd decides that the other NAT gateway is
"better", then switching to this new gateway will result in termination of all
connected sessions (TCP and HTTP).
The user experience will be rather painful and users will experience hanging
SSH and HTTP sessions (or anything using TCP).

NatThreshold tries to help by introducing a hysteresis factor for
choosing the route to the default gateway. Only if the new gateway has
a lower cost than the current gateways path cost multiplied by
NatThreshold the node will switch the gateway.
In short:

  if (cost(new_gateway) < cost(current_gw)*NatThreshold)) {
        switch_gateway();
  }


Practical experience shows that this leads to much better quality of default
gateway selection, even if (in theory) a small NatThreshold together with
Fisheye can lead to  persistent routing loops.
Please note that even with NatThreshold enabled, some users will still
experience gateway switching. However, most users will not.

Smart Gateways can replace NatThreshold all together because they allow sending
traffic directly to a gateway circumventing the problems described above which
stem from a hop-by-hop routing approach



     7.) References
************************
[0] MIC Metric: "Designing Routing Metrics for Mesh Networks",
        Yaling Yang, Jun Wang, Robin Kravets
        http://www.cs.ucdavis.edu/~prasant/WIMESH/p6.pdf

[1] "Making link-state routing scale for ad hoc networks",
        Cesar A. Santivanez, Ram Ramanathan, Ioannis Stavrakakis
        http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.5940