[Olsr-cvs] olsrd-current README-Link-Quality-Fish-Eye.txt,NONE,1.1

[Thomas Lopatic]

Update of /cvsroot/olsrd/olsrd-current
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv593

Added Files:
	README-Link-Quality-Fish-Eye.txt 
Log Message:
Added Elektra's Fish Eye documentation.


--- NEW FILE: README-Link-Quality-Fish-Eye.txt ---
+=====================================================================+
|        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