Een interactieve tour door het Spanning Tree Protocol

Stel je voor dat je kantoorruimte huurt voor een driedaags evenement. Je stelt snel een paar Ethernet-switches op en plakt wat kabels op de vloer om iedereen online te krijgen. Helaas schopt Stan, je onhandigste collega, elke keer dat hij koffie gaat halen, een kabel uit de aansluiting. Je zou extra kabels kunnen toevoegen, maar dan krijg je een broadcast storm: Ethernet-pakketten die in lussen blijven rondgaan en zich vermenigvuldigen totdat er niets anders meer door komt.

Dat is waar het Spanning Tree Protocol (STP) om de hoek komt kijken. STP blokkeert precies genoeg van je reservekabels om een boomstructuur zonder lussen over te houden. Wanneer Stan opnieuw toeslaat, herbouwt het protocol binnen een seconde de boom, waardoor Blobby, je eenmans supportcrew, tijd heeft om de kabel opnieuw aan te sluiten.

De basis

Het Spanning Tree Protocol, ontworpen in de jaren '80, is geëvolueerd naar een "snelle" variant (RSTP) en een "VLAN-bewuste" variatie (MSTP). Hoewel elke ervaren netwerkengineer weet dat er betere alternatieven zijn, zoals BGP EVPN VXLAN, vervult het venerable STP nog steeds een niche omdat elke switch het spreekt.

  • STP werd geïntroduceerd in IEEE 802.1D-1990. Het is nog aanwezig in IEEE 802.1D-1998, maar werd in IEEE 802.1D-2004 ingetrokken ten gunste van RSTP.
  • RSTP werd geïntroduceerd in IEEE 802.1w-2001.
  • MSTP werd geïntroduceerd in IEEE 802.1s-2002 en later samengevoegd in IEEE 802.1Q-2003.
  • Zowel RSTP als MSTP maken deel uit van IEEE 802.1Q-2022, samen met SPB.

In dit artikel focussen we op RSTP, dat het oorspronkelijke protocol in 2004 verving. Om netwerklussen te elimineren, implementeert RSTP een complexe toestandsmachine. De overgangen worden aangestuurd door timers, wijzigingen in de linkstatus en link-lokale controleframes die een bridge ontvangt van zijn buren. Deze Ethernet-frames worden Bridge Protocol Data Units (BPDUs) genoemd.

Na verloop van tijd convergeert de topologie naar een boom: vanaf de root is er een pad naar elke bridge en is er geen lus aanwezig.

Historische tussenstop

Radia Perlman, in 2014 opgenomen in de Internet Hall of Fame, vatte de voorloper van STP die ze bij DEC uitvond samen met dit gedicht, dat later in een Amerikaans patent werd opgenomen:

Ik denk dat ik nooit zal zien een graaf die mooier is dan een boom. Een boom wiens cruciale eigenschap lusvrije connectiviteit is. Een boom die zeker moet spannen zodat pakketten elk LAN kunnen bereiken. Eerst moet de root worden geselecteerd. Op basis van ID wordt deze verkozen. Kortste paden vanaf de root worden getraceerd. In de boom worden deze paden geplaatst. Een mesh wordt gemaakt door mensen zoals ik, en vervolgens vinden bridges een spanning tree. — Radia Perlman, Algorhyme.

De root bridge kiezen

Om een boom te bouwen, kiest RSTP eerst de bridge met de laagste bridge identifier als de root bridge. De bridge identifier is een combinatie van de prioriteit en het MAC-adres (bijv. 8192.6e:2b:10:a0:5f:29).

Bijvoorbeeld:

  • Als S1 een prioriteit heeft van 4.096 en S2 van 8.192, wordt S1 de root.
  • Als S4 een prioriteit heeft van 12.288 en S3 de standaardprioriteit van 32.768 behoudt, wordt S4 de root.
  • Als S5 en S6 geen specifieke prioriteit hebben, wint het laagste MAC-adres en wordt S5 de root.

Aanvankelijk adverteert elke bridge zichzelf als root:

Spanning Tree Protocol
Protocol Identifier: Spanning Tree Protocol (0x0000)
Protocol Version Identifier: Rapid Spanning Tree (2)
BPDU Type: Rapid/Multiple Spanning Tree (0x02)
Root Identifier: 8192.02:00:00:01:00:01
Bridge Identifier: 8192.02:00:00:01:00:01

Zodra een bridge een BPDU ontvangt die een betere root bridge adverteert, propageert hij deze nieuwe informatie naar zijn buren.

Spanning Tree Protocol
Protocol Identifier: Spanning Tree Protocol (0x0000)
Protocol Version Identifier: Rapid Spanning Tree (2)
BPDU Type: Rapid/Multiple Spanning Tree (0x02)
Root Identifier: 4096.02:00:00:00:00:00
Bridge Identifier: 8192.02:00:00:00:00:01

Rollen toewijzen aan poorten

De tweede stap is het toewijzen van een rol aan elke poort. RSTP definieert vijf rollen:

  • Root (R)
  • Designated (D)
  • Alternate (A)
  • Disabled (X)
  • Backup (B) (Een backup-poort bestaat alleen als de bridge meerdere poorten heeft in hetzelfde collision-domein, wat in een geswitcht netwerk niet zou mogen voorkomen).

Elke non-root bridge kiest zijn root port: de poort met het pad met de laagste kosten naar de root. Tenzij dit handmatig wordt overschreven, bepaalt de bridge de linkkosten op basis van de snelheid (bijv. 20.000 voor 1 Gbps). Bij gelijkheid wint de laagste poort-identifier.

Elke overige poort wordt een designated port als de BPDU die hij verzendt "beter" is dan de BPDU die hij ontvangt. Anders wordt het een alternate port. Later, als de root port uitvalt, wordt de "beste" alternate port de nieuwe root port.

De tiebreakers voor de beste BPDU zijn:

  1. De laagste root bridge identifier.
  2. De laagste geaccumuleerde kosten naar de root.
  3. De laagste bridge identifier.
  4. De laagste poort-identifier.

Voorbeeld van een BPDU:

Spanning Tree Protocol
Protocol Identifier: Spanning Tree Protocol (0x0000)
Protocol Version Identifier: Rapid Spanning Tree (2)
BPDU Type: Rapid/Multiple Spanning Tree (0x02)
Root Identifier: 4096.02:00:00:00:00:00
Root Path Cost: 20000
Bridge Identifier: 32768.02:00:00:00:00:01
Port identifier: 0x8002

Tenzij er een specifiek event plaatsvindt, verzenden designated ports elke 2 seconden BPDUs (de "hello" timer). Als een bridge gedurende 3 opeenvolgende hello-perioden geen BPDUs van zijn buurman ontvangt, beschouwt hij de buurman als dood en verwijdert hij de poortinformatie.

Overgang van poortstatus

Elke poort kan zich in een van de drie statussen bevinden:

  • Discarding (rood)
  • Learning (geel)
  • Forwarding (groen)

Een root port gaat automatisch over naar de forwarding status. Een alternate port blijft in de discarding status. Een designated port heeft twee opties om van discarding naar forwarding over te gaan:

  1. Edge ports: Als de poort een edge port is (via configuratie of omdat het externe apparaat geen STP spreekt), gaat de designated port onmiddellijk naar de forwarding status.
  2. Proposal/Agreement proces: In andere gevallen verzendt de poort een proposal naar zijn downstream buurman. Als de ontvangende bridge akkoord gaat dat de ontvangen BPDU "beter" is dan welke andere BPDU dan ook, kiest hij de ontvangende poort als zijn root port en start hij het synchronisatieproces: hij zet alle non-edge non-synced designated ports in de discarding status om lussen te voorkomen. Daarna verzendt hij een agreement. Bij ontvangst hiervan gaat de peer designated port over naar de forwarding status.

Indien er geen agreement wordt ontvangen na het verstrijken van de hello-timer, valt het systeem terug op de timer-gebaseerde methode voor compatibiliteit met STP: de poort gaat naar learning, wacht tot de hello-timer verloopt, en gaat dan naar forwarding.

Meldingen over topologiewijzigingen

Een bridge bouwt een MAC-adrestabel op: hij koppelt elk bron-MAC-adres aan de poort die dit als laatste heeft ontvangen. Wanneer een link uitvalt, kan een apparaat dat bereikbaar was via één poort, nu bereikbaar zijn via een andere. De betrokken bridges moeten de geleerde MAC-adressen flushen.

RSTP implementeert topologiewijzigingen (topology change notifications) via een flooding-mechanisme. Wanneer een non-edge poort overgaat naar de forwarding status, genereert een bridge BPDUs met de topology change (TC) bit ingesteld op 1. Deze worden verzonden naar alle non-edge designated ports en de root port. Tegelijkertijd wordt de MAC-adrestabel op deze poorten geflusht.

Wanneer een bridge zo'n BPDU ontvangt, propageert hij de melding verder naar alle non-edge designated ports en de root port, behalve naar de poort waarvan de melding kwam.

Om resistent te zijn tegen pakketverlies, zet een poort de TC-bit in elke BPDU op 1 gedurende een periode die gelijk is aan de hello-timer plus één seconde.

Beveiliging

RSTP is kwetsbaar voor configuratiefouten en kwaadwillende actoren. Een bridge die geen RSTP spreekt, kan een lus veroorzaken, en aanvallers kunnen zich in de topologie nestelen om verkeer te onderscheppen of te wijzigen.

Om dit te beperken, moeten edge ports (poorten naar eindapparaten zoals PC's) worden geïdentificeerd:

  • AdminEdge: Wanneer waar, wordt een poort geïnitialiseerd als edge port. Standaard is dit onwaar.
  • AutoEdge: Wanneer waar, wordt een poort een edge port als hij gedurende 3 seconden geen BPDUs ontvangt. Standaard is dit waar.

Als een edge port een BPDU ontvangt, keert hij ongeacht deze vlaggen terug naar een non-edge poort.

Daarnaast zijn er niet-standaard functies:

  • Bridge Assurance: De poort verzendt BPDUs ongeacht de rol. Als er gedurende 3 hello-perioden geen BPDUs worden ontvangen, gaat de poort naar de discarding status.
  • BPDU Guard: Schakelt een poort direct uit als er een BPDU wordt ontvangen.

Voor optimale beveiliging is het aanbevolen om AdminEdge op waar te zetten en BPDU Guard in te schakelen voor poorten naar eindgebruikers.

Waarom RSTP vandaag de dag?

Een overtuigend gebruiksscenario voor RSTP is een out-of-band (OOB) netwerk voor een datacenter, aangezien een uitval van enkele seconden daar acceptabel is. De configuratie is minimaal en er kunnen goedkope switches worden gebruikt. Door twee switches als root bridges in te stellen en meerdere lussen te bouwen om OOB-switches in elk kastje te verbinden, overleeft het ontwerp één defect per lus.

Hoe groot kan een netwerk zijn?

De maximum age (standaard 20) bepaalt de maximale afstand van een bridge tot de root. Als een netwerk te groot is, kunnen BPDUs de maximum age overschrijden, waardoor delen van het netwerk onafhankelijk van elkaar een eigen root bridge kiezen.

Dit kan worden opgelost door de maximum age te verhogen (bijv. naar 40). Wanneer dit gebeurt, moet ook de forward delay worden verhoogd, omdat de standaard de volgende conditie vereist: 2 × (Forward Delay − 1) ≥ Max Age.

Hoe snel is RSTP?

RSTP convergeert meestal binnen een paar seconden bij opstarten en herstelt een boom vaak in minder dan een seconde. Sommige topologieën kunnen echter langer nodig hebben om te herstellen wanneer de root bridge onbeschikbaar wordt.

Dit kan leiden tot het "Count-to-Infinity" fenomeen, waarbij bridges elkaar in een cirkel overtuigen van wie de root is. Dit stopt uiteindelijk wanneer de BPDUs die een bepaalde bridge als root aanwijzen, verlopen omdat hun message age de maximum age overschrijdt.

Over MSTP

MSTP is de VLAN-bewuste versie van RSTP. Het draait meerdere instanties van RSTP en stelt de beheerder in staat om elk VLAN aan een specifieke instantie te koppelen. De resterende VLANs worden toegewezen aan de Internal Spanning Tree (IST). In feite creëert dit meerdere logische topologieën die onafhankelijk van elkaar opereren.

Over de interactieve voorbeelden

De interactieve voorbeelden in dit artikel draaien MSTPD direct in de browser, gecompileerd naar WebAssembly met Emscripten. Een C API vervangt de code die normaliter met de Linux-kernel communiceert; deze beheert bridges en poorten, exporteert de status als JSON en stuurt de tijd deterministisch aan.

Een JavaScript-wrapper maakt dit gebruiksvriendelijk. De implementatie bevat tientallen unit-tests om functies zoals prioriteit, lussen en reconvergentie te controleren. Om te bepalen of een topologie is geconvergeerd, maakt de simulatie gebruik van snapshots van het geheugen om stabiliteit over een periode van 50 seconden te verifiëren.