Uvod OOO HCC TCP ooooooooooooooooooooooooo Závět OOO Hybrid congestion control for high-speed networks Martin Skala Fakulta informatiky Masarykovy univerzity 9. listopadu 2011 Martin Skala Hybrid congestion control for high-speed networks Uvod OOO HCC TCP ooooooooooooooooooooooooo Závět OOO Obsah O Úvod • Základní termíny • Průlet historií • Členění protokolů pro řízení zahlcení 0 HCC TCP • Související protokoly • Koncept • Architektura • Implementace • Nastavení testovací prostředí • Výsledky testování Martin Skala Hybrid congestion control for high-speed networks Uvod HCC TCP ooooooooooooooooooooooooo Závět ooo Základní termíny Základní termíny ► Vlastnosti vztahující se k přenosovým protokolům1 ► aggressiveness - využití dostupné linky (maximální zvýšení rychlosti odesílání během jednoho RTT [pkts/s]) *■ responsiveness - schopnost reagovat na zahlcení (počet RTT potřebných ke snížení rychlosti odesílání na polovinu při trvajícím zahlcení) ► fairness - férové rozdělení síťové kapacity mezi více proudů ► RTT-fairness - férové rozdělení síťové kapacity v rámci proudů s různými RTT *■ TCP-friendliness - férovost daného transportního protokolu vůči klasickému TCP robustness - odolnost vůči náhodným výpadkům ► convergence time - čas potřebný ke zkonvergování do férového stavu mezi existujícími proudy a nově začínajícím ^ 1 Zdroj: viz [2] a [3] Martin Skala Hybrid congestion control for high-speed networks Hrulet Reno Vegas New Reno I I I I I I I I I I I I I 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 CUBIC-TCP RUDP STCP BIC-TCP FAST Illinois Westwoocl XCP HSTCP HTCP VCP CTCP UDT EEFAST HCC H I I I I I I I I-1 I I 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 Zachycení vývoje vybraných TCP variant na časové ose Uvod HCC TCP Závěr oo« ooooooooooooooooooooooooo ooo Členění protokolů pro řízení zahlcení Členění protokolů pro řízení zahlcení ► router-based ► strategie zvolena na základě explicitní zpětné vazby z routerů ► přidání podpory do existujících routerů ve světě je nepraktické ► protokoly: XCP, VCP, .. ► end-to-end ► loss-based CC ► ztráta paketu jako indikátor zahlcení ► zvětšení okna po každém ACK, zmenšení při ztrátě paketu - protokoly: HSTCP, STCP, BIC, CUBIC, HTCP, .. *■ delay-based CC ► zpoždění ve frontách routerů / RTT jako indikátor zahlcení ► vytěžování front routerů ► protokoly: FAST, Vegas *■ loss-delay-based CC ► snaha o kombinaci předchozích přístupů ►• někdy jeden přístup primární a druhý jako fallback - protokoly: CTCP, Illinois, EEFAST, HCC Martin Skala Hybrid congestion control for high-speed networks Úvod HCC TCP Závěr °°° ooooooooooooooooooooooooo OOO Obsah O Úvod • Základní termíny • Průlet historií • Členění protokolů pro řízení zahlcení 0 HCC TCP • Související protokoly • Koncept • Architektura • Implementace • Nastavení testovací prostředí • Výsledky testování Martin Skala Hybrid congestion control for high-speed networks Uvod OOO HCC TCP »OOOOOOOOOOOOOOOOOOOOOOO0 Závět OOO Související protokoly Související protokoly Loss-based Mezi společné problémy patří oscilace mezi plným využitím kapacity sítě a pod ním, což zvyšuje ztrátovost paketů. HSTCP ► využití krokovacích funkcí pro zvětšování / zmenšování okna ► umožňuje rychlé využití volné kapacity ► Problém: velké problémy s RTT-fairness, rychlé zvětšování okna i v případě blížícího se zahlcení ► STCP ► hodnota pro zvětšení / zmenšení nastavována proporčně vzhledem k aktuálnímu oknu - Problém: viz HSTCP ► HTCP ► doba od posledního výpadku pro růstovou hodnotu ► při zahlcení použití adaptivní back-off strategie A ► Problém: rychlé zvětšování okna i v případě blížícího se \W Martin Skala Hybrid congestion control for high-speed networks Uvod OOO HCC TCP o«ooooooooooooooooooooooo Závět OOO Související protokoly Související protokoly II. ► BIC-TCP ► přibližování k refer. hodnotě metodou binárního vyhledávání - parametry Wmin, Wmax, ► v počáteční fázi roste okno lineárně a poté logaritmicky (M = w^-w^- M < Smax?M : Smax) *■ Problém: lepší než předchozí, ale má problémy s RTT-fairness Delay-based Společným problémem je provoz na zpětné cestě, jenž snižuje propustnost na cestě dopředně (tzv. reverse traffic problém). Nepříjemný je požadavek na velikost bufferů, který by měl být větší než celkové množství paketů aktuálně zpracovávaných na routerech. ► FAST TCP ► odvozen od TCP Vegas *■ udržuje obsazení front routerů na malé nenulové hodnotě ► umožňuje plné využití síťové kapacity ^ ► umožňuje dosáhnout vyšší průměrné propustnosti \^ *■ rychlá konvergence do rovnovážného stavu, RTT-fairness Martin Skala Hybrid congestion control for high-speed networks Uvod OOO HCC TCP oo»oooooooooooooooooooooo Závět OOO Související protokoly Související protokoly III. Loss-delay-based Podobně jako v předchozím případě je propustnost některých protokolů z této kategorie negativně ovlivněna provozem na zpětné cestě. Stále zůstává požadavek na velikost bufferů jako v předchozím případě. ► CTCP ► delay-based komponenta odvozená od TCP Vegas *■ zpočátku použití tradiční Slow-Start fáze ► indikátor zpoždění paketů použit ve fázi congestion avoidance ► TCP-Illinois ► indikátor ztráty paketů je primární, zpoždění paketů sekundární ► ztrátovost udává směr změny velikosti okna ► zpožďování udává velikost/tempo této změny ► konkávnost křivky velikosti okna dána parametry a,/3 *■ nehrozí-li zahlcení, pak a ^> /3; v opačném případě f3 ^> a *■ EEFAST / ► navržen pro odstranění vlivu provozu na zpětné cestě ► dynamicky mění okno vzhledem k jednocestnému zpoždění Martin Skala Hybrid congestion control for high-speed networks Uvod OOO HCC TCP ooo«ooooooooooooooooooooo Závět OOO Koncept Koncept Základní charakteristika HCC TCP spadá do kategorie loss-delay-based protokolů ► zpožďování jako primární indikátor, ztrátovost jako sekundární ► funguje dobře při provozu na zpětné cestě, měří pouze jednocestné zpoždění stejně jako EEFAST ► nevyžaduje explicitně větší velikost bufferů (díky sekundárnímu indikátoru) další vlastnosti ověřeny při testovacích měření Martin Skala Hybrid congestion control for high-speed networks •oooooo Z architektury znázorněné na obrázku 2 je patrné, že se protokol v podstatě skládá ze 3 komponent - komponenta odhadu na bázi zpoždění (delay-based estimation), komponenta odhadu na bázi ztrátovosti (loss-based estimation) a komponenta společné kontroly (joint control). Architektura HCC Značení a.-, - počet paketů v rovnovážném stavu ve frontách routerů Wj, «í-(t),Ai*i - velikost okna, resp. předpokl. velikost okna zdroje / v čase ř, resp. rozdíl mezi aktuální a předpokl. velikostí okna Df, d; - dopředně jednocestné resp. propagační zpoždění zdroje i baseDf - minimální doposud pozorované Df Qf, Qf - dopředně resp. zpětné zpoždění ve frontách zdroje /, Qf = Df - baseDf avgQf (t), avgDj(t) - průměrné hodnoty Qf(t) resp. RTT Uvod OOO HCC TCP ooooo«ooooooooooooooooooo Závět OOO Architektura Komponenty I. Komponenta delay-based estimation ► využívá mechanismů EEFAST pro odhad zahlcení v síti ► rozšíření o nové kontrolní postupy řídící velikost okna ► v rovnovážném stavu by mělo být ve frontách routerů a, paketů bez negativního efektu provozu na zpětné cestě velikost okna lze zapsat jako w,- = -gf D/ = ^ (Q( + Q- + d i) ► předpokládaná velikost okna v čase ŕ odpovídá ► v iniciální fázi obvykle Qf velmi malé a wf{t) naopak velmi vysoké (než wf[t)) ► s rostoucí wf{t) roste také D- =4> se wf{t) snižuje í^lf Martin Skala Hybrid congestion control for high-speed networks oo«oooo Pokud se vzdálenost mezi předpokl. a aktuální velikostí okna nachází v oblasti stable range (viz obr. 3), můžeme říct, že je plně využito dostupné kapacity sítě. Každý zdroj si spočítá předpokl. velikost okna vf(ř) = ivgQf(t) wgDi(t) Poté rozdíl Awi mezi přepodkl. a aktuální velikostí okna Aw,-(t) = wf(f) — wf(t). Pokud je Awi > 0, pak by se mělo aktuální okno zvětšit. V opačném případě by mělo dojít ke zmenšení, které povede k přiblížení se k přepodkl. oknu. Á ^ Window Size Approaching phase i "* \ Stable phase Anticipated window size ^--I i t / Current wjndow size Stable Range Změna velikosti okna na základě delay-based strategie Uvod OOO HCC TCP ooooooo«ooooooooooooooooo Závět OOO Architektura Komponenty III. Před změnou velikosti okna musí dojít ke kontrole, zda změna velikost o Awj není větší než lmax- |Aw,j > \max1 lmax ■ |Avi/fj. Příliš velké změny by mohly zapříčinit výkyvy, které by měly za následek degradaci výkonu protokolu. Z předešlých výzkumů v oblasti protokolu FAST TCP bylo zjištěno, že ideální hodnota lmax = lOLj. ► protokol aktualizuje velikost okna jednou za RTT ► pozvolné přibližování k wf{ť), velikost se mění pouze o Aw/,-/2 Martin Skala Hybrid congestion control for high-speed networks Uvod OOO HCC TCP oooooooo«oooooooooooooooo Závět OOO Architektura Komponenty IV. Komponenta loss-based estimation Delay-based algoritmy vyžadují ve frontách routerů určený počet paketů, aby mohly udržovat průměrnou propustnost okolo maximálního možné hodnoty. Proto by velikost bufferů na routerech měla být větší než tento určený počet paketů. V opačném případě může docházet k výrazným ztrátám paketů v síti. ► rychlé získání volné kapacity sítě a prodloužení doby mezi po sobě následujícími zahlceními díky změnám velikosti okna v prim. komponentě (lineární —> logaritmický růst - viz obr. 4) ► změna velikosti okna vzhledem k parametrům lmax a lm;n stejně jako v primární komponentě ► bere také pouze polovina vypočítané hodnoty, která by měla /*°"\ určovat změnu okna i vi^J Martin Skala Hybrid congestion control for high-speed networks Uvod OOO HCC TCP OOOOOOOOOO«OOOOOOOOOOOOO0 Závět OOO Architektura Komponenty VI. ► při detekci ztraceného paketu dojde k zaznamenání aktuální velikosti okna (loss-reference) a k nastavení okna na polovinu ► poté fáze zotavení, kde w-"ax = loss-reference, w™"1 = aktuální velikost okna a cílové zvětšení okna (w//ar) bude wfar = (wj713* - w["'n) /2 ► není-li po navýšení okna ve fázi zotavení detekována ztráta, nastaví se w™"1 na akt. velikost okna a celý proces se opakuje ► je-li detekována ztráta, dojde k zaznamenání aktuální velikosti okna na loss-reference a w-"ax Martin Skala Hybrid congestion control for high-speed networks Uvod OOO HCC TCP 00000000000*0000000000000 Závět OOO Implementace Implementace ► při startu protokolu se pro odhad zahlcení na dopředně cestě nastaví threshold hodnota mi_threshold ► pokud avgQ-(t) < mi-threshold, pak indikuje, že dopředně zpoždění ve frontách je nízké - lze použít schéma multiplikativního navýšení (Ml) ► v opačném případě se předá řízení zahlcení primární komponentě ► dále se nastaví loss-reference na svou maximální (implicitní) hodnotu (dokud není detekována ztráta) Martin Skala Hybrid congestion control for high-speed networks Variables: W Current window size; Previous window size; w,{t) Window size of source i. at time r; a. Packet numbers that should be maintained at routers for source i; mi_thresho!d Threshold value for forward congestion estimation. Startup ( ): Set ioss-reference to be a default maximum value; Start to calculate average queuing delay: avgQ^(t); Start to calculate average RTT: avgDf(f); If ovgQf(t) < mi_ttireshotd, then W=2Wo!d per RTT; If avgQf(t) > mLthreshold, then turn to delay-based congestion control function { ); I Delay-based congestion control function ( ): Estimate anticipated window size {delay-reference): w°(t) = «f avgom/avgQ((ty, Calculate the change for current window size: AWj(t) =wf(t)-wf(t); If Aw,-(t) > fmax, then Awt{t) = lmox; If Awtft) < —Imax, then Awj(t) - -Jmm; Update congestion window: W=Wgid+(AWf/2) per RTT; Upon detected loss packet: update loss-reference; back off to W=W/2; turn to loss-based congestion control function ( ); Loss-based congestion control function ( }: Calculate increment for current window size: (ufm-wj"'n)/2; Fmra, then wf* = !mai; Imin, then = Jmfn; Update congestion window: W = W0H+(wjar/2) per RTT; If W> loss-reference & no packet loss is detected, reset Joss-re/en?nce; turn to delay-based congestion control function ( ); Upon detected loss packet: update loss-reference; back off to W=W}2; If WJ If w\ Algoritmus - pseudokod simulace prostřednictvím The Network Simulator (ns-2) cílem porovnat a vyhodnotit vlastnosti HCC TCP s dalšími protokoly2 zvolena topologie na obr. 6, jedna sdílená 200 Mbps linka (d; = 20ms) routery Rl i R2 využívají FIFO fronty, velikost datových paketů 1000 bajtů parametrizované protokoly (FAST, HCC) implicitně a = 400,7 = 0.5 standardní doba měření každé simulace je 300 s 2 TCP Reno, TCP Vegas, HSTCP, STCP, HTCP, BIC-TCP, TCP-lllinois alf/ lená k testování FAST TCP HCC TCP oo«oooooooo bufferu 2 Průměrná propustnost 3 homogenních RTT (120 ms) prenosu Jain's fairness index (Fl), počet paralelních proudů n, průměrná prop, proudu / = x; HCC TCP ooooo»ooooo fficiency index (El) odpovídá součtu propustností všech paralelních proudů 175.96 [•y:\.oz 156.56 187.13 177.03 0.08 9.38 0.Q2 42.2S 12.43 22.45 99.54 03.S4 09.5G 99 A3 0.5085 0.5004 0.5532 0.5031 0.7517 0.5661 0.6248 96.75 '"11.24 8-1.6-1 6.09 99.00 0.62 73.75 23.15 90.11 9.44 79.19 20.26 90.33 00.73 99.02 90.90 09.55 0.5140 (1.5015 0.5329 0.5031 0.6309 0.5495 íl.fil 16 velikost bufreru 600 paketů Fl El 99.56 76.20 09. 35 03.74 02.97 0.5033 0.5001 0.5556 0.5017 0.5150 0.5332 0.5880 1S9.S7 190.35 130.19 109.13 99.94 2.8 1 0.93 9.79 0.31 61127 99.40 99.55 99.66 99.67 09.6G 99.64 99.46 09.55 00.49 0.514-1 0.5047 0.5514 0.5016 0.9147 1.0000 1.0000 1S9.55 193.17 1 fil .90 109.33 109.13 0.23 U.12 10.00 199.53 199.5/ 109.53 109.50 199.46 109.57 199.46 0.5012 0.5006 0.5526 0.5067 0.7201 1.0000 1.0000 ufferu 2000 paketů Výsledky měření indexů El a Fl zpětné cestě Uvod OOO HCC TCP ooooooooooooooooooooooooo Závěr OOO Obsah O Úvod • Základní termíny • Průlet historií • Členění protokolů pro řízení zahlcení 0 HCC TCP • Související protokoly • Koncept • Architektura • Implementace • Nastavení testovací prostředí • Výsledky testování Martin Skala Hybrid congestion control for high-speed networks Úvod HCC TCP Závěr ooooooooooooooooooooooooo •oo Shrnutí Shrnutí ► V případě, že primární delay-based algoritmus pracuje neefektivně (tj. jsou detekované ztráty), využívá HCC růstovou funkci založenou na měření ztrát, která zpočátku roste lineárně a ke konci logaritmicky. ► HCC dokáže velmi rychle a efektivně využít volnou kapacitu sítě, přičemž vždy dosahuje lepší průměrné propustnosti než ostatní testované high-speed TCP varianty s různou velikostí bufferů na routerech. ► Pracuje dobře v prostředích s homogenními i heterogenními RTT proudy. Může se ovšem chovat RTT-unfriendly v případě, že velikost bufferů je nízká (viz obr. 13b). ► Protokol se chová TCP-friendly (viz obr. 16), robustně (dosahuje dobrých výsledků v přítomnosti výrazného zpětnéhcf^^r| provozu, viz obr. 18b). Martin Skala Hybrid congestion control for high-speed networks Uvod OOO HCC TCP ooooooooooooooooooooooooo Závěr Reference Reference a užitečné odkazy Wenjun Xu et al.: Hybrid congestion control for high-speed networks, 2011, http://dx.doi.org/10.1016/j.jnca.2011.03.025>. Holub P.: Výlet za hranice TCP: protokoly pro sítě s velkým součinem latence a šířky pásma, 2006, . Floyd S.: Metrics for the Evaluation of Congestion Control Mechanisms, 2008, . Martin Skala Hybrid congestion control for high-speed networks Úvod HCC TCP ooooooooooooooooooooooooo Závěr oo« Dotazy Dotazy Nějaké dotazy? Martin Skala Hybrid congestion control for high-speed networks Úvod HCC TCP ooooooooooooooooooooooooo Závěr oo« Dotazy Dotazy Nějaké dotazy? Děkuji za Vaši pozornost Martin Skala Hybrid congestion control for high-speed networks