Niezawodna transmisja i adaptery sieci

Niezawodna transmisja

• ramki ulegają czasami uszkodzeniu podczas transmisji, a do wykrywania błędów stosuje się kody takie, jak CRC

• mimo, że pewne kody są w stanie poprawić wykryte błędy, to jednak ta dziedzina nie jest tak bardzo zaawansowana

• uszkodzone ramki są więc generalnie odrzucane, ale trzeba je w jakiś sposób odzyskać

• zazwyczaj uzyskuje się to za pomocą kombinacji dwóch mechanizmów: potwierdzeń (), nazwach w skrócie ACK, oraz czasów oczekiwania (timeouts)

  • ACK jest niewielką ramką sterującą, którą protokół nadaje do swojego partnera, informując go, że odebrał poprzednią ramkę

  • ramka sterująca to nagłówek bez żadnych danych

  • protokół może przenosić również ACK na barana (piggyback) na ramce danych, która jest akurat nadawana w przeciwnym kierunku

  • odbiór potwierdzenia wskazuje nadawcy ramki, że jego ramka została dostarczona

  • jeżeli nadawca nie odbierze potwierdzenia w sensownym czasie, wtedy dokonuje retransmisji ramki, ten czas nazywany jest czasem oczekiwania

• ogólna strategia stosowania potwierdzeń  i czasów oczekiwania, w celu implementacji niezawodnej dostawy ramek, jest zwana automatycznym żądaniem powtórzenia (automatic repeat request) - ARQ

• rozpatrzymy trzy różne algorytmy ARQ

Diagram czasowy pokazujący cztery różne scenariusze algorytmu stój i czekaj.

a) ACK odebrane przed upływem czasu oczekiwania; b) oryginalna ramka jest stracona; c) ACK jest stracone; d) sygnał upływu czasu oczekiwania jest przedwczesny

1.  Algorytm stój i czekaj (stop - and - wait)

• idea algorytmu: po nadaniu jednej ramki, nadajnik czeka na potwierdzenie przed nadaniem następnej

• na rysunku przedstawiono cztery różne scenariusze wynikające z algorytmu podstawowego

Diagram czasowy dla stój i czekaj z 1-bitowym numerem sekwencyjnym

• w przypadku c) i d) powstają duplikaty już odebranych i potwierdzonych ramek

• aby sprostać temu problemowi, nagłówek protokołu stój i czekaj zawiera 1-bitowy numer sekwencyjny

  • numer ten może przyjmować wartość 0 i 1, a numery sekwencyjne stosowane dla każdej ramki występują na przemian (patrz, rysunek)

  • odbiornik może więc określić, czy jest to ramka, czy jej duplikat 

• główna wada algorytmu, to wysyłanie przez nadajnik tylko jednej ramki w łącze w danej chwili, co może być znacznie poniżej przepustowości łącza

• rozważmy np. łącze 1.5Mb/s z czasem podróży w obie strony (RTT) równym 45ms

  • łącze ma iloczyn:  opóżnienie * szerokość pasma = 67.5kb albo w przybliżeniu 8kB

  • ponieważ nadajnik przesyła jedną ramkę na czas RTT, a zakładamy rozmiar ramki równy 1kB, to daje maksymalną szybkość nadawania (1024 * 8) : 0,045 = 128 kb/s, co jest około 1/8 przepustowości łącza

• iloczyn opóżnienie * szerokość pasma reprezentuje ilość danych, które mogą być przesłane i które chcielibyśmy być zdolni nadać bez czekania na potwierdzenie

Diagram czasowy dla algorytmu przesuwanego okna

    2.    Przesuwane okno

• rozważmy ponownie łącze, w którym opóżnienie * szerokość pasma  = 8kB i ramki mają rozmiar 1kB

• chcielibyśmy, aby nadajnik był gotowy do transmisji dziewiątej ramki prawie w tej samej chwili, w której przychodzi potwierdzenie ACK na pierwszą ramkę

• algorytm, który pozwala to zrobić, jest nazywany przesuwnym oknem (sliding window) - patrz, rysunek

Przesuwnego okno nadajnika

Algorytm przesuwnego okna

• nadajnik przydziela każdej ramce numer sekwencyjny, oznaczony Seq Num

• w nadajniku są trzy zmienne:

  • rozmiar okna nadawanego (send window size - SWS), który podaje górną granice na liczbę wysyłanych (a niepotwierdzonych) ramek, które nadajnik może nadać

  • numer sekwencyjny ostatniego odebranego potwierdzenia - LAR 

  • numer sekwencyjny ostatniej nadanej ramki - LFS

• nadajnik utrzymuje zależność między zmiennymi:  LFS - LAR <= SWS

Przesuwne okno odbiornika

• kiedy przychodzi potwierdzenie, nadajnik przesuwa LAR w prawo i może nadać następną ramkę

• dodatkowo, nadajnik przydziela zegar każdej ramce, którą nadaje

  • nadajnik retransmituje ramkę, gdyby zegar upłynął przed odebraniem ACK

  • nadajnik musi być zdolny do buforowania ramek do ilości równej SWS, ponieważ musi być przygotowany do ich retransmisji dopóki nie zostaną potwierdzone

• w odbiorniku występują następujące zmienne:

  • rozmiar okna odbiorczego (receive window size - RWS), który podaje górną granice na liczbę ramek poza kolejnością, które odbiornik chce przyjąć

  • LFA oznacza numer sekwencyjny ostatniej akceptowanej ramki

  • NFE oznacza numer sekwencyjny następnej oczekiwanej ramki

• odbiornik podtrzymuje zależność: LFA - NFE + 1 <= RWS

• gdy przychodzi ramka z numerem sekwencyjnym Seq Num, odbiornik podejmuje następującą akcję:

  • jeżeli : SeqNum < NFE lub Seq Num > LFA  to oznacza, że ramka znajduje się poza oknem odbiornika i jest odrzucona 

  • jeżeli : NFE <= SeqNum <= LFA  wtedy ramka znajduje się wewnątrz okna odbiornika i jest akceptowana 

• teraz odbiornik musi podjąć decyzje, czy ma nadawać ACK czy też nie

  • niech SeqNumToACK oznacza największy numer sekwencyjny, który nie został jeszcze potwierdzony, ale taki, że wszystkie ramki o numerach sekwencyjnych mniejszych niż SeqNumToACK zostały odebrane 

  • odbiornik potwierdza odbiór SeqNumToACK, nawet gdy zostały odebrane pakiety o wyższych numerach 

  • takie potwierdzenie nazywa się potwierdzeniem kumulacyjnym

  • odbiornik ustawia następnie  NFE =  SeqNumToACK + 1  i modyfikuje  LFA =  SeqNumToACK + RWS

• załóżmy, że NFE = 5 (czyli ostatni ACK, który odbiornik nadał, odnosił się do numeru sekwencyjnego 4), a RWS = 4

  • to implikuje, że LFA = 9

  • gdyby ramki 6 i 7 przyszły, to będą buforowane, ponieważ są w oknie odbiornika, ale ACK nie może być nadane, ponieważ ramka 5 jeszcze musi nadejść 

  • gdy przyjdzie opóżniona ramka 5, wtedy odbiornik potwierdza ramkę 7, podwyższa NFE na 8 i ustawia LFA = 12  

Kolejność ramek a sterowanie przepływem 

• protokół przesuwnego okna, być może najbardziej znany algorytm w sieciach komputerowych, może być wykorzystywany do trzech ról

  • niezawodne dostarczenie ramki za pomocą zawodnego łącza; jest to jego zasadnicza funkcja 

  • zachowanie kolejności ramek, w jakiej zostały nadane

    • ponieważ każda ramka ma numer sekwencyjny, to odbiornik jedynie musi się upewnić, że nie prześle ramki do protokołu na wyższym poziomie, zanim nie prześle wszystkich ramek z mniejszymi numerami sekwencyjnymi

    • oznacza to, że odbiornik buforuje (czyli nie przesyła dalej), ramki będące poza kolejnością 

  • obsługa sterowania przepływem, czyli rola mechanizmu sprzężenia zwrotnego, za pomocą którego odbiornik jest w stanie zdławić nadajnik

    • uzyskuje się to przez wzmocnienie protokołu przesuwnego okna w taki sposób, że odbiornik nie tylko potwierdza odebrane ramki, ale również informuje nadajnik, na jak wiele ramek ma jeszcze miejsce

    3    Współbieżne kanały logiczne .

• protokół IMP-IMP w sieci ARPANET, daje interesującą alternatywę dla protokołu przesuwnego okna, przez to że jest w stanie zapewnić wypełnione łącze nadal stosując protokół stój i czekaj 

  • ramki przesyłane na pewnym łączu nie są utrzymywane w jakiejś konkretnej kolejności

  • protokół IMP-IMP nie zakłada też nic odnośnie do sterowania przepływem

• idea protokołu IMP-IMP

  • multipleksacja kilku kanałów logicznych, nazywanych współbieżnymi kanałami logicznymi (concurrent logical channels), na jednym łączu dwupunktowym i uruchomieniu algorytmu stój i czekaj na każdym z nich

  • nie ma ustalonej relacji między ramkami przesyłanymi na dowolnym z logicznych kanałów 

  • ponieważ inna ramka może występować na każdym z kilku kanałów logicznych, to nadajnik może utrzymywać łącze zapełnione

• nadajnik utrzymuje trzy bity stanu każdego kanału : flagę boolle'owską i informującą czy kanał jest aktualnie zajęty ; 1-bitowy numer sekwencyjny do wykorzystania gdy następny raz ramka jest nadawana na tym kanale logicznym, oraz jeszcze jeden numer sekwencyjny oczekiwany w ramce, która przychodzi na tym kanale

• kiedy węzeł ma ramkę do przesłania, to wybiera najniższy bezczynny kanał , a poza tym zachowuje się tak, jak algorytm stój i czekaj

• sieć ARPANET obsługuje 8 logicznych kanałów na każdym łączu pod ziemią i 16 na każdym łączu satelitarnym 

• w przypadku łącza pod ziemią, nagłówek każdej ramki zawierał 3-bitowy numer kanału i 1-bitowy numer sekwencyjny, co razem daje 4-bity - dokładnie tyle wymaga protokół przesuwania okna do obsługi aż ośmiu ramek występujących w łączu
  

Adaptery sieci

• prawie wszystkie funkcje sieci, a więc rozpoznawanie ramek, wykrywanie błędów i protokół dostępu do medium są implementowane w adapterze sieci

  • wyjątkiem są schematy automatycznego powtórzenia (ARQ), omawiane wcześniej, które są implementowane w protokole najniższego poziomu w komputerze

  

  Schemat blokowy typowego adaptera sieci.

   

Składniki

• adapter służy jako interfejs między komputerem a siecią i posiada

  • interfejs szyny, który rozumie jak porozumieć się z komputerem

  • interfejs łącza, który posługuje się poprawnym protokołem sieci

• adaptery sieci są zawsze zaprojektowane dla konkretnej szyny wejścia / wyjścia - nie jest więc zwykle możliwe przeniesienie adaptera z komputera jednego dostawcy do komputera drugiego dostawcy

• każda szyna definiuje

  • protokół stosowany przez jednostkę centralną komputera do programowania adaptera

  • protokół stosowany przez adapter do generowania przerwania do jednostki centralnej

  • protokół stosowany przez adapter do odczytu i zapisu pamięci komputera

• jedną z głównych cech szyny wejścia / wyjścia jest szybkość transmisji danych, jaką ona obsługuje

  • np. typowa szyna może mieć ścieżkę danych o szerokość 32 bitów (tzn. przesyłać równolegle 32 bity), pracując z częstotliwością  25MHz ( czas cyklu szyny 40 ns), dając maksymalną szybkość transmisji 800 Mb/s wystarczającą do obsługi łącza STS - 12 o szerokości 800 Mb/s

• część adaptera od strony łącza implementuje protokół poziomu łącza

  • dla Ethernetu i FDDI część adaptera od strony łącza jest implementowana przez zestaw układów scalonych, które można kupić w handlu

  • dla nowszych technik łączy, protokół na poziomie łącza może być zaimplementowany przez oprogramowanie na uniwersalnym mikroprocesorze; podnosi to koszt adaptera, ale czyni go bardziej elastycznym (łatwiej jest modyfikować oprogramowanie niż sprzęt)

• ponieważ szyna komputera i łącze sieciowe działają zwykle z różnymi szybkościami, to istnieje potrzeba umieszczania niewielkiej liczby buforów między dwoma składnikami adaptera (patrz, rysunek)

Spojrzenie na adapter od strony komputera

#1: Rejestr stanu sterowania

• adapter sieci jest sterowany oprogramowaniem uruchomionym w jednostce centralnej (CPU)

• procesor i adapter komunikują się poprzez rejestr stanu sterowania - specjalną komurkę w pamięci komputera

  • rejestr ten umożliwia procesorowi, poprzez odczytywanie zawartości rejestru, lub przez zapis do niego (a) poznanie aktualnego stanu adaptera (b) nakazanie mu nadania lub odbioru ramki

#2: Przerwania

• jednostka centralna komputera znajduje się w pętli, czytając rejestr stanu sterowania i czeka, aż zdarzy się coś interesującego i następnie podejmuje odpowiednią akcję

  • może to być np. obserwacja pojedynczego bity rejestru stanu, który identyfikuje nadejście nowej ramki

  • nazywa się to odpytywaniem (pooling)

• zamiast odpytywania, wiele komputerów zwraca uwagę na urządzenia sieciowe tylko wtedy, adapter generuje przerwanie do komputera

  • architektura komputera posiada mechanizm powodujący wywołanie odpowiedniej procedury w systemie operacyjnym, kedy takie przerwanie występuje

  • procedura ta nazywana programem obsługi przerwań, bada rejestr CSR, określa przyczynę przerwania i podejmuje odpowiednie działanie

• przy obsłudze przerwania, komputer zazwyczaj wprowadza zakaz (disable) innych przerwań

Bezpośredni dostęp do pamięci a programowane wejście / wyjście

• istnieją dwa podstawowe sposoby przesyłania bajtów ramek między adapterem a pamięcią komputera

  • bezpośredni dostęp do pamięci (direct memory access - DMA)

    • adapter bezpośrednio czyta i zapisuje pamięć komputera bez żadnego zaangażowania jednostki centralnej

    • komputer po prostu podaje adapterowi adres pamięci, a adapter czyta do niego albo z niego zapisuje

  • programowane wejście / wyjście (programmed input /output - PIO)

    • za przesyłanie danych jest odpowiedzialna jednostka centralna

    • aby nadać ramkę, jednostka centralna wchodzi w pętle, w której najpierw odczytuje słowo z pamięci komputera, a następnie zapisuje je do adaptera

Lista deskryptorów buforów.

• przy korzystaniu z DMA jednostka centralna przekazuje adapterowi dwie listy deskryptorów buforów (do transmisji do sieci/z sieci)

• lista jest tablicą par adres / długość (patrz, rysunek)

  • przy odbiorze ramek adapter stosuje tyle buforów, ile jest mu potrzebne, aby przechować przychodzącą ramkę

  • ramki są umieszczane w całości w buforach, albo jeśli się nie mieszczą, są rozrzucane między wiele buforów (odczyt rozrzucony)

Programowane wejście / wyjście.

• w przypadku PIO , adapter sieci musi zawierać pewną liczbę buforów - jednostka centralna kopiuje ramki między pamięcią komputera a pamięcią adaptera ( patrz, rysunek )