Multicast for OLSR mesh networks: Obamp release by Saverio Proto

Saverio Proto (ZioPRoTo) has the released the olsr OBAMP plugin, that was a freifunk project for the Google Summer Of Code. The OBAMP plugin allows multicast traffic to be forwarded in a OLSR mesh network. OBAMP is an overlay protocol. It first makes a mesh network with overlay links (udp tunnels) between the OBAMP nodes, and then it creates a distribution spanning tree over these mesh links.

This version of the OBAMP protocol, implemented as an OLSR plugin, is a simplified one for Wireless Community Networks, where we assume the nodes to be in fixed positions on the roof of the houses. Protocol features regarding mobility have not been implemented (yet).

To explain how the plugin works consider the scenario in the following figure:

There are 7 routers, where only 5 have the OBAMP plugin working. Router 1 2 and 6 also have an attached HNA network with some hosts.

OBAMP nodes generate OLSR OBAMP_ALIVE messages, these OLSR messages are forwarded in the whole network (also by the nodes that do not understand OBAMP thanks to the OLSR design). Because of the flooding mechanism every OBAMP node has a complete list of all the other OBAMP nodes in the mesh network. Every OBAMP node listens on the UDP port 6226 for OBAMP signalling.

When a OBAMP nodes starts it has 5 timers to periodically start operations:

OBAMP_alive_timer: every obamp node sends alive messages to advertise its presence to the other obamp nodes in the network. In the alive message every nodes states its IP address, and if it has already a tree link or not (we will see later this information is important for the outer tree create procedure).
The OBAMP network must have a member called “Core”, that starts the TREE_CREATE procedure. The core is the node with the smallest IP address. When the list of known OBAMP nodes changes, the Core Election procedure is eventually called.

mesh_create_timer: every obamp node every OBAMP_MESH_CREATE_IVAL evaluates how far the other obamp nodes are and selects a subset of nodes to keep mesh links with. Note that to reduce signalling and to increase scalability, the overylay mesh links are setup only with a subset of the nearest OBAMP nodes. To select the overlay neighbor the OBAMP nodes first calculates the ETX distance of the nearest OBAMP nodes, and the creates overlay mesh links to every node that are far in the range (minETX,minETX+1)

tree_create_timer: the core of the network every OBAMP_TREE_CREATE_IVAL sends a message called TREE_CREATE on its mesh links. The creation of the spanning tree is very similar to the spanning tree protocol. When a TREE_CREATE message is received a OBAMP node enables a tree link with its parent and forwards the TREE_CREATE on the other mesh links. TREE_CREATE messages are generated only by the core and are numbered, so TREE_CREATE received over loops can be discarded.

outer_tree_create_timer: The mesh_create algorithm may create cluster of OBAMP nodes within the network that are disconnected between each other. This happens if there are groups OBAMP nodes that are far from each other. If this happens only the cluster where the Core is present will receive the TREE_CREATE and will receive traffic from the distribution tree. To overcome this problem if in a cluster there are not TREE_CREATE every OBAMP_TREE_CREATE_IVAL the node with the smallest IP in the cluster will make a long mesh link with the nearest node that has at least a tree link. All the necessary information to perform this procedure is diffused in the OBAMP_ALIVE messages.

purge_nodes_timer: checks expire time of various variables, and deletes nodes or tree links in a soft state fashion

The OBAMP nodes will capture the multicast udp traffic from the non-OLSR interfaces, and will forward this traffic encapsulated in the UDP tunnels of the distribution tree. The other OBAMP nodes will forward the traffic in the tree and will decapsulate it on their non-OLSR interfaces. To avoid duplicated packets the data is carried into OBAMP_DATA messages, that are identified by a sequence number, and the OBAMP source node where the traffic has been encapsulated.

In the figure black links represent real radio links, and red links represent overlay mesh links (udp tunnels). Router 1 2 3 and will create a OBAMP cluster, with two mesh links. Router 6 and 7 will create a mesh link between them. Because the mesh_create algorithm does not create a mesh link between the two clusters, the router 6 (supposing it has the smallest IP address in the mesh) will create an outer tree link with Router 3.

So please download the code and use it . If you find bugs please report them to Saverio and in the Sourceforge tracker here: 

http://sourceforge.net/tracker/?atid=681702&group_id=117612&func=browse

Thanks for this great result of the summer. Special thanks also to Nino from ninux.org who was the mentor for this projet.

Links

* http://zioproto.ninux.org/wordpress/2009/08/31/olsrd-obamp-plugin/
* http://gredler.at/hg/olsrd/rev/8e7887c1247f
* http://olsr.org
* http://blog.freifunk.net
* http://ninux.org

The Fonera Pack Story

This blog entry is mainly in english. Sorry for that, but the original recipient (a belgian guy) is very much better in english. Since beginning of 2007, a startup company called "FON" is distributing very cheap (subventioned) WLAN devices: the la-Fonera wireless LAN router. For these, I've created and published an additional software, called the Freifunk-Fonera-Pack available here: http://download.olsrexperiment.de/fonera/ . The Pack offers Freifunk meshing in parallel to the FON function. Obviously, I've missed to explain the different networking modes and hance a posting on our internal berlin mailing list reaches me with a lot of questions. Mario asked me to publish the anwers here.
Hi Steven,
yes I know. There's not enough info about the networking / mode stuff in the ff-fonera-pack readme. OK – I'll try.
Networking Model
The networking model / how internet is distributed in a Freifunk mesh is very different to the FON business model. The FON model includes a certain amount of hotspots scattered over an arbitrary area. Each FON router should have its own (wired) internet access via DSL, leased line or dialup modem. The idea is – as you hopefully know – to share/sell the unused bandwidth of the payed personal internet access to others. Freifunk is different. We form a wireless intranet, where internet access is a service offered by volunteers. We normally do not pay for internet connectivity. In short: Freifunk forms a network and FON is a hotspot service offer.
To "catch" paying users, a FON hotspot offers it's connectivity in a mode easily understand by typical end-user laptops/notebooks/PCs: the access point wifi mode. A connecting PC should have connectivity and zero-admin config, so it is hopefully really easy to display the"insert-coin-here" page. Freifunk again is different here. To participate as equal with equals in a network, we need to cooperate at least on the techical level. This includes using a specific wifi mode (ad-hoc or IBSS) as well as relaying data of other users and running a certain protocol program to find and configure optimized data paths through the network.
To combine these different networking models, the Freifunk-Fonera-Pack offers different operation "modes". These modes are designed following these simple rules:

  1. The FON and Freifunk stuff should function as designed in parallel
  2. It should not be possible to sell the internet connectivity offered by Freifunk volunteers via FON
  3. It should not be possible to nerve wreck Freifunk users with the FON login page
  4. There should be a benefit for the average FON user to install that stuff

You can use the "Open" mode, if you want to share your own internet uplink with the community. Every Freifunk user connecting via Ad-Hoc and running the OLSR routing program can use your internet gateway. It's announced per "HNA" which basically says "Internet here". The OLSR program will search and configure a data path ("route") to the nearest HNA internet gateway available. Without the FON login page of course.
You can use the "Ego" mode, if you do not want the FON stuff / FON login page at all. To keep fair play, the FON callback is stopped and there is no "FON_AP" signal then. If you want to offer internet to the community, simply configure internet as usual. If you want to use a Freifunk gateway, simply do not connect any internet uplink.
If you want to relay data via WLAN/radio from other Freifunk users, but you want your own internet uplink for yourself (and the FON users loggin in), you can use the "Stealth" mode. All the Freifunk mesh routing happens in a background routing table. You do not announce your internet gateway via HNA and an Ad-Hoc connected Freifunk node / PC / laptop uses a different default route (not your standard internet default route).
As a benefit for the FON offering user, you can tunnel your own internet gatway via Freifunk and offer a FON uplink elsewhere in the Freifunk mesh. For this, the different Master-Modes (Open-Master, Ego-Master, Ego-Slave) are offered. You can configure a second / third / forth Fonera as "Slave" and set up a tunnel via Freifunk-meshing to use and sell your own internet gateway via FON. You'll find a sample configuration on the "Freifunk-Advanced" web page installed as part of the Freifunk-Fonera-Pack. Besides that, the Freifunk-Fonera-Pack adds a bit more security currently, provided that you do not use 192.168.x.x as meshing IP – but that's another story.
Q: Why there are no "Open-Slave", "Ego-Slave" nor "Stealth-Slave" modes?
A: Well, if you re-think it and maybe read the above once more you will understand. "Open-Slave" is contraprodutive. A device should not announce internet which it does not have. "Ego-Slave" is not necessary. Simply use "Ego". "Ego" will configure/use the next HNA / Freifunk gateway, possibly your Fonera in "Open" mode. "Stealth-Slave": This is offered as "Slave" mode.
HTH
// Sven-Ola
At the next day, a posting with more questions dropped in. I don't want to cite that here, mainly because I have not asked Steven to do so. To summarize: He has not tried the tunnel stuff and wanted to have an easy configuration for a couple of other guys, e.g. "publish the FON password" and "we are all in Linus mode". I may be wrong, but those points are the main questions asked IMO.
Steven,
uuh! Lots of questions 🙁 OK – to sort that out, here are some more statements.
Tunneling Internet
Our understanding of a mesh network includes using those cheap devices, to form a network. You can – of course – use the precious laptops to join in. But in the long run, a mesh only functions, if the nodes (the laptops, PCs, the routing boxes running OLSR) are switched on for a longer period. I talk about months not minutes. Also, you normally do not want to place the laptop on the roof of your house. For example: we do not have OLSR for Vista currently – and only a very small number of whiners. We all use those boxes to connect (e.g. via DHCP and NAT). You plug in your laptop into the box (either by ethernet or by a second Access Point) and go. That's the main use case.
You wote, that you (and your friends) don't want to break your "FON promise". The ff-fonera-pack is open source, and because of that you are free to do anything you like. Some expertize required. Especially the "Chillispot needs to fiddle with the default route thing" will be the hurdle to master here. Also I expect some dirty policy routing tricks are required. I personally do not want to make that, because of the reasons I wrote in my last post.
Lets form an example. You have internet access via DSL. You have a fonera connected to the DSL line, configured all, and switched to "Open". You have two friends who also bought a Fonera. One has his own DSL line and one not. Your own fonera uses 172.16.0.254/12 as meshing IP, channel 3 and 02:ca:ff:ee:ba:be as meshing BSSID.
Friend1 with DSL line: That's easy. Just proceed as usual. He can use "Open" or "Stealth" modes, which depends on "does he want to share for free" or not. He switches to channel 3, configures an arbitrary ESSID (say IZEFON, but I would prefer a more sexy name) for meshing and the FON_Friend1 and MyPlace_Friend1 as usual. He configures 172.16.0.1/12 as meshing IP. The critical thing is the BSSID (the hex number). The meshing ESSID is not really used – the BSSID for meshing and the channel needs to be the same on all meshing Foneras. Ah – and you need a Wiki page stating: "Friend1 uses 172.16.0.1/12" as well as "Steven uses 172.16.0.254/12".
Friend2 without DSL line: To keep the "Fon promise", he normally needs to buy a DSL line. The FON promise is based on that. But: that friend can use for example the Steven-DSL via the tunnel setup. Setting up tunnels is easy, and the standad Fonera should be able to run ~ 8 tunnels concurrently (depends on memory consumption). The tunnel stuff should also be able to handle ~500kbyte/sec, which in most cases matches your DSL line speed. You will be happy if you reach that speed via meshing with some kilometres distance which also requires a very good antenna setup.
The first thing to do is adding "Friend2 uses 172.16.0.2/12" to the wiki page. Friend2 configures BSSID, MeshingIP and Channel3. Friend2 also switches to "Slave" which basically means: The device has internet via tunnel and does not interfere with the OLSR-HNA-search-best-gateway algorithm. He also changes the private MyPlace_Friend2 IP range from the default 192.168.10.1/24 to 192.168.11.1/24 (more on this later).
Now Steven switches to Open-Master to let Friend2 in. It needs to be a good friend, since he sells your DSL line to FON and he has access to your private IP range (the 192.168.10.1/24 used for your own MyPlace_Steven domain). To let his friend in, Steven needs to browse to the Advanced/Freifunk-Advanced page of his Fonera and enter this in the "Private IP" input field: "192.168.10.2:192.168.11.2/24". Steven also enters a tunnel password there, any arbitrary string will do.
Friend2 now also browse to the Freifunk-Advanced page, and enter the same tunnel password as well as this to the "Private IP" input: "192.168.11.2:192.168.10.2/24". You may note that those settings are symmetrical. Friend2 needs to define, which Master tunnel endpoint to use. So he enters this to the "Master IP" input: "172.16.0.254:4711". Which basically says: On Stevens fonera, there is an open tunnel endpoint on port 4711.
After restarting both Foneras, you should notice the "FON_xxx" on the Fonera of Friend2. This proves: Setup is working. Ah – you may enter the Foners command line or connect to MyPlace_Friend2. Then send "ping 192.168.10.1". This proves, that both private IP ranges (the 192.168.10.1/24 and 192.168.11.1/24) are linked by routing and theres no firewalling in between.
Phew. Much blabla. I hope this will help you a bit.
// Sven-Ola
To write down some final words: It is obvious, that setting up a Freifunk network is not too easy. To teach and inform, it needs much more text than (for example) attracting FON users with a Plug-and-Play promise. I'm sure, that we never reach that Plug-and-Play state, but of course things can be made more easy with good documentation and good Web-UI-Design. I hope that Steven finds his way through the competing network models. It should be clear that a company needs to make a profit, while Freifunk is created by volunteers. But we also want something from others of course – e.g. World domination (cited from Linus). TANSTAAFL!

Auf dem Weg zum überregionalen Freifunk-Netz

Viele Freifunker kennen das: Man ist der erste und hat keinen
Kontakt zur „großen Wolke“. Auch wenn sich einige Freunde in der Umgebung mit anschließen,
solange kein Kontakt zur großen Wolke besteht, bleibt das Freifunk-Erlebnis doch
ziemlich unspektakulär. Warum also den ganzen Aufwand betreiben und mitmachen?
Warum nicht warten, bis sich die Lücke zu zum lokalen Netz schließt?

Um verstreute Netze – kleine und große miteinander zu
verbinden, gibt es nun das FreifunkVPN-Projekt. Denn, mittels VPN-Technik ergibt
sich die Möglichkeit einzelne Wolken über das Internet mit einem Tunnel zu
verbinden und so die Freifunkwolken in einer Stadt und sogar die Netze
verschiedener Städte in einem gemeinsamen überregionalen Freifunk-Netz zu
vereinen. Dies ermöglicht nun auch den Freifunkern in kleinen Netzen mit
größeren Freifunk-Wolken in Kontakt zu treten und so direkt mit entfernten
Teilnehmern zu kommunizieren –  ein
starker Motivationsschub. Die Frage des Mitmachens wird klar mit „Ja, so
schnell wie möglich“ beantwortet.

Auf der WE.FUNK06 ist
die Idee nun konkret vorangetrieben worden. Weimar,
Leipzig und Berlin setzten sich zusammen und
überlegten erste Schritte. Ein Jahr zuvor hatte man an gleicher Stelle erste
Überlegungen getroffen, nun konnte die zwischenzeitliche, sehr instabile
Kopplung (mit viel NAT gewürzt) deaktiviert werden, mit einer skalierbaren
Lösung in Griffweite. Die prototypische Einrichtung der neuen Verbindung folgte
noch am selben Wochenende.

Möglich soll die dauerhafte Kopplung der Netze durch die
Installation von so genannten VPN’s – Virtuellen Privaten Netzwerken werden. Ein
Virtual Private Network ist ein Computernetz, das zum Transport privater Daten
ein öffentliches Netz (zum Beispiel das Internet) nutzt. Teilnehmer eines VPN
können Daten wie in einem internen LAN austauschen. Die einzelnen Teilnehmer
selbst müssen hierzu nicht direkt verbunden sein. Genauso wie einzelne
Freifunk-Router in einem lokalen Netz können die „Freifunk-Wolken“ der
verschiedenen Städte verstanden werden. Diese können dann durch Links
miteinander vernetzt werden. Nicht nur ein stadtweites Netz, sondern ein großes
Freifunknetz ist das Ergebnis. Die freien Netze von Weimar und Leipzig konnten
bereits experimentell über eine Kabelverbindung per DSL miteinander verbunden
werden. Nun soll das Verbund-Experiment dauerhaft weitergeführt werden.

Auch bisher konnte sich theoretisch jeder mit entfernten
Netzen über Tunnel und VPN verbinden. Dies verlangte jedoch spezifische Kenntnisse
und einen nicht unbeträchtlichen Konfigurationsaufwand. Indem wir einige Server
der verschiedenen Freifunk-Netze dauerhaft miteinander koppeln, bestehen die
Verbindungen zwischen den Netzen ohne dass Teilnehmer eines Netzes ihren
Computer konfigurieren müssen, um gleichzeitig in verschiedenen Netzen präsent
zu sein. Die Konfiguration von VPN-Verbindungen auf einzelnen Rechnern zum
Beispiel für Audiostreaming entfällt hierdurch. Die Freifunker hoffen nun, dass
sie bald in der Lage sein werden die notwendigen Rechnerkapazitäten und
DSL-Verbindungen zur Verfügung zu haben, um das Experiment dauerhaft
fortzuführen.

Ein detailliertes Bild der Netze und des Verkoppelungsexperiments
Weimar-Leipzig gibt es auf http://wiki.freifunk-leipzig.public-ip.org/index.php/NetzkopplungWeimarLeipzig.

(Artikeltext u.a. auf Basis von Egmont)