Sieci komputerowe

Wykład 6: Algorytmy protokołu TCP

Marcin Bie ´nkowski

Instytut Informatyki

Uniwersytet Wrocławski

Sieci komputerowe (II UWr)

Wykład 6

1 / 27

Przypomnienie

Warstwy w systemie operacyjnym

1

fizyczna (kable i elektrony)

2

ł ˛

acza danych (Ethernet)

3

sieciowa (routing, IP)

4

transportowa (TCP, UDP)

Sieci komputerowe (II UWr)

Wykład 6

2 / 27

Przypomnienie

TCP

Protokół warstwy transportowej

Udost ˛epnia wygodne usługi przesyłania danych mi ˛edzy dwoma
komputerami.

Porty

Przesyłane jednostki: segmenty

Flagi segmentów (SYN, ACK, FIN, ...)

Poł ˛

aczeniowy, kontrola bł ˛edów, sterowanie przepływem, radzenie

sobie z duplikatami

Klucz do sukcesu: numery sekwencyjne, potwierdzanie i ewentualne
ponowne przesyłanie segmentów

Sieci komputerowe (II UWr)

Wykład 6

3 / 27

Przypomnienie

TCP

Protokół warstwy transportowej

Udost ˛epnia wygodne usługi przesyłania danych mi ˛edzy dwoma
komputerami.

Porty

Przesyłane jednostki: segmenty

Flagi segmentów (SYN, ACK, FIN, ...)

Poł ˛

aczeniowy, kontrola bł ˛edów, sterowanie przepływem, radzenie

sobie z duplikatami

Klucz do sukcesu: numery sekwencyjne, potwierdzanie i ewentualne
ponowne przesyłanie segmentów

Sieci komputerowe (II UWr)

Wykład 6

3 / 27

Przypomnienie

Numery sekwencyjne

Na pocz ˛

atku poł ˛

aczenia ka˙zda ze stron ustala jaki´s numer i

wysyła go drugiej stronie.

Wszystkie wysyłane

bajty

dostaj ˛

a kolejne numery.

Je´sli segment zostanie niepotwierdzone przez dłu˙zszy czas (timer,
szacowanie RTT (round trip time)), to wysyłany jest ponownie.

Druga strona co jaki´s czas potwierdza = pisze, ˙ze dostała
wszystkie bajty do numeru x i czeka teraz na bajty od
numeru x + 1 (ACK x + 1).

Sieci komputerowe (II UWr)

Wykład 6

4 / 27

Przypomnienie

Numery sekwencyjne

Na pocz ˛

atku poł ˛

aczenia ka˙zda ze stron ustala jaki´s numer i

wysyła go drugiej stronie

.

Wszystkie wysyłane

bajty

dostaj ˛

a kolejne numery.

Je´sli segment zostanie niepotwierdzone przez dłu˙zszy czas (timer,
szacowanie RTT (round trip time)), to wysyłany jest ponownie.

Druga strona co jaki´s czas potwierdza = pisze, ˙ze dostała
wszystkie bajty do numeru x i czeka teraz na bajty od
numeru x + 1 (ACK x + 1).

Sieci komputerowe (II UWr)

Wykład 6

4 / 27

Przypomnienie

Nawi ˛

azywanie poł ˛

aczenia

Trójstopniowe nawi ˛

azywanie poł ˛

aczenia → obrazek

Ko ´

nczenie poł ˛

aczenia

Wysyłane 4 segmenty (

dowolna

ze stron zaczyna wykonuj ˛

ac

zamkni ˛ecie aktywne)

Jakikolwiek segment FIN dotrze do drugiej strony, to nawet je´sli
wszystko zaginie to po pewnym czasie poł ˛

aczenie jest zrywane.

Problem: Jedna strona robi aktywne zamkni ˛ecie i WSZYSTKIE
pakiety FIN gin ˛

a → druga strona nigdy si ˛e nie dowiaduje.

Rozwi ˛

azanie: je´sli nie otrzymujemy przez jaki´s czas ˙zadnych

pakietów, to zwalniamy poł ˛

aczenie.

Sieci komputerowe (II UWr)

Wykład 6

5 / 27

Przypomnienie

Nawi ˛

azywanie poł ˛

aczenia

Trójstopniowe nawi ˛

azywanie poł ˛

aczenia → obrazek

Ko ´

nczenie poł ˛

aczenia

Wysyłane 4 segmenty (

dowolna

ze stron zaczyna wykonuj ˛

ac

zamkni ˛ecie aktywne)

Jakikolwiek segment FIN dotrze do drugiej strony, to nawet je´sli
wszystko zaginie to po pewnym czasie poł ˛

aczenie jest zrywane.

Problem: Jedna strona robi aktywne zamkni ˛ecie i WSZYSTKIE
pakiety FIN gin ˛

a → druga strona nigdy si ˛e nie dowiaduje.

Rozwi ˛

azanie: je´sli nie otrzymujemy przez jaki´s czas ˙zadnych

pakietów, to zwalniamy poł ˛

aczenie.

Sieci komputerowe (II UWr)

Wykład 6

5 / 27

Przypomnienie

Flagi segmentów — podsumowanie

SYN: u˙zywana przy nawi ˛

azywaniu poł ˛

aczenia, ustala pocz ˛

atkowy

numer sekwencyjny.

ACK: je´sli jest wł ˛

aczona, to pole „potwierdzenie” ma znaczenie.

FIN: u˙zywane przy ko ´nczeniu poł ˛

aczenia.

RST: oznacza wyst ˛

apienie bł ˛edu, ko ´nczy poł ˛

aczenie. Wysyłane

przykładowo przy próbie poł ˛

aczenia z portem, na którym nikt nie

nasłuchuje.

Mo˙zliwe wszystkie kombinacje, wi ˛ekszo´s´c ma niezdefiniowane i
ciekawe efekty.

Sieci komputerowe (II UWr)

Wykład 6

6 / 27

Dzisiaj

Poprzednie elementy: wszystkie implementacje TCP

Kilkadziesi ˛

at wariantów implementacji:

TCP Tahoe, Reno, Vegas, New Reno, Westwood, BIC-TCP, ...

Ró˙znice: algorytmy stosowane przy potwierdzaniu segmentów,
sterowaniu przepływem i szybko´sci ˛

a wysyłania, kontroli

obci ˛

a˙zenia ł ˛

acza ...

Cz ˛e´s´c z tych algorytmów to klocki, które mo˙zna wł ˛

acza´c lub

wył ˛

acza´c.

Sieci komputerowe (II UWr)

Wykład 6

7 / 27

Dzisiaj

Poprzednie elementy: wszystkie implementacje TCP

Kilkadziesi ˛

at wariantów implementacji:

TCP Tahoe, Reno, Vegas, New Reno, Westwood, BIC-TCP, ...

Ró˙znice: algorytmy stosowane przy potwierdzaniu segmentów,
sterowaniu przepływem i szybko´sci ˛

a wysyłania, kontroli

obci ˛

a˙zenia ł ˛

acza ...

Cz ˛e´s´c z tych algorytmów to klocki, które mo˙zna wł ˛

acza´c lub

wył ˛

acza´c.

Sieci komputerowe (II UWr)

Wykład 6

7 / 27

Potwierdzenia

Potwierdzanie

Potwierdzanie ka˙zdego segmentu jest nieefektywne

potwierdzenia mo˙zna wysyła´c „przy okazji” razem z danymi

problem je´sli nie ma danych do wysłania

opó´znione potwierdzanie (delayed acknowledgements) — mi ˛edzy
kolejnymi potwierdzeniami musi upłyn ˛

a´c konkretny czas, np. 200

ms.

Sieci komputerowe (II UWr)

Wykład 6

8 / 27

Potwierdzenia

MSS

Rozmiary segmentów

Przy nawi ˛

azywaniu poł ˛

aczenia wysyłany jest MSS (maximum

segment size) = max. ilo´s´c danych w pojedynczym segmencie.

Warstwa 4: MSS, warstwa 2: MTU

Brak naturalnego ograniczenia od dołu na rozmiar segmentu

Sieci komputerowe (II UWr)

Wykład 6

9 / 27

Potwierdzenia

Sterowanie przepływem, cz ˛e´s´c I

Problemy przy szybkim wysyłaniu

Odbiorca nie nad ˛

a˙za odbiera´c danych

Ograniczenia przepustowo´sci kanału (+ inne transmisje)

Sieci komputerowe (II UWr)

Wykład 6

10 / 27

Potwierdzenia

Sterowanie przepływem, cz ˛e´s´c I

Problemy przy szybkim wysyłaniu

Odbiorca nie nad ˛

a˙za odbiera´c danych

Ograniczenia przepustowo´sci kanału (+ inne transmisje)

Sieci komputerowe (II UWr)

Wykład 6

10 / 27

Okno przesuwne

Okno przesuwne

Odbiorca ma bufor na odebrane bajty (z segmentów), jeszcze nie
przeczytane przez aplikacj ˛e.

Wolne miejsce w tym buforze jest wysyłane w polu Window przy
potwierdzaniu (ACK).

Kolejka pakietów nadawcy:

4

5

6

7

8

9

10

11

12

3

2

1

wyslane i potwierdzone

ostatnio deklarowany rozmiar okna odbiorcy

dane, ktore

moga zostac

wyslane

dane, ktore moga

zostac wyslane dopiero

po przesunieciu okna

wyslane ale niepotwierdzone

Sieci komputerowe (II UWr)

Wykład 6

11 / 27

Okno przesuwne

Okno przesuwne, cd.

Kolejka pakietów nadawcy:

4

5

6

7

8

9

10

11

12

3

2

1

wyslane i potwierdzone

ostatnio deklarowany rozmiar okna odbiorcy

dane, ktore

moga zostac

wyslane

dane, ktore moga

zostac wyslane dopiero

po przesunieciu okna

wyslane ale niepotwierdzone

Potwierdzanie danych
→ okno zamyka si ˛e = lewy koniec okna idzie w prawo

Aplikacja po stronie odbiorcy czyta dane z bufora
→ okno otwiera si ˛e = prawy koniec idzie w prawo

Sieci komputerowe (II UWr)

Wykład 6

12 / 27

Okno przesuwne

Syndrom głupiutkiego okna

Silly window syndrome

J ˛

adro odbiorcy potwierdza segmenty

Aplikacja odbiorcy nie nad ˛

a˙za odbiera´c pakietów → deklarowany

rozmiar okna jest coraz mniejszy

Nadawca wysyła bardzo małe segmenty → nieefektywne

Jedno z mo˙zliwych rozwi ˛

aza ´n: zgłasza´c rozmiar okna = 0.

Sieci komputerowe (II UWr)

Wykład 6

13 / 27

Okno przesuwne

Syndrom głupiutkiego okna

Silly window syndrome

J ˛

adro odbiorcy potwierdza segmenty

Aplikacja odbiorcy nie nad ˛

a˙za odbiera´c pakietów → deklarowany

rozmiar okna jest coraz mniejszy

Nadawca wysyła bardzo małe segmenty → nieefektywne

Jedno z mo˙zliwych rozwi ˛

aza ´n: zgłasza´c rozmiar okna = 0.

Sieci komputerowe (II UWr)

Wykład 6

13 / 27

Okno przesuwne

Dualny problem

Odbiorca ma mało danych do wysłania:

Algorytm Nagle’a

Wstrzymujemy wysłanie bardzo małych segmentów, dopóki nie
dostaniemy potwierdzenia wszystkich wysłanych segmentów albo do
momentu zebrania wi ˛ekszej ilo´sci danych do wysłania.

Zalety: dostosowuje si ˛e do bie˙z ˛

acego obci ˛

a˙zenia.

Szybkie ł ˛

acze — wysyłane małe segmenty

Wolne ł ˛

acze — małe segmenty zbierane w wi ˛eksze kawałki

Mo˙zna go wył ˛

aczy´c: np. je´sli przesyłamy ruchy mysz ˛

a.

Sieci komputerowe (II UWr)

Wykład 6

14 / 27

Okno przesuwne

Dualny problem

Odbiorca ma mało danych do wysłania:

Algorytm Nagle’a

Wstrzymujemy wysłanie bardzo małych segmentów, dopóki nie
dostaniemy potwierdzenia wszystkich wysłanych segmentów albo do
momentu zebrania wi ˛ekszej ilo´sci danych do wysłania.

Zalety: dostosowuje si ˛e do bie˙z ˛

acego obci ˛

a˙zenia.

Szybkie ł ˛

acze — wysyłane małe segmenty

Wolne ł ˛

acze — małe segmenty zbierane w wi ˛eksze kawałki

Mo˙zna go wył ˛

aczy´c: np. je´sli przesyłamy ruchy mysz ˛

a.

Sieci komputerowe (II UWr)

Wykład 6

14 / 27

Okno przesuwne

Wró´cmy do okna przesuwnego

4

5

6

7

8

9

10

11

12

3

2

1

wyslane i potwierdzone

ostatnio deklarowany rozmiar okna odbiorcy

dane, ktore

moga zostac

wyslane

dane, ktore moga

zostac wyslane dopiero

po przesunieciu okna

wyslane ale niepotwierdzone

Im wi ˛eksze okno, tym wi ˛eksza szybko´s´c wysyłania danych

.

Sieci komputerowe (II UWr)

Wykład 6

15 / 27

Kontrola przeci ˛

a˙ze ´n

Sterowanie przepływem, cz ˛e´s´c II

Problemy przy szybkim wysyłaniu

Odbiorca nie nad ˛

a˙za odbiera´c danych

→ rozmiar okna odbiorcy wnd

Ograniczenia przepustowo´sci kanału (+ inne transmisje)

Idea: wysyłamy za szybko →
→ sie´c staje si ˛e przeci ˛

a˙zona →

→ pakiety si ˛e gubi ˛

a / potwierdzenia nie docieraj ˛

a →

→ zwalniamy pr ˛edko´s´c wysyłania

Sieci komputerowe (II UWr)

Wykład 6

16 / 27

Kontrola przeci ˛

a˙ze ´n

Sterowanie przepływem, cz ˛e´s´c II

Problemy przy szybkim wysyłaniu

Odbiorca nie nad ˛

a˙za odbiera´c danych

→ rozmiar okna odbiorcy wnd

Ograniczenia przepustowo´sci kanału (+ inne transmisje)

Idea: wysyłamy za szybko →
→ sie´c staje si ˛e przeci ˛

a˙zona →

→ pakiety si ˛e gubi ˛

a / potwierdzenia nie docieraj ˛

a →

→ zwalniamy pr ˛edko´s´c wysyłania

Sieci komputerowe (II UWr)

Wykład 6

16 / 27

Kontrola przeci ˛

a˙ze ´n

cwnd

Okno przeci ˛

a˙zenia (congestion window)

Dwa parametry:

1. rozmiar okna odbiorcy wnd

2. rozmiar „okna przeci ˛

a˙zenia” cwnd

Wykorzystujemy okno o rozmiarze min{ wnd , cwnd }

cwnd zmienia si ˛e w zale˙zno´sci od zachowania si ˛e ł ˛

acza (i innych

współbie˙znych transmisji), odpowiada zaj ˛eto´sci ł ˛

acza

Sieci komputerowe (II UWr)

Wykład 6

17 / 27

Kontrola przeci ˛

a˙ze ´n

cwnd

Uwagi upraszczaj ˛

ace

Nie my´slimy o bajtach, tylko o segmentach o rozmiarze MSS.

Liczymy wszystko w segmentach.

Zakładamy, ˙ze wnd = ∞.

Sieci komputerowe (II UWr)

Wykład 6

18 / 27

Kontrola przeci ˛

a˙ze ´n

cwnd

Zmiana cwnd, wolny start

Na pocz ˛

atku

ssthresh = ∞

cwnd = 1

tryb wolnego startu (dopóki cwnd ≤ ssthresh)

Wolny start

Za ka˙zdym potwierdzeniem zwi ˛ekszamy cwnd o 1
→ co RTT (round trip time) mamy: cwnd ← 2 · cwnd

W momencie utraty pakietu:

ssthresh = max{2, cwnd /2}

cwnd = 1

→ rysunek

Sieci komputerowe (II UWr)

Wykład 6

19 / 27

Kontrola przeci ˛

a˙ze ´n

cwnd

Zmiana cwnd, wolny start

Na pocz ˛

atku

ssthresh = ∞

cwnd = 1

tryb wolnego startu (dopóki cwnd ≤ ssthresh)

Wolny start

Za ka˙zdym potwierdzeniem zwi ˛ekszamy cwnd o 1
→ co RTT (round trip time) mamy: cwnd ← 2 · cwnd

W momencie utraty pakietu:

ssthresh = max{2, cwnd /2}

cwnd = 1

→ rysunek

Sieci komputerowe (II UWr)

Wykład 6

19 / 27

Kontrola przeci ˛

a˙ze ´n

cwnd

Zmiana cwnd, unikanie kolizji

Kiedy cwnd > ssthresh

cwnd = cwnd + 1 (co tur ˛e = RTT)

Utrata pakietu → to samo co poprzednio:

ssthresh = max{2, cwnd /2}

cwnd = 1

Sieci komputerowe (II UWr)

Wykład 6

20 / 27

Kontrola przeci ˛

a˙ze ´n

cwnd

Zmiana cwnd, podsumowanie

Pomijaj ˛

ac krótkie odcinki wolnego startu, gra wygl ˛

ada nast ˛epuj ˛

aco:

Co tur ˛e (czas RTT) cwnd = cwnd + 1

Je´sli nast ˛epuje utrata pakietu, to cwnd = cwnd /2.

Algorytm AIMD
additive increase,
multiplicative decrease

Pokazali´smy „jak”.
Ale „dlaczego”?

Obrazek ze strony http://courseweb.sp.cs.cmu.edu/ cs395/2005/applications/ln/lecture24.html

Sieci komputerowe (II UWr)

Wykład 6

21 / 27

Kontrola przeci ˛

a˙ze ´n

cwnd

Zmiana cwnd, podsumowanie

Pomijaj ˛

ac krótkie odcinki wolnego startu, gra wygl ˛

ada nast ˛epuj ˛

aco:

Co tur ˛e (czas RTT) cwnd = cwnd + 1

Je´sli nast ˛epuje utrata pakietu, to cwnd = cwnd /2.

Algorytm AIMD
additive increase,
multiplicative decrease

Pokazali´smy „jak”.
Ale „dlaczego”?

Obrazek ze strony http://courseweb.sp.cs.cmu.edu/ cs395/2005/applications/ln/lecture24.html

Sieci komputerowe (II UWr)

Wykład 6

21 / 27

Kontrola przeci ˛

a˙ze ´n

cwnd

Nasz model

Jeden kanał komunikacyjny

Całkowita przepustowo´s´c = K

n konkuruj ˛

acych komunikacji TCP

W ka˙zdym kroku: transmisja i wybiera pr ˛edko´s´c przesyłania
danych x

i

∈ [0, K ].

Je´sli

P

n
i=1

x

i

≤ K , komunikacja powodzi si ˛e.

W przeciwnym przypadku segmenty s ˛

a gubione.

Ka˙zdy uczestnik komunikacji wie, która z opcji zaszła (cho´c nie
zna warto´sci

P

n
i=1

x

i

)

Sieci komputerowe (II UWr)

Wykład 6

22 / 27

Kontrola przeci ˛

a˙ze ´n

cwnd

Co chcieliby´smy osi ˛

agn ˛

a´c

1

Efektywne wykorzystanie ł ˛

acza:

P

n
i=1

x

i

jak najbli˙zsze K .

2

Sprawiedliwy podział ł ˛

acza: wszystkie x

i

jak najmniej si ˛e ró˙zni ˛

ace.

3

Strategia dla ka˙zdej transmisji powinna by´c taka sama.

Sieci komputerowe (II UWr)

Wykład 6

23 / 27

Kontrola przeci ˛

a˙ze ´n

cwnd

Model, cd.

Wybieramy funkcje f

I

: [

0, B] → [0, B], f

D

: [

0, B] → [0, B].

x

i

(

t): warto´s´c x

i

w kroku t.

Obliczanie warto´sci x

i

w kolejnym kroku

n

X

i=1

x

i

≤ K =⇒ x

i

(

t + 1) = f

I

(

x

i

(

t))

(dla wszystkich i)

n

X

i=1

x

i

>

K =⇒ x

i

(

t + 1) = f

D

(

x

i

(

t))

(dla wszystkich i)

Ograniczymy si ˛e do liniowych funkcji f

I

i f

D

.

Sieci komputerowe (II UWr)

Wykład 6

24 / 27

Kontrola przeci ˛

a˙ze ´n

cwnd

Analiza

→ notatki, obrazki

Sieci komputerowe (II UWr)

Wykład 6

25 / 27

Kontrola przeci ˛

a˙ze ´n

cwnd

Pokazali´smy, ˙ze

Jedynym sensownym wyborem liniowych funkcji f

I

i f

D

jest

f

I

(

z) ≥ z + a

I

,

gdzie a

I

>

0 ,

f

D

(

z) = b

D

· z,

gdzie 0 < b

D

<

1 .

W TCP:

a

I

=

MSS,

b

D

=

1
2

Sieci komputerowe (II UWr)

Wykład 6

26 / 27

Kontrola przeci ˛

a˙ze ´n

cwnd

Jeszcze jedna sztuczka

Fast retransmit

Normalnie segmenty s ˛

a wysyłane ponownie, je´sli s ˛

a

niepotwierdzone przez pewien czas

Je´sli dostajemy trzy takie same potwierdzenia z rz ˛edu: ACK x, to
jest du˙za szansa, ˙ze segment zaczynaj ˛

acy si ˛e od bajtu x zagin ˛

ał

Wysyłamy go bez czekania na jego timeout

Fast recovery: nie przechodzimy do trybu wolnego startu tak jak
przy „zwykłej” utracie pakietu

Sieci komputerowe (II UWr)

Wykład 6

27 / 27