wiki/Technik/Routing/Fussgaengerzonenproblem.page

---
title: Das Fußgängerzonenproblem
...

# Freifunk - das erste Problem: WLAN mesh Chaos

Das offensichtlichste Routingproblem des Freifunk 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.

![upstream](/img/fuzo-1.png)

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 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.

![downstream](/img/fuzo-2.png)

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".

Eine gute Lösung für dieses Problem muss also dafür sorgen, dass die Metrik des Meshes auch im Routing des Backbones berücksichtigt wird. Aber kein vernünftiger (d.h. kommerzieller) Backbonebetreiber wird sich das Gezappel, das in einem WLAN-Mesh an Routinginformationen unterwegs ist, in den Backbone holen wollen. Also keine Hoffnung :-( ... außer auf eigene FF-Backbones!

# Fußgängerzonenproblem - erste Lösung: 1 IGP für das ganze FF-Netz

Die offensichtlichste Lösung für das Fußgängerzonenproblem besteht darin, im kabelbasierten Netz (FF-Backbone) das gleiche Routingprotokoll zu fahren wie in den WLAN-Meshes. Diese Methode wird zZ in den Communities des FF-Rheinland und vmtl. auch in Berlin verwendet. Dass zZ im FF-RL das Routing auf Layer 2 abläuft (B.A.T.M.A.N. advanced) und nicht auf Layer 3 (wie in Berlin mit OLSR), ändert nichts am Grundproblem.

Durch die Ausdehnung des Routings in einem WLAN-Mesh auf das gesamte (FF-)Netz wird das Fußgängerzonenproblem so gelöst:

- der Router mit dem WLAN-client am unteren Ende der Straße schickt die von seinem client ausgehenden Pakete (bzw. frames bei L2-Routing) entsprechend der Metrik der (default-)Route, also wie bisher normalerweise über seinen Kabeluplink, da er von dort die (default-)Route mit der besten Metrik bekommt.

- Umgekehrt schicken die Router des FF-Backbone Pakete für den client zum Router am unteren Ende der Straße, da dieser die Route zum client mit der besten Metrik in Richtung FF-Backbone announced.

Im Beispiel hat zwar der untere Router (U) einen schwächeren Uplink zum Backbone (BB) als der Router (O) am oberen Ende (m(BB->U) > m(BB->O)), aber dafür kommt die Metrik für die Durchquerung der Fußgängerzone per WLAN hinzu, sodass (bei geeigneter Kostenfunktion m: Linkqualität -> Metrik) insgesamt gilt: m(BB->O) + m(O->U) > m(BB->U). Das ist aber keine Magie, sondern Designziel eines IGP, dass es innerhalb seiner Routingdomäne optimales Routing herstellt.

Je besser ein IGP und seine Metrik mit der Heterogenität der Übertragungsmedien (WLAN vs. Kabel) klarkommt, um so optimaler ist auch das globale Routing in diesem FF-Netz (= Backbone + Uplinks + Meshes). (ZB hat Babel differenziertere Möglichkeiten für die Metrik als B.A.T.M.A.N.) Weil optimales Routing in einem WLAN adhoc Mesh ein schwierigeres Problem ist als das Routing im Kabel, nimmt man sinnvollerweise das in den meshes verwendete IGP auch für's Kabel (FF-RL: B.A.T.M.A.N., Berlin: OLSR). (Umgekehrt liefert zB OSPF zwar ein prima Routing in großen Kabelnetzen, aber in einem WLAN adhoc mesh taugt es in der Praxis nicht, da es bestenfalls (im Point-to-Multipoint Modus) eine hop count Metrik verwenden kann. Und die kann geradezu fatal sein, weil "dank" WLAN dabei auch der link mit den übelsten Paketverlusten vom OSPF gern genommen wird, solange der Zielrouter noch mit einem hop durch die Luft erreichbar ist.)

Diese erste, einfache Lösung hat aber auch ihre Schattenseiten:

- Bei L2-Routing zB die riesige Broadcastdomäne, die B.A.T.M.A.N. über das ganze betrachtete Netz herstellt.
 
- Außerdem benötigt jeder Router auch für jeden client die Information, mit welchem Router dieser verbunden ist. Wie in der Realität zu beobachten, führt dies neben überwiegend unnützem Braodcasttraffic auch zu mehr Routinginformation. Und diese wird bei DV-Routing regelmäßig in eher kurzen Abständen durchs Netz geschickt, und trägt sogar mehr zum Grundrauschen bei, als der Broadcasttraffic der clients.

Broadcastrauschen kann man durch die Verwendung von L3-Routing vermeiden, und den Traffic des Routingprotokolls insb. durch Verwendung eines link-state Protokolls minimieren. Beides zusammen erreicht man zB mit OLSR.

Link-state hat in diesem Szenario aber auch eine Schattenseite:

- der Berechnungsaufwand für eine Topologie wächst bei guter Implementierung mit r * log(r) + v, wobei r die Anzahl der Router und v die Anzahl aller direkten Verbindungen zwischen Routern bezeichnet [s. Wikipedia](https://de.wikipedia.org/wiki/Dijkstra-Algorithmus#Zeitkomplexit.C3.A4t.). Konkret kann das bedeuten, dass ein Router in einem 10 mal größeren Netz das 30fache an Berechnungszeit braucht, um den optimalen SPF-Spannbaum zu allen anderen Routern zu ermitteln.
 
Und je größer das Netz und vor allem der Anteil an WLAN adhoc meshes darin ist, desto häufiger ändert sich die Topologie. (Zumindest im vorigen Jahrzehnt führte dieser Zusammenhang zur (auch thermischen;) Überlastung der FF-Plasterouter in großen OLSR Netzen.)

Zusammenfassung: 1 IGP für ein ganzes FF-Netz funktioniert, aber skaliert nicht beliebig.
 
# Fußgängerzonenproblem - zweite Lösung: 2 IGPs
 
Offenbar kaum beachtet ist in der Praxis bisher ein alternativer Denkansatz geblieben, nämlich die Trennung eines FF-Netzes in zwei Routingdomänen:

- ein IGP wird im Kabelteil des Netzes gesprochen,

- das andere IGP in dem oder den WLAN meshes.

Der Grund für diese Unterbelichtung dürfte vor allem darin liegen, dass es bisher keine einfache Möglichkeit gibt, Routinginformationen zwischen FF-relevanten IGPs auszutauschen. Frühere Bemühungen waren das [OLSRv1-plugin für Quagga](http://www.olsr.org/git/?p=olsrd.git;a=tree;f=lib/quagga;h=413b69f912fb014bd9ffe7e3b9868e103c9ab9bf;hb=HEAD) sowie [OLSRv1 als Teil von XORP](https://github.com/greearb/xorp.ct/tree/master/xorp/contrib/olsr). Letztere verwendet nur die einfache Metrik des "offiziellen" OLSRv1 [RFC 3626](http://tools.ietf.org/html/rfc3626) und ist daher in WLAN adhoc meshes praktisch unbrauchbar - denn ohne ETX Metrik o.dgl. geht in dem adhoc Chaos des WLAN Gewabers leider nix. Echte Hoffnung verspricht aber die zZ (Anfang 2016) laufende Integration von [Babel in Bird](http://article.gmane.org/gmane.network.bird.user/4573).
 
IGPs, die für WLAN adhoc Meshes entworfen werden, hatten traditionell eher schwache Unterstützung für externe Routen. Verständlich, da viel mehr als die default Route nicht gebraucht wurde. Außerdem hatte wohl niemand den Plan, Transittraffic über ein WLAN Gewaber zu schicken.
 
Beispiel: die externen Routinginformationen bei OLSRv1 ("HNA") enthalten nur das Ziel der Route, aber nicht die Entfernung dorthin (Metrik). Ein OLSRv1 Mesh macht daher, wenn es mit einem anderen IGP "peert", immer "hot potato" Routing (auch "best exit" genannt). Das kann aber in straßenüblichen FF-meshes dazu führen, dass der ausgehende Traffic eines clients zu einem Uplink router geht, der bereits einen ziemlich verstopften Uplink hat. Wenn dieser verstopfte Uplink so grade noch die gelegentlichen Routinginformationen durchkriegt, aber zB die zu einem Stream gehörigen ACK Pakete eines clients im oberen Sekundenbereich verzögert oder gar verwirft, dann entsteht Frust beim client. Insb. dann, wenn er wüsste, dass er über einen Nachbarrouter problemlos konsumieren könnte, dieser aber leider eine etwas größere (OLSR-ETX-)Metrik hat als der Router mit dem überlasteten Uplink - aber dafür einen dicken freien Uplink.

Dieses "hot potato Problem" kann glücklicherweise mit OLSRv2 [RFC 7181](http://tools.ietf.org/html/rfc7181) vermieden werden, denn dort kann die Metrik externer Routinginformationen importiert werden. Bei erfolgreicher Integration von Babel in Bird (s.o.) wäre der Import externer Metriken ebenfalls möglich. (Eine sogar für OLSRv1 gangbare Variante wäre es, die Grenze zwischen den IGPs nicht in den Uplinkroutern an der Straße zu ziehen, sondern in den VPN-Endpunkten, zB "Supernodes". Aber dann hat man den für ein WLAN adhoc Mesh unvermeidlichen Routingtraffic auf den Uplinks.)
 
Zusammenfassung: Die Möglichkeit, zwei oder mehr IGPs zu verwenden, um das Fussgängerzonenproblem zu lösen, hängt von der Fähigkeit der beteiligten IGPs ab, externe Routinginformationen zu nutzen.

(BTW, auch bei B.A.T.M.A.N. könnte man dank [BLA](https://www.open-mesh.org/projects/batman-adv/wiki/Bridge-loop-avoidance) mehrere Instanzen über einen normalen (realen oder virtuellen) L2-Switch zusammenschalten. Selbst ohne Metrikübermittlung wäre dann das Routing zwischen den Instanzen optimal, muss aber immer über den Switch laufen. Bei dieser Konstruktion teilt man das Routing des Netzes zwar in zwei oder mehr Bereiche auf, sodass der Routingtraffic in jeder Instanz nur mit der Größe der Instanz wächst, nicht mit der Größe des gesamten Netzes - abgesehen von allen MAC Adressen aus den anderen Instanzen, die in den B.A.T.M.A.N. Tabellen auf den Routern im Innern der Instanz als clients der Router am Switch erscheinen ("externe Routen"). Mglw. könnte so eine Kopplung auch durch die Präsenz zweier Instanzen innerhalb eines Routers erfolgen: "As of 2010.2.0 it is possible to let a single mesh node participate in mutliple mesh clouds at the same time which makes it necessary to assign interfaces to individual mesh clouds and having multiple batX interfaces." [B.A.T.M.A.N. Doku](https://www.open-mesh.org/projects/batman-adv/wiki/Tweaking)

Fazit: Mglw. könnte man mit BLA größere B.A.T.M.A.N. Netze bauen als mit einer einzelnen Instanz, aber wer bitteschön will denn noch größere Broadcastdomänen, wie sie hierbei - mit Hilfe des Switches - zustandekämen? Allerdings besteht ein interessanter Aspekt des Routings auf Layer 2 darin, dass interessierte Freifunkerinnen unmittelbar eine Verbindung auf Layer 2 zueinander aufbauen können, was die Nutzungsmöglichkeiten einer freien Netzwerkinfrastruktur erweitert. Doch dafür müssen wohl andere Lösungen untersucht werden, als die Ausdehnung des L2 Routing auf das FF-Kabelnetz.)

## Anmerkung: Die Begriffe "Autonomes System" und "externe Route"

Weil die Verwendung mehrerer, gleichrangiger IGPs innerhalb eines Netzes für die Leserin mglw. ungewohnt ist, sei hier betont, dass in diesem Text mit dem Begriff "externe Route" nicht (nur) solche Routen gemeint sind, die aus einem anderen AS (AS im Sinne eines EGP) stammen, sondern alle Routen, die nicht aus dem betrachteten IGP stammen. "Extern" sind hier also auch alle Routen, die aus einem benachbarten IGP kommen, und nicht nur die per eBGP gelernten. "AS" hat bei IGP eben eine andere Bedeutung als bei EGP. So heißt es in der OSPF Spezifikation [RFC 2328](http://tools.ietf.org/html/rfc2328):

    Autonomous System
       A group of routers exchanging routing information via a
       common routing protocol. Abbreviated as AS.

Dieser Text hier verwendet dafür stattdessen den Ausdruck "IGP Instanz", um den Begriff "AS" eindeutig verwenden zu können, d.h. den EGPs zu überlassen. Beim Lesen der noch folgenden Zitate aus der OSPF Spezifikation also bitte dran denken, das "AS" aus dem Zitat mit "IGP Instanz" zu übersetzen.

## Ein Konzept für die Kopplung von IGP Instanzen

Im Kontext des Fußgängerzonenproblems besteht die wesentliche Motivation für einen Verbund verschiedener IGPs in einem (FF-)Netz darin, das Fluten / die Flut von Routinginformationen zu minimieren, und trotzdem im ganzen Netz optimales Routing zu erzielen, wie man es innerhalb eines einzelnen IGPs kennt. Die zentrale Gleichung dieses Ansatzes lautet:

    Kopplung von IGPs = gemeinsame Metrik trotz Entkopplung der Topologien

Das ist übrigens nichts Neues, sondern wird schon in der OSPF Spezifikation formuliert. (Zitat s.u. im Abschnitt "OSPF areas").

Leider kommt OSPF selbst nicht als (einheitliche) Lösung für FF-Netze in Frage, und zwar wegen seiner Unbrauchbarkeit in WLAN adhoc Meshes (s.o.). Wie aber ein Netz aufgebaut werden kann, dass diese Idee nicht durch areas innerhalb einer OSPF Instanz realisiert, sondern mit mehreren eigenständigen IGP Instanzen, soll weiter unten noch untersucht werden.

## Globale Metrik auch bei unterschiedlichen IGPs?

Aus der gewünschten Metriktreue (zwecks global optimalem Routing) folgt nicht zwingend die Verwendung genau gleicher Metriken innerhalb der beteiligten IGP Instanzen. Diese müssen nur an den Grenzen der IGPs in eine globale (gemeinsame) Metrik umgerechnet werden, wobei die strenge Monotonie der jeweiligen Metriken erhalten bleibt. Der Einfachheit halber lassen wir diesen Schritt im Folgenden weg und gehen von gleichbedeutenden (und praktischerweise arithmetischen) Metrik-Werten in allen beteiligten IGPs aus. (Zu allgemeineren Metriken lohnt es sich, die bereits erwähnte Babel RFC zu goutieren.)

Vor dem Weiterlesen sollte sich der Leser nochmal vergegenwärtigen, dass optimales Routing zwischen Routingdomänen nicht auf die Topologieinformationen aus den verschiedenen Routingdomänen angewiesen ist, sondern nur auf deren Metriken, die als externe Routinginformation in das jeweilige IGP exportiert ("redistributed") werden. (S.o. die "zentrale Gleichung" und das OSPF-Zitat.)

## So machen's die Großen[tm] 

### BGP - MED
 
Die offensichtliche und übliche Möglichkeit zur Verbindung von IGPs ist die Verwendung eines EGP (d.h. eBGP). Im FF-Kontext würde also am besten BGP über den Uplinks zwischen Straßenroutern und dessen VPN-Endpunkt gesprochen werden. (iBGP ginge auch, aber führt hier wg. des "i" nur zu Verwirrung.) Die Metriken können bei BGP über das MED Attribut der BGP Routen zwischen den verschiedenen IGPs transportiert werden. (MED = Multi-Exit Discriminator, s.a. [RFC 4451](http://tools.ietf.org/html/rfc4451).)

Nachteil dabei ist, 

- dass BGP nicht gerade für die FF-straßenüblichen (Konsumenten-)Uplinks gedacht war;-) S. zB route flap dampening bei überlasteten Uplinks. 

- Außerdem tauscht BGP seine Routinginformationen über TCP aus, kann also nur eine konfigurierte Liste von Nachbarn ansprechen, sie aber nicht per Broadcast oder Multicast "adhoc" finden. Das bedeutet im FF-Szenario, dass die VPN-Endpunkte auch ebenso viele BGP-peers konfigurieren müssten, wie sie VPN clients (Konsumentenuplinks) bzw. peers (zB [IC-VPN](http://wiki.freifunk.net/IC-VPN)) versorgen. Da BGP ein vergleichsweise aufwändiges Protokoll ist, bedeutet diese Lösung aus dem Kontext der Großen[tm] aber im FF-Kontext eher eine Belastung der "Supernodes" (von der Belastung der Konfigurationsmechanik und der Plasterouter mal zu schweigen;). 

Zusammenfassung: BGP-MED ist eine echte Option, kann aber in der Praxis Probleme machen, insb. beim Skalieren.

### OSPF areas 

OSPF erreicht seine Reduktion des Routingtraffics auf zwei Ebenen. Zunächst dadurch, dass OSPF ein link-state Protokoll ist. Dessen Kern ist die link-state Datenbank (LS DB), die auf jedem Router der betrachteten area den gleichen Stand haben muss. Nur unter dieser Voraussetzung kann jeder Router autonom den SPF-Baum mit den kürzesten Pfaden zwischen ihm und allen anderen Routern berechnen, so dass die von den verschiedenen Routern getroffenen Routingentscheidungen zu einem schleifenfreien und optimalen Routing führen. Der Umfang der RFC 2328 (240 Seiten) rührt auch von der Komplexität, die Konsistenz der LS DBs auf den verschiedenen Routern unbedingt sicherzustellen - und zwar mit möglichst wenig Routingtraffic. 

Hinzu kommt das Konzept des Designated Routers (DR) in jedem Subnetz der area, das eine broadcast (oder zumindest NBMA) Topologie hat:

    Designated Router 
            Each broadcast and NBMA network that has at least two  
            attached routers has a Designated Router.  The Designated  
            Router generates an LSA for the network [...]  
            The Designated Router concept enables a reduction in the  
            number of adjacencies required on a broadcast or NBMA  
            network.  This in turn reduces the amount of routing  
            protocol traffic and the size of the link-state database.

Wie wichtig solch ein "Detail" für größere Netze sein kann, lässt sich auch an der oben erwähnten Formel r * log(r) + v ablesen. Das v steht darin für die Anzahl der direkten Verbindungen zwischen Routern. In einem broadcast (oder NBMA) Subnetz mit r' Routern, die ein interface in dieses Subnetz haben, wächst die Verbindungsanzahl des Subnetzes (v') quadratisch mit der Anzahl der Router:

v' = 1 + 2 + 3 + ... + (r' - 1) = [r' * (r' - 1) / 2](https://de.wikipedia.org/wiki/Vollst%C3%A4ndiger_Graph)

(Anmerkung: OLSR ist auch ein link-state Protokoll, und dort lässt sich ein zum DR ähnliches Konzept entdecken: multipoint relay (MPR).)
  
Die zweite Ebene der Reduktion von Routingtraffic besteht darin, die OSPF Instanz (in OSPF-Sprech: das "AS") in areas aufzuteilen, die jeweils eigene, unabhängige LS DBs haben. Wenn man zB eine OSPF Instanz in a gleich große areas aufteilt, ergibt sich als durchschnittliche Berechnungskomplexität für jeden Router:
 
r/a * log(r/a) + k/a = r/a * (log(r) - log(a)) + k/a
 
D.h. schon eine Aufteilung in zwei areas kann bei größeren Netzen den (Berechnungs-)Aufwand spürbar verringern. Ähnlich folgt aus der Halbierung des Konnektivitätsgraphen - und damit der LS DB - die entsprechende Reduktion des Routingtraffics, der für die Synchronisation der LS DBs auf den Routern innerhalb einer area anfällt.
 
Die Routinginformationen aus der anderen area tauchen nur als area-externe Routen auf. D.h. wenn sich eine solche Route ändert, so muss jeder Router der betrachteten area *nicht* den SPF Baum neu berechnen -  sondern nur die zu dieser Route gehörige Zeile in der Routingtabelle (RIB) ändern. Für Metrikänderungen braucht es dazu nur eine Addition (neue Metrik = neue externe Metrik + unveränderte SPF Distanz).
 
Zusammenfassung: OSPF areas sind ein optimierter Kandidat um größere Netze so zu strukturieren, dass der Routingtraffic minimiert wird. Doch leider taugt OSPF nicht für WLAN adhoc Meshes:-(

## And the winner is ...

Beide Varianten aus der Welt der Großen führen jeweils für sich alleine nicht zum FF-Glücklichrouting. Aber in einem üblicherweise heterogenen FF-Netz gibt es ja verschiedene Problemzonen, die mit verschiedenem Werkzeug bearbeitet werden könnten und sollten:

- Im WLAN adhoc Mesh braucht es auf jeden Fall ein darauf angepasstes Protokoll (OLSR, B.A.T.M.A.N., Babel, ...).

- Im stabilen Teil innerhalb des AS (größere Uplinks, VPN peering Netze, Richfunknetze) kann OSPF für minimalen Routingtraffic sowie schnelle Konvergenz sorgen.

- Und nach außen schließlich, beim Austausch mit dem "echten" Internet muss man sowieso BGP sprechen. (Evtl. auch schon auf den Uplinks, s.o. BGP-MED.)

Zusammenfassung: the winner is ... die Integration verschiedener Routingprotokolle unter Verwendung einer globalen Metrik. (Mit "global" ist hier (noch;) nicht die ganze Welt(herrschaft;;) gemeint, sondern alle Teile eines (heterogenen) FF-Netzes, die Routinginformationen (und ergo Datenpakete) direkt mit mindestens einem anderen Teil des betrachteten FF-Netzes austauschen.