Meshing

Überblick

Im Gegensatz zum WLAN-typischen Client-Server-Betrieb (ein Access Point als Server, Endgeräte als Client - der sogenannte Infrastructure-Modus), bei dem Datenpakete sternförmig vom Server zu den Clients verteilt werden, tauschen bei Meshing die einzelnen Rechner/Netzknoten direkt Daten miteinander aus (Peer-to-Peer- oder Ad-Hoc-Modus).

Die Routen, auf denen die Daten durch das Mesh-Netzwerk (das Mobile Ad-Hoc Network, MANET) geschleust werden, werden dynamisch auf Basis der Verfügbarkeit der Knoten und der Verbindungsqualität und -auslastung berechnet. Es existieren zahlreiche unterschiedliche Ansätze (Routingprotokolle), diese Routen zu berechnen. Hat die Routing-Software Kontakt zu anderen Knoten im Mesh aufgenommen, ruft sie Informationen darüber ab, wer noch im Netzwerk ist, und errechnet Pfade zu vorhandenen Knoten (ad-hoc routing). Hat man etwa einen Laptop mit WLAN und Meshing-Software und trifft auf Gleichgesinnte, baut sich das Netzwerk auf, und man kann Daten austauschen oder unter Umständen über mehrere Zwischenstationen ins Internet gelangen.

Elektra hat zu der Idee der Mesh-Netzwerke, die technische Grundlage von Freifunk sind, einen ausführlichen Beitrag im Chaosradio Express gemacht, der sehr empfehlenswert ist.

Die Vorteile von Meshing

Netzabdeckung: Jeder Knoten fungiert als „Repeater”: Es wird sehr gute räumliche Abdeckung mit WLAN erreicht.

Zuverlässigkeit: Kein Single Point Of Failure. Mehrere Knoten können gleichzeitig Dienste wie z.B. Übergang in „den Rest des Internets” zur Verfügung stellen; fällt ein Übergangsknoten aus, übernimmt ein anderer seine Aufgabe.

Ressourcensparsamkeit: Jeder Knoten ist zugleich Sender, Empfänger und Verteiler (quasi AP, Client, Repeater und Switch). Außerdem wird vom gesamten Meshing-Netzwerk nur ein Kanal im WLAN benötigt - andere Techniken brauchen in der Praxis meist einen Kanal pro Sendestation/AP.

Weiteres: Je nach benutztem Protokoll und Software sind andere Features wie z. B. Roaming möglich.

Die Nachteile von Meshing

Softwareanfordungen: In normalen WLAN-Geräten ist die für Meshing nötige Software nicht in der Firmware enthalten, kann aber bei bestimmten – in der Regel Geräten, auf denen Linux installiert ist – recht einfach eingespielt werden.

Aufwand: Genügend Teilnehmer müssen vorhanden sein, um ein stabiles Netz aufzubauen, das größere Distanzen überbrücken kann. Die Infrastruktur muss zudem gewartet werden, zum Beispiel bei Software-Updates. Diese müssen häufig zeitnah bei allen Teilnehmern im Netz erfolgen, wenn zum Beispiel Routing-Protokolle verändert werden.

Routingverfahren allgemein

Um eine zielgerichtete Weiterleitung der Daten in einem mobilen Ad-hoc-Netz zu ermöglichen, kommen spezielle Routingprotokolle zum Einsatz. Diese haben die Aufgabe, einen Pfad vom Quell- zum Zielknoten zu bestimmen. Je nach verwendeter Metrik sollte dieser z. B. möglichst kurz sein, oder möglichst gering belastete Regionen des Netzes nutzen. Weitere Anforderungen an die Protokolle sind möglichst kleine Routingtabellen, welche ständig aktualisiert werden müssen, wenn Knoten verschwinden, sich bewegen oder neue erscheinen. Die Zeit und die Anzahl der Nachrichten, die zum Auffinden einer Route benötigt werden, sollten möglichst gering sein.

Auf Grund der speziellen Bedingungen in einem mobilen Ad-hoc-Netzwerk können die üblicherweise im Internet eingesetzten Routingalgorithmen nicht verwendet werden. Die wesentlichen Gründe hierfür sind:

• Knoten haben kein Vorwissen über die Topologie des Netzwerkes, sie müssen diese selbst erkunden
• keine zentralen Instanzen zum Speichern von Routinginformationen
• Mobilität der Knoten und damit verbundener ständiger Topologiewechsel
• Wechselnde Metrik der Übertragungsstecken z.B. durch Interferenzen
• Beschränkte Ressourcen der Knoten (z.B. Systemleistung, Energieverbrauch)

Welche Routing-Protokolle gibt es für Meshing?

Es gibt mehr als 70 konkurrierende Entwürfe für das Mesh-Routing. Eine Auflistung gibt es z.B. auf Wikipedia dazu oder auch hier im Wiki unter Routingprotokolle. Eine Möglichkeit der Klassifikation besteht in der Einteilung der Protokolle hinsichtlich des grundsätzlichen Ansatzes. Diese Ansätze werden im Folgenden vorgestellt.

Topologiebasierte Routingverfahren

Die topologiebasierten Routingverfahren kommen ohne genaue Informationen über die Positionen der Knoten des mobilen Ad-hoc-Netzes aus. Ihnen genügen Informationen über die Nachbarschaftsbeziehungen der Knoten, also welche Knoten eine direkte Verbindung haben und somit ohne die Hilfe anderer Knoten miteinander kommunizieren können. Diese Informationen werden meistens durch den Versand so genannter HELLO-Pakete gewonnen.

Proaktive Verfahren

Proaktive Routingverfahren bestimmen die zu verwendenden Pfade zwischen zwei Knoten bereits bevor diese tatsächlich benötigt werden. Sollen dann tatsächlich Daten verschickt werden, so muss nicht auf die Bestimmung des Pfads zum Zielknoten gewartet werden. Nachteilig ist dafür jedoch, dass diese Verfahren viele Kontrollpakete verschicken um Pfade zu bestimmen, die womöglich später nicht benötigt werden.

Beispiele:

• "Optimized Link State Routing" (OLSR)
• "Better approach to mobile ad-hoc networking" (B.A.T.M.A.N.)

Reaktive Verfahren

Im Gegensatz zu den proaktiven Verfahren bestimmen reaktive Routingverfahren für mobile Ad-hoc-Netze die benötigten Pfade zwischen zwei Knoten erst, wenn diese tatsächlich benötigt werden. Daraus ergibt sich, dass das erste Datenpaket einer Verbindung erst mit einer geringen Verzögerung versendet werden kann, da zunächst auf den Abschluss der Routenbestimmung gewartet werden muss. Dafür werden allerdings auch nur Kontrollpakete versendet, wenn tatsächlich Daten verschickt werden und dies zur Routenbestimmung notwendig ist. Dies schlägt sich positiv im Energieverbrauch der Knoten nieder.

Beispiel: "Ad hoc On-Demand Distance Vector" (AODV)

Hybride Verfahren

Hybride Verfahren kombinieren proaktive und reaktive Routingverfahren. Dabei soll das Ziel erreicht werden, die Vorteile der beiden Ansätze in einem neuen Routingprotokoll zusammenzufassen. Beispielsweise kann in einem lokal beschränkten Bereich ein proaktives Verfahren eingesetzt werden, während für weiter entfernte Ziele ein reaktives Verfahren eingesetzt wird. Dies vermindert die Belastung des Netzes durch Kontrollpakete, die bei einem rein proaktiven Verfahren über das gesamte Netz versendet würden. Trotzdem stehen für lokale Ziele sofort Pfade zur Verfügung, ohne dass auf deren Bestimmung wie bei einem rein reaktiven Verfahren gewartet werden müsste. ZRP ist ein Routingprotokoll, das diesen Ansatz umsetzt.

Beispiel: Zone Routing Protocol (ZRP)

Positionsbasierte Routingverfahren

Positionsbasierte Routingverfahren nutzen Informationen über die genauen Positionen der Knoten. Diese Informationen werden z. B. über GPS-Empfänger gewonnen. An Hand dieser Informationen lässt sich der beste Pfad zwischen Quell- und Zielknoten bestimmen.

Beispiel: LAR

Welche Projekte gibt es?

Eine Übersicht der Freifunk-Communities gibt es unter community.freifunk.net und Freifunk Weltweit

Siehe Auch

• Routingprotokoll
  • OLSR - Optimized Link State Routing
  • B.A.T.M.A.N. - better approach to mobile ad-hoc networking
• Pico Peering Agreement - Vorlage zu Richtlinien im Umgang mit Freifunk-Netzwerken