Protokoły Okna Przesuwnego

Wprowadzenie: ograniczenia Stop-and-Wait

Protokół Stop-and-Wait wysyła pojedynczą ramkę i czeka na potwierdzenie przed wysłaniem następnej. W połączeniu z kontrolą integralności, timerem i retransmisją może zapewnić niezawodną dostawę, a jednocześnie ogranicza liczbę ramek obciążających odbiorcę. Wydajność spada jednak na łączach o dużym opóźnieniu propagacji i wysokim Czasie Podróży w Obie Strony (RTT). Kanał komunikacyjny pozostaje wtedy przez większość czasu bezczynny, ponieważ nadawca czeka na powrót potwierdzenia (ACK).

Sposobem na ograniczenie oczekiwania jest przesyłanie potokowe (pipelining): nadawca wysyła wiele ramek przed otrzymaniem potwierdzeń. Dane mogą wtedy zajmować łącze w czasie propagacji wcześniejszych ramek, co zwiększa jego wykorzystanie. Rozmiar okna dobiera się do iloczynu przepustowości i opóźnienia, a także do pojemności buforów. Zbyt małe okno nadal powoduje oczekiwanie, a zbyt duże zwiększa wymagania buforowania i utrudnia kontrolę numerów sekwencyjnych. Protokoły realizujące tę zasadę określa się jako protokoły przesuwnego okna. Mechanizmy tego typu występują między innymi w TCP i HDLC, choć szczegóły potwierdzania i retransmisji zależą od protokołu.

Podstawowe mechanizmy przesuwnego okna

Typowe protokoły przesuwnego okna korzystają z numerów sekwencyjnych, okien nadawczych i odbiorczych oraz potwierdzeń. Elementy te pozwalają zarządzać wieloma ramkami znajdującymi się jednocześnie w transmisji. Potwierdzenie skumulowane obejmuje ciągły prefiks, a selektywne wskazuje pojedyncze ramki. Wybór wpływa na buforowanie i retransmisję. W TCP numeracja dotyczy oktetów, a w protokołach łącza często ramek. Zasada przesuwania pozostaje podobna.

1. Numery Sekwencyjne

Jeśli wiele ramek może znajdować się w sieci w tym samym czasie, protokół musi rozróżniać je w obrębie danego połączenia. Służy do tego numer sekwencyjny umieszczany w nagłówku ramki. Numery te służą do:

• Wskazywania brakujących ramek po wykryciu luki w numeracji. Uszkodzenia wykrywa kontrola integralności.
• Powiązania potwierdzenia z określoną ramką lub zakresem ramek.
• Porządkowania ramek, jeśli dany protokół buforuje ramki odebrane poza kolejnością.
• Wykrywania i odrzucania zduplikowanych ramek.

Pole numeru sekwencyjnego ma skończoną liczbę bitów, $k$, więc numery mieszczą się w zakresie od 0 do $2^k - 1$, a następnie zawijają się (np. dla $k=3$ sekwencja to 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, ...). Arytmetyka modularna wymaga ograniczenia rozmiaru okna, aby po zawinięciu numerów starych i nowych ramek nie można było pomylić. Dokładny warunek zależy od wariantu, ponieważ Go-Back-N i Selective Repeat inaczej traktują ramki poza kolejnością. Implementacja musi też określać sposób porównywania zawiniętych numerów. Samo porównanie wartości liczbowych nie wystarcza.

Perspektywa Nadawcy: Okno Nadawcze

Nadawca utrzymuje zakres numerów sekwencyjnych znany jako okno nadawcze. Okno określa ramki, które może wysłać bez oczekiwania na wcześniejsze potwierdzenia. Jego rozmiar, często oznaczany jako $W_S$, wpływa na liczbę ramek znajdujących się jednocześnie w transmisji.

Przestrzeń numerów sekwencyjnych z perspektywy nadawcy jest podzielona na cztery regiony:

1. Ramki Wysłane i Potwierdzone: Te ramki pomyślnie zakończyły swoją podróż. Znajdują się za oknem.
2. Ramki Wysłane, ale Jeszcze Niepotwierdzone: Są to ramki „w locie”, aktualnie przemieszczające się przez sieć. Zajmują one okno nadawcze. Nadawca musi buforować te ramki w swojej pamięci na wypadek, gdyby musiały zostać retransmitowane.
3. Dozwolone Ramki, Jeszcze Niewysłane: Te ramki mają numery sekwencyjne, które mieszczą się w dozwolonym oknie, ale nie zostały jeszcze wysłane. Nadawca może je wysłać, gdy tylko będzie gotowy.
4. Ramki Poza Oknem: Tych ramek nie można wysłać, dopóki okno się nie „przesunie”.

Okno przesuwa się po otrzymaniu potwierdzenia obejmującego najstarszą niepotwierdzoną ramkę, czyli tę przy jego dolnej granicy. Potwierdzenie skumulowane może objąć kilka kolejnych ramek, dlatego dolna granica przesuwa się wtedy o odpowiednią liczbę pozycji i pojawiają się nowe numery dozwolone do wysłania. Potwierdzenie zwalnia też bufory, które przechowywały kopie ramek potrzebne do retransmisji.

Perspektywa Odbiorcy: Okno Odbiorcze

Odbiorca również utrzymuje okno odbiorcze o rozmiarze $W_R$. Okno to definiuje zakres numerów sekwencyjnych dla ramek, które jest on aktualnie gotów zaakceptować. Jego rozmiar ogranicza ilość danych spoza kolejności przechowywanych w buforze i może zależeć od dostępnej pamięci odbiorcy.

Reakcja na ramkę z numerem spoza okna odbiorczego zależy od protokołu. Ramka może zostać odrzucona albo potraktowana jako duplikat. Dla ramek z numerem wewnątrz okna odbiorca stosuje reguły danego wariantu. Po zaakceptowaniu ramki wyznaczającej początek ciągłego bloku przekazuje dostępne dane do warstwy sieciowej i przesuwa okno do następnego oczekiwanego numeru. W Selective Repeat ramki po luce pozostają w buforze do czasu jej uzupełnienia.

Wariant 1 Przesuwnego Okna: Go-Back-N (GBN)

Go-Back-N jest prostszym wariantem przesuwnego okna. Odbiorca wymaga kolejności numerów i nie buforuje ramek przychodzących po luce. Może potwierdzać następną oczekiwaną wartość, dzięki czemu jedno potwierdzenie obejmuje ciągły prefiks strumienia.

Główna zasada: W typowym Go-Back-N okno odbiorcze ($W_R$) ma rozmiar dokładnie 1. Odbiorca oczekuje jednej konkretnej ramki, następnej w sekwencji, i nie buforuje ramek przychodzących w innej kolejności.

Proces i Odzyskiwanie po Błędach w GBN

• Zachowanie Nadawcy: Nadawca może wysłać do $N$ ramek (rozmiar swojego okna) bez czekania na potwierdzenie.
• Zachowanie odbiorcy: Odbiorca oczekuje ramki o numerze sekwencyjnym k. Jeśli ramka k dotrze poprawnie, jest akceptowana, a odbiorca odsyła potwierdzenie skumulowane. Następnie oczekuje ramki k+1.
• Obsługa błędów: Jeśli ramka k zaginie albo dotrze inna ramka, na przykład k+1, odbiorca odrzuca ramkę poza kolejnością i ponownie wysyła potwierdzenie wskazujące k jako następną oczekiwaną ramkę.
• Retransmisja: Nadawca monitoruje najstarszą niepotwierdzoną ramkę lub stosuje równoważny timer. Po wygaśnięciu timera dla k retransmituje ramkę k i wszystkie późniejsze ramki, które wcześniej wysłał, czyli k+1, k+2 i kolejne. Dzieje się tak także wtedy, gdy późniejsze ramki dotarły poprawnie, ponieważ odbiorca odrzucił je jako przychodzące poza kolejnością.

GBN: Zalety i Wady

Zalety: Logika odbiorcy jest prosta, ponieważ nie zarządza buforem ramek spoza kolejności. Wystarcza mu numer sekwencyjny następnej oczekiwanej ramki.

Wady: Protokół traci wydajność na łączach o dużym opóźnieniu lub wysokim wskaźniku błędów. Jedna utracona ramka może wymusić retransmisję wielu kolejnych ramek, co obniża wykorzystanie przepustowości. Przy małym oknie nadawca może dodatkowo pozostawiać łącze bezczynne podczas oczekiwania na ACK.

Wariant 2 Przesuwnego Okna: Powtórzenie Selektywne (SR)

Powtórzenie selektywne (Selective Repeat lub Selective Reject) ogranicza retransmisje względem Go-Back-N, lecz wymaga bardziej złożonego zarządzania stanem. Odbiorca może przechowywać ramki odebrane poza kolejnością. Musi przechowywać informacje o każdej zaakceptowanej ramce i rozróżniać zawiniętą wartość od starszej kopii.

Główna zasada: W Selective Repeat okno odbiorcze ($W_R$) jest większe niż 1, często równe oknu nadawcy ($W_S$). Odbiorca może akceptować i buforować poprawnie odebrane ramki, nawet gdy dotrą poza kolejnością.

Proces i Odzyskiwanie po Błędach w SR

• Zachowanie Nadawcy: Tak samo jak w GBN, nadawca może wysłać do $N$ ramek bez czekania na potwierdzenie.
• Zachowanie odbiorcy: Odbiorca utrzymuje bufor dla swojego okna. Gdy ramka o numerze k dotrze bez błędów i mieści się w oknie, akceptuje ją, zapisuje w buforze i odsyła potwierdzenie selektywne dla k.
• Obsługa błędów: Jeśli timer określonej ramki, na przykład k, wygaśnie, nadawca może retransmitować tylko tę ramkę. Potwierdzenia późniejszych ramek, takich jak k+1 i k+2, mogą wskazywać, że dotarły one poprawnie.
• Retransmisja: Nadawca retransmituje tylko ramkę, której brakuje, na przykład k. Po jej otrzymaniu odbiorca wypełnia lukę w buforze. Jeśli powstaje ciągły blok od początku okna, przekazuje go do warstwy sieciowej i przesuwa okno.

SR: Zalety, wady i ograniczenie rozmiaru okna

Zalety: Zwykle wykorzystuje łącze lepiej niż GBN, szczególnie przy dużym opóźnieniu i podwyższonym wskaźniku błędów. Ogranicza retransmisje do ramek, których rzeczywiście brakuje, lecz wymaga bufora po stronie odbiorcy.

Wady: Wymaga bardziej złożonej logiki po obu stronach. Nadawca śledzi timery i statusy potwierdzeń poszczególnych ramek, a odbiorca buforuje ramki spoza kolejności i składa z nich strumień danych.

Ograniczenie rozmiaru okna: W klasycznym Selective Repeat, aby po zawinięciu numerów rozróżnić stare i nowe ramki, suma rozmiarów okien nie może przekraczać liczby dostępnych numerów ($W_S + W_R \le 2^k$). Gdy oba okna są równe, często przyjmuje się połowę przestrzeni numerów: $W_S = W_R = 2^{k-1}$.