Spanning Tree Algorithmus

Das Problem der kreisenden Rahmen bei der mehrfachen Verbindung (Schleifen) von Bridges/Switches kann durch das sogenannte STP 1) spanning tree protocol gelöst werden. STP löst dieses Problem, indem gezielt Ports deaktiviert werden, so dass keine mehrfachen Verbindungen mehr existieren. Das Protokoll ist im Standard IEEE 802.1d festgelegt. Im Folgenden wird die Vorgehensweise detailiert erläutert.

Festlegungen im ST-Algorithmus

Jede Brücke hat eine eindeutige vorkonfigurierte ID.

Die Wichtigkeit von Brücken in parallelen Verbindungen müssen durch Bridge-Prioritäten (Bridge Priority) definiert sein.

Jeder Port einer Brücke hat eine eindeutige lokale ID.

Jedem Port sind Port-Kosten (Port Cost) zugewiesen. Die Port-Kosten sind umgekehrt proportional zur Bitrate oder proportional zur Auslastung auszulegen. Port-Kosten im WAN können proportional den Übertragungskosten angepasst werden.

Bestimmung des aufspannenden Baums durch Abwickeln eines Protokolls zwischen den Brücken eines Netzes

Die Brücken kommunizieren über die Configuration BPDUs 2) bridge protocol data unit , Konfigurations-PDUs oder Konfigurations-nachrichten, auch: „Hallo-Pakete„ (Hellopackets) genannt und versenden die Konfigurations-PDUs in normalen Schicht 2 Rahmen, z.B. in IEEE 802.2-Codierung:

Zieladresse	Quelladresse	DSAP	SSAP	Control	Konfigurations-PDU	FCS

Die Zieladresse ist eine spezielle Multicast-Adresse „An alle Brücken“. Die Quelladresse ist die echte MAC-Adresse des Ports, über den die Konfigurations-Nachricht gesendet wird. (Auch die Ports von Brücken haben echte MAC-Adressen, hier werden sie vom Sender „korrekt„ eingetragen - im Gegensatz zum „Normalfall“ eines weitergeleiteten Rahmens.)

Die SAPs3) service access point haben den Wert 01000010 (Byteordnung immer korrekt !).

Die Multicast-Adresse für Hallo-Pakete ist 09:00:2B:01:00:01 („An alle Brücken„)

Der Ethernet-Protokolltyp (Bei Rahmen im V2.0-Format oder SNAP) ist 8038

Das ST-Protokoll legt fest:

Root Bridge: die Bridge, die die Wurzel der Baum-Topologie darstellt. Als Root-Bridge dient die Brücke mit der niedrigsten Kennung (Bridge ID). Erstes Entscheidungskriterium ist die Priority. Ist diese gleich (tie break), so gewinnt die niedrigste MAC-Adresse.

Root Port: Der Root-Port einer Bridge ist der, über den die niedrigsten Übertragungskosten zur Root-Bridge entstehen, der am „nächsten“ zur Wurzelbrücke liegt und die Daten dorthin weiterleitet.

Root Path: die Route zwischen einem Root Port und der Root Bridge, auf der die niedrigsten Übertragungskosten entstehen.

Root Path Cost (RPC): Mit jedem Root Port sind die Kosten RPC verbunden. Sie stellen die Summe von Kosten aller Root Ports auf dem Root-Pfad dar.

Jedes gekoppelte Teilnetz (LAN) hat genau einen(!) Anschlusspunkt in Form einer designated Bridge 4) ausgewählte Brücke mit designated Port. Diese designated Bridge verbindet das betreffende Teilnetz mit dem Rest des Netzes. Normalerweise ist mit der designated Bridge eines LANs auch deren designated Port festgelegt. Ist eine Brücke aber über mehrere Ports mit einem LAN verbunden, dann wird der designated Port der designated Bridge noch bestimmt.

Jede Brücke hat einen Root-Port, der sie mit dem „Kern„ des Gesamtnetzes verbindet. Der ST-Algorithmus verwandelt das Netz in einen Baum, in dem sich Rahmen schleifenfrei ausbreiten können: von jedem Punkt in zwei Richtungen: in Richtung Wurzel und in Richtung Blätter.

Der Baum besteht zunächst aus der Wurzelbrücke. Dazu kommen die an sie direkt angeschlossenen LANs. Für sie ist jeweils die Wurzelbrücke die designated Bridge. In der nächsten Stufe kommen die nächsten LANs dazu: jeweils mit der Brücke, die sie mit den LANs der ersten Stufe verbindet, also mit ihrer designated Bridge. Jede dieser designated Bridges der zweiten Stufe hat als Root-Port den Port, der sie mit einem LAN der ersten Stufe verbindet und so rekursiv immer weiter. Der Graph des Gesamtnetzes wird dadurch zu einem Baum, sodass alle Ports aller Brücken deaktiviert werden, es sei denn, sie sind Root-Port der Brücke oder designated Port des angeschlossenen LANs.

Hallo-Pakete (Konfigurationsnachrichten) werden von Brücken berechnet und an alle anderen Brücken im gleichen LAN gesendet (via Multicast). Sie werden grundsätzlich nicht weitergeleitet. Mit Hallo-Paketen werden Konfigurationsdaten verbreitet.

Konfigurationsdaten bestehen aus:

Transmitting Bridge ID: die ID der Brücke, die das Paket gesendet hat.

Cost: die Kosten des Weges von der Brücke, die das Paket gesendet hat (Transmitting Bridge), bis zur Wurzel. Meist wird als Kosten die Zahl der „Hops“ verwendet.

Aus den empfangenen Hallo-Paketen (Konfigurationsdaten) berechnet jede Brücke die Konfigurationsdaten, die sie selbst versendet (die eigene Konfigurationsnachricht): ihren Root Port und die Ports, die designated Port für das angeschlossene LAN sind.

Animation von Cisco zum Thema Spanning Tree

Die folgende Animation erklärt den Prozess der Wahl der Root-Bridge, der Root-Ports sowie der designated Ports. Ferner wird das Verhalten der Bridges gezeigt, welches im eingeschwungenen Zustand vorherrscht. Animation starten