CSMA/CD

Představte si skupinku lidí (tedy nejméně dva jedince) zavřených v malé místnosti se špatnou akustikou. Tak špatnou, že když jeden mluví, slyší to všichni, ale jakmile by začalo mluvit více lidí najednou, nikdo by už ničemu nerozuměl.

Obdobná situace nastává i u lokálních počítačových sítí se sběrnicovou topologií (tedy například u sítí typu Ethernet). Zde jsou všechny uzly napojeny na jediný vícebodový spoj, a když jeden uzel něco vysílá, mohou jeho vysílání přijímat všechny uzly současně. Kdyby ovšem začalo najednou vysílat více uzlů, všichni by přijímali jen jakousi dále nerozlišitelnou směs.

V obou případech je tedy nutné zavést a dodržovat taková pravidla či postupy, které zajistí korektní způsob komunikace - tedy takový, při kterém nebude mluvit více lidí současně, resp. současně vysílat více uzlů. V případě počítačové sítě se těmto pravidlům říká přístupová metoda (access method), jak jsme si již naznačili v minulém příspěvku této rubriky.

Jaké jsou principiální možnosti zajištění korektního způsobu komunikace ve výše naznačeném smyslu? Ukažme si to nejprve na příkladu skupinky lidí: mezi nimi může existovat jedna autoritativní osoba, kterou všichni ostatní respektují a která rozhoduje o tom, kdo bude mluvit. Může to dělat tak, že se potenciálních zájemců postupně dotazuje (zda mají připraveno nějaké sdělení, které by chtěli přednést), nebo naopak čeká na explicitní žádosti těch, kteří chtějí promluvit. V případě počítačové sítě odpovídá tato situace existenci uzlu, který vystupuje v roli arbitra a sám rozhoduje o tom, kdo smí vysílat. Pokud se tento centrální arbitr sám dotazuje ostatních uzlů, jde o tzv. centrální přidělování na základě výzvy. Alternativou je přidělování na žádost, kdy arbitr čeká, až se mu žadatelé o právo vysílat přihlásí sami.

Existence centrálního arbitra je ovšem vždy spojena s nebezpečím jeho výpadku, který zanechává všechny ostatní v nezáviděníhodné situaci - sami se nedokáží domluvit.

Jiná řešení existenci centrálního arbitra nepředpokládají a místo toho sází na distribuovaný charakter rozhodovacího mechanismu, tedy na schopnosti všech zájemců dohodnout se i bez existence rozhodčího. Konkrétní řešení může být například takové (použijeme-li naše přirovnání ke skupince lidí), že mezi účastníky koluje "průkazka mluvčího" a pouze její držitel je oprávněn mluvit, zatímco ostatní mohou pouze poslouchat. Pokud si každý držitel ponechá průkazku jen konečně dlouhou dobu a je-li zajištěn spravedlivý "koloběh" předávání průkazek, který nikoho nevynechá, je dokonce zaručeno, že se každý dostane ke slovu. Dokonce to lze zařídit i tak, že nikdo nebude muset čekat déle než určitou předem stanovenou dobu (k tomu stačí vhodně omezit maximální dobu, po kterou si každý smí průkazku ponechat).

Vrátíme-li se k počítačovým sítím, odpovídá tato strategie distribuované přístupové metodě, která spadá do kategorie tzv. řízených metod. Řízených proto, že neobsahují žádný prvek náhodnosti a jejich aplikace vždy vede k předem odhadnutelnému výsledku. Příkladem může být přístupová metoda, která se používá v sítích Token Ring a Token Bus, kde "průkazkou mluvčího" je tzv. token (do češtiny překládaný obrazně jako pešek, s menší mírou představivosti jen jako oprávnění). Token je ve skutečnosti zvláštním druhem rámce (paketu), který nenese žádná data, ale opravňuje svého příjemce k následnému vysílání.

Alternativou k řízeným metodám jsou metody neřízené, které v nějaké formě uplatňují náhodný prvek, a v důsledku toho nemusí být jejich výsledek predikovatelný. Neřízená přístupová metoda obvykle nezaručuje, že se zájemce o vysílání skutečně dostane ke slovu v konečném čase - místo toho zajišťuje každému žadateli přístup v konečném čase jen s určitou pravděpodobností, která sice bývá dosti vysoká, ale není stoprocentní.

Proč se ale takovéto neřízené metody vůbec používají, když místo jistoty nabízí jen určitou pravděpodobnost? Jejich výhodou oproti řízeným metodám je větší jednoduchost, snazší implementovatelnost, ale především menší režie v situaci, kdy síť je málo zatížena (tj. když požadavků na vysílání je relativně málo). Naopak při velkém zatížení sítě jsou neřízené přístupové metody méně efektivní než metody řízené a obvykle neumožňují využít teoretickou přenosovou kapacitu sítě na plných 100 procent (ale např. jen na 60 až 80 procent).

Nejznámějším příkladem neřízené metody je přístupová metoda sítí typu Ethernet (viz minulé vydání této rubriky). Označuje se zkratkou CSMA/CD, která v sobě skrývá tři základní principy, na kterých je založena.

První dvě písmena, CS, jsou od anglického Carrier Sense (česky: příposlech, detekce nosné). Znamenají to, že když některý uzel chce vysílat, nejprve poslouchá, zda nevysílá někdo jiný - snaží se detektovat signál (tzv. nosnou) pocházející od vysílání jiného uzlu.

Pokud uzel zjistí, že nikdo právě nevysílá, může začít vysílat sám. Sběrnicová topologie, v jejímž rámci jsou všechny uzly přímo připojeny na jediný vícebodový spoj, to umožňuje každému a přímo. Je tedy možný tzv. vícenásobný přístup (Multiple Access, odsud druhá dvě písmena, MA), který znamená nejen současné fyzické připojení více uzlů na jedno společné přenosové médium, ale i možnost současného příjmu více uzly, a dokonce i možnost současného vysílání více uzly. Této poslední možnosti je třeba správně rozumět: je samozřejmě nežádoucí, ale díky technickému řešení sítí typu Ethernet nezpůsobí současné vysílání více uzlů žádnou technickou závadu či poškození přenosového média nebo výstupních obvodů (tzv. budičů) jednotlivých uzlů. Projeví se však změnou parametrů elektrických signálů na přenosovém médiu, a tuto změnu je možné jednoznačně detektovat.

Díky příposlechu (detekci nosné) nedochází k tomu, že by jeden uzel zahájil vysílání v době, když již nějakou dobu probíhá vysílání jiného uzlu (i když technicky by mohl, díky vícenásobnému přístupu). Může však dojít k tomu, že v této době projeví zájem o vysílání více uzlů. Všechny sice spořádaně počkají, až právě probíhající vysílání skončí, ale pak se doslova "utrhnou ze řetězu" a začnou vysílat všechny najednou. Pak dochází k tzv. kolizi (collision), která je ale jednoznačně rozpoznatelná (viz výše). Každý uzel, který začal vysílat, může kolizi rozpoznat a z ní si pak odvodit, že nezačal vysílat sám. Dokonce je povinen to dělat, jak mu přikazují poslední dvě písmena v názvu přístupové metody CSMA/CD - CD neboli Collision Detect (detekce kolizí).

Zajímavá je pak otázka, jak se mají zachovat zúčastněné uzly poté, co ke kolizi došlo.

Pravidlo je takové, že každý uzel, který detektuje kolizi, se na určitou dobu odmlčí, a teprve pak může znovu usilovat o své vysílání (tedy nejprve poslouchat, zda někdo již nevysílá atd.). Kdyby se ovšem všechny uzly, zúčastněné na kolizi odmlčely na stejně dlouhou dobu, došlo by po uplynutí této doby ke kolizi nové. Nejlepší by bylo, kdyby se zúčastněné uzly vhodně domluvily a každý si zvolil jinou dobu, na kterou by se odmlčel. To však není možné zařídit - jednotlivé uzly totiž nemají žádnou možnost zjistit, kolik se jich v kolizi sešlo, ani které uzly to jsou (mohou si odvodit pouze to, že jsou nejméně dva). Nemohou se tedy žádným způsobem vzájemně zkoordinovat. Proto se právě v této situaci uplatňuje náhodný prvek a každý uzel si délku svého odmlčení volí sám a nezávisle na ostatních jako náhodné číslo z určitého intervalu. Díky tomu se v obecném případě každý uzel odmlčí na různě dlouhou dobu a ten, který se "probere" jako první, většinou již na kolizi nenarazí. Není to ale zaručené a novou k olizi nelze vyloučit.

Každý uzel, který se opakovaně dostane do kolize, si zdvojnásobí interval, ze kterého si náhodně volí délku svého odmlčení. Různými simulacemi se totiž ukázalo, že právě při takovémto postupu bude následných kolizí nejméně. Opět ale není zaručeno, že se konkrétní uzel nebude neustále dostávat do kolizí s jinými uzly, a tak se tento uzel vlastně nikdy nedostane k vysílání (pravidla přístupové metody CSMA/CD říkají, že po 16 neúspěšných pokusech to má "vzdát"). I když pravděpodobnost tohoto případu je velmi malá, není nulová, a přístupová metoda CSMA/CD právě z tohoto důvodu není schopna zaručit přístup ke sběrnici (právo vysílat) v konečném čase.

Přístupovou metodu CSMA/CD lze tedy přirovnat k soutěži (v angličtině se v této souvislosti používá termín: contention), ve které neexistuje centrální rozhodčí, a v níž jednotliví účastníci přísně dodržují předem stanovená pravidla. Tato pravidla jsou ve své podstatě implementací distribuovaného algoritmu, a korektnost celé soutěže je pak zajištěna korektností tohoto algoritmu a disciplínou jednotlivých účastníků, kteří pravidla skutečně dodržují.

Vzhledem k existenci náhodného prvku (náhodně volené doby, na kterou se uzel po kolizi odmlčí) je příslušný distribuovaný algoritmus nedeterministický. Z něj vycházející soutěž je pak korektní v tom smyslu, že nemůže mít více než jednoho vítěze, ale na druhé straně nemusí mít také vítěze žádného. Díky tomu pak také není zaručeno, že se každý zájemce o vysílání dostane ke slovu v konečném čase. Pravděpodobnost této situace je velmi malá, ale nelze ji v principu vyloučit. Zda to je, či není na závadu, záleží hlavně na konkrétním způsobu využití lokální sítě. Kdyby například měla síť s přístupovou metodou CSMA/CD sloužit k řízení jaderné elektrárny, měl by tento její nedostatek zřejmě naprosto zásadní význam. Když je ale používána v běžném kancelářském prostředí, je tato její vlastnost zcela nepodstatná.