Spanning Tree

Odborná počítačová terminologie je dnes samostatným světem, který žije vlastním životem, a který si sám vytváří vlastní nové termíny. Přesto ale na počátku počítačová věda převzala mnoho termínů z jiných disciplín, a některé z nich dokonce obohatila měrou, o jaké se původním oborům ani nesnilo.

Jedním z nejvýznamnějších "dodavatelů" bezesporu byla ta část matematiky, která se honosí názvem teorie grafů. Zde se běžně operuje pojmy jako strom, kořen, list či les, a ty se natolik zalíbily lidem od počítačů, že je převzali i s jejich původním významem.

Jednou z oblastí informatiky, ve které se stromům zvláště dobře daří, jsou i počítačové sítě. Jak jsme si již několikrát naznačili, mohou mít počítačové sítě topologii sběrnicovou, kruhovou, hvězdicovitou, stromovitou (či ještě obecnější, kterou nelze zahrnout do žádné z těchto kategorií), přičemž právě stromovitá struktura je v současné době velmi oblíbená, díky nástupu kroucené dvoulinky, rozbočovačů (hub/ů) a tzv. strukturované kabeláže vůbec.

Když jsme si v CW 41/93 vysvětlovali, co je most (anglicky: bridge), a popisovali způsob fungování samoučícího se (self-learning) mostu, zmínili jsme se o jedné zajímavé drobnosti: pro správnou funkci tohoto druhu mostů je nezbytně nutné, aby síť měla přísně stromovitou strukturu - jinak totiž může dojít k tomu, že samoučící se most doslova "zblbne".

Připomeňme si nejprve, v čem spočívá podstata samostatného učení: most si sám odvozuje skutečnou topologii sítě z toho, odkud přijímá bloky dat od konkrétních odesilatelů. Jestliže například přijme ze směru A (přesněji: z kabelového segmentu A) datový rámec od odesilatele X, pak si z toho odvodí, že uzel X leží právě v tomto směru, a veškeré rámce, adresované uzlu X jako příjemci, pak bude posílat směrem A.

Teď si ale představme, že by most "zaslechl" rámec od jednoho a téhož odesilatele ze dvou, či dokonce z více různých směrů současně. Co by si měl odvodit pak?

Tato situace, která musí samoučící se most dokonale zmást, přitom není zdaleka vyloučená. K tomu, aby mohla nastat, stačí jediné: existence redundantních spojení, neboli více jak jedné možné cesty mezi dvěma uzly sítě. Kdo by ale mohl zájem na tom, aby něco takového existovalo?

Odpověď je velmi jednoduchá - redundantní spojení zvyšují celkovou spolehlivost sítě, protože zajišťují existenci alespoň jedné cesty i v případě výpadku některého spoje či přepojovacího uzlu. Pokud bychom si pak skutečnou topologii sítě představovali jako graf, projevovala by se existence těchto redundantních spojení v tom, že příslušný graf by obsahoval cykly.

Redundantní spojení jsou nejčastěji vytvářena zcela záměrně, za účelem zvýšení spolehlivosti či rozložení zátěže přenosových cest. Někdy ale ke vzniku redundance dochází nechtěně - ve složitých soustavách vzájemně propojených sítí s nepřehlednou topologií může zapojením nového mostu snadno dojít k nepředvídanému "zacyklení".

Existence redundantních spojení je na jedné straně žádoucí (zvyšují spolehlivost), ale na druhé straně znemožňuje správné fungování samoučících se mostů. Jak z toho ven?

Řešením, které jsme si avizovali již v CW 41/93, je vybavit mosty dodatečnou inteligencí, která jim umožní vyrovnat se i s redundantními spojeními. To, co samoučícím se mostům na redundantních spojích vadí, je právě existence cyklů v neorientovaném grafu, který reprezentuje skutečnou topologii sítě. "Inteligentní" mosty se proto potřebují navzájem domluvit, a z cyklického grafu vybrat a používat takovou podmnožinu, která již nebude obsahovat žádné cykly, ale bude stále ještě zajišťovat existenci přenosové cesty mezi každými dvěma uzly, mezi kterými existovalo spojení i v původním cyklickém grafu. V terminologii teorie grafů by se jednalo o neorientovaný acyklický podgraf, neboli o tzv. kostru (která je v případě neorientovaného grafu vždy stromem). Odpovídající anglický ekvivalent, který se používá i v souvislosti s mosty, je Spanning Tree. V doslovném překladu jde o "strom, který pokrývá" (některé starší odborné prameny tento termín p řekládaly do češtiny jako: "napnutý strom").

Aby jednotlivé mosty dokázaly ve své vzájemné součinnosti takovýto "spanning tree" nalézt, potřebují k tomu vhodný algoritmus. Tento je označován jako Spanning Tree Algorithm (zkratkou STA). Původně byl vyvinut firmami DEC a Vitalink, později však byl přijat jako standard americké společnosti elektrotechnických a elektronických inženýrů (společností IEEE, v rámci její řady standardů IEEE 802). Součástí tohoto standardu je mj. i protokol pro vzájemnou komun ikaci, pomocí které se jednotlivé mosty vzájemně domlouvají na nejvhodnější acyklické topologii. Z této vzájemné domluvy vychází jeden most v roli tzv. kořenového mostu (root bridge), a všechny ostatní mosty vybírají ze všech svých směrů právě jeden, který prohlásí za "kořenový" (ve smyslu: vedoucí ke kořenovému mostu). Tím vzniká přísně stromovitá (a tudíž acyklická) struktura, v jejímž kořeni je kořenový most.

Celý algoritmus je navíc řešen tak, aby při výpadku některého mostu či spojení dokázal využít existenci redundantních spojení a zajistil automatické zotavení celé sítě.