Protokol s posuvným okénkem

Protokoly s posuvným okénkem slouží k efektivnímu zajištění spolehlivého přenosu dat nespolehlivým kanálem. Spolehlivostí není míněna stoprocentní jistota úspěšného přenosu dat; znamená, že pokud ani opakované pokusy o přenos nebudou úspěšné, bude oznámena chyba. Spolehlivosti se obecně dosahuje postupem nazývaným zpětná vazba s automatickým opakováním, což je potvrzování přenesených dat pomocí zpětného kanálu a opakovaným vysíláním při chybě. U jednoduchých protokolů musí odesilatel po odeslání každého bloku dat čekat na potvrzení (jednotlivé potvrzování); protokoly s posuvným okénkem jsou efektivnější, protože umožňují vyslání většího množství dat bez čekání na potvrzení od příjemce. Toto množství vytváří „okénko“, které umožňuje používat omezený rozsah čísel na potvrzování a regulovat rychlost vysílání, aby nedošlo k zahlcení komunikačního spoje.

Princip fungování

Koncepčně je každé přenosové jednotce (většinou rámcům linkové vrstvy, ale v TCP jednotlivým bytům) přiřazeno jednoznačné pořadové číslo. Příjemce tato čísla používá pro řazení přijatých paketů do správného pořadí, zahazování duplicitních paketů a identifikaci chybějících. V praktické implementaci je nutné omezit velikost pořadových čísel, obvykle pomocí funkce modulo.

Omezením počtu paketů, které mohou být vyslány nebo přijaty v libovolném okamžiku, protokol s posuvným okénkem umožňuje přenos neomezeného počtu paketů při použití pořadových čísel s pevnou velikostí. Termín „okénko“ na straně odesilatele reprezentuje logickou hranici celkového počtu paketů, které ještě mají být potvrzeny příjemcem. Příjemce informuje odesilatele v každém potvrzovacím paketu o aktuální maximální velikosti přijímací vyrovnávací paměti (velikosti okénka). V TCP hlavičce je šestnáctibitové pole pro oznámení velikosti přijímacího okénka odesilateli. Největší použitelné okénko je tedy 2¹⁶ = 64 kilobytů. V režimu s pomalým startem odesilatel začíná posílat malý počet paketů a tento počet zvyšuje při každém vysílání po přijetí potvrzení paketu z příjemce. Po každém potvrzení přijetí paketu se okénko posune o jeden paket pro vysílání dalšího paketu. Po dosažení hranice okénka odesilatel posílá jeden paket při přijetí každého potvrzovacího paketu. Jestliže je například velikost okénka 10 paketů, pak v režimu pomalého startu odesilatele může začít přenos jedním paketem následovaným dvěma pakety (před přenosem dvou paketů musí být přijato potvrzení jednoho paketu), následovaný třemi pakety a tak dále, dokud se bez potvrzení neposílá 10 paketů. Po dosažení 10 paketů je vysílání omezeno na vyslání jednoho paketu při přijetí jednoho potvrzovacího paketu. Při simulaci to vypadá, jako kdyby se okénko posouvalo o jeden paket při přijetí každého potvrzovacího paketu. Také na přijímací straně se okénko posunuje o jeden paket pro každý přijatý paket. Metoda posuvného okénka zaručuje, že nedojde k zahlcení sítě provozem. Aplikační vrstva bude stále nabízet data pro přenos na TCP bez ohledu na problémy se zahlcením sítě, protože TCP na straně odesilatele i příjemce implementuje metodu posuvného okénko pro vyrovnávací paměť paketů. Velikost okénka se může měnit dynamicky podle intenzity provozu v síti.

Pro dosažení maximální propustnosti musí být vysílací okénko tak velké, aby odesilatel nebyl brzděn čekáním na potvrzení, což znamená, že okénko musí mít takovou velikost, aby bylo možné vysílat data bez potvrzení po celou dobu trvání obousměrného zpoždění (RTT). Velikost okénka musí být větší než součin přenosové rychlosti a zpoždění komunikačního spoje. Jestliže tomu tak není, bude protokol omezovat efektivní šířku pásma spoje.

Motivace

Pokud se pro detekci a opravu chyb při komunikaci používá zpětná vazba s automatickým opakováním, musí příjemce potvrzovat přijaté pakety podle protokolu. Jestliže odesilateli nepřijde potvrzení v přiměřeném čase, pošle data znovu.

Když odesilatel nedostane potvrzení, nemůže vědět, zda příjemce skutečně paket přijal; jak původní paket, tak potvrzení se mohlo ztratit nebo poškodit při přenosu. Jestliže algoritmus detekce a opravy chyb odhalí poškození, příjemce paket zahodí a nepošle žádné potvrzení. Podobně příjemce obvykle nemá jistotu, zda jeho potvrzení bylo přijato. Pokud se ztratí potvrzení, mohou příjemci dojít stejná data dvakrát nebo vícekrát. V tomto případě příjemce musí znovu vyslat potvrzení, aby zabránil dalšímu opakování vysílání, ale duplicitní data ignoruje.

Fungování protokolu

V typické implementaci je n_t  číslo dalšího paketu, který má být poslán, tj. pořadové číslo prvního zatím nevyslaného paketu. Obdobně n_r je číslo prvního zatím nepřijatého paketu. Zatím budeme pro zjednodušení předpokládat, že ani jedno z čísel v průběhu času neklesá.

Odesilatel i příjemce si udržují aktuální hodnoty n_t a n_r. Také si pamatují velikost okénka w_t a w_r. Velikosti okének se mohou měnit, ale v jednodušších implementacích jsou pevné. Aby bylo možné přenášet data, velikost okénka musí být větší než nula.

Příjemce si také pamatuje nejvyšší dosud přijaté pořadové číslo; v proměnné n_s má hodnotu o jedničku větší. Jednoduché přijímače, které přijímají pakety pouze po řadě, mají w_r = 1, a n_r = n_s. U chytřejších přijímačů se n_r a n_s může lišit.

Základním pravidlem je, že všechny pakety s číslem nižším než n_r byly přijaty, žádné pakety s číslem vyšším než n_s nebyly přijaty a v rozsahu n_r a n_s byly některé pakety přijaty.

Když příjemce přijme paket, aktualizuje si proměnné a pošle potvrzení s novým n_r. Odesilatel si udržuje číslo n_a nejvyššího potvrzení, které přijal. Odesilatel ví, že všechny pakety s číslem menším než n_a byly přijaty, ale o paketech mezi n_a a n_s to neví; tj. n_a ≤ n_r ≤ n_s.

Pro pořadová čísla vždy platí: n_a ≤ n_r ≤ n_s ≤ n_t ≤ n_a + w_t. Tj.:

• n_a ≤ n_r: Nejvyšší potvrzení přijaté odesilatelem nemůže být vyšší než nejvyšší n_r potvrzený příjemcem.
• n_r ≤ n_s: Rozpětí plně přijatých paketů se nemůže rozšířit za konec částečně přijatých paketů.
• n_s ≤ n_t: Nejvyšší přijaté číslo paketu nemůže být větší než nejvyšší číslo poslaného paketu.
• n_t ≤ n_a + w_t: Nejvyšší číslo posílaného paketu je omezené nejvyšším přijatým potvrzením a velikostí vysílacího okénka.

Fungování odesilatele

Odesilatel může po přijetí potvrzení n_a poslat až w_t paketů. To znamená, že může vysílat pakety číslo n_t, dokud n_t < n_a+w_t.

Pokud při komunikaci nedochází k chybám, odesilateli přicházejí rychle potvrzení pro všechny pakety, které odeslal, takže n_a je rovno n_t. Pokud dojde k chybě, musí odesilatel po přiměřeném zpoždění opakovat vysílání paketů s čísly mezi n_a a n_t.

Metody pro definování „přiměřeného zpoždění“ mohou být velmi komplikované, ale ovlivňují pouze efektivitu komunikace; základní spolehlivost protokolu s posuvným okénkem na detailech nezávisí.

Fungování příjemce

Při přijetí paketu s číslem x příjemce zkontroluje, zda padne do přijímacího okénka: n_r ≤ x < n_s+w_r (nejjednodušším příjemcům stačí udržovat jednu hodnotu n_r=n_s). Paket, jehož číslo padne do okénka, příjemce přijme. Pokud má přijatý pakt číslo n_r, příjemce zvětší přijímací pořadové číslo o 1 nebo o více, pokud už má přijaty a uloženy následující pakety. Jestliže x > n_r, paket bude uložen až do doby, dokud nebudou přijaty všechny předchozí pakety. Jestliže x≥n_s, je n_s aktualizováno na n_s=x+1.

Jestliže číslo paketu neleží uvnitř přijímací okénka, příjemce jej zahodí a nemění ani n_r ani n_s.

Bez ohledu na to, zda byl paket v pořádku přijat nebo ne, příjemce pošle potvrzení obsahující aktuální n_r. Potvrzení může obsahovat i informace o dalších paketech přijatých mezi n_r nebo n_s pro zlepšení efektivity – to je tak zvané selektivní opakování.

Nemá význam, aby velikost přijímacího okénka w_r byla větší než vysílacího w_t, protože není třeba se starat o přijaté pakety, které zatím nebyly vyslané; užitečný rozsah je 1 ≤ w_r ≤ w_t.

Potřebný rozsah hodnot čísel paketů

Posloupnost čísel modulo 4 s w_r=1. Na počátku, n_t=n_r=0. První sloupec je počáteční stav, druhý sloupec po odeslání prvního rámce, třetí po přijetí prvního rámce, čtvrtý po přijetí prvního potvrzení.

Zatím jsme předpokládali, že pořadová čísla mohou mít neomezenou velikost, takže mohou stále růst. V praxi je ale nutné velikost pořadových čísel x omezit na x mod N, pro nějaké konečné N. (N obvykle je mocnina 2.)

Odesilatel pak bude přijímat pouze potvrzení v rozsahu n_a až n_t včetně. Protože to zaručuje, že n_t−n_a ≤ w_t, existuje nejvýše w_t+1 možných pořadových čísel, která mohou přijít v libovolném okamžiku. Odesilatel tedy může jednoznačně dekódovat pořadové číslo, pokud N > w_t.

Silnější omezení je vynuceno příjemcem. Fungování protokolu závisí na tom, aby příjemce byl schopen spolehlivě rozlišit nové pakety (které musí být přijaty a zpracovány) od opakovaného vysílání starých paketů (který musí být zahozeny a znovu odvysíláno poslední potvrzení). To lze provést, pokud známe velikost okénka odesilatele. Po přijetí paketu s číslem x, příjemce ví, že x < n_a+w_t, tak n_a > x−w_t. Tedy pakety s čísly x−w_t nebudou znovu vysílány.

Nejnižší pořadové číslo, které budeme ochotni přijímat v budoucnosti, je n_s−w_t

Příjemce také ví, že n_a odesilatele nemůže být větší než nejvyšší dosud poslané potvrzení, což je n_r. Tedy nejvyšší pořadové číslo paketu, který může příjemce dostat, je n_r+w_t ≤ n_s+w_t.

Příjemce tedy může v určitém okamžiku rozlišit 2w_t různých pořadových čísel. Proto se může zdát, že musíme mít N ≥ 2w_t. Ale skutečný limit je nižší.

Příjemce nemusí akceptovat ani příliš malá ani příliš velká pořadová čísla (menší než n_r nebo větší nebo rovná n_s+w_r). V těchto případech příjemce paket ignoruje a pouze znovu pošle potvrzení. Musí pouze platit N ≥ w_t+w_r. Často bývá w_r<w_t (viz např. opakování s návratem níže), což umožňuje, aby w_t bylo pro pevné N větší.

Příklady

Nejjednodušší posuvné okénko: jednotlivé potvrzování

I když se obvykle k protokolům s posuvným okénkem nepočítá, je jednotlivé potvrzování ve skutečnosti nejjednodušší možnou implementací posuvného okénka. Vysílací i přijímací okénko má velikost 1 paket. To vyžaduje N=1+1=2 pořadová čísla (obvykle reprezentovaná jediným bitem).

Příklad nejednoznačnosti

Odesilatel střídavě posílá pakety označené „lichý“ a „sudý“. Potvrzení také říká „lichý“ nebo „sudý“. Předpokládejme, že odesilatel, který měl poslat lichý paket, nečekal na jeho („liché“) potvrzení a místo toho okamžitě poslal následující sudý paket. Pak může přijmout potvrzení říkající „další očekávaný paket je lichý“. Tak by se odesilatel dostal do dilematu: přijal příjemce oba pakety nebo žádný?

Opakování s návratem

Opakování s návratem je protokol s posuvným okénkem s w_t>1, ale s pevným w_r=1. Kromě prvního dosud nepřeneseného paketu příjemce všechny ostatní pakety odmítá. Jestliže dojde, ke ztrátě paketu při přenosu, následující pakety jsou ignorovány, dokud není znovu vyslán chybějící paket, což způsobí zpoždění minimálně jednoho obousměrného zpoždění. Proto je tato metoda neefektivní na spojích, kde dochází často ke ztrátě nebo poškození paketů.

Příklad nejednoznačnosti

Předpokládejme, že používáme tříbitová pořadová čísla, jako je tomu u normálních režimů protokolu HDLC. To dává N=2³=8. Protože w_r=1, musí být w_t≤7. Důvodem je, že po přenosu 7 paketů existují 8 možných výsledků: mohlo být úspěšně přijato 0 až 7 paketů. To je 8 možností a odesilatel je potřebuje všechny rozlišit.

Pokud by odesilatel poslal 8 paketů bez čekání na potvrzení, mohl by se dostat do stejného dilematu jako při jednotlivém potvrzování: znamená opakování stejného čísla v potvrzení, že bylo přijato úspěšně všech 8 paketů nebo žádný?

Selektivní opakování

Nejobecnějším případem protokolu s posuvným okénkem je selektivní opakování. U tohoto protokolu příjemce přijímá pakety s pořadovými čísly vyššími než je aktuální n_r a ukládá je, dokud se nezaplní díry po nepřijatých paketech. To vyžaduje mnohem komplikovanější práci s vyrovnávacími pamětmi na straně příjemce.

Výhodou však je, že není nutné zahazovat už přenesená správná data po dobu jednoho round-trip intervalu, než je odesilatel informován, že je nutné opakovat přenos. Tato metoda je proto upřednostňována na spojích s velkou chybovostí nebo s vysokým součinem přenosové rychlosti a zpoždění.

Velikost okénka w_r musí být větší než největší počet po sobě jdoucích ztracených paketů, se kterými může protokol pracovat. Proto se často používají malé hodnoty, např. w_r=2.

Příklad nejednoznačnosti

Velmi oblíbený protokol HDLC používá tříbitová pořadová čísla a má volitelnou podporu pro selektivní opakování. Pokud se ale má používat selektivní opakování, musí se dodržet požadavek, aby n_t+n_r ≤ 8; jestliže w_r je zvětšeno na 2, w_t musí být zmenšeno na 6.

Předpokládejme, že w_r =2, ale je použit neupravený odesilatel s w_t =7, jak je v HDLC typické pro opakování s návratem. Dále předpokládejme, že příjemce začíná s n_r =n_s =0.

Nyní předpokládejme, že příjemce přijme následující řadu paketů (čísla jsou modulo 8):

0 1 2 3 4 5 6 (pause) 0

Protože w_r =2, příjemce přijme a uloží poslední paket 0 (domnívá se, že je to paket 8 v řadě) a požaduje opakování přenosu paketu 7. Je ale možné, že odesilatel nepřijal žádné potvrzení a proto znovu odvysílal paket 0. Pak je ale chybou, že příjemce považoval poslední paket za paket 8. Řešením je omezit na odesilateli w_t ≤6. S tímto omezením příjemce po přijetí paketu 6 ví, že pro n_a odesilatele platí n_a ≥1, a tedy následující paket s číslem 0 musí být paket 8. Pokud by se ztratila všechna potvrzení, pak musí odesilatel po paketu 5 přestat vysílat a čekat na potvrzení.

Rozšíření

Protokol s posuvným okénkem lze různými způsoby rozšířit:

• Výše uvedené příklady předpokládaly, že pakety nejsou při přenosu nikdy prohozeny; mohou se ztratit (algoritmus detekce a opravy chyb zahazuje poškozené pakety), ale nikdy nebudou doručeny ve špatném pořadí.

Protokol může být rozšířen, aby dovoloval přehození paketů, pokud je vzdálenost přehození omezená; pak musí být pořadové číslo modulo N zvětšeno o maximální vzdálenost přehození.

• Je možné nepotvrzovat každý paket, pokud se zajistí pozdější poslání potvrzení, když za určitou dobu žádný další paket nepřijde. TCP například normálně potvrzuje každý druhý paket.
• Protože odesilatel posílá pakety po řadě, je obvyklé informovat odesilatel okamžitě, jakmile se vyskytne díra v posloupnosti paketů. HDLC má pro tento účel speciální paket REJ (reject).
• Velikosti vysílacího a přijímacího okénka se během komunikace může měnit, ale jejich součet nesmí překročit N. Omezení velikosti vysílacího okénka se používá pro zmenšení rychlosti přenosu tak, aby vyhovovala rychlosti spoje a zabránilo se saturaci nebo zahlcení.
• Obvyklým zjednodušením selektivního opakování je tak zvaná „zpětná vazba s automatickým opakováním SREJ-REJ“. Používá w_r=2 a přijme následující pakety, ale povoluje pouze jediný ztracený paket; jestliže se ztratí druhý paket, žádné další pakety se do vyrovnávací paměti neukládají. (Tj. w_r=1 při čekání). Tak je možné zvýšit výkonnost na úroveň úplného protokolu se selektivním opakováním při jednodušší implementaci.

Související články

• Zpětná vazba s automatickým opakováním
• Jednotlivé potvrzování
• Opakování s návratem
• Selektivní opakování

Reference

V tomto článku byl použit překlad textu z článku Sliding window protocol na anglické Wikipedii.

• Comer, Douglas E. "Internetworking with TCP/IP, Volume 1: Principles, Protocols and Architecture", Prentice Hall, 1995. ISBN 0-13-216987-8
• Peterson, Larry L. & Davie, Bruce S. "Computer Networks: A Systems Approach", Morgan Kaufmann, 2000. ISBN 1558605142

Externí odkazy

• Obrázky, zvuky či videa k tématu Protokol s posuvným okénkem na Wikimedia Commons
• RFC 1323 – Rozšíření TCP pro vysokou výkonnost
• TCP window scaling and broken routers, 2004
• Sliding Window Demo Archivováno 11. 3. 2011 na Wayback Machine. (vyžaduje Flash)