Protokół Stop-and-Wait

Podstawowe wyzwanie: niezawodna komunikacja przez zawodne medium

Jednym z zadań warstwy łącza danych może być zapewnienie niezawodnego transferu między bezpośrednio połączonymi urządzeniami. Nie każda technologia łącza zapewnia taką usługę, dlatego mechanizm ARQ musi być określony przez konkretny protokół. Medium fizyczne, takie jak kabel miedziany, światłowód lub kanał radiowy, jest podatne na zakłócenia. Sygnały mogą zostać zniekształcone przez szum, osłabione wraz z odległością albo utracone wskutek chwilowych interferencji. Powstają dwa problemy:

1. Uszkodzone ramki: Jak odbiorca wykrywa zmianę danych względem ramki wysłanej przez nadawcę?
2. Utracone ramki: Jeśli ramka albo jej potwierdzenie nie dotrze, jak nadawca wykrywa potrzebę retransmisji?

Jedną z najprostszych odpowiedzi jest protokół Stop-and-Wait, czyli podstawowa odmiana ARQ (Automatic Repeat reQuest). Kontrola FCS lub CRC wykrywa uszkodzenie, lecz sama nie odzyskuje ramki. Czysty wariant ma małą wydajność na łączach o dużym iloczynie przepustowości i opóźnienia. Jego potwierdzenia, timery i retransmisje pomagają zrozumieć działanie TCP, chociaż TCP korzysta z okna przesuwnego i własnych reguł sterowania.

Główna zasada Stop-and-Wait

Działanie protokołu można sprowadzić do jednej zasady po stronie nadawcy:

Ta zasada ogranicza liczbę niepotwierdzonych ramek, więc pełni funkcję kontroli przepływu. W połączeniu z kontrolą integralności i retransmisją zapewnia też kontrolę błędów. Nadawca przechodzi do kolejnej ramki dopiero po otrzymaniu potwierdzenia.

Stop-and-Wait w działaniu: scenariusz bez błędów

Rozważmy scenariusz, w którym kanał nie gubi ramek i nie zgłasza błędów kontroli integralności.

1. Krok 1: Nadawca Wysyła Ramkę: Nadawca (Węzeł A) pobiera pierwszą porcję danych, zamyka ją w ramce z numerem sekwencyjnym 0 i wysyła ją do odbiorcy (Węzeł B).
2. Krok 2: Nadawca Uruchamia Licznik Czasu: Natychmiast po wysłaniu ramki, Węzeł A uruchamia licznik czasu (timeout). Ten licznik działa jak zabezpieczenie.
3. Krok 3: Odbiorca Otrzymuje Ramkę: Po pewnym opóźnieniu propagacji, Węzeł B otrzymuje Ramkę 0. Sprawdza FCS, aby upewnić się, że ramka nie jest uszkodzona.
4. Krok 4: odbiorca wysyła potwierdzenie: Po poprawnym sprawdzeniu ramki Węzeł B odsyła ACK. W przyjętej tu konwencji ACK wskazuje numer sekwencyjny następnej oczekiwanej ramki. Po odebraniu Ramki 0 wysyła ACK 1.
5. Krok 5: Nadawca Otrzymuje ACK: Węzeł A otrzymuje ACK 1 przed wygaśnięciem swojego licznika. Potwierdzenie oznacza, że odbiorca przyjął Ramkę 0 bez wykrytego uszkodzenia. Węzeł A zatrzymuje licznik.
6. Krok 6: Powtórzenie Cyklu: Teraz, gdy Ramka 0 została potwierdzona, Węzeł A może wysłać następną ramkę w sekwencji, Ramkę 1, i cykl rozpoczyna się od nowa.

Obsługa utraty ramki: mechanizm limitu czasu (timeout)

Ramka albo potwierdzenie może zaginąć. W wariancie bez ujemnych potwierdzeń nadawca wykrywa taki brak przez wygaśnięcie timera. Jego wartość powinna obejmować oczekiwany czas obiegu, przetwarzanie i zmienność opóźnienia, aby nie wywoływać przedwczesnych retransmisji.

Scenariusz 1: Utracona Ramka Danych

1. Nadawca przesyła Ramkę 0 i uruchamia swój licznik czasu.
2. Ramka ginie w tranzycie z powodu nagłego zakłócenia w kanale.
3. Odbiorca, Węzeł B, nigdy nic nie otrzymuje. Czeka pasywnie.
4. Nadawca, Węzeł A, czeka. Żadne ACK nie nadchodzi.
5. Timer nadawcy wygasa. Nadawca uznaje brak potwierdzenia za przesłankę do retransmisji.
6. Zakładając, że ramka została utracona, nadawca pobiera kopię Ramki 0 ze swojego bufora i retransmituje ją, ponownie uruchamiając licznik.

Timer jest elementem mechanizmu automatycznego żądania powtórzenia. Po jego wygaśnięciu nadawca ponawia wysyłanie ramki, dla której nie otrzymał potwierdzenia.

Scenariusz 2: Utracona Ramka Potwierdzająca (ACK)

Ramka z danymi może dotrzeć poprawnie, a jej potwierdzenie może zaginąć w drodze powrotnej.

1. Nadawca przesyła Ramkę 0 i uruchamia swój licznik czasu.
2. Odbiorca poprawnie odbiera Ramkę 0 i odsyła ACK 1.
3. Ramka ACK 1 ginie w tranzycie.
4. Nadawca, nieświadomy, że dane dotarły, nadal czeka.
5. Timer nadawcy wygasa. Nadawca nie rozróżnia, dlaczego ACK nie dotarło, więc traktuje brak potwierdzenia jako podstawę do retransmisji.
6. Nadawca retransmituje Ramkę 0.

Rozwiązanie problemu duplikatów: jeden bit

Scenariusz utraty ACK powoduje, że odbiorca może otrzymać duplikat Ramki 0. Przekazanie go do warstwy sieciowej ponownie dostarczyłoby te same dane, na przykład powielając fragment pliku.

Stop-and-Wait rozwiązuje ten problem za pomocą naprzemiennej numeracji sekwencyjnej. Wystarcza jeden bit, którego wartości 0 i 1 oznaczają kolejne ramki.

Jak działa 1-bitowa numeracja sekwencyjna

Odbiorca porównuje numer otrzymanej ramki z numerem, którego oczekuje:

1. Nadawca wysyła Ramkę 0.
2. Odbiorca otrzymuje Ramkę 0, odsyła ACK 1 i teraz oczekuje Ramki 1.
3. ACK 1 zostaje utracony. Licznik czasu nadawcy wygasa.
4. Nadawca retransmituje Ramkę 0.
5. Odbiorca otrzymuje zduplikowaną Ramkę 0. Sprawdza jej numer sekwencyjny. Oczekiwał Ramki 1, a otrzymał Ramkę 0.
6. Odbiorca rozpoznaje duplikat. Odrzuca zduplikowaną ramkę i ponownie wysyła ostatnie udane potwierdzenie, ACK 1, aby zakończyć oczekującą wymianę.

Przy założeniu poprawnej kontroli integralności, zgodnych timerów i obsługi duplikatów ten 1-bitowy numer pozwala odróżnić retransmisję od nowej ramki. Odbiorca odsyła ACK dla ostatniej zaakceptowanej wartości, więc nadawca może ponowić próbę bez powielania danych u odbiorcy. W tych warunkach poprawna ramka danych trafia do wyższej warstwy najwyżej raz, także po utracie ACK.

Analiza wykorzystania łącza w Stop-and-Wait

Protokół Stop-and-Wait jest prosty, lecz jego wydajność na szybkich łączach dalekiego zasięgu ogranicza czas oczekiwania na potwierdzenie. Przy braku błędów ograniczenie wynika głównie z opóźnienia propagacji względem czasu transmisji ramki. Rzeczywista przepływność jest dodatkowo mniejsza przez nagłówki, czas przetwarzania i ewentualne retransmisje.

Przykład obliczeniowy: światłowód transatlantycki

Przyjmijmy w przykładzie dedykowane łącze światłowodowe między Nowym Jorkiem a Londynem o długości 5 600 km.

• Przepustowość łącza (R): 1 Gigabit na sekundę ($1 \times 10^9$ bps).
• Odległość (d): Około 5 600 km.
• Prędkość propagacji (v): Prędkość sygnału w światłowodzie to około $2 \times 10^8$ m/s.
• Ładunek danych (L): 1 500 bajtów (12 000 bitów), a narzuty nagłówków pomijamy.

Obliczmy trzy składniki czasu transmisji i oczekiwania:

1. Czas transmisji $(T_{tx})$: Czas wysłania wszystkich bitów ładunku na łącze.

   $T_{tx} = \frac{\text{Rozmiar Ramki (L)}}{\text{Przepustowość (R)}} = \frac{12,000 \text{ bitów}}{1 \times 10^9 \text{ bps}} = 0.000012 \text{ sekundy} = 12\,\mu\text{s}$

2. Opóźnienie propagacji $(T_p)$: Czas przejścia pierwszego bitu z jednego końca na drugi.

   $T_p = \frac{\text{Odległość (d)}}{\text{Prędkość (v)}} = \frac{5,600,000 \text{ m}}{2 \times 10^8 \text{ m/s}} = 0.028 \text{ sekundy} = 28,000\,\mu\text{s}$

3. Czas podróży w obie strony (RTT): Czas dotarcia ramki i powrotu ACK. Zakładamy pomijalny czas transmisji ACK oraz pomijalne przetwarzanie, więc RTT przybliżamy dwukrotnym opóźnieniem propagacji.

   $RTT \approx 2 \times T_p = 2 \times 28,000\,\mu\text{s} = 56,000\,\mu\text{s}$

Obliczanie wykorzystania łącza

Nadawca spędza $12\,\mu\text{s}$ na nadawaniu i $56,000\,\mu\text{s}$ na oczekiwaniu. Wykorzystanie łącza $(U)$ to udział czasu przeznaczonego na wysyłanie danych:

$U = \frac{T_{tx}}{T_{tx} + RTT} = \frac{12}{12 + 56000} \approx \frac{12}{56012} \approx 0.000214$

Przy tych założeniach łącze pozostaje bezczynne przez 99.9786% czasu. Teoretyczna przepływność danych wynosi $1 \text{ Gb/s} \times 0.000214 \approx 214 \text{ kbps}$. Jest to górne przybliżenie dla braku błędów, bez narzutów nagłówków, czasu przetwarzania i ponowień. Rzeczywista wartość będzie niższa.

Wnioski: prosta metoda o ograniczonej wydajności

Protokół Stop-and-Wait dobrze ilustruje podstawy niezawodności w warstwie łącza. Ogranicza liczbę ramek w locie, a po dodaniu kontroli integralności, numerów sekwencyjnych, potwierdzeń i retransmisji może zapewnić niezawodny transfer.

Jego przepływność spada, gdy czas oczekiwania jest duży w porównaniu z czasem transmisji. Z tego powodu stosuje się protokoły przesuwnego okna, takie jak Go-Back-N i Powtórzenie Selektywne. Zachowują one potwierdzenia i retransmisje, lecz pozwalają wysłać kilka ramek przed otrzymaniem odpowiedzi, lepiej wykorzystując łącze.