Your search query "linkto:"olsr-story.txt"" didn't return any results. Please change some terms and refer to HelpOnSearching for more information.
(!) Consider performing a full-text search with your search terms.

Clear message
Italiano English
Edit History Actions

olsr-story.txt

The OLSR.ORG story

Proactive protocols (Link State Routing Protocols) generate a lot of
overhead because they have to keep topoloy information and routing tables in
sync amongst all or at least amongst adjacent nodes. If the protocol does
not manage to keep the routing tables synced it is likely that the payload
will spin in routing loops until the TimeToLive (TTL) is expired. Apart from
high traffic-overhead and CPU-Load this is the biggest issue for Link State
Routing Protocols.

We were actively involved in the evolution of olsrd from olsr.org. Actually
we were the people that made it functional. RFC3626 - the initial IETF-draft
of olsr - does not work in real life. If you want to find out what it's
developers intended it to be and how it should work, I would like to suggest
reading the RFC3626 after you have seen the presentation of Andreas
Tøennesen on the OLSR.ORG website about RFC3626.


We heavily modified olsr over the time. We disabled almost everything that
the inital designers of olsr thought was smart and replaced it with the
LQ/ETX-Mechanism and Fish-Eye Mechanism tp update topology information.



What we did to improve olsr (in historical order):

* Test OLSR according to RFC3626 at the conference Wizards of OS III in 2004
  - Meshcloud with 25 Nodes

        Results:

        Routing tables take long time to build and no time to break down.
        Routes flap.
        Routing loops.
        No throughput.
        Gateway switches all the time - so stateful applications will brake 
        down all the time



        Conclusion:

        Hysteresis mechanism frequently kicks Multi Point Relays (MPRs) out 
        of the routing table --> Infrastructure to broadcast topology information 
        breaks down all the time and MPRs have to be negotiated again...

        Multipoint relay selection selects nodes far away to keep the number of 
        necessary Multi Point Relays low --> Links to MPRs are weak, so hysteresis 
        kicks them out of the routing table more often than not
        
        Multipoint relay selection reduces protocol overhead and prevents topology 
        information from being in sync --> Routing loops
        
        Routes are unstable --> No throughput
        
        Routes selected on minimum Hop-count maximises packetloss --> No throughput

        Routing loops --> No throughput

        Dynamic gateway selection --> Stateful connections get interrupted when a 
        different gateway is selected



        What we did:
        Disable hysteresis.
        Disable MPRs - all nodes forward topology information.




Now almost everything that was meant to optimize Link State Routing was
disabled - a simple proactive link-state routing protocol with support for
multiple interfaces was all that was left. We started to deploy OLSR in the
Freifunk Mesh in Berlin - rather we should have named it LSR back then. But
since the implementation came from olsr.org and everything could be switched
on and off by the configuration file we didn't think about starting a new
project and renaming it. This became later a source of confusion and
disappointment for all people that tried olsr.org and had no idea what was
going on in Berlin. If you use the standard configuration file that is
shipped with olsr.org, olsrd will still behave according to RFC3626. So if
you want to see how miserable RFC3626 works - try it with the default
configuration file.




* Deployment of OLSR (with 'Optimizations' removed) in the Berlin Freifunk
  mesh cloud - 2004 

        Results:
        Works much better than RFC3626. Still it was hardly usable.
        Throughput very low and unstable.
        Routing table doesn't break down anymore
        Dynamic gateway selection --> Stateful connections get interrupted 
        when a different gateway is selected
        

        Conclusion:
        We knew routes based on minimum hopcount will likely have very 
        low throughput. 
        Dynamic gateway selection is a tradeoff of automatic gateway 
        selection by the protocol


        
I knew from my first experience with mobilemesh (another Link State Routing
Protocol that we tried at the beginning of the Freifunk Mesh) that minimum
hop count sucks completely as an algorithm to select routes. So I started to
think about routes that are chosen based on metrics measuring the
quality/throughput of links. I decided to use a metric based on packet loss
and found the idea of ETX (Expected Transmission Count) in a paper written
at the MIT. I didn't like the way they suggested to implement it (sending
extra UDP packets), so I developed the idea of ETX/LQ together with Thomas
Lopatic who implemented the new ideas in olsrd. Rather than sending extra
UDP-packets we could just keep track of missed or successfully transmitted
Hello-Packets which are frequently broadcasted by the LSR-mechanism anyway.
And we could send the information about the successfully received packets
within the Hello messages - so neighbors are updated immediately with every
"Hello" broadcast how their neighbor thinks about their own transmissions.

This was a lot of work in the code of olsrd and Thomas did a cumbersome but
really great job. I had the feeling that this would be a major milestone on
the way to a good working protocol. It was released as olsr-0.48 - we had a
nice party and a big barrel of beer at the c-base to celebrate the moment :) 
There was one tradeoff, however. We had to break compatibility with
RFC3626. But since RFC3626 wasn't usable in real-life we didn't bother much.


* Deployment of olsr-0.48 in the Freifunk-Mesh with ETX/LQ-Mechanism

        Results:
        Probably bugs in the huge amount of new program-code
        
        Good routing decisions on wireless links operating at the same speed 
        as long as the network is idle
        
        Throughput improved - but throughput is interrupted by routing loops 
        as soon as heavy network load is introduced
        
        Payload runs for a while at high speed, then the traffic is interrupted, 
        comes back after a while at slow speed - caused by routing loops
        
        Dynamic gateway selection --> Stateful connections get interrupted 
        when a different gateway is selected

        Conclusion:
        This was a mayor improvement, but... 
        Payload causes interference and alters LQ/ETX-Values - interference causes 
        lost LQ-Messages, so LQ/ETX-Values in topology messages change when
        traffic is introduced. If the protocol fails to update the link state 
        information in time the routing tables are not in sync - thus causing
         routing loops.

Freifunk OLSR-Networks in other cities that had relatively low traffic
compared to the capacity of their wireless links were quite happy with 0.48.
But networks where links got saturated were still unstable.

Now it became even more clear how stupid the idea of Multipoint-Relays was.
Traffic causes interference and lost topology update messages. So the link
quality values change - and the information that tells the nodes in the mesh
about the topology changes are likely to get lost on their way. MPRs reduce
the redundancy that is desperately needed to keep routing tables in sync.
And - even worse - the information about who is whose MPR is another
information that has to be synced. Another source of failure.

So we had to find a way to make sure that information about topology changes
is updated in time to avoid routing loops. A perfect routing table that only
works as long as the network is idle is quite useless...

One viable solution in a small mesh would be to send topology control
messages (TC-Messages) more often than Hello's - but we already had a mesh
with more than 100 nodes, so the traffic caused by redundant TC-Messages
would suffocate the network by introducing massive overhead. Than we had the
idea of sending TC-Messages with different TTL (Time-To-Live) values. I had
the hypothesis that routing loops would occur amongst adjacent nodes - so we
would only have to update topology changes quickly and redundant amongst
adjacent nodes.

We had to design an algorithm that would make sure that adjacent nodes have
correct topology information - but the problem is that it seemingly would
not work without massive overhead.

The idea we came up with is to send TC messages to adjacent nodes very
often, i.e. nodes that are likely to be involved in routing loops, without
flooding the whole mesh with each sent TC message. We called it Link Quality
Fish Eye mechanism.

OLSR packets carry a Time To Live (TTL) that specifies the maximum 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.

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 implementation of Link Quality Fish Eye mechanism took Thomas only a few
minutes - and it was the second major improvement. Thomas also introduced a
new switch, called LinkQualityDjikstraLimit. The slow CPUs of embedded
routers have serious problems to recalculate the routing tables in a Mesh
with more than 100 nodes. Every incoming TC-Message would trigger another
recalculation of the Djikstra-Table - this would be far too often.
LinkQualityDjikstraLimit allows to set an interval for recalculating the
Djikstra-Table.

* Deployment of olsr-0.4.10 

                Results:
                Now it is really working and usable :)
                
                It's still not absolutely loop-free
                
                Multihop-Links with 10 Hops work and are stable as long 
                as the wireless links work.
                
                LinkQualityDjikstraLimit allows to run olsr even on a 
                realtively slow CPU in a big Mesh-Cloud -
                but the routing-table becomes very very static
                
                Gateway-Switching is still a constant annoyance if a mesh 
                has more than one Internet-Gateway

                Conclusions:
                Apart from the problems with Gateway-Switching it is now a 
                well behaving routing protocol


But still... Thomas and I agreed that we could cope with the increasing size
of the Freifunk-Networks only by making the protocol more and more static.
Link State Routing has significant design flaws. Why does every node
calculate a whole routing table from every node to every node - if all it
can do is decide which direct neighbor it sends the packet to? Synchronized
Link State Information is impossible to achieve in a wireless network. Why
let every CPU calculate unneccessary information? Link State Routing thinks
too much and is far too complex for is own good. Why do all this?


We decided to come up with something better. Thomas had the idea for a name:
B.A.T.M.A.N - Better Approach To Mobile Ad-Hoc Networking.