Báječný svět počítačových sítí. Část X. Řízení přístupu klasifikace, řešení kolizí a propustnost

Internet | 01.01.06

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ájem...





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.












Komentáře

K tomuto článku není připojena žádná diskuze, nebo byla zakázána.