Spanning Tree Protocol

Spanning Tree Protocol (zkratka STP, v překladu protokol kostry grafu) je v informatice název pro síťový protokol, který v ethernetových LAN sítích odstraňuje smyčky. Switch s managmentem zjistí pomocí protokolu topologii sítě a odpojí redundantní spoje, které v síti způsobují množení broadcastů. Protokol též umožňuje automaticky aktivovat odpojené spoje v případě, kdy dojde k přerušení aktivní cesty. Spanning Tree Protocol je standardizován jako IEEE 802.1D. STP je založeno na algoritmu, který navrhla Radia Perlmanová ve firmě Digital Equipment Corporation.

Provoz protokolu

1.Příklad sítě. Číslované kolonky představují mosty (číslo představuje bridge ID). Mraky představují síťové segmenty.

2. Nejmenší Most ID je 3. Proto je most 3 je kořenový (hlavní) most.

3. Cesta s nejnižšími náklady na cestu od mostu 4 ke kořenovému mostu prochází segmentem sítě C.

4. Nejmenšími náklady ke kořenu od síťového segmentu e prochází most 92. Proto určený port pro síť segmentu E je port, který se připojuje na most 92 na segmentu sítě E.

Operace protokolu lze představit jako směsice mostů v místní síti (LAN), která může být zobrazena pomocí grafu, jehož uzly jsou mosty a segmenty LAN (nebo kabely), jehož okraje jsou rozhraní spojující síťové mosty (bridge) v segmenty. Chcete-li přerušit smyčku v síti při zachování přístupu ke všem segmentům LAN, mosty společně vypočítají spanning tree. Správce sítě tak může snížit množství spanning tree v případě potřeby tím, že změní některé konfigurační parametry tak, aby si protokol vybral hlavní cestu. Spanning Tree Protokol lze určit pomocí následujících pravidel.

Výběr kořenového (hlavního) mostu

Kořenový most je most s nejmenším bridge ID. Každý takovýto most má tedy nastavitelnou prioritu (danou číslem) a adresu MAC. Bridge ID obsahuje obě tato čísla spojená dohromady: priorita Bridge + MAC (32768.0200.0000.1111). Výchozí hodnotou bridge ID je číslo 32768 a mohou být nastaveny pouze v násobcích 4096 (Spanning tree používá 12 bitů rozšířeného systému ID). Při porovnávání dvou bridge ID, jsou tato čísla porovnány prioritně a MAC adresy jsou porovnávány pouze v případě, pokud je bridge ID stejné. Switch s nejnižší prioritou tak bude kořenový. Pokud nastane opět shoda, pak bude kořenový switch ten s nejnižší prioritou a nejnižší MAC adresou. Například, je-li switch A (MAC = 0200.0000.1111) a B (MAC = 0200.0000.2222) a oba mají prioritu 32768 pak bude jako kořenový most vybrán switch A. Pokud by se síťovým administrátorům chtělo použít switch B, musí nastavit jeho prioritu tak, aby byla menší než 32768 nebo nakonfigurovat spanning tree jako primární nebo sekundární. Při konfiguraci lze použít jeden kořenový switch jako primární a další (sekundární) switche si automaticky změní prioritu podle výchozí konfigurace.

Určení nejmenších nákladů cesty ke kořenovému mostu

Spanning tree má tu vlastnost, že zprávy poslané z libovolného připojeného zařízení automaticky vyhledají cestu do kořenového mostu za použití nejmenších nákladů, tj. zvolená je ta cesta, do kořenového adresáře která má minimální náklady mezi všemi ostatními cestami. Náklady na křížení cesty lze spočítat jako součet všech nákladů na cestě (doby potřebné pro doručení zpráv do kořenového mostu). Různé technologie mají různé výchozí náklady na segmenty sítě. Správce může konfigurovat náklady na konkrétní segment sítě. Vlastnost, která zprávy donutí vždy projít nejméně nákladnými cesty do kořenového adresáře je zaručena následujícími dvěma pravidly:

Cesta nejnižšími náklady od každého mostu

Pokud byl vybrán kořenový most, každý most určuje jisté náklady na každou možnou cestu od sebe ke kořenu. Z těchto nákladů se vybere cesta s počtem nejmenších nákladů (cesta nejnižšími náklady ). Port připojení k této cestě se stává kořenovým portem (root port) tohoto mostu.

Cesta nejnižšími náklady od každého segmentu sítě

Mosty na síťovém segmentu kolektivně určí, který most má nejvýhodnější cestu ze segmentu sítě do kořenového adresáře. Port připojení tohoto mostu do segmentu sítě je pak určený port (designated port) pro daný segment.

Zakázat všechny ostatní kořenové cesty

Každý aktivní port, který není kořenem portu nebo určený port je blokován.

Změny v případě vazby

Výše uvedené pravidla mírně zjednodušují situaci, protože v reálu je možné, že mohou existovat vazby, například dva nebo více portů na jednom síťovém mostě, nebo dva čí více mostů na stejném segmentu sítě mají stejné náklady na cestu. Pro vyřešení těchto případů se používá:

Vypínací vazby na kořenové porty

Při více cest směrem od mostu jsou vybrané nejméně nákladné trasy. Vybraná cesta používá most s nejnižším bridge ID. Kořenovým portem je tedy ten, připojený k mostu s nejnižším bridge ID.

Vypínací vazby na určených portech

Pokud více než jeden most na segmentu vede k nejméně nákladné cestě směrem ke kořenovému adresáři, potom se most s dolní bridge ID používá k předávání zpráv do kořenového adresáře. Port připojující tento most do segmentu sítě je určený port pro segment. Na obr.4 jsou vidět dvě stejně nákladné cesty od síťového segmentu D na kořenový most, kde cesta prochází přes most 24 a druhá přes most 92. Nejnižší bridge ID je 24, takže určuje, že určený port je port kterým je síťový segment D připojen k překlenutí 24. Pokud by bridge ID bylo stejné, pak bude most s nejnižší adresou MAC mít určený port.

Finální vypínací vazba

V některých případech může být problémem, pokud jsou dva mosty spojeny pomocí více kabelů. V tomto případě je více portů na jednom mostě bráno jako kandidát pro kořenový port. V tomto případě se použije cesta, která prochází z portu na most který má nejnižší identifikátor portu. Používá se prioritní port (standartně = 128) + číslo portu.

Nejvýhodnější cesta

V souhrnu určení nejvýhodnější cesty (cesty ke kořeni s nejméně náklady) se používá:

• Nejnižší bridge ID - určuje kořenový most
• Nejnižší náklady na kořenový most - určuje přepínač s nejnižšími náklady na kořenový most
• Nejnižší bridge ID odesilatel - v případě více switchu, které mají stejné náklady na kořenový most
• Nejnižší port ID odesílatele - pokud switch má několik možných cest, kde:
  • Bridge ID = priorita = (16 bitů) + ID[ MAC adresa ] (48 bitů),priorita (výchozí most je 32768)
  • Port ID = priorita = (8 bitů) + ID [ číslo Interface ] (12 bitů),priorita (výchozí port je 128)

Externí odkazy

• Cisco home page for the Spanning-Tree protocol family (informace o CST, MISTP, PVST, PVST+, RSTP, STP)
• Educational explanation of STP domovská adresa pro vývoj STP
• STP článek na Wireshark wiki zahrnuje PCAP-soubor pro zachycení STP cest.
• PERLMAN, Radia. Algorhyme [online]. University of California at Berkeley [cit. 2011-09-01]. Dostupné v archivu pořízeném z originálu dne 2011-07-19. 
• IEEE Standards
  • ANSI/IEEE 802.1D-2004 standard, kapitola 17
  • ANSI/IEEE 802.1Q-2005 standard,
• RFC
  • RFC 2674-1999, (Proposed standard, Definitions of Managed Objects for Bridges with Traffic Classes, Multicast Filtering and Virtual LAN Extensions)
  • RFC 1525-1993, (SBRIDGEMIB, proposed standard, Definitions of Managed Objects for Source Routing Bridges)
  • RFC 1493-1993 (BRIDGEMIB, draft standard, Definitions of Managed Objects for Bridges)
• Spanning Tree studie CCIE