Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Ne-TCP Závěr Literatura OOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOCSaESÍXEEm oooo oo ooo Výlet za hranice TCP: protokoly pro sítě s velkým součinem latence a šířky pásma Petr Holub hopetOics.muni.cz PSaAPII 2006-03-23 □ vysílací okno 83.333 paketů ==> ztráta jednoho paketu za 1:36 hodiny • Jak dosáhnout lepšího využití sítě? • Jak zajistit rozumnou koexistenci s tradičním TCP? • Jak zajistit postupné nasazování nového protokolu? □ v d): odesílač přijímač síť □ kernel <-> síťová karta • page flipping - přesun user-land <-> kernel • podpora např. pro sendfileO • implementace pro Linux, FreeBSD, Solaris, ... □ -O O, O 18/57 Vylepšení TCP Závěr oooooooooooooooo» Ladění implementace TCP • WeblOO [4, 5] • instrumentace TCP/IP stacku pro Linux - TCP Kernel Instrumentation Set (TCP-KIS) • více jak 125 „táhel" • informace jsou dostupné přes /proč • knihovna pro přístup k instrumentaci • klientské nástroje v uživatelském prostoru (command-line, GUI) • monitoring • ladění parametrů podpora pro auto-tuning □ -O O, O 19/57 Rozšíření TCP OOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOCSaESIGÍSD oooo oo ooo Přehled přednášky Tradiční TCP a jeho problémy Vylepšení TCP Víceproudové TCP WeblOO Konzervativní rozšíření TCP GridDT Scalable TCP, High-Speed TCP, H-TCP, BIC-TCP Rozšíření TCP s podporou IP QuickStart, E-TCP, FAST Přístupy odlišné od TCP tsunami XCP SCTP, DCCP, STP, Reliable UDP, XTP Závěrečné poznámky Literatura ^„^ □ -O O, O 20/5 Rozšíření TCP Závěr • oo oo oo o o o o o o o asxsssxsm) GridDT • sbírka ad-hoc modifikací :( • korekce sstresh • rychlejší slowstart • modifikace AIMD řízení zahlcení • cwnd = cwnd + a ... pro úspěšné RTT cwnd = b cwnd ... pro výpadek • modifikace pouze na straně odesílače □ -0 0,0 21/57 Rozšíření TCP Závěr o »o oo oo o o o o o o o asxsssxsm) GridDT - férovost 100 80 60 40 20 0 0 20 40 60 80 100 □ -T) Q, O 22/57 Tradiční TCP Vylepšení TCP ooooooooooooooooo Rozšíření TCP o o« oo oo o o o o o o o asxsssxsm) Ne-TCP oooo Závěr oo Literatura ooo GridDT - příklad | Host#1 l-iGE IHost*2 hrSÉ 1GE ŕít\ POS 2.5 Gb/s Starlight (CHI) í^10GEÍŤt\ POS 10 Sb/s GbE Switch -(R)—| Host #2 | !&> | HostSI | Sunnyvale TCP Reno performance (see slide #8): First stream GVA <-> Sunnyvale : RTT =181 ms ; Avg. throughput over a period of 7000s = 202 Mb/s Second stream GVA<->CHI : RTT = 117 ms; Avg. throughput over a period of 7000s =514 Mb/s Links utilization 71,6% Grid DT tuning in order to improve fairness between two TCP streams with different RTT: First stream GVA <-> Sunnyvale : RTT = 181 ms, Additive increment = A = 7 ; Average throughput = 330 Mb/s Second stream GVA<->CHI : RTT =117 ms, Additive increment = B = 3 ; Average throughput = 388 Mb/s Links utilization 71.8% Throughput of two streams with different RTT sharing a 1Gbps bottleneck -A=7 ; RTT=181ms —Average over the life of the connection RTT=181ms -B=3 ; RTT=117ms 21 Rozšíření TCP Závěr o oo »o oo o o o o o o o asxsssxsm) Scalable TCP • navrhl Tom Kelly [1] • řízení zahlcení již není AIMD: • cwnd = cwnd + 0,01 cwnd ... pro úspěšné RTT cwnd = cwnd + 0,01 ... per-ACK • cwnd = 0,875 cwnd ... pro výpadek =^- Multiplicative Increase Multiplicative Decrease • pro malé velikosti okna a/nebo větší množství ztrát v síti se přepíná od AIMD režimu □ ^) Q, O 24/57 84 Tradiční TCP Vylepšení TCP ooooooooooooooooo Rozšíření TCP o oo o« oo o o o o o o o osxsssxsm) Ne-TCP oooo Závěr oo Literatura ooo Scalable TCP Rate (pkteRTT) 2 j ľ / / 1 1 1 1 1 2 2 Rate -logjoars) (pktiRTT) lOQil^BOl) lÁJÁÁJÁJÁJ JÁ \'" 0875c .....JL/1/ / iYV\£-UY\ /.Y Li Rate (pktsfRTT) r---------•< c ! 2 □ -T)<\(y 25/57 Tradiční TCP Vylepšení TCP ooooooooooooooooo Rozšíření TCP o oo oo »o o o o o o o o osxsssxsm) Ne-TCP oooo Závěr oo Literatura ooo Scalable TCP - férovost dva soutěžící Scalable TCP proudy, přepnutí na Scalable řízení @ >30Mb/s, dvojnásobek kroků oproti předchozím simulacím 100 80 60 40 20 ......./ é ——:--------1--------:--------1--------'■--------i--------:-------4-—:—— 20 40 60 80 100 □ -T)<\(y Tradiční TCP Vylepšení TCP ooooooooooooooooo Rozšíření TCP O OO OO O« O O O O O O O OmBGHBOD Ne-TCP oooo Závěr OO Literatura ooo Scalable TCP - férovost soutěžící Scalable TCP a tradiční TCP proudy, přepnutí na Scalable řízení @ >30Mb/s, dvojnásobek kroků 100 80 60 40 20 A//, ——:---------í---------:---------í---------'■---------1---------:--------4-—:—— 20 40 60 80 100 □ -T)<\(y Tradiční TCP Vylepšení TCP ooooooooooooooooo Rozšíření TCP o oo oo oo • o o o o o o osxsssxsm) Ne-TCP oooo Závěr oo Literatura ooo Scalable TCP - response curve iz a* ■ji o "O 1000 100 Standard TCP Scalable TCP 0.0001 0.001 Loss rale □ -O O, O 28/57 Rozšíření TCP Závěr ooooooooÄOOoooceesíXEEm High-Speed TCP (HSTCP) • Sally Floyd, RFC3649, [2] • řízení zahlcení AIMD/MIMD: • cwnd = cwnd + a(cwnd) ... pro úspěšné RTT i i . a(cwnd) cwnd = cwnd + ^/ ... per-ACK • cwnd = b(cwnd) cwnd ... pro výpadek • emuluje chování tradičního TCP pro malé velikosti okna a/nebo větší množství ztrát v síti □ ^) Q, O 29/57 Tradiční TCP Vylepšení TCP ooooooooooooooooo Rozšíření TCP o oo oo oo o o • o o o o osxsssxsm) Ne-TCP oooo Závěr oo Literatura ooo High-Speed TCP (HSTCP) navržená parametrizace MIMD: -0,4(log(o/i/nc/) - 3,64) b(cwnd) a(cwnd) 7,69 j2i 2cwnd b(cwnd) 12,8(2 - b^cwnd^w1'2 0,5 [KIT] □ -T) O, O 30/57 Rozšíření TCP Závěr oooooooooosoooceesíXEEm High-Speed TCP (HSTCP) • možná parametrizace ekvivalentní Scalable TCP: Linear HSTCP • porovnání s víceproudovým TCP N(cwnd) « 0,23o/i/nc/0'4 • ani Scalable TCP ani HSTCP neřeší nijak sofistikovaně fázi slow-start □ -0 0,0 31/57 Tradiční TCP Vylepšení TCP ooooooooooooooooo Rozšíření TCP o oo oo oo o o o o • o o asxsssxsm) Ne-TCP oooo Závěr oo Literatura ooo HSTCP - response curve Regular TCP Highspeed TCP Scalable TCP 1 le-iÉ le-89 le-09 le-07 le-ee le-05 0.0001 0.001 Loss Rate P □ -OQ.O Rozšíření TCP Závěr o oo oo oo o o o o o • o asxsssxsm) H-TCP • A ... čas uplynulý od minulého výpadku • přírůstek cwnd závisí na A jakožto indikaci součinu šířka pásma - zpoždění a také na RTT, aby se kompenzovala neférovost mezi toky s různým RTT • AL ... pro A < AL se používá TCP nárůst • Aß ... hranice změny dostupné šířky pásma, nad níž se používá TCP pokles (pro velké změny dostupné šířky pásma se používá TCP pokles 0,5) • Tmjn, Tmax ... minimální resp. maximální změřené RTT • B(k + 1) ... měření maximální propustnosti za poslední interval bez výpadku □ -O O, O 33/57 Tradiční TCP Vylepšení TCP ooooooooooooooooo Rozšíření TCP o oo oo oo o o o o o o • asxsssxsm) Ne-TCP oooo Závěr oo Literatura ooo H-TCP cwnd = cwnd + ——'*} ' cwnd ...per-AC K • cwnd = b(B) cwnd ... pro výpadek a(A) b(B) max{a'(A)Tmin;l} 0,5 mjn ji™ Q gj L ' max J A At B(k+1)-B(k) B(k) > A< v opačném případě a'(A) = 1 + 10(A - AL) + 0,25(A - A^)2 ... kvadratická přírůstková funkce □ -O O, O 34/57 Rozšíření TCP Závěr o oo oo oo o o o o o o o msxsssxsm) BIC-TCP • K aktualizaci cwnd používá binární prohledávací algoritmus [3] • 4 fáze fungování (1) reakce na výpadek (2) aditivní nárůst (3) binární prohledávání (4) hledání maxima □ -O O, O 35/57 Rozšíření TCP OOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOCfflESIGiSD oooo oo BIC-TCP (1) Výpadek • redukce okna • původní okno —>■ Wmax • redukované okno —>■ Wmin • ==> protože k výpadku došlo při cwnd < Wmax, budeme rovnovážné cwnd hledat v intervalu (Wmin;Wmax) (2) Aditivní nárůst • začít hledání od cwnd = —aÚĽ\—— by mohlo být pro síť příliš náročné pokud m^ aditivním nárůstem o konstantu cwnd = Wmin + Sn • pokud w™"+w™x > wmin + Smax, postupujeme □ ^) Q, O 36/57 Rozšíření TCP ooooooooooooooooo oooooooooooooocsaaßiaiSD oooo oo BIC-TCP (3) Binární hledání . cwnd = w-+w- 2 • pokud předchozí bod (i aditivní nárůst) prošel bez výpadku, Wmm = cwnd, v opačném případě Wmax = cwnd hledání pokračuje, pokud změna cwnd není menší než konstanta Sm/n, kdy se nastaví cwnd = Wmax výsledkem bodů (2) a (3) je obvykle lineární růst (aditivní nárůst), který se mění na logaritmický (binární hledání) □ ^) Q, O 37/57 Rozšíření TCP Závěr o oo oo oo o o o o o o o asxsmms) BIC-TCP (4) Hledání maxima • inverzní proces k bodům (3) a (2) • nejdříve inverzní binární hledání, dokud nárůst není větší jakO J max • lineární nárůst o velký inkrement po překročení předchozího bodu • očekávané výhody • „přáteskost" vůči TCP • během plata (3) mají TCP toky šanci „dorůst" • AIMD chování (byť rychlejší) ve fázích (2) a (4) • stabilnější velikost okna => lepší využití sítě • většinu času by BIC-TCP mělo trávit v platu (3) □ -O O, O 38/57 Rozšíření TCP OOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOCCGßiaKD oooo oo BIC-TCP Explicitní vyjádření chování cwnd . ß = 2, M/i ~ W™ + W™* r __ wi — cwnd O — B j j i a(S,cwnd) cwnd = cwnd H———^-J- cwna W\ = < 2 per-ACK (l+b)cwnd cwnd < m cwnd cwnd > w\ 1/1/2 = cwnd cwnd = b cwnd ... pro výpadek □ -O O, O 39/57 Rozšíření TCP OOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOCCCSIGÍ» oooo oo BIC-TCP Explicitní vyjádření chování cwnd ^ (6 < l,cwnd < w\) nebo (w\ < cwnd < w\ + B) ö 1 < ö < Smax,cwnd < w\ ^l B < cwnd - w/i < Smax(B - 1) Smax jinak (Explicitní vyjádření je spíše pro zajímavost, není nutno si pamatovat. Důležité je znát prinicipl) □ -O Q^ O 40/57 Rozšíření TCP s IP Závěr O OO OO OO O O O O O O O QKBB8X13® Quickstart (QS)/Limited Slowstart existuje silné podezření, že slow-start fáze se nedá vylepšit bez interakce s níže položenými síťovými vrstvami • návrh: 4-byte option v IP hlavičce, který zahrnuje pole QS TTL a Initial Rate • odesílač, který chce použít QS, nastaví QS TTL na náhodnou hodnotu a Initial Rate na požadovanou rychlost, kterou chce začít vysílat, a pošle SYN paket □ -0 0,0 41/57 Rozšíření TCP s IP Závěr o oo oo oo o o o o o o o asms®®® Quickstart (QS)/Limited Slowstart • všechny routery po cestě, které podporují QS, sníží QS TTL o jedničku a sníží Initial Rate, pokud je to potřeba • Přijímač pošle pole QS TTL a Initial Rate v SYN/ACK paketu odesílací • Odesílač ví, jestli všechny směrovače po cestě podporují QS (porovnáním QS TTL a TTL) • Odesílač si nastaví příslušné cwnd a začne používat svůj mechanismus řízení zahlcení (např. AIMD) • Vyžaduje změny v IP vrstvě! :-( □ -O O, O 42/57 Rozšíření TCP s IP Závěr o oo oo oo o o o o o o o asxsxtis® E-TCP • Early Congestion Notification (ECN) • součást Advanced Queue Management (AQM) • bit, který nastavují routery, když se blíží linky/buffery/fronty zahlcení • ECN příznak musí být odzrcadlen přijímačem • na ECN bit má TCP zareagovat stejně jako na výpadek • problém s tím, aby správci routerů konfigurovali AQM/ECN :-( □ -O O, O 43/57 Rozšíření TCP s IP Závěr o oo oo oo o o o o o o o asxEssm® E-TCP E-TCP • navrhuje odzrcadlit ECN bit jen jednou (poprvé) • zamrzne cwnd když dorazí od přijímače ACK s nastaveným ECN bitem • vyžaduje (umělé) zavedení malých náhodných výpadků do sítě, aby se zajistil multiplikativní pokles kvůli férovému chování v čase • vyžaduje změnu chování k ECN bitu na přijímačích :-( □ -O Q^ O 44/57 Tradiční TCP Vylepšení TCP ooooooooooooooooo Rozšíření TCP s IP o oo oo oo o o o o o o o asxsssxsm Ne-TCP oooo Závěr OO Literatura ooo FAST Fast AQM Scalable TCP (FAST) [5] používá end-to-end delay, ECN a ztráty paketů pro detekci/vyhýbání se zahlcení T mm, T' ... minimální a průměrný pozorovaný RTT Tq ... odhad zpoždění front u RTT %(B) ... (8, 20, 200) pro bw (< 10 Mb/s, 10- 100 Mb/s, > 100 Mb/s), lze měnit přes sysctlO parametr návrhu ;-) • 7 ■■ ACK: cwnd = min J2x cwnd,(l — ^)cwnd + 7 výpadek: cwnd = 0,5 cwnd r, ff*cwnd + fa(B,Tq) fa(B,Tq) a x cwnd Tq = 0 Tq^0 □ ^) Q, O 45/57 Ne-TCP OOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOCSaESIGÍSD oooo oo ooo Přehled přednášky Tradiční TCP a jeho problémy Vylepšení TCP Víceproudové TCP WeblOO Konzervativní rozšíření TCP GridDT Scalable TCP, High-Speed TCP, H-TCP, BIC-TCP Rozšíření TCP s podporou IP QuickStart, E-TCP, FAST Přístupy odlišné od TCP tsunami XCP SCTP, DCCP, STP, Reliable UDP, XTP Závěrečné poznámky Literatura ^„^ □ -O O, O 46/57 Ne-TCP •ooo tsunami • TCP spojení pro out-of-band řídící kanál • vyjednávání parametrů přenosu • požadavky na retransmisi - používá NACKy místo ACKů • vyjednávání ukončení přenosu • UDP kanál pro přenos dat • řízení zahlcení MIMD • vysoce konfigurovatelné • parametry MIMD, nastavení prahu chyb, maximální velikost fronty pro retransmisi, interval zasílání požadavků na retransmisi □ -O O, O 47/57 Tradiční TCP Vylepšení TCP ooooooooooooooooo Rozšíření TCP Rozšíření TCP s IP o oo oo oo o o o o o o o asxsssxsm) Ne-TCP o»oo Závěr OO Literatura ooo XCP zpětná vazba od směrovačů per paket Réu Round Trip Time Cono Congestion Window Feedback = + 0.1 packet Congestion Header □ -O0>0 48/57 Tradiční TCP Vylepšení TCP ooooooooooooooooo Rozšíření TCP Rozšíření TCP s IP o oo oo oo o o o o o o o asxsssxsm) Ne-TCP o»oo Závěr OO Literatura ooo XCP zpětná vazba od směrovačů per paket Congestion Window Feedback = - 0.3 packet □ -00*0 49/57 Ne-TCP OOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOCSaESÍXEEm otoo oo XCP • zpětná vazba od směrovačů per paket Congestion Window = Congestion Window + Feedback □ -T) Q, O 50/57 Ne-TCP oo«o Jiné přístupy • SCTP • víceproudový, multi-homed transport • http://www.sctp.org/ • DCCP • nezajištěný protokol (UDP) s řízením zahlcení kompatibilním s TCP • http://www.ietf.org/html.charters/ dccp-charter.html • http://www.icir.org/kohler/dcp/ □ -0 0,0 51/57 25 Ne-TCP ooo» Jiné přístupy • STP • založený na CTS/RTS • jednoduchý protokol pro snadnou implementaci v HW • bez sofistikovaného řízení zahlcení • http://lwn.net/2001/features/0LS/pdf/pdf/ stlinux.pdf • Reliable UDP • zajišťuje spolehlivé, in-order doručení (do maximálního počtu opakování retransmise) • RFC908 a RFC1151 • původně vzniklo kvůli IP telefonii • konfigurace parametrů spojení per-spojení • http://www.j avvin.com/protocolRUDP.html • XTP (Xpress Transfer Protocol), ... □ -O O, O 52/57 Závěr • O Závěrečné poznámky • Současný stav • víceproudové TCP se intenzivně používá (např. Gridové aplikace) • hledání cesty, jak bezpečně (zpětně kompatibilně) zajistit vývoj/nasazení post-TCP protokolů • používání agresivních protokolů na privátních/dedikovaných sítích a okruzích (např. A-sítě CzechLight/CESNET2, SurfNet, CaNET*4, ...) □ -O O, O 53/57 Závěr O« Závěrečné poznámky • Interakce s L3 (IP) • Interakce se linkovou vrstvou • proměnné zpoždění a propustnost u bezdrátových sítí • optical burst switching • Specifické per-flow stavy ve směrovacích • např. per-flow nastavení generovaných výpadků (—> E-TCP) • může pomoci krátkým tokům s vysokými přenosovými nároky (makro-bursty) • problém se škálovatelností a náklady :-( □ -O O, O 54/57 Literatura OOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOCSaESÍXSSD oooo oo »oo Literatura I__| Jacobson V. "Congestion Avoidance and Control", Proceedings of ACM SIGCOMM'88 (Standford, CA, Aug. 1988), pp. 314-329. ftp://ftp.ee.lbl.gov/papers/congavoid.ps.Z Q Allman M., Paxson V., Stevens W. "TCP Congestion Control", RFC2581, Apr. 1999. http://www.rfc-editor.org/rfc/rfc2581.txt |__| Brakmo L, Peterson L. "TCP Vegas: End to End Congestion Avoidance on a Global Internet", IEEE Journal of Selected Areas in Communication, Vol. 13, No. 8, pp. 1465-1480, Oct. 1995. ftp://ftp.cs.arizona.edu/xkernel/Papers/j sac.ps |__| http://www.weblOO.org |__| Hacker T. J., Athey B. D., Sommerfield J. "Experiences Using WeblOO for End-To-End Network Performance Tuning" http://www.weblOO.org/docs/ExperiencesUsingWeblOOforHostTuning.pdf □ ^) Q, O 55/57 Literatura OOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOCSaESÍXSSD oooo oo o«o Literatura I__| Kelly T. "Scalable TCP: Improving Performance in Highspeed Wide Area Networks", PFLDnet2003, http://datatag.web.cern.ch/datatag/pfldnet2003/papers/kelly.pdf, http://wwwlce.eng.cam.ac.uk/~ctk21/scalable/ | 1 Floyd S. "HighSpeed TCP for Large Congestion Windows", 2003, http: //www.potaroo.net/ietf/all-ids/dr aft-floyd-tcp-highspeed-03.txt |__| BIC-TCP, http://www.csc.ncsu.edu/faculty/rhee/export/bitcp/ Hi Floyd S., Allman M., Jain A., Sarolahti P. "Quick-Start for TCP and IP", 2006, http: //www.ietf.org/internet-drafts/draft-ietf-tsvwg-quickstart-02.txt li Jin C, Wei D., Low S. H., Buhrmaster G., Bunn J., Choe D. H., Cottrell R. L. A., Doyle J. C, Newman H., Paganini F., Ravot S., Singh S. "FAST - Fast AQM Scalable TCP." http://netlab.caltech.edu/FAST/ http://netlab.caltech.edu/pub/papers/FAST-infocom2004.pdf |__| tsunami, http://www.anml.iu.edu/anmlresearch.html □ ^) Q, O 56/57 Závěr Literatura oo» Další studijní materiály • Workshopy PFLDnet 2003-2006 • http://datatag.web.cern.ch/datatag/ pfldnet2003/program.html http://www-didc.lbl.gov/PFLDnet2004/ • http://www.ens-lyon.fr/LIP/RESO/pfldnet2005/ • http://www.hpcc.jp/pfldnet2006/ • Strany s příspěvky prof. Sally Floyd • http://www.icir.org/floyd/papers.html • RFC3426 - "General Architectural and Policy Considerations" http: //www.hamilton.ie/net/eval/results_HI2005.pdf □ -O O, O 57/57