CSMA/CD | Teleinf Edu

Problem współdzielonego medium

Współdzielony kanał transmisyjny wymaga zasad dostępu, ponieważ wiele stacji korzysta z tego samego medium. Stacja sprawdza stan kanału przed rozpoczęciem nadawania, a po wykryciu kolizji przerywa transmisję, odczekuje wyznaczony czas i ponawia próbę. Reguły te należą do podwarstwy MAC i dotyczą klasycznego Ethernetu w półdupleksie.

Wczesne sieci Ethernet korzystały ze (zazwyczaj kabla koncentrycznego w topologii magistrali albo koncentratora), do którego podłączone były wszystkie urządzenia. Jeśli co najmniej dwie stacje rozpoczęły nadawanie w tym samym czasie, sygnały nakładały się na medium i ramki ulegały uszkodzeniu. Warstwa fizyczna przekazywała informację o kolizji do MAC, a uszkodzona transmisja wymagała ponowienia. Takie zdarzenie nazywa się kolizją.

Do kontroli dostępu do takiego medium wczesny Ethernet wykorzystywał protokół CSMA/CD, czyli Carrier Sense Multiple Access with Collision Detection. Protokół łączy nasłuch nośnej, wielodostęp oraz wykrywanie kolizji podczas nadawania.

Znaczenie skrótu CSMA/CD

Nazwa opisuje trzy funkcje protokołu:

CS: Carrier Sense (nasłuch nośnej)
Przed transmisją urządzenie sprawdza stan kanału i wykrywa obecność sygnału nośnego. Gdy inna stacja nadaje, urządzenie odracza rozpoczęcie transmisji. Próbuje wysłać dane po stwierdzeniu, że kanał jest bezczynny, zachowując wymagany odstęp między ramkami.
MA: Multiple Access (wielodostęp)
Wiele stacji korzysta z tego samego medium. Każda z nich może próbować uzyskać dostęp, gdy kanał jest bezczynny, a protokół określa sposób obsługi jednoczesnych prób transmisji. Żadna stacja nie ma stałego, wyłącznego przedziału czasu. Decyzję o dostępie podejmuje lokalnie każda stacja, bez centralnego arbitra.
CD: Collision Detection (wykrywanie kolizji)
Nasłuch nośnej nie wyklucza kolizji. Dwie stacje mogą uznać kanał za bezczynny w tej samej chwili i rozpocząć nadawanie. Nadająca stacja monitoruje medium podczas transmisji i porównuje sygnał nadawany z sygnałem obserwowanym na interfejsie. Różnica wskazuje kolizję, którą należy zgłosić pozostałym stacjom przez sygnał Jam. Po zakończeniu Jam stacja przechodzi do procedury wycofania.

Algorytm CSMA/CD krok po kroku

Proces CSMA/CD w segmencie współdzielonego Ethernetu obejmuje następujące fazy:

Faza inicjalizacji: przygotowanie do transmisji

1: Host chce nadawać: stacja przygotowuje dane do wysłania.
2: Sprawdzenie, czy wykryto nośną (czy ktoś inny nie nadaje).
- TAK: odczekaj do zwolnienia kanału, a następnie wróć do sprawdzenia dostępu.
- NIE: przejdź do kroku 3 i przygotuj ramkę do wysłania.
3: Złożenie ramki: host buduje ramkę Ethernet z odpowiednimi polami nagłówka.
4: Rozpoczęcie transmisji: bity ramki trafiają na współdzielone medium.

Faza monitoringu: transmisja i wykrywanie kolizji

5: Sprawdzenie, czy wystąpiła kolizja: host porównuje sygnał wysyłany z sygnałem obecnym na medium.
- TAK: przejdź do kroku 9 i poinformuj sieć o kolizji.
- NIE: przejdź do kroku 6 i kontynuuj transmisję.
6: Kontynuacja transmisji: ramka jest nadawana do końca albo do wykrycia kolizji.
7: Sprawdzenie czy transmisja dobiegła końca.
- NIE: wróć do kroku 6 i kontynuuj nadawanie.
- TAK: przejdź do kroku 8.
8: Zakończenie transmisji: MAC zakończył nadawanie ramki.

Faza obsługi kolizji

9: Rozgłoszenie sygnału zakłócającego: w klasycznym CSMA/CD wysyłany jest 32-bitowy sygnał Jam, aby każda stacja wykryła kolizję.
10: Zwiększenie liczby prób: aktualizacja licznika kolizji dla danej ramki. Licznik dotyczy bieżącej ramki i jest zerowany dla nowej ramki.
11: Sprawdzenie czy zbyt wiele kolizji wystąpiło.
- NIE: przejdź do kroku 13, aby wyznaczyć czas oczekiwania i ponowić próbę.
- TAK: przejdź do kroku 12: transmisja tej ramki zostaje przerwana.
12: Zbyt wiele kolizji, przerwanie transmisji: ramka zostaje odrzucona po przekroczeniu limitu prób. MAC zgłasza wtedy błąd do wyższej warstwy, która może zdecydować o dalszym postępowaniu.

Faza wycofania i ponownej próby

13: Obliczenie czasu oczekiwania: stacja losuje opóźnienie zgodnie z algorytmem binarnego wykładniczego wycofania. Opóźnienie jest całkowitą wielokrotnością czasu szczeliny, a zakres losowania rośnie po kolejnych kolizjach i jest ograniczany przez parametr procedury. Przy pierwszej próbie zakres obejmuje zero i jedną szczelinę, a później rośnie aż do limitu.
14: Oczekiwanie przez określony czas: po upływie opóźnienia host wraca do nasłuchu nośnej i ponawia transmisję.

Minimalny rozmiar ramki a wykrywanie kolizji

W CSMA/CD minimalny rozmiar ramki Ethernet wynoszący 64 bajty zapewnia czas potrzebny na wykrycie kolizji w całym segmencie. Stacja musi nadawać w chwili, gdy informacja o kolizji wraca do niej z najdalszej części medium.

Dwa urządzenia A i B mogą znajdować się na przeciwnych końcach najdłuższego segmentu.

Jeśli A zakończy nadawanie krótkiej ramki zanim dotrze do niego sygnał o kolizji wywołanej przez B, uzna transmisję za zakończoną i nie zaplanuje retransmisji.

Opóźnienie propagacji i czas szczeliny

Opóźnienie propagacji $(\tau)$ : Czas potrzebny na przejście sygnału z jednego końca kabla na drugi.
Czas szczeliny (slot time): Najgorszy czas wykrycia kolizji obejmuje przejście sygnału do najdalszego punktu i powrót sygnału kolizji. To okno czasowe jest zdefiniowane jako i jest większy od $2\tau$ , aby uwzględnić opóźnienia urządzeń. Dla Ethernetu 10 i 100 Mb/s wynosi 512 czasów bitowych, czyli 51,2 µs przy szybkości 10 Mb/s.
Obliczenia: Aby stacja nadal nadawała po powrocie sygnału kolizji, czas nadawania najmniejszej ramki musi być co najmniej równy czasowi szczeliny. Zależność ta wiąże minimalny rozmiar ramki z maksymalną średnicą segmentu.

Przykład: Ethernet 10 Mb/s

$\text{Minimalny Rozmiar Ramki} = \text{Przepływność Bitowa} \times \text{Czas Szczeliny}$
$\text{Minimalny Rozmiar Ramki} = 10,000,000 \text{ bit/s} \times 51.2 \times 10^{-6} \text{ s}$
$\text{Minimalny Rozmiar Ramki} = 512 \text{ bitów}$

8 bitów tworzy 1 bajt, więc $512 \text{ bitów} / 8 \text{ bitów/bajt} = 64 \text{ bajty}$ . Minimalny rozmiar 64 bajtów obejmuje pola od adresu docelowego do FCS. W gigabitowym półdupleksie zachowanie okna kolizji wymagało dodatkowych mechanizmów, takich jak rozszerzenie nośnej i przesyłanie serii ramek, przy zachowaniu ograniczeń średnicy sieci. Przełączniki i pełny dupleks ograniczyły zastosowanie CSMA/CD w nowoczesnym Ethernecie.

CSMA/CD w nowoczesnych sieciach

CSMA/CD było rozwiązaniem dostosowanym do współdzielonego medium wczesnego Ethernetu. Umożliwiało współdzielenie jednego segmentu przez wiele stacji. Współczesne sieci przewodowe korzystają głównie z przełączanych łączy pełnodupleksowych, dlatego ten mechanizm ma w nich ograniczone zastosowanie.

Przełącznik sieciowy rozdziela porty na osobne domeny kolizyjne i przekazuje ramki do portu wynikającego z tablicy adresów MAC. W połączeniu punkt-punkt między przełącznikiem i hostem nie występuje wspólne medium dla wielu stacji.

Pełny dupleks pozwala jednocześnie wysyłać i odbierać na łączu punkt-punkt, więc na takim łączu nie występują kolizje CSMA/CD. Mechanizm wykrywania kolizji i wycofania jest wyłączony, a transmisja może rozpocząć się po spełnieniu wymagań odstępu między ramkami.

Dzisiaj CSMA/CD pozostaje pojęciem historycznym i może działać na starszych współdzielonych łączach Ethernet w półdupleksie, na przykład z koncentratorami. Wymaga ono zgodnego trybu pracy po obu stronach łącza, ponieważ konflikt z pełnym dupleksem prowadzi do błędów i utraty ramek. W przełączanych sieciach liczba urządzeń w domenie kolizyjnej jest zwykle ograniczona do portu i jego sąsiada. Sieci WLAN stosują CSMA/CA, dlatego nie są przykładem Ethernetu z CSMA/CD.