STARTSEITE | GLOSSAR | DOWNLOADS | HÄUFIGE FRAGEN (FAQ) | IMPRESSUM




Idee Magazin Wiki blog Community









NEUE FREIKARTE ANLEGEN











ANMELDEN



5656 registrierte freifunker






















FREIFUNK.NET | wiki | Meshing

Meshing

last edited 2 years ago by MarioBehling
Bitte verwendet das neue Wiki unter wiki.freifunk.net

Im Gegensatz zum WLAN-typischen Client-Server-Betrieb (ein Access Point als Server, Endgeräte als Client), 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 Meshing-Netzwerk (das Mobile Ad-Hoc Network, MANET) geschleust werden, werden dynamisch auf Basis der Verfügbarkeit der Knoten und auf Basis der Verbindungsqualität und -auslastung berechnet. Elektra hat zu diesem Thema einen ausführlichen Beitrag im Chaosradio gemacht, der sehr empfehlenswert ist: http://chaosradio.ccc.de/archive/chaosradio_express_016.mp3

Um Meshing - "das Maschen" - zu verstehen kann man sich zunächst ein Maschennetz vorstellen. Ein Maschennetz (Mesh Network) ist ein Nachrichtennetz bei dem jeder Knoten mit mindestens zwei weiteren Knoten verbunden ist. Ein vollständiges Maschennetz ist vorhanden, wenn alle Knoten unmittelbar miteinander verbunden sind. Maschennetze stellen einen nahezu idealen Ansatz für große und skalierbare Netzwerke dar.

In der Technik versteht man unter einem Maschennetzwerk (Meshed Network) ein drahtloses Netz das sich selbstständig organisiert. Entsprechende Software ist in der Lage dynamisch nach anderen Netzwerkpartnern zu suchen. Hat sie Kontakt aufgenommen, ruft sie Informationen darüber ab wer noch im Netzwerk ist, und errechnet automatisch die besten Pfade zu vorhandenen Knoten (ad-hoc routing). Hat man etwa einen Laptop mit Wlan-Karte und Meshing-Software und trifft man auf Gleichgesinnte, baut sich das Netzwerk auf, und man kann Daten austauschen, kommunizieren, oder unter Umständen über mehrere Zwischenstationen ins Internet gelangen. Dies ist die Idee hinter freifunk-Netzwerken.


Technische Funktionsweise

Mit Mesh-Routing-Protokollen können Netze gebaut werden, die sich dynamisch den Gegebenheiten anpassen. Neue Teilnehmer werden einfach Teil des Netzes, ohne dass jemand händisch Routing-Einträge oder ähnliches machen muss. Dabei erweitert jeder neue Teilnehmer(in) das Netz, erhöht die Gesamt-Kapazität des Netzes und ermöglicht somit weiteren Zugang zu bekommen. Das entstehende Netz ist nicht hierarchisch organisiert, sondern basiert auf einem peer-to-peer Prinzip, bei dem jeder auch Pakete für andere routet (siehe PicoPeeringAgreement?).

Es gibt diverse Protokolle, die Meshing-Netzwerke realisieren, z.B. das ältere MobileMesh? oder das neuere OLSR. Diese Protokolle ermöglichen, dass sich die Wlan-Karten im Ad-Hoc-Modus wie Relaisstationen verhalten. Durch den Betrieb von Relais lässt sich die Reichweite des Funknetzes sehr weit ausdehnen. Jede Station spürt eventuelle Nachbarn auf und fragt diese, zu wem sie noch Kontakt haben, wie gut die Verbindung ist, und so weiter. Daraus entsteht dynamisch eine Routingtabelle. Wenn eine gewisse Menge von Computern, auf denen das Protokoll läuft, sich in einem Gebiet aufhalten - sich eine Mobile-Mesh-Wolke gebildet hat - ist jedes Gerät mit jedem anderen Gerät verbunden. Mit dieser Methode lässt sich ein MAN (Metropolitan Area Network) oder auch MANET (Mobile Ad-Hoc Network) aufbauen.

Wireless Mesh Networking ist ein vermaschtes Netz, das in einem Wireless LAN implementiert ist. Ein Mobiles Ad-hoc-Netz (MANet?, auch Mesh Netz) ist ein selbstkonfigurierendes Netz, das meist auf Basis eines Funknetzes aufgebaut ist.

Innerhalb des Netzes können mobile Geräte, wie z.B. Mobiltelefone, Kleincomputer oder Laptops, sofort eine Verbindung zueinander aufbauen, ohne dass eine übergeordnete Infrastruktur (wie z. B. Wireless Access Points) benötigt wird. Jedes Gerät (Knoten) dient hierbei nicht nur als Sende- und Empfangsstation für Sprache oder Datenübertragung, sondern auch als Router für andere Teilnehmer. Wichtig ist daher kooperatives Verhalten, da oft knappe Ressourcen wie Rechenzeit, Energie und Bandbreite für andere Teilnehmer bereitgestellt werden müssen. Ähnlich wie in Peer-to-Peer-Netzen führt die Kommunikation über MANets? zu günstiger Lastverteilung, da es keine zentralen Instanzen gibt. Die Bewegung der Knoten erfordert aufwändige Routingverfahren, weil die Tabellen für die Weiterleitung von Datenpaketen ständig aktualisiert werden müssen.

Funktionsweise

  1. direkte Verbindung: die einzelnen Knoten sehen sich und können miteinander kommunizieren.
  2. indirekte Verbindung: die einzelnen Knoten sind zum Teil so weit voneinander entfernt, dass sie nicht direkt miteinander kommunizieren können. Hierbei leiten die dazwischen liegenden Knoten die Daten weiter. Auf diese Weise kann ein fast beliebig großes, sich selbst verwaltendes Netz entstehen.


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, dass 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 Protokolle gibt es für Meshing?

Viele ;-). Wikipedia-Übersicht: http://en.wikipedia.org/wiki/Ad_hoc_protocol_list

Weit verbreitet sind OLSR und das ältere MMRP. Die meisten Freifunk-Netze basieren ebenfalls auf OLSR.

Routing-Protokolle

Es gibt mehr als 70 konkurrierende Entwürfe für das Routing der Pakete durch ein Mobiles ad-hoc / Maschennetzwerk. Eine Klassifikation der Routingprotokolle kann durch Anzahl der Empfänger getroffen werden:

  • unicast Routing - Ziel der Datenübertragung ist ein einzelner Knoten
  • multicast Routing - Ziel sind mehrere Knoten
  • geocast Routing - Ziel sind alle Knoten in einem bestimmten geografischen Bereich
  • broadcast Forwarding - Ziel sind alle Knoten in der Reichweite des Senders

Eine andere Möglichkeit der Klassifikation besteht in der Einteilung der Protokolle hinsichtlich des grundsätzlichen Ansatzes. Diese Ansätze werden im Folgenden vorgestellt.

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. Ein Beispiel für ein positionsbasiertes Routingprotokoll ist LAR.

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. Ein Beispiel für ein Protokoll aus dieser Klasse ist das "Optimized Link State Routing" (OLSR).

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. Das Protokoll "Ad hoc On-Demand Distance Vector" (AODV) ist ein Beispiel für ein Protokoll dieser Kategorie.

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.

Kommerzielle Bedeutung

2004 ist das Thema noch ziemlich akademisch und es existieren fast ausschließlich einige Pilotprojekte. Die Übernahme von MeshNetworks?, einem führenden Anbieter im Bereich mobiler Ad-hoc-Netze, durch Motorola Ende 2004 zeigt, dass die Industrie hier mit stark wachsenden Märkten rechnet.


Welche Software gibt es für Meshing?

OLSRD dürfte zur Zeit die empfehlenswerteste Implementierung sein (OLSR-Protokoll). Für den Linksys WRT54G(S) gibt es dafür hier die FreifunkFirmware. Etwas älter ist MobileMesh?, eine Implementierung des Protokolls MMRP.


Welche Projekte gibt es?

In Berlin, Rostock, Weimar und Dresden laufen zur Zeit die größten öffentlichen Meshing-Experimente. Beteiligen können sich alle, die einen WLAN-fähigen Computer haben oder über einen linuxfähigen Access Point verfügen. Mehr Infos findet sich unter OlsrFreifunkNet.

Meshing-Projekte:


Siehe Auch


Weblinks







TEILT IDEEN IM WIKI











SEITE BEARBEITEN






Ergänze Deine Inhalte an sinnvoller Stelle innerhalb dieser Seite.










ÄNDERUNGEN ANZEIGEN






Vorherige Versionen dieser Seite.










SEITE ABONNIEREN






Du wirst über Änderungen an dieser Seite per E-Mail informiert. (Momentan 7 Abonnementen)










BACKLINKS






Verweise von anderen Wiki-Seiten auf diese Seite.










WIKI-ÄNDERUNGEN






Letzte Änderungen im gesamten freifunk.net Wiki.


Seite in der Wiki-Sitemap anordnen:











UNTERORDNEN




Neue Oberseite festlegen.









NEU ERSTELLEN




Neue Unterseite anlegen.






 
  Seitenanfang