1/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Výlet za hranice TCP: protokoly pro sítě
s velkým součinem latence a šířky pásma
Petr Holub
hopet@ics.muni.cz
SitSem
2011–10–12
2/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Přehled přednášky
Tradiční TCP a jeho problémy
Vylepšení TCP
Víceproudové TCP
Web100
Konzervativní rozšíření TCP
GridDT
Scalable TCP, High-Speed TCP, H-TCP, BIC-TCP
Rozšíření TCP s podporou IP
QuickStart, E-TCP, FAST
Implementace v OS
Přístupy odlišné od TCP
tsunami
RBUDP
XCP
SCTP, DCCP, STP, Reliable UDP, XTP
Závěrečné poznámky
3/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Protokoly pro zajištěný přenos dat
• Zajištění spolehlivosti přenosu
• retransmise ztracených dat
• vypomoci může FEC
• Ochrana před zahlcením
• vysílače, sítě, přijímače
• Hodnocení chování
• agresivita – využití dostupné kapacity
• responsivita – schopnost zotavení se po výpadku
• férovost – získání férového podílu na síťové kapacitě při
více účastnících
4/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Problém
• Síťové spoje s vysokou kapacitou a vysokou latencí
• iGrid 2005: San Diego ↔ Brno, RTT = 205 ms
• SC|05: Seattle ↔ Brno, RTT = 174 ms
• Tradiční TCP není připraveno pro takové prostředí
• 10 Gb/s, RTT = 100 ms, 1500B MTU
=⇒ 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?
5/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Tradiční TCP
• řízení toku (flow control) vs. řízení zahlcení (congestion
control)
bez řízení:
odesílač síť přijímač
řízení toku (rwnd):
odesílač síť přijímač
řízení zahlcení (cwnd):
odesílač síť přijímač
6/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Tradiční TCP
• Řízení toku
• explicitní zpětná vazba od příjemce pomocí rwnd
• deterministické
• Řízení zahlcení
• přibližný odhad pomocí odesílatelem určovaného cwnd
• Finální výslední výstupní okno ownd
ownd = min{rwnd,cwnd}
Použitá šířka pásma bw je pak
bw =
8 · ownd · MTU
RTT
(1)
7/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Tradiční TCP – Tahoe a Reno
• řízení zahlcení
• tradičně založeno na přístupu AIMD – Additive Increase
Multiplicative Decrease
• Tahoe [1]
• cwnd = cwnd + MSS
...za každý RTT bez výpadku nad hranicí sstresh
• sstresh = 0,5cwnd
cwnd = MSS
...pro každý výpadek
• Reno [2] přidává
• fast retransmission (rychlé přeposlání) – ztráta indikovaná
třemi po sobě jdoucími identickými ACKy
• fast recovery (rychlá obnova) – zrušení slow-start fáze
sstresh = cwnd = 0,5cwnd
8/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Tradiční TCP – Tahoe
0 10 20 30 40 50
čas [RTT]
0
5
10
15
20
25
30
[MSS]
cwnd sstresh
9/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Tradiční TCP – Reno
0 10 20 30 40 50
čas [RTT]
0
5
10
15
20
25
30
[MSS]
cwnd sstresh
10/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
TCP Vegas
• Koncept řízení zahlcení Vegas [3]
• při zahlcení sítě se začíná prodlužovat RTT
• monitoring RTT v průběhu spojení
• lineární zmenšování okna jako reakce na prodlužování
RTT
• Možnost měření dostupného pásma měřením
mezipaketové disperze (inter-packet spacing/dispersion)
11/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Tradiční TCP
• Reakce na ztrátu dat – přeposlání
• Tahoe: celé současné okno ownd
• Reno: jeden segment v režimu Fast Retransmission
• NewReno: více segmentů v režimu Fast Retransmission
• Selective Acknowledgement (SACK): pouze ztracené
pakety
• Základní otázka:
Jak dosáhnout za realistických podmínek dostatečně velké
cwnd na síti s velkým součinem kapacity a RTT?
...a jak přitom neznemožnit přístup k síťové kapacitě pro
,,běžné‘‘ uživatele?
12/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Tradiční TCP – Response Function
• Response Function vyjadřuje vztah mezi bw a
rovnovážnou frekvencí výpadků paketů p (steady-state
packet loss rate)
• ownd ≈ 1,2√
p
• dosazením z (1) bw ≈ 9,6 MSS
RTT
√
p
• Resposivnost tradičního TCP
• za předpokladu, že k výpadku došlo když
cwnd = bw · RTT
=
bw RTT2
2MSS
13/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Tradiční TCP – ResponsivnostTraditional TCP responsivness
TCP responsiveness
0
2000
4000
6000
8000
10000
12000
14000
16000
18000
0 50 100 150 200
RTT (ms)
Time(s)
C= 622 Mbit/s
C= 2.5 Gbit/s
C= 10 Gbit/s
14/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Tradiční TCP – Férovost
• Férovost v rovnovážném stavu
• Posuzování férovosti
• pro proudy s různou RTT
• pro proudy s různou MTU
• Podstatná je také rychlost konvergence do
rovnovážného stavu!
15/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Tradiční TCP – Férovost
• cwnd += MSS, cwnd ∗= 0,5
0
0
20
20
40
40
60
60
80
80
100
100
16/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Tradiční TCP – Férovost
• cwnd += MSS, cwnd ∗= 0,83
0
0
20
20
40
40
60
60
80
80
100
100
17/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Přehled přednášky
Tradiční TCP a jeho problémy
Vylepšení TCP
Víceproudové TCP
Web100
Konzervativní rozšíření TCP
GridDT
Scalable TCP, High-Speed TCP, H-TCP, BIC-TCP
Rozšíření TCP s podporou IP
QuickStart, E-TCP, FAST
Implementace v OS
Přístupy odlišné od TCP
tsunami
RBUDP
XCP
SCTP, DCCP, STP, Reliable UDP, XTP
Závěrečné poznámky
18/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Víceproudové TCP
• Zlepšuje chování TCP prakticky pouze v případě, že
nastávají izolované výpadky paketů
• Výpadek více paketů obvykle ovlivní více proudů
• Často dostupné díky snadné implementaci
• bbftp, GridFTP, Internet Backplane Protocol, ...
• Nevýhody:
• komplikovanější než TCP (obvykle více vláken)
• nastartování je zrychleno nanejvýš lineárně
• synchronní přetěžování front a vyrovnávacích pamětí na
směrovačích
19/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Ladění implementace TCP
• Spolupráce s HW
• Rx/Tx TCP Checksum Offloading
• běžně dostupné (ale někdy obsahuje chyby)
• Zero copy
• přístup k síti obvykle zahrnuje několik kopií dat:
user-land ↔ kernel ↔ síťová karta
• page flipping – přesun user-land ↔ kernel
• podpora např. pro sendfile()
• implementace pro Linux, FreeBSD, Solaris, ...
20/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Ladění implementace TCP
• Web100 [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 /proc
• 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
21/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Přehled přednášky
Tradiční TCP a jeho problémy
Vylepšení TCP
Víceproudové TCP
Web100
Konzervativní rozšíření TCP
GridDT
Scalable TCP, High-Speed TCP, H-TCP, BIC-TCP
Rozšíření TCP s podporou IP
QuickStart, E-TCP, FAST
Implementace v OS
Přístupy odlišné od TCP
tsunami
RBUDP
XCP
SCTP, DCCP, STP, Reliable UDP, XTP
Závěrečné poznámky
22/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
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
23/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
GridDT – férovost
0
0
20
20
40
40
60
60
80
80
100
100
24/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
GridDT – příklad
PSaAP II
2004-03-19
24/52
GridDT example
SunnyvaleSunnyvale
Starlight (CHI)Starlight (CHI)
CERN (GVA)CERN (GVA)
RR RRGbEGbE
SwitchSwitch
POS 2.5POS 2.5 Gb/sGb/s1 GE1 GE
1 GE1 GE
Host #2Host #2
Host #1Host #1
Host #2Host #2
1 GE1 GE
1 GE1 GE
BottleneckBottleneck
RRPOS 10POS 10 Gb/sGb/s
RR
10GE10GE
Host #1Host #1
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
0
100
200
300
400
500
600
700
800
900
1000
0 1000 2000 3000 4000 5000 6000
Time (s)
Throughput(Mbps)
A=7 ; RTT=181ms
Average over the life of the
connection RTT=181ms
B=3 ; RTT=117ms
Average over the life of the
connection RTT=117ms
25/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
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
(MIMD)
• pro malé velikosti okna a/nebo větší množství ztrát v síti
se přepíná od AIMD režimu
26/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Scalable TCP
PSaAP II
2004-03-19
26/52
Scalable TCP (2)
27/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
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
0
0
20
20
40
40
60
60
80
80
100
100
28/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Scalable TCP – férovost
soutěžící Scalable TCP a tradiční TCP proudy, přepnutí na
Scalable řízení @ >30Mb/s, dvojnásobek kroků
0
0
20
20
40
40
60
60
80
80
100
100
29/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Scalable TCP – response curve
PSaAP II
2004-03-19
28/52
Scalable TCP - response curve
30/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
High-Speed TCP (HSTCP)
• Sally Floyd, RFC3649, [2]
• řízení zahlcení AIMD/MIMD:
• cwnd = cwnd + a(cwnd)
...pro úspěšné RTT
cwnd = cwnd + a(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
31/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
High-Speed TCP (HSTCP)
• navržená parametrizace MIMD:
b(cwnd) =
−0,4(log(cwnd) − 3,64)
7,69
+ 0,5
a(cwnd) =
2cwnd2
b(cwnd)
12,8(2 − b(cwnd))w1,2
200 400 600 800 1000 1200 1400 1600 1800 2000
čas [RTT]
10000
20000
30000
40000
50000
60000
70000
80000
cwnd[MSS]
32/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
High-Speed TCP (HSTCP)
• možná parametrizace ekvivalentní Scalable TCP: Linear
HSTCP
• porovnání s víceproudovým TCP
N(cwnd) ≈ 0,23cwnd0,4
• ani Scalable TCP ani HSTCP neřeší nijak sofistikovaně fázi
slow-start
33/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
HSTCP – response curveHSTCP (4)
34/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
H-TCP
• ∆ ... čas uplynulý od minulého výpadku
• přírůstek cwnd závisí na ∆ jakožto indikaci ( šířka pásma
× zpoždění ) a také na RTT, aby se kompenzovala
neférovost mezi toky s různým RTT
• ∆L ... pro ∆ ≤ ∆L se používá TCP nárůst
• ∆B ... 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)
• Tmin, Tmax ... minimální resp. maximální změřené RTT
• B(k + 1) ... měření maximální propustnosti za poslední
interval bez výpadku
35/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
H-TCP
• cwnd = cwnd + 2(1−β) a(∆)
cwnd
...per-ACK
• cwnd = b(B) cwnd
...pro výpadek
a(∆) =
1
max{a (∆)Tmin; 1}
∆ ≤ ∆L
∆ > ∆L
b(B) =
0,5
min{ Tmin
Tmax
; 0,8}
B(k+1)−B(k)
B(k)
> ∆B
v opačném případě
a (∆) = 1 + 10(∆ − ∆L) + 0,25(∆ − ∆L)2
...kvadratická přírůstková funkce
36/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
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
aditivní nárůst binární hledání hledání maxima
> Smax
37/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
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 = Wmin+Wmax
2 by mohlo být pro síť
příliš náročné
• pokud Wmin+Wmax
2 > Wmin + Smax, postupujeme aditivním
nárůstem o konstantu cwnd = Wmin + Smax
38/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
BIC-TCP
(3) Binární hledání
• cwnd = Wmin+Wmax
2
• pokud předchozí bod (i aditivní nárůst) prošel bez
výpadku, Wmin = cwnd, v opačném případě
Wmax = cwnd
• hledání pokračuje, pokud změna cwnd není menší než
konstanta Smin, 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 logaritmícký (binární hledání)
39/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
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 Smax
• lineární nárůst o velký inkrement po překročení
předchozího bodu
• očekáváné 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)
40/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
BIC-TCP versus CUBIC
• BIC-TCP v. 2.0 se označuje jako CUBIC
A. BIC Window Growth Function
Before delving into CUBIC, let us examine the features of
BIC. The main feature of BIC is its unique window growth
function.
Fig. 1 shows the growth function of BIC. When it gets a
packet loss event, BIC reduces its window by a multiplicative
factor β. The window size just before the reduction is set to the
maximum Wmax and the window size just after the reduction is
set to the minimum Wmin. Then, BIC performs a binary search
using these two parameters – by jumping to the “midpoint”
between Wmax and Wmin. Since packet losses have occurred at
Wmax, the window size that the network can currently handle
without loss must be somewhere between these two numbers.
However, jumping to the midpoint could be too much
increase within one RTT, so if the distance between the
midpoint and the current minimum is larger than a fixed
The good performance of BIC comes
around Wmax and linear increase during
max probing.
B. CUBIC Window Growth Function
Although BIC achieves pretty good s
stability during the current high speed en
growth function can still be too aggress
under short RTT or low speed netwo
several different phases of window
complexity in analyzing the protocol. W
for a new window growth function that
strengths of BIC (especially, its stab
simplifies the window control and
friendliness.
In this paper, we introduce a new hi
CUBIC. As the name of the new pr
Wmax
Steady State Behavior
Fig. 2: The Window Growth Functi
Wmax
Additive Increase
Max Probing
Fig. 1: The Window Growth Function of BIC
Binary Search
C Window Growth Function
delving into CUBIC, let us examine the features of
e main feature of BIC is its unique window growth
The good performance of BIC comes from the slow increase
around Wmax and linear increase during additive increase and
max probing.
Wmax
Steady State Behavior
Max Probing
Fig. 2: The Window Growth Function of CUBIC
rease
Max Probing
Fig. 1: The Window Growth Function of BIC
Binary Search
http://www4.ncsu.edu/~rhee/export/bitcp/
cubic-paper.pdf
41/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Srovnání variant
path propagation delay is varied. Results are shown for 10Mbit/sec and 250Mbit/sec bottleneck bandwi
traffic. Observe that while standard TCP and H-TCP are essentially fair (the competing flows achieve
these conditions, Scalable-TCP and FAST-TCP are notably unfair. HS-TCP and BIC-TCP can also be s
degree than Scalable-TCP and FAST-TCP.
0
200
400
600
800
1000
1200
100 200 300 400 500 600
cwnd(packets)
Time (seconds)
ScalableTCP 1
ScalableTCP 2
0
500
1000
1500
2000
2500
3000
3500
4000
4500
100 200 300 400 500 600
cwnd(packets)
Time (seconds)
ScalableTCP 1
ScalableTCP 2
Fig. 4. Scalable-TCP cwnd time histories following startup of a second flow.
RTT of both flows is 42ms (top) and 162ms (bottom). Bottleneck bandwidth
is 250Mbit/sec, queue size 20% BDP, no web traffic.
0
200
400
600
800
1000
1200
100
cwnd(packets)
0
500
1000
1500
2000
2500
3000
3500
4000
100
cwnd(packets)
Fig. 5. FAST-TCP cw
RTT is 42ms (top) and 1
queue size 20% BDP, n
http://www.hamilton.ie/net/eval/ToNfinal.pdf
42/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Srovnání variant
or 10Mbit/sec and 250Mbit/sec bottleneck bandwidths. The bottleneck queue size is 20% BDP, no web
P are essentially fair (the competing flows achieve, to within 5%, the same average throughput) under
otably unfair. HS-TCP and BIC-TCP can also be seen to exhibit significant unfairness, albeit to a lesser
500 600
lableTCP 1
lableTCP 2
500 600
lableTCP 1
lableTCP 2
startup of a second flow.
). Bottleneck bandwidth
0
200
400
600
800
1000
1200
100 200 300 400 500 600
cwnd(packets)
Time (seconds)
FAST 1
FAST 2
0
500
1000
1500
2000
2500
3000
3500
4000
100 200 300 400 500 600
cwnd(packets)
Time (seconds)
FAST 1
FAST 2
Fig. 5. FAST-TCP cwnd time histories following startup of a second flow.
RTT is 42ms (top) and 162ms (bottom). Bottleneck bandwidth is 250Mbit/sec,
queue size 20% BDP, no web traffic.
http://www.hamilton.ie/net/eval/ToNfinal.pdf
43/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Srovnání variant
0
200
400
600
800
1000
1200
100 200 300 400 500 600
cwnd(packets)
Time (seconds)
HSTCP 1
HSTCP 2
0
500
1000
1500
2000
2500
3000
3500
4000
100 200 300 400 500 600
cwnd(packets)
Time (seconds)
HSTCP 1
HSTCP 2
0
1000
2000
3000
4000
5000
6000
7000
8000
100 200 300 400 500 600
cwnd(packets)
Time (seconds)
HSTCP 1
HSTCP 2
Fig. 6. HS-TCP cwnd time histories following startup of a second flow.
RTT is 42ms (top), 162ms(middle) and 324ms (bottom). Bottleneck bandwidth
250Mbit/sec, queue size 20% BDP, no web traffic.
800
1000
1200
ckets)
HSTCP 1
HSTCP 2
0
200
400
600
800
1000
1200
100 200 300
cwnd(packets)
Time (second
0
500
1000
1500
2000
2500
3000
3500
4000
100 200 300
cwnd(packets)
Time (second
0
1000
2000
3000
4000
5000
6000
7000
8000
100 200 300
cwnd(packets)
Time (second
Fig. 8. BIC-TCP cwnd time histories followin
is 42ms (top), 162ms(middle) and 324ms (bot
250Mbit/sec, queue size 20% BDP, no web tra
800
1000
1200
ets)
http://www.hamilton.ie/net/eval/ToNfinal.pdf
44/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Srovnání variant
300 400 500 600
Time (seconds)
e histories following startup of a second flow.
dle) and 324ms (bottom). Bottleneck bandwidth
BDP, no web traffic.
120 140 160 180 200
Time (seconds)
HSTCP 1
HSTCP 2
120 140 160 180
0
0.2
0.4
0.6
0.8
1
beta
Time (seconds)
HSTCP 1 alpha
HSTCP 2 alpha
HSTCP 1 beta
HSTCP 2 beta
cwnd time histories (top) and α, β time
artup of a second flow. RTT is 42ms, bottleneck
e size 20% BDP, no web traffic.
tions in fairness, BIC-TCP and HScant
levels of unfairness.
what surprising nature of these results,
gating this behaviour in more detail.
ch of the protocols exhibiting greater
n standard TCP.
re 4 shows typical examples of meahistories.
It can seen that the cwnds
verge to fairness or else converge
d (not reaching fairness within the
0
100 200 300 400 500 600
Time (seconds)
Fig. 8. BIC-TCP cwnd time histories following startup of a second flow. RTT
is 42ms (top), 162ms(middle) and 324ms (bottom). Bottleneck bandwidth is
250Mbit/sec, queue size 20% BDP, no web traffic.
0
200
400
600
800
1000
1200
100 200 300 400 500 600
cwnd(packets)
Time (seconds)
HTCP 1
HTCP 2
0
500
1000
1500
2000
2500
3000
3500
4000
100 200 300 400 500 600
cwnd(packets)
Time (seconds)
HTCP 1
HTCP 2
0
1000
2000
3000
4000
5000
6000
7000
8000
100 200 300 400 500 600
cwnd(packets)
Time (seconds)
HTCP 1
HTCP 2
Fig. 9. H-TCP cwnd time histories following startup of a second flow. RTT
is 42ms (top), 162ms (middle) and 324ms (bottom). Bottleneck bandwidth is
250Mbit/sec, queue size 20% BDP, no web traffic.
easily shown that the Scalable-TCP algorithm is in fact
a multiplicative-increase multiplicative-decrease (MIMD)
http://www.hamilton.ie/net/eval/ToNfinal.pdf
45/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Srovnání variant 7
300 400 500 600
Time (seconds)
HSTCP 1
HSTCP 2
300 400 500 600
Time (seconds)
HSTCP 1
HSTCP 2
300 400 500 600
Time (seconds)
HSTCP 1
HSTCP 2
e histories following startup of a second flow.
dle) and 324ms (bottom). Bottleneck bandwidth
BDP, no web traffic.
HSTCP 1
HSTCP 2
0
200
400
600
800
1000
1200
100 200 300 400 500 600
cwnd(packets)
Time (seconds)
BicTCP 1
BicTCP 2
0
500
1000
1500
2000
2500
3000
3500
4000
100 200 300 400 500 600
cwnd(packets)
Time (seconds)
BicTCP 1
BicTCP 2
0
1000
2000
3000
4000
5000
6000
7000
8000
100 200 300 400 500 600
cwnd(packets)
Time (seconds)
BicTCP 1
BicTCP 2
Fig. 8. BIC-TCP cwnd time histories following startup of a second flow. RTT
is 42ms (top), 162ms(middle) and 324ms (bottom). Bottleneck bandwidth is
250Mbit/sec, queue size 20% BDP, no web traffic.
800
1000
1200
ets)
HTCP 1
HTCP 2http://www.hamilton.ie/net/eval/ToNfinal.pdf
46/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
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
47/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
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ílači
• 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ě! :-(
48/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
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 :-(
49/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
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 :-(
50/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
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í
• Tmin, T ... minimální a průměrný pozorovaný RTT
• Tq ... odhad zpoždění front u RTT
• fα(B) ... (8, 20, 200) pro bw (< 10 Mb/s, 10 − 100 Mb/s,
> 100 Mb/s), lze měnit přes sysctl()
• γ ... parametr návrhu ;-)
ACK: cwnd = min 2 × cwnd,(1 − γ)cwnd + γ Tmin
T
cwnd + fα(B,Tq)
výpadek: cwnd = 0,5 cwnd
fα(B,Tq) =
a × cwnd Tq = 0
fα(B) Tq = 0
51/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Algoritmy v jádrech OS
• Linux
• BIC-TCP (default 2.6.8–2.6.18)
• CUBIC (default 2.6.19–)
• dostupné implementace ve 2.6.22:
Reno, Vegas, BIC, CUBIC, Westwood, H- TCP, High speed,
Hybla, Scalable, Yeah, VENO, Illinois, and Low Priority
• http://git.kernel.org/?p=linux/kernel/git/
torvalds/linux.git;a=blob_plain;f=net/ipv4/
Kconfig;hb=HEAD
TCP_CONG_ADVANCED
• TCP Implementation in Linux: A Brief Tutorial,
http://www.ece.virginia.edu/cheetah/
documents/papers/TCPlinux.pdf
52/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Algoritmy v jádrech OS
• Linux
hopet@frakira:/lib/modules/2.6.24−24−server$ find . −name "*tcp*" \
| fgrep ipv4
./kernel/net/ipv4/tcp_yeah.ko
./kernel/net/ipv4/tcp_vegas.ko
./kernel/net/ipv4/tcp_highspeed.ko
./kernel/net/ipv4/tcp_cubic.ko
./kernel/net/ipv4/tcp_lp.ko
./kernel/net/ipv4/tcp_scalable.ko
./kernel/net/ipv4/tcp_probe.ko
./kernel/net/ipv4/tcp_illinois.ko
./kernel/net/ipv4/tcp_bic.ko
./kernel/net/ipv4/tcp_veno.ko
./kernel/net/ipv4/tcp_hybla.ko
./kernel/net/ipv4/tcp_westwood.ko
./kernel/net/ipv4/tcp_htcp.ko
sysctl net.ipv4.tcp_available_congestion_control
sysctl −w net.ipv4.tcp_congestion_control=cubic
53/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Algoritmy v jádrech OS
• FreeBSD 9.x
• ztráty: NewReno, CUBIC, HTCP
• latence: Vegas, HD and CHD (odolnost proti výpadkům
nezpůsobeným ucpáním)
• http://caia.swin.edu.au/freebsd/5cc/
• http://freebsdfoundation.blogspot.com/2011/
03/summary-of-five-new-tcp-congestion.html
• [3]
• Windows Vista/7/2008 Server
• Compound TCP
netsh interface tcp set global congestionprovider=ctcp
netsh interface tcp set global congestionprovider=none
netsh interface tcp show global
54/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Přehled přednášky
Tradiční TCP a jeho problémy
Vylepšení TCP
Víceproudové TCP
Web100
Konzervativní rozšíření TCP
GridDT
Scalable TCP, High-Speed TCP, H-TCP, BIC-TCP
Rozšíření TCP s podporou IP
QuickStart, E-TCP, FAST
Implementace v OS
Přístupy odlišné od TCP
tsunami
RBUDP
XCP
SCTP, DCCP, STP, Reliable UDP, XTP
Závěrečné poznámky
55/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
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
56/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Reliable Blast UDP – RBUDP
• podobné jako tsunami – out-of-band TCP kanál pro
řízení, UDP pro přenos
• vytvořeno pro přenosy z disku na disk, příp. takové, kde
kompletní přenášená data lze udržet v paměti vysílače
• posílá data uživatelem definovanou rychlostí
• app_perf (klon iperfu) pro odhad kapacity sítě a
přijímače
57/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Reliable Blast UDP – RBUDP
into account the fact that in a real application, data is not simply streamed to a receiver and discarded. It has
to be moved into main memory for the application to use. This has motivated us to produce app_perf (a
modified version of iperf) to take into account an extra memory copy that most applications must perform.
We can therefore use app_perf as a more realistic bound for how well a transmission scheme should be able
to reasonably obtain. In the experiments detailed in Section 5, we however include both iperf and
app_perf’s prediction of available bandwidth.
Figure 1. The Time Sequence Diagram of RBUDP
Three versions of RBUDP were developed:
1. RBUDP without scatter/gather optimization – this is a naïve implementation of RBUDP where
each incoming packet is examined (to determine where it should go in the application’s memory
buffer) and then moved there.
2. RBUDP with scatter/gather optimization – this implementation takes advantage of the fact that
most incoming packets are likely to arrive in order, and if transmission rates are below the
maximum throughput of the network, packets are unlikely to be lost. The algorithm works by
using readv() to directly move the data from kernel memory to its predicted location in the
application’s memory. After performing this readv() the packet header is examined to determine if
it was placed in the correct location. If it was not (either because it was an out-of-order packet, or
an intermediate packet was lost), then the packet is moved to the correct location in the user’s
memory buffer.
3. “Fake” RBUDP – this implementation is the same as the scheme without the scatter/gather
Sender Receiver
…
A
B
C
D
E
F
G
UDP data traffic
TCP signaling traffic
Zdroj: E. He, J. Leigh, O. Yu, T. A. DeFanti, “Reliable Blast UDP: Predictable High Performance Bulk Data Transfer,” IEEE
Cluster Computing 2002, Chicago, Illinois, Sept, 2002.
A zahájení vysílání nastavenou rychlostí
B konec vysílní
C zaslání signálu DONE po řídícím kanálu, na nějž přijímající zareaguje
zasláním masky dat, které dorazily
D opětovné zaslání chybějících dat
E-F-G dokončení přenosu
Přižemž body C a D se opakují tak dlouho, dokud nejsou doručena všechna data.
58/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
XCP
• zpětná vazba od směrovačů per paket
PSaAP II 44/52
XCP
• per packet feedback from routers
Feedback
Round Trip Time
Congestion Window
Congestion Header
Feedback
Round Trip Time
Congestion Window
Feedback =
+ 0.1 packet
59/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
XCP
• zpětná vazba od směrovačů per paketXCP (2)
Feedback =
+ 0.1 packet
Round Trip Time
Congestion Window
Feedback =
- 0.3 packet
60/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
XCP
• zpětná vazba od směrovačů per paket
PSaAP II 46/52
XCP (3)
Congestion Window = Congestion Window + Feedback
61/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
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/
62/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
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/OLS/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.javvin.com/protocolRUDP.html
• XTP (Xpress Transfer Protocol), ...
63/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
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ř. λ-sítě
CzechLight/CESNET2, SurfNet, CaNET*4, ...)
• implementace SCTP ve FreeBSD 7.0
• implementace DCCP v Linuxu
64/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
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ěrovačí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 :-(
65/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Literatura
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
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/jsac.ps
http://www.web100.org
Hacker T. J., Athey B. D., Sommerfield J. “Experiences Using Web100 for End-To-End
Network Performance Tuning”
http://www.web100.org/docs/ExperiencesUsingWeb100forHostTuning.pdf
66/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Literatura
Kelly T. “Scalable TCP: Improving Performance in Highspeed Wide Area Networks”,
PFLDnet 2003,
http://datatag.web.cern.ch/datatag/pfldnet2003/papers/kelly.pdf,
http://wwwlce.eng.cam.ac.uk/~ctk21/scalable/
Floyd S. “HighSpeed TCP for Large Congestion Windows”, 2003, http:
//www.potaroo.net/ietf/all-ids/draft-floyd-tcp-highspeed-03.txt
BIC-TCP, http://www.csc.ncsu.edu/faculty/rhee/export/bitcp/
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
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
67/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
Literatura
E. He, J. Leigh, O. Yu, T. A. DeFanti, “Reliable Blast UDP: Predictable High Performance
Bulk Data Transfer,” IEEE Cluster Computing 2002, Chicago, Illinois, Sept, 2002.
Stephen Hemminger, “TCP testing – Preventing global Internet warming”, 2007,
http://www.linuxconf.eu/2007/papers/Hemminger.pdf
David Hayes, Lawrence Stewart, Grenville Armitage, “Evaluating the FreeBSD 9.x
Modular Congestion Control Framework’s Performance Impact”, CAIA Technical Report
110228A, February 2011, p. 5,
http://caia.swin.edu.au/reports/110228A/CAIA-TR-110228A.pdf
68/68
Tradiční TCP Vylepšení TCP Rozšíření TCP Rozšíření TCP s IP Implementace Ne-TCP Závěr Literatura
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/
• http://wil.cs.caltech.edu/pfldnet2007/
• Strány 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