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

Část X: Řízení přístupu

Lokální počítačové sítě (sítě LAN), na rozdíl od většiny rozlehlých sítí (sítí WAN), mají 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ě sítí lokálních (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, nebo do sběrnice atd. - s využitím takového přenosového média, které má sdílený charakter. Tedy takového 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, tj. ke všem dostupným uzlům, nebo jako tzv. multicast, tj. jen k některým z dostupných uzlů).

Obr. 1: Představa topologií sítí WAN a LAN

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 mu 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řeci jen může dojít, a 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". Takže kolizím je dobré se vyhýbat, předcházet jim, nebo je úplně vyloučit. No a ten, 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í

Takže 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éto deterministické přístupové metody mají "vše pod kontrolou", a výsledek jejich působení je vždy možné predikovat (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ředikovat (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 správně vyznali: přístupové metody lze dělit podle různých kritérií. Jedním z nich je celkový přístup ke kolizím, a 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 s 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 s 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 bez toho, aby 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, vyhrazené pro daný účel.

Obr. 2: Představa žádostí a výzev

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 rámci které 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 pak ří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.

Představa topologie datové části kabelové sítě

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 ukazuje následující obrázek (č. 3.):

Obr. 3: Představa principu rezervací , u centralizované přístupové metody používané v kabelových sítích.

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, a dokonce se původně snažila je prosadit jako 100-megabitovou 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", a využívající stromovitý charakter kabeláže (viz obrázek č. 4). Podstatné je zde to, že každý uzel má k dispozici (a jen a jen pro sebe) svou samostatnou přípojku k nejbližšímu nadřazenému rozbočovači (tzv. hub-u). 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. No a všechny rozbočovače dohromady (a 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.

Obr. 4: Představa fungování metody Demand Priority, v sítích 100VG-AnyLAN

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 žádnou výhodu oproti deterministickým). 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 jeho 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á je v praxi používána poměrně často. Jmenuje se "Token Passing", a její hlavní princip naznačuje už toto 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, tak aby pešek obíhal pořád dokola. No a 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)

Obr. 5: Představa fungování metody Token Passing

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 i fyzická topologie sítě, kde je tato metoda použita, musí být také kruhová. Ostatně, na předchozím obrázku (č. 5) je znázorněna sběrnicová topologie, jako u sítí Token Bus. Pravdou ale že, ž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 Ethernetu

Pojďme nyní již 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 (tj. nemá žádného centrálního arbitra, resp. centrální autoritu, který by vše řídil)
• neřízené (nedeterministické) přístupové metody. To 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). Takže v Ethernetu může ke kolizím docházet, ale tyto jsou následně detekovány, a jsou řešeny

Praktické fungování přístupové metody CSMA/CD, používané v Ethernetu, si můžeme přiblížit následovně (viz též obrázek č. 6):

• 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í, skrze příposlech nosné, že právě někdo vysílá, čeká až toto vyslání skončí (tj. stále sleduje průběh vysílání, skrze příposlech nosné). Jakmile vysílání skončí, uzel začne vysílat sám.

Obr. 6: Představa využití detekce nosné (/CS) v Ethernetu

Důležité je, že skrze uvedené dva body, a zejména pak skrze 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é si 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ě, a ukazuje je následující obrázek (č. 7).

Obr. 7: Možné důvody pro vznik kolizí v Ethernetu

Méně častou příčinou je souběh dvou uzlů, které ve stejném čase (viz horní část obrázku č. 7). Může se totiž stát, že dva uzly se 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 sami.

Častějším důvodem pro vznik kolizí je situace, kterou znázorňuje spodní část obrázku č. 7: dva nebo více uzlů se rozhodne 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. Ani nemají k dispozici žádný mechanismus, prostřednictvím kterého by se vzájemně domluvili. Proto to řeší tak, že se spolehnou na náhodu. Vygenerují si náhodné číslo z určitého intervalu, a na dobu danou tímto číslem se odmlčí (a 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, a poté se při dalším pokusu o vysílání již do kolize nedostanou a odvysílají si svá data. Představu ukazuje následující obrázek (č. 8).

Obr. 8: Představa odmlčení dvou uzlů, zúčastněných na kolizi

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 i to, že uzly se odmlčí na stejnou dobu (oba si náhodně zvolí stejnou dobu). Nebo, a to je asi 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, viz obrázek č. 9:

Obr. 9: Představa následné kolize

Pokud ovšem náhoda v prvním kole nepomohla, není nutné ji hned zatracovat. Výhodnější je náhodě pomoci, tak aby měla větší šanci zaúčinkovat. Přístupová metoda CSMA/CD, používaná v Ethernet, to řeší následovně: interval, ze kterého se vybírá náhodná doba pro odmlčení, se při každém neúspěšném pokusu zdvojnásobuje. Dělá se to tak celkem 16x, a teprve pokud se to ani na šestnáctý pokus nepodaří, přístupová metoda to vzdá a ohlásí neúspěch.

Obr. 10: Prodlužování intervalu při následných kolizí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 to 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 nejde ani 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 garantovat, že se nějaký uzel dostane "ke slovu", a obvykle i za jak dlouho. Například u sítí s metodou Token Passing záleží jen na tom, kolik je uzlů v logickém kruhu, a jak dlouho si každý uzel smí nechat peška ve svém držení.

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 tím i lacinější. A také 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 následující obrázek (č. 11), 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%.

Obr. 11: Chování řízené a neřízené přístupové metody, vzhledem k zátěži (intenzitě požadavků)

K obrázku č. 11 je ovšem nutné přidat 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 intenzita požadavků jednotlivých uzlů na vysílání je relativně nízká. Na obrázku odpovídá tmavěji vyšrafované části. Takže "křivka vytíženosti" se 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 jaké vrstvě, v rámci sedmivrstvého modelu ISO/OSI?

Pokud by to mělo být na linkové vrstvě, pak by to 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", ale 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 i 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 také následující obrázek, č. 12:

Obr. 12: Rozdělení linkové vrstvy RM ISO/OSI na dvě podvrstvy

---