Spanning Tree Protocol (STP) bygger på en algoritm som utvecklades av Radia Perlman under hennes tid på Digital Equipment Corporation. Algoritmen presenterades i artikeln “An Algorithm for Distributed Computation of a Spanning Tree in an Extended LAN” från 1985.

Syftet med algoritmen är att skapa en loopfri logisk topologi i ett Layer 2-nätverk. Detta görs genom att välja en central referenspunkt i nätverket – Root Bridge – och låta alla andra switchar beräkna den lägsta kostnadsvägen till denna switch.

Resultatet blir en struktur där varje switch har en enda aktiv väg till Root Bridge, vilket eliminerar risken för Layer 2-loopar samtidigt som redundanta länkar fortfarande finns kvar i nätverket.

För att förstå hur detta fungerar ska vi studera de viktigaste delarna av STP-algoritmen i ett exempel med flera Layer 2-switchar.

Root Bridge

Ett centralt steg i STP-algoritmen är att välja en RootBridge. Den fungerar som den logiska referenspunkten i spanning tree-topologin. Alla andra switchar beräknar sin lägsta kostnadsväg till denna switch.

I ett scenario där alla länkar har samma bandbredd innebär detta i praktiken att varje switch väljer den väg som kräver färst hopp till Root Bridge.

Obs: I STP-terminologi används ofta ordet bridge i stället för switch. Detta beror på att switchar historiskt utvecklades ur äldre Ethernet-enheter som kallades bridges.

Blockering av redundanta vägar

När Root Bridge har valts analyserar STP hela nätverkstopologin och identifierar redundanta vägar.

För att förhindra loopar kommer STP att:

• välja en aktiv väg mellan switchar
• blockera övriga vägar som skulle kunna skapa en loop

När en port placeras i blocking state kan den fortfarande ta emot STP-information, men den skickar inte vidare vanliga Ethernet-ramar. På detta sätt säkerställer STP att det endast finns en logisk väg mellan två punkter i nätverket.

Loopfri topologi

När STP har blockerat alla redundanta vägar bildas en loopfri logisk struktur som kallas ett spanning tree. Det innebär att:

• varje switch har en aktiv väg till Root Bridge
• inga ramar kan cirkulera i en sluten krets
• redundanta länkar finns kvar som reservvägar

Den fysiska topologin kan alltså fortfarande innehålla flera länkar mellan switchar, men STP skapar en logisk topologi utan loopar.

Omräkning vid nätverksförändringar

STP övervakar kontinuerligt nätverkstopologin. Om en förändring inträffar måste protokollet beräkna om spanning tree-topologin. Detta kan ske när exempelvis:

• en länk går ner
• en switch slutar fungera
• en ny switch ansluts till nätverket

När detta händer startar STP en omräkning av topologin (recalculation). Under denna process kan vissa portar ändra tillstånd, till exempel från blocking till forwarding, för att skapa en ny loopfri struktur.

Till exempel kan en tidigare blockerad länk aktiveras om en annan länk slutar fungera. På så sätt bibehålls nätverkets redundans, samtidigt som kravet på en loopfri topologi upprätthålls.

Notera att den tidigare redundanta länken mellan S4 och S5 nu blockeras av för att kompensera den felaktiga länken mellan S2 och S4. Trots detta finns det fortfarande endast en väg mellan varje switch och rotbryggan.