PA159, přednáška 2 2. 10. 2009 Co nás dnes čeká... • Úvaha o tom, jak zapisovat protokoly • Úvod do abstraktní protokolové notace • Zajištěné přenosové protokoly • TCP Abstraktní protokolová notace Specifikace protokolů • Jak vůbec formálně protokol specifikovat? • Popis v přirozeném jazyce – problém s exaktností, jednoznačností • Popis v programovacím jazyce – typicky v C – neohrabané, matematicky nepraktické a neelegantní – hůře čitelné (na druhé straně notaci zná dost lidí) – problém s verifikací • Diagramy Specifikace protokolů (2) • Časové osy Specifikace protokolů (3) • Časové osy – přehledné pro jednoduché případy, obtížně použitelné pro složitější • Problém s dokazováním/verifikací • => Potřeba formální notace – Abstraktní protokolová (AP) notace • M. Gouda, Protocol verification made simple: a tutorial. Computer Networks and ISDN Systems 25 (1993), 969 - 980 • M. Gouda, Elements of Network Protocol Design, 1998 Ukázka AP • Prodejní automat ;o) Elementy AP • Základní struktura specifikace • Typy konstant – positive integer – sdílení konstant se stejným jménem přes procesy Elementy AP (2) • Typy vstupů – boolean, range, integer, set, enumerated, array – nesdílí se • Proměnné – boolean, range, integer, enumerated, array – nesdílí se Elementy AP (3) • Akce • Stráže – operátory • porovnání: =, /=, <, >, <=, >= • logické operace: Ù, , ~ • aritmetické operace: +, –, *, +[n], –[n], min, max – příjem dat – timeout Elementy AP (4) • Výrazy – dolce far niente – přiřazení • napřed se vyhodnotí, pak se přiřadí! – odeslání zprávy/dat Elementy AP (5) – sekvence výrazů – podmíněný výběr (Ú[k] local_guard.k = true) – opakování • Kanál p ® q: ch.p.q – #ch.p.q - počet zpráv v kanálu ch.p.q – m#ch.p.q - počet zpráv m v kanálu ch.p.q Elementy AP (6) • Vykonávání specifikace protokolu – nedeterministický výběr • výběr z více povolených možností ve výrazu if • výběr z více povolených akcí – atomicita akce – férové vykonávání protokolu • je-li akce neustále povolena, bude určitě vykonána • definice přes nekonečné běhy A nyní trochu praxe... • Kódování Manchester – odesílající proces – přijímající proces Elementy AP (7) • zprávy s poli • nedeterministické přiřazování • pole procesů Elementy AP (8) • parametrizované akce – v deklarační části přibude – použití A opět trochu praxe... • protokol pro alokaci zdrojů – uživatel – hlídač • protokol není férový - hlídač může stále ignorovat jeden proces (pozor, podmínka férového výkonu protokolu sice platí, ale potíže je v tom, že díky nastavení avail[r] := false je příslušná akce na vypnuta!) • řešení: a) determinismus (klientům přiděluji v definovaném pořadí) b) randomizace: Chyby při přenosu sítí • 3 základní typy – ztráta dat – poškození dat • zahozením se dá převést na ztrátu – přeuspořádání zpráv/paketů • pro snazší práci se zavádí 2 pravidla – atomičnost chyb – chyby se vyskytují zřídka (pouze konečný počet chyb v potenciálně nekonečném běhu protokolu) Ošetření chyb • příjem poškozených dat – převedeme na ztrátu • ztráta paketu => timeout Normální timeouty • Forma normálního timeoutu – po každý pár (ms#ch.s.t <= ks) Ù (mt#ch.t.u <= kt) platí, že stráž akce posílající zprávy mt má tvar recv ms from s Normální timeouty (2) • Implementace pomocí hodin s reálným časem Zajištěný protokol pro transportní vrstvu Požadavky na protokol • Odolnost vůči chybám – kontrola integrity dat – detekce výpadků pomocí timeoutů – vypořádání se s přeuspořádáním (nějak) • Obrana proti zahlcení přijímajícího uzlu – informace od přijímající strany • Obrana proti zahlcení sítě – není-li spolehlivá odezva ze sítě, odhad Odolnost proti chybám • Detekce poškození dat – Backward Error Recovery • ověření integrity – kontrolní součty • v případě selhání data skartována • vyžádá se nová kopie – Forward Error Recovery • data jsou posílána redundantně tak, že se omezené výpadky dají rekonstruovat – n-ohraničené poškození, ztráty a přeuspořádání Odolnost proti chybám (2) • Detekce výpadku => potvrzování – vlastně také Backward Error Recovery – určité množství dat může být odesláno bez potvrzení • Typy potvrzení – individuální potvrzování – kumulativní potvrzování – blokové potvrzování – negativní potvrzování (přímo informace o výpadku) Kumulativní potvrzování Kumulativní potvrzování (2) Kumulativní potvrzování (3) • Je nutné použít neohraničená sekvenční čísla – příklad problému s ohraničenými čísly: 1. odesílatel pošle data(3), data(4) 2. příjemce pošle ack(4), ack(5) 3. ack(5) se zadrhne na lince a je předběhnut následnými acky 4. dojde k přetočení ohraničených sekvenčních č. 5. přijde ack(5) 6. neštěstí je hotovo ;-) Další typy potvrzování • Individuální – potvrzování každé zprávy zvlášť • neefektivní – použití cirkulárního bufferu o velikosti nejméně 2w – možnost použití ohraničených sekvenčních čísel • Blokové – potvrzování přijatých spojitých bloků – cirkulární buffer o velikosti nejméně 2w – možnost použití ohraničených sekvenčních čísel Řízení velikosti okna • modifikace odesílatele u kumulativního potvrzování – stačí modifikace odesílatele – povede-li se bez ztráty zprávy odeslat více než cmax zpráv, je okno w inkrementováno o 1 – dojde-li k timeoutu a zmenšení velikosti okna, je třeba počítat s tím, že mohlo dojít ke ztrátě dat v dosud nepotvrzeném okně a zmenšovat proto dál okno (condition DNR) Kvalita protokolu • Agresivita – schopnost využít dostupnou volnou kapacitu • Responsivnost – schopnost přizpůsobení se menší kapacitě • Férovost – férové (případně jinak definované) dělení šířky pásma mezi klienty při požadavcích převyšujících možnosti sítě TCP Z historie • Poprvé formálně specifikován r. 1974: Vint Cerf, Yogen Dalal a Carl Sunshine • Zajišťuje – spolehlivost – ochranu proti zahlcení (různé algoritmy) – uspořádání paketů Mechanismy potvrzování • kumulativní potvrzování • piggybacking (duplexní protokol) – potvrzení je součástí zprávy jdoucí opačným směrem • jedno potvrzení na 2 segmenty – je-li přenos dost rychlý (timeout 500ms) • duplikované potvrzení – indikuje ztracený (poškozený) paket Zpracování malých zpráv • Nagleův algoritmus 1. Pokud proces p obdržel potvrzení pro všechna data dříve odeslaná q, potom proces p posílá zprávu ihned 2. Pokud proces p neobdržel potvrzení pro všechna data dříve odeslaná q, potom proces p uloží zprávu pro pozdější odeslání 3. Pokud velikost uložených zpráv přesáhne maximální velikost segmentu (MSS), tak se začne odesílat Řízení toku • řízení velikosti okna Okno TCP • outstanding window (ownd) • receiver window (rwnd) – flow control, self-clocking • congestion window (cwnd) Řízení zahlcení • aproximativní • detekce zahlcení pomocí výpadků – následná detekce – existují i preventivní mechanismy – závislost na informacích ze sítě • congestion window (cwnd) – bw = 8*MSS*cwin/RTT v případě že owin je limitováno cwin Hlavička TCP Ustavení spojení • Entity (programy) A a B, sekvenční čísla SEQ(A) a SEQ(B) • A: SYN, RAND(SEQ(A)) -> B • B: SYN/ACK, RAND(SEQ(B)), SEQ(A)+1 -> A • A: ACK, SEQ(B)+1 -> B • => three-way handshake Fáze Slow Start • cwnd += MSS pro každý ACK • exponenciální nárůst cwnd • limitováno sstresh • přechod do congestion avoidance fáze Fáze Congestion Avoidance (Tahoe) • AIMD (Tahoe) – additive increase, multiplicative decrease – cwnd += 1 MSS během každého RTT bez výpadku – cwnd = cwnd / 2 při výpadku • Detekce výpadku – timeout – duplikované ACKy při výpadku • sstresh = max{0.5*cwnd, 2*MSS} – návrat k slow start fázi Chování velikosti okna – Tahoe Vylepšené chování – Reno • fast retransmission – detekce výpadku 3 duplikovanými ACKy • fast recovery – neprovádí se fáze slowstart • sstresh = max{0.5*cwnd, 2*MSS} – (stejný jako TAHOE) • cwnd = sstresh + 3*MSS Chování velikosti okna – Reno Reakce na zahlcení • celé aktuální okénko (owin) – TCP Tahoe – klasický cummulative ACK • jeden segment v rámci „Fast Retransmit” – TCP Reno • více segmentů v rámci “Fast Retransmit” – TCP NewReno • právě ztracené segmenty – TCP SACK – blokové potvrzení Alternativní přístup k řízení zahlcení – Vegas • monitoruje RTT • zahlcení detekuje pomocí prodlužování RTT • na zahlcení reaguje lineárním poklesem cwnd TCP Response Function • Vztah mezi rychlostí výpadků a propustností (owin/bw) – owin ~ 1.2/sqrt(p) – bw = 8*MSS*owin/RTT – bw = (8*MSS/RTT)*1.2/sqrt(p) • p... packet loss rate [packet/s] Responsivnost TCP • Schopnost návratu na plnou přenosovou rychlost po výpadku • Přepokládejme výpadek v okamžiku, kdy cwnd = bw*RTT • závislost na RTT a MSS/MTU Responsivnost TCP (2) Férovost TCP Vylepšování implementace TCP • checksum offloading – jak při vysílání, tak při příjmu • zero copy – uživatelský prostor <-> jádro <-> karta – page flipping – Linux, FreeBSD, Solaris Povídání o současném dění kolem zajištěných protokolů pro přenosovou vrstvu na PSaA II.