Wprowadzenie: Jak Przezwyciężyć Oczekiwanie w Stop-and-Wait

W naszej dyskusji o kontroli przepływu przeanalizowaliśmy protokół Stop-and-Wait. Jest on doskonale niezawodny – nadawca wysyła pojedynczą ramkę i czeka na potwierdzenie przed wysłaniem następnej. Ta prosta zasada całkowicie zapobiega zalewaniu odbiorcy przez nadawcę. Jednak jego wydajność jest fatalna, szczególnie na łączach o dużym opóźnieniu propagacji i wysokim Czasie Podróży w Obie Strony (RTT). Kanał komunikacyjny spędza większość czasu w stanie bezczynności, podczas gdy nadawca czeka na powrót potwierdzenia (ACK). To jak prowadzenie rozmowy, w której po każdym zdaniu musisz czekać na „tak, zrozumiałem” – uprzejme, ale bolesne wolne.

Oczywistym rozwiązaniem tej nieefektywności jest przesyłanie potokowe (pipelining): pozwolenie nadawcy na wysłanie wielu ramek, zanim będzie musiał zatrzymać się i czekać na potwierdzenie. Pozwala to na wypełnienie kanału komunikacyjnego, czyli „potoku”, danymi, co radykalnie zwiększa jego wykorzystanie i przepustowość. Rodzina protokołów implementująca tę strategię jest znana jako Protokoły Przesuwnego Okna. Są one fundamentem niezawodnego, wysokowydajnego transferu danych w nowoczesnych sieciach, używanym przez protokoły takie jak TCP i HDLC.

Mechanizmy Rdzeniowe Przesuwnego Okna

Wszystkie protokoły przesuwnego okna dzielą wspólny zestaw fundamentalnych koncepcji, które pozwalają im zarządzać wieloma ramkami „w locie” jednocześnie.

1. Numery Sekwencyjne

Jeśli wiele ramek może znajdować się w sieci w tym samym czasie, potrzebujemy sposobu, aby unikalnie zidentyfikować każdą z nich. Osiąga się to poprzez dodanie numeru sekwencyjnego do nagłówka każdej ramki. Numery te są używane do:

• Identyfikacji ramek, które zostały utracone lub uszkodzone podczas transmisji.
• Potwierdzania odbioru konkretnych ramek.
• Ponownego uporządkowania ramek, które mogły dotrzeć do celu w niewłaściwej kolejności.
• Wykrywania i odrzucania zduplikowanych ramek.

Pole numeru sekwencyjnego ma skończoną liczbę bitów, $k$, co oznacza, że 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, ...). Ta arytmetyka modularna jest wystarczająca, o ile liczba ramek w locie jest mniejsza niż całkowita liczba dostępnych numerów sekwencyjnych.

Perspektywa Nadawcy: Okno Nadawcze

Nadawca utrzymuje zakres numerów sekwencyjnych znany jako okno nadawcze. Okno to reprezentuje zbiór ramek, które ma on prawo wysłać. Rozmiar tego okna, często oznaczany jako $W_S$, jest krytycznym parametrem.

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”.

Akcja „przesuwania” następuje, gdy nadawca otrzymuje potwierdzenie dla najstarszej niepotwierdzonej ramki (tej na dolnym krańcu okna). Potwierdzenie to pozwala nadawcy przesunąć dolną granicę swojego okna do przodu, wprowadzając tym samym nowe, „dozwolone” numery sekwencyjne do okna i umożliwiając wysłanie większej liczby ramek.

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ć.

Każda ramka, która przybywa z numerem sekwencyjnym spoza okna odbiorczego, jest odrzucana. W przypadku ramek przybywających z numerem sekwencyjnym wewnątrz okna, zachowanie odbiorcy zależy od konkretnego protokołu przesuwnego okna, który jest używany. Gdy odbiorca zaakceptuje ramkę na dolnej granicy swojego okna, przekazuje dane do warstwy sieciowej i „przesuwa” swoje okno do przodu do następnego oczekiwanego numeru sekwencyjnego.

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

Go-Back-N jest prostszym, ale bardziej surowym z dwóch głównych protokołów przesuwnego okna. Opiera się na zasadzie wymagającej od odbiorcy idealnej kolejności.

Główna Zasada: Odbiorca ma rozmiar okna ($W_R$) wynoszący dokładnie 1. Oznacza to, że w danym momencie oczekuje tylko jednej konkretnej ramki – następnej w sekwencji. Nie ma mechanizmu buforowania ramek, które docierają w niewłaściwej 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 dla `k`. Następnie aktualizuje swoje oczekiwanie na ramkę `k+1`.
• Obsługa Błędów („Wróć się”): Jeśli ramka `k` zostanie utracona, lub jeśli dotrze jakakolwiek inna ramka niż `k` (np. `k+1`, `k+2`), odbiorca podejmuje surową akcję: odrzuca nieprawidłową ramkę i ponownie wysyła potwierdzenie dla ostatniej poprawnie odebranej ramki (`k-1`).
• Retransmisja: Nadawca ma licznik czasu dla każdej niepotwierdzonej ramki. W końcu jego licznik dla utraconej ramki `k` wygaśnie. W tym momencie nadawca „wraca się” do numeru sekwencyjnego `k` i retransmituje ramkę `k` i wszystkie kolejne ramki, które już wysłał (tj. `k+1`, `k+2`, itd.). Dzieje się tak nawet, jeśli ramki `k+1` i `k+2` pierwotnie dotarły poprawnie – odbiorca już je odrzucił, ponieważ dotarły w złej kolejności.

GBN: Zalety i Wady

Zalety: Logika odbiorcy jest niezwykle prosta, ponieważ nie musi on zarządzać złożonymi buforami dla ramek spoza kolejności. Musi przechowywać tylko jedną zmienną: numer sekwencyjny następnej oczekiwanej ramki.

Wady: Jest wysoce nieefektywny, zwłaszcza na łączach o długim opóźnieniu i wysokim wskaźniku błędów. Pojedyncza utracona ramka może spowodować retransmisję dużej liczby kolejnych, poprawnych ramek, marnując znaczną część przepustowości.

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

Powtórzenie Selektywne (Selective Repeat lub Selective Reject) to bardziej inteligentny i wydajny – ale także bardziej złożony – protokół przesuwnego okna. Został zaprojektowany, aby naprawić marnotrawstwo przepustowości charakterystyczne dla Go-Back-N.

Główna Zasada: Odbiorca ma rozmiar okna ($W_R$) większy niż 1 (często równy rozmiarowi okna nadawcy, $W_S$). Może on akceptować i buforować poprawnie odebrane ramki, nawet jeśli dotrą w niewłaściwej 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 całego swojego okna. Gdy ramka z numerem sekwencyjnym `k` dotrze bezbłędnie, a `k` mieści się w jego oknie odbiorczym, akceptuje ją, przechowuje w buforze i odsyła potwierdzenie selektywne dla ramki `k`.
• Obsługa Błędów („Selektywna”): Jeśli licznik czasu nadawcy dla określonej ramki (np. ramki `k`) wygaśnie, wie on, że tylko ta konkretna ramka została utracona (ponieważ mógł otrzymać SACKi dla późniejszych ramek, jak `k+1` i `k+2`).
• Retransmisja: Nadawca retransmituje tylko tę pojedynczą ramkę, która została utracona (ramka `k`). Gdy odbiorca otrzyma retransmitowaną ramkę `k`, wypełnia lukę w swoim buforze. Jeśli ma teraz ciągły blok ramek od początku swojego okna, może dostarczyć ten blok do warstwy sieciowej i przesunąć swoje okno do przodu.

SR: Zalety, Wady i Kluczowe Ograniczenie

Zalety: Znacznie wydajniejszy niż GBN, szczególnie na łączach o wysokim opóźnieniu i dużym wskaźniku błędów („długie grube sieci”). Minimalizuje niepotrzebne retransmisje, co prowadzi do znacznie wyższej przepustowości.

Wady: Wymaga znacznie bardziej złożonej logiki po obu stronach. Nadawca musi zarządzać licznikami czasu i statusami potwierdzeń dla każdej indywidualnej ramki. Odbiorca potrzebuje bardziej skomplikowanego systemu buforowania, aby zarządzać ramkami spoza kolejności i ponownie składać strumień danych.

Ograniczenie Rozmiaru Okna: Aby uniknąć niejednoznaczności między starymi a nowymi oknami po zawinięciu się numerów sekwencyjnych, suma rozmiarów okien nadawcy i odbiorcy nie może być większa niż całkowita liczba dostępnych numerów sekwencyjnych ($W_S + W_R \le 2^k$). Powszechną, bezpieczną implementacją jest ustawienie rozmiarów okien nadawcy i odbiorcy na połowę przestrzeni numerów sekwencyjnych: $W_S = W_R = 2^{k-1}$.