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 managementem zjistí pomocí protokolu topologii sítě a odpojí redundantní spoje, které v síti způsobují množení broadcastů. Protokol také 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.. Mezi další vylepšení patří: Multiple Spanning Tree Protocol (IEEE 802.1s), Rapid Spanning Tree Protocol (IEEE 802.1w), Shortest Path Bridging (IEEE 802.1aq-2012)

Popis fungování protokolu 

Topologii místní sítě LAN lze zobrazit jako graf, jehož uzly jsou switche (mosty) a kabely s koncovými segmenty. Úkolem protokolu je přerušit všechny redundantní spoje tak, aby zůstala zachována kostra grafu (spanning tree). Správce sítě může ovlivnit, jaké spoje se pro kostru grafu vyberou pomocí změny nastavení. Kostru grafu lze najít za použití následujících pravidel:

Výběr kořenového (hlavního) mostu Kořenový most (bridge, resp. switch) je most s nejmenším identifikátorem. Každý most má nastavitelnou prioritu (danou číslem) a adresu MAC. Mostový identifikátor je složen z obou těchto čísel spojených dohromady (priorita mostu + MAC = 32768.0200.0000.1111). Výchozí hodnotou tohoto identifikátoru jsou čísla 32768 a mohou být nastaveny pouze v násobcích 4096 (kostra grafu používá 12 bitů v identifikátoru). Při porovnávání dvou identifikátorů, je porovnána jejich priorita a MAC adresy jsou porovnány pouze v případě, pokud je identifikátor stejný. Switch s nejnižší prioritou bude považován za 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 Kostra graf má tu vlastnost, že zprávy poslané z libovolného připojeného zařízení automaticky použijí cestu do kořenového mostu s nejmenšími náklady, tj. je zvolena 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 identifikátorem. Kořenovým portem je tedy ten, připojený k mostu s nejnižším číslem.

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 nízkým identifikátorem 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žší identifikátor 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 číslo identifikátor 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 (standardně = 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žší náklady na kořenový most – určuje přepínač s nejnižšími náklady na kořenový most
 Nejnižší identifikátor mostu– určuje kořenový most
 Nejnižší identifikátor odesilatele – v případě více switchů, které mají stejné náklady na kořenový most
 Nejnižší číslo port odesílatele – pokud switch má několik možných cest, kde:
 Identifikátor mostu = priorita = (16 bitů) + identifikátor mostu + [MAC adresa] (48 bitů), priorita (výchozí most je 32768)
 Identifikátor portu = priorita = (8 bitů) + identifikátor + [číslo Interface] (12 bitů), priorita (výchozí port je 128)

Reference

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.
 
 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

Komunikační protokoly počítačových sítí
OSI protokoly
Síťová architektura
Grafové algoritmy
Ethernet