# Spanning Tree Protocol

Das Spanning Tree Protocol (STP, deutsch: Spannbaum-Protokoll) ist ein Teil von Switch-Infrastrukturen. Rechnernetzwerke können mit einer Vielzahl von Switches als Koppelungselement aufgebaut werden. Allerdings muss die Ethernet-Technologie sicherstellen, dass zwischen zwei Rechnern jeweils nur ein Datenpfad existiert, um Pakete eindeutig weiterleiten zu können.
Die Vermeidung von Effekten wie Broadcast-Stürmen wird nur erreicht, wenn ein Algorithmus existiert, der die Schleifenfreiheit der Topologie sicherstellt. Der Spanning-Tree-Algorithmus sorgt nun dafür, dass es keine unerwünscht kreisenden Pakete gibt. Er identifiziert Mehrfachwege, indem er Topologien mit redundanten Wegen durch eine logische Blockierung bestimmter Pfade in eine Baumtopologie ohne Schleifen überführt. Dazu werden auf den Switches mit mehreren Verbindungen zu anderen Switches alle bis auf eine Verbindung blockiert. Bei Ausfall der primären Verbindung können diese sofort aktiviert werden und erzeugen auf diese Weise ein hohes Maß an Fehlertoleranz.
Der Spanning-Tree Algorithmus wurde von Radia Perlman entworfen und 1990 als IEEE 802.1D standardisiert. Voraussetzung für die Funktionsfähigkeit dieses Konzeptes ist, dass der aufspannende Baum für den Nutzer vollkommen transparent erstellt werden kann. Als einzige Aktion muss der Spanning-Tree-Algorithmus auf den Switches aktiviert sein. Zum Austausch von Konfigurationsnachrichten wird eine Bridge Protocol Data Unit (BPDU) als Multicast-Paket genutzt, das standardmäßig alle zwei Sekunden versendet wird und damit eine nicht unerhebliche Netzlast verursacht.

## Funktionsweise

Um den logischen Spanning-Tree kennenzulernen, geht jeder Switch durch einen Ablauf von Portzuständen, die durch drei Timer beeinflusst werden. Wenn ein Switchport unmittelbar von einem blockierenden (Blocking) in einen weiterleitenden (Forwarding) Status versetzt würde, bestünde die Gefahr, Topologieinformationen zu verlieren und eine Schleife zu erzeugen. Dies ist der Grund, warum zwischen fünf Portzuständen unterschieden wird:
| Portzustand | Beschreibung |
| Disabled | Verwirft Frames; lernt keine Adressen; empfängt und verarbeitet keine BPDUs |
| Blocking | Verwirft Frames; lernt keine Adressen; empfängt und verarbeitet BPDUs |
| Listening | Verwirft Frames; lernt keine Adressen; empfängt, verarbeitet und überträgt BPDUs |
| Learning | Verwirft Frames; lernt Adressen; empfängt, verarbeitet und überträgt BPDUs |
| Forwarding | Leitet Frames weiter, lernt Adressen; empfängt, verarbeitet und überträgt BPDUs |
Die Zeitspanne, die ein Port in einem Zustand verweilt, wird durch Timer bestimmt. Nur die Root-Bridge kann die Einstellungen verändern. Drei Timer beeinflussen den Zustandswechsel und damit die Ausführungsgeschwindigkeit des Algorithmus:
* Der Hello-Timer gibt die Zeitspanne zwischen zwei BPDUs (Bridge Protocol Data Units) an. Er beträgt standardmäßig zwei Sekunden.
* Forward-Delay ist die Zeit, die in den Zuständen Listening und Learning verbracht wird. Hierfür sind jeweils 15 Sekunden vorgesehen, also insgesamt 30 Sekunden.
* Der "Max Age"-Timer kontrolliert, wie lange ein Switchport die Konfigurationsinformation behält. Der Standardwert beträgt 20 Sekunden.
Wenn STP aktiviert ist, passiert jeder Port auf jedem Switch die Zustände in der Reihenfolge: Blocking – Listening – Learning – Forwarding. Für diesen Zustandsübergang werden in der Standardkonfiguration 50 Sekunden benötigt – eine im Netzwerkbereich relativ lange Zeitspanne. Die Konvergenz, also die Zeit, die benötigt wird, um den Spanning Tree im Falle des Ausfalls einer Verbindung neu zu berechnen, ist damit nicht unerheblich und ein Kritikpunkt an diesem Verfahren.
Als erste Aktivität in einem Netz wird unter den Spanning-Tree-fähigen Switches eine sogenannte Root Bridge gewählt, die die Wurzel des aufzuspannenden Baumes wird und „Chef“ des Netzes ist. Dies geschieht, indem alle Switches bzw. Bridges ihre Bridge-ID (kurz: BID; jede Bridge wird über eine eigene BID identifiziert) an eine bestimmte Multicast-Gruppe mitteilen. Die Bridge-ID ist 8 Byte lang (2 Byte Bridge Priority, 6 Byte MAC-Adresse). Die Bridge mit der höchsten Priorität (d. h. dem kleinsten Wert) wird zur Root Bridge. Sollte die Bridge Priority identisch sein, wird als ergänzendes Kriterium die MAC-Adresse der Komponenten benutzt (auch hier gewinnt wieder die Bridge mit dem niedrigeren Wert).
Von der Root Bridge aus werden nun Pfade festgelegt, über die die anderen Bridges im Netz erreichbar sind. Sind redundante Pfade vorhanden, so müssen die dortigen Bridges den entsprechenden Port deaktivieren. Die Pfade, über die kommuniziert werden darf, werden anhand von Pfadkosten bestimmt, die die dortige Bridge übermittelt.
Diese Pfadkosten sind abhängig vom Abstand zur Root Bridge und der zur Verfügung stehenden Datenverbindung („uplink“) zum Ziel. Ein 10-Mbit/s-Uplink hat höhere Pfadkosten als ein 100-Mbit/s-Uplink zum selben Ziel, die 10-Mbit/s-Verbindung würde daher als redundanter Pfad blockiert werden. Die Pfadkosten sind nach IEEE-Vorgaben genormt, können aber manuell abweichend festgelegt werden, beispielsweise um bei gleicher Geschwindigkeit einen bevorzugten Uplink auszuwählen, um so die reellen Kosten von WAN-Verbindungen widerzuspiegeln. Auf diese Weise ist jedes Teilnetz im „geswitchten“ LAN nur noch über eine einzige, die Designated Bridge, erreichbar. In der grafischen Darstellung ergibt sich ein Baum aus Netzpfaden, der dem Algorithmus sowie dem Protokoll seinen Namen gab.
Die Root Bridge teilt den in der Hierarchie eine Stufe unterhalb liegenden Designated Bridges im Abstand von zwei Sekunden mit, dass sie noch da ist, woraufhin die empfangende Designated Bridge ebenfalls an nachfolgende Bridges die entsprechende Information senden darf. Wenn diese Hello-Pakete ausbleiben, hat sich folglich an der Topologie des Netzes etwas geändert, und das Netz muss sich reorganisieren. Diese Neuberechnung des Baumes dauert im schlimmsten Fall bis zu 30 Sekunden. Während dieser Zeit dürfen die Spanning-Tree-fähigen Bridges außer Spanning-Tree-Informationen keine Pakete im Netz weiterleiten. Dies ist einer der größten Kritikpunkte am klassischen Spanning-Tree-Protokoll, da es möglich ist, mit gefälschten Spanning-Tree-Paketen eine Topologieänderung zu signalisieren und das gesamte Netz bis zu 30 Sekunden lang lahmzulegen. Um diesen potenziellen Sicherheitsmangel zu beheben, aber auch um bei echten Topologieänderungen das Netz schnell wieder in einen benutzbaren Zustand zu bringen, wurden schon früh von verschiedenen Herstellern Verbesserungen an der Implementierung des Spanning Tree Protokolls und der dazu verwendeten Algorithmen entwickelt. Eine davon, das Rapid Spanning Tree Protocol (RSTP), ist inzwischen zum offiziellen IEEE-Standard 802.1w geworden.

## RSTP

Die Idee hinter dem Rapid Spanning Tree Protocol (RSTP) ist, dass bei signalisierten Topologieänderungen nicht sofort die Netzstruktur gelöscht wird, sondern erst einmal wie gehabt weiter gearbeitet wird und Alternativpfade berechnet werden. Erst anschließend wird ein neuer Baum zusammengestellt. Die Ausfallzeit des Netzes lässt sich so von 30 Sekunden auf unter 1 Sekunde reduzieren. In der 2003 verabschiedeten Revision des 802.1d-Standards wurde das alte STP zugunsten von RSTP (IEEE 802.1w) ersetzt. Inzwischen ist dieses durch IEEE 802.1D-2004 ersetzt worden.

## MSTP

Das Multiple Spanning Tree Protocol (MSTP) ist eine Erweiterung des RSTPs. Es ermöglicht im Zusammenhang mit Virtual Local Area Networks (VLANs) verschiedene Instanzen des Spanning Tree. Für ein VLAN oder eine Gruppe von VLANs können also voneinander unabhängige STP-Instanzen gebildet werden, die innerhalb eines LANs jeweils eigene unterschiedliche Spannbäume nutzen. Das MSTP wurde ebenfalls erstmals in der 2003 verabschiedeten Revision des 802.1D-Standards unter IEEE 802.1s definiert und später unter IEEE 802.1Q eingegliedert.

## Shortest Path Bridging (SPB)

Um die Begrenzungen des Spanning Tree Protocol zu überwinden, wurde das Shortest Path Bridging entwickelt und in IEEE 802.1aq standardisiert.

## Schrittweiser Aufbau des Baumes

* Einschalten („Power up“) aller Bridges.
* Alle Bridges stellen ihre Ports auf „Blocked“.
* Jede Bridge nimmt an, sie sei die Root-Bridge, und sendet BPDUs (Bridge Protocol Data Unit) aus.
* Die Bridge mit der kleinsten Bridge-ID (= Priority & MAC-Adresse) wird zur Root-Bridge.
* Die Root-Bridge sendet Konfigurations-BPDUs aus.
* Jede Bridge bestimmt den Port mit den kleinsten Pfadkosten zur Root-Bridge als Root-Port. Bei Ports mit gleichen Kosten gewinnt die kleinere Port-ID.
* Die Designated Bridge wird vom LAN festgelegt, dies ist die Bridge mit dem Root-Port ins LAN mit den niedrigsten Pfadkosten.

## Trivia

Die Erfinderin Radia Perlman hat dem "Spanning Tree Protocol" auch ein Gedicht gewidmet, welches später vertont wurde.