Wissenschaftsladen Dortmund

Probleme und Lösungsansätze

Wie die Datenpakete von einem Rechner zum Anderen gelangen – das Routing – ist die technische Kernfrage des Internets. Das gilt auch für Freifunk-Netze. Allerdings unterscheiden sich die Bedingungen in Freifunk-Netzen an einigen Stellen von denen im „großen“ Internet. Deshalb lassen sich die Routing-Konzepte, die im Internet zur Anwendung kommen, nicht einfach 1:1 für Freifunk-Netze übernehmen. Wir haben uns die Besonderheiten des Routings in Freifunk-Netzen näher angeschaut.

Der aktuelle Anlass für diese Bemühung ist das „Rauschen“ in Freifunknetzen, in denen – wie hier in Dortmund – B.A.T.M.A.N. als Routingprotokoll eingesetzt wird. Dieses „Rauschen“ bedeutet permanentes Datenaufkommen, das auch ohne Nutzung des Freifunknetzes anfällt, nur um das Routing im Netz aufrecht zu erhalten. Da die Freifunknetze erfreulicherweise größer werden, wächst aber auch das unerfreuliche „Rauschen“, was bis zur Unbenutzbarkeit an DSL-Uplinks mit geringer Bandbreite führen kann, zB in ländlichen Gebieten. Daher haben einige Freifunk-Communities begonnen, ihr Netz in mehrere Teile aufzuspalten. Das ist mit Arbeit verbunden, hilft aber erstmal. Solange, bis die Teile (erfreulicherweise:) größer werden … ein Schelm, wer „Hydra“ dabei denkt.

Vor 10 Jahren hatte der WiLaDo das Freifunkprojekt DUDL mit aufgebaut. In dem damaligen Routing-Konzept war schon eine Lösungsidee enthalten, um das „Rauschen“ zu verhindern, nämlich die Gliederung des Netzes in verschiedene Routingbereiche. Dadurch blieb das in einem WLAN-Mesh unvermeidliche „Rauschen“ auf das WLAN-Mesh beschränkt. Allerdings waren damals nicht die Kräfte und Techniken vorhanden, um das daraus resultierende Problem vollständig zu lösen: das „Fußgängerzonenproblem“.

Das „Rauschen“ im heutigen Freifunk war nun der Anlass, die alte Baustelle noch einmal durchzuackern. Dabei herausgekommen ist ein erstaunlich einfacher Ansatz, der das Skalierungsproblem im Freifunk-Routing vermeiden kann. Dieser Ansatz wird aus einem gründlichen Abklopfen bekannter Routing-Strategien hergeleitet, und mit einem Prototyp konkretisiert. 

Freifunk – das erste Problem: WLAN mesh Chaos

Das offensichtlichste Problem des Routings in Freifunknetzen besteht darin, unter den schwierigen Randbedingungen eines WLAN adhoc Netzes optimales Routing zu erreichen. Im Gegensatz zu einer Kabelverbindung ändern sich in einem WLAN-Netz die vorhandenen Verbindungen und die Qualität der Verbindungen häufig. Dieses Problem ist mittlerweile für die Praxis ausreichend gut gelöst. Ein wesentlicher Schritt dazu waren die Entwicklung von angepassten Routingprotokollen (OLSR, B.A.T.M.A.N., Babel, …) sowie von Metriken (insb. ETX).

Freifunk – das zweite Problem: die lange Fußgängerzone

Weniger offensichtlich ist das Problem der entkoppelten Metriken, eher bekannt unter dem Namen “Fußgängerzonenproblem”. Betrachten wir als Beispiel eine längere Fußgängerzone, die nur an beiden Enden Uplinks in ein FF-Backbone Netz hat.

Zwischen diesen beiden Enden zieht sich ein WLAN mesh die Straße entlang. Befindet sich nun ein WLAN client am unteren Ende der Straße, so werden die von ihm ausgehenden Datenpakete Richtung Internet von dem FF-Router, an dem der client hängt, über den kürzesten Weg gemäß der mesh-Metrik Richtung Uplink geroutet. D.h. sie gehen über den Uplink am unteren Ende der Straße raus, was in dieser Situation auch optimal ist.

Bleibt aber die Frage nach dem retour traffic, der aus dem Internet zum client geht? Diese Frage ist übrigens nicht nur von akademischem Interesse, sondern auch von praktischem, da der download üblicherweise das Gros des client traffics ausmacht (Konsumiere!). Mit der Verbreitung von Freifunk entstehen auch größere Meshes, in denen suboptimales Routing bis zur Ungenießbarkeit führen kann. Und zwar dann, wenn das Routing im Backbone nicht die Metrik des Meshes berücksichtigt.

Der umgekehrte Fall ist quantitativ vernachlässigbar, wg. kaum upstream traffic. Außerdem hat ein Backbone deutlich mehr Bandbreite als die Uplinkverbindungen (VPN), die das Mesh mit dem Backbone verbinden. Hat zB der Uplinkrouter am oberen Ende der Straße einen dickeren Uplink (50/10 Mbit) und der am unteren Ende einen kleineren (10/1 Mbit), so wird traffic aus dem Backbone des Freifunk-AS vor allem über das obere Ende der Straße ins Mesh kommen – und dann nach längerer, verlustreicher Reise den client am unteren Ende der Straße erreichen. (Im Bild ist wegen der Übersichtlichkeit nur ein Mesh-Router auf der Strecke dargestellt. Das könnten aber auch 10, 20 oder noch mehr „Zwischenstationen“ sein.)

Diese Situation setzt voraus, dass der Backbone die jeweiligen Metriken zwischen Backboneroutern und Uplinkroutern berücksichtigt, zB indem die Metrik die Bandbreite des jeweiligen Uplinks oder die Latenz einbezieht. Das ist aber ohnehin sinnvoll, um zumindest die maximale einzelne downstream Bandbreite des Meshes auszunutzen.

Wenn die Metrik des Backbones keine Uplinks mit einbezieht, geschieht das Routing in Richtung Mesh eben zufällig, d.h. mal hat dieser, mal jener downstream traffic zum client das “Fußgängerzonenproblem”.

Die erste und heute überwiegend praktizierte Lösung für das Fußgängerzonenproblem besteht darin, im kabelbasierten Netzbereich das gleiche IGP zu fahren wie im WLAN adoc Mesh der Fußgängerzone. Dies führt zu Skalierungsproblemen, u.a. durch stark zunehmenden Routingtraffic.

Lösungsansatz: IGP-Kopplung

Die alternative und bisher unterbelichtete Lösung verwendet für beide Netzbereiche unterschiedliche IGPs. Die Routen werden zwischen den IGPs als externe Routen ausgetauscht, unter Beibehaltung der (kompatibel gewählten) Metrikwerte. So hat man weiterhin optimales Routing, aber die Topologieinformationen beider IGPs bleiben voneinander getrennt, wodurch das Routing die Skalierungsprobleme der ersten Lösung vermeidet.

Die Verallgemeinerung dieses Vorgehens nennen wir “Kopplung von IGPs = gemeinsame Metrik trotz Entkopplung der Topologien”. Um dieses einfache, geradezu triviale Konzept auszuarbeiten, wird zunächst untersucht, wie IGPs in der Praxis (bei den Großen[tm]) verbunden werden. BGP und vor allem OSPF areas liefern wichtige Ideen, sind aber nicht unmittelbar für IGP-Kopplung im FF verwendbar.

Als praktische Basis für die Umsetzung einer IGP-Kopplung betrachten wir routing suites. In diesen sind bereits verschiedene IGPs integriert, und mit ihrer Hilfe können Routen zwischen den IGPs innerhalb eines Grenzrouters austauscht werden. Da routing suites Alltag sind, kommt vmtl. niemand mehr auf die Idee, IGP-Kopplung als eigenständigen Begriff zu untersuchen.

IGP-Kopplung lässt sich am einfachsten als OSPF areas ohne backbone area verstehen (prekäres OSPF;). Durch das Fehlen der backbone area wird das Routing auf der Ebene der IGP-Kopplung aber zum distance-vector Routing. Auch das ergibt optimales Routing, kann aber Probleme machen, die bei link-state Routing nicht auftreten, insb. counting-to-infinity.

Nach intensiver Auseinandersetzung mit DV und Routingschleifen ergänzen wir die einfache IGP-Kopplung um eine Schleifenverhinderung. Diese benutzt einen zur Menge eingedampften Pfadvektor bei BGP (prekäres BGP;).

Nach einem Überblick über die Anforderungen zur Umsetzung einer solchen IGP-Kopplung wird eine konkrete Implementierung mit Bird als routing suite und OSPF als (in mehreren Instanzen auftretendes) IGP beschrieben.

Die komplette Geschichte:

• als pdf-Datei
• mit config-Dateien und Anhang im dortmunder Freifunk-Wiki:
  http://url.free.de/ffdo/Technik/Routing/Fussgaengerzonenproblem