lots of typos and clarified some topics
authorAaron Kaplan <aaron@ultrastabil.lan>
Mon, 15 Mar 2010 17:53:02 +0000 (18:53 +0100)
committerAaron Kaplan <aaron@ultrastabil.lan>
Mon, 15 Mar 2010 17:53:02 +0000 (18:53 +0100)
README-Olsr-Extensions

index 84f714b..62846e6 100644 (file)
@@ -29,7 +29,8 @@ The LQ-Plugin rewrite was done by Henning Rogge in 2008.
 The NIIT kernel module was written by lynxis in 2009.
 
 The asymmetric gateway tunnels was written by Markus Kittenberg
-and Henning Rogge, but were used by BATMAN before OLSRd.
+and Henning Rogge, but the concept was used by B.A.T.M.A.N before OLSRd.
+
 
 
     2.) Link quality algorithm
@@ -39,21 +40,34 @@ Concept:
 --------
 
 OLSRd (since version 0.5.6) use a dimensionless integer value for a
-representation of the 'cost' of each link. There are multiple LQ-Plugins,
-each of them calculating a cost for the links of the router. At the moment
-(version 0.5.7.0) all lq_plugins are using an ETX-metric (expected
-transmission count).
-
-Each link is described by a LQ (link quality) and a NLQ (neighbor link
-quality) value, which describe the quality towards the router (LQ) and
-towards the neighbor (NLQ). Both LQ and NLQ can be a value between 0 and 1.
-The total cost of the link is calculated as ETX - 1.0/(LQ * NLQ). The
-ETX value of a link could be considered as the number of retransmissions
-necessary to deliver the packet to the target. ETX 1.0 mean a perfect
-link without packet loss.
-
-OLSRd chooses the route towards a target by using the path with the
-smallest sum of link costs.
+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.5.7.0) all lq_plugins are
+using an ETX-metric (expected transmission count) but others would be possible
+and imaginable, such as MIC [0], WCETT [1], etc.
+
+
+Each link is described by a LQ (link quality) and a NLQ (neighbor link quality)
+value, which describe the quality towards the router (LQ) and towards the
+neighbor (neighbor link quality, NLQ). Both LQ and NLQ can be a value 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 |  <--- LQ --- | B |
+     +---+  ---- NLQ -->+---+
+
+Note that the LQ and NLQ are always seen as from one nodes' perspective: the LQ
+of node A towards B is the percentage of packets that A can transmit to B.
+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:
 --------------
@@ -64,17 +78,17 @@ The link quality system is activated by setting the config variable
 You can use the "LinkQualityAlgorithm" parameter to choose the current
 link quality algorithm in the config file. Some embedded OLSRd versions
 are only compiled with one plugin (mostly etx_ff), so don't use the
-configuration option with this agents.
+configuration option with these agents.
 
 There are four different link quality algorithms in OLSRd 0.5.7.0, two
-current Freifunk ETX implementations and two legacy implementations.
+current Funkfeuer/Freifunk ETX implementations and two legacy implementations.
 
 LinkQuality-Algorithm "etx_ff":
 -------------------------------
 
-"Etx_ff" (etx freifunk) is the current default lq algorithm for OLSRd.
+"Etx_ff" (ETX Funkfeuer/Freifunk) is the current default LQ algorithm for OLSRd.
 It uses the sequence number of the OLSR packages (which are link specific)
-to determine the current loss rate. Etx_ff includes a hysteresis
+to determine the current packet loss rate. Etx_ff includes a hysteresis
 mechanism to suppress small fluctuations of the LQ and NLQ value. If
 no packages are received from a certain neighbor at all, a timer begins
 to lower the calculated LQ value until the next package is received or
@@ -84,16 +98,18 @@ 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.
-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).
+"Etx_ffeth" is an experimental and INCOMPATIBLE extension of etx_ff (meaning it
+will not interoperate 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 latter path would be better!
 
 "Etx_ffeth" tries to work around this problem by introducing a special
 LQ encoding for the value ETX 0.1, which is only used for ethernet
@@ -104,19 +120,25 @@ implementations detect etx_ffeth nodes with LQ 0 (ETX infinite).
 etx_ffeth only use integer arithmetic, so it performs well on embedded
 hardware.
 
+At the time of this writing, etx_ffeth is the prefered 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's easier to understand than etx_ff, but the results are not as
-good as in etx_ff, because it cannot use the TC messages for link
+It is easier to understand than etx_ff, but the results are not as
+good as in 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"
 --------------------------------------
 
@@ -127,6 +149,16 @@ 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
 *******************
 
@@ -136,33 +168,32 @@ meshs 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)
+The Fisheye (sometimes called Hazy Sighted Link State Routing [2])
 mechanism implements a strategy to reach a compromise between
-this two problems. When activated only every 8th TC is send
+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 introduce artifical borders
+The problem with Fisheye is that it introduces artifical 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 Freifunk meshs.
+for most larger Funkfeuer/Freifunk meshs.
 
 
     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 OLSRd 0.5.7.0
-there is integrated support for NIIT in the routing daemon, so
-setting up IPv4 traffic over IPv6 OLSR meshs is very easy. Instead
-of creating routes and tunnels by hand all the administrator of a
-router has to do is to set up his own IPv4 targets as "IPv4-mapped"
-IPv6 HNAs.
+NIIT is a special linux kernel device that allows easy transmission of IPv4
+unicast traffic through an IPv6 network. Since version 0.5.7.0 OLSRd has
+integrated support for NIIT in the routing daemon. So setting up IPv4 traffic
+over IPv6 OLSR meshs 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
@@ -178,6 +209,10 @@ HNA6 {
 }
 
 
+More information on NIIT can be found at: http://wiki.freifunk.net/Niit
+(german)
+
+
     5.) Smart gateways (asymmetric gateway tunnels)
 *******************************************************
 
@@ -238,22 +273,51 @@ SmartGatewayPrefix <prefix>
     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 because of normal fluctuations of the link metrics. Each
-change will terminate all connected sessions (tcp and http), which will
-make using the internet rather painful.
+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. 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 a persistent routing loop.
+NatThreshold the node will switch the gateway. 
+In short:
 
-Smart Gateways can replace NatThreshold because they allow to send
-traffic directly to a gateway instead of hop-by-hop.
+  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 alltogether 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] WCETT Metric: Weighted Cumulative Expected Transmission Time,
+       "Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks"
+       Authors: Richard Draves, Jitendra Padhye, Brian Zill
+       Published: MobiCom 2004
+       http://research.microsoft.com/apps/pubs/default.aspx?id=73099
+       
+  [2] "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