Added Elektra's Fish Eye documentation.
authorThomas Lopatic <thomas@lopatic.de>
Wed, 14 Dec 2005 10:45:34 +0000 (10:45 +0000)
committerThomas Lopatic <thomas@lopatic.de>
Wed, 14 Dec 2005 10:45:34 +0000 (10:45 +0000)
README-Link-Quality-Fish-Eye.txt [new file with mode: 0644]
files/olsrd.conf.default.lq-fisheye [new file with mode: 0644]

diff --git a/README-Link-Quality-Fish-Eye.txt b/README-Link-Quality-Fish-Eye.txt
new file mode 100644 (file)
index 0000000..1e58990
--- /dev/null
@@ -0,0 +1,163 @@
++=====================================================================+
+|        Link Quality Fish Eye Mechanism   December 3th 2005          |
+|                                                                    | 
+|                          olsrd-0.4.10                              |
++=====================================================================+
+
+       Corinna 'Elektra' Aichele   (onelektra at gmx.net)
+
+---------------
+I. Introduction
+---------------
+
+Link Quality Fish Eye is a new (experimental) algorithm introduced in
+olsrd 0.4.10. To increase stability in a mesh, TC messages should be
+sent quite frequently. However, the network would then suffer from the
+resulting overhead. The idea is to frequently send TC messages to
+adjacent nodes, i.e. nodes that are likely to be involved in routing
+loops, without flooding the whole mesh with each sent TC message.
+
+OLSR packets carry a Time To Live (TTL) that specifies the maximal
+number of hops that the packets is allowed to travel in the mesh. The
+Link Quality Fish Eye mechanism generates TC messages not only with
+the default TTL of 255, but with different TTLs, namely 1, 2, 3, and
+255, restricting the distribution of TC messages to nodes 1, 2, 3, and
+255 hops away. A TC message with a TTL of 1 will just travel to all
+one-hop neighbours, a message with a TTL of 2 will in addition reach
+all two-hop neighbours, etc.
+
+TC messages with small TTLs are sent more frequently than TC messages
+with higher TTLs, such that immediate neighbours are more up to date
+with respect to our links than the rest of the mesh. We hope that this
+reduces the likelihood of routing loops.
+
+--------------
+II. How to use
+--------------
+
+The Fish Eye algorithm can be enabled in the configuration file
+/etc/olsrd.conf with the following lines:
+
+       # Fish Eye mechanism for TC messages 0 = off, 1 = on
+
+       LinkQualityFishEye 1
+
+Fish Eye should be used together with a small TcInterval setting as
+follows:
+
+       # TC interval in seconds (float)
+
+        TcInterval 0.5
+
+If olsrd is started with debug-level 3 it will print out a message
+every time a TC message is issued or dropped.
+
+The following sequence of TTL values is used by olsrd.
+
+        255 3 2 1 2 1 1 3 2 1 2 1 1
+
+Hence, a TC interval of 0.5 seconds leads to the following TC
+broadcast scheme.
+
+  * Out of 13 TC messages, all 13 are seen by one-hop neighbours (TTL
+    1, 2, 3, or 255), i.e. a one-hop neighbour sees a TC message every
+    0.5 seconds.
+
+  * Two-hop neighbours (TTL 2, 3, or 255) see 7 out of 13 TC messages,
+    i.e. about one message per 0.9 seconds.
+
+  * Three-hop neighbours (TTL 3 or 255) see 3 out of 13 TC messages,
+    i.e. about one message per 2.2 seconds.
+
+  * All other nodes in the mesh (TTL 255) see 1 out of 13 TC messages,
+    i.e. one message per 6.5 seconds.
+
+The sequence of TTL values is hardcoded in lq_packet.c and can be
+altered easily for further experiments.
+
+The Link Quality Fish Eye algorithm is compatible with earlier
+versions of olsrd or nodes that do not have the Fish Eye feature
+enabled.
+
+A default configuration file with the Link Quality Fish Eye mechanism
+and ETX enabled is located in ./files/olsrd.conf.default.lq-fisheye
+
+---------------
+III. Background
+---------------
+
+A major problem of a proactive routing algorithm is keeping topology
+control information in sync. If topology information is not in sync
+routing loops may occur. Usually routing loops happen in a local area
+in the mesh - within a few hops.
+
+It may happen that node A assumes that the best way to send packets to
+node C is by forwarding them to node B, while node B thinks that the
+best route to C is via node A. So A sends the packet to node B, and B
+returns it to A - we have a loop. This can of course also happen with
+more than two nodes involved in the loop, but it is unlikely that a
+routing loop involves more than a few nodes.
+
+Routing information like all data traffic gets lost on radio links
+with weak signal-to-noise ratio (SNR) or if collisions occur. Setting
+fragmentation and RTS (request-to-send) to conservative values on
+wireless interfaces is a must in a mesh to deal with hidden nodes,
+interference and collisions. A mesh that utilizes only one channel has
+to deal with many collisions between packets and a lot of
+self-generated interference. While a radio interface may have a range
+of only 300 meters its signals can disturb receivers that are more
+than 1000 meters away. The data traffic of a node in the distance is
+not readable, but it's signals add to the noise floor in receivers,
+reducing signal-to-noise ratio of local links.
+
+When a route is saturated with traffic the transmitters involved
+introduce permanent interference into the mesh, causing packet loss on
+other links in the neighbourhood. OLSR messages get lost, causing
+confusion. While the timeout values of MID messages or HNA messages
+can be increased to increase stability without a big tradeoff, TC
+messages that are up to date and arrive in time are critical. It is
+also critical to have MPR information in sync if the MPR algorithm is
+used, but in the author's opinion this optimization doesn't do any
+good anyway. The MPR algorithm introduces a new source of failure and
+reduces TC message redundancy, so it should be switched off in the
+configuration file /etc/olsrd.conf with these lines:
+
+        TcRedundancy 2
+        MprCoverage 25
+
+olsrd with LQ Extension attempts to know the best routes all over the
+whole mesh cloud, but it is likely that it never will be able to
+achieve this in a mesh that has more than a handful of nodes. TC
+information is likely to be lost on its way through the whole
+mesh. And this likelyhood increases with the number of hops.
+
+But this fact doesn't necessarily harm the routing of traffic on a
+long multihop path. A node at one end of a mesh cloud may have the
+illusion to know the exact and best path along which its packets
+travel when communicating with a node that is several hops away. But
+this information may be pretty outdated and incomplete.
+
+In fact all that the algorithm has to achieve is a reasonable choice
+for the next two or three hops. If the routing path is 8 hops, for
+example, nodes that are 5 hops away from the node initiating traffic
+and closer to the destination have better and more accurate
+information about the best path. They don't know what a node that
+initiates traffic thinks about the path that its packets should take,
+they have more accurate routing information and will look into their
+routing table and make a choice based on their knowledge.
+
+Someone that sends a snail mail parcel from Europe to India doesn't
+have to write the name of the Indian postman on the paket that is
+supposed to hand it over to the recipient or the brand of bicycle he
+is supposed to ride when transporting the parcel. He doesn't have to
+decide the path that the postman has to take in the recipient's
+village. The postman knows better than the sender.
+
+It should be sufficient if nodes have a vague idea about the topology
+of the mesh in the distance and who is out there. If only a few TC
+messages out of many TC packets that are broadcast make it over the
+whole mesh this should be sufficient.
+
+Have fun!
+
+Elektra
diff --git a/files/olsrd.conf.default.lq-fisheye b/files/olsrd.conf.default.lq-fisheye
new file mode 100644 (file)
index 0000000..8b22cf1
--- /dev/null
@@ -0,0 +1,298 @@
+#
+# olsr.org OLSR daemon config file
+#
+# Lines starting with a # are discarded
+#
+# This file was shipped with olsrd 0.X.X
+#
+
+# This file is an example of a typical
+# configuration for a mostly static
+# network(regarding mobility) using
+# the LQ extention
+
+# Debug level(0-9)
+# If set to 0 the daemon runs in the background
+
+DebugLevel     2
+
+
+# Fisheye mechanism for TC messages 0=off, 1=on
+
+LinkQualityFishEye 1
+
+
+
+# IP version to use (4 or 6)
+
+IpVersion      4
+
+# Clear the screen each time the internal state changes
+
+ClearScreen     yes
+
+# HNA IPv4 routes
+# syntax: netaddr netmask
+# Example Internet gateway:
+# 0.0.0.0 0.0.0.0
+
+Hna4
+{
+#   Internet gateway:
+#   0.0.0.0      0.0.0.0
+#   more entries can be added:
+#   192.168.1.0  255.255.255.0
+}
+
+# HNA IPv6 routes
+# syntax: netaddr prefix
+# Example Internet gateway:
+Hna6
+{
+#   Internet gateway:
+#   ::              0
+#   more entries can be added:
+#   fec0:2200:106:: 48
+}
+
+
+# Should olsrd keep on running even if there are
+# no interfaces available? This is a good idea
+# for a PCMCIA/USB hotswap environment.
+# "yes" OR "no"
+
+AllowNoInt     yes
+
+# TOS(type of service) value for
+# the IP header of control traffic.
+# If not set it will default to 16
+
+#TosValue      16
+
+# The fixed willingness to use(0-7)
+# If not set willingness will be calculated
+# dynamically based on battery/power status
+# if such information is available
+
+#Willingness           4
+
+# Allow processes like the GUI front-end
+# to connect to the daemon.
+
+IpcConnect
+{
+     # Determines how many simultaneously
+     # IPC connections that will be allowed
+     # Setting this to 0 disables IPC
+
+     MaxConnections  0
+
+     # By default only 127.0.0.1 is allowed
+     # to connect. Here allowed hosts can
+     # be added
+
+     Host            127.0.0.1
+     #Host            10.0.0.5
+
+     # You can also specify entire net-ranges 
+     # that are allowed to connect. Multiple
+     # entries are allowed
+
+     #Net             192.168.1.0 255.255.255.0     
+}
+
+# Wether to use hysteresis or not
+# Hysteresis adds more robustness to the
+# link sensing but delays neighbor registration.
+# Used by default. 'yes' or 'no'
+# Do not use hysteresis with ETX!
+
+UseHysteresis  no
+
+# Hysteresis parameters
+# Do not alter these unless you know 
+# what you are doing!
+# Set to auto by default. Allowed
+# values are floating point values
+# in the interval 0,1
+# THR_LOW must always be lower than
+# THR_HIGH.
+
+#HystScaling   0.50
+#HystThrHigh   0.80
+#HystThrLow    0.30
+
+
+# Link quality level
+# 0 = do not use link quality
+# 1 = use link quality for MPR selection
+# 2 = use link quality for MPR selection and routing
+# Defaults to 0
+
+LinkQualityLevel       2
+
+# Link quality window size
+# Defaults to 10
+
+LinkQualityWinSize     100
+
+# Polling rate in seconds(float). 
+# Default value 0.05 sec
+
+Pollrate       0.05
+
+
+# TC redundancy
+# Specifies how much neighbor info should
+# be sent in TC messages
+# Possible values are:
+# 0 - only send MPR selectors
+# 1 - send MPR selectors and MPRs
+# 2 - send all neighbors
+#
+# defaults to 0
+
+TcRedundancy   2
+
+
+#
+# MPR coverage
+# Specifies how many MPRs a node should
+# try select to reach every 2 hop neighbor
+#
+# Can be set to any integer >0
+#
+# defaults to 1
+
+MprCoverage    5
+
+
+# Olsrd plugins to load
+# This must be the absolute path to the file
+# or the loader will use the following scheme:
+# - Try the paths in the LD_LIBRARY_PATH 
+#   environment variable.
+# - The list of libraries cached in /etc/ld.so.cache
+# - /lib, followed by /usr/lib
+
+# Example plugin entry with parameters:
+
+#LoadPlugin "olsrd_dyn_gw.so.0.3"
+#{
+    # Here parameters are set to be sent to the
+    # plugin. Theese are on the form "key" "value".
+    # Parameters ofcause, differs from plugin to plugin.
+    # Consult the documentation of your plugin for details.
+
+    # Example: dyn_gw params
+
+    # how often to check for Internet connectivity
+    # defaults to 5 secs
+#   PlParam     "Interval"   "40"
+    
+    # if one or more IPv4 addresses are given, do a ping on these in
+    # descending order to validate that there is not only an entry in
+    # routing table, but also a real internet connection. If any of
+    # these addresses could be pinged successfully, the test was
+    # succesful, i.e. if the ping on the 1st address was successful,the
+    # 2nd won't be pinged
+#   PlParam     "Ping"       "141.1.1.1"
+#   PlParam     "Ping"       "194.25.2.129"
+#}
+
+
+
+# Interfaces and their rules
+# Omitted options will be set to the
+# default values. Multiple interfaces
+# can be specified in the same block
+# and multiple blocks can be set.
+
+# !!CHANGE THE INTERFACE LABEL(s) TO MATCH YOUR INTERFACE(s)!!
+# (eg. wlan0 or eth1):
+
+Interface "XXX" "YYY"
+{
+
+    # IPv4 broadcast address to use. The
+    # one usefull example would be 255.255.255.255
+    # If not defined the broadcastaddress
+    # every card is configured with is used
+
+    # Ip4Broadcast             255.255.255.255
+
+    # IPv6 address scope to use.
+    # Must be 'site-local' or 'global'
+
+    # Ip6AddrType              site-local
+
+    # IPv6 multicast address to use when
+    # using site-local addresses.
+    # If not defined, ff05::15 is used
+
+    # Ip6MulticastSite         ff05::11
+
+    # IPv6 multicast address to use when
+    # using global addresses
+    # If not defined, ff0e::1 is used
+
+    # Ip6MulticastGlobal       ff0e::1
+
+
+    # Emission intervals.
+    # If not defined, RFC proposed values will
+    # be used in most cases.
+
+    # Hello interval in seconds(float)
+    HelloInterval    5.0
+
+    # HELLO validity time
+    HelloValidityTime  200.0
+
+    # TC interval in seconds(float)
+    TcInterval        0.5
+
+    # TC validity time
+    TcValidityTime     50.0
+
+    # MID interval in seconds(float)
+    MidInterval        5.0
+
+    # MID validity time
+    MidValidityTime    100.0
+
+    # HNA interval in seconds(float)
+    HnaInterval        5.0
+
+    # HNA validity time
+    HnaValidityTime    100.0
+
+    # When multiple links exist between hosts
+    # the weight of interface is used to determine
+    # the link to use. Normally the weight is
+    # automatically calculated by olsrd based
+    # on the characteristics of the interface,
+    # but here you can specify a fixed value.
+    # Olsrd will choose links with the lowest value.
+
+    # Weight 0
+
+
+    # If a certain route should be preferred 
+    # or ignored by the mesh, the Link Quality 
+    # value of a node can be multiplied with a factor 
+    # entered here. In the example the route 
+    # using 192.168.0.1 would rather be ignored.
+    # A multiplier of 0.5 will result in a small
+    # (bad) LinkQuality value and a high (bad)
+    # ETX value.
+
+    # LinkQualityMult 192.168.0.1 0.5
+
+    # This multiplier applies to all other nodes 
+    # LinkQualityMult default 0.8
+
+
+}
+