Rapid Spanning Tree Protocol

RSTP je protokol rýchleho vetviaceho sa stromu, ako by sa dal voľne preložiť názov
Rapid Spanning Tree Protocol. Pracuje na druhej vrstve OSI. Je evolúciou štandardu IEEE 802.1D . Nové vydanie štandardu 802.1D - IEEE 802.1D-2004 teda zahŕňa štandardy IEEE
802.1t-2001 (802.1D Maintenance) a IEEE 802.1w (Rapid Reconfiguration of Spanning Tree).

Princíp fungovania 
RSTP nastavuje stavy portov každého portu sieťového mostu v BLAN. RSTP zabezpečuje, že stabilné pripojenie poskytované každým sieťovým mostom medzi jeho portami a individuálnymi LAN sieťami, ktoré
sú k týmto portom pripojené je predvídateľné, spravovateľné, úplné, jednoduché
a symetrické. RSTP okrem toho zabezpečuje, že nevznikajú dočasné slučky
v aktívnej topológii v prípade, že sieť sa musí prekonfigurovať v dôsledku
poruchy, odobratia alebo pridania sieťového zariadenia a že chybná informácia
o umiestnení chybného zariadenia sa po rekonfigurácii odstráni z filtrovacej
databázy.

Každý zo sieťových mostov v sieti posiela konfiguračné správy . Každá konfiguračná správa obsahuje prioritný vektor vetviaceho sa stromu, ktorý identifikuje jeden most ako koreňový most siete a umožňuje každému mostu vypočítať si vlastnú najnižšiu cenu cesty k tomuto koreňovému mostu, ktorá sa ďalej odošle v konfiguračnej správe. Rola koreňového portu je pridelená jednému z portov mostu, ktorý ponúka najnižšiu cenu cesty ku koreňovému mostu a rola predurčeného portu je pridelená jednému z portov pripojených ku každej zo sietí, ktoré ponúkajú najnižšiu cenu cesty z tejto siete ku koreňovému mostu. Roly náhradného portu a záložného portu sú pridelené portom, ktoré poskytujú pripojenie pri poruche iného sieťového komponentu.

Stavové automaty súvisiace s rolami portov udržujú a menia stavy portov , ktoré riadia odosielanie a učenie sa  rámcov MAC prenosovej jednotky, podporujú a spravujú kvalitu MAC služieb. V stabilnej sieti sú koreňové a predurčené porty v stave odosielania alebo učenia sa, kým náhradné, záložné a blokované porty sú v stave odmietania.

Rola každého portu sa mení v prípade, že most, port mostu alebo LAN zlyhá, pridá sa alebo sa odoberie zo siete. Prechod portu do stavu učenia sa alebo odosielania je oneskorený, teda porty môžu dočasne prejsť do stavu odmietania kvôli zaručeniu zanedbateľného množstva zle usporiadaných a duplikovaných rámcov.

RSTP poskytuje rýchlu obnovu pripojenia, čím sa minimalizuje strata rámcov. Nový koreňový port a predurčené porty pripojené k P2P sieťam môžu prejsť do stavu odosielania bez toho, aby museli čakať na vypršanie časovačov protokolu. Koreňový port môže prejsť do stavu odosielania bez toho, aby musel prijímať alebo posielať správy z iných mostov, zatiaľ čo predurčený port pripojený k P2P LAN môže zmeniť stav, až keď príjme explicitne zadanú rolu od iného mostu zapojeného v sieti. Oneskorenie odosielania, ktoré používa predurčený port pripojený k LAN, je dosť dlhý nato, aby ostatné mosty zapojené v tejto sieti mohli prijať a zareagovať na odosielané správy, a tiež je nezávislý od celkovej veľkosti siete. Ak všetky LAN v sieti sú P2P, RSTP časovače definujú najväčšie oneskorenia, ktoré nastanú iba v prípade straty správ alebo v prípade prekročenia prenosového limitu.

Koreňový port pripojený k LAN, ku ktorej nie sú pripojené žiadne iné mosty, môže byť administratívne nastavený ako hraničný port. RSTP sleduje LAN pre zaistenie, že žiadne iné mosty nie sú k nej pripojené, dokonca môže byť nastavené na automatickú detekciu hraničných portov. Každý hraničný port prechádza priamo do stavu odosielania, pokiaľ neexistuje žiadna možnosť vytvorenia slučky.

Matematický základ RSTP 
V matematickej oblasti teórie grafov – vetviaci sa strom T súvislého neorientovaného grafu G je strom zložený zo všetkých vrcholov a niektorých (pravdepodobne všetkých) hrán grafu G. Neoficiálne je vetviaci sa strom grafu G výber jeho hrán, ktoré tvoria strom spájajúci všetky vrcholy. To znamená, že každý vrchol je pripojený k stromu, ale nie sú vytvorené žiadne slučky. Na druhej strane, každé zo spojení grafu G musí patriť do stromu T.

Vetviaci sa strom súvislého grafu G môže byť tiež definovaný ako maximálna množina hrán grafu G, ktorá neobsahuje slučky alebo ako minimálna množina hrán, ktorá spája všetky vrcholy.

Všeobecne, vetviaci sa les ľubovoľného (pravdepodobne nesúvislého), neorientovaného grafu G je maximálny les ktorý je subgrafom G. Ekvivalentne, vetviaci sa les je zjednotenie vetviacich sa stromov pre každý súvislý komponent grafu G.

V určitých oblastiach teórie grafov je tiež užitočné nájsť minimálny vetviaci sa strom vyváženého grafu.

Prvý algoritmus na hľadanie minimálneho vetviaceho sa stromu bol vyvinutý českým vedcom Otakarom Borůvkom v roku 1926. Jeho zámerom bolo efektívne elektrické pokrytie Čiech. V súčasnosti sú bežne používanými algoritmami Primov algoritmus a Kruskalov algoritmus. Ďalším zriedkavo používaným algoritmom je reverse-delete algoritmus, ktorý je reverzný ku Kruskalovému algoritmu.

Najrýchlejší algoritmus minimálneho vetviaceho sa stromu vyvinul Bernard Chazelle a bol založený na Borůvkovom algoritme.

Stavy a role portov 
Štandard IEEE 802.1D definuje tieto štyri rôzne stavy portov:
 počúvanie
 učenie sa
 blokovanie
 odosielanie

Stav portu je vyberaný na základe toho, či blokuje alebo preposiela sieťovú premávku a rola portu zohráva úlohu v aktívnej topológii (koreňový port, predurčený port, atď.). Napríklad z operatívneho pohľadu nie je žiaden rozdiel medzi portom v stave blokovania a v stave počúvania. Obidva odmietajú rámce a neučia sa MAC adresy. Skutočný rozdiel je v rolách, ktoré im priradí algoritmus vetviaceho sa stromu. Spoľahlivo sa dá predpokladať, že port v stave počúvania je buď predurčený alebo koreňový port a je na ceste k tomu, aby prešiel do stavu odosielania. Žiaľ, ak je port v stave odosielania, nie je možné z tohto stavu usúdiť, či je port koreňový alebo predurčený. Takto sa demonštruje zlyhanie terminologie založenej iba na stavoch portov. RSTP teda rozlišuje rolu a stav portu, aby sa rola portu dala jednoznačne určiť.

Stavy portov 
Oproti 802.1D sú v RSTP iba tri stavy portov, ktoré korešpondujú s tromi operačnými stavmi. Stavy zablokovaný, blokovanie a počúvanie, definované v 802.1D, sú spojené do osobitného 802.1w stavu odmietanie.

Role portov 

Rola portu je premenlivo pridelená danému portu. Oproti štandardu 802.1D je niekoľko zmien. Rola koreňového portu a predurčeného portu ostala tá istá, no rola blokujúceho portu sa rozdelila na rolu záložného portu a rolu náhradného portu. STA rozlišuje roly portov na základe BPDU.
Pre jednoduchosť sa dá povedať, že existuje metóda, ktorá porovná dve BPDU a rozhodne, či jedna z nich je viac užitočná ako ostatné. Toto je založené na hodnote uloženej v BPDU.

Port, ktorý príjme najlepšiu BPDU na tomto moste, je koreňový port. Toto je teda port, ktorý je najbližšie ku koreňovému mostu z hľadiska ceny cesty. STA zvolí iba jeden koreňový most v celej premostenej sieti (na každú VLAN). Koreňový most odosiela BPDU, ktoré sú užitočnejšie ako BPDU z ktoréhokoľvek iného mostu. Koreňový most je jediný most v sieti, ktorý nemá koreňový port. Všetky ostatné mosty prijímajú BPDU aspoň na jeden port.

Port je v role predurčeného, ak je schopný poslať najlepšiu BPDU na segmente, ku ktorému je pripojený. 802.1D most spája rôzne segmenty, ako napríklad Ethernet segment, na vytvorenie premostenej domény. Na danom segmente môže byť iba jedna cesta smerom ku koreňovému mostu. Ak sú takéto dve, tak je v sieti vytvorená slučka. Všetky mosty pripojené k danému segmentu prijímajú BPDU od všetkých ostatných. Zhodnú sa, že most, ktorý odosiela najlepšie BPDU, bude predurčený most pre daný segment. Port na tomto moste, ktorý tomu odpovedá, je predurčený port.

Role náhradného a záložného portu odpovedajú stavu blokovania v 802.1D. Blokovaný port je definovaný ako port, ktorý nie je predurčený a ani koreňový. Blokovaný port prijíma užitočnejšie BPDU ako tie, ktoré posiela na svoj segment. Treba si uvedomiť, že port samozrejme potrebuje prijať BPDU, aby ostal blokovaný. Na tento účel RSTP poskytuje tieto dve role.

Náhradný port prijíma užitočnejšie BPDU od iného mostu a teda je to port blokovaný.

Záložný port prijíma užitočnejšie BPDU z toho istého mostu, na ktorom sa nachádza a tiež to je port blokovaný.

Rozdiel medzi náhradným a záložným portom už je interne vyriešený v rámci 802.1D. Vysvetlenie spočíva v tom, že náhradný port poskytuje alternatívnu cestu ku koreňovému mostu a preto môže nahradiť koreňový port v prípade jeho poruchy. Ale záložný port poskytuje redundantné (nadbytočné) pripojenie k tomu istému segmentu a preto nemôže zaručiť alternatívne pripojenie ku koreňovému mostu.

Rýchly prevod do stavu odosielania 
Rýchly prechod je najdôležitejšia funkcia predstavená v 802.1w. RSTP je schopný prepnúť port do stavu odosielania bez toho, aby závisel na nastaveniach časovačov. Na dosiahnutie rýchlej zmeny stavu portu sa protokol spolieha na dve premenné: hraničný port a typ linky.

Hraničné porty 
Všetky porty pripojené priamo ku koncovým staniciam nemôžu vytvoriť slučky v sieti. Preto hraničný port priamo prechádza do stavu odosielania a preskakuje stavy počúvania a učenia sa. Tento port neinicializuje zmenu topológie, ak sa linka prepne. Hraničný port, ktorý príjme BPDU automaticky stráca status hraničného portu a stáva sa normálnym portom vetviaceho sa stromu. Pre hraničný port existuje užívateľské nastavenie a prevádzková hodnota.

Typ linky 
RSTP docieli rýchly prechod do stavu odosielania iba na hraničných portoch a na P2P linkách. Typ linky je automaticky odvodený z duplexného módu linky. Port, ktorý pracuje v obojsmernom móde (full duplex) je považovaný za P2P, zatiaľ čo port pracujúci v jednosmernom móde (half duplex) je štandardne stanovený ako zdieľaný port. Toto automatické nastavenie typu linky môže byť prestavené explicitným nastavením. V súčasných sieťach s prepínačmi väčšina liniek pracuje v obojsmernom móde, takže RSTP s nimi pracuje ako s P2P linkami a teda sú kandidátmi na rýchly prechod do stavu odosielania.

Mechanizmus zmeny topológie 
Ak 802.1D most deteguje zmenu topológie, použije spoľahlivý mechanizmus, aby najprv upozornil koreňový most. Ak je koreňový port informovaný o zmene sieťovej topológie, nastaví TC (návesť zmeny topológie) návesť v BPDU a odošle ju. Tá je prenesená k všetkým mostom v sieti. Ak most príjme BPDU s nastavenou TC návesťou, zmenší čas vypršania platnosti položiek v premosťovacej tabuťke na hodnotu forward delay. Týmto sa zabezpečí relatívne rýchle odstráňovanie starých informácií. Tento mechanizmus zmeny topológie je oproti STP úplne prerobený.

V RSTP spôsobujú zmenu topológie iba nehraničné porty, ktoré prejdú do stavu odosielania. To znamená, že strata spojenia nie je považovaná za zmenu topológie na rozdiel od 802.1D (port, ktorý prejde do stavu blokovania negeneruje zmenu topológie).

TCN správy (správy s nastavenout TC návesťou) sa v sieti šíria veľmi rýchlo, keďže most, ktorý takéto srávy príjme ju odošle na všetky predurčené porty. Šírenie sa TC správ je jednokrokový proces.

Je fakt, že iniciátor zmeny topológie rozposiela túto informáciu po sieti, na rozdiel od 802.1D kde to robil iba koreňový most. Mechanizmus je teda oveľa rýchlejší. Nie je nutné čakať na koreňový most, kým tým bude oboznámený a začne obhajovať zmenu topológie celej siete.

Kompatibilita s STP 

RSTP je schopné interpolovať s pôvodným STP protokolom. Je nutné poznamenať, že výhody 802.1w, čiže rýchla zmena stavov sa týmto stráca.

Každý port udržiava premennú, ktorá definuje protokol na danom segmente. Ak sa port pripojí, spustí sa časovač. Počas toho sa aktuálne priradený STP alebo RSTP mód zablokuje. Ak tento časovač vyprší, port sa adaptuje na mód, ktorý odpovedá najskôr prijatej BPDU. Po zmene operačného módu ako dôsledku prijatej BPDU, spomínaný časovač sa reštartuje. Takto je určená frekvencia možnej zmeny módu.

Napríklad predpokladajme, že máme v sieti zapojené dva mosty. Jeden z nich je predurčený pre tento sieťový segment (most A). Teraz sa k sieti pripojí most C, ktorý podporuje iba STP. Keďže 802.1D mosty ignorujú RSTP BPDU správy a zahadzujú ich, tento most je presvedčený, že na tomto sieťovom segmente už nie je zapojený žiaden ďalší most a začne odosielať svoju podradnú správu vo formáte 802.1D. Most A, ktorý bol označený ako predurčený, príjme túto správu a na základe toho zmení operačný mód na 802.1D, ale iba pre tento port. Výsledkom toho je, že najneskôr pripojený STP most rozumie správam od tohto mostu a akceptuje ho ako predurčený most pre tento segment. Ak je v tomto špecifickom prípade STP most odobratý, prvý most na tomto porte stále operuje v STP móde aj napriek tomu, že je schopný pracovať oveľa efektívnejšie v RSTP móde s jediným susedným mostom B. Je to dôsledok toho, že tento most nedokáže zistiť, že STP most bol zo segmentu odobraný. V tomto zriedkavom prípade je nutný zásah užívateľa, ktorý reštartuje detekciu protokolu pre tento port manuálne.

Referencie 

Počítačové siete
Smerovanie