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

Část IX: Zajištění spolehlivosti

Některé aplikace vyžadují, aby přenosy dat fungovaly spolehlivě a nedocházelo při nich k žádným chybám ani ztrátám. Jiným aplikacím naopak nějaké to poškození dat až tak nevadí, a dávají přednost rychlosti, pravidelnosti a malému zpoždění. Když už je ale spolehlivý přenos požadován, jakým způsobem ho zle zajistit? Co jsou detekční a samoopravné kódy? Jak funguje potvrzování a jaké má varianty?

Na první pohled by se mohlo zdát, že když se někde přenáší nějaká data, mělo by jít o přenos spolehlivý. Tedy takový, který data ani neztratí, ani nedopustí, aby se při přenosu poškodila (změnila). Ostatně, k čemu by pak byl nějaký "nespolehlivý" přenos?

Na druhý pohled už to ale tak jasné není. V praxi totiž mohou existovat, a také reálně existují, takové situace a účely, kterým lépe vyhovuje nespolehlivý přenos. Samozřejmě nikoli takový, který nějak samovolně (sám od sebe) zahazuje či poškozuje přenášená data. "Nespolehlivostí" se myslí to, že když už k nějakému problému dojde (něco se ztratí či poškodí), přenosový mechanismus nepovažuje za svou povinnost postarat se o nápravu. Takže s tím, co se ztratilo, si neláme hlavu, a nad tím, noc se poškodilo, mávne rukou (zahodí to) - a hlavně se nezdržuje a pokračuje dál, jako kdyby se nic nestalo.

Spolehlivost může vadit

Naopak, pokud by se jednalo o spolehlivý přenos, měl by ten, kdo ho zajišťuje, v takové situaci plné ruce práce s nápravou toho, co se stalo. Musel by nejprve zjistit, že vůbec došlo k něčemu nežádoucímu - a pak by si musel vyžádat nový (opakovaný) přenos těch dat, která se ztratila či přišla poškozená. To by ale způsobilo poměrně velké zdržení, které by současně nabouralo průběžné doručování přenášených dat. A právě to může někomu (resp. něčemu) docela vadit.

Představme si třeba, že jde o přenos nějakého živého obrazu, a tento je přenášen po vzoru filmového pásu - každé políčko jako jeden samostatný blok (paket či rámec). Příjemce potřebuje dostávat takovéto bloky pravidelně, aby je mohl stejně pravidelně zobrazovat (posouvat filmový pás konstantní rychlostí). Pokud by ale došlo na opakování přenosu nějakého bloku (políčka na filmovém pásu), pravidelnost by se okamžitě narušila, a lidské oko by to ihned poznalo. Kolísání rychlosti posuvu filmového pásu lidské oko zaregistruje poměrně spolehlivě. Naproti tomu výpadek či poškození (zkreslení) jednoho políčka na filmovém pásu nemusí lidské oko ani postřehnout. Pak je ale rozumnější oželet nějaký ten výpadek (ztracené políčko) či zkreslení (poškození políčka), před narušením pravidelnosti přísunu dat. Navíc takový dočasný výpadek či zkreslení lze relativně snadno "zaretušovat" (interpolací z předchozích a následujících snímků), díky inteligenci a výpočetní kapacitě na straně příjemce.

Někdy je lepší to, jindy ono

Celkově tedy lze konstatovat, že existují případy a situace, kdy je výhodnější nespolehlivý přenos, který dává přednost pravidelnosti doručování dat, před spolehlivým přenosem. Například v již popisovaném případě multimediálních přenosů (živého zvuku a obrazu).

Existují ale i jiné důvody pro preferenci nespolehlivého přenosu před přenosem spolehlivým. Podstata tohoto důvodu je v tom, že ani spolehlivý přenos není nikdy zcela a stoprocentně spolehlivý. I jemu totiž může "proklouznout" nějaká ta chybička v přenášených datech, i když pravděpodobnost je zde opravdu velmi malá.

Nicméně mohou existovat i takové aplikace, kterým takováto "nedostatečná spolehlivost" vadí. Třeba takové bankovní aplikace, převádějící peníze z účtu na účet, si musí dávat opravdu velký pozor na každou nulu, desetinnou tečku či čárku atd. Takovéto aplikace si pak obvykle zajišťují spolehlivost samy, na takové úrovni jakou samy potřebují.

Problém je pak ale v tom, že není rozumné zajišťovat spolehlivost dvakrát, či dokonce vícekrát (na různých úrovních, resp. vrstvách, "nad sebou"). Ne, že by to nešlo. Jde to, ale je to nevýhodné. Zajištění spolehlivosti sebou totiž přináší nenulovou režii, a to jak co do spotřeby výpočetní kapacity (je nutné zjišťovat, jestli k chybě došlo), tak především co spotřeby přenosové kapacity a přenosového zpoždění (na opakování přenosu poškozených dat). No a pokud se spolehlivost zajišťuje na více vrstvách, režie s tím spojená se v lepším případě pouze sčítá, v horším násobí či kombinuje ještě nevýhodněji.

Takže z hlediska režie je jednoznačně výhodnější, aby se spolehlivost zajišťovala jen jednou, a to tam kde je skutečně zapotřebí - a "pod tím" (tj. na nižších úrovních), se spolehlivost nezajišťovala a přenosy fungovaly nespolehlivě.

Asi nejlépe to je vyřešené v rámci rodiny protokolů TCP/IP, kde základní přenosový protokol síťové vrstvy (protokol IP) funguje nespolehlivě. Nad ním, na úrovni transportní vrstvy, pak existují dva transportní protokoly:

• spolehlivý protokol TCP, Transmission Control Protocol (tj. zajišťující spolehlivost)
• nespolehlivý protokol UDP, User Datagram Protocol (tj. nezajišťující spolehlivost)

Jednotlivé aplikace si pak mohou svobodně vybrat, který z obou transportních protokolů využijí. Pokud si spolehlivost chtějí zajistit samy, nebo o ni naopak nestojí, vybírají si protokol UDP. Pokud o spolehlivost přenosů stojí a nechtějí si ji zajišťovat samy, volí protokol TCP. Představu ukazuje následující obrázek (č. 1).

Obr. 1: Aplikace v TCP/IP si samy volí mezi dvěma vzájemně alternativními transportními protokoly, TCP a UDP

Když už tušíme, jak je to se spolehlivostí přenosu dat - že je žádoucí jen někdy, a nikoli vždy - pojďme si nyní říci, jak se jí vlastně dosahuje. Nebo spíše: jak se spolehlivost přenosu zvyšuje (když už víme, že není nikdy absolutní). I tento úkol si ale musíme rozdělit na dvě samostatné části, abychom se v tom snáze vyznali:

• na detekci chyb, a na
• na nápravu detekovaných chyb

Detekcí chyb se rozumí již samotné zjištění toho, že se "něco stalo" - že došlo k nějaké nestandardní situaci, konkrétně k nějaké chybě v přenášených datech. Správně by sem měla patřit také úplná ztráta přenášeného bloku dat (paketu, rámce), ale k tomu se dostaneme záhy. Nyní se soustředíme na to, jak příjemce dokáže rozpoznat, že v přijatých datech je nějaká chyba.

Zabezpečovací údaj

Aby příjemce mohl rozpoznat, zda přijatá data jsou či nejsou v pořádku, musí k nim odesilatel "přibalit" určitý dodatečný údaj, kterému se obecně říká "zabezpečovací údaj". Odesilatel tento zabezpečovací údaj určitým způsobem vypočítá z dat, která mají být odeslána. Pak je přidá k těmto (užitečným) datům, a přenese k příjemci výsledný celek, viz obrázek (č. 2).

Obr. 2.: Představa přenášeného bloku dat, obsahujícího zabezpečovací údaj

Příjemce postupuje obdobně: vezme přijatá (užitečná) data, sám z nich vypočítá zabezpečovací údaj (přesně stejným postupem, jako to dělal odesilatel), a výsledek porovná se zabezpečovacím údajem, který mu přišel od odesilatele spolu s daty. Pokud se oba zabezpečovací údaje liší, může z toho příjemce usuzovat, že se něco po cestě poškodilo, a vyžádat si opakované zaslání týchž dat. Samozřejmě se mohlo stát i to, že se užitečná data přenesla v pořádku, a poškozen byl pouze přenášený zabezpečovací údaj - ale toto příjemce nedokáže rozlišit.

V opačném případě, tj. pokud se oba zabezpečovací údaje shodují, příjemce předpokládá že přenos proběhl bez chyb a pokračuje dál. Opět ale nemá stoprocentní jistotu, že tomu tak skutečně je. Představu ukazuje následující obrázek (č. 3).

Obr. 3.: Představa použití zabezpečovacího údaje při přenosu dat

Mechanismy detekce chyb

Důvod, proč příjemce nemůže mít stoprocentní jistotu o bezchybnosti přenosu, a to ani v případě shody obou zabezpečovacích údajů, je prostý - stoprocentní nejsou již samotné mechanismy detekce, podle kterých je konstruován zabezpečovací údaj, a podle kterých se chyby detekují. I těmto mechanismům může občas nějaká ta chybička utéci (zůstat bez povšimnutí).

Jaké mechanismy se ale používají pro detekci chyb, a jak vlastně fungují?

Mezi nejjednodušší, ale bohužel také nejméně účinné, patří tzv. parita. Její princip je jednoduchý: bity, které mají být přeneseny, se doplní o další bit (tzv. paritní bit), který se nastaví tak, aby celkový počet bitů byl buď sudý (pak jde o tzv. sudou paritu), nebo naopak lichý (tzv. lichá parita). Představu (sudé parity) ukazuje následující obrázek (č. 4)..

Obr. 4: Představa sudé parity

Jistě není těžké nahlédnout, že parita dokáže odhalit (detekovat) chybu v lichém počtu bitů. Ovšem chyby v sudém počtu bitů se z pohledu parity vzájemně ruší, a nejsou tedy detekovány. V praxi bývají paritou (paritním bitem) opatřovány relativně malé skupiny bitů, kde pravděpodobnost výskytu chyby je relativně malá. Tedy například jednotlivé byty či slova (dvojice bytů, čtveřice atd.). Příkladem může být asynchronní (správně arytmický) přenos, o kterém jsme si říkali v minulém dílu tohoto seriálu.

V případě přenosu větších datových bloků (rámců, event. paketů) je dnes použití parity spíše vzácností, a to kvůli její relativně malé účinnosti. Ale když už je i zde parita použita, může být použita dvěma různými způsoby (event. současně):

• jako tzv. příčná parita, kdy je každý byte (či slovo) v přenášeném bloku opatřen vlastním paritním bitem
• jako tzv. podélná parita, kdy jsou jedním paritním bitem zabezpečeny "stejnolehlé" bity ve všech bytech, resp. slovech přenášeného bloku.

Vše názorně ukazuje následující obrázek (č. 5)..

Obr. 5: Podélná a příčná parita

Na příkladu parity si také můžeme zdůraznit jeden významný aspekt, který souvisí se zajištěním spolehlivosti přenosu. Obě varianty parity totiž umožňují detekovat, ve které části přenášeného bloku k chybě došlo. V případě příčné parity se příjemce dozví, ve kterém bytu (event. slově) přenášeného bloku k chybě došlo, zatímco v případě podélné parity se dozví, ve které skupině "stejnolehlých" bitů se tak stalo. Je ale takováto informace příjemci vůbec k užitku?

Podstatné je, jak bude příjemce reagovat na výskyt nějaké (jakékoli) chyby v přijatém bloku. V případě nespolehlivého přenosu zahodí celý blok a už se o něj dále nestará. V případě spolehlivého přenosu si nechá znovu poslat celý blok. Takže k čemu mu je informace o tom, ve které části přenášeného bloku k chybě došlo? Není mu k ničemu, protože ji nedokáže využít. Stačí mu podstatně méně detailní informace, o tom že někde (kdekoli) v rámci bloku došlo k nějaké chybě (či chybám).

S touto skutečností počítají i další mechanismy, které se již nesnaží "lokalizovat" chybu, a soustřeďují se na lepší (přesnější) detekci jejího výskytu, kdekoli v bloku přenášených dat.

Jedním takovým mechanismem je kontrolní součet. Funguje tak, že přenášený blok se chápe jako lineární posloupnost bytů (resp. slov, tj. dvojic či čtveřic bytů), každý prvek této posloupnosti se interpretuje jako číslo, a tato čísla se sečtou. Jako zabezpečovací údaj se pak použije výsledný součet (ořezaný na stejný počet bitů, jaký mají jednotlivé sčítance). Představu ukazuje následující obrázek (č 6).

Obr. 6: Představa kontrolního součtu

Snad není těžké nahlédnout, že kontrolní součty dokáží detekovat více chyb, než parita. Je to dáno už jen tím, že dvojice chyb se většinou vzájemně neruší, tak jako je tomu u parity. Na druhou stranu stále mohou existovat takové kombinace chyb, které se navzájem vyruší a dávají stejný kontrolní součet, jako nepoškozený blok. Takže i kontrolním součtům mohou některé chyby uniknout.

Nejspolehlivější, a v praxi nejpoužívanější, je detekce chyb pomocí tzv. cyklických kódů, známějších spíše podle anglické zkratky CRC (Cyclic Redundancy Check). Jejich účinnost je přímo vynikající. Dokáží detekovat všechny shluky chyb s lichým počtem bitů, dále všechny shluky chyb do velikost n bitů (kde n je počet bitů zabezpečovacího údaje). Všechny větší shluky chyb pak CRC dokáží detekovat s pravděpodobností 99.99999998%. Výhodou je také poměrně snadná implementace a praktický výpočet zabezpečovacího údaje. Stačí k tomu poměrně jednoduchý obvod, který rychle zajistí potřebný výpočet. Tak kde je potom nějaký háček?

Vlastně nikde. Snad jenom v tom, že v pozadí za celou touto metodou detekce chyb stojí silná matematická teorie. Ta také dává návod na to, jak zabezpečovací údaj konkrétně počítat. Abychom se s tím mohli seznámit, museli bychom zabrousit opravdu hodně hluboko do algebry, na což zde rozhodně nemáme prostor. Proto se ani nebudeme snažit si nějak zjednodušeně popsat, jak se vlastně takové "CRC-éčko" počítá. Spokojíme se jen s konstatováním, že způsob využití je stejný jako u kontrolních součtů - zabezpečovací údaj se připojí k bloku, přenese spolu s ním, a na straně příjemce se počítá znovu a porovnává s přeneseným. Výsledkem je konstatování, že v bloku jako takovém je (resp. není) chyba. Opět, na rozdíl od parity, není patrné v které části bloku k eventuelní chybě došlo. Rozdíl, oproti kontrolním součtům, je v podstatně větší spolehlivosti, se kterou je eventuelní chyba detekována. Proto se také CRC v praxi používají velmi často.

Mechanismy pro opravu chyb

Výše popisované mechanismy (parita, kontrolní součty i CRC) jsou pouze detekčními mechanismy. Jsou tedy určené pouze k tomu, aby detekovaly výskyt jedné či více chyb. Zjišťovat počet chyb vlastně ani nemusí, protože se od nich očekávají pouze dvě možné odpovědi: "celý blok je v pořádku", a "blok není v pořádku". Další pokračování se totiž vždy týká celého bloku jako takového: buďto je celý zahozen (v případě nespolehlivého přenosu), nebo je vyžádán opakovaný přenos celého bloku (v případě spolehlivého přenosu).

Někdy ale je zapotřebí zajistit spolehlivý přenos, resp. zvýšit jeho spolehlivost, a není možné opakovat přenos poškozeného bloku dat. Třeba proto, že vůbec neexistuje možnost přenosu v opačném směru. Nebo proto, že takovýto přenos by neúnosně narušil pravidelnost doručování dat (viz výše). Co dělat v takovémto případě?

I zde existuje určité řešení, spočívající v použití takových zabezpečovacích údajů, které dokáží chyby nejenom detekovat, ale také je opravovat (u příjemce). V praxi se hovoří o tzv. samoopravných kódech (nejčastěji jsou v této roli používány tzv. Hammingovy kódy). V angličtině se zase lze setkat se zkratkou FEC, od: Forward Error Control, ve smyslu: dopředná ochrana proti chybám. Proč se ale tato možnost používá spíše vzácně, a přednost se dává opakovanému přenosu poškozených dat?

Problém je v tom, že takovéto samoopravné kódy mají příliš velkou režii. Aby dokázaly opravit byť jen "malé" chyby, musí přenést o hodně více dat. Princip jejich fungování si lze představit tak, že místo jedné "sady" dat jich přenáší hned několik (ve smyslu: dvakrát, třikrát atd. ta samá data), a z nich se u příjemce vybírá tu sada, která se přenesla bez poškození. V praxi to funguje poněkud efektivněji (dat se nepřenáší n x více), ale zase ne o tolik. Proto je celá tato varianta zajištění (zvýšení) spolehlivosti používána jen tam, kde nepřipadá v úvahu opakované zaslání poškozených dat.

Potvrzování

Pojďme nyní zpět k tomu, jak se spolehlivý přenos zajišťuje nejčastěji - skrze opakovaný přenos poškozených dat. Základní podmínkou je zde to, aby se odesilatel vůbec dozvěděl, zda příslušný datový blok byl či nebyl přenesen v pořádku. Z toho si pak již odvodí, zda přenos bloku opakovat či nikoli.

Nutnou podmínkou k tomu, aby se odesilatel dozvěděl cokoli od příjemce, je existence zpětné vazby, resp. možnost přenosu "v opačném směru" (od příjemce dat k jejich odesilateli). V praxi to znamená, že mezi oběma stranami musí existovat obousměrný přenosový kanál, resp. okruh. Ne nutně plně duplexní, ale alespoň poloduplexní. Skrze takovýto obousměrný kanál pak mohou obě strany vést určitý dialog, využívající mechanismus tzv. potvrzování.

Potvrzování (anglicky: Acknowledgement) funguje přesně tak, jak napovídá jeho název: potvrzuje, že byl určitý blok dat přenesen. Jde tedy o zprávu, kterou generuje příjemce datového bloku, a přijímá ji odesilatel tohoto bloku. Cestuje tedy v opačném směru, než v jakém je přenášen ten datový blok, který potvrzuje (od příjemce k odesilateli), viz obrázek (č. 7).

Jednotlivé potvrzování

Důležité je, že potvrzení může být jak kladné (potvrzující bezchybný přenos), nebo naopak záporné (signalizující chybně přenesený blok). Podstatné je také to, jak odesilatel s potvrzením nakládá.

Jedna základní možnost je taková, že když odesilatel odešle nějaký blok dat, nejprve čeká na odezvu druhé strany. Pokud dostane kladné potvrzení, pokračuje odesláním dalšího bloku (a znovu čeká na potvrzení atd.). Pokud dostane záporné potvrzení, odešle stejný blok znovu. Kromě toho ale musí počítat ještě i se dvěma dalšími možnostmi:

• s tím, že se mohl ztratit celý přenášený blok, takže příjemce ani neví, že by měl něco potvrzovat.
• s tím, že se ztratilo samotné potvrzení, které příjemce vygeneroval.

V obou případech si odesilatel musí natáhnout stopky a čekat určitou dobu (po určitý časový limit, v angličtině: timeout). Když do uplynutí této doby nedostane žádné potvrzení, interpretuje to stejně jako potvrzení záporné, a přenos bloku opakuje.

Celý právě popsaný postup je označován jako tzv. jednotlivé potvrzování (v angličtině: Stop&Wait ARQ). Ilustruje ho i následující obrázek (č. 8):

Obr. 8: Jednotlivé potvrzování

Snad není těžké nahlédnout, že velikost časového limitu musí být volena velmi pečlivě. Pokud by byla příliš krátká, odesilatel by mohl "předčasně zpanikařit" (a opakovat přenos dříve, než mu potvrzení přijde). Naopak, pokud časový limit byl moc velký, odesilatel by čekal zbytečně dlouho, a přenos by se zbytečně zpomaloval.

Kontinuální potvrzování

Jednotlivé potvrzování je vhodné pouze pro takové sítě, ve kterých "cesta tam a zpět", od odesilatele k příjemci, netrvá dlouho. Tedy tam, kde je malé tzv. přenosové zpoždění. To znamená hlavně v lokálních sítích (sítích LAN). V rozlehlých sítích (sítích WAN) je přenosové zpoždění relativně velké - a kvůli tomu neúměrně narůstají prodlevy, způsobené čekáním na potvrzení každého jednotlivého bloku. Ilustruje to i následující obrázek (č. 9.)

Obr. 9: Vliv přenosového zpoždění při jednotlivém potvrzování

V prostředí rozlehlých sítí je proto výhodnější jiná strategie, označovaná jako kontinuální potvrzování. Od jednotlivého potvrzování se liší v tom, že když odesilatel odešle nějaký blok, nečeká na jeho potvrzení, ale pokračuje odesláním dalšího bloku. Posílá tedy jednotlivé datové bloky stylem "jeden za druhým", a teprve zpětně přijímá potvrzení o tom, jak byly tyto bloky doručeny. Představu ukazuje následující obrázek (č. 10):

Obr. 10: Představa kontinuálního potvrzování

Jak je tomu ale v případě, že odesilateli přijde záporné potvrzení? Nebo že se ani po uplynutí časového limitu (timeoutu) nedočká žádného potvrzení, a musí to interpretovat jako záporné potvrzení? Zde existují dvě možné varianty toho, jak odesilatel reaguje.

První varianta je označována jako tzv. selektivní opakování. Spočívá v tom, že odesilatel zopakuje (znovu odešle) právě a pouze ten blok, který se poškodil či ztratil (ke kterému se vztahuje záporné potvrzení), a dále pokračuje jako kdyby se nic nestalo. Ukazuje to i následující obrázek (č. 11).

Obr. 11: Představa kontinuálního potvrzování se selektivním opakováním

Nevýhodou selektivního opakování je vyšší náročnost na příjemce. Pokud totiž přijme nějaký poškozený blok (nebo jej nepřijme vůbec), ještě nějakou dobu poté musí přijímat následující bloky, které ale nemůže ještě zpracovávat. Místo toho je musí někam ukládat a čekat, až dostane znovu původně poškozený či ztracený blok. Teprve pak může začít zpracovávat i následující., již přijaté bloky.

Uvedený problém řeší druhá varianta kontinuálního potvrzování, označovaná jako opakování s návratem. Spočívá v tom, že když odesilatel dostane záporné potvrzení (nebo mu vyprší časový limit), znovu odešle příslušný blok, a poté pokračuje těmi bloky, které po něm následující (bez ohledu na to, že některé z nich mohly v mezidobí být odeslány). Jinými slovy: vrátí se k poškozenému bloku, a dál pokračuje od něj. Ukazuje to i následující obrázek (č. 12).

Obr. 12: Představa kontinuálního potvrzování s návratem

I varianta "s návratem" ovšem má své nevýhody. Je sice šetrnější vůči příjemci, ale na druhé straně může plýtvat přenosovou kapacitou. Může totiž znovu přenášet takové bloky, které se již jednou přenesly úspěšně (bez chyb).

Samostatné a nesamostatné potvrzování

Na závěr se ještě zastavme u toho, jakou konkrétní podobu mohou mít potvrzení, zasílaná od příjemce směrem k odesilateli. Jedna možnost je taková, že potvrzení jsou zcela samostatná, neboli že jde o principiálně stejné bloky, v jakých se přenáší i samotná data. Mají tedy mj. svou vlastní hlavičku, která určitým způsobem zvyšuje režii na přenos.

Snaha eliminovat tuto režii vedla ke vzniku tzv. nesamostatného potvrzování (anglicky: piggybacking). To spočívá v tom, že příjemce původních dat čeká s jejich potvrzením, dokud " v protisměru" necestuje nějaký jiný datový blok, z nějakého jiného přenosu - a do něj jen "přidá" své potvrzení. Využívá tedy toho, že zmíněný blok "v protisměru", patřící nějakému jinému přenosu, již tak jako tak má svou hlavičku a další náležitosti, a tudíž přírůstek režie na zajištění potvrzení je minimální. Obě varianty ilustruje následující obrázek (č. 13).

Obr. 13: Představa samostatného a nesamostatného potvrzování

I nesamostatné potvrzování však má svá úskalí. Zejména to, že příjemce nemůže čekat příliš dlouho na to, až "v protisměru" bude přenášen nějaký jiný datový blok, do kterého by své potvrzení vložil. Odesilatel o tom totiž neví, a mohl by mu vypršet jeho časový limit (timeout). V praxi se příjemce snaží o nesamostatné potvrzení jen chvíli, a pokud se mu nepodaří, přechází k samostatnému potvrzení (tj. odešle své potvrzení jako samostatný blok).

---