Zabezpečení dat při přenosech

Problémy při komunikaci v reálné síti

ztrácení a poškozování paketů
duplikace a změna pořadí paketů v sítích s alternativními cestami

=> nutnost zavedení zpětné vazby do přenosu

Typy zpětné vazby

potvrzovací - zpět ACK/NAK
detekční - zpět CRC
informační - zpět celý rámec

Poznámka:
Mohou se ztrácet nejen informační pakety, ale i potvrzení :-).

Číslování rámců (sekvenční čísla)

pro zajištění správného pořadí rámců
proti duplicitám při opakovaném vyslání (retransmisi)

Komunikační protokol

Soubor syntaktických a sémantických pravidel (včetně definice časových poměrů) pro komunikaci dvou nebo více zařízení.
Dále budeme diskutovat protokoly pro zajištění spolehlivé komunikace dvou stanic.

Potvrzovací schémata

Typy potvrzování

pozitivní (ACK) - potvrzuje správné přijetí
negativní (NAK) - informuje o přijetí rámce s chybou (samo o sobě nestačí, urychluje však detekci chyb)
kombinované - používá se ACK i NAK

Potvrzování a časovým limitem (timeout)

volba vhodného timeoutu řeší problém ztráty pozitivního potvrzení
komplikuje formální popis protokolu (nutnost zavedení časového kontextu).
problém volby velikosti timeoutu: brzké zjištění nutnosti retransmise vs. předčasné retransmise

Problém tří armád

Konečným počtem vyměněných zpráv nelze zajistit, aby měl přijímač jistotu, že jeho potvrzení došlo zpět na vysílač.

Klasifikace potvrzovacích schemat (protokolů)

Stop-and-wait

Vysílač vyšle jediný rámec a čeká na potvrzení.

Na kanálech s velkým zpožděním velmi neefektivní.

Skupinové potvrzování (pipelining)

Efektivní pro spoje s velkou dobou zpoždění

Continuous ARQ (Automatic Retransmission Request): na full-duplex kanálu, efektivita až 100%
Potvrzení zpravidla inkluzivní (potvrzuje vše až do uvedeného sekvenčního čísla)
- chrání před ztrátou předchozího potvrzení

Protokoly využívající metody klouzavého okénka (Sliding Window)

Stanice smí vyslat i více rámců (počet dán šířkou vysílacího okna).
Při odeslání se pro každý rámec nastartuje časovač pro potvrzení.
ACK se posílá od každého přijatého rámce, popř. do časového limitu od času příchodu prvního dosud nepotvrzeného rámce (ušetření některých ACK).
Při přijetí rámce s chybou ACK nevyšleme (nebo vyšleme NAK)

Negativní potvrzení nejsou nutná, jen urychlují detekci neúspěšného přenosu rámce (která by se jinak zjistila až při vypršení timeoutu)

Vysílací okno
- buffer s vyslanými rámci, které dosud nebyly potvrzeny a možná budou muset být vyslány znovu

Přijímací okno
- buffer na přijímané rámce, které ještě nemohly být doručeny vyšší vrstvě přijímače, protože dosud chybí některý z předchozích rámců v řadě

Obě okénka "kloužkou" po sekvenčních číslech:

Vysílač:

   Seq# ------------------------------------------------->

   +-------------+---------------------+-----------------+
   |  vyslané a  |  vyslané, ale       |  budoucí rámce  |
   |  potvrzené  |  dosud nepotvrzené  |  od vyšší       |
   |  rámce      |  rámce              |  vrstvy         |
   +-------------+---------------------+-----------------+

Používají se dvě varianty sliding window protokolu:

Go-back-N
Selective Repeat

1) Go-back-N

šířka okna přijímače 1 rámec

Chování při chybě v přenosu rámce:

a) přijímač detekoval chybu v rámci i:
- přijímač pošle NAK nebo mlčí (převod na ztrátu rámce v síti)
- vysílač při příjmu NAK opakuje všechny rámce vysílacího okna od i znovu

b) rámec se ztratí:
- přijímač očekává rámec i-1, ten se ztratil, ale přišel jeho následník i.
Přijímač odešle NAK i (nebo mlčí, čímž se převede na ztrátu rámce)

c) rámec i se ztratí a další se nevysílají:
- vysílač vytimeoutuje a rámec i pošle znovu

Chování při poškození potvrzení:

- pokud se ztratí ACK i, může jej nahradit ACK s vyšším číslem, pokud příjde před timeoutem vysílače
pro rámec i. Pokud se to nestihne, vyšle vysílač rámec i a zbytek vysílacího okna znovu

- Poškozený/ztracený NAK i: vysílač vytimeoutuje a vyšle všechny rámce svého okna znovu od i včetně

Při timeoutu (nebo explicitním odmítnutí) rámce se zopakuje nepotvrzený rámec i všechny následující (předpokládá se, že přijímač s přijímacím okénkem o jedné pozici je stejně odmítne a zahodí).

Poznámka:
Šířka okna musí být aspoň o jednu menší než počet použitelných sekvenčních čísel (nepoznali bychom ztrátu všech rámců okna)

2) Selective repeat

šířka okna přijímače více než jeden rámec

selektivní retransmise jen těch rámců, které vytimeoutují nebo jsou přijímačem explicitně odmítnuty (NAK)
přijímač musí obsahovat buffery na rámce, které příjdou za chybovým a uchovávat je do doplnění celé sekvence (a jejího poskytnutí aplikaci).

Maximální šířka okna: polovina sekvenčních čísel (z důvodu překrývání vysílacího a přijímacího okna).

Poznámky k oběma variantám Sliding Window

Chování algoritmu Sliding Window při šířce okna přijímače
a) 1 rámec (go-back-N)
b) více rámců (selective repeat):

Negativní potvrzování se často nepoužívá, řeší se timeouty na straně vysílače. Může však urychlit opravu chyb.
Maximální šířka přijímacího okna může být stanovena pevně. Inzerování aktuální šířky přijímacího okna v povrzeních však můžeme protokol současně použít pro řízení toku dat od vysílače (flow control) - využito např. v protokolu TCP. Vysílací okno se pak dynamicky upravuje tak, aby nepřesahovalo šířku přijímacího okna.
piggybacking = připojování potvrzení k informačním rámcům ve druhém směru.
Sliding window nalezneme např. na spojové nebo transportní vrstvě modelu OSI-RM.

Efektivita potvrzovacích schemat

Stop and Wait

ef = lm / (lm+cT+la+cT) = lm / (lm+la+2cT) [%]

Konkrétní příklady

Modemová linka, pomalá a LAN se spíše větším zpožděním:
lm=80B, la=1B, c=14400 bps, T=1ms, ef=94.56 %

Družicový spoj
lm=80B, la=1B, c=14400 bps, T=270 ms, ef=7.6 %

Prodloužení rámce 8x:

Modemová linka, pomalá a LAN se spíše větším zpožděním:
lm=640B, la=1B, c=14400 bps, T=1ms, ef=99.28 %

Družicový spoj
lm=640B, la=1B, c=14400 bps, T=270 ms, ef=40.38 %

Prodloužení rámce efektivitu zlepší, ale v případě výskytu chyby v rámci se pak zahazuje celý (dlouhý) rámec, oproti např. jen jednomu ze dvou polovičních.

Sliding Window

ef = M.lm / (lm+cT+la+cT) = M.lm / (lm+la+2cT) [%]

Lze dosáhnout až 100% efektivity: