plugin: dot_draw: readme: make it clear, that it only opens an IPv4-socket, so a...
[olsrd.git] / unmaintained / README-Link-Quality-Fish-Eye.txt
1 +=====================================================================+
2 |        Link Quality Fish Eye Mechanism   December 3th 2005          |
3 |                                                                     | 
4 |                           olsrd-0.4.10                              |
5 +=====================================================================+
6
7         Corinna 'Elektra' Aichele   (onelektra at gmx.net)
8
9 ---------------
10 I. Introduction
11 ---------------
12
13 Link Quality Fish Eye is a new (experimental) algorithm introduced in
14 olsrd 0.4.10. To increase stability in a mesh, TC messages should be
15 sent quite frequently. However, the network would then suffer from the
16 resulting overhead. The idea is to frequently send TC messages to
17 adjacent nodes, i.e. nodes that are likely to be involved in routing
18 loops, without flooding the whole mesh with each sent TC message.
19
20 OLSR packets carry a Time To Live (TTL) that specifies the maximal
21 number of hops that the packets is allowed to travel in the mesh. The
22 Link Quality Fish Eye mechanism generates TC messages not only with
23 the default TTL of 255, but with different TTLs, namely 1, 2, 3, and
24 255, restricting the distribution of TC messages to nodes 1, 2, 3, and
25 255 hops away. A TC message with a TTL of 1 will just travel to all
26 one-hop neighbours, a message with a TTL of 2 will in addition reach
27 all two-hop neighbours, etc.
28
29 TC messages with small TTLs are sent more frequently than TC messages
30 with higher TTLs, such that immediate neighbours are more up to date
31 with respect to our links than the rest of the mesh. We hope that this
32 reduces the likelihood of routing loops.
33
34 --------------
35 II. How to use
36 --------------
37
38 The Fish Eye algorithm can be enabled in the configuration file
39 /etc/olsrd.conf with the following lines:
40
41         # Fish Eye mechanism for TC messages 0 = off, 1 = on
42
43         LinkQualityFishEye 1
44
45 Fish Eye should be used together with a small TcInterval setting as
46 follows:
47
48         # TC interval in seconds (float)
49
50         TcInterval 0.5
51
52 If olsrd is started with debug-level 3 it will print out a message
53 every time a TC message is issued or dropped.
54
55 The following sequence of TTL values is used by olsrd.
56
57         255 3 2 1 2 1 1 3 2 1 2 1 1
58
59 Hence, a TC interval of 0.5 seconds leads to the following TC
60 broadcast scheme.
61
62   * Out of 13 TC messages, all 13 are seen by one-hop neighbours (TTL
63     1, 2, 3, or 255), i.e. a one-hop neighbour sees a TC message every
64     0.5 seconds.
65
66   * Two-hop neighbours (TTL 2, 3, or 255) see 7 out of 13 TC messages,
67     i.e. about one message per 0.9 seconds.
68
69   * Three-hop neighbours (TTL 3 or 255) see 3 out of 13 TC messages,
70     i.e. about one message per 2.2 seconds.
71
72   * All other nodes in the mesh (TTL 255) see 1 out of 13 TC messages,
73     i.e. one message per 6.5 seconds.
74
75 The sequence of TTL values is hardcoded in lq_packet.c and can be
76 altered easily for further experiments.
77
78 The Link Quality Fish Eye algorithm is compatible with earlier
79 versions of olsrd or nodes that do not have the Fish Eye feature
80 enabled.
81
82 A default configuration file with the Link Quality Fish Eye mechanism
83 and ETX enabled is located in ./files/olsrd.conf.default.lq-fisheye
84
85 ---------------
86 III. Background
87 ---------------
88
89 A major problem of a proactive routing algorithm is keeping topology
90 control information in sync. If topology information is not in sync
91 routing loops may occur. Usually routing loops happen in a local area
92 in the mesh - within a few hops.
93
94 It may happen that node A assumes that the best way to send packets to
95 node C is by forwarding them to node B, while node B thinks that the
96 best route to C is via node A. So A sends the packet to node B, and B
97 returns it to A - we have a loop. This can of course also happen with
98 more than two nodes involved in the loop, but it is unlikely that a
99 routing loop involves more than a few nodes.
100
101 Routing information like all data traffic gets lost on radio links
102 with weak signal-to-noise ratio (SNR) or if collisions occur. Setting
103 fragmentation and RTS (request-to-send) to conservative values on
104 wireless interfaces is a must in a mesh to deal with hidden nodes,
105 interference and collisions. A mesh that utilizes only one channel has
106 to deal with many collisions between packets and a lot of
107 self-generated interference. While a radio interface may have a range
108 of only 300 meters its signals can disturb receivers that are more
109 than 1000 meters away. The data traffic of a node in the distance is
110 not readable, but it's signals add to the noise floor in receivers,
111 reducing signal-to-noise ratio of local links.
112
113 When a route is saturated with traffic the transmitters involved
114 introduce permanent interference into the mesh, causing packet loss on
115 other links in the neighbourhood. OLSR messages get lost, causing
116 confusion. While the timeout values of MID messages or HNA messages
117 can be increased to increase stability without a big tradeoff, TC
118 messages that are up to date and arrive in time are critical. It is
119 also critical to have MPR information in sync if the MPR algorithm is
120 used, but in the author's opinion this optimization doesn't do any
121 good anyway. The MPR algorithm introduces a new source of failure and
122 reduces TC message redundancy, so it should be switched off in the
123 configuration file /etc/olsrd.conf with these lines:
124
125         TcRedundancy 2
126         MprCoverage  7
127
128 olsrd with LQ Extension attempts to know the best routes all over the
129 whole mesh cloud, but it is likely that it never will be able to
130 achieve this in a mesh that has more than a handful of nodes. TC
131 information is likely to be lost on its way through the whole
132 mesh. And this likelyhood increases with the number of hops.
133
134 But this fact doesn't necessarily harm the routing of traffic on a
135 long multihop path. A node at one end of a mesh cloud may have the
136 illusion to know the exact and best path along which its packets
137 travel when communicating with a node that is several hops away. But
138 this information may be pretty outdated and incomplete.
139
140 In fact all that the algorithm has to achieve is a reasonable choice
141 for the next two or three hops. If the routing path is 8 hops, for
142 example, nodes that are 5 hops away from the node initiating traffic
143 and closer to the destination have better and more accurate
144 information about the best path. They don't know what a node that
145 initiates traffic thinks about the path that its packets should take,
146 they have more accurate routing information and will look into their
147 routing table and make a choice based on their knowledge.
148
149 Someone that sends a snail mail parcel from Europe to India doesn't
150 have to write the name of the Indian postman on the paket that is
151 supposed to hand it over to the recipient or the brand of bicycle he
152 is supposed to ride when transporting the parcel. He doesn't have to
153 decide the path that the postman has to take in the recipient's
154 village. The postman knows better than the sender.
155
156 It should be sufficient if nodes have a vague idea about the topology
157 of the mesh in the distance and who is out there. If only a few TC
158 messages out of many TC packets that are broadcast make it over the
159 whole mesh this should be sufficient.
160
161 Have fun!
162
163 Elektra