Báječný svět počítačových sítí

Část X. Řízení přístupu klasifikace, řešení kolizí a propustnost

Lokální počítačové sítě (sítě LAN) mají na rozdíl od většiny rozlehlých sítí (sítí WAN) systematickou topologii, například do kruhu, do stromu či ve tvaru sběrnice. Pro vzájemnou komunikaci svých uzlů přitom používají přenosové médium, které je společně sdíleno více uzly. To umožňuje, aby vysílání jednoho uzlu přijímaly třeba všechny ostatní uzly najednou. Problém ovšem nastává v případě, pokud by chtělo vysílat více uzlů najednou. Pak musí nastoupit někdo či spíše něco, co zajistí, že se ze všech zájemců vybere jeden a pouze on pak bude vysílat. To je podstata řízení přístupu.



U rozlehlých sítí (sítí WAN) už jejich samotný název naznačuje, že jednotlivé uzly asi budou více vzdáleny od sebe a tak se pro jejich vzájemné propojení používají spíše dvoubodové spoje, vedené tak, jak je to ekonomicky i realizačně nejsnazší a nejefektivnější. Výsledek pak obvykle připomíná nějaký obecný graf, bez pravidelné (systematické) struktury. V případě lokálních sítí (sítí LAN) však bývá situace diametrálně odlišná. Geografická blízkost uzlů sítí LAN umožňuje jejich propojení nějakým systematickým způsobem například do kruhu, do hvězdy či stromu, do sběrnice atd. s využitím takového přenosového média, které má sdílený charakter. Tedy média, které je využíváno více uzly současně. Například k tomu, aby se vysílání jednoho uzlu šířilo k více uzlům (ať již jako tzv. broadcast, tedy ke všem dostupným uzlům, nebo jako tzv. multicast, jen k některým z dostupných uzlů).
Systematická topologie a sdílené médium mají i další výhody, ale také své nevýhody. Tou největší je zřejmě nutnost řídit přístup ke společně sdílenému přenosovému médiu, pro potřeby vysílání. Jak už jsme si řekli, současný příjem je možný a je dokonce jednou z hlavních předností společně sdíleného přenosového média. Ovšem současné vysílání dvěma či více uzly už žádoucí není a je třeba se ho vyvarovat. Ne snad proto, že by současným vysíláním mohlo dojít k nějakému fyzickému poškození přenosového média. To nikoli.
Někdy k současnému vysílání přece jen může dojít, pak se hovoří o tzv. kolizi. Při ní dochází k "promíchání" jednotlivých vysílání, která už pak zase nejdou zpětně "oddělit od sebe". Kolizím je tedy dobré se vyhýbat, předcházet jim nebo je úplně vyloučit. Tím, kdo by to měl zajistit (resp. "to, co by to mělo zajistit"), jsou tzv. přístupové metody, anglicky access methods, plným jménem: metody přístupu ke sdílenému médiu.

Klasifikace přístupových metod

Už z pouhé zmínky o kolizích lze vytušit, že přístupové metody mohou pracovat různým způsobem a vycházet z různých principů. Například podle toho, jak se chovají vůči kolizím, je lze dělit na přístupové metody:
zcela vylučující kolize (CA, collision avoidance),
detekující kolize (CD, collision detection),
bez detekce kolizí.
Například metody detekující kolize (CD) se obvykle snaží nějak předcházet jejich výskytu, ale nejdou až tak daleko, aby je vyloučily zcela. Takže kolize mohou přesto nastat a metody s přívlastkem CD je dokáží detekovat a následně i řešit (postarat se o nápravu). Jak záhy uvidíme, přístupová metoda, používaná v oblíbeném Ethernetu, je právě tohoto typu.
Jiné přístupové metody naopak fungují striktně v tom smyslu, že žádné kolize nepřipouští. Obvykle to souvisí i s další jejich vlastností, kterou je řízený (deterministický) charakter. Takové deterministické přístupové metody mají "vše pod kontrolou" a výsledek jejich působení je vždy možné předpovídat (na základě znalosti výchozího stavu). Alternativou k nim jsou neřízené, alias nedeterministické přístupové metody, které při svém rozhodování používají nějaký náhodný prvek. Pak ale jejich výsledek nelze přesně předpovídat (a ze stejné výchozí situace mohou vzniknout různé výsledky). Například již zmiňovaná přístupová metoda Ethernetu je nedeterministická.
Abychom se v tom ale vyznali: přístupové metody lze dělit podle různých kritérií. Jedním z nich je celkový přístup ke kolizím, podle něj se přístupové metody rozpadají na metody vylučující kolizi (CA, collision avoidance), detekující kolizi (CD, collision detection) a bez detekce kolizí. Dalším možným kritériem je již zmiňovaná existence náhodného prvku při rozhodování podle něj se přístupové metody dělí na:

deterministické (řízené),
nedeterministické (neřízené).

Ještě dalším kritériem pak je to, zda přístupová metoda předpokládá existenci nějakého centrálního prvku (centrální autority, arbitra), který by sám realizoval veškeré rozhodování podle pravidel příslušné přístupové metody a ostatním uzlům říkal, co a jak mají dělat. Podle toho se pak přístupové metody dají dělit na:

centralizované (s centrálním prvkem, resp. centrální autoritou),
distribuované (bez centrální autority).

Ani tím se však možnosti klasifikace přístupových metod nevyčerpaly. Ještě dalším možným dělením je to, zda se uzel, usilující o vysílání, nejprve snaží detekovat, zda po společně sdíleném přenosovém médiu právě probíhá nějaké vysílání. Říká se tomu "příposlech nosné", anglicky carrier sense (CS). Pokud je příposlech nosné používán a uzel zjistí, že právě vysílá někdo jiný, do přenosu sám nevstupuje, aby jej nenarušil. U metod bez detekce nosné se uzel na právě probíhající vysílání neohlíží. Pak ale hrozí nebezpečí, že někomu "skočí do řeči" (naruší právě probíhající vysílání kolizí).
Důležité také je, že všechna výše uvedená dělení jsou na sobě nezávislá. Takže třeba přístupová metoda, používaná v Ethernetu (viz dále) je nedeterministická, distribuovaná, s detekcí kolizí (CD) a s detekcí nosné. Jmenuje se konkrétně CSMA/CD, což zdůrazňuje i její hlavní vlastnosti.

Centralizované metody

Než se ale pustíme do zřejmě nejznámější přístupové metody CSMA/CD, používané v Ethernetu, zastavme se nejprve u toho, jak mohou vypadat centralizované přístupové metody. Musí mít nějaký centrální prvek, který nějakým způsobem "přiděluje slovo" jednotlivým uzlům sítě pro potřeby vysílání. Může to dělat i aniž by se snažil nějak zjistit, zda vysílat skutečně chtějí nebo nikoli toto právo jim pak jednoduše přiděluje nejspíše nějak cyklicky, aby se dostalo postupně na všechny uzly. Inteligentnější je ale varianta, kdy se centrální autorita zajímá o to, kdo a jak chce vysílat a právo vysílat přiděluje pouze tomu, kdo o něj má zájem.
O existenci zájmu se centrální autorita může dozvědět dvěma principiálně odlišnými způsoby:
na základě výzev (anglicky: polling), kdy se sama pravidelně dotazuje uzlů, zda nechtějí vysílat,
na základě žádostí, kdy uzly samy žádají centrální autoritu o právo vysílat.
V obou případech je ale "s agendou zjišťování zájmu" spojena nemalá režie, buď ve formě samostatných vedení (pro žádosti či výzvy), nebo alespoň ve formě části přenosové kapacity sdíleného přenosového média, pro daný účel vyhrazené. Výhodou centralizovaných přístupových metod je naopak velká pružnost v rozhodování centrální autority. Ta může používat prakticky libovolný algoritmus pro své rozhodování a dokonce jej může i průběžně měnit, například v závislosti na stavu sítě a průběhu komunikace.
Konkrétním příkladem z praxe může být kabelový internet, přesněji způsob přenosu dat v kabelových sítích na bázi standardu DOCSIS. Zde je vždy určitý počet modemů zapojen "do skupiny", v jejímž rámci sdílí jeden společný přenosový kanál pro oba směry komunikace. K celé skupině kabelových modemů je pak přiřazen jeden prvek CMTS (Cable Modem Termination System). Ten řídí veškerou komunikaci v rámci skupiny na dopředném kanále (směrem ke kabelovým modemům) vysílá vždy pouze on sám. V opačném směru může standardně vysílat vždy jen ten kabelový modem, kterému "udělí slovo" CMTS.
CMTS tedy plní roli centrální autority a zájem jednotlivých kabelových modemů o vysílání (na zpětném kanále) zjišťuje pomocí speciálního rezervačního rámce, který "nechává kolovat" (rozesílá po dopředném kanále a přijímá po zpětném kanále). V tomto rezervačním rámci může každý jednotlivý kabelový modem vyznačit svůj zájem o vysílání a následně mu CMTS ve vhodnou dobu udělí slovo. Představu zachycuje obrázek.
Poněkud odlišným způsobem je řešena centralizovaná přístupová metoda v sítích 100VG-AnyLAN. Ty svého času velmi propagovala firma Hewlett-Packard, společně s IBM, dokonce se původně snažila je prosadit jako 100megabitovou verzi Ethernetu. Nakonec se tak nestalo, právě kvůli tomu, že technologie 100VG-AnyLAN používá jinou přístupovou metodu než klasický Ethernet. Jde o metodu nazývanou Demand Priority, využívající stromovitý charakter kabeláže. Podstatné je zde to, že každý uzel má k dispozici (jen a jen pro sebe) svou samostatnou přípojku k nejbližšímu nadřazenému rozbočovači (tzv. hubu). Takže pokud právě sám nevysílá nebo něco nepřijímá, může tuto svou přípojku využít k tomu, aby požádal svůj nadřazený rozbočovač o právo vysílat. Všechny rozbočovače dohromady (ve vzájemné součinnosti) pak plní roli centrální autority a podle momentální situace udělují žadatelům (koncovým uzlům) právo vysílat.

Distribuované metody

Centralizované přístupové metody mají své výhody, ale i své nevýhody. Největší nevýhodou je asi to, že centrální autorita představuje příslovečné single point of failure, neboli jedno místo, jehož vyřazením (poruchou, závadou atd.) je vyřazena z provozu celá síť. Tuto nevýhodu naopak nemají distribuované metody, které nemají žádnou centrální autoritu a uplatňování pravidel přístupové metody "rozkládají" rovnoměrně mezi všechny uzly. Jinými slovy: když zde není žádná centrální autorita, musí se uzly domluvit mezi sebou distribuovaným způsobem. Činí tak na základě pravidel, které musí korektně dodržovat všechny uzly. Ve svém vzájemném souběhu pak tato pravidla naplňují příslušnou přístupovou metodu.
I distribuované (decentralizované) přístupové metody se přitom mohou dělit na řízené (deterministické) a neřízené (nedeterministické) s tím, že obě tyto dílčí varianty mají smysl. Naopak u centralizovaných přístupových metod měly smysl spíše jen deterministické přístupové metody (zatímco nedeterministické by nepřinášely oproti deterministickým žádnou výhodu). U distribuovaných metod však nedeterministické metody smysl mají. To proto, že jejich implementace může být výrazně jednodušší (lacinější) než implementace deterministických metod. Lze to ostatně demonstrovat na příkladu Ethernetu, který používá distribuovanou a nedeterministickou přístupovou metodu a jeho implementace je relativně velmi jednoduchá. Naproti tomu například síť Token Ring používá distribuovanou a deterministickou přístupovou metodu a její implementace je kvůli tomu složitější. S tím pak souvisí i komerční úspěšnost Ethernet je dnes mnohem rozšířenější než Token Ring.

Token Passing, aneb předávání peška

Popišme si nejprve jednu deterministickou a distribuovanou přístupovou metodu, která se v praxi používá poměrně často. Jmenuje se Token Passing a její hlavní princip naznačuje už její jméno: existuje zde "něco", čemu se v angličtině říká token a co má význam jakéhosi oprávnění, povolení apod. Někdy se tomu česky říká také "pešek", což zase naznačuje způsob manipulace s tímto tokenem: jednotlivé uzly si jej postupně předávají, podle určitého pořadí. Toto pořadí musí mít charakter logického kruhu, aby pešek obíhal pořád dokola. Když se zajistí, že obíhat bude vždy jen jeden pešek, pak s ním lze vyřešit i problém přístupu ke sdílenému médiu: právo vysílat bude mít ten, kdo má právě ve svém držení peška, až své vysílání skončí, předá peška dalšímu uzlu v pořadí (v logickém kruhu). Důležité je, že metoda Token Passing vyžaduje logický kruh, definující způsob předávání tokenu (peška) mezi jednotlivými uzly. To ale nemusí nutně znamenat, že fyzická topologie sítě, kde je tato metoda použita, musí být také kruhová. Ostatně na obrázku je znázorněna sběrnicová topologie jako u sítí Token Bus. Pravdou ale je, že v praxi se metoda Token Passing používá nejčastěji v sítích, které skutečně mají kruhovou topologii (například v sítích Token Ring a FDDI).
CSMA/CD přístupová metoda Ethernet
Pojďme nyní již k tomu, co je pro dnešní praxi asi nejzajímavější k přístupové metodě CSMA/CD, používané v Ethernetu. Jak jsme si již naznačili, patří mezi:
distribuované přístupové metody (nemá žádného centrálního arbitra,
resp. centrální autoritu, která by vše řídila),
neřízené (nedeterministické) přístupové metody (proto, že při rozhodování jednotlivých uzlů se v jisté situaci uplatňuje náhodný prvek),
přístupové metody využívající příposlech nosné (CS, carrier sense) jednotlivé uzly tedy před začátkem vlastního vysílání poslouchají, zda právě nevysílá někdo jiný,
přístupové metody s detekcí kolize (CD, collision detect) v Ethernetu může ke kolizím docházet, ale ty jsou následně detekovány a řešeny.
Praktické fungování přístupové metody CSMA/CD, používané v Ethernetu, si můžeme přiblížit následovně:
Uzel, který má zájem vysílat, nejprve použije příposlech nosné (CS). Pokud zjistí, že právě nikdo nevysílá, může začít vysílat sám.
Pokud však uzel zjistí přes příposlech nosné, že právě někdo vysílá, čeká, až toto vyslání skončí (tedy stále sleduje průběh vysílání přes příposlech nosné). Jakmile vysílání skončí, uzel začne vysílat sám. Důležité je, že přes uvedené dva body a zejména pak přes příposlech nosné (CS, carrier sense) se zájemci dokáží vyvarovat toho, aby někomu "skočili do řeči" (narušili nějaké již probíhající vysílání). Tím je výrazně snížena pravděpodobnost výskytu nežádoucích kolizí. Bohužel ale není zcela eliminována, a to je nutné náležitě zdůraznit. I přes toto chování jednotlivých uzlů může ke kolizím stále docházet. Možné příčiny jsou dvě, ukazuje je rovněž obrázek.
Méně častou příčinou je souběh dvou uzlů. Může se totiž stát, že se dva uzly ve stejnou dobu rozhodnou, že začnou vysílat. Oba zjistí, že žádné vysílání právě neprobíhá, a tak začnou vysílat samy.
Častějším důvodem pro vznik kolizí je jiná situace: dva nebo více uzlů se rozhodnou začít vysílat v době, kdy právě probíhá nějaké jiné vysílání. Všichni to zjistí, a tak spořádaně počkají na konec tohoto vysílání ale pak začnou vysílat všichni najednou. A dojde ke kolizi.

Řešení kolizí v Ethernetu

Co ale s kolizí dál? Jak se má zachovat uzel v situaci, kdy zjistí, že jeho vysílání se dostalo do kolize s vysíláním jiného uzlu?
Pravidla fungování Ethernetu říkají, že v takové situaci hlavně nesmí zpanikařit a okamžitě přestat vysílat. Pak by se totiž mohlo stát, vzhledem ke konečné rychlosti šíření signálu po sdíleném médiu a jeho nenulové délce, že by tuto kolizi jiné uzly nemusely korektně zaregistrovat. Proto musí uzel kolizi ještě naopak "utvrdit" a po předepsanou dobu naopak ještě vysílat. Teprve pak může uzel začít kolizi řešit. Optimálně tak, aby se ze všech uzlů, které se kolize zúčastnily, vybral jeden a ten získal právo vysílat. Jenže k tomu by se uzly musely mezi sebou umět domluvit kolik jich je, které to jsou atd., a pak mezi sebou jednoho vybrat.
To ale není možné. Uzly, které se setkaly v kolizi, o sobě neví. Ani netuší, kolik jich je zda dva (což je minimum pro kolizi jako takovou), nebo více. Nemají k dispozici žádný mechanismus, jehož prostřednictvím by se vzájemně domluvili. Proto to řeší tak, že se spolehnou na náhodu. Vygenerují náhodné číslo z určitého intervalu a na dobu danou tímto číslem se odmlčí (teprve pak zkouší vše znovu). Spoléhají se přitom na to, že jim pomůže právě náhoda že se různé uzly odmlčí na náhodnou dobu, poté se při dalším pokusu o vysílání již do kolize nedostanou a odvysílají svá data. Představu ilustruje další obrázek. Pravdou je, že takto využitý prvek náhody obvykle pomůže a uzly už se znovu do kolize nedostanou. Jenže problém je v tom, že to není zaručeno. Může se stát, že se uzly odmlčí na stejnou dobu (oba si náhodně zvolí stejnou dobu). Nebo, což je pravděpodobnější, se oba odmlčí na různě dlouhou dobu, ale pak stejně musí čekat, až skončí nějaké právě probíhající vysílání, a tak se znovu dostanou do kolize. Pokud ovšem náhoda v prvním kole nepomohla, není nutné ji hned zatracovat. Výhodnější je náhodě pomoci, aby měla větší šanci se projevit. Přístupová metoda CSMA/CD, používaná v Ethernetu, to řeší následovně: interval, ze kterého se vybírá náhodná doba odmlčení, se při každém neúspěšném pokusu zdvojnásobuje. Dělá se to celkem 16x, teprve pokud se to ani na šestnáctý pokus nepodaří, přístupová metoda to vzdá a ohlásí neúspěch.

Propustnost řízených a neřízených metod

Pravdou je, že zvětšování intervalu, ze kterého se náhodně volí doba pro odmlčení, snižuje pravděpodobnost výskytu následných kolizí. Na druhou stranu ale ani tento postup negarantuje, že k následným kolizím vůbec nedojde. V praxi je to sice velmi málo pravděpodobné, ale přesto se něco takového může stát: může dojít k tomu, že díky nedeterminismu (náhodnému prvku) v přístupové metodě CSMA/CD se konkrétní uzel nedostane vůbec "ke slovu" (nezíská přístup ke sdílenému médiu za účelem vysílání). Stejně tak ani není možné garantovat, že se ke slovu dostane nejpozději za nějakou konkrétní dobu T. Opět to lze slíbit jen s nějakou pravděpodobností, relativně vysokou, ale nelze to garantovat. Naproti tomu u řízených (deterministických) přístupových metod obecně lze zaručit, že se nějaký uzel dostane "ke slovu". Obvykle se i ví, za jak dlouho. Například u sítí s metodou Token Passing záleží jen na tom, kolik uzlů je v logickém kruhu a jak dlouho si každý uzel smí peška ponechat.
Pro praxi to má jeden velmi významný důsledek: Ethernet, který nedokáže nic garantovat, se nedá použít tam, kde je nutná garantovaná odezva sítě v reálném čase. Tedy například ve výrobě, při řízení výrobních procesů apod. Zde jsou nutné lokální sítě s řízenými přístupovými metodami. Naproti tomu v běžném kancelářském prostředí minimální (ale ne zcela nulová) pravděpodobnost, že se něco nepřenese včas, vůbec nevadí. Zde naopak Ethernet se svým nedeterminismem drtivě vítězí, protože je jednodušší a lacinější. A také je vlastně rychlejší, protože se nemusí zabývat mnoha složitostmi, na které naopak musí pamatovat sítě s řízenými přístupovými metodami.
Obecně přitom platí, že vytížení (celková propustnost) sdíleného přenosového média závisí nejen na použité přístupové metodě, ale také na intenzitě provozu. Není asi těžké nahlédnout, že při větší zátěži (při větší četnosti požadavků od jednotlivých uzlů na vysílání) bude pravděpodobnost výskytu kolizí růst, a to i kolizí následných. V praxi to dokonce vypadá tak, že od určitého okamžiku se s růstem zátěže propustnost dokonce zmenšuje, právě kvůli kolizím a kvůli tomu, že režie spojená s jejich výskytem a řešením začíná převažovat. Ukazuje to ostatně i obrázek, na kterém je názorně vidět, jak se při rostoucí zátěži (na ose X) chová neřízená přístupová metoda (například metoda CSMA/CD Ethernetu) a jak se (obecně) chová řízená přístupová metoda. Pro ní celková propustnost, měřená ve využití sdíleného média pro "užitečné" přenosy, neklesá, ale asymptoticky se blíží k ideálním 100 %. Je ovšem nutné doplnit jednu velmi důležitou poznámku: při použití neřízených (nedeterministických) metod se předpokládá jejich využití v méně zatížených sítích. Tedy tam, kde je intenzita požadavků jednotlivých uzlů na vysílání relativně nízká. Na obrázku odpovídá tmavší šrafované části. "Křivka vytíženosti" se tedy ani nedostane k tomu, aby se začala lámat.

Podvrstva MAC

Na samotný závěr si ještě řekněme jednu důležitou věc: kde vlastně jsou všechny přístupové metody implementovány? Na které vrstvě v rámci sedmivrstvého modelu ISO/OSI?
Pokud by to mělo být na linkové vrstvě, pak by už bylo pozdě. Linková vrstva, která zajišťuje přenos celých (linkových) rámců, už musí mít přístup ke sdílenému médiu vyřešen. Takže přístupové metody musí být implementovány pod linkovou vrstvou. Analogická úvaha, byť s opačným znaménkem, platí i pro vrstvu fyzickou: jelikož přístupové metody potřebují ke svému fungování vysílat do sdíleného média jednotlivé bity, musí být implementovány nad fyzickou vrstvou.
Jenže mezi fyzickou a linkovou vrstvou referenčního modelu ISO/OSI už žádná další vrstva není. Autoři RM ISO/OSI přitom ani nepočítali s tím, že by nějaké přístupové metody museli implementovat, protože předpokládali spíše existenci rozlehlých sítí, bez sdílených přenosových médií. Když se pak objevily i sítě lokální a s nimi potřeba přístupových metod, už se jim nechtělo zvyšovat beztak vysoký počet vrstev a vložit mezi fyzickou a linkovou vrstvu ještě jednu další vrstvu. A tak to vyřešili zajímavým "kompromisem" původní linkovou vrstvu rozdělili na dvě podvrstvy:
vyšší podvrstvu LLC (Logical Link Control), která zajišťuje úkoly celé původní linkové vrstvy,
nižší podvrstvu MAC (Media Access Control), na které jsou implementovány dnes popisované přístupové metody.
Představu obou podvrstev ukazuje další obrázek.