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 16×, 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.