Plan całości wykładu
Wprowadzenie (2 wykłady)
Warstwa aplikacji (2 wykłady)
Warstwa transportu (2-3 wykłady)
Warstwa sieci (2-3 wykłady)
Warstwa łącza i sieci lokalne (3 wykłady)
Podstawy ochrony informacji (2-3 wykłady)
3-1
Plan czasowy wykładu i ćwiczeń
start
zadania programistyczne
(łącznie 16 punktów)
kolokwium (24 punktów)
zadania programistyczne i
zaliczenie ćwiczeń
egzamin (60 punktów)
3-2
Zadanie dodatkowe!
Do zarobienia 5 punktów:
wygrywa najlepsza odpowiedz
w terminie
Termin: do końca doby, w którym zostało ogłoszone (24h)
Zadanie:
do jakich sieci zagranicznych jest podłączony Internet w Polsce?
znalez
ć jak najwięcej sieci. Dla każdej z nich, pokazać ścieżkę (wynik
traceroute) oraz napisać, jaka organizacja zarządza systemem
autonomicznym.
do jakiej sieci zagranicznej Internet w Polsce został podłączony po raz
pierwszy w historii?
3-3
Literatura do warstwy transportu
Rozdział 3, Computer Networking: A Top-Down
Approach Featuring the Internet, wydanie 2
lub 3, J. Kurose, K. Ross, Addison-Wesley, 2004
Rozdziały 3.5, 6.2, 8.3, Sieci komputerowe 
podejście systemowe, L. Peterson, B. Davie,
Wyd. Nakom, Poznań, 2000
Rozdziały 17, 18, 20, 21, Biblia TCP/IP, tom 1, R.
Stevens, Wyd. RM, Warszawa, 1998
3-4
Warstwa transportu
Cele:
poznanie mechanizmów
zrozumienie
transportowych Internetu
podstawowych
UDP: transport
mechanizmów
bezpołączeniowy
transportowych:
TCP: transport połączeniowy
multipleksacja/demult
kontrola przeciążenia TCP
ipleksacja
niezawodna
komunikacja
kontrola przepływu
kontrola przeciążenia
3-5
Mapa wykładu
Usługi warstwy Transport połączeniowy:
transportu TCP
struktura segmentu
Multipleksacja i
niezawodna komunikacja
demultipleksacja
kontrola przepływu
Transport
zarządzanie połączeniem
bezpołączeniowy: UDP
Mechanizmy kontroli
Zasady niezawodnej
przeciążenia
komunikacji danych
Kontrola przeciążenia w
TCP
3-6
Usługi i protokoły warstwy transportu
logiczna komunikacja pomiędzy
procesami aplikacji działającymi
application
transport
na różnych hostach
network
data link
network
physical
protokoły transportowe działają
data link
network
physical
na systemach końcowych data link
physical
network
nadawca: dzieli komunikat
data link
physical network
aplikacji na segmenty,
data link
physical
przekazuje segmenty do
network
warstwy sieci
data link
physical
odbiorca: Å‚Ä…czy segmenty w
application
komunikat, który przekazuje
transport
network
do warstwy aplikacji
data link
physical
więcej niż jeden protokół
transportowy
Internet: TCP oraz UDP
3-7
l
o
g
i
c
a
l
en
d
-
en
d
t
r
a
n
s
p
o
r
t
Warstwy transportu i sieci
Analogia:
warstwa sieci: logiczna
komunikacja pomiędzy pracownicy firmy
hostami zamawiajÄ… pizzÄ™
warstwa transportu: procesy = pracownicy
logiczna komunikacja
komunikaty = pizze
pomiędzy procesami
hosty = firma i pizzeria
korzysta z oraz
protokół transportowy =
uzupełnia usługi warstwy
zamawiajÄ…cy pracownik
sieci
protokół sieci =
doręczyciel pizzy
3-8
Protokoły transportowe Internetu
niezawodna, uporzÄ…dkowana
application
komunikacja (TCP)
transport
network
kontrola przeciążenia
data link
network
physical
data link
network
physical
kontrola przepływu
data link
physical
tworzenie połączenia
network
data link
physical network
zawodna, nieuporzÄ…dkowana
data link
physical
komunikacja (UDP)
network
data link
proste rozszerzenie usługi
physical
 best-effort IP
application
transport
niedostępne usługi:
network
data link
gwarancje maksymalnego
physical
opóz
nienia
gwarancje minimalnej
przepustowości
3-9
l
o
g
i
c
a
l
en
d
-
en
d
t
r
a
n
s
p
o
r
t
Mapa wykładu
Usługi warstwy Transport połączeniowy:
transportu TCP
struktura segmentu
Multipleksacja i
niezawodna komunikacja
demultipleksacja
kontrola przepływu
Transport
zarządzanie połączeniem
bezpołączeniowy: UDP
Mechanizmy kontroli
Zasady niezawodnej
przeciążenia
komunikacji danych
Kontrola przeciążenia w
TCP
3-10
Multipleksacja/demultipleksacja
Multipleksacja u nadawcy
Demultipleksacja u odbiorcy
zbieranie danych z wielu gniazd,
przekazywanie otrzymanych
dodanie nagłówka (używanego
segmentów do właściwych gniazd
póz
niej przy demultipleksacji)
= gniazdo = proces
P4
aplikacji
P1 P2
P3 P1
aplikacji aplikacji
transportu
transportu transportu
sieci
sieci sieci
Å‚Ä…cza
Å‚Ä…cza Å‚Ä…cza
fizyczna
fizyczna fizyczna
host 3
host 2
host 1
3-11
Jak działa demultipleksacja
host otrzymuje pakiety IP
każdy pakiet ma adres IP
32 bity
nadawcy, adres IP
odbiorcy
port nadawcy port odbiorcy
każdy pakiet zawiera
jeden segment warstwy
inne pola nagłówka
transportu
każdy segment ma port
nadawcy i odbiorcy
dane aplikacji
(pamiętać: powszechnie
(komunikat)
znane numery portów dla
określonych aplikacji)
host używa adresu IP i portu
żeby skierować segment do
format segmentu TCP/UDP
odpowiedniego gniazda
3-12
Demultipleksacja bezpołączeniowa
Kiedy host otrzymuje
Gniazda sÄ… tworzone przez
segment UDP:
podanie numeru portu:
sprawdza port odbiorcy w
DatagramSocket mojeGniazdo1 =
segmencie
new DatagramSocket(99111);
kieruje segment UDP do
DatagramSocket mojeGniazdo2 =
gniazda z odpowiednim
new DatagramSocket(99222);
numerem portu
Gniazdo UDP jest
Datagramy IP z różnymi
identyfikowane przez parÄ™:
adresami IP lub portami
(adres IP odbiorcy, port odbiorcy)
nadawcy sÄ… kierowane do
tego samego gniazda
3-13
Demultipleksacja bezpołączeniowa (c.d.)
DatagramSocket gniazdoSerwera = new DatagramSocket(6428);
P1
P2 P1
P3
PN: 6428 PN: 6428
PO: 9157 PO: 5775
PN: 9157 PN: 5775
PO: 6428 PO: 6428
klient klient
serwer
IP:B
IP: A
IP: C
Port nadawcy (PN) jest  adresem zwrotnym .
3-14
Demultipleksacja połączeniowa
Gniazdo TCP jest określane Host serwera może
przez cztery wartości: obsługiwać wiele gniazd
TCP jednocześnie:
adres IP nadawcy
port nadawcy każde gniazdo ma inne 4
wartości
adres IP odbiorcy
port odbiorcy Serwery WWW majÄ…
oddzielne gniazda dla
Host odbierający używa
każdego klienta
wszystkich 4 wartości,
HTTP z nietrwałymi
żeby skierować segment do
połączeniami wymaga
właściwego gniazda
oddzielnego gniazda dla
Uwaga: host sprawdza
każdego żądania
także 5 wartość: protokół
3-15
Demultipleksacja połączeniowa (c.d)
P1P3
P6 P2
P1 P4 P5
PN: 5775
PO: 80
IP-N: B
IP-O: C
PN: 9157 PN: 9157
PO: 80 PO: 80
klient klient
serwer
IP-N: A IP-N: B IP: B
IP: A
IP: C
IP-O: C
IP-O: C
3-16
Demultipleksacja połączeniowa i
serwer wielowÄ…tkowy
P1P3
P2
P1 P4
PN: 5775
PO: 80
IP-N: B
IP-O:C
PN: 9157 PN: 9157
PO: 80 PO: 80
klient klient
serwer
IP-N: A IP-N: B IP: B
IP: A
IP: C
IP-O: C
IP-O: C
3-17
Porty komunikacyjne
Numer przydzielony przez system: 0
po wywołaniu bind system wybiera numer portu 1024-
5000 (znalez
ć go można po wywołaniu getsockname())
Porty zarezerwowane: 1-1023
Porty dobrze znane: 1-255 (/etc/services)
Porty zwyczajowo zarezerwowane dla Unixa BSD: 256-
511
Przydzielane przez rresvport: 512-1023
Porty wolne 1024-65535
3-18
Mapa wykładu
Usługi warstwy Transport połączeniowy:
transportu TCP
struktura segmentu
Multipleksacja i
niezawodna komunikacja
demultipleksacja
kontrola przepływu
Transport
zarządzanie połączeniem
bezpołączeniowy: UDP
Mechanizmy kontroli
Zasady niezawodnej
przeciążenia
komunikacji danych
Kontrola przeciążenia w
TCP
3-19
UDP: User Datagram Protocol [RFC 768]
 bez bajerów ,  odchudzony
protokół transportowy
Czemu istnieje UDP?
Internetu
nie ma inicjalizacji
usługa typu  best effort ,
połączenia (co może
segmenty UDP mogą zostać:
zwiększać opóz
nienie)
zgubione
prosty: nie ma stanu
dostarczone do aplikacji
połączenia u nadawcy ani
w zmienionej kolejności
odbiorcy
bezpołączeniowy:
mały nagłówek segmentu
nie ma inicjalizacji
między nadawcą i
nie ma kontroli
odbiorcÄ… UDP
przeciążenia: UDP może
każdy segment UDP jest
słać dane tak szybko, jak
obsługiwany niezależnie
chce
od innych
3-20
Więcej o UDP
Długość segmentu
UDP w bajtach
(z nagłówkiem)
Często używane do
32 bity
komunikacji strumieniowej
port nadawcy port odbiorcy
tolerujÄ…cej straty
suma kontrolna
długość
wrażliwej na opóz
nienia
Inne zastosowania UDP
DNS
SNMP
Dane aplikacji
niezawodna komunikacja po
(komunikat)
UDP: dodać niezawodność w
warstwie aplikacji
Praca domowa
Format segmentu UDP
3-21
Suma kontrolna UDP
Cel: odkrycie  błędów (n.p., odwróconych bitów) w
przesłanym segmencie
Nadawca:
Odbiorca:
traktuje zawartość
oblicza sumÄ™ kontrolnÄ…
segmentu jako ciÄ…g 16-
odebranego segmentu
bitowych liczb
sprawdza, czy obliczona suma
całkowitych
kontrolna jest równa tej,
suma kontrolna: dodawanie
która jest w nagłówku:
(i potem negacja sumy)
NIE  wykryto błąd
zawartości segmentu
TAK  Nie wykryto błędu.
nadawca wpisuje wartość
Ale może błąd jest i tak?
sumy kontrolnej do
Wrócimy do tego & .
odpowiedniego pola
nagłówka UDP
3-22
Przykład sumy kontrolnej
Uwaga
DodajÄ…c liczby, reszta z dodawania najbardziej
znaczących bitów musi zostać dodana do wyniku
(zawinięta, przeniesiona na początek)
Przykład: suma kontrolna dwóch liczb 16-bitowych
1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
zawinięcie
1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1
suma
1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0
suma kontrolna
1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1
3-23
Mapa wykładu
Usługi warstwy Transport połączeniowy:
transportu TCP
struktura segmentu
Multipleksacja i
niezawodna komunikacja
demultipleksacja
kontrola przepływu
Transport
zarządzanie połączeniem
bezpołączeniowy: UDP
Mechanizmy kontroli
Zasady niezawodnej
przeciążenia
komunikacji danych
Kontrola przeciążenia w
TCP
3-24
Zasady niezawodnej komunikacji danych
Ważne w warstwie aplikacji, transportu i łącza
Jeden z najważniejszych tematów w dziedzinie sieci!
Proces
warstwa Proces
odbiorcy
nadawcy
wyższa
dane
dane
deliver_data() dane
npk_send() dane
kanał niezawodny
warstwa Niezawodny Niezawodny
protokół protokół
niezawodna
transportowy transportowy
(nadawca) (odbiorca)
zpk_send() pakiet npk_recv() pakiet
kanał zawodny
warstwa
niższa
b) implementacja
a) udostępniana
usługi
usługa
charakterystyka zawodnego kanału określa złożoność niezawodnego
protokołu komunikacji (npk)
3-25
Niezawodna komunikacja (npk)
deliver_data():
npk_send(): wywoływany
wywoływany przez npk.
przez wyższą warstwę.
Przekazuje dane do
Przekazuje dane do
wyższej warstwy
przesłania do odbiorcy
dane
dane
deliver_data
npk_send
()
()
Niezawodny
Niezawodny
protokół
protokół
transportowy
warstwa transportowy
(odbiorca)
(nadawca)
niezawodna
npk_recv
pakiet
zpk_send pakiet
()
()
kanał zawodny
warstwa
niższa
nadawca odbiorca
npk_rcv(): wywoływany
zpk_send(): wywoływany
przez niższą warstwę, gdy
przez npk. Wysyła pakiet
pakiet zostanie odebrany po
przez zawodny kanał do
stronie odbiorcy
odbiorcy
3-26
Niezawodna komunikacja: poczÄ…tki
Co zrobimy:
stopniowo zaprojektujemy nadawcÄ™ i odbiorcÄ™
niezawodnego protokołu komunikacji (npk)
komunikacja danych tylko w jednÄ… stronÄ™
ale dane kontrolne w obie strony!
użyjemy automatów skończonych (AS) do
specyfikacji nadawcy, odbiorcy
zdarzenie powodujÄ…ce zmianÄ™ stanu
czynności wykonywane przy zmianie stanu
stan: w określonym
stan
 stanie , następny stan stan
zdarzenie (lub brak: ›)
1
jest jednoznacznie
2
czynnoÅ›ci (lub brak: ›)
określony przez
następne zdarzenie
3-27
Npk1.0: niezawodna komunikacja przez niezawodny kanał
używany kanał jest w pełni niezawodny
nie ma błędów bitowych
pakiety nie sÄ… tracone
oddzielne AS dla nadawcy, odbiorcy:
nadawca wysyła dane przez kanał
odbiorca odbiera dane z kanału
npk_rcv(packet)
npk_send(data)
Czekaj na Czekaj na
extract (packet,data)
wywołanie wywołanie
packet = make_pkt(data)
deliver_data(data)
z góry z dołu
zpk_send(packet)
nadawca
odbiorca
3-28
Npk2.0: kanał z błędami bitowymi
kanał może zmieniać bity w pakiecie
suma kontrolna pozwala rozpoznać błędy bitowe
pytanie: jak naprawić błąd:
potwierdzenia (ang. acknowledgement, ACKs): odbiorca
zawiadamia nadawcę, że pakiet jest dotarł bez błędu
negatywne potwierdzenia (NAKs): odbiorca zawiadamia
nadawcę, że pakiet ma błędy
nadawca retransmituje pakiet po otrzymaniu NAK
nowe mechanizmy w npk2.0:
rozpoznawanie błędów
informacja zwrotna od odbiorcy: komunikaty kontrolne
(ACK,NAK) odbiorca->nadawca
3-29
npk2.0: specyfikacja AS
npk_send(data)
snkpkt = make_pkt(data, checksum)
odbiorca
zpk_send(sndpkt)
npk_rcv(rcvpkt) &&
isNAK(rcvpkt)
Czekaj na
npk_rcv(rcvpkt) &&
Czekaj na
wywołanie
zpk_send(sndpkt corrupt(rcvpkt)
ACK lub
z góry
)
NAK
zpk_send(NAK)
npk_rcv(rcvpkt) && isACK(rcvpkt)
Czekaj na
›
wywołanie
z dołu
nadawca
npk_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
zpk_send(ACK)
3-30
npk2.0: działanie bez błędów
npk_send(data)
snkpkt = make_pkt(data, checksum)
zpk_send(sndpkt)
npk_rcv(rcvpkt) &&
isNAK(rcvpkt)
Czekaj na
Czekaj na
npk_rcv(rcvpkt) &&
ACK lub
wywołanie
zpk_send(sndpkt corrupt(rcvpkt)
NAK
z góry
)
zpk_send(NAK)
npk_rcv(rcvpkt) && isACK(rcvpkt)
Czekaj na
›
wywołanie
z dołu
npk_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
zpk_send(ACK)
3-31
npk2.0: działanie z błędami
npk_send(data)
snkpkt = make_pkt(data, checksum)
zpk_send(sndpkt)
npk_rcv(rcvpkt) &&
isNAK(rcvpkt)
Czekaj na
Czekaj na
npk_rcv(rcvpkt) &&
ACK lub
wywołanie
zpk_send(sndpkt corrupt(rcvpkt)
NAK
z góry
)
zpk_send(NAK)
npk_rcv(rcvpkt) && isACK(rcvpkt)
Czekaj na
›
wywołanie
z dołu
npk_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
zpk_send(ACK)
3-32
npk2.0 ma fatalny błąd!
Co siÄ™ stanie, gdy
Obsługa duplikatów:
ACK/NAK będzie miał
nadawca dodaje numer
błąd?
sekwencyjny do każdego pakietu
nadawca nie wie, co siÄ™
nadawca retransmituje aktualny
stało u odbiorcy!
pakiet, jeśli ACK/NAK ma błąd
nie można po prostu zawsze
odbiorca wyrzuca (nie
retransmitować: możliwe
przekazuje wyżej) zduplikowane
jest wysłanie pakietu
pakiety
podwójnie (duplikatu).
wstrzymaj i czekaj
Nadawca wysyła jeden pakiet,
potem czeka na odpowiedz

odbiorcy
3-33
npk2.1: nadawca, obsługuje błędne ACK/NAK
npk_send(data)
sndpkt = make_pkt(0, data, checksum)
zpk_send(sndpkt)
npk_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
Czekaj na Czekaj na
wywołanie ACK lub
isNAK(rcvpkt) )
z góry NAK
zpk_send(sndpkt)
numer=0 numer=0
npk_rcv(rcvpkt)
npk_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt)
&& isACK(rcvpkt)
›
›
Czekaj na Czekaj na
ACK lub wywołanie
NAK z góry
numer=1 numer=1
npk_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
npk_send(data)
isNAK(rcvpkt) )
sndpkt = make_pkt(1, data, checksum)
zpk_send(sndpkt)
zpk_send(sndpkt)
3-34
npk2.1: odbiorca, obsługuje błędne ACK/NAK
npk_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq0(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK, chksum)
npk_rcv(rcvpkt) && npk_rcv(rcvpkt) &&
zpk_send(sndpkt)
(corrupt(rcvpkt) (corrupt(rcvpkt)
sndpkt = make_pkt(NAK, chksum)
sndpkt = make_pkt(NAK, chksum)
zpk_send(sndpkt)
zpk_send(sndpkt)
Czekaj Czekaj
na wyw. na wyw.
npk_rcv(rcvpkt) &&
npk_rcv(rcvpkt) &&
z dołu z dołu
not corrupt(rcvpkt) &&
not corrupt(rcvpkt) &&
numer=0 numer=1
has_seq1(rcvpkt)
has_seq0(rcvpkt)
sndpkt = make_pkt(ACK, chksum)
sndpkt = make_pkt(ACK, chksum)
zpk_send(sndpkt)
zpk_send(sndpkt)
npk_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq1(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK, chksum)
zpk_send(sndpkt)
3-35
npk2.1: dyskusja
Nadawca: Odbiorca:
Dodaje numer sekwencyjny musi sprawdzać, czy
do pakietu odebrany pakiet jest
duplikatem
Dwa numery (0,1) wystarczÄ….
stan wskazuje, czy oczekuje
Dlaczego?
numeru sekwencyjnego
musi sprawdzać, czy
0, czy 1
ACK/NAK jest poprawny
uwaga: odbiorca może nie
dwa razy więcej stanów
wiedzieć czy ostatni
(niż w npk2.0)
ACK/NAK został poprawnie
stan musi  pamiętać aktualny
odebrany przez nadawcÄ™
numer sekwencyjny (0 lub 1)
3-36
npk2.2: protokół bez negatywnych
potwierdzeń (NAK)
ta sama funkcjonalność co w npk2.1, używając tylko
zwykłych potwierdzeń (ACK)
zamiast NAK, odbiorca wysyła ACK za ostatni
poprawnie odebrany pakiet
odbiorca musi dodać numer sekwencyjny pakietu,
który jest potwierdzany
powtórne ACK u nadawcy powoduje tę samą czynność
co NAK: retransmisję ostatnio wysłanego pakietu
3-37
npk2.2: fragmenty nadawcy, odbiorcy
npk_send(data)
sndpkt = make_pkt(0, data, checksum)
zpk_send(sndpkt)
npk_rcv(rcvpkt) &&
Czekaj na ( corrupt(rcvpkt) ||
Czekaj na
wywołanie
isACK(rcvpkt,1) )
ACK
z góry
zpk_send(sndpkt)
numer=0
numer=0
fragment AS
npk_rcv(rcvpkt)
nadawcy
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt,0)
npk_rcv(rcvpkt) &&
(corrupt(rcvpkt) ||
›
Czekaj na
fragment AS
has_seq1(rcvpkt))
wywołanie
odbiorcy
z dołu
zpk_send(sndpkt)
numer=0
npk_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq1(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK1, chksum)
3-38
zpk_send(sndpkt)
npk3.0: kanał z błędami oraz stratami
Nowe założenie: Podejście: nadawca czeka
używany kanał może przez  rozsądny czas na
gubić pakiety potwierdzenie ACK
(z danymi lub ACK)
retransmituje, jeśli nie otrzyma
ACK w tym czasie
suma kontrolna, numery
sekwencyjne, jeśli pakiet (lub ACK) jest tylko
potwierdzenia, opóz
niony, ale nie stracony:
retransmisje będą
retransmisja będzie
pomocne, ale nie
duplikatem, ale za pomocÄ…
wystarczÄ…
numerów sekwencyjnych już
to obsługujemy
odbiorca musi określić numer
sekwencyjny pakietu, który
jest potwierdzany
wymagany jest licznik czasu
3-39
npk3.0 nadawca
npk_send(data)
npk_rcv(rcvpkt) &&
sndpkt = make_pkt(0, data, checksum)
zpk_send(sndpkt)
( corrupt(rcvpkt) ||
start_timer
isACK(rcvpkt,1) )
npk_rcv(rcvpkt) ›
Czekaj na
Czekaj
›
wywołanie
na ACK
timeout
z góry
zpk_send(sndpkt)
numer=0 numer=0
start_timer
npk_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
npk_rcv(rcvpkt)
&& isACK(rcvpkt,1)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt,0)
stop_timer
stop_timer
Czekaj na
Czekaj
wywołanie
na ACK
timeout
z góry
zpk_send(sndpkt)
numer=1 numer=1
npk_rcv(rcvpkt)
start_timer
›
npk_send(data)
npk_rcv(rcvpkt)
sndpkt = make_pkt(1, data, checksum)
&&
zpk_send(sndpkt)
( corrupt(rcvpkt) ||
start_timer
isACK(rcvpkt,0) )
›
3-40
npk3.0 w działaniu
nadawca odbiorca
nadawca odbiorca
pkt0
wyślij pkt0
pkt0
wyślij pkt0
odbierz pkt0
odbierz pkt0
ACK0
wyślij ACK0
ACK0
wyślij ACK0 odbierz ACK0
odbierz ACK0
pkt1
wyślij pkt1
pkt1
wyślij pkt1
(strata)
odbierz pkt1
timeout, retransmituj
ACK1
wyślij ACK1
pkt1
odbierz ACK1
pkt1
wyślij pkt0 pkt0
odbierz pkt1
odbierz pkt0
ACK1
wyślij ACK1
ACK0
odbierz ACK1
wyślij ACK0
pkt0
wyślij pkt0
odbierz pkt2
ACK0
wyślij ACK0
działanie bez strat
działanie ze stratą
pakietu
3-41
npk3.0 w działaniu
nadawca odbiorca
nadawca odbiorca
pkt0
wyślij pkt0 pkt0
wyślij pkt0
odbierz pkt0
odbierz pkt0
ACK0
ACK0
wyślij ACK0
wyślij ACK0
odbierz ACK0
odbierz ACK0
pkt1
wyślij pkt1
pkt1
wyślij pkt1
odbierz pkt1
odbierz pkt1
ACK1
wyślij ACK1
wyślij ACK1
timeout, retransmituj
(strata)
timeout, retransmituj
pkt1
pkt1
pkt1
ACK1
odbierz pkt1
odbierz pkt1
pkt1
wykryj duplikat
ACK1
wyślij ACK1
wyślij ACK1
odbierz ACK1
odbierz ACK1 ACK1
pkt0 odbierz pkt0
pkt2
wyślij pkt2
wyślij pkt2
wyślij ACK0
odbierz pkt2
ACK2
wyślij ACK2
ACK0
Nic siÄ™ nie
dzieje!
działanie ze stratą ACK
za wczesny timeout
3-42
Wydajność npk3.0
npk3.0 działa, ale wydajność ma bardzo kiepską
przykład: link 1 Gb/s, opóz
nienie k-k 15 ms, pakiet 1KB:
L (rozmiar pakietu w b)
8kb/pkt
Ttransmisji
=
=
= 8 mikros.
R (przepustowość, b/s)
109 b/s
.008
L / R
W 0.00027
= =
=
nadawcy
30.008
RTT + L / R
microsec
onds
W nadawcy: wykorzystanie  procent czasu, w jakim nadawca nadaje
pakiet rozmiaru 1KB co 30 ms -> przepustowość 33kB/s przez
Å‚Ä…cze 1 Gb/s
protokół ogranicza wykorzystanie fizycznych zasobów łącza!
3-43
npk3.0: działanie wyślij i czekaj
nadawca odbiorca
pierwszy bit pakietu wysłany, t =0
ostatni bit pakietu wysłany, t = L / R
pierwszy bit odebrany
RTT
ostatni bit odebrany, wyślij ACK
ACK odebrane, wyślij
następny pakiet, t = RTT + L / R
.008
L / R
W 0.00027
= =
=
nadawcy
30.008
RTT + L / R
microsec
onds
3-44
Protokoły "wysyłające grupowo"
Wysyłanie grupowe: nadawca wysyła wiele pakietów
bez czekania na potwierdzenie
trzeba zwiększyć zakres numerów sekwencyjnych
trzeba mieć bufor u nadawcy i/lub odbiorcy
Dwa podstawowe rodzaje protokołów wysyłania
grupowego: wróć o N, selektywne powtarzanie
3-45
Wysyłanie grupowe: zwiększone
wykorzystanie
nadawca odbiorca
pierwszy bit pakietu
wysłany, t =0
ostatni bit pakietu
wysłany, t = L / R
pierwszy bit odebrany
ostatni bit odebrany, wyślij ACK
RTT
ostatni bit 2giego pakietu odebrany,
wyślij ACK
ostatni bit 3ciego pakietu odebrany,
ACK odebrane, wyślij następny
wyślij ACK
pakiet, t = RTT + L / R
Trzykrotnie zwiększone
wykorzystanie!
.024
3 * L / R
W 0.0008
= =
=
nadawcy
30.008
RTT + L / R
microsecon
ds
3-46
Wróć o N (WN)
Nadawca:
k bitów na numer sekwencyjny w nagłówku pakietu
wysyła  okno co najwyżej N kolejnych, niepotwierdzonych pakietów
poczÄ…tek okna
(pocz_okn)następny numer
sekwencyjny
już
gotowy, nie
(nast_num)
potwierdzony
wysłany
wysłany, nie
nie gotowy
potwierdzony
rozmiar okna: N
ACK(n): potwierdza wszystkie pakiety aż do (i łącznie z) pakietem
o numerze sekwencyjnym n -  skumulowany ACK
może otrzymywać duplikaty potwierdzeń (patrz odbiorca)
potrzebny jest zegar  jeden dla całego okna
timeout: retransmisja wszystkich niepotwierdzonych pakietów w
oknie, czyli od pocz_okn do nast_num
3-47
WN: rozszerzony AS nadawcy
npk_send(dane)
if (nast_num < pocz_okn+N)
{
sndpkt[nast_num] = make_pkt(nast_num, dane, suma_kontr)
zpk_send(sndpkt[nast_num])
if (pocz_okn == nast_num)
start_timer
nast_num++
}
else
›
refuse_data(dane)
pocz_okn=1
nast_num=1
timeout
start_timer
Czekaj
zpk_send(sndpkt[pocz_okn])
zpk_send(sndpkt[pocz_okn+1])
npk_rcv(rcvpkt)
&
&& corrupt(rcvpkt)
zpk_send(sndpkt[nast_num-1])
npk_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
pocz_okn = numer_ACK(rcvpkt) + 1
If (pocz_okn == nast_num)
stop_timer
else
start_timer
3-48
WN: rozszerzony AS odbiorcy
default
zpk_send(sndpkt)
npk_rcv(rcvpkt)
&& notcurrupt(rcvpkt)
&& hasseqnum(rcvpkt,expectedseqnum)
›
Czekaj
extract(rcvpkt,data)
expectedseqnum=1
deliver_data(data)
sndpkt =
sndpkt = make_pkt(expectedseqnum,ACK,chksum)
make_pkt(expectedseqnum,ACK,chksum)
zpk_send(sndpkt)
expectedseqnum++
tylko ACK: zawsze wysyła ACK dla ostatniego poprawnie
odebranego pakietu spośród pakietów odebranych
w kolejności
może generować zduplikowane ACK
trzeba pamiętać tylko expectedseqnum
pakiety nie w kolejności:
sÄ… wyrzucane -> nie ma buforowania u odbiorcy!
Wysyłane jest ponownie ACK z numerem sekwencyjnym
ostatniego pakiety odebranego w kolejności
3-49
nadawca odbiorca
WN w
pkt0
wyślij pkt0
działaniu
odbierz pkt0
pkt1
wyślij pkt1
pierwsze
wyślij ACK0
okno
odbierz pkt1
N = 4 pkt2
wyślij pkt2
wyślij ACK1
pkt3 (strata)
wyślij pkt3
czekaj
odbierz pkt3
ACK0
i odrzuć go!
odbierz ACK0 ACK1
wyślij ACK1
wyślij pkt4
przesuwanie pkt4
odbierz pkt4
okna
odbierz ACK1
i odrzuć go!
pkt5
po ACK
wyślij pkt5
wyślij ACK1
odbierz pkt5
i odrzuć go!
timeout pkt2
wyślij ACK1
pkt2
wyślij pkt2
odbierz pkt2
pkt3
wyślij pkt3
retransmisje
wyślij ACK2
wyślij pkt4
pkt4
odbierz pkt3
wyślij pkt5
pkt5
wyślij ACK3
3-50