Protokol razapinjućeg stabla

Protokol razapinjućeg stabla (STP) je mrežni protokol koji obezbeđuje lup-fri topologiju za bilo koju povezanu lokalnu mrežu. Osnovna funkcija STP je da prevent bridge loops and the broadcast radiation that results from them. Razapinjuće stablo takođe dozvoljava mrežnom dizajnu da priključi rezevne linkove da obezbedi automatski bek-up put ako aktivni link ne uspe, bez opasnosti od povezanih petlji, ili potrebe za ručnim uključivanjem/isključivanjem tih bek-up linkova.

Protokol razapinjućeg stabla (STP) je standardizovan u IEEE 802.1d. Kako ime kaže, pravi razapinjuće stablo unutar mreže povezane s lejer-2 mostovima(eternet svičevi), i isključuje one linkove koji nisu deo razapinjućeg stabla, ostavljajući jedinstveni aktivan put između dva povezana čvora.

STP je zasnovan na algoritmu koji je izumela Rejdia Prlmen dok je radila za Digital Ekvipment Korporejšn.

Protokolske operacije

Operacija je jednostavna, kao kolekcija mostova, u LAN može biti opisana kao grafikon čiji su čvorovi mostovi i LAN segmenti i čije su ivice interfejsi koji povezuju mostove do segmenata. Prekinuti petlje u LAN-u, dok se održava pristup svim LAN segmentima, mostovi kolektivno računaju razapinjuće stablo. Razapinjuće stablo ne predstavlja obavezno minimalno razapinjuće stablo. Administrator mreže može da smanji razapinjuće stablo, po potrebi, prepravljajući neke koniguracijske parametre, na način da utiče na izbor korena razapinjućeg stabla. Razapinjuće stablo koje mostovi računaju koristeći protokol razapinjućeg stabla može biti određen koristeći prateća pravila. Primer mreže desno, ispod, biće korišćena da ilustruje pravila.

1. Primer mreže. Kvadratići predstavljaju mostove. Oblačići predstavljaju mrežne segmente.

2. Najmanji most je pod brojem 3. Stoga je most 3 glavni most.

3. Pretpostavljajući da je vrednost poprečnog bilo kog mrežnog segmenta 1, najmanji put od mosta 4 do glavnog mosta vodi kroz mrežni segment c. Stoga, glavni port za most 5 je u segmentu c.

4. Najkraći put do glavnog od segmenta e ide preko mosta 92. Stoga odrećeni je port za segment e je port koji je povezan sa mostom 92 do mrežnog segmenta e.

5. Ovaj dijagram ilustruje sva stanja portova određena algoritmom razapinjućeg stabla. Bilo koji aktivan port koji nije glavni ili određeni je blokiran.

6. Posle neuspelog povezivanja, algoritam razapinjućeg stabla izračunava i razapinje novo minimalno stablo.

Biranje glavnog mosta. Glavni most razapinjućeg stabla je most sa najmanjom identifikacijom mosta. Svaki most ima konfigurisani, prioritetski broj i MEK adresu. Identifikacija mosta sadrži kombinovane brojeve - prioritet mosta + MEK (32768.02000.0000.1111). Prioritet mosta obično je 32768 i jedino može biti konfigurisan u umnožcima od 4096. U pređenju dve identifikacije mosta, prioritet je upoređen prvo, kada bi gledali pravi broj, sve ispod 32768... postaće kandidat za glavni. Ako su dva mosta jednakih prioriteta, onda će se MEK adrese uporediti; na primer, ako prekidač A(MEK = 0200.0000.1111) i B(MEK = 0200.0000.2222) oboje imaju prioritet od 32758 onda će prekidač A biti izabran kao glavni most. Ako bi administrator mreže voleo da prekidač B postane glavni most, moraju postaviti njegov prioritet da bude manji od 32768 ili da konigurišu razapinjujuće stablo.

Odrediti najmanju putanju do glavnog mosta. Sastvljeno razapinjuće stablo ima mogućnost da poruke od bilo kog povezanog uređaja do glavnog mosta pronađe najkraću putanju. Cena poprećne putanje je suma svih vrednosti segmenata na putu. Drugačije tehnologije imaju različite podrazumevane vrednosti za mrežne segmente.

Najmanja vrednost puta od svakog mosta. Nakon što je izabran glavni most, svaki most određuje vrednost svakog puta od njega do glavnog mosta. Od njih bira onaj sa najmanjom putanjom.

Najmanja vrednost puta iz svakog segmenta Mostovi na segmentu mreže zajedno određuju koji most ima najkraću putanju od segmenta mreže do glavnog. Port koji povezuje ovaj most do segmenta mreže je onda i određeni port za taj segment.

Onemogući sve druge puteve korena. Svaki aktivni port koji nije glavni port ili određeni port je blokiran.

Izmene u slučaju veza. Nvedena pravila malo pojednostavljuju situaciju, jr je moguće da postoje veze, na primer, dva ili više portova na jednom mostu su vezani za najkraće puteve do korena, ili dva ili više mostova na istom mrežnom segmentu imaju jednake najkraće puteve do korena. Da se probiju takve veze: Pekidanje veza za korenske portove. Kada ima više staza iz mosta sa najkraćim putem, izabrani put koristi susedni mosta sa manjom identifikacijom(ID). Na primer, na slici 3 ako je prekidač 4 povezan sa mrežnim segmentom D umesto C, bila bi dva puta dužine 2 do korena, jedna putanja prelazi kroz most 24, a druga kroz most 92. POšto postoje dve najmanje putanje, niža identifikacija mosta (24) će se koristiti kao raskid veze u izboru koji put da koristi.

Prekidanje veze za određene portove. Kada više od jednog mosta na segmentu dovode do najmanjeg puta do korena, most sa nižom identifikacijom mosta se koristi da prosledi poruke u korenu. POrt koji pričvršćuje taj most na mrežni segment je port određen za segment. Na slici 4, postoje dva najkraća puta iz D segmenta mreže do korena., jedna ide preko mosta 24 a druga preko 92. Most sa manjom identifikacijom je 24, pa svič veze nalaže da je određeni port port kroz koji je mrežni segment D konektovan na most 24. Ako su identifikacije mostova jednake, onda će most sa najmanjom MEK adresom imati određen port. U svakom slučaju, gubitnik podešava port kao blokiran.

Konačni prekidač veza. U nekim slučajevima, još uvek može biti veza, kao kada su dva mosta povezana sa više kablova. U ovom slučaju, više portova na jednom mostu su kandidati za korenski port. U ovom slučaju, put koji prolazi kroz port na susednom mostu koji ima prioritet mosta se koristi.

Ukratko, sekvenca događaja da se odredi najbolje primljen BPDU je:

• Najniža identifikacija glavnog mosta
• Najkraći put do glavnog mosta
• Najniža identifikacija mosta pošaljioca
• Najniža identifikacija porta

Prenos podataka i vrednost STP-a

Tabela ispod prikažuje standardnu vrednost interfejsa za date prenose podataka

Prenos podataka	Vrednost STP (802.1D-1998)	Vrednost RSTP (802.1D-2004 / 802.1v)
4 Mbit/s	250	5,000,000
10 Mbit/s	100	2,000,000
16 Mbit/s	62	1,250,000
100 Mbit/s	19	200,000
1 Gbit/s	4	20,000
2 Gbit/s	3	10,000
10 Gbit/s	2	2,000

Protokol jedinice podataka mosta

Gorenavedena pravila opisuju jedan od načina utvrđivanja koje razapinjuće stablo će biti određeno algoritmom, ali napisana pravila zahtevaju poznavanje čitave mreže. Mostovi moraju da odrede koji je most glavni i primene pravila portova sa informacijama koje imaju. Da bi obezvedili da svaki most ima dovoljno informacija, mostovi koriste smecijalne okvire podataka zvani Protokol jedinice podataka mosta da bi razmenili informacije o identifikaciji mosta i gde se nalazi glavni most.

Mostovi šalju BPDU okvire koristeći jedinstvenu mek adresu porta kao izvorne adrese, i destinaciju višeslojne RSP adrese 01:80:C2:00:00:00.

Postoje tri vrste BPDU-a:

• Konfiguracijski BPDU, koristi se za odabir razapinjućeg stabla
• Topološko obaveštenje o promeni
• Prihvatanje topološkog obaveštenja o promeni

BPDU se redovno menja (standardno svake 2 sekunde) i uključuje prekidače da prate promene na mreži i pokrene i zaustavi prosleđivanje na portovima ako je zahtevano.

Kada se uređaj prvi put poveže na port sviča, on neće odmah početi da prosleđuje podatke. Nego će umesto toga proći kroz nekoliko stanja dok procesira BPDU i utvrdi topologiju mreže. Kada je host priključen kao npr. računar, štampač ili server port će uve biti u stanju prosleđivanja, iako posle odlaga od oko 30 sekundi dok prođe kroz sva stanja. Vreme utrošeno za prolazak kroz određena stanja određeno je vrednošću poznatom kao odloženo prosleđivanje. Međutim, ako je priključen drugi svič, port može da ostane u blokiranom modu ako se utvrdi da će izazvati petlju u mreži. Topološko obaveštenje o promeni BPDU koristi da informiše druge portove o promenama. TOP je ubačen u mrežu preko ne glavnog sviča i propagiran je do glavnog sviča. Po prijemu TOP-a, glavni svič će postaviti zastavicu za topološku promenu. Ova zatavica se propagira do ostalih svičeva da ih uputi o ostarelosti unosta tabele prosleđivanja.

RSP stanje portova sviča:

• Blokirano
• Slušanje
• Učenje
• Prosleđivanje
• Isključeno

Da bi se sprečilo čekanje kada se povezuje host sa svičom i tokom nekih promena u topologiji, BRSTP je razvijen i standardizovan u IEEE 802.1v, koji dozvoljava portu na sviču brzi prelaz i stanje prosleđivanja tokom ovih situacija

Polja protokola jedinica podataka mosta

Identifikacija mosta je polje unutar BPDU paketa. Dužine je 8 bajtova. Prva dva bajta određuju prioritet mosta, kao neoznačeni intidžer 0-65535. Poslednjih 6 bajtova su mek adresa sviča. U slučaju da je korišćen smanjivač mek adrese, prva dva bajta se koriste drugačije. Prva četiri bita su prioritet konfiguracije, a ostalih dvanaest bitova su VLAN identifikacija ili VRSP broj instance.

Napredovanje i proširenja

Prvi protokol razapinjućeg stabla je izmišnjen 1985-e u kompaniji Digital Ekvipment Korporejšn od strane Rejdia Perlman. Godine 1990, IEEE je objavio prvi standard za protokol, 802.1d, na osnovu algoritma dizajniranog od strane Perlmanove. Naknadne verzije su objavljene 1998 i 2004, uključujući različite ekstenzije.

Iako je svrha standarda da promoviše međusobni rad opreme različitih proizvođača, različite implementacije standarda ne moraju grantovati da rade, na primer, zbog realike u početnim podešavanjima tajmer. IEEE podstiče poizvođače da obezbede "Izjavu o implementaciji protokola za usaglašavanje", deklarišući koje su mogućnosti i opcije primenjene, da pomogne korisnicima da se utvrdi da li će različite implementacije raditi međusobno isprano.

Takođe, originalni Prlman insipirisan "protokol razapinjućeg stabla", pod nazivom DEC-STP, nije standard i razlikuje se od verzije IEEE u formatu poruke, kao i u podešavanjima tajmera. Neki mostovi implementiraju obadve, IEEE I DEC verzije za protokola razapinjućeg stabla, ali njihov međusobni rad može stvoriti probleme za administratora mreže, što ilustruje problem dikutovan u on-lajn Sisko dokumentu.

Brzi protokol razapinjućeg stabla

Godine 2001, IEEE uvodi brzi protokol razapinjućeg stabla (RSTP) kao 802.1v. RSTP omogućava znatno bržu konvergenciju razapinjućeg stabla posle promene topologije, uvođenje novih knvergencija ponašanja i uloge portova da se to uradi. RSTP je dizajniran tako da bude kompatibilan sa standarnim STP.

Dok STP može da za 30 do 50 sekundi odgovori na promene topologije, RSTP je obično u stanju da odgovori na promene rogu od 3 helo puta, ili u roku od nekoliko milisekundi o fizičkoj grešci linka. Takozvani "Helo tajm" je važan i konfigurišući vremenski interval koji se koristi od strane RSTP za više namena, njegova podrazumevana vrednost je 2 sekunde. 802.1d Standard IEEE-2004 sadrži RSTP i zastareli originalni STP standard.

Operacije brzog protokola razapinjućeg stabla

RSTP dodaje nove uloge za portove mostova kako bi se ubrzala konvergencija lnka neuspeha. Broj stanja portova može biti smanjen na tri, umesto prvobitnih pet.

Uloga portova mostova kod RSTP:

• Glavni
• Dizajniran
• Alternativan
• Bekap
• Isključen

RSTP stanja sviča:

• Onemogućen
• Učenje
• Prosleđivanje

Dodatni detalji RSTP operacija:

• Otkrivanje neuspeha glavnog sviča je urađeno 3 helo puta, što je 6 sekundi, ako podrazumevano vreme nije promenjeno.
• Portovi se mogu konfigurisati kao krajnji portovi ako su vezani na LAN a da nema drugih mostova povezanih. Ovi krajnji portovi prelaze direktno u stanje prosleđivanja. RSTP i dalje nastavlja da prati port za BPDU u slučaju da je most spojen. RSTP može da se konfiguriše da automatski detektuje krajnje portove. Čim most detektuje BPDU da dolazi ka krajnjem portu, port više nije krajnji.
• Za razliku od STP, RSTP će odgovoriti na BPDU poslate iz pravca glavnog mosta. RSTP most će "predložiti" informacije on njegovom razapinjućem stablu svojim određenim portovima. Ako je drugi most RSTP prima ove informacije i utvrdi da je nadređeni glavni, postavlja sve drugi portove na "onemogućeno“. Most može poslati "dogovor" sa prvog mosta potvrđujući svoju superiornu informaciju o razapinjućem stablu. PRvi most, po dobijanju ovog sporazuma, zna da može brzo da prosledi port za prosleđivanje stanja mimo tradicionalnog slušanja/učenja prosleđivanja stanja. Ovo u suštini stvara kaskadni efekat od glavnog mosta gde svaki određeni most nudi na svojim susedima da utvrdi da li može da napravi brzu tranziciju. Ovo je jedan od glavnih elemenata koji omogućava da RSTP postigne bržu konvergenciju nego STP.
• Kao što je rečeno iznad, RSTP održava rezervne detalje o odbacivanju statusa portova. Time se izbegavaju vremenska ograničenja ako je za prosleđivanje portova zakazalo ili BPDU nije primljen na osnovi porta u određenom intervalu.
• RSTP će se vratiti na nasleđe STP na interfejsku ako je naslđena verzija STP BPDU detektovana na tom portu.

Po-VLAN razapinjuće stablo i po-VLAN razapinjuće stablo pluse

U eternet svič okolini gde postoje više virtualnih LAN-ova, često je poželjno napraviti više razapinjućih stabala tako da saobraćaj iz različitih VLAN-ova koristi različite linkove. Siskova verzija STP-a se zove po-VLAN razapinjuće stablo (PVST) i po-VLAN razapinjuće stablo plus (PMST+) pravi odvojena razapinjuća stabla za svaki VLAN. Oba PVST I PVST+ protokoli su Siskovo vlasništvo i oni ne mogu biti korišćeni u većini third party switches. Neka oprema iz Fors10 Netvorks, Ekstrim Netvorks, Evia and Blejd Netvork Tehnolodži podržavaju PVST+. Ekstrim Netvork to radi sa dve prepreke (nedostatak podrške na portovima gde se povezuje VLAN i takođe VLAN sa ID 1). PVST radi samo sa ISL (Siskov porotokola za enkapsuliranje VLAN-a) zahvaljujući ugrađenim ID-om razapinjućeg stabla. Ovo je opšti protokol na Sisko svičevima koji podržavaju ISL. Zahvaljujući velikom prodoru IEEE 802.1ku VLAN standardu i PVST-ovom zavisnošću od ISL, Sisko je definisao drugačiji PVST+ standard koji je kompatibilan sa enkapsulacijom 802.1ku. Ovo je postalo standardni protokol za Sisko svičeve kada je Sisko ukinuo i uklonio podršku za ISL sa njegovih svičeva. PVST+ može preko tunnel MSTP regiona.

Brzo po-VLAN razapinjuće stablo

Siskova verzija brzog protokola razapinjućeg stabla. Stvara razapinjuće stablo za svaki VLAN, kao PVST. Sisko zove ovo brzi po-VLAN razapinjuće stablo (RPVST).

VLAN protokol razapinjućeg stabla

U Džuniper Netvorks okruženju, ako je kompatibilnost sa Siskovim PVST protokolom zahtevano, VLAN protokol razapinjućeg stabla se moće konfigurisati. VSTP sadrži odvojene instance razapinjućeg stabla za svaki konfigurisani VLAN u sviču. VSTP protokol jedini podržava EH I MH serije iz Džuniper Netvorks. Tu su i dva uslova za kompatablinost sa VSTP: VSTP podržava samo 253 razlitičte topologije razapinjućeg stabla. Ako ima veše od 253 VLANA, preporučuje se konfiguracija RSTP-a u zamenu za VSTP. MVRP ne podržava VSTP. Po standardu, VSTP koristi RSTP protokol kao njegov unutrašnji protokol razapinjućeg stabla.

Za više informacija oko konfigurisanja VSTP na Džuniper Netvorks svičevima, pogledati zvaničnu dokumentaciju.

Protokol više razapinjućih stabala

Protokol više razapinjućih stabala MSTP, definisan je u IEEE 802.1S i kasnije spojen u IEEE 802.1ku-2005, definiše nadogradnju na RSTP za dalja korisna razvijanja VLAN-a. Ovaj "po-VLAN" protokola za više razapinjućih stabala konfiguriše odvojena razapinjuća stabla za svaku grupu VLAN-ova. Ako bi bio samo jedan VLAN na mreži, svaki STP bi radio odgovarajuće. Ako bi mreža sadržala više od jednog VLAN-a, mreža konfigurisana jedinstvenim STP bi radila, ali bi bilo moguće bolje korišćenje alternativnih puteva dostupnih korišćenjem alternativnih razapinjućih stabala za različite VLAN-ove ili grupu VLAN-ova.

MSTP omogućava formiranje MST regiona koji mogu pokrenuti više instanci (MST MSTI). Višestruke regije i drugi STP mostovi su interno povezani korišćenjem jednog zajedničkog razapinjućeg stabla.

MSTP je sličan Siskovom sistemu protkola razapinjućeg stabla sa više instanci (MISTP), i ovo je evolucija protokola razapinjućeg stabla i brzog razapinjućeg stabla. Predstavljen je u IEEE 802.1s kao amandmant na 802.1ku 1998. Standard 802.1ku-2005 sada sadrži MSTP.

Za razliku od nekih implementacija "po-VLAN" razapinjućeg stabla, MSTP sadrži sve informacije o svom razapinjućem stablu u jednom BPDU formatu. Ne sam o da ovo smanjuje broj BPDU-sa koje LAN zahteva za komuniciranje sa informacijama razapinjućeg stabla za svaki VLAN, ali takođe osigurava povratnu kompatibilnost sa RSTP. MSTP radi ovo tako što kodira dodatne regionalne informacije po standardu RSTP BPDU-a dobro kao brojeve MSTI poruka. Svaka od ovih MSTI-a konfiguracionih poruka prenosi informacije za svaku instancu. Svakoj instanci može biti dodeljen broj konfigurisanih VLAN-ova i okvir dodeljen ovim VLAN-ovima rade u toj instanci razapinjućeg stabla kad god su unutar MST regiona. Da bi se izbeglo prenošenje celog VLAN-a u mapiranje celog razapinjućeg stabla u svakom BPDU-u, mostovi kodiraju MD5 otisak njihovih VLAN-ova u tabelu instance u MSTP BPDU-u. Ovaj otisak posle koriste drugi MSTP mostovi, uporedo sa drugim administrativno konfigurisanim vrednostima, da bi se utvrdilo da li je most u blizini u istom MST regionu kao i on.

MSTP je potpuno kompatibilan sa RSTP mostovima. Ovo ne dozvoljava samo kompatiblinost sa RSTP mostovima bez konfiguracijskih promena, causes any RSTP bridges outside of an MSTP region to see the region as a single RSTP bridge, regardless of the number of MSTP bridges inside the region itself. Da bi se dodatno olakšao pregled MST regiona kao jedinstveni RSTP most, MSTP Protokol koristi promenljive poznate kao preostali hmelj as a time to live counter instead of the message age timer used by RSTP. Vreme starosti poruke je povećano jednom kada informacije o razapinjućem stablu uđu u MST region, zato će RSTP mostovi videti region kao jedan "hmelj" i razapetom stablu. Portovi na ivici MST regiona povezani ili RSTP ili STP mostom ili krajnom tačkom su poznati kao granični portovi. Kao i u RSTP, ovi portovi mogu biti konfigurisani kao krajnji portovi da bi se olakšale brze promene na prosleđenim stanjima kada je konektovan na krajne tačke.

Najkraće povezivanje mostova

IEEE je odobrio IEEE 802.1aku standard maja 2012, takođe poznat i dokumentovan u većini knjiga o najkraćim putevima povezivanja. SPB dozvoljava svim linkovima da budu aktivni preko više jednakih puteva, i obezbede mnogo veću lejer-2 topologiju, bržu konvergenciju, i unaprede korisnost mrežne topoligije kroz povećanu propusnu moć izveđu svih uređaja. SPB objedinjuje više postojeće funkcionalnosti, uključujući protokol razapinjućeg stabla (STP), protokol sa više razapinjućih stabala (MSTP), brzo razapinjuće stablo (RSTP), i višestruki MEK registracioni protokol (MMRP) u jedan protokol. SPB je dizajniran da praktično eliminiše ljudske greške u konfiguraciji i čuva plag and plez konfiguraciju..

Literatura

• Perlman, Radia (2000). Interconnections, Second Edition. USA: Addison-Wesley. ISBN 978-0-201-63448-8. 

Spoljašnje veze

• Cisco home page for the Spanning-Tree protocol family (discusses CST, MISTP, PVST, PVST+, RSTP, STP)
• STP article in the Wireshark wiki Includes a sample PCAP-file of captured STP traffic.
• Perlman, Radia. „Algorhyme”. University of California at Berkeley. Arhivirano iz originala 19. 7. 2011. g. Pristupljeno 1. 9. 2011. 
• IEEE Standards
  • ANSI/IEEE 802.1D-2004 standard, section 17 discusses RSTP (Regular STP is no longer a part of this standard. This is pointed out in section 8.)
  • ANSI/IEEE 802.1Q-2005 standard Arhivirano na sajtu Wayback Machine (6. jul 2010), section 13 discusses MSTP
• RFCs
  • 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 Direct vs Indirect Link Failures - CCIE Study