wiki/Technik/Richtfunk/MSTP.page

---
title: MSTP im Richtfunknetz
toc: yes
...

Diese Seite beschäftigt sich mit den Möglichkeiten, die sich durch die Verwendung von MSTP in Richtfunknetzen ergeben, sowie ihrer praktischen Umsetzung. Zunächst aber etwas Kontext zur Motivation der dann folgenden technischen Details.

# Anforderungen an das Richtfunknetz

## Redundanz

Das Richtfunknetz soll auch redundante Verbindungen enthalten. Dies soll vor allem vermeiden, dass das Netz durch den Ausfall einer einzelnen Verbindung oder einzelner Standorte partitioniert wird. Potentiell bedeuten mehr Links aber auch mehr insgesamt verfügbare Bandbreite innerhalb des Netzes und weniger Umwege für Datenpakete, die zwischen den Standorten unterwegs sind. Die Möglichkeit von beliebigen Topologien (statt nur schleifenfreien = baumförmigen) macht auch das Wachstum des Netzes flexibler. So ähnlich wie bei den "klassischen" Freifunk-adhoc-Meshes in der Luft, die sich leicht erweitern lassen und damit in Nachbarschaften ausbreiten können.

## Layer 2

Das Richtfunknetz soll nicht als reiner Zubringer zu einem zentralen Uplink konzipiert werden, sondern auch  mehrere Uplinks gut nutzen können. Außerdem sollte es flexibel genug sein, um weitere Nutzungsmöglichkeiten für die Bevölkerung im Viertel und dann perspektivisch in der ganzen Stadt zu eröffnen. Dies macht eine auf das gesamte Richtfunknetz ausgedehnte Layer 2 Infrastruktur wünschenswert, weil dadurch das Richtfunknetz den Nutzungen gegenüber konzeptionell neutraler wird. Für die Nutzungen stellt das Richtfunknetz VLANs zur Verfügung, die zwischen den jeweils beteiligten Standorten geschaltet werden.

## Layer 3

An Orten wie Berlin gibt es bereits eine vermaschte Richtfunkinfrastruktur. Das Berliner Richtfunknetz stellt aber (unseres Wissens) keine Layer 2 Infrastruktur zur Verfügung, die sich über das ganze Netz erstreckt. Ein VLAN existiert nur zwischen benachbarten Standorten, d.h. auf der Richtfunkstrecke, die diese verbindet. Der Zusammenhang des gesamten Netzes wird durch Routing (Layer 3) hergestellt: an jedem Standort befindet sich je ein Router, der zu den benachbarten (d.h. durch Richtfunkstrecken verbundenen) Routern je eine Punkt-zu-Punkt-Verbindung (P2P) aufbaut (über das o.g. streckenspezifische VLAN), und darüber ein Layer 3 Routingprotokoll spricht. Dieses Konzept hat den Vorteil, die Richtfunkstrecken direkt im Routing abzubilden (als P2P-Link mit eigener Metrik) und damit optimales Routing zu ermöglichen, incl. Ausnutzung der Redundanz (wie sie im Berliner Richtfunknetz bereits vorliegt).

# Warum ein STP?

(Wer selbst noch keine Erfahrung mit STP gemacht hat, sollte sich vor dem Weiterlesen die Begriffe [Spannbaum](https://de.wikipedia.org/wiki/Spannbaum) und [Spanning Tree Protocol](https://de.wikipedia.org/wiki/Spanning_Tree_Protocol) aneignen.)

In Hamburg wird das Berliner Konzept leicht abgewandelt benutzt. Statt OLSR wird B.A.T.M.A.N. verwendet, und letzterer operiert auf Layer 2. Das macht hier allerdings keinen wesentlichen Unterschied, denn Routing ist Routing, auch wenn damit Layer 2 Frames geroutet werden. (Das ist ähnlich wie bei den IEEE Standards 802.11s und SPB, und insofern könnte man auch den "B.A.T.M.A.N.-Luftswitch" zur Realisierung der Idee von beliebigen Nutz-VLANs zwischen Richtfunkstandorten benutzen. Allerdings ist B.A.T.M.A.N. kein IEEE Standard, sodass er eine komplizierte Mechanik darstellt, mit der u.a. die eigentlichen Nutz-Frames gekapselt und fragmentiert werden, um dann über IEEE Standards transportiert zu werden. Es handelt sich um die Emulation eines Switches, der gegenüber einer in Hardware gegossenen Layer 2 Infrastruktur also notwendig suboptimal ist. Damit sollen die Verdienste von B.A.T.M.A.N. nicht kleingeredet werden, aber es geht hier um das Konzept einer optimalen Layer 2 Infrastruktur.) Entscheidend ist jedenfalls, dass in beiden Fällen (Berlin und Hamburg) die Richtfunkstrecken als P2P-Links im Routing abgebildet werden.

In einem scheinbar winzigen Detail unterscheiden sich die beiden Konzepte aber doch noch: in Hamburg ist ein Management-VLAN konfiguriert, das sich offenbar auf das gesamte dortige Richtfunknetz erstreckt. So etwas ist erstens sehr praktisch für den Betrieb des Netzes und zweitens ein Anwendungsbeispiel für unsere obige Anforderung einer "auf das gesamte Richtfunknetz ausgedehnten Layer 2 Infrastruktur". Der praktische Vorteil eines Management-VLANs besteht insb. darin, dass man alle Geräte der Infrastruktur unmittelbar auf Layer 2, d.h. ohne Routing, erreichen kann - zB um Probleme beim Routing zu lösen. Doch der Vorteil bringt auch einen Nachteil.

## Linkabschaltungen

Wenn man nämlich ein "globales" Management-VLAN auf Layer 2 haben möchte, dann muss ein STP gefahren werden! Denn sonst gibt es auf Layer 2 Broadcastschleifen in diesem Management-VLAN, die das (gesamte) Richtfunknetz unbrauchbar machen können (und werden;). Daher wird in Hamburg offenbar RSTP auf den Richtfunkstrecken aktiviert.

Sobald also redundante Links vorhanden sind, müssen diese durch ein STP soweit abgeschaltet werden, bis nur noch eine Netztopologie ohne Kreise vorliegt (also ein Baum). RSTP (und STP) schalten Switchports an redundanten Links komplett für Nutztraffic ab, um die fatalen Broadcastschleifen zu verhindern. Die aktiven, d.h. nicht abgeschalteten Switchports bilden einen Spannbaum, sodass trotz der Abschaltungen alle Geräte auf Layer 2 erreicht werden können.

Welche Switchports (und damit Richtfunkstrecken) konkret abgeschaltet werden, kann man durch die Konfiguration von Präferenzen für Root Bridge und Portkosten beeinflussen. Aber trotzdem ist eine solche Abschaltung ein Layer 2 Artefakt, das ganz offensichtlich das optimale Routing des Nutztraffics vereitelt: denn Pakete, die optimalerweise über eine durch (R)STP abgeschaltete (aber ansonsten funktionierende!) Richtfunkverbindung laufen würden, müssen jetzt einen Umweg nehmen.

Wenn die Verbindungen eines solches Richtfunknetzes genug Bandbreite bei geringer Latenz bieten, dann bemerkt man eine solche Abschaltung vielleicht gar nicht. (In Hamburg bilden die real ex. Richtfunkstrecken vmtl. noch einen Baum, sodass (bisher) gar keine Abschaltung erforderlich ist.) Wenn man aber wie in Dortmund ein neues Richfunknetz mit den obigen Anforderungen konzipiert, dann wäre es schon gut, Suboptimalitäten wie insb. komplette Linkabschaltungen von vorneherein zu vermeiden.

# MSTP

Um komplette Linkabschaltungen durch (R)STP in einem Layer 2 Netz mit Redundanz zu vermeiden, hat man zZ wohl nur eine (für Freifunk-Communities erschwingliche;) Wahl: MSTP, das Multiple Spanning Tree Protocol.

Mehrfache Spannbäume - das klingt gut, weil Viel hilft viel, ist aber zunächst nur eine Idee und noch keine konkrete Lösung. Wir versuchen im Folgenden, eine Lösung mit MSTP zu entwickeln, welche die beiden bisher genannten entgegengesetzten Extreme in einem Layer 2 Richtfunknetz gleichzeitig realisiert:

1. Ein "globales" Management-VLAN.

2. VLANs je Punkt-zu-Punkt-Verbindung, über die geroutet wird, sodass jede Richtfunkstrecke auf einen P2P-Link im Routing abgebildet wird. Alle funktionierenden Richtfunkstrecken können für das Routing benutzt werden.

Die Gegensätzlichkeit der Extreme sieht man bei folgender Formulierung vmtl. leichter:

1. Das gewünschte Artefakt heißt "ein an allen Standorten verfügbares VLAN", und alles andere ist gleichgültig.

2. Keine Artefakte, insb. keine Linkabschaltungen, sondern optimales Routing. Layer 2 ist ansonsten gleichgültig.

Oder noch knapper:

1. Ein VLAN mit maximaler Ausdehnung (über alle Links).

2. VLANs mit minimaler Ausdehnung (über jeweils nur einen Link), die aber zusammengenommen alle verfügbaren Links abdecken.

## Lösungsidee

### Das Management-VLAN

Das Management-VLAN kommt in eine eigene MST-Instanz. In dieser Instanz werden per Spanning Tree Verfahren natürlich Links abgeschaltet um Layer 2 Schleifen zu verhindern. Das ist notwendig, aber man erreicht das Ziel eines "globalen" Management-VLANs. Solange das Richtfunknetz nicht durch den Ausfall von Richtfunkstrecken partitioniert wird, bleiben alle Geräte der Infrastruktur erreichbar.

Die unvermeidlichen Linkabschaltungen betreffen nur die VLANs dieser MST-Instanz, also das Management-VLAN. Andere VLANs sind davon nicht betroffen - das ist das entscheidende Argument für die Verwendung von MSTP.

### Die P2P-VLANs

Alle P2P-VLANs (über die das optimale Routing laufen soll) existieren nur auf je einem Link (um
Router zu verbinden). Wenn man nun die Nutz-VLANs einfach alle in der MST-Instanz 0 belässt (das ist der default), dann gibt es doch wieder Linkabschaltungen. Denn in diesem Fall ist ein einzelner Spannbaum (der CIST) für alle Links zwischen den Standorten zuständig, und dann müssen redundante Links (in der MST-Instanz 0) abgeschaltet werden.

Es werden also P2P-VLANs abgeschaltet, und das genau das wollten wir wg. des resultierenden suboptimalen Routings vermeiden. Daher müssen wir die P2P-VLANs "irgendwie" auf mehrere MST-Instanzen so verteilen, dass es nicht zu Linkabschaltungen kommt.

### Die Verteilung der P2P-VLANs auf MST-Instanzen

Abstrakt lässt sich die Lösung sehr leicht spezifizieren: Man verteilt alle Links (und damit P2P-VLANS) auf kantendisjunkte, schleifenfreie Teilgraphen, sodass jeder dieser Teilgraphen dem Spannbaum einer MST-Instanz entspricht. (Ein P2P-VLAN, das Teil des Spannbaums einer MST-Instanz ist, wird nicht abgeschaltet. Wenn kein 
P2P-VLAN durch MSTP abgeschaltet wird, ist optimales Routing möglich.)

Man könnte nun ganz einfach hingehen, und für jedes P2P-VLAN eine eigene MST-Instanz anlegen. Der Standard sieht bis zu 64 mögliche MST-Instanzen vor. Damit käme man schon recht weit - wenn da nicht der klamme Geldbeutel wäre, der mit den üblichen Switches zZ nur 8 MST-Instanzen erlaubt.

Dadurch stellt sich folgendes Problem: Wie verteilt man die P2P-VLANs auf **möglichst wenige MST-Instanzen**, sodass es nicht zu Linkabschaltungen kommt?

Zur Veranschaulichung hier eine minimale Verteilung für einen K4:

~~~
I1: A-B-C-D
I2: B-D-A-C
~~~

Und für einen K6:

~~~
I1: A-C-E-F-B-D
I2: C-F-A-B-E-D
I3: E-A-D-C-B
        +-F
~~~

Notation:

A,B,C,D,E,F: Knoten eines K6

A-B: Kante zwischen den Knoten A und B

In: Spannbaum der MST-Instanz n

## Die Konstruktion der MST-Instanzen

Definition:

### Zerlegung eines Graphen G in Instanzen

:= eine Menge schleifenfreier, zusammenhängender Teilgraphen ("Instanzen") von G, wobei jede Kante von G in genau einer Instanz enthalten ist.

Praktisch bedeutet das Finden einer solche Zerlegung eine Möglichkeit, die Spannbäume in dem Layer 2 Netz so zu wählen, dass jede Kante zu einem von ihnen gehört. Denn dann repräsentiert diese Kante (als Teil eines Spannbaums) einen aktiven Link, über den Nutztraffic transportieren werden kann. Damit kommt es nicht mehr zur Vollabschaltung irgendeines Richtfunklinks, sondern alle P2P-VLANs sind aktiv.

### Vermutung: einen vollständigen Graphen mit n Knoten (Kn) kann man in n/2 Instanzen zerlegen

Dabei ist n eine gerade Zahl. (Bei ungeradem n betrachtet man den Kn als Teilgraph des K(n+1), denn dann ist n+1 gerade.)

### Beweis (konstruktive Induktion)

#### Induktionsanfang

Für n=2 reicht 2/2 = 1 Instanz. Das ist trivial, da der K2 nur eine Kante hat.

#### Induktionsvoraussetzung

Kn sei in n/2 Instanzen zerlegbar.

#### Induktionsschritt (= Konstruktionsalgorithmus)

1. Man teilt die Knotenmenge von Kn (V(Kn) = { v1, ..., vn }) in zwei disjunkte Mengen M1 und M2 mit |M1| = |M2| = n/2. Dann ist V(K(n+2)) = M1 + M2 + { v(n+1), v(n+2) }.

2. Jede der n/2 Instanzen von Kn wird um je eine Kante zu v(n+1) und v(n+2) erweitert, wobei v(n+1) mit einem Knoten aus M1 und v(n+2) mit einem Knoten aus M2 verbunden wird. Das Resultat ist eine Instanz von
K(n+2).

3. Die Instanz n/2 + 1 bildet man aus der Kante (v(n+1), v(n+2)), sowie den Kanten (v(n+1), m2) für alle Knoten m2 aus M2, und entsprechend (v(n+2), m1) für alle m1 aus M1.

Damit sind alle Kanten, die durch die Erweiterung des Kn zum K(n+2) hinzugekommen sind, Teil einer der mit 2. bzw. 3. konstruierten Instanzen von K(n+2). K(n+2) lässt sich also in n/2 + 1 Instanzen zerlegen, wenn eine Zerlegung von Kn in n/2 Instanzen bekannt ist.

#### Fazit

Da die Induktionsvoraussetzung für n = 2 gilt, folgt aus der wiederholten Anwendung des Induktionsschritts, dass sich für alle geraden n der Kn in n/2 Instanzen zerlegen lässt, q.e.d.

## Die Umsetzung mit realen Switchen

Die in einem Testaufbau benutzten Switch-Konfigurationen (für die MSTP-fähigen Geräte TL-SG3210, TL-SG2008, TL-SG3424) sind in einem Unterordner dokumentiert. Die für MSTP irrelevanten Teile der Konfiguration sind dort zwecks besserer Übersicht weggelassen.

Für das "globale" Management-VLAN wird die VLAN-ID 2005 verwendet, die zur MST-Instanz 1 gehört. Die zweistelligen IDs der P2P-VLANS haben als erste bzw. zweite Ziffer die Nummern der beiden Switches, die durch diesen P2P-Link verbunden werden. D.h. VLAN 23 liegt auf dem Link, der Switch 2 mit Switch 3 verbindet:

~~~
hostname "MSTP-sw2"
[...]
interface gigabitEthernet 1/0/3
[...]
  switchport trunk allowed vlan 23,2005
~~~

Den Kanten des Spannbaums einer MST-Instanz entsprechen die Zeilen der folgenden Form:

~~~
hostname "MSTP-sw2"
[...]
interface gigabitEthernet 1/0/3
[...]
  spanning-tree mst instance 3 port-priority 128 cost 1000
~~~

Das bedeutet, dass port 3 dieses Switches zum Spannbaum der MST-Instanz 3 gehört. Die cost 1000 ist nämlich erheblich kleiner gewählt als die default cost von 20000 (für Gigabitports).

Alle anderen Kanten des K6 gehören zwar auch zur MST-Instanz 3, spielen aber praktisch keine Rolle wegen ihrer hohen cost Werte (20000 versus nur 1000 für die wie oben konfigurierten Kanten). D.h. sie werden abgeschaltet, sodass nur die Kanten mit cost 1000 Teil des Spannbaums werden, also von MSTP aktiv geschaltet werden, d.h. Nutztraffic über Richtfunkstrecken transportieren.

Welche ports in welchen Instanzen zum Spannbaum gehören sollen (d.h. auf cost 1000 konfiguriert werden) ergibt sich durch den oben im Induktionsschritt beschriebenen Algorithmus. (Wenn man ihn auf Papier ausführt, bringt die Verwendung von Buntstiften zur Kennzeichnung der verschiedenen Spannbäume sogar noch mehr Spaß:-)