Sieci komputerowe
Wykład 6: Algorytmy protokołu TCP
Marcin Bieńkowski
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
łącza 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ępnia wygodne usługi przesyłania danych między dwoma
komputerami.
Porty
Przesyłane jednostki: segmenty
Flagi segmentów (SYN, ACK, FIN, ...)
Połączeniowy, kontrola błędó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ępnia wygodne usługi przesyłania danych między dwoma
komputerami.
Porty
Przesyłane jednostki: segmenty
Flagi segmentów (SYN, ACK, FIN, ...)
Połączeniowy, kontrola błędó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ątku połączenia każda ze stron ustala jakiś numer i
wysyła go drugiej stronie.
Wszystkie wysyłane bajty dostają kolejne numery.
Jeśli segment zostanie niepotwierdzone przez dłuższy czas (timer,
szacowanie RTT (round trip time)), to wysyłany jest ponownie.
Druga strona co jakiś czas potwierdza = pisze, że 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ątku połączenia każda ze stron ustala jakiś numer i
wysyła go drugiej stronie.
Wszystkie wysyłane bajty dostają kolejne numery.
Jeśli segment zostanie niepotwierdzone przez dłuższy czas (timer,
szacowanie RTT (round trip time)), to wysyłany jest ponownie.
Druga strona co jakiś czas potwierdza = pisze, że 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ązywanie połączenia
Trójstopniowe nawiązywanie połączenia obrazek
Kończenie połączenia
Wysyłane 4 segmenty (dowolna ze stron zaczyna wykonując
zamknięcie aktywne)
Jakikolwiek segment FIN dotrze do drugiej strony, to nawet jeśli
wszystko zaginie to po pewnym czasie połączenie jest zrywane.
Problem: Jedna strona robi aktywne zamknięcie i WSZYSTKIE
pakiety FIN giną druga strona nigdy się nie dowiaduje.
Rozwiązanie: jeśli nie otrzymujemy przez jakiś czas żadnych
pakietów, to zwalniamy połączenie.
Sieci komputerowe (II UWr) Wykład 6 5 / 27
Przypomnienie
Nawiązywanie połączenia
Trójstopniowe nawiązywanie połączenia obrazek
Kończenie połączenia
Wysyłane 4 segmenty (dowolna ze stron zaczyna wykonując
zamknięcie aktywne)
Jakikolwiek segment FIN dotrze do drugiej strony, to nawet jeśli
wszystko zaginie to po pewnym czasie połączenie jest zrywane.
Problem: Jedna strona robi aktywne zamknięcie i WSZYSTKIE
pakiety FIN giną druga strona nigdy się nie dowiaduje.
Rozwiązanie: jeśli nie otrzymujemy przez jakiś czas żadnych
pakietów, to zwalniamy połączenie.
Sieci komputerowe (II UWr) Wykład 6 5 / 27
Przypomnienie
Flagi segmentów  podsumowanie
SYN: używana przy nawiązywaniu połączenia, ustala początkowy
numer sekwencyjny.
ACK: jeśli jest włączona, to pole  potwierdzenie ma znaczenie.
FIN: używane przy kończeniu połączenia.
RST: oznacza wystąpienie błędu, kończy połączenie. Wysyłane
przykładowo przy próbie połączenia z portem, na którym nikt nie
nasłuchuje.
Możliwe wszystkie kombinacje, większość ma niezdefiniowane i
ciekawe efekty.
Sieci komputerowe (II UWr) Wykład 6 6 / 27
Dzisiaj
Poprzednie elementy: wszystkie implementacje TCP
Kilkadziesiąt wariantów implementacji:
TCP Tahoe, Reno, Vegas, New Reno, Westwood, BIC-TCP, ...
Różnice: algorytmy stosowane przy potwierdzaniu segmentów,
sterowaniu przepływem i szybkością wysyłania, kontroli
obciążenia łącza ...
Część z tych algorytmów to klocki, które można włączać lub
wyłączać.
Sieci komputerowe (II UWr) Wykład 6 7 / 27
Dzisiaj
Poprzednie elementy: wszystkie implementacje TCP
Kilkadziesiąt wariantów implementacji:
TCP Tahoe, Reno, Vegas, New Reno, Westwood, BIC-TCP, ...
Różnice: algorytmy stosowane przy potwierdzaniu segmentów,
sterowaniu przepływem i szybkością wysyłania, kontroli
obciążenia łącza ...
Część z tych algorytmów to klocki, które można włączać lub
wyłączać.
Sieci komputerowe (II UWr) Wykład 6 7 / 27
Potwierdzenia
Potwierdzanie
Potwierdzanie każdego segmentu jest nieefektywne
potwierdzenia można wysyłać  przy okazji razem z danymi
problem jeśli nie ma danych do wysłania
opóz
nione potwierdzanie (delayed acknowledgements)  między
kolejnymi potwierdzeniami musi upłynąć konkretny czas, np. 200
ms.
Sieci komputerowe (II UWr) Wykład 6 8 / 27
Potwierdzenia
MSS
Rozmiary segmentów
Przy nawiązywaniu połączenia wysyłany jest MSS (maximum
segment size) = max. ilość 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ęść I
Problemy przy szybkim wysyłaniu
Odbiorca nie nadąża odbierać danych
Ograniczenia przepustowości kanału (+ inne transmisje)
Sieci komputerowe (II UWr) Wykład 6 10 / 27
Potwierdzenia
Sterowanie przepływem, część I
Problemy przy szybkim wysyłaniu
Odbiorca nie nadąża odbierać danych
Ograniczenia przepustowości kanału (+ inne transmisje)
Sieci komputerowe (II UWr) Wykład 6 10 / 27
Okno przesuwne
Syndrom głupiutkiego okna
Silly window syndrome
Jądro odbiorcy potwierdza segmenty
Aplikacja odbiorcy nie nadąża odbierać pakietów deklarowany
rozmiar okna jest coraz mniejszy
Nadawca wysyła bardzo małe segmenty nieefektywne
Jedno z możliwych rozwiązań: zgłaszać rozmiar okna = 0.
Sieci komputerowe (II UWr) Wykład 6 13 / 27
Okno przesuwne
Syndrom głupiutkiego okna
Silly window syndrome
Jądro odbiorcy potwierdza segmenty
Aplikacja odbiorcy nie nadąża odbierać pakietów deklarowany
rozmiar okna jest coraz mniejszy
Nadawca wysyła bardzo małe segmenty nieefektywne
Jedno z możliwych rozwiązań: zgłaszać 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ększej ilości danych do wysłania.
Zalety: dostosowuje się do bieżącego obciążenia.
Szybkie łącze  wysyłane małe segmenty
Wolne łącze  małe segmenty zbierane w większe kawałki
Można go wyłączyć: np. jeśli przesyłamy ruchy myszą.
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ększej ilości danych do wysłania.
Zalety: dostosowuje się do bieżącego obciążenia.
Szybkie łącze  wysyłane małe segmenty
Wolne łącze  małe segmenty zbierane w większe kawałki
Można go wyłączyć: np. jeśli przesyłamy ruchy myszą.
Sieci komputerowe (II UWr) Wykład 6 14 / 27
Kontrola przeciążeń
Sterowanie przepływem, część II
Problemy przy szybkim wysyłaniu
Odbiorca nie nadąża odbierać danych
rozmiar okna odbiorcy wnd
Ograniczenia przepustowości kanału (+ inne transmisje)
Idea: wysyłamy za szybko
sieć staje się przeciążona
pakiety się gubią / potwierdzenia nie docierają
zwalniamy prędkość wysyłania
Sieci komputerowe (II UWr) Wykład 6 16 / 27
Kontrola przeciążeń
Sterowanie przepływem, część II
Problemy przy szybkim wysyłaniu
Odbiorca nie nadąża odbierać danych
rozmiar okna odbiorcy wnd
Ograniczenia przepustowości kanału (+ inne transmisje)
Idea: wysyłamy za szybko
sieć staje się przeciążona
pakiety się gubią / potwierdzenia nie docierają
zwalniamy prędkość wysyłania
Sieci komputerowe (II UWr) Wykład 6 16 / 27
Kontrola przeciążeń cwnd
Okno przeciążenia (congestion window)
Dwa parametry:
1. rozmiar okna odbiorcy wnd
2. rozmiar  okna przeciążenia cwnd
Wykorzystujemy okno o rozmiarze min{ wnd, cwnd }
cwnd zmienia się w zależności od zachowania się łącza (i innych
współbieżnych transmisji), odpowiada zajętości łącza
Sieci komputerowe (II UWr) Wykład 6 17 / 27
Kontrola przeciążeń cwnd
Uwagi upraszczające
Nie myślimy o bajtach, tylko o segmentach o rozmiarze MSS.
Liczymy wszystko w segmentach.
Zakładamy, że wnd = ".
Sieci komputerowe (II UWr) Wykład 6 18 / 27
Kontrola przeciążeń cwnd
Zmiana cwnd, wolny start
Na początku
ssthresh = "
cwnd = 1
tryb wolnego startu (dopóki cwnd d" ssthresh)
Wolny start
Za każdym potwierdzeniem zwiększamy 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ążeń cwnd
Zmiana cwnd, wolny start
Na początku
ssthresh = "
cwnd = 1
tryb wolnego startu (dopóki cwnd d" ssthresh)
Wolny start
Za każdym potwierdzeniem zwiększamy 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ążeń cwnd
Zmiana cwnd, unikanie kolizji
Kiedy cwnd > ssthresh
cwnd = cwnd + 1 (co turę = 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ążeń cwnd
Zmiana cwnd, podsumowanie
Pomijając krótkie odcinki wolnego startu, gra wygląda następująco:
Co turę (czas RTT) cwnd = cwnd + 1
Jeśli następuje utrata pakietu, to cwnd = cwnd/2.
Algorytm AIMD
additive increase,
multiplicative decrease
Pokazaliśmy  jak .
Ale  dlaczego ?
Obrazek ze stronyhttp://courseweb.sp.cs.cmu.edu/ cs395/2005/applications/ln/lecture24.html
Sieci komputerowe (II UWr) Wykład 6 21 / 27
Kontrola przeciążeń cwnd
Zmiana cwnd, podsumowanie
Pomijając krótkie odcinki wolnego startu, gra wygląda następująco:
Co turę (czas RTT) cwnd = cwnd + 1
Jeśli następuje utrata pakietu, to cwnd = cwnd/2.
Algorytm AIMD
additive increase,
multiplicative decrease
Pokazaliśmy  jak .
Ale  dlaczego ?
Obrazek ze stronyhttp://courseweb.sp.cs.cmu.edu/ cs395/2005/applications/ln/lecture24.html
Sieci komputerowe (II UWr) Wykład 6 21 / 27
Kontrola przeciążeń cwnd
Nasz model
Jeden kanał komunikacyjny
Całkowita przepustowość = K
n konkurujących komunikacji TCP
W każdym kroku: transmisja i wybiera prędkość przesyłania
danych xi " [0, K ].
n
Jeśli xi d" K , komunikacja powodzi się.
i=1
W przeciwnym przypadku segmenty są gubione.
Każdy uczestnik komunikacji wie, która z opcji zaszła (choć nie
n
zna wartości xi)
i=1
Sieci komputerowe (II UWr) Wykład 6 22 / 27
Kontrola przeciążeń cwnd
Co chcielibyśmy osiągnąć
n
1
Efektywne wykorzystanie łącza: xi jak najbliższe K .
i=1
2
Sprawiedliwy podział łącza: wszystkie xi jak najmniej się różniące.
3
Strategia dla każdej transmisji powinna być taka sama.
Sieci komputerowe (II UWr) Wykład 6 23 / 27
Kontrola przeciążeń cwnd
Model, cd.
Wybieramy funkcje fI : [0, B] [0, B], fD : [0, B] [0, B].
xi(t): wartość xi w kroku t.
Obliczanie wartości xi w kolejnym kroku
n
xi d" K =�! xi(t + 1) = fI(xi(t)) (dla wszystkich i)
i=1
n
xi > K =�! xi(t + 1) = fD(xi(t)) (dla wszystkich i)
i=1
Ograniczymy się do liniowych funkcji fI i fD.
Sieci komputerowe (II UWr) Wykład 6 24 / 27
Kontrola przeciążeń cwnd
Analiza
notatki, obrazki
Sieci komputerowe (II UWr) Wykład 6 25 / 27
Kontrola przeciążeń cwnd
Pokazaliśmy, że
Jedynym sensownym wyborem liniowych funkcji fI i fD jest
fI(z) e" z + aI, gdzie aI > 0 ,
fD(z) = bD � z, gdzie 0 < bD < 1 .
W TCP:
1
aI = MSS, bD =
2
Sieci komputerowe (II UWr) Wykład 6 26 / 27
Kontrola przeciążeń cwnd
Jeszcze jedna sztuczka
Fast retransmit
Normalnie segmenty są wysyłane ponownie, jeśli są
niepotwierdzone przez pewien czas
Jeśli dostajemy trzy takie same potwierdzenia z rzędu:ACK x, to
jest duża szansa, że segment zaczynający się od bajtuxzaginął
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