4

Podwarstwa kontroli dostępu do nośnika

Jak powiedzieliśmy już, sieci można podzielić na dwie kategorie: używające łączy dwupunktowych i używające kanałów rozgłoszeniowych. W tym rozdziale zajmiemy się sieciami rozgłoszeniowymi i ich protokołami.

W każdej sieci rozgłoszeniowej kluczowym problemem jest metoda ustalenia, kto skorzysta z ka­nału, gdy pojawi się rywalizacja o dostęp. Wyobraźmy sobie konferencyjne połączenie telefoniczne, w którym połączonych jest razem sześć osób przy sześciu telefonach tak, że każda jednocześnie słyszy i może mówić do wszystkich pozostałych. Całkiem możliwe, że gdy jedna z nich przestanie mówić, dwie lub więcej zaczną mówić jednocześnie, co doprowadzi do chaosu. W spotkaniu twarzą w twarz tego chaosu unika się metodami zewnętrznymi, na przykład na zebraniu uczestnicy podno­szą rękę, aby zażądać pozwolenia na zabranie głosu. Gdy dostępny jest tylko jeden kanał, ustalenie, kto powinien być następny, staje się znacznie trudniejsze. Znanych jest wiele protokołów rozwią­zujących ten problem i to one stanowią treść niniejszego rozdziału. W literaturze kanały rozgłoszeniowe są czasem określane, jako kanały wielodostępne lub kanały o dostępie swobodnym.

Protokoły służące do ustalania, kto następny będzie mógł skorzystać z kanału wielodostępnego, należą do podwarstwy warstwy łącza danych zwanej MAC (Medium Access Control — kontrola dostępu do nośnika). Podwarstwa MAC jest szczególnie ważna w sieciach lokalnych, z których wiele używa kanałów wielodostępnych, jako podstawy łączności. Sieci rozległe używają łączy dwupunktowych, z wyjątkiem sieci satelitarnych. Ponieważ kanały wielodostępne i sieci LAN są ze sobą blisko powiązane, w tym rozdziale omówimy ogólnie sieci lokalne oraz kilka kwestii, które nie wiążą się ściśle z podwarstwa MAC.

Z technicznego punktu widzenia podwarstwa MAC jest dolną częścią warstwy łącza danych, więc powinniśmy właściwie przestudiować ją przed omówieniem protokołów dwupunktowych , jednakże większość ludzi potrafi łatwiej zrozumieć protokoły obejmujące wiele urządzeń po zapoznaniu się z protokołami dwustronnymi. Z tego powodu naruszyliśmy trochę kolejność prezentacji warstw od dołu w górę.

4.1. Problem przydzielania kanału

Głównym motywem niniejszego rozdziału jest pytanie, jak przydzielać pojedynczy kanał rozgłoszeniowy rywalizującym ze sobą użytkownikom. Najpierw przyjrzymy się ogólnie schematom statycznym i dynamicznym, a następnie zapoznamy się z szeregiem konkretnych algorytmów.

4.l.l. Statyczne przydzielanie kanałów w sieciach LAN i MAN

Tradycyjną metodą przydzielania pojedynczego kanału (np. telefonicznego łącza dalekosiężnego) wielu rywalizującym użytkownikom jest multipleksowanie z podziałem częstotliwości (FDM). Jeśli mamy N użytkowników, pasmo dzielone jest na N części o równej szerokości (patrz rysunek 2.27), . każdemu użytkownikowi przydziela się jedną część. Ponieważ każdy ma prywatne pasmo częstotliwości, użytkownicy nie zakłócają się nawzajem. Gdy liczba użytkowników jest niewielka i stała, i ruch generowany przez każdego jest duży (buforowany), jak w przypadku central telefonicznych, TDM stanowi prosty i wydajny mechanizm przydzielania kanału.

Jeśli jednak liczba nadawców jest duża i nieustannie się zmienia lub gdy transmisje mają charakter impulsowy, FDM sprawia pewne problemy. Jeśli pasmo jest podzielone na N zakresów i w danej chwili mniej niż N użytkowników chce się komunikować, marnuje się duża część dostępnego pa­rna. Gdy będzie chciało się komunikować więcej niż N użytkowników, niektórzy nie otrzymają pozwolenia z braku dostępnego pasma, nawet jeśli niektórzy z tych, którzy otrzymali pasmo częstotliwości, bardzo rzadko cokolwiek wysyłają lub odbierają.

Jednakże nawet zakładając, że liczbę użytkowników jakimś sposobem uda się utrzymać na stałym poziomie N, podział jednego dostępnego kanału na statyczne podkanały jest z natury niewydajny. Podstawowy problem polega na tym, że gdy użytkownicy nie korzystają z kanału, ich pasmo marnuje się i nikt inny nie ma prawa z niego skorzystać. Co więcej, w większości systemów kom­puterowych ruch danych jest wyjątkowo impulsowy (często zdarza się, że ruch w szczycie tysiąckrotnie przewyższa średni). Oznacza to, że gros kanałów przez większość czasu będzie bezczynna.

Marną efektywność statycznego FDM można udowodnić prostym obliczeniem. Zacznijmy od średniego opóźnienia T dla kanału o przepustowości C bitów na sekundę, w którym częstotliwość przychodzenia ramek wynosi X na sekundę, a każda ramka ma długość wyliczoną według wykładniczej funkcji gęstości prawdopodobieństwa, co oznacza l/µ. bitów na ramkę. Przy tych parametrach szybkość przychodzenia wynosi λ ramek na sekundę, a szybkość usługi µC ramek na sekundę. Według teorii kolejek można udowodnić:

Na przykład, jeśli C wynosi 100 Mb/s, l/µ wynosi 10 000 bitów, a szybkość przychodzenia ramek λ jest równa 5000 ramek na sekundę, wówczas T= 200 µs. Proszę zwrócić uwagę, że jeśli zignoru­jemy opóźnienie kolejkowania i zapytamy, jak długo potrwa przesłanie 10 000-bitowej ramki w sieci 100 Mb/s, otrzymamy (niepoprawny) wynik 100 µs. Taki wynik będzie poprawny tylko w przypadku braku rywalizacji w kanale.

Dokładnie te same argumenty co dla FDM obowiązują dla multipleksowania z podziałem czasu (TDM). Każdemu użytkownikowi statystycznie przydziela się każdą ;V-tą szczelinę czasową. Jeśli użytkownik nie wykorzysta swojego czasu, to ten będzie leżeć odłogiem. To samo będzie obo­wiązywać, gdy podzielimy sieć fizycznie. Używając ponownie powyższego przykładu, gdybyśmy zastąpili sieć 100 Mb/s dziesięcioma sieciami po 10 Mb/s i statycznie przypisali każdego użyt­kownika do jednej z nich, średnie opóźnienie wzrosłoby z 200 µs do 2 ms.

Ponieważ żadna z tradycyjnych statycznych metod przydzielania kanału nie sprawdza się do­brze przy impulsowym charakterze ruchu w sieci, przyjrzymy się teraz metodom dynamicznym.

4.1.2. Dynamiczne przydzielanie kanału w sieciach LAN i MAN

Zanim przejdziemy do pierwszej z licznych metod przydzielania kanału, które omówimy tym roz­dziale, dobrze będzie precyzyjnie zdefiniować problem przydzielania. Wszystkie prace dotyczące tego zagadnienia opierają się na pięciu kluczowych założeniach, opisanych poniżej.

1. Model stacji. Model składa się z N niezależnych stacji (tzn. komputerów, telefonów lub oso­bistych komunikatorów), z których każda ma program lub użytkownika generującego ramki do przesłania. Stacje nazywa się czasem terminalami. Prawdopodobieństwo wygenerowania ramki w interwale o długości Δt wynosi λΔt, gdzie λ jest stałą (szybkością przychodzenia no­wych ramek). Po wygenerowaniu ramki stacja jest blokowana i nie robi nic, dopóki ramka nie zostanie z powodzeniem wysłana.

2. Założenie pojedynczego kanału. Do wszelkiej komunikacji dostępny jest pojedynczy kanał. Wszystkie stacje mogą w nim nadawać i wszystkie mogą w nim odbierać. Ze sprzętowego punktu widzenia wszystkie stacje są równorzędne, aczkolwiek oprogramowanie protokołu może przy­dzielać im priorytety.

3. Założenie kolizji. Gdy jednocześnie wysyłane są dwie ramki, nakładają się w czasie i otrzy­many sygnał zostaje zniekształcony. Takie zdarzenie nosi nazwę kolizji. Wszystkie stacje potra­fią wykrywać kolizje. Ramka, która uległa kolizji, musi zostać wysłana jeszcze raz. Nie wy­stępują inne błędy poza powodowanymi przez kolizje.

(4a) Czas ciągły. Nadawanie ramki może się zacząć w dowolnej chwili. Nie istnieje żaden główny zegar dzielący czas na dyskretne odcinki.

(4b) Czas podzielony na szczeliny. Czas jest dzielony na dyskretne interwały (szczeliny). Transmi­sja ramki zawsze zaczyna się na początku szczeliny. Szczelina może zawierać 0, 1 lub więcej ramek, co odpowiada odpowiednio bezczynności, transmisji i kolizji.

(5a) Wykrywanie nośnej. Stacje potrafią rozpoznać, czy kanał jest używany, przed próbą skorzy­stania z niego. Jeśli wykryta zostaje zajętość kanału, żadna stacja nie będzie próbować uży­wać go, dopóki nie przejdzie w stan bezczynny.

(5b) Bez wykrywania nośnej. Stacje nie potrafią wykryć stanu kanału przed próbą użycia go. Po prostu nadają informacje. Dopiero później mogą ustalić, czy transmisja powiodła się.

Warto tu omówić krótko powyższe założenia. Pierwsze mówi, że stacje są niezależne i że praca generowana jest ze stałą szybkością. Zakłada też niejawnie, że każda stacja ma tylko jednego użyt­kownika lub Sieci komputerowe program, więc podczas gdy stacja jest zablokowana, nie są genero­wane nowe zadania. Bardziej wyrafinowane modele pozwalają na użycie wielozadaniowych stacji, które generują zadania w czasie, gdy stacja jest zablokowana, lecz analiza takich stacji jest o wiele bardziej złożona.

Założenie pojedynczego kanału jest w tym modelu najważniejsze. Nie istnieją żadne zewnętrz­ne metody komunikacji. Stacja nie może „podnieść ręki" żądając prawa do głosu.

Założenie kolizji też jest podstawowe, aczkolwiek w niektórych systemach (zwłaszcza z wid­mem rozproszonym) założenie to jest łagodzone z zaskakującymi wynikami. Ponadto niektóre sie­ci lokalne, na przykład Token Ring, przekazują od stacji do stacji specjalny żeton, który pozwala wy­słać ramkę stacji posiadającej go w danej chwili. W następnych podrozdziałach pozostaniemy jednak przy modelu pojedynczego kanału z rywalizacją i kolizjami.

Możliwe są dwa alternatywne założenia związane z czasem. Czas jest albo ciągły (4a), albo po­dzielony na szczeliny (4b). Niektóre systemy używają jednej metody, inne drugiej, więc omówimy i przeanalizujemy obie. Dla konkretnego systemu obowiązuje zawsze tylko jedna.

Analogicznie, sieć może albo stosować wykrywanie nośnej (5a), albo nie (5b). W sieciach lo­kalnych zasadniczo stosuje się wykrywanie nośnej, jednakże sieci bezprzewodowe nie mogą z tego skutecznie korzystać, ponieważ nie każda stacja może być w zasięgu radiowym wszystkich pozosta­łych stacji. Stacje w sieciach kablowych z wykrywaniem nośnej mogą przerwać wcześniej transmi­sję, jeśli wykryją kolizję z inną transmisją. Z przyczyn technicznych wykrywanie nośnej rzadko stosuje się w sieciach bezprzewodowych. Słowo „nośna" oznacza tutaj elektryczny sygnał w kablu.

4.2. Protokoły dostępu wielokrotnego

Istnieje wiele algorytmów przydzielania dostępu wielokrotnego do kanału. W poniższych punktach omówimy próbkę co ciekawszych z nich i podamy kilka przykładów ich zastosowań.

4.2.1. ALOHA

W latach 70. dwudziestego wieku Norman Abramson wraz z kolegami z University of Hawaii opra­cowali nową, elegancką metodę rozwiązania problemu przydzielania dostępu do kanału. Ich osią­gnięcia zostały od tamtej pory rozwinięte przez wielu innych naukowców (Abramson, 1985). Wprawdzie dzieło Abramsona, zwane systemem ALOHA, używało radiowej transmisji naziemnej, lecz podstawową ideę można zastosować w każdym systemie, w którym niekoordynowani użytkowni­cy rywalizują o użycie pojedynczego wspólnego kanału.

Omówimy tu dwie wersje ALOHA: prostą i szczelinową. Różnią się one tym, czy czas jest w proto­kole dzielony na dyskretne przedziały, w których muszą mieścić się wszystkie ramki. Prosty ALOHA nie wymaga globalnej synchronizacji czasu, szczelinowy tak.

Prosty ALOHA

Podstawowa idea systemu ALOHA jest prosta — pozwala się użytkownikom nadawać, kiedy tylko mają dane do wysłania. Oczywiście będą występować kolizje, a kolidujące ramki będą uszkodzo­ne. Jednakże dzięki naturze transmisji rozgłoszeniowej, która daje informacje zwrotne, nadajnik zawsze może ustalić, czy ramka została zniszczona, słuchając kanału, podobnie jak pozostali użyt­kownicy. W sieci lokalnej informacja zwrotna jest dostępna natychmiast; w łączności satelitarnej nadajnik dopiero po 270 ms może ustalić, czy transmisja odbyła się pomyślnie. Jeśli odbiór jedno­czesny z nadawaniem jest z jakiegoś powodu niemożliwy, potrzebne są potwierdzenia. Jeśli ramka została uszkodzona, nadajnik oczekuje losowy czas i wysyła ramkę ponownie. Czas oczekiwania musi być losowy; w przeciwnym razie te same ramki kolidowałyby ze sobą raz za razem. Systemy, w których wielu użytkowników wspólnie korzysta z jednego kanału w sposób, który mógłby prowa­dzić do konfliktów, są powszechnie nazywane systemami rywalizacyjnymi lub kontencyjnymi.

Rysunek 4.1 przedstawia w sposób uproszczony generowanie ramek w ALOHA. Ramki na naszym rysunku mają stałą długość, ponieważ przepustowość systemów ALOHA jest maksymali­zowana przez stosowanie stałego rozmiaru ramki zamiast ramek o zmiennej długości.

RYSUNEK 4.1.

W prostym protokole ALOHA ramki są wysyłane w całkowicie dowolnych momentach

Gdy dwie ramki próbują zająć kanał w tym samym czasie, występuje kolizja i obie zostają zniekształcone. Jeśli pierwszy bit nowej ramki nałoży się choćby na ostatni bit prawie ukończonej ramki poprzedniej, obie zostaną całkowicie zniszczone i obie trzeba będzie później wysłać ponow­nie. Suma kontrolna nie może (i nie powinna) rozróżniać pomiędzy całkowitą utratą ramki i trafie­niem w brzeg ramki. Uszkodzenie jest uszkodzeniem i tyle.

Można zadać pytanie, jaka jest wydajność kanału ALOHA? Inaczej mówiąc, jaki odsetek wy­słanych ramek unika kolizji w takich chaotycznych warunkach? Rozważmy najpierw nieskończo­ny zbiór interaktywnych użytkowników siedzących przy komputerach (stacjach). Użytkownik zawsze jest w jednym z dwóch stanów: pisze lub czeka. Na samym początku wszyscy użytkowni­cy piszą. Po ukończeniu wiersza tekstu użytkownik przestaje pisać i czeka na odpowiedź. Teraz stacja wysyła ramkę zawierającą wiersz i kontroluje kanał, aby sprawdzić, czy transmisja się po­wiodła. Jeśli tak, użytkownik widzi odpowiedź i wraca do pisania. Jeśli nie, użytkownik czeka dalej, a ramka jest ponownie wysłana raz za razem, dopóki nie zostanie przesłana pomyślnie.

Niech „czas ramki" oznacza ilość czasu niezbędną do nadania standardowej ramki o stałej długości (czyli długość ramki podzielona przez szybkość transmisji bitów). Zakładamy teraz, że nieskończona populacja użytkowników generuje nowe ramki zgodnie z rozkładem Poissona ze średnią N ramek na czas ramki. Założenie nieskończonej populacji jest nam potrzebne, by zapew­nić, że N nie zmaleje z powodu blokowania poszczególnych użytkowników. Jeśli N> 1, społecz­ność użytkowników generuje ramki szybciej niż kanał jest w stanie je obsłużyć i niemal każda ramka ucierpi z powodu kolizji. Dla rozsądnej przepustowości możemy oczekiwać 0 < N< 1.

Oprócz nowych ramek stacja generuje też retransmisje tych ramek, które poprzednio ucier­piały z powodu kolizji. Załóżmy jeszcze, że prawdopodobieństwo k prób transmisji w czasie ramki, łącznie nowych i ponawianych również ma rozkład Poissona, co oznacza G na czas ramki. Oczy­wiście G > N. Przy niewielkim obciążeniu (tzn. N ≈ 0) kolizji i powodowanych nimi retransmisji będzie niewiele, więc G w N. Przy dużym obciążeniu wystąpi wiele kolizji, więc G> N. Przy każdym obciążeniu zdolność przepustowa kanału S jest równa iloczynowi generowanego obciążenia G i praw­dopodobieństwa powodzenia transmisji P₀ — inaczej mówiąc, S = GP₀, gdzie P₀ oznacza prawdo­podobieństwo, że ramka nie ulegnie kolizji.

Ramka nie ulegnie kolizji, gdy w okresie jednego czasu ramki od początku jej nadawania nie zostanie wysłana żadna inna ramka, jak na rysunku 4.2. Jakie warunki są potrzebne, by zacieniowana (o czasie t) ramka dotarła bez uszkodzenia?

Niech t oznacza czas wymagany do wysłania ramki. Gdyby dowolny inny użytkownik wygenerował ramkę w czasie od t₀ do t₀ + t, koniec tej ramki zderzyłby się z początkiem zacieniowanej. W istocie los ramki zacieniowanej został przypieczętowany jeszcze zanim został wysłany pierwszy bit, lecz ponieważ w prostym protokole ALOHA stacja nie nasłu­chuje w kanale przed nadawaniem, nie ma żadnego sposobu zorientowania się, czy jakaś inna ramka nie jest już w drodze. Podobnie każda inna ramka rozpoczęta w czasie pomiędzy t₀ + t i t₀ + 2t zderzy się z końcem zacieniowanej ramki.

Prawdopodobieństwo, że w danym czasie ramki zostanie wygenerowanych k ramek, określa rozkład Poissona:

więc prawdopodobieństwo zera ramek wynosi e^-G . W okresie o długości dwóch czasów ramek średnia liczba wygenerowanych ramek wynosi 2G. Prawdopodobieństwo, że w całym okresie wraż­liwym na kolizję nie zostanie zainicjowana żadna inna transmisja, wynosi więc P₀ = e^-2G. Używając S = GP₀ otrzymamy:

RYSUNEK 4.3.

Zależność pomiędzy

generowanym ruchem

i zdolnością

przepustową

w systemach ALOHA

Zależność pomiędzy generowanym ruchem i zdolnością przepustową kanału przedstawia rysunek 4.3. Maksymalna zdolność przepustowa występuje przy G = 0,5 z S = l/(2e), czyli w przybliżeniu 0,184. Inaczej mówiąc, najlepsze wykorzystanie kanału, na jakie możemy liczyć, wynosi 8%. Wynik mało zachęcający, ale gdy każdy nadaje jak mu się podoba, trudno oczekiwać 100% udanych transmisji.

Szczelinowy ALOHA

W roku 1972 Roberts opublikował metodę podwojenia przepustowości systemu ALOHA (Roberts, 1972). Jego propozycja polegała na podzieleniu czasu na dyskretne odcinki, gdzie każdy odcinek odpowiadał jednej ramce. Takie podejście wymaga od użytkowników uzgodnienia granic szczelin. Jedną z możliwych metod synchronizacji jest wysyłanie przez specjalną stację krótkiego impulsu na początku każdego interwału, jak takt zegara.

W metodzie Robertsa, która otrzymała nazwę szczelinowy ALOHA (slotted ALOHA), w od­różnieniu od prostego ALOHA (pure ALOHA), komputer nie ma prawa nadawać od razu po wprowadzeniu symbolu powrotu karetki. Zamiast tego musi czekać na początek następnej szczeliny. W ten sposób ciągły prosty ALOHA został przekształcony w dyskretny. Ponieważ okres wrażliwości na kolizję został zmniejszony o połowę, prawdopodobieństwo, że w tej samej szczelinie czasu ra­zem z naszą testową ramką nie wystąpi inny ruch, wynosi e^-2G, co prowadzi do:

Jak widać z rysunku 4.3, dla szczelinowego ALOHA szczyt przypada na G = 1 ze zdolnością prze­pustową. S= l/e, czyli około 0,368 — dwa razy wyższą niż w prostym ALOHA. Gdy system działa przy 0=1, prawdopodobieństwo trafienia pustej ramki wynosi 0,368 (z równania 4.2). W najlep­szym przypadku dla szczelinowego ALOHA możemy liczyć na 37% pustych szczelin, 37% po­myślnych transmisji i 26% kolizji. Praca z wyższymi wartościami G zmniejsza liczbę pustych szczelin, lecz wykładniczo zwiększa liczbę kolizji. Aby zobaczyć, jak szybko rośnie liczba kolizji ze wzrostem G, rozważmy transmisję ramki testowej. Prawdopodobieństwo uniknięcia przez nią ko­lizji jest równe prawdopodobieństwu, że w danej szczelinie żaden inny użytkownik nie będzie nadawał, czyli e^-G. Prawdopodobieństwo kolizji jest więc równe 1 - e^-G . Prawdopodobieństwo, że transmisja będzie wymagać dokładnie k prób (tzn. k - 1 kolizji, po których wystąpi 1 pomyślna transmisja), wynosi:

Spodziewana liczba transmisji E na jeden wprowadzony powrót karetki wynosi więc:

W wyniku wykładniczej zależności E od G już niewielki wzrost obciążenia kanału może drastycznie pogorszyć jego wydajność.

Szczelinowy protokół ALOHA jest ważny z powodu, który może nie wydawać się od razu oczywisty. Został o opracowany w latach 70., zastosowany w kilku wczesnych systemach ekspery­mentalnych, a potem niemal zapomniany. Gdy wynaleziono dostęp do Internetu

przez sieć telewi­zji kablowej, nagle pojawił się problem, jak podzielić wspólny kanał pomiędzy wielu rywalizujących użytkowników. Szczelinowy ALOHA wyciągnięty z lamusa uratował sytuację. Często zdarzało się, że zupełnie dobre protokoły wychodzą z użycia z powodów politycznych (na przykład duża fir­ma chce, żeby wszyscy postępowali zgodnie z jej życzeniami), lecz po latach ktoś spostrzegawczy odkrywa, że dawno zarzucony protokół rozwiązuje jego bieżący problem. Z tego powodu przestu­diujemy tu szereg eleganckich protokołów, które nie są dziś powszechnie używane, lecz mogą z ła­twością znaleźć zastosowanie w przyszłości, pod warunkiem, że wystarczająco wielu projektantów sieci będzie miało świadomość ich istnienia. Oczywiście zajmiemy się też wieloma protokołami obecnie stosowanymi.

4.2.2. Protokoły dostępu wielokrotnego z wykrywaniem nośnej

W szczelinowym ALOHA najlepsze wykorzystanie kanału, jakie można osiągnąć, wynosi l/e. Nie jest to zaskakujący wynik, ponieważ gdy stacje nadają, jak im się podoba, bez zwracania uwagi na to, co robią inne stacje, musi występować wiele kolizji. Jednakże w sieciach lokalnych istnieje moż­liwość wykrywania przez stacje działania innych stacji i odpowiedniego dostosowania swojego zachowania. Sieci takie mogą osiągać znacznie wyższy stopień wykorzystania niż l/e. W tym punkcie omówimy kilka protokołów zwiększających wydajność.

Protokoły, w których stacje nasłuchują nośnej (tzn. transmisji) i reagują zależnie od wyniku, noszą nazwę protokołów z wykrywaniem nośnej (carrier sense protocol). Zaproponowano do tej pory szereg takich protokołów. Kleinrock i Tobagi (1975) przeanalizowali część z nich szcze­gółowo. Poniżej przedstawimy kilka wersji protokołów z wykrywaniem nośnej.

Protokoły persistent CSMA i nonpersistent CSMA

Pierwszy protokół z wykrywaniem nośnej, który przedstawimy, nosi nazwę 1-persistent CSMA (Carrier Sense Multiple Access). Gdy stacja ma dane do wysłania, najpierw nasłuchuje na kanale, czy ktoś w danej chwili nadaje. Jeśli kanał jest zajęty, stacja czeka na jego zwolnienie. Gdy wykryje, że kanał jest bezczynny, wysyła ramkę. W przypadku wystąpienia kolizji stacja odczekuje losowy odstęp czasu i próbuje od nowa. Protokół nosi nazwę 1-persistent („1-ciągły"), ponieważ stacja na­daje ramkę z prawdopodobieństwem równym 1, gdy wykryje wolny kanał.

Na wydajność protokołu duży wpływ ma opóźnienie propagacji. Istnieje niewielkie prawdopo­dobieństwo, że natychmiast po rozpoczęciu nadawania przez stację inna stacja stanie się gotowa do nadawania i sprawdzi stan kanału. Jeśli sygnał pierwszej stacji jeszcze nie dotarł do drugiej, to druga wykryje kanał jeszcze bezczynny i również zacznie nadawać, co spowoduje kolizję. Im większe opóź­nienie propagacji, tym większy wpływ będzie miało to zjawisko i tym gorsza będzie wydajność protokołu.

Nawet przy zerowym czasie propagacji będą występować kolizje. Jeśli dwie stacje przygotują się do nadawania w połowie transmisji trzeciej stacji, obie grzecznie poczekają na koniec tej transmi­sji i obie zaczną nadawać dokładnie jednocześnie, co spowoduje kolizję. Gdyby nie były tak niecier­pliwe, kolizji byłoby mniej. Mimo to ten protokół jest o wiele lepszy od prostego ALOHA, ponieważ obie stacje są na tyle dobrze wychowane, że powstrzymują się od zakłócania ramki trzeciej stacji. Już intuicyjnie widać, że takie podejście prowadzi do wyższej wydajności niż w prostym ALOHA. To samo dotyczy szczelinowego ALOHA.

Drugim protokołem z wykrywaniem nośnej jest nonpersistent CSMA (nieciągry CSMA). W tym protokole podjęto świadomą próbę zmniejszenia „zachłanności" w stosunku do poprzedniego. Przed nadawaniem stacja sprawdza stan kanału. Jeśli nikt nie nadaje, stacja sama zaczyna transmisję. Jeśli jednak kanał jest już używany, stacja nie nasłuchuje w sposób ciągły z myślą o natychmiastowym przechwyceniu go po wykryciu końca poprzedniej transmisji. Zamiast tego odczekuje losowy czas, a następnie powtarza algorytm. Dzięki temu użycie tego algorytmu powoduje lepsze wykorzysta­nie kanału, lecz większe opóźnienia niż w 1-persistent CSMA.

Ostatnim protokołem jest p-persistent CSMA, przeznaczony dla kanałów szczelinowych i dzia­łający następująco: gdy stacja staje się gotowa do nadawania, sprawdza stan kanału. Jeśli kanał jest bezczynny, stacja nadaje z prawdopodobieństwem p. Z prawdopodobieństwem q = 1 - p czeka na następną szczelinę. Jeśli ta również jest bezczynna, stacja albo nadaje, albo ponownie czeka, z praw­dopodobieństwem odpowiednio wynoszącym p i q. Proces jest powtarzany, dopóki albo ramka nie zostanie wysłana, albo inna stacja nie zacznie nadawać. W drugim przypadku pechowa stacja za­chowuje się, jakby wystąpiła kolizja (tzn. czeka losowy czas i próbuje ponownie). Jeśli stacja na początku wykryje ząjętość kanału, to czeka do następnej szczeliny i postępuje zgodnie z powyższym algorytmem. Rysunek 4.4 przedstawia wyliczoną zdolność przepustową w zależności od obciążenia dla tych trzech protokołów oraz dla prostego i szczelinowego ALOHA.

CSMA z wykrywaniem kolizji

Protokoły persistent CSMA i nonpersistent CSMA są wyraźnym postępem w stosunku do ALOHA, ponieważ gwarantują, że żadna stacja nie zacznie nadawać po wykryciu zajętości kanału. Kolej­nym ulepszeniem jest przerywanie transmisji przez stacje natychmiast po wykryciu kolizji. Inaczej mówiąc, jeśli dwie stacje wykryją, że kanał jest bezczynny i zaczną nadawać jednocześnie, to obie niemal natychmiast wykryją kolizję. Zamiast nadawać do końca ramkę, która i tak jest bezpowrot­nie zniekształcona, powinny przerwać nadawanie natychmiast po wykryciu kolizji. Szybkie prze­rywanie nadawania uszkodzonych ramek oszczędza czas i pasmo. Ten protokół, znany pod nazwą CSMA/CD (CSMA with Collision Detection — CSMA z wykrywaniem kolizji) jest powszechnie stosowany w sieciach LAN w podwarstwie MAC. Jest on podstawią popularnych sieci lokalnych Ethernet, więc warto poświęcić trochę czasu na szczegółowe zapoznanie się z nim.

CSMA/CD, podobnie jak wiele innych protokołów LAN, opiera się na modelu ideowym z ry­sunku 4.5. W chwili oznaczonej t₀ stacja kończy nadawanie swojej ramki. Każda inna stacja, która ma ramkę do wysłania, może teraz próbować ją nadać. Jeśli dwie lub więcej stacji zdecyduje się nada­wać jednocześnie, wystąpi kolizja. Kolizja może zostać wykryta przez obserwację mocy lub szero­kości impulsu odebranego sygnału i porównanie jej z sygnałem nadawanym.

Po wykryciu kolizji stacja przerywa transmisję, odczekuje losowy okres czasu i próbuje ponow­nie, pod warunkiem, że w tym czasie nie zaczęła nadawać żadna inna stacja. Wobec tego nasz model CSMA/CD będzie składał się z naprzemiennych okresów rywalizacji i transmisji, z okresami bez­czynności występującymi, gdy żadna stacja nie będzie nadawać (z braku zadań).

Przyjrzyjmy się teraz dokładniej algorytmowi rywalizacji. Załóżmy, że obie stacje zaczną nadawać dokładnie w chwili t₀. Po jakim czasie wykryją kolizję? Odpowiedź na to pytanie jest decydująca przy ustalaniu czasu rywalizacji, a co za tym idzie, jakie będą opóźnienia i zdolność przepustowa. Minimalny czas potrzebny do wykrycia kolizji to czas potrzebny na propagację sygnału z jednej stacji do drugiej.

Na podstawie tej logiki może się wydawać, że stacja, która nie wykryje kolizji przez czas równy czasowi propagacji przez całą długość kabla od rozpoczęcia swojej transmisji, może być pewna, że przejęła kabel. Mówiąc „przejęła", mamy na myśli, że wszystkie pozostałe stacje wiedzą już ojej transmi­sji i nie będą przeszkadzać. Ten wniosek jest błędny. Rozważmy najbardziej niepomyślny scenariusz. Niech czas potrzebny do propagacji pomiędzy dwoma najdalszymi stacjami wynosi x. W chwili t₀ jedna stacja zaczyna nadawać. W chwili x - s, na moment przed dotarciem sygnału do najodleglej­szej stacji, ta również zaczyna nadawać. Oczywiście wykrywa kolizję niemal natychmiast i przerywa transmisję, lecz spowodowany przez kolizję krótki impuls zakłócający dociera do pierwszej stacji dopiero w chwili 2x - s. Inaczej mówiąc, w najgorszym przypadku stacja może być pewna przejęcia kanału dopiero po 2x nadawania bez wykrycia kolizji. Z tego powodu będziemy modelować okres rywalizacji jako szczelinowy system ALOHA z długością szczeliny równą 2x. W kablu koncentrycz­nym o długości 1 km czas x ≈ 5us. Dla uproszczenia założymy, że szczelina zawiera tylko jeden bit. Po przejęciu kanału stacja może nadawać z dowolną szybkością, nie tylko 1 bit na 2x sekundy.

Musimy zdać sobie sprawę, że wykrywanie kolizji jest procesem analogowym. Sprzęt stacji musi monitorować kabel podczas transmisji. Jeśli to, co odczyta, będzie inne niż sygnał, który wy­słał, to wiadomo, że wystąpiła kolizja. Stąd wniosek, że kodowanie sygnału musi pozwalać na wykry­wanie kolizji (np. kolizja dwóch sygnałów o napięciu 0 V byłaby raczej niemożliwa do wykrycia). Z tego powodu powszechnie stosuje się specjalne kodowanie.

Warto też zauważyć, że stacja nadająca musi nieustannie monitorować kanał, nasłuchując impulsów zakłóceń, które mogą oznaczać kolizję. Z tego powodu CSMA/CD z pojedynczym ka­nałem jest z natury systemem półdupleksowym. Niemożliwe jest jednoczesne nadawanie i odbie­ranie ramek przez stację, ponieważ układ logiczny odbiornika jest używany i szuka kolizji podczas każdej transmisji.

Aby uniknąć nieporozumień, warto zanotować, że żaden protokół podwarstwy MAC nie gwa­rantuje niezawodnego doręczania. Nawet przy braku kolizji odbiornik z różnych powodów może nie skopiować ramki poprawnie (np. z braku miejsca w buforze lub przeoczonego przerwania).

4.2.3. Protokoły bezkolizyjne

Wprawdzie po jednoznacznym przejęciu kanału przez stację w CSMA/CD nie występują kolizje, lecz mogą nadal zdarzyć się w okresie rywalizacji. Kolizje takie pogarszają wydajność systemu, zwłaszcza gdy kable są długie (tzn. przy dużych x), a ramki krótkie. Oprócz tego CSMA/CD nie wszę­dzie da się zastosować. W tym punkcie przedstawimy kilka protokołów, które rozstrzygają rywalizację o kanał bez żadnych kolizji, nawet w okresie rywalizacji. Większości z nich nie używa się obecne w liczących się systemach, lecz w gwałtownie zmieniającej się branży dobrze jest często mieć pod ręką takie protokoły o doskonałych właściwościach.

W protokołach opisanych poniżej zakładamy, że jest dokładnie N stacji, z których każda ma „zaszyty" unikatowy adres od 0 do N. Nieważne, że część stacji przez część czasu pozostaje nieak­tywnych. Zakładamy też, że opóźnienie propagacji jest pomijalne. Pozostaje podstawowe pytanie: która stacja otrzyma dostęp do kanału po udanej transmisji? Będziemy dalej używać modelu z rysunku 4.5 z dyskretnymi szczelinami rywalizacji.

Protokół z mapą bitową

W naszym pierwszym protokole wolnym od kolizji, podstawowej metodzie z mapą bitową, każdy okres rywalizacji zawiera dokładnie N szczelin. Jeśli stacja nr 0 ma ramkę do wysłania, to nadaje bit 1" w zerowej szczelinie. Podczas tej szczeliny żadna inna stacja nie ma prawa nadawać. Niezależnie od tego, co robi stacja 0., stacja 1. ma okazję nadać „1" w szczelinie 1., lecz tylko wtedy, gdy ma w kolejce ramkę. Ogólnie mówiąc, stacja j może ogłosić, że ma ramkę do wysłania, wstawiając bit „1" do szczeliny j. Po ukończeniu wszystkich N szczelin każda stacja dysponuje pełną wiedzą o tym, które stacje chcą nadawać. Teraz zaczynają transmisję ramek w porządku numerycznym (rysunek 4.6).

RYSUNEK 4.6. Podstawowy protokół z mapą bitową

Ponieważ kolejność została z góry ustalona, nigdy nie wystąpi kolizja. Po nadaniu ramki przez ostatnią gotową stację (to zdarzenie mogą monitorować wszystkie stacje), rozpoczyna się kolejny ,N-bitowy okres rywalizacji. Jeśli stacja osiągnie gotowość zaraz po minięciu jej bitu, to musi pocze­kać z nadawaniem, dopóki wszystkie stacje nie otrzymają swojej szansy na transmisję i ponownie pojawi się mapa bitowa. Protokoły tego typu, w których zamiar nadawania jest ogłaszany przed faktyczną transmisją, noszą nazwę protokołów z rezerwacją.

Przeanalizujmy pokrótce wydajność tego protokołu. Dla wygody będziemy mierzyć czas w jednost­kach szczeliny bitowej z okresu rywalizacji, gdzie ramki danych będą składać się z d jednostek czasu. Przy małym obciążeniu mapa bitowa będzie po prostu nadawana raz za razem z braku ramek danych.

Rozważmy sytuację z perspektywy stacji o niskim numerze, na przykład 0 lub 1. Statystycznie, gdy stacja staje się gotowa do transmisji, „bieżąca" szczelina będzie gdzieś w środku mapy bitowej. Stacja musi czekać przeciętnie N/2 szczelin do zakończenia bieżącej mapy i ukończenie kolejnych pełnych N szczelin, zanim będzie mogła nadawać.

Dla stacji o wyższych numerach sytuacja wygląda lepiej. Te ogólnie muszą czekać tylko poło­wę przebiegu (N/2 szczelin) przed rozpoczęciem nadawania. Ponieważ stacje o niskich numerach muszą czekać średnio 1,5N szczelin, a stacje o wysokich numerach przeciętnie 0,5N szczelin, to średnia dla wszystkich stacji wynosi N szczelin. Wydajność kanału przy niskich obciążeniach ła­two obliczyć. Na każdą przesłaną ramkę przypada dodatkowe N bitów, a ramka ma d bitów, więc wydajność wynosi d/(N + d).

Przy dużych obciążeniach, gdy wszystkie stacje mają cały czas coś do wysłania, N-bitowy okres rywalizacji przypada na N ramek, co daje dodatkowe obciążenie tylko 1 bitu na ramkę i wydajność d/(d+ 1). Średnie opóźnienie dla ramki jest równe sumie czasu kolejkowania w stacji i N(d + l)/2 od momentu, gdy dostanie się na początek wewnętrznej kolejki.

Odliczanie binarne

Problem z podstawowym protokołem z mapą bitową polega na tym, że dodatkowe obciążenie wynosi 1 bit na stację, więc rozwiązanie nie skaluje się dobrze przy tysiącach stacji. Możemy poprawić sytuację, używając binarnych adresów stacji. Teraz stacja, która chce użyć kanału, ogłasza swój adres w postaci binarnego łańcucha bitów, zaczynając od bitu najstarszego. Zakłada się, że wszystkie adre­sy mają tę samą długość. Na bitach na każdej pozycji z różnych stacji wykonywana jest operacje bulowska LUB. Ten protokół nazwiemy odliczaniem binarnym (binary countdown). Został on użyty w sieci Datakit (Fraser, 1987). Zakłada się tu w sposób domniemany, że opóźnienia transmi­sji są pomijalne, więc wszystkie stacje natychmiast widza, otrzymane bity.

Aby uniknąć konfliktów, musi zostać zastosowana reguła arbitrażu: gdy tylko stacja zobaczy, że bardziej znaczący bit w jej adresie równy 0 został nadpisany przez 1, rezygnuje z transmisji. Na przykład, gdy jednocześnie próbują zdobyć dostęp do kanału stacje 0010, 0100, 1001 i 1010, w pierw­szym bicie stacje te nadają odpowiednio 0, 0, 1 i 1. Operacja LUB daje wynik „1". Stacje 0010 i 0100 rozpoznają przez to, że konkurują z nimi stacje o wyższym numerze, więc w tej rundzie rezygnują. Sta­cje 1001 i 1010 idą dalej.

Następny bit to „0" i obie stacje kontynuują nadawanie adresu. Następny bit to „1", więc stacja 1001 rezygnuje. Zwycięzcą jest stacja 1010, ponieważ ma najwyższy adres. Po wygranej licytacji stacja może wysłać ramkę, po czym rozpoczyna się kolejny cykl licytacji. Ten protokół przedstawia rysunek 4.7. Stacje o wyższych numerach mają w nim pierwszeństwo przed stacjami o niższych nu­merach, co może być dobre lub złe, zależnie od kontekstu.

RYSUNEK 4.7. Protokół binarnego zliczania wstecz. Kreska oznacza brak transmisji

Wydajność tej metody wynosi d/(d + log₂N) Jeśli jednak format ramki zostanie tak sprytnie dobrany, że adres nadawcy będzie pierwszym polem w ramce, nawet te log₂N nie zmarnuje się i wy­dajność wyniesie 100%.

Mok i Ward (1979) opisali odmianę binarnego zliczania wstecz używającą interfejsu równo­ległego zamiast szeregowego. Zasugerowali też używanie wirtualnych numerów stacji, w których numery od 0 aż do stacji, która z powodzeniem nadała ramkę włącznie, są permutowane po każdej transmisji, co daje wyższy priorytet stacjom przez dłuższy czas niewysyłającym niczego. Na przy­kład, gdyby stacje C, H, D, A,G,B,E\F miały odpowiednio priorytety 7, 6, 5,4, 3,2, 1 i 0, to udana transmisja D przenosiłaby tę stację na koniec listy, dając kolejność priorytetów C, H, A, G, B, E, F i D. W ten sposób C pozostaje wirtualną stacją nr 7, lecz A przechodzi w górę z 4 na 5, a D spada z 5 do 0. Teraz stacja D będzie mogła przejąć kanał tylko wtedy, gdy żadna inna stacja nie będzie chciała nadawać.

Odliczanie binarne jest przykładem prostego, eleganckiego i wydajnego protokołu, który czeka na ponowne odkrycie. Może któregoś dnia znajdzie dla siebie nowe miejsce.

4.2.4. Protokoły z ograniczoną rywalizacją

Omówiliśmy dwie podstawowe strategie przejmowania kanału w sieci kablowej: z rywalizacją, takie jak CSMA, i bezkolizyjne. Każdą strategię można ocenić pod kątem skuteczności w dwóch ważnych parametrach wydajności: opóźnieniach przy małym obciążeniu i wydajności kanału przy dużym obciążeniu. W warunkach małego obciążenia preferowana jest rywalizacja (np. czysty i szczelinowy ALOHA) z uwagi na małe opóźnienia. Ze wzrostem obciążenia rywalizacja staje się coraz mniej atrakcyjna, ponieważ rośnie dodatkowe obciążenie kanału związane z arbitrażem. Dokładnie na od­wrót jest w sytuacji protokołów bezkolizyjnych. Przy małych obciążeniach wprowadzają duże opóźnienia, lecz ze wzrostem obciążenia wydajność kanału rośnie zamiast maleć, jak w protoko­łach rywalizacyjnych.

Oczywiście dobrze byłoby połączyć najlepsze właściwości protokołów rywalizacyjnych i bez­kolizyjnych i otrzymać nowy protokół, który będzie używać rywalizacji przy niskich obciążeniach, aby zapewnić małe opóźnienia, oraz technik bezkolizyjnych przy wysokich obciążeniach, aby za­pewnić dobrą wydajność kanału. W rzeczy samej takie protokoły, które będziemy nazywać proto­kołami z ograniczoną rywalizacją (limited-contention protocol), istnieją i ich prezentacja za­kończy naszą analizę sieci z wykrywaniem nośnej.

Jak do tej pory wszystkie przedstawione przez nas protokoły rywalizacyjne były symetrycz­ne, to znaczy każda stacja usiłowała przejąć kanał z pewnym prawdopodobieństwem p, a dla wszystkich stacji wartość p była taka sama. Co ciekawe, ogólną wydajność systemu można czasem zwiększyć za pomocą protokołu, który przydziela różne prawdopodobieństwa różnym stacjom.

Zanim przyjrzymy się protokołom asymetrycznym, oceńmy wydajność protokołów symetrycz­nych. Załóżmy, że k stacji rywalizuje o dostęp do kanału. Każdy ma prawdopodobieństwo nada­wania w każdej szczelinie równe p. Prawdopodobieństwo, że stacja z powodzeniem przejmie kanał w danej szczelinie wynosi wtedy kp(1 -p) ^k-1. Aby znaleźć optymalną wartość p, zróżniczkujemy względem p, przyrównajmy do 0 i rozwiążmy równanie dla p. Zobaczymy, że najlepszą wartością dla p jest 1/k. Podstawiając p = 1/k, otrzymamy:

Wykres tego prawdopodobieństwa przedstawia rysunek 4.8. Dla niewielu stacji prawdopodobień­stwo powodzenia jest wysokie, lecz już przy pięciu stacjach prawdopodobieństwo spada w pobliże asymptotycznej wartości l/e.

RYSUNEK 4.8. Prawdopodobieństwo przejęcia kanału przy rywalizacji symetrycznej

Z rysunku 4.8 w sposób oczywisty wynika, że prawdopodobieństwo przejęcia kanału przez sta­cję możemy zwiększyć, tylko zmniejszając poziom rywalizacji. Dokładnie tak zachowują się proto­koły z ograniczoną rywalizacją. Najpierw dzielą stacje na grupy (niekoniecznie rozłączne). Jedynie członkowie grupy 0 mają prawo rywalizować o szczelinę 0. Zwycięzca przejmuje kanał i wysyła swoją ramkę. Jeśli szczelina nie jest wykorzystana lub, jeśli wystąpi kolizja, członkowie grupy 1. ry­walizują o szczelinę 1. itd. Odpowiedni podział stacji na grupy pozwala na zmniejszenie rywalizacji o każdą szczelinę, dzięki czemu kanał będzie funkcjonować w pobliżu lewej krawędzi rysunku 4.8.

Cała sztuka polega na przydzielaniu stacji do szczelin. Zanim przyjrzymy się przypadkowi ogólnemu, rozważmy kilka przypadków szczególnych. W jednej skrajności każda grupa ma tylko jed­nego członka. Taki przydział gwarantuje, że kolizja nigdy nie wystąpi, ponieważ o każdą szczelinę ry­walizuje najwyżej jedna stacja. Widzieliśmy takie protokoły wcześniej (np. odliczanie binarne). Następny przypadek szczególny to dwie stacje na grupę. Prawdopodobieństwo, że obie będą pró­bować nadawać w danej szczelinie, wynosi p², więc jest pomijalne dla małych p. W miarę przy­dzielania coraz większej liczby stacji do tej samej szczeliny prawdopodobieństwo kolizji rośnie, lecz maleje długość mapy bitowej niezbędnej, aby każdemu dać szansę. Przypadkiem granicznym jest jedna grupa zawierająca wszystkie stacje (czyli szczelinowy ALOHA). Potrzebujemy sposobu dynamicznego przydzielania stacji do szczelin, z wieloma stacjami na szczelinę przy niskim ob­ciążeniu i kilkoma (lub nawet jedną) stacją na szczelinę, gdy obciążenie jest wysokie.

Protokół adaptacyjnego przejścia przez drzewo

Szczególnie prostą metodą dokonywania niezbędnych przydziałów może być użycie algorytmu opracowanego przez armię USA do badania żołnierzy na syfilis podczas II wojny światowej (Dorfman, 1943). W skrócie wyglądało to tak: pobierano próbkę krwi od TV żołnierzy, a część każdej próbki wlewano do wspólnej probówki. Ta wymieszana próbka była testowana na obecność antyciał. Jeśli ich nie znaleziono, wszyscy żołnierze byli uznawani za zdrowych. Jeśli antyciała były obecne, przygotowywano dwie nowe mieszane próbki, jedną od żołnierzy od 1 do N/2, a drugą od reszty. Proces był powtarzany rekurencyjnie, dopóki nie wykryto zarażonych żołnierzy.

W komputerowej wersji tego algorytmu (Capetanakis, 1979) wygodnie będzie wyobrazić sobie stacje jako liście binarnego drzewa, jak na rysunku 4.9. W pierwszej szczelinie rywalizacji nastę­pującej po pomyślnej transmisji ramki (szczelinie 0) wszystkie stacje mają prawo próbować prze­jąć kanał. Jeśli jedna z nich to zrobi, wszystko w porządku. Jeśli wystąpi kolizja, to w szczelinie 2 rywalizować mogą tylko stacje podpadające pod węzeł 2 drzewa Jeśli jedna z nich przejmie kanał, kolejna szczelina po wysłanej ramce będzie zarezerwowana dla stacji pod węzłem 3. Jeśli z drugiej strony dwie lub więcej stacji pod węzłem 2 będą chciały nadawać, wystąpi kolizja w szczelinie 1 i wte­dy szczelina 2 przypadnie węzłowi 4.

RYSUNEK 4.9. Drzewo z ośmioma stacjami

Krótko mówiąc, jeśli kolizja występuje w szczelinie 0, przeszukiwane jest zstępująco całe drzewo w celu zlokalizowania wszystkich gotowych stacji. Każda jednobitowa szczelina jest sko­jarzona z konkretnym węzłem drzewa. Jeśli wystąpi kolizja, poszukiwanie będzie kontynuowane rekurencyjnie w lewym i prawym potomku węzła. Jeśli szczelina bitowa jest wolna lub jeśli nadaje w niej tylko jedna stacja, szukanie węzła może się skończyć, ponieważ zostały zlokalizowane wszystkie gotowe stacje (gdyby była więcej niż jedna, wystąpiłaby kolizja).

Gdy obciążenie systemu jest duże, nie opłaca się zbytnio przydzielać szczeliny 0 do węzła 1, ponieważ to miałoby sens jedynie w mało prawdopodobnym przypadku tylko jednej stacji mającej ramkę do wysłania. Można podobnie argumentować, że węzły 2 i 3 również należałoby pominąć z tego samego powodu. Uogólniając, na którym poziomie drzewa powinno rozpocząć się przeszukiwanie drzewa? To oczywiste, że im większe obciążenie, na tym niższym poziomie. Założymy, że każda stacja dysponuje dość dobrym szacunkiem gotowych stacji (q), na przykład na podstawie monitoro­wanego ostatnio ruchu.

Ponumerujmy poziomy drzewa, licząc od góry. Węzeł 1 z rysunku 4.9 będzie na poziomie 0. węzły 2 i 3 na poziomie 1 i tak dalej. Zwróćmy uwagę, że każdy węzeł n poziomie i ma pod sobą ułamek 2^-i stacji. Jeśli q gotowych stacji rozkłada się równomiernie, ich spodziewana liczba pod konkretnym węzłem na poziomie i wynosi 2^-iq. Intuicyjnie możemy się spodziewać, że optymalna poziom, na którym należy zacząć przeszukiwać drzewo, to ten, gdzie średnia liczba stacji rywali­zujących o szczelinę wynosi 1, czyli tam, gdzie 2^-iq = 1. Rozwiązanie tego równania pozwoli znaleźć i = log₂q.

Znaleziono wiele udoskonaleń podstawowego algorytmu, które zostały omówione szczegółowe przez Bertsekasa i Gallagera (1992). Rozważmy na przykład sytuację, w której nadawać chcą tylko stacje G i H. W węźle 1 wystąpi kolizja, więc zostanie wypróbowany węzeł 2 i okaże się, że jest bezczynny. Nie ma sensu testować węzła 3, ponieważ na pewno wystąpi w nim kolizja (wiemy, że gotowe są dwie lub więcej stacji pod węzłem 1 i żadna pod węzłem 2, więc obie muszą być pod wę­złem 3. Możemy pominąć próbę węzła 3 i sprawdzić w następnej kolejności 6. Gdy ten test rów­nież nie da żadnego wyniku, będziemy mogli pominąć 7 i sprawdzić w następnej kolejności węzeł G.

4.2.5. Protokoły dostępu wielokrotnego z podziałem długości fal

Inne podejście do przydzielania kanału polega na podzieleniu go na podkanały z użyciem FDM TDM lub obu metod i dynamicznym przydzielaniu podkanałów w miarę potrzeb. Metody tego typu są powszechnie stosowane w światłowodowych sieciach LAN, pozwalając przeprowadzać jedno­cześnie różne konwersacje na różnych długościach fal (czyli częstotliwościach). W tym punkcie przedstawimy jeden taki protokół (Humblet i in., 1992).

W całości optyczną sieć LAN można prosto zbudować z użyciem pasywnego sprzęgacza gwiaź­dzistego (patrz rysunek 2.8). Dwa włókna światłowodowe z każdej stacji są stapiane ze szklanym cylindrem. Jedno włókno kieruje wyjście do cylindra, a drugie jest przeznaczone dla wejścia z cylin­dra. Światło wysyłane przez dowolną stację oświetla cylinder i może być wykryte przez wszystkie pozostałe stacje. Pasywne gwiazdy mogą łączyć setki stacji.

Aby umożliwić wiele jednoczesnych transmisji, widmo jest dzielone na kanały (pasma długo­ści fal), jak na rysunku 2.27. W tym protokole o nazwie WDMA (Wavelength Division Multiph Access — dostęp wielokrotny z podziałem długości fal) każdej stacji przydzielane są dwa kanały Wąski kanał zostaje przyznany jako sterujący do sygnalizowania do stacji, a szeroki pozwala stacji wysyłać ramki danych.

Każdy kanał jest podzielony na grupy szczelin czasowych, jak na rysunku 4.10. Oznaczmy licz­bę szczelin w kanale sterującym literą w, a liczbę szczelin w kanale danych n + 1, gdzie n szczelin Jest dla danych, a ostatniej szczeliny stacja używa do raportowania swojego stanu (głównie tego które szczeliny w obu kanałach są wolne). W obu kanałach sekwencja szczelin powtarza się nie Przerwanie, a szczelina 0. jest oznaczona w specjalny sposób, co pozwala ją wykryć spóźnialskim Wszystkie kanały są synchronizowane przez pojedynczy globalny zegar.

Może się zdarzyć, że w tym samym czasie co A szczelinę sterującą 4 kanału B będzie usiłował przejąć stacja C. Żadna jej nie zdobędzie i obie zauważą niepowodzenie, monitorując szczelin stanu w kanale danych stacji B. Obie odczekają losowy odcinek czasu i ponowią próbę później.

W tej chwili każda strona dysponuje bezkonfliktowym mechanizmem przesyłania do siebie nawzajem krótkich komunikatów sterujących. Aby przeprowadzić transfer pliku, A wysyła teraz do B komunikat sterujący, który mówi np. „Obserwuj moją następną wyjściową szczelinę danych 2 Będzie w niej ramka danych dla ciebie". Gdy B otrzymuje komunikat sterujący, dostraja swój odbiornik do kanału wyjściowego stacji A, aby odczytać ramkę danych. W zależności od protokół; wyższej warstwy B może użyć tego samego mechanizmu do odesłania potwierdzenia.

Zwróćmy uwagę, że pojawia się problem, jeśli zarówno A, jak i C mają połączenie z B i obi stacje nagle każą B obserwować szczelinę 3. B wybierze losowo jedno z tych żądań, a druga transmisja zostanie utracona.

Dla ruchu o stałej szybkości transmisji używana jest odmiana tego protokołu. Gdy A żąda połączenia, jednocześnie zadaje pytanie typu: „czy mogę do ciebie wysyłać ramkę w każdym kolejnym wystąpieniu szczeliny 3?". Jeśli stacja B będzie mogła przyjąć taką prośbę (tzn. nie ma żadnych wcześniejszych zobowiązań względem szczeliny 3), zostanie nawiązane połączenie o gwarantowane przepustowości. Jeśli nie, A ponowi pytanie z inną propozycją, zależnie od tego, które szczelin} wyjściowe ma wolne.

Ruch klasy 3. (datagramy) opiera się na jeszcze innej odmianie protokołu. Zamiast zapisywać komunikat CONNECTION REQUEST w znalezionej szczelinie sterującej (nr 4) stacja zapisuje komunika DATA FOR YOU IN SLOT 4 (dane dla ciebie w szczelinie 4). Jeśli B jest wolna w następnej szczelinie danych (3), transmisja powiedzie się. W przeciwnym razie ramka danych zostanie utracona. Dzięki tej metodzie połączenia są całkowicie niepotrzebne.

Możliwych jest kilka odmian tego protokołu. Na przykład zamiast osobnego kanału sterującego dla każdej stacji wszystkie stacje mogą używać jednego wspólnego kanału. Każda stacja otrzymuje w każdej grupie blok szczelin, czyli wiele wirtualnych kanałów jest multipleksowanych w jednym kanale fizycznym.

Może też wystarczyć jeden przestrajalny nadajnik i jeden przestrajalny odbiornik na stację, jeśli kanał każdej stacji będzie podzielony na m szczelin sterujących, po których nastąpi n + 1 szczelin danych. Wada tego rozwiązania polega na tym, że nadajniki muszą dłużej czekać na prze­chwycenie szczeliny sterującej, a kolejne ramki danych są bardziej odległe od siebie, ponieważ po drodze występują informacje sterujące.

Zaproponowano i zaimplementowano też wiele innych protokołów WDMA, różniących się roz­maitymi szczegółami. Niektóre używają tylko jednego kanału sterującego, inne wielu. Niektóre włączają czas strojenia do modelu, inne ten czas ignorują. Protokoły różnią się też złożonością przetwarza­nia, zdolnością przepustową kanału i skalowalnością. Gdy używana jest duża liczba częstotliwości, systemy czasem nazywane są DWDM (Dense Wawelength Division Multiplexing — multipleksowanie z zagęszczonym podziałem długości fal). Dodatkowe informacje przedstawiają Bogineni i inni (1993). Chen (1994), Góralski (2001), Kartalopoulos (1999) oraz Levine i Akyilidz (1995).

4.2.6. Protokoły bezprzewodowych sieci LAN

Ze wzrostem liczby przenośnych urządzeń komunikacyjnych i komputerowych rośnie też zapotrze­bowanie na łączenie ich ze światem zewnętrznym. Nawet najwcześniejsze mobilne telefony mogły łączyć się z innymi telefonami. Pierwsze komputery przenośnie nie miały tej zdolności, lecz wkrótce modemy stały się normą w notebookach. Aby włączyć taki komputer do sieci, trzeba było podłączyć się do naściennego gniazdka telefonicznego. Ponieważ niezbędne było kablowe połączenie ze stałą siecią, te komputery były przenośne, a nie mobilne.

Aby osiągnąć prawdziwą mobilność, notebooki wymagają do komunikacji sygnałów radiowych (lub podczerwonych). Dzięki temu gorliwi użytkownicy mogą czytać i wysyłać pocztę elektroniczną podczas pieszych wędrówek i płynąc łodzią. System notebooków komunikujących się za pomocą radia można uważać za bezprzewodową sieć lokalną, jak mówiliśmy w punkcie 1.5.4. Takie sieci mają nieco inne właściwości niż konwencjonalne sieci LAN i wymagają specjalnych protokołów w pod-warstwie MAC. W niniejszym punkcie poznamy kilka takich protokołów. Dodatkowe informacje o bezprzewodowych sieciach lokalnych opisali Geier (2002) oraz 0'Hara i Petrick (1999).

Typową konfiguracją bezprzewodowej sieci LAN jest budynek biurowy ze stacjami bazowymi (zwanymi też punktami dostępowymi) rozmieszczonymi w strategicznych miejscach. Wszystkie sta­cje bazowe są ze sobą połączone kablami miedzianymi lub światłowodowymi. Jeśli moc nadawcza stacji bazowych i notebooków jest tak ustawiona, by zasięg wynosił 3 lub 4 metry, każdy pokój staje się pojedynczą komórką, a budynek dużym systemem komórkowym, podobnie jak w telefonii ko­mórkowej omówionej w rozdziale 2. W przeciwieństwie do komórkowych systemów telefonicznych każda komórka ma tylko jeden kanał zajmujący całe dostępne pasmo i obejmujący wszystkie sta­cje w komórce. Przepustowość kanału wynosi zwykle od 11 do 54 Mb/s.

W poniższych opisach przyjmiemy upraszczające założenie, że wszystkie nadajniki radiowe mają jakiś stały zasięg. Gdy odbiornik znajduje się w zasięgu dwóch aktywnych nadajników, sygnał wynikowy będzie ogólnie zniekształcony i bezużyteczny. Inaczej mówiąc, nie będziemy dalej brali pod uwagę systemów typu CDMA. Należy zdać sobie sprawę, że w niektórych bezprzewodowych sieciach LAN nie wszystkie stacje są w zasięgu pozostałych, co prowadzi do szeregu komplikacji. Co więcej, w przypadku bezprzewodowych sieci LAN wewnątrz budynków obecność ścian po­między stacjami może mieć poważny wpływ na skuteczny zasięg każdej stacji.

Naiwnym podejściem do korzystania z bezprzewodowej LAN mogłaby być próba użycia CSMA — nasłuchiwanie innych transmisji i nadawanie tylko wtedy, gdy nikt inny tego nie robi. Problem w tym, że ten protokół nie jest tu naprawdę odpowiedni — ważne są zakłócenia w odbiorniku, a nie w na­dajniku. Aby zrozumieć, na czym polega problem, spójrzmy na rysunek 4.11 przedstawiający czte­ry stacje bezprzewodowe. Dla naszych potrzeb nie jest istotne, które z nich są stacjami bazowymi, a które notebookami. Zasięg transmisji radiowej jest taki, że A i B są w swoim zasięgu i mogą za­kłócać się nawzajem. C może potencjalnie zakłócać B i D, lecz nie A.

RYSUNEK 4.11. Bezprzewodowa sieć lokalna: (a) nadaje stacja A, (b) nadaje stacja B

Zobaczmy najpierw, co się dzieje, gdy A nadaje do 6, jak na rysunku 4.11 (a). Jeśli C wykrywa nośną, to nie usłyszy A, ponieważ jest poza jej zasięgiem, i dojdzie do fałszywego wniosku, że może nadawać do B. Jeżeli C zacznie nadawać, to spowoduje zakłócenia w stacji B, powodując utratę ramki od A. Problem niezdolności stacji do wykrycia potencjalnego rywala w dostępie do nośnika z tego powodu, że rywal znajduje się za daleko, nosi nazwę problemu ukrytej stacji (ang. hidden station problem).

Rozważmy teraz sytuację odwrotną: B nadaje do A, jak na rysunku 4.11 (b). Jeśli C monitoruje nośnik, to wykryje trwającą transmisję i dojdzie do fałszywego wniosku, że nie może nadawać do D, podczas gdy w rzeczywistości taka transmisja powodowałaby błędy odbioru tylko w strefie pomię­dzy stacjami B i C, gdzie nie mieści się żaden docelowy odbiornik. Jest to tzw. problem odkrytej sta­cji (ang. exposed station problem).

Problem polega na tym, że przed rozpoczęciem transmisji stacja musi wiedzieć, czy w okoli­cy odbiornika nie występuje jakaś aktywność. CSMA informuje jedynie, czy coś się dzieje do­okoła stacji wykrywającej nośną. W przypadku kabla wszystkie sygnały propagują się do wszystkich stacji, więc w jednej chwili w obrębie całego systemu może zachodzić tylko jedna transmisja. W sys­temie opartym na falach radiowych o krótkim zasięgu jednocześnie może występować wiele trans­misji, jeśli mają różne miejsca przeznaczenia, a każda stacja docelowa jest poza zasięgiem reszty na­dajników.

Wyobraźmy sobie budynek biurowy, w którym każdy pracownik ma bezprzewodowy note­book. Załóżmy, że Linda chce wysłać wiadomość do Miltona. Komputer Lindy nasłuchuje w kanale i ponieważ w swoim otoczeniu nie wykrywa transmisji, zaczyna nadawać. Jednakże w biurze Miltona może wystąpić kolizja, jeśli trzecia osoba będzie akurat nadawać do niego z lokalizacji tak odległej od Lindy, że jej komputer nie wykryje transmisji.

MACA i MACA W

Wczesnym protokołem zaprojektowanym dla bezprzewodowych sieci LAN był MACA (Multiple Access with Collision Avoidance — wielodostęp z unikaniem kolizji) (Karn, 1990). Podstawowa idea tego protokołu polega na tym, że nadajnik stymuluje odbiornik do wysłania krótkiej ramki, dzięki której okoliczne stacje mogą wykryć transmisję i uniknąć nadawania w trakcie następnej (dużej) ramki danych. Protokół MACA przedstawia rysunek 4.12.

(a) (b)

RYSUNEK 4.12. Protokół MACA: (a) A wysyła RTS do B, (b) B odpowiada A ramką CTS

Rozważmy teraz, jak A wysyła ramkę do B. A zaczyna od wysłania do B ramki RTS (Request to Send — zgłoszenie do wysłania), jak na rysunku 4.12 (a). Ta krótka ramka (30 bajtów) zawiera długość ramki danych, która po niej nastąpi. Następnie B odpowiada ramką CTS (Clear to Send — gotowy do wysłania), jak na rysunku 4.12 (b). Ramka CTS zawiera długość danych (skopiowaną z ramki RTS). Po odebraniu ramki CTS A rozpoczyna nadawanie.

Zobaczmy teraz, jak reagują stacje odbierające którąś z tych ramek. Każda stacja odbierająca RTS znajduje się blisko A i musi pozostać bezczynna wystarczająco długo, by ramka CTS została odesłana do A bez konfliktu. Każda stacja, która odbierze CTS, jest w pobliżu B i musi powstrzymać się od nadawania podczas następującej po CTS transmisji danych, której długość może poznać z za­wartości ramki CTS.

Na rysunku 4.12 stacja C jest w zasięgu A, lecz poza zasięgiem B. Oznacza to, że usłyszy RTS ze stacji A, lecz nie CTS ze stacji B. Stacja C, o ile nie zakłóci CTS, może nadawać podczas przesy­łania danych. Za to stacja D jest w zasięgu B, lecz poza zasięgiem A. Nie odbiera RTS, lecz słyszy CTS. Odebranie CTS oznacza dla stacji D, że jest w pobliżu stacji, która za chwilę będzie odbierać ramkę, więc D powstrzymuje się od jakichkolwiek transmisji, dopóki ramka nie zostanie teoretycznie ukończona. Stacja E obiera oba komunikaty sterujące i podobnie jak D musi powstrzymać się od nadawania aż do zakończenia ramki danych.

Mimo tych środków ostrożności kolizje mogą się zdarzać. Na przykład B i C mogą jednocze­śnie wysłać ramkę RTS do stacji A. Wystąpi kolizja i ramki zostaną utracone. W przypadku kolizji nadajnik, któremu się nie udało (czyli ten, który nie odbierze CTS w oczekiwanym czasie) odcze-kuje losowy okres czasu i ponawia próbę. Używany jest tu algorytm binarnego odczekiwania wy­kładniczego, którym zajmiemy się, gdy przejdziemy do sieci Ethernet.

Na podstawie badań symulacyjnych MACA Bharghavan i in. (1994) dostroili MACA, tak by poprawić jego wydajność, i nazwali nowy protokół MACAW (MACA for Wireless). Po pierwsze zauważyli, że bez potwierdzeń w warstwie łącza danych utracone ramki były retransmitowane znacznie później, gdy ich brak został wykryty przez warstwę transportową. Rozwiązali ten problem, wprowadzając ramkę potwierdzającą (ACK) po każdej pomyślnie przesłanej ramce danych. Spostrzegli też, że CSMA przydaje się do czegoś, a konkretne do powstrzymania stacji przed wysłaniem RTS w tym samym czasie, gdy pobliska stacja również nadaje RTS do tego samego celu, więc zostało dodane wykrywanie nośnej. Oprócz tego zdecydowali się użyć algorytmu odczekiwania wykładni­czego dla każdego strumienia danych (pary źródło-cel) osobno, a nie dla każdej stacji. Ta zmiana poprawiła „uczciwość" protokołu. Na koniec dodali mechanizm wymiany pomiędzy stacjami infor­macji o zatorach i sposób na mniej gwałtowne reagowanie algorytmu odczekiwania wykładniczego na tymczasowe problemy, aby poprawić wydajność systemu.

4.3. Ethernet

Zakończyliśmy ogólny opis protokołów przydzielania kanału, więc pora zobaczyć, jak te reguły sto­sują się do rzeczywistych systemów, a zwłaszcza sieci LAN. Jak powiedzieliśmy w punkcie 1.5.3, IEEE utworzyła standardy dla szeregu sieci lokalnych i miejskich pod nazwą IEEE 802. Kilka z nich przeżyło, lecz wiele nie, jak widać z tabeli 1.4. Niektórzy wierzący w reinkarnację sądzą, że Karol Darwin powrócił jako członek IEEE, aby wyplewić najsłabsze protokoły. Do najważniejszych, które przetrwały, zaliczają się 802.3 (Ethernet) i 802.11 (bezprzewodowe LAN). W przypadku 802.15 (Blu-etooth) i 802.16 (bezprzewodowe sieci miejskie) jeszcze za wcześnie, żeby można było coś powie­dzieć. Proszę sprawdzić w piątym wydaniu niniejszej książki. 802.3 i 802.11 mają odmienne warstwy fizyczne i podwarstwy MAC, lecz zbiegają się w tej samej podwarstwie sterowania łączem logicz­nym, więc mają ten sam interfejs do warstwy sieciowej.

Wprowadzenie do sieci Ethernet przedstawiliśmy w punkcie 1.5.3 i nie będziemy tu powta­rzać tych informacji. Zamiast tego skoncentrujemy się na technicznych aspektach Ethernetu, proto­kołach i najnowszych osiągnięciach w dziedzinie szybkich (gigabitowych) sieci Ethernet. Ponie­waż Ethernet i IEEE 802.3 są identyczne z wyjątkiem dwóch pomniejszych różnic, które za chwilę omówimy, często stosuje się pojęcia „Ethernet" i „IEEE 802.3" zamiennie i my też tak będziemy robić. Dodatkowe informacje o sieciach Ethernet przedstawili Breyer i Riley (1999), Seifert (1998) oraz Spurgeon (2000).

4.3.1. Okablowanie sieci Ethernet

Ponieważ nazwa „Ethernet" odnosi się do kabla („eter" jako „medium"), zaczniemy właśnie od oka­blowania. Powszechnie używa się czterech typów kabli porównanych w tabeli 4.1.

TABELA 4.1.

Najpopularniejsze typy okablowania Ethernet

Nazwa	Kabel	Maks. segment	Węzły na segment	Zalety
10Base5	Gruby koncentryk	500 m	100	Oryginalny kabel, dziś przestarzały.
10Base2	Cienki koncentryk	185 m	30	Nie potrzeba koncentratora.
10Base-T	Skrętka	100 m	1024	Najtańszy system.
10Base-F	Światłowód	2000 m	1024	Najlepszy do połączeń między
				budynkami.

Historycznie pierwsze było okablowanie typu 10Base5, popularnie zwane grubym Etherne­tem (thick Ethernet). Kabel przypomina żółty wąż ogrodniczy z oznaczeniami co 2,5 metra w miej­scach na rozgałęźniki (standard 802.3 nie wymaga, żeby kabel był żółty, ale naprawdę to zaleca). Połączenia z kablem wykonywane są zasadniczo przez tzw. rozgałęźniki-wampiry (vampire tap), w których szpilka jest bardzo precyzyjnie wbijana do połowy do rdzenia kabla koncentrycznego. Zapis „10Base5" oznacza, że sieć działa z szybkością 10 Mb/s, używa sygnalizacji w paśmie podsta­wowym i pozwala na segmenty o długości do 500 metrów. Pierwsza liczba oznacza szybkość w Mb/s. Następnie słowo „Base" (czasem zapisywane „BASE") oznacza transmisję w paśmie podstawo­wym (baseband). Istniała kiedyś odmiana szerokopasmowa, 10Broad36, lecz nigdy nie przyjęła się na rynku i już się jej nie spotyka. Na koniec, jeśli medium jest kabel koncentryczny, długość zostaje podana w zaokrągleniu do 100-metrowych jednostek po słowie „Base".

Historycznie drugim typem kabla był 10Base2, inaczej cienki Ethernet (thin Ethernet), który w przeciwieństwie do grubego Ethernetu, przypominającego wąż ogrodniczy, można łatwo zginać. Połączenia z nim wykonywane są za pomocą standardowych złączy BNC i złączek typu T zamiast rozgałęźników-wampirów. Złącza BNC są łatwiejsze w użyciu i bardziej niezawodne. Cienki Ether­net jest o wiele tańszy i łatwiejszy w instalacji, lecz segment może mieć najwyżej 185 metrów i łączyć maksymalnie 30 urządzeń.

W obu mediach poważnym problemem może być wykrywanie przerw w kablu, złych rozgałęź­ników i luźnych złączy. Z tego powodu opracowano techniki wyszukiwania takich uszkodzeń, które zasadniczo polegają na wysłaniu impulsu w kabel. Gdy impuls trafi na przeszkodę lub koniec ka­bla, pojawi się echo. Dokładny pomiar czasu pomiędzy wysłanym impulsem i odebranym echem umożliwia lokalizację źródła odbicia. Ta technika nosi nazwę reflektometrii w domenie czasu.

Problemy z wykrywaniem przerw w kablu były motywacją do przechodzenia systemów na inny schemat okablowania, w którym z każdej stacji biegnie kabel do centralnego koncentratora. W nim wszystkie kable są łączone elektrycznie (jakby były zlutowane razem). Najczęściej służy do tego skrętka telefoniczna, ponieważ większość budynków biurowych jest już tak okablowana i zwykle mnóstwo par przewodów jest dostępnych. Ten schemat nosi nazwę 10Base-T. Koncentratory nie buforują wchodzącego ruchu. W dalszej części rozdziału omówimy ulepszoną wersję tego pomy­słu (przełączniki), które buforują przychodzące dane.

Trzy powyższe schematy okablowania przedstawia rysunek 4.13. Dla 10Base5 na kabel nałożo­ny jest i zaciśnięty nadajnik-odbiornik, którego wyprowadzenie kontaktuje się elektrycznie z rdze­niem kabla. Nadajnik-odbiornik zawiera elektronikę, która wykrywa nośną i kolizje. Przy wykry­ciu kolizji nadajnik-odbiornik wysyła w kabel specjalny niepoprawny sygnał, aby zagwarantować powiadomienie wszystkich pozostałych nadajników-odbiorników o kolizji.

W 10Base5 kabel nadajnika-odbiornika (inaczej kabel dołączeniowy) łączy nadajnik-odbiornik z kartą interfejsu w komputerze. Kabel nadajnika-odbiornika może mieć do 50 metrów długości i zawiera pięć osobno ekranowanych skrętek. Dwie pary przeznaczone są odpowiednio na transmisję danych w obie strony. Dwie kolejne służą do przesyłania w obie strony sygnałów sterują­cych. Piąta para, nie zawsze używana, pozwala na zasilanie elektroniki nadajnika-odbiornika z kom­putera. Niektóre nadajniki-odbiorniki pozwalają na podłączenie do nich maksymalnie ośmiu pobli­skich komputerów, aby zmniejszyć liczbę potrzebnych nadajników-odbiorników.

Kabel dołączeniowy kończy się na karcie interfejsu wewnątrz komputera. Karta ta zawiera układ scalony sterownika, który przesyła ramki do i z nadajnika-odbiornika. Sterownik odpowiada za skła­danie danych we właściwy format ramek oraz obliczanie sum kontrolnych w ramkach wychodzących i ich weryfikację w ramkach wchodzących. Niektóre układy sterowników zarządzają też pulą bu­forów dla ramek wejściowych, kolejką buforów do wysłania, dostępem bezpośrednim do pamięci komputera macierzystego i innymi aspektami zarządzania siecią.

W przypadku 10Base2 połączenie z kablem to po prostu pasywne złącze BNC typu T. Elektronika nadajnika-odbiornika mieści się na karcie sterownika, a każda stacja ma własny nadajnik-odbiornik.

W l0Base-T nie ma w ogóle wspólnego kabla, a jedynie koncentrator (pudełko nafaszerowane elektroniką), z którym każda stacja łączy się dedykowanym (tzn. nie wspólnym) kablem. Dodawa­nie i odłączanie stacji jest w tej konfiguracji prostsze, a uszkodzenia kabli można z łatwością wykryć. Wadą l0Base-T jest to, że maksymalna długość kabla biegnącego z koncentratora może wynosić tylko 100 metrów, może 200, jeśli użyje się bardzo wysokiej jakości kabla kategorii 5. Mimo to standard l0Base-T szybko zdobył przewagę, ponieważ używa istniejącego okablowania i jest ła­twy w utrzymaniu. W dalszej części rozdziału omówimy szybszą wersję l0Base-T (l00Base-T).

Czwartą opcję dla sieci Ethernet stanowi l0Base-F (okablowanie światłowodowe). Jest to droga alternatywa z uwagi na koszty złączy i terminatorów, lecz zapewnia doskonałą odporność na zakłócenia i jest najlepszą metodą łączenia budynków lub odległych od siebie koncentratorów. Dopuszczalne są połączenia długości rzędu kilometrów. Oprócz tego l0Base-F zapewnia dobre bezpieczeństwo, ponieważ podsłuchiwanie łącza światłowodowego jest o wiele trudniejsze niż pod­słuch na kablu miedzianym.

Rysunek 4.14 przedstawia różne metody okablowania budynku. Na rysunku 4.14 (a) pojedyn­czy kabel wije się od pokoju do pokoju, a każda stacja podpina się do niego w najbliższym punkcie. Na rysunku 4.14 (b) pionowy „kręgosłup" biegnie od piwnicy aż do dachu, a poziome kable na każdym piętrze łączą się z kręgosłupem poprzez specjalne wzmacniacze (wzmacniaki).

W niektórych budynkach kable poziome są cienkie, a sieć szkieletowa gruba. Najbardziej ogólną topologią jest drzewo, jak na rysunku 4.14 (c), ponieważ sieć z dwoma ścieżkami pomiędzy jaki­miś parami stacji miałaby problemy z zakłóceniami pomiędzy tymi dwoma sygnałami.

Każda wersja sieci Ethernet ma jakąś maksymalną długość kabla w pojedynczym segmencie. Aby pozwolić na większe sieci, można łączyć kable wzmacnia kam i. jak na rysunku 4.14 (d). Wzmacniak jest urządzeniem warstwy fizycznej: odbiera, wzmacnia (regeneruje) i przesyła dalej sygnały w obu kierunkach. Z punktu widzenia oprogramowania seria segmentów kabla połączo­nych wzmacniakami nie różni się niczym od pojedynczego kabla (poza opóźnieniami wprowadza­nymi przez wzmacniaki). System może zawierać wiele segmentów kabla i wiele wzmacniaków, lecz żadne dwa nadajniki-odbiorniki nie mogą być od siebie odległe o więcej niż 2,5 km i żadna ścieżka pomiędzy dowolnymi dwoma nadajnikami-odbiornikami nie może przechodzić przez wię­cej niż cztery wzmacniaki.

4.3.2. Kodowanie Manchester

Żadna z wersji Ethernetu nie stosuje prostego kodowania binarnego, w którym 0 V odpowiada „0" lo­gicznemu, a 5 V jedynce logicznej, ponieważ prowadziłoby to do wieloznaczności. Gdyby jedna sta­cja nadała łańcuch bitów 00010000, inne mogłyby go fałszywie zinterpretować jako 10000000 lub 01000000, ponieważ nie mogłyby rozróżnić pomiędzy bezczynnym nadajnikiem (0 V) a bitem „0" (0 V). Można rozwiązać ten problem, używając +1 V dla „1" i -1 V dla „0", lecz nadal pozostaje pro­blem próbkowania sygnału przez odbiornik z nieco inną częstotliwością niż ta, której nadajnik użył do wygenerowania go. Różne szybkości zegara mogą spowodować utratę synchronizacji granic bi­tów pomiędzy nadajnikiem i odbiornikiem, zwłaszcza po długim ciągu następujących po sobie zer lub ciągu jedynek.

Potrzeba nam metody pozwalającej odbiornikom w sposób jednoznaczny ustalić początek, ko­niec lub środek każdego bitu bez odwoływania się do zewnętrznego zegara. Dwa takie podejścia noszą nazwę kodowania Manchester i różnicowego kodowania Manchester. W kodzie Manche­ster okres każdego bitu jest dzielony na dwa równe odcinki. Binarna „1" jest przesyłana przez usta­wienie wysokiego napięcia w pierwszej połówce i niskiego w drugiej. Zero jest po prostu odwrot­nością: najpierw poziom niski, a potem wysoki.

Ten schemat gwarantuje, że każdy okres bitu ma w środku przejście między poziomami ułatwiają­ce synchronizację odbiornika z nadajnikiem. Wadą kodowania Manchester jest to, że wymaga dwukrotnie więcej pasma niż proste kodowanie binarne, ponieważ impulsy mają szerokość o połowę krótszą. Na przykład, aby wysyłać dane z szybkością 10 Mb/s, sygnał musi zmieniać się 20 milionów razy na sekundę. Kodowanie Manchester przedstawia rysunek 4.15 (b).

Różnicowe kodowanie Manchester, przedstawione na rysunku 4.15 (c), jest odmianą podsta­wowego kodowania Manchester. W tej wersji bit „1" oznacza brak przejścia na początku interwału, natomiast „0" jest sygnalizowane przez zmianę stanu na początku. W obu przypadkach w połowie bitu również występuje przejście. Schemat różnicowy wymaga bardziej złożonego sprzętu, lecz zapewnia większą odporność na zakłócenia. Poziom wysoki sygnału to +0,85 V, a niski -0,85V, co daje składową stałą sygnału równą 0 V. Ethernet nie wykorzystuje różnicowego kodowania Manchester, lecz inne sieci LAN (np. 802.5 Token Ring) korzystają z niego.

4.3.3. Protokół podwarstwy MAC w sieciach Ethernet

Rysunek 4.16 (a) przedstawia oryginalną strukturę ramki DIX (DEC, Intel, Xerox). Każda ramka zaczyna się od 8-bajtowej preambuły, w której każdy bajt zawiera ciąg 10101010. Zakodowanie tego wzorca kodem Manchester daje falę prostokątną o częstotliwości 10 MHz i długości 6,4 us pozwalającą zsynchronizować zegar odbiornika z zegarem nadajnika. Od nadajnika i odbiornika wymaga się, by zachowały synchronizację aż do końca ramki, używając kodowania Manchester do rozpoznawania granic bitów.

RYSUNEK 4.16. Formaty ramek: (a) DIX Ethernet, (b) IEEE 802.3

-

Ramka zawiera dwa adresy, źródłowy i docelowy. Standard dopuszcza adresy o długości 2 lub 6 bajtów, lecz parametry zdefiniowane dla standardu 10 Mb/s w paśmie podstawowym pozwalają tylko na adresy 6-bajtowe. Najstarszy bit adresu docelowego to „0" dla zwykłych adresów i „1" dla adresów grupowych. Adresy grupowe pozwalają na nasłuchiwanie przez wiele stacji na jednym adresie. Gdy ramka zostaje wysłana na adres grupowy, odbierają ją wszystkie stacje należące do orupy. Taka technika nosi nazwę multiemisji (multicast). Adres składający się wyłącznie z bitów J" jest zarezerwowany na rozgłoszenia (broadcast). Ramka, w której polu adresu docelowego znajdują się same jedynki, jest akceptowana przez wszystkie stacje w sieci. Różnica pomiędzy ad­resowaniem grupowym i rozgłaszaniem jest na tyle ważna, że warto ją powtórzyć. Ramka grupo­wa jest przeznaczona w Ethernecie dla grupy wybranych stacji; ramka rozgłoszeniowa jest wysyłana do wszystkich stacji w sieci Ethernet. Multiemisja jest bardziej selektywna, lecz wiąże się z zarzą­dzaniem grupami. Rozgłaszanie jest bardziej toporne, lecz nie wymaga zarządzania grupami.

Inną ciekawą cechą adresowania jest użycie bitu 46. (sąsiadującego z najstarszym bitem) do rozróżniania pomiędzy adresami lokalnymi i globalnymi. Adresy lokalne są przydzielane przez każ­dego administratora sieci i nie mają żadnego znaczenia poza siecią lokalną. Adresy globalne są przyznawane centralnie przez IEEE, aby zagwarantować, że żadna para stacji na całym świecie nie będzie miała identycznych adresów. Przy dostępnych 46 bitach (48 - 2) istnieje około 7 x 10¹³ adresów globalnych. Idea polega na tym, że każda stacja może jednoznacznie adresować każdą inną stację, podając poprawny 48-bitowy numer. Znalezienie stacji docelowej jest zadaniem warstwy sieciowej.

Następne jest pole Typ, które informuje odbiornik, co ma zrobić z ramką. W jednym kompu­terze może być jednocześnie używanych kilka protokołów warstwy sieciowej, więc gdy przycho­dzi ramka Ethernet, jądro musi wiedzieć, dokąd ją przekazać. Pole typu wskazuje proces, dla któ­rego przeznaczona jest ramka..

Następne są dane, maksymalnie 1500 bajtów. Ten limit został ustalony raczej arbitralnie w cza­sie, gdy standard DIX był ustalany na wieki, głównie w oparciu o fakt, że nadajnik-odbiornik musi pomieścić całą ramkę w pamięci RAM, a pamięć RAM była w roku 1978 droga. Wyższy limit oznaczałby więcej RAM, czyli droższy nadajnik-odbiornik.

Oprócz maksymalnej jest jeszcze minimalna długość ramki. Wprawdzie pole danych o długości 0 bajtów jest czasem przydatne, lecz powoduje problem. Gdy nadajnik-odbiornik wykrywa kolizję, prze­rywa bieżącą ramkę, co oznacza, że bezdomne bity i kawałki ramek cały czas pojawiają się w kablu. Aby łatwiej odróżnić poprawne ramki od śmieci, Ethernet wymaga minimalnej długości ramki równej 64 bajty, od adresu docelowego aż do sumy kontrolnej włącznie. Jeśli dane zawarte w ram­ce mają mniej niż 46 bajtów, pole wypełnienie służy do dopełnienia ramki do minimalnej długości

Kolejnym (i ważniejszym) powodem dla minimalnej długości ramki jest zapobieganie przed ukończeniem transmisji krótkiej ramki przez stację, zanim pierwszy bit w ogóle dotrze do końca kabla, gdzie może zderzyć się z inną ramką. Ten problem został przedstawiony na rysunku 4.17. W chwili 0 stacja A na jednym końcu sieci wysyła ramkę. Oznaczmy czas propagacji ramki do drugiego końca sieci symbolem τ. Tuz przed dotarciem ramki do drugiego końca (czyli w chwili τ - ε) najbardziej odległa stacja B zaczyna nadawać. Gdy B odkryje, że odbiera silniejszy sygnał niż wy­słała, rozpoznaje wystąpienie kolizji, wobec czego przerywa swoją transmisję i generuje 48-bitowy pakiet zakłócający, aby ostrzec wszystkie pozostałe stacje. Inaczej mówiąc, zakłóca kanał, aby zapewnić, że nadajnik nie przeoczy kolizji. W chwili mniej więcej 2τ nadajnik odbiera impuls zakłócający i również przerywa swoją transmisję, po czym odczekuje losowy okres czasu przed ponowieniem próby.

Jeśli stacja będzie próbowała wysłać bardzo krótką ramkę, to może się zdarzyć, że wystąpi kolizja, lecz transmisja zostanie ukończona przed powrotem impulsu zakłócającego w chwili 2τ. Nadajnik dojdzie wówczas do błędnego wniosku, że ramka została wysłana pomyślnie. Aby zapo­biec takim sytuacjom, wysyłanie każdej ramki musi trwać dłużej niż 2τ, aby transmisja jeszcze trwała, gdy impuls zakłócający powróci do nadajnika. Dla sieci LAN 10 Mb/s o maksymalnej dłu­gości 2500 m z czterema wzmacniakami (według specyfikacji 802.3) czas podróży w dwie strony (łącznie z czasem propagacji przez wzmacniaki) został ustalony na niemal 50 µs w najgorszym Przypadku, razem z niezerowym czasem przejścia przez wzmacniaki. Przy 10 Mb/s bit zajmuje 100 ns, więc najmniejsza ramka, która na pewno będzie działać, ma 500 bitów. Aby dodać pewien margines bezpieczeństwa, wielkość ramki została zaokrąglona do 512 bitów czyli 64 bajtów. Ramki mające mniej niż 64 bajty są dopełniane do 64 bajtów za pomocą pola Wypełnienie.

Ze wzrostem szybkości sieci musi proporcjonalnie rosnąć minimalna długość ramki lub ma­leć maksymalna długość kabla. Dla 2500-metrowej sieci LAN działającej z szybkością 1 Gb/s mi­nimalna długość ramki musiałaby wynieść 6400 bajtów. Zamiast tego minimalna długość ramki może wynieść 640 bajtów, lecz maksymalna odległość pomiędzy dwoma stacjami musi być równa 250 metrów. Te ograniczenia stają się coraz bardziej dokuczliwe w miarę przechodzenia do wielo-gigabitowych sieci.

Ostatnie pole ramki Ethernet zawiera sumę kontrolną. Jest to 32-bitowy skrót danych. Jeśli jakieś bity danych zostaną odebrane z błędem (z powodu zakłóceń w kablu), suma kontrolna niemal na pewno będzie niewłaściwa i błąd zostanie wykryty. Stosowany algorytm sumy kontrolnej to CRC typu, jaki omawialiśmy w rozdziale 3. Pozwala on wykrywać błędy, lecz nie umożliwia ich korekty.

Gdy IEEE normalizował Ethernet, komitet wprowadził dwie zmiany w formacie DIX, jak na rysunku 4.16 (b). Pierwszą było skrócenie preambuły do 7 bajtów i użycie ostatniego bajta jako granicy początku ramki, aby zapewnić zgodność z 802.4 i 802.5. Druga polegała na zastąpieniu pola łyp polem Długość. Oczywiście teraz odbiornik w żaden sposób nie może ustalić, co powinien urobić z odebraną ramką, lecz ten problem został rozwiązany przez dodanie małego nagłówka do samej sekcji danych udostępniającego tę informację.

Niestety, w chwili, gdy 802.3 został opublikowany, tak wiele sprzętu i oprogramowania dla sieci DIX Ethernet było już w użytku, że niewielu producentów i użytkowników entuzjastycznie )odeszło do zamiany pola typu na pole długości ramki. W roku 1997 IEEE poddał się i stwierdził, :e obie wersje są w porządku. Na szczęście wszystkie pola Typ używane przed 1997 miały wartość wyższą niż 1500. Dzięki temu każda liczba w tym polu mniejsza lub równa 1500 może być interpretowana jako długość, a wyższa niż 1500 jako typ ramki. Teraz IEEE może utrzymywać, że wszyscy używają ich standardu, a cała reszta może robić to, co poprzednio, nie mając z tego powodu wyrzutów sumienia.

4.3.4. Algorytm binarnego odczekiwania wykładniczego

Zobaczmy teraz, jak generuje się losowe odczekiwanie po kolizji. Model weźmiemy z rysunku 4.5. Po kolizji czas jest dzielony na dyskretne szczeliny, których długość jest równa czasowi propagacji nośniku w obie strony w najgorszym przypadku (2τ). Aby dostosować się do najdłuższej ścieżki dopuszczanej przez Ethernet, długość szczeliny została ustawiona na 512 okresów pojedynczych bitów, czyli 51,2 µs. Po pierwszej kolizji każda stacja odczekuje 0 albo 1 czas szczeliny przed ponowieniem próby. Jeśli dwie stacje po kolizji wybiorą ten sam numer losowy, kolizja wystąpi jeszcze raz. Po drugiej kolizji każda stacja wybierze losowo 0, 1, 2 lub 3 i odczeka tyleż szczelin. Jeśli wystąpi trzecia kolizja (jej prawdopodobieństwo wynosi 0,25), to następnym razem liczba szczelin do odczekania zostanie wybrana losowo od 0 do 2³ - 1. W ogólnej postaci po i kolizji wybierana jest losowa liczba całkowita z zakresu od 0 do 2ⁱ - 1 i tyle szczelin zostaje pominiętych. Jednakże po dojściu do dziesięciu kolizji okres randomizacji zostaje ustalony na maksymalnie 1023 szczeliny. Po 16 kolizjach sterownik poddaje się i zgłasza niepowodze­nie z powrotem do komputera. Dalsze przywracanie transmisji należy już do wyższych warstw.

Algorytm ten, zwany binarnym odczekiwaniem wykładniczym (ang. binary exponential backoff), został wybrany po to, aby dynamicznie dostosowywać oczekiwanie do liczby stacji próbu­jących nadawać. Gdyby okres randomizacji dla wszystkich kolizji wynosił 1023, prawdopodobień­stwo zderzenia transmisji dwóch stacji po raz drugi byłoby pomijalne, lecz średni czas oczekiwa­nia po kolizji wynosiłby setki okresów szczeliny, wprowadzając poważne opóźnienie. Z drugiej strony, gdyby każda stacja oczekiwała 0 lub 1 szczelinę, to gdyby 100 stacji spróbowało kiedykol­wiek nadawać jednocześnie, to kolidowałyby raz za razem, dopóki jedna z nich nie wybrałaby 1, a pozostałe 0. To mogłoby potrwać latami. Dzięki temu, że okres randomizacji rośnie wykładni­czo w miarę występowania coraz większej liczby kolizji, algorytm zapewnia małe opóźnienie przy kolizji niewielkiej liczby stacji, lecz również rozwiązywanie w rozsądnym czasie konfliktu, gdy koliduje wiele stacji. Ograniczenie odczekiwania na poziomie 1023 zapobiega zbyt dużemu wzro­stowi czasu oczekiwania.

Jak do tej pory mówiliśmy, CSMA/CD nie udostępnia potwierdzeń. Ponieważ sama nieobec­ność kolizji nie gwarantuje, że bity nie zostaną zniekształcone przez impulsy zakłóceń w kablu, dla niezawodnej komunikacji stacja docelowa musi zweryfikować sumę kontrolną, a jeśli ta będzie po­prawna, odesłać do nadajnika ramkę potwierdzającą. Zwykle potwierdzenie jest z punktu widzenia protokołu kolejną ramką i również musi walczyć o dostęp do kanału podobnie jak ramka danych. Jednakże prosta modyfikacja algorytmu rywalizacji pozwala na szybkie potwierdzenie odbioru ramki (Tokoro i Tamaru, 1977). Wystarczy zarezerwować pierwszą szczelinę okresu rywalizacji po pomyślnej transmisji dla jej odbiorcy. Niestety, standard nie zapewnia tej możliwości.

4.3.5. Wydajność sieci Ethernet

Maksimum A przypada na p = 1/k, przy czym A → l/e dla k→oo. Prawdopodobieństwo, że okres rywalizacji zawiera dokładnie j szczelin, wynosi A(1 - A)^j-1, więc średnia liczba szczelin w okresie rywalizacji wyniesie:

Przyjrzyjmy się teraz pokrótce wydajności Ethernetu w warunkach dużego, stałego obciążenia (tzn. k stacji jest zawsze gotowe nadawać). Dokładna analiza algorytmu binarnego odczekiwania wykładniczego jest skomplikowana. Zamiast tego pójdziemy śladami Metcalfe'a i Boggsa (1976) i za­łożymy stałe prawdopodobieństwo retransmisji w każdej szczelinie. Jeśli każda stacja nadaje w szczeli­nie rywalizacji z prawdopodobieństwem p, to prawdopodobieństwo A, że któraś stacja przejmie kanał w tej szczelinie, wynosi:

Ponieważ każda szczelina ma okres 2τ, średni okres rywalizacji, w, wynosi 2τ/A. Zakładając optymalne p, średnia liczba szczelin rywalizacji nigdy nie przekracza e, więc w wynosi maksymalnie 2τe « 5.4τ.

Jeśli wysłanie średniej ramki zajmuje P sekund, to gdy wiele stacji ma ramki do wysłania:

Widzimy tu. że maksymalna odległość kabla pomiędzy dowolnymi dwoma stacjami wchodzi do wy­ników wydajności, co prowadzi do stosowania topologii innych niż ta z rysunku 4.14 (a). Im dłuż­szy kabel, tym dłuższy okres rywalizacji. Ta obserwacja spowodowała, że Ethernet definiuje mak­symalną długość kabla.

Interesujące będzie wyrażenie równania (4.6) w zależności od długości ramki F, pasma prze­pustowości sieci 5, długości kabla L i szybkości propagacji sygnału c dla optymalnego przypadku e szczelin rywalizacji na ramkę. Przy P = F/B z równania (4.6) uzyskujemy:

Gdy drugi człon mianownika będzie duży, wydajność sieci będzie niska. Dokładniej mówiąc, zwięk­szenie przepustowości sieci lub odległości (iloczynu BL) zmniejsza wydajność dla danej wielkości ramki. Niestety, wiele badań nad sprzętem sieciowym dąży dokładnie do zwiększenia tej wartości. Użytkownicy chcą dużego pasma na duże odległości (na przykład w światłowodowych sieciach miejskich), z czego wynika, że taka implementacja Ethernetu może nie być najlepszym systemem w tych zastosowaniach. Poznamy inne sposoby implementacji Ethernetu, gdy przejdziemy w dalszej części rozdziału do sieci Ethernet opartych na koncentratorach przełączających.

Na rysunku 4.18 wydajność kanału została przedstawiona w zależności od liczby stacji gotowych do nadawania, dla 2τ = 51,2 us i szybkości transmisji danych 10 Mb/s i z wykorzystaniem równania (4.7). Przy 64-bajtowej długości szczeliny nie zaskakuje fakt, że 64-bajtowe ramki są mało wydajne. Z drugiej strony przy ramkach o długości 1024 bajtów i asymptotycznej wartości e 64-bajtowych szczelin na okres rywalizacji okres ten ma długość 174 bajtów, a wydajność wynosi 0,85.

Aby ustalić średnią liczbę stacji gotowych do nadawania w warunkach małego obciążenia, możemy użyć następującego (uproszczonego) spostrzeżenia: każda ramka zajmuje kanał na jeden okres rywalizacji i jeden czas transmisji, w sumie P + w sekund. Liczba ramek na sekundę wynosi więc l/(P + w). Jeśli każda stacja generuje ramki ze średnią szybkością λ ramek na sekundę, to gdy system jest w stanie k, łączna szybkość nadawania wszystkich niezablokowanych stacji wyno­si kλ ramek na sekundę. Ponieważ w stanie równowagi szybkości wejściowa i wejściowa muszą być identyczne, możemy porównać te dwa wyrażenia i rozwiązać równanie dla k (zwróćmy uwa­gę, że w jest funkcją k). Bardziej wyrafinowaną analizę przedstawiają Bertsekas i Gallager (1992).

Warto chyba wspomnieć, że dużo prac poświęcono analizie teoretycznej wydajności Ethernetu (i innych sieci). Praktycznie wszystkie te prace zakładały, że ruch w sieci ma rozkład Poissona. Gdy badacze zaczęli przyglądać się prawdziwym danym, okazało się, że ruch w sieci rzadko ma taki rozkład, lecz jest samopodobny (Paxson i Floyd, 1994, Willinger i in., 1995). Oznacza to, że uśrednianie w długich okresach czasu nie wygładza ruchu w sieci. Średnia liczba ramek w każdej

RYSUNEK 4.18. Wydajność sieci Ethernet przy 10 Mb/s i 512-bitowych czasach szczelin

minucie godziny ma taką samą wariancję jak średnia liczba ramek w każdej sekundzie minuty. Z tego odkrycia wynika, że większość modeli ruchu w sieci nie stosuje się do rzeczywistych warunków i do modeli tych należy podchodzić ze szczyptą (a raczej toną) rezerwy.

4.3.6. Przełączany Ethernet

W miarę dodawania coraz większej liczby stacji do sieci Ethernet ruch w sieci rośnie. W końcu LAN ulegnie nasyceniu. Jednym z wyjść może być przejście na wyższą szybkość, np. z 10 Mb/s na 100 Mb/s. Lecz rozwój multimediów powoduje, że nawet sieci Ethernet 100 Mb/s i 1 Gb/s mogą się nasycić.

Na szczęście istnieje dodatkowy sposób radzenia sobie ze zwiększonym obciążeniem — przełą­czany Ethernet, jak na rysunku 4.19. Sercem tego systemu jest przełącznik zawierający szybką płytę magistrali i zwykle miejsce na od 4 do 32 kart rozszerzających, z których każda zawiera od jednego do ośmiu złączy. Najczęściej każde złącze ma połączenie skrętką l0Base-T z pojedyn­czym komputerem-hostem.

Gdy stacja chce wysłać ramkę Ethernet, wysyła standardową ramkę do przełącznika. Karta od­bierająca ramkę może sprawdzić, czy ramka jest przeznaczona dla jednej z innych stacji podłączo­nych do tej samej karty. Jeśli tak, to ramka zostaje do niej skopiowana.

Jeśli nie, przełącznik przesyła ramkę przez płytę magistrali do karty stacji docelowej. Płyta pracuje zwykle z szybkością wielu Gb/s, używając własnego protokołu.

Co się dzieje, gdy dwa komputery podłączone do tej samej karty jednocześnie nadają ram­kę? To zależy od konstrukcji karty. Wszystkie porty na karcie mogą być połączone w jedną lokalną sieć LAN. Kolizje w takiej sieci LAN zbudowanej na karcie są wykrywane i obsługiwane tak jak wszelkie inne kolizje w sieci CSMA/CD — przez retransmisje stosujące algorytm binarnego odczekiwania wykładniczego. W karcie tego typu w danej chwili możliwa jest tylko jedna transmi­sja na kartę, lecz wszystkie karty mogą nadawać równolegle. Przy takiej strukturze każda karta tworzy swoją domenę kolizji niezależnie od pozostałych. Gdy w każdej domenie kolizji znajduje się tylko jedna stacja, kolizje są niemożliwe i wydajność wzrasta.

W drugim typie kart rozszerzających każdy port wejściowy jest buforowany, więc przycho­dzące ramki są zapisywane w pamięci RAM karty. Taka konstrukcja pozwala na jednoczesne od­bieranie (i wysyłanie) ramek przez wszystkie porty wejściowe, umożliwiając równoległe działanie pełnodupleksowe — coś, co nie jest możliwe przy CSMA/CD w jednym kanale. Po odebraniu całej ramki karta może sprawdzić, czy ramka jest adresowana do innego portu na tej samej karcie, czy do portu odległego. W pierwszym przypadku ramka może zostać wysłana wprost do odbiorcy. W drugim musi zostać przesłana przez płytę magistrali do właściwej karty. Tutaj każdy port jest odrębną domeną kolizji, więc kolizje nie występują. Całkowitą zdolność przepustową systemu można często zwiększyć o rząd wielkości w porównaniu z siecią 10Base5, w której cały system jest jedną domeną kolizji.

Ponieważ przełącznik oczekuje standardowych ramek Ethernet na każdym porcie wejściowym, to można użyć części portów jako koncentratorów. Na rysunku 4.19 port w prawym górnym rogu nie jest połączony z pojedynczą stacją, lecz z 12-portowym koncentratorem. Ramki docierające do koncentratora rywalizują o nośnik w standardowy sposób, obejmujący kolizje i binarne odczekiwanie wykładnicze. Pomyślnie wysłane ramki docierają do przełącznika i są traktowane jak wszelkie inne ramki przychodzące — komutowane do właściwej linii wyjściowej przez szybką płytę magi­strali. Koncentratory są szybsze od przełączników, lecz z uwagi na malejące ceny przełączników szybko stają się przestarzałe. Jednakże stare koncentratory nadal są używane.

13.7. Fast Ethernet

W tej nazwie zostało użyte słowo „fibrę", a nie „fiber", ponieważ autor dokumentu był Anglikiem.

Z początku 10 Mb/s wydawało się rajem na ziemi, podobnie jak modemy 1200 b/s dla wczesnych użytkowników akustycznych modemów 300 b/s. Lecz ta nowość szybko spowszedniała. Wygląda na o, że prawo Parkinsona („praca wypełnia cały czas przeznaczony na jej wykonanie") można rozszerzyć na dane, które wypełniają całe pasmo dostępne dla ich transmisji. Aby podkręcić szybkość sieci, różne grupy branżowe zaproponowały dwie nowe optyczne sieci LAN o topologii pierścienia, pierwsza nosiła nazwę FDDI (Fiber Distributed Data Interface), a druga Fibrę Channel¹. Krótko mówiąc, obie były używane jako sieci szkieletowe, lecz żadna nie zadomowiła się w komputerach biurkowych. W obu przypadkach zarządzanie stacjami było zbyt skomplikowane, co prowadziło do powstania złożonej elektroniki i wysokich cen. Lekcję, która powinna była zostać z tego wyciągnięta, podsumowuje amerykańska maksyma KISS (Keep it Simple, Stupid — nie komplikuj, idioto).

Tak czy owak, umiarkowane powodzenie optycznych sieci LAN pozostawiło lukę dla stan­dardowego Ethernetu o szybkości powyżej 10 Mb/s. Wiele instalacji potrzebowało większej prze­pustowości, więc składało się z licznych sieci lokalnych 10 Mb/s połączonych labiryntem wzmacniaków, mostów, routerów i bram, aczkolwiek administratorzy takich sieci często odnosili wrażenie, że całość trzyma się na ślinę i słowo honoru.

W takich właśnie warunkach IEEE zebrał z powrotem komitet 802.3 w roku 1992 z poleceniem opracowania szybszej sieci LAN. Jedna z propozycji polegała na zachowaniu standardu 802.3 bez zmian, jedynie przyspieszenie go. Inna zakładała całkowite przerobienie standardu, aby dać mu mnóstwo nowych funkcji, takich jak transmisje w czasie rzeczywistym i głos cyfrowy, lecz z za­chowaniem starej nazwy (z powodów marketingowych). Po pewnych sporach komitet zdecydował się zachować 802.3 bez zmian i tylko przyspieszyć. Grupa autorów drugiej propozycji zrobiła tak, jak postąpiłby każdy w branży komputerowej w takich warunkach — trzasnęła drzwiami, utworzyła własny komitet i tak czy inaczej znormalizowała własną sieć LAN (później znaną pod nazwą 802.12). Ten standard padł kompletnie.

Komitet 802.3 zdecydował się na podrasowany Ethernet z trzech podstawowych powodów:

1. Potrzeba zgodności wstecz z istniejącymi sieciami lokalnymi Ethernet.

2. Obawa, że w nowym protokole mogą wystąpić nieprzewidziane problemy.

3. Chęć ukończenia pracy, zanim zmieni się technologia.

Prace postępowały szybko (jak na komitet tworzący standard) i wynik, 802.3u, został oficjalnie zaapro­bowany przez IEEE w czerwcu 1995. Technicznie 802.3u nie jest nowym standardem, lecz dodatkiem do istniejącego standardu 802.3 (aby podkreślić jego zgodność wstecz). Ponieważ praktycznie wszy­scy nazywają go „szybkim Ethernetem" (Fast Ethernet), a nie 802.3u, my też tak zrobimy.

Podstawowe założenie było proste: zachować wszystkie stare formaty ramek, interfejsy i reguły procedur, lecz skrócić okres bitu ze 100 ns do 10 ns. Technicznie można było po prostu skopiować 10Base5 albo 10Base2 i nadal wykrywać kolizje przez dziesięciokrotne skrócenie maksymalnej długości kabla. Jednakże zalety okablowania 10Base-T były tak ogromne, że Fast Ethernet opiera się na nim w całości. Wobec tego wszystkie systemy Fast Ethernet stosują koncentratory i prze­łączniki; kable wielogałęziowe z rozgałęźnikami-wampirami i złączami BNC nie są dozwolone.

Mimo to trzeba było dokonać pewnych wyborów, z których najważniejszym był wybór stoso­wanych typów kabla. Jednym z proponowanych była skrętka kategorii 3. Przemawiał za nią fakt, że praktycznie każde biuro w krajach zachodnich dysponuje przynajmniej czterema skrętkami ka­tegorii 3. (lub lepszej) biegnącymi do telefonicznej szafki kablowej położonej w zasięgu 100 m. Czasami dostępne są dwa takie kable. Wobec tego użycie skrętki kategorii 3. umożliwiło łączenie komputerów biurkowych szybkim Ethernetem bez konieczności kładzenia nowego okablowania w całym budynku, co jest ogromną zaletą dla wielu firm i organizacji.

Główną wadą skrętki kategorii 3. jest niezdolność do przenoszenia sygnałów 200-megabodowych (100 Mb/s z kodowaniem Manchester) na odległość 100 metrów, co jest maksymalną odległością pomiędzy komputerem i koncentratorem zdefiniowaną dla lOBase-T (patrz tabela 4.1). Okablowanie skrętką kategorii 5. z łatwością radzi sobie z tą odległością, a światłowody mogą mieć jeszcze większy zasięg. Został wybrany kompromis pozwalający na wszystkie trzy opcje przedstawione w tabeli 4.2 i jednocześnie pozwalający zwiększyć przepustowość w sieciach używających skrętki kategorii 3.

Odmiana z UTP kategorii 3., zwana 100Base-T4, używa szybkości sygnalizacji 25 MHz, jedynie o 25% wyższej od standardowej 20 MHz w sieci Ethernet (pamiętajmy, że kodowanie Manchester, jak na rysunku 4.15, wymaga dwóch okresów zegara dla każdego z 10 milionów bitów w sekundzie). Aby jednak osiągnąć niezbędną przepustowość, 100Base-T4 wymaga czterech skrętek. Ponieważ standardowe kable telefoniczne przez dziesiątki lat miały po cztery pary skręconych przewodów, w większości biur nie było problemów z zainstalowaniem łącza. Oczywiście oznaczało to rezy­gnację z telefonu na biurku, ale to niewielka cena za szybszą pocztę e-mail.

Z czterech skrętek jedna zawsze służy do transmisji do koncentratora, druga zawsze z kon­centratora, a dwie pozostałe są przełączane zależnie od aktualnego kierunku transmisji. Aby osiągnąć niezbędną przepustowość, zrezygnowano z kodowania Manchester, lecz przy nowoczesnych zega­rach i tak niewielkich odległościach nie jest już to potrzebne. Oprócz tego wysyłane są sygnały trójko­we, więc w jednym okresie zegara w kablu może być przesłana wartość 0, 1 lub 2. Przy trzech skręt­kach dla jednego kierunku i sygnalizacji trójkowej można nadać 27 różnych symboli, co umożliwia przesyłanie 4 bitów z pewną redundancją. Transmisja 4 bitów w każdym z 25 milionów cykli zegara daje niezbędne 100 Mb/s. Oprócz tego zawsze jest dostępny kanał zwrotny o przepustowości 33,3 Mb/s wykorzystujący czwartą skrętkę. Taki schemat, znany pod nazwą 8B/6T (8 bitów mapowanych na 6 „tritów"), raczej nie dostanie żadnej nagrody za elegancję, ale działa w istniejącym okablowaniu.

Rozwiązanie dla okablowania kategorii 5. (100Base-TX) jest prostsze, ponieważ kable potrafią przenosić impulsy z częstotliwością 125 MHz. Używane są tylko dwie pary skręconych przewodów na stację: jedna do koncentratora i jedna z koncentratora. Nie jest stosowane proste kodowanie binarne, lecz schemat o nazwie 4B/5B wzięty z FDDI i zgodny z tym standardem. Każda grupa pięciu okre­sów zegara, z których każdy zawiera jedną z dwóch wartości sygnału, daje 32 kombinacje. Szesna­ście z nich jest używanych do nadawania czterobitowych grup 0000, 0001, 0010, ..., 1111. Część z pozostałych szesnastu ma przeznaczenie sterujące, np. do oznaczania granic ramek. Kombinacje zostały tak wybrane, aby zapewnić wystarczającą liczbę przejść do zachowania synchronizacji zegara. System 100Base-TX jest pełnodupleksowy; stacje mogą jednocześnie nadawać i odbierać z szybko­ścią 100 Mb/s. Systemy 100Base-TX i 100Base-T4 są czasem nazywane kolektywnie l00Base-T.

Ostatnia opcja, 100Base-FX, używa dwóch włókien wielomodowego światłowodu, po jednym w każdą stronę, więc również jest pełnodupleksowa i daje 100 Mb/s w każdym kierunku. Poza tym odległość pomiędzy stacją i koncentratorem może wynosić do 2 km.

Na ogólne życzenie komitet 802 w roku 1997 dodał nowy typ okablowania, 100Base-T2, po­zwalający na budowanie sieci Fast Ethernet z wykorzystaniem dwóch skrętek kategorii 3. Do ob­sługi niezbędnego schematu kodowania jest jednak niezbędny zaawansowany procesor sygnałowy, przez co ta opcja jest dość kosztowna. Jak do tej pory jest używany rzadko, z uwagi na złożoność, cenę i fakt, że w wielu budynkach biurowych położono już nowe okablowanie kategorii 5. UTP.

W l00Base-T możliwe są dwa typy urządzeń łączących stacje: koncentratory i przełączniki, jak na rysunku 4.19. W koncentratorze wszystkie wchodzące linie (a przynajmniej wszystkie linie wchodzące do jednej karty rozszerzającej) są połączone logicznie, tworząc jedną domenę kolizji. Stosują się tu wszystkie standardowe reguły, w tym algorytm binarnego odczekiwania wykładni­czego, więc cały system działa jak staroświecki Ethernet. Inaczej mówiąc, koncentratory wymagają komunikacji półdupłeksowej.

W przełączniku każda przychodząca ramka jest buforowana w karcie rozszerzającej i w razie konieczności przekazywana przez szybką płytę magistrali do karty docelowej. Interfejs płyty magi­strali nie został znormalizowany i nie musi być, ponieważ jest całkowicie ukryty wewnątrz przełącz­nika. Jeśli można sugerować się dotychczasowymi doświadczeniami, producenci będą prześcigać się w konstruowaniu coraz szybszych płyt magistrali, aby zwiększyć zdolność przepustową systemu. Ponieważ kable 100Base-FX są zbyt długie dla standardowego algorytmu kolizji w sieciach Ethernet, to muszą być podłączane do przełączników, aby każdy był odrębną domeną kolizji. W 100Base-FX koncentratory nie są dozwolone.

Możemy na koniec zanotować, że praktycznie każdy przełącznik potrafi obsługiwać mieszankę stacji 10 Mb/s i 100 Mb/s, aby ułatwić proces modernizacji. Gdy firma będzie nabywała kolejne stacje robocze 100 Mb/s, wystarczy że dokupi niezbędne karty rozszerzające i włoży je do przełącznika W rzeczy samej już sam standard udostępnia sposób automatycznej negocjacji przez dwie stacje optymalnej szybkości (10 lub 100 Mb/s) i trybu transmisji (pół- lub pełnodupleksowego). Większość szybkich urządzeń Ethernet używa tej funkcji do automatycznej konfiguracji siebie samych.

4.3.8. Gigabit Ethernet

Ledwie wysechł atrament na standardzie Fast Ethernet, a komitet 802 zaczął prace nad jeszcze szybszym Ethernetem (1995). Ten standard szybko zyskał przydomek Gigabit Ethernet i został ratyfikowany przez IEEE w roku 1998 pod nazwą 802.3z. Identyfikator ten sugeruje, że gigabitowy Ethernet to ostatni z serii, chyba że ktoś szybko wymyśli literę po z. Poniżej przedstawimy kilka najważniej szych cech standardu Gigabit Ethernet. Więcej informacji na ten temat przedstawia Seifert (1998).

Cele komitetu 802.3z były zasadniczo takie same jak komitetu 802.3u — dziesięciokrotnie przyspieszyć Ethernet, lecz zachować zgodność wstecz z wszystkimi istniejącymi standardami te sieci. Dokładnie mówiąc, Gigabit Ethernet miał oferować usługę niepotwierdzonych datagramów z transmisjami pojedynczymi i grupowymi, używać tego samego 48-bitowego schematu adreso­wania, który jest już stosowany i zachować ten sam format ramki, łącznie z minimalnymi i mak­symalnymi wielkościami ramek. Ostateczny standard spełnił wszystkie te założenia.

Cała konfiguracja gigabitowego Ethernetu jest dwupunktowa, a nie wielogałęziowa jak w ory­ginalnym standardzie 10 Mb/s, który zdążył zostać uhonorowany nazwą classic Ethernet. W naj­prostszej konfiguracji sieci Gigabit Ethernet, przedstawionej na rysunku 4.20 (a), dwa komputery sć ze sobą połączone bezpośrednio. Jednakże bardziej typowym przypadkiem jest kilka komputerów podłączonych do koncentratora lub przełącznika, z którym mogą być połączone kolejne przełącznik lub koncentratory, jak na rysunku 4.20 (b). W obu konfiguracjach każdy indywidualny kabel Et­hernet może łączyć dokładnie dwa urządzenia, nie więcej i nie mniej.

RYSUNEK 4.20. (a) Dwustacyjny Ethernet, (b) Wielostacyjny Ethernet

Gigabit Ethernet obsługuje dwa różne tryby działania: pełnodupleksowy i półdupleksowy. „Normalnym" trybem jest pełny dupleks, który pozwala na jednoczesny ruch w obu kierunkach. Ten tryb jest stosowany, gdy komputery (i przełączniki) są połączone z centralnym przełączni­kiem. W tej konfiguracji wszystkie linie są buforowane, więc każdy komputer i przełącznik może wysyłać ramki w każdej chwili. Nadajnik nie musi wykrywać stanu nośnika, aby sprawdzić, czy ktoś go nie używa, ponieważ rywalizacja jest tu niemożliwa. Na linii pomiędzy komputerem i prze­łącznikiem komputer jest jedynym możliwym nadajnikiem wysyłającym ramki w stronę przełącz­nika, więc transmisja powiedzie się nawet wtedy, gdy przełącznik będzie w tej samej chwili wy­syłał ramkę do komputera (linia jest pełnodupleksowa). Ponieważ rywalizacja jest niemożliwa, protokół CSMA/CD nie jest używany, więc o maksymalnej długości kabla decyduje raczej kwestia mocy sygnału, a nie maksymalny czas propagacji impulsu zakłócającego z powrotem do nadajni­ka. Przełączniki mogą dowolnie mieszać szybkości transmisji. Automatyczna konfiguracja jest ob­sługiwana tak samo jak w sieci Fast Ethernet.

Drugi tryb działania, półdupleksowy, jest używany, gdy komputery są podłączone do koncentrato­ra zamiast do przełącznika. Koncentrator nie buforuje przychodzących ramek. Zamiast tego łączy we­wnątrz elektrycznie wszystkie linie, symulując wielogałęziowy kabel używany w klasycznym Ethernecie. W tym trybie kolizje mogą występować, więc niezbędny jest protokół CSMA/CD. Ponieważ ramka o minimalnej wielkości (64 bajty) może teraz zostać przesłana stukrotnie szybciej niż w klasycznym Ethernecie, maksymalny dystans jest stukrotnie mniejszy i wynosi 25 metrów, aby zachować założenie, iż nadajnik wciąż będzie nadawał ramkę, gdy impuls zakłócający wróci do niego, nawet w najgorszym przypadku. Przy dwuipółkilometrowym kablu nadajnik 64-bajtowej ramki przy 1 Gb/s ukończyłby ramkę, zanim ta przebyłaby 1/10 drogi do końca, nie mówiąc już o dotarciu do końca i z powrotem.

Komitet 802.3z uznał zasięg 25 metrów za nie do przyjęcia i dodał do standardu dwie funkcje, które pozwoliły zwiększyć zasięg. Pierwsza z nich, zwana carrier extension (przedłużenie nośni­ka), zasadniczo polega na dodaniu przez sprzęt własnego wypełnienia po zwykłej ramce, tak że jej długość zostaje rozszerzona do 512 bajtów. Ponieważ to wypełnienie jest dodawane przez sprzęt nadajnika i usuwane przez sprzęt odbiornika, oprogramowanie nie jest go świadome, co oznacza, że niepotrzebne są jakiekolwiek zmiany w istniejącym oprogramowaniu. Oczywiście użycie 512 bajtów pasma do przesłania 46 bajtów danych użytkownika (taki jest ładunek użyteczny 64-bajtowej ramki) daje wydajność linii rzędu 9%.

Druga metoda, zwana frame bursting (przesyłanie ramek wiązkami), pozwala nadajnikowi w jednej transmisji wysłać połączoną sekwencję wielu ramek. Jeśli cała paczka ma mniej niż 512 bajtów, to jest ponownie dopełniana przez sprzęt. Jeśli na transmisję oczekuje wystarczająco dużo ramek, ta metoda ma bardzo wysoką wydajność i jest preferowana w stosunku do carrier extension. Te nowe funkcje zwiększają zasięg sieci do 200 metrów, co wystarcza w większości biur.

Szczerze mówiąc, trudno wyobrazić sobie organizację, która zada sobie trud kupowania i in­stalowania gigabitowych kart Ethernet, aby otrzymać dużą wydajność, a następnie połączy kompute­ry koncentratorem, aby zasymulować klasyczny Ethernet z wszystkimi jego kolizjami. Wprawdzie koncentratory są trochę tańsze od przełączników, lecz karty sieciowe Gigabit Ethernet nadal pozo­stają dość drogie. Oszczędzanie po ich zakupie przez nabycie tańszego koncentratora, powodującego utratę wydajności, jest głupotą. Mimo to zgodność wstecz to świętość w branży komputerowej, więc zażądano jej od komitetu 802.3z.

Gigabit Ethernet obsługuje kable zarówno miedziane, jak i światłowodowe, zestawione w tabeli 4.3. Nadawanie w okolicach 1 Gb/s światłowodem oznacza, że źródło światła musi być załączane i wyłą­czane w czasie krótszym niż 1 ns. Diody LED po prostu nie potrafią działać tak szybko, więc nie­zbędne są lasery. Dopuszcza się dwie długości fali: 0,85 mikrona (Short) i 1,3 mikrona (Long). Lasery na 0,85 urn są tańsze, lecz nie współpracują ze światłowodami jednomodowymi.

Dopuszczalne są trzy średnice światłowodów: 10, 50 i 62,5 mikrona. Pierwszy światłowód jest jednomodowy, a dwa pozostałe wielomodowe. Nie wszystkie kombinacje są jednak dozwolone, a mak­symalna odległość zależy od użytej kombinacji. Liczby z tabeli 4.3 dotyczą najlepszych przypadków. 5000 metrów można osiągnąć tylko z użyciem lasera 1,3 (im w jednomodowym światłowodzie 10 µrn. lecz jest to najlepsze rozwiązanie dla sieci szkieletowych pomiędzy budynkami i przypuszczalnie będzie dość popularne, mimo że jest opcją najdroższą.

Wersja 1000Base-CX wykorzystuje ekranowaną skrętkę miedzianą. Jej problem polega na tym, że konkurują z nią światłowód o lepszych osiągach i skrętka o niższej cenie. Prawdopodobnie będzie stosowana rzadko, jeśli w ogóle.

Ostatnią opcją są cztery równoległe pary UTP kategorii 5. Ponieważ mnóstwo takiego okablowa­nia zostało już położonego, prawdopodobnie to będzie wersja sieci Gigabit Ethernet na każdą kieszeń.

Gigabit Ethernet stosuje w światłowodach inne reguły kodowania. Kod Manchester wymagałby sygnału 2-gigabodowego, co uznano za zbyt trudne do uzyskania i marnujące przepustowość. Za­miast tego wybrano nowy schemat o nazwie 8B/10B, oparty na kanałach światłowodowych. Każdy 8-bitowy bajt jest kodowany w światłowodzie na 10 bitach (stąd nazwa). Ponieważ dla każdego bajta wejściowego możliwych jest 1024 słów kodowych, pozwoliło to na pewną dowolność w dobie­raniu słów kodowych. Przy wyborze słów kierowano się dwoma zasadami:

1. Żadne słowo kodowe nie może mieć więcej niż cztery identyczne bity pod rząd.

2. Żadne słowo kodowe nie może mieć więcej niż sześć zer lub sześć jedynek.

Miało to na celu zagwarantowanie, że w strumieniu będzie wystarczająco wiele przejść dla zachowa­nia synchronizacji odbiornika z nadajnikiem, oraz zachowanie możliwie jednakowej liczby zer i je­dynek w kanale. Oprócz tego do wielu bajtów wejściowych przypisano dwa możliwe słowa kodowe. Gdy koder ma możliwość wyboru słowa kodowego, zawsze wybiera takie, które zmniejsza różnicę pomiędzy liczbą wysłanych do tej pory zer i jedynek. Nacisk na równoważenie zer i jedynek jest niezbędny, aby utrzymać jak najniższą składową stałą sygnału, co pozwala na przechodzenie przez transformatory bez zniekształceń. Wprawdzie informatycy nie lubią, gdy właściwości fizyczne trans­formatorów wymuszają formę kodowania, lecz tak już w życiu bywa.

Gigabit Ethernet w l000Base-T używa innego schematu kodowania, ponieważ wysyłanie przez kabel miedziany danych z zegarem 1 ns jest zbyt trudne. To rozwiązanie wykorzystuje cztery skrętki kategorii 5. do równoległego nadawania czterech symboli. Każdy symbol jest kodowany z użyciem jednego z pięciu poziomów napięcia. Taki schemat kodowania pozwala na zakodowaniu w jednym symbolu 00, 01, 10, 11 lub specjalnej wartości na potrzeby kontrolne. Wobec tego w jednym cyklu zegara na jedną parę przewodów przypadają 2 bity danych, a na cały kabel z czterema skrętkami 8 bitów. Zegar działa z szybkością 125 MHz, co pozwala na transmisję 1 Gb/s. Pięć poziomów napięcia zamiast czterech dobrano, aby pozostały wolne kombinacje na ramkowanie i kontrolę.

1 Gb/s to spora szybkość. Na przykład, jeśli odbiornik będzie zajęty innymi zadaniami przez choćby 1 ms i nie opróżni bufora na którejś linii, to podczas tej przerwy w buforze może zebrać się do 1953 ramek. Poza tym, jeśli komputer z interfejsem Gigabit Ethernet wysyła dane gdzieś do komputera w klasycznym Ethernecie, przepełniania buforów są całkiem prawdopodobne. W konse­kwencji tych dwóch spostrzeżeń Gigabit Ethernet obsługuje sterowanie przepływem (podobnie jak Fast Ethernet, aczkolwiek ich mechanizmy się różnią).

Sterowanie przepływem polega na wysyłaniu przez jedną stronę do drugiej specjalnej ramki sterującej, która żąda wstrzymania transmisji na jakiś czas. Ramki sterujące to standardowe ramki Ethernet zawierające w polu Typ wartość 0x8808. Dwa pierwsze bajty pola danych zawierają polecenie; kolejne mogą zawierać parametry. Do sterowania przepływem używane są ramki PAUSE, w których parametr informuje, jak długa ma być przerwa, mierzona w jednostkach czasu transmisji najkrótszej ramki. Dla sieci Gigabit Ethernet jednostka czasu to 512 ns i pozwala na przerwy w nadawaniu aż do 33,6 ms.

Ledwo Gigabit Ethernet stał się standardem, komitet 802 zaczął się nudzić i chciał zabrać się znowu do pracy. IEEE nakazał zacząć prace nad 10-gigabitowym Ethernetem. Po długich poszuki­waniach litery, która mogłaby nastąpić po „z", zrezygnowano z tego podejścia i nastąpiło przejście do dwuliterowych sufiksów. Komisja zabrała się do dzieła i standard został przyjęty przez IEEE w roku 2002 jako 802.3ae. Czy 100-gigabitowy Ethernet jest jeszcze daleko?

4.3.9. IEEE 802.2: sterowanie łączem fizycznym

Pora chyba zestawić to, czego nauczyliśmy się dotąd w tym rozdziale z rzeczami, które będziemy studiować w następnym. W rozdziale 3. zobaczyliśmy, jak dwa komputery mogą komunikować się w sposób niezawodny z użyciem zawodnego łącza za pomocą różnych protokołów łącza danych. Protokoły te zapewniały kontrolę błędów (za pomocą potwierdzeń) i sterowanie przepływem (z uży­ciem okna przesuwnego).

W tym rozdziale dla odmiany nie powiedzieliśmy ani słowa na temat niezawodnej komunikacji. Ethernet i inne protokoły 802 oferują jedynie usługę datagramów z użyciem dostępnych możliwo­ści (best-effort). Czasami taka usługa wystarcza. Na przykład przy przesłaniu pakietów IP nie wyma­ga się, a nawet nie oczekuje gwarancji. Pakiet IP można po prostu wstawić do pola ładunku uży­tecznego 802 i posłać w drogę. Jeśli pakiet zostanie utracony, mówi się trudno.

Jednakże istnieją też systemy, w których protokół łącza danych z kontrolą błędów i stero­waniem przepływem jest pożądany. IEEE zdefiniował jeden taki protokół, który może opierać się na Ethernecie i innych protokołach 802. Oprócz tego protokół ten, zwany LLC (Logical Link Control — sterowanie łączem logicznym), ukrywa różnice pomiędzy różnorodnymi typami sieci 802 przez udostępnienie jednego formatu i interfejsu dla warstwy sieciowej. Ten format, protokół i interfejs dość dokładnie opierają się na protokole HDLC, który poznaliśmy w rozdziale 3. LLC stanowi górną połowę warstwy łącza danych, z podwarstwa MAC poniżej, jak na rysunku 4.21.

Typowe zastosowanie LLC wygląda następująco: warstwa sieciowa w komputerze nadają­cym przekazuje pakiet do LLC, używając funkcji podstawowych dostępu LLC. Następnie pod­warstwa LLC dodaje nagłówek LLC, zawierający numery sekwencyjny i potwierdzający. Uzy­skana struktura zostaje wstawiona do pola ładunku ramki 802 i wysłana. W odbiorniku zachodzi odwrotny proces.

RYSUNEK 4.21.

1. Miejsce LLC.

1. Formaty protokołów

LLC udostępnia trzy opcje usług: niegwarantowaną usługę datagramów, usługę datagramów z potwierdzeniami i niezawodną usługę połączeniową. Nagłówek LLC zawiera trzy pola: docelo­wy punkt dostępu, źródłowy punkt dostępu i pole sterujące. Punkty dostępu informują, z którego procesu pochodzi ramka i gdzie ma zostać doręczona, zastępując pole typu z DIX. Pole sterujące zawiera numery sekwencyjny i potwierdzenia, bardzo podobne jak w HDLC (patrz rysunek 3.17) lecz nie identyczne. Pola te są używane przede wszystkim wtedy, gdy na poziomie łącza danych niezbędne jest niezawodne połączenie; w takim przypadku używane są protokoły podobne do tych które omówiliśmy w rozdziale 3. W Internecie próba doręczenia pakietów IP z użyciem dostęp­nych możliwości wystarcza, więc nie są potrzebne potwierdzenia na poziomie LLC.

4.3.10. Ethernet z perspektywy czasu

Ethernet istnieje od ponad 20 lat i nie ma poważnych rywali w zasięgu wzroku, więc najprawdopo­dobniej będzie używany jeszcze przez długie lata. Bardzo niewiele architektur CPU, systemów operacyjnych lub języków oprogramowania rządziło niepodzielnie przez prawie trzydzieści lat. Najwyraźniej Ethernet pod jakimś względem został dobrze pomyślany. Pod jakim?

Chyba główną przyczyną tej długowieczności jest prostota i elastyczność Ethernetu. W praktyce przekłada się to na niezawodność, niskie koszty i łatwość w utrzymaniu. Gdy tylko rozgałęźniki-wampiry zostały zastąpione złączami BNC, awarie stały się wyjątkowo rzadkie. Zwykle wahamy się przed wymianą czegoś, co działa niezawodnie, zwłaszcza że mnóstwo rzeczy w branży kompute­rowej działa wyjątkowo marnie, więc wiele „udoskonaleń" jest znacznie gorszych od zastąpionych przez nie technologii.

Prosty to też znaczy tani. Cienki Ethernet i skrętka są stosunkowo niedrogie. Karty sieciowe też kosztują niewiele. Dopiero wprowadzenie koncentratorów i przełączników wymaga znaczących inwestycji, lecz gdy te pojawiły się na rynku, Ethernet miał już solidną pozycję.

Ethernet jest łatwy w utrzymaniu. Nie trzeba instalować żadnego oprogramowania (nie licząc sterowników) i nie zarządza się żadnymi tablicami konfiguracji (w których można byłoby namieszać). Poza tym dodawanie nowych hostów polega na prostym podłączeniu do sieci.

Kolejnym plusem Ethernetu jest łatwość łączenia z TCP/IP, który zdominował sieci kompute­rowe. IP jest protokołem bezpołączeniowym, więc doskonale pasuje do Ethernetu, który również jest bezpołączeniowy. IP znacznie gorzej współpracuje z ATM, które są sieciami połączeniowymi. To niedopasowanie znacznie pogarsza szansę ATM.

Poza tym wszystkim Ethernet był w stanie ewoluować w decydujący sposób. Szybkość wzrosła o kilka rzędów wielkości i zostały wprowadzone koncentratory i przełączniki, lecz te zmiany nie wymagały zmian w oprogramowaniu. Gdy w firmie pojawi się przedstawiciel handlowy i oświadczy: „Mam dla Państwa nową, fantastyczną sieć. Wystarczy że wyrzucicie cały stary sprzęt i napiszecie całe oprogramowanie od nowa", to raczej niewiele zarobi. W chwili wprowadzenia FDDI, Fibrę Channel i ATM były szybsze od Ethernetu, lecz jednocześnie były z nim niezgodne, znacznie bar­dziej złożone i trudniejsze w zarządzaniu. W końcu Ethernet dogonił je w szybkości, więc nie po­zostały im żadne zalety i po cichu wymarły, z wyjątkiem szkieletowych sieci systemu telefonii.

4.4. Bezprzewodowe sieci lokalne

Wprawdzie Ethernet jest powszechnie stosowany, lecz szykuje mu się konkurencja. Bezprzewodowe sieci LAN stają się coraz popularniejsze i wyposaża się w nie coraz więcej budynków biurowych, portów lotniczych i innych miejsc publicznych. Bezprzewodowe sieci LAN mogą działać w jednej ^z dwóch konfiguracji, które widzieliśmy na rysunku 1.32: ze stacją bazową i bez niej. Standard LAN 802.11 bierze to pod uwagę i uwzględnia oba rozwiązania, jak zobaczymy za chwilę.

W punkcie 1.5.4 przedstawiliśmy wprowadzenie 802.11. Teraz pora przyjrzeć się dokładniej technologii. W poniższych punktach opiszemy stos protokołów, techniki transmisji w radiowej warstwie fizycznej, protokół podwarstwy MAC, strukturę ramki i usługi. Dodatkowe informacje o 802.11 przedstawili Crow i inni (1997), Geier (2002), Heegard i inni (2001), Kapp (2002), 0'Hara i Petrick (1999) oraz Severance (1999). Aby zdobyć informacje z pierwszej ręki, możemy skorzystać z samego opublikowanego standardu 802.11.

4.4.1. Stos protokołów 802.11.

Protokoły używane we wszystkich odmianach 802, łącznie z Ethernetem, mają pewne podobieństwa w strukturze. Rysunek 4.22 przedstawia częściowy widok stosu protokołów 802.1 1. Warstwa fi­zyczna dość blisko odpowiada warstwie fizycznej OSI, lecz warstwa łącza danych we wszystkich protokołach jest dzielona na dwie lub więcej podwarstw. W 802.11 podwarstwa MAC (Medium Access Control — sterowanie dostępem do nośnika) decyduje, jak kanał jest przydzielany, to zna­czy, kto będzie nadawał następny. Nad nią znajduje się podwarstwa LLC (Logical Link Control — sterowanie łączem logicznym), której zadaniem jest ukrywanie różnic pomiędzy różnymi wa­riantami 802; dzięki niej wersje te sanie do rozróżnienia dla warstwy sieciowej. Z LLC zapoznali­śmy się wcześniej przy okazji Ethernetu i nie będziemy tu powtarzać tego materiału.

RYSUNEK 4.22. Fragment stosu protokołów 802.11

Standard 802.11 z roku 1997 definiuje trzy techniki transmisji dopuszczalne w warstwie fi­zycznej. Metoda na podczerwień używa bardzo podobnej technologii jak stosowana w pilotach do telewizorów. Dwie pozostałe wykorzystują radio o małym zasięgu, używając technik nazwanych FHSS i DSSS. Obie wykorzystują zakres widma, w którym nie są wymagane licencje (pasmo ISM 2,4 GHz). Z tego zakresu pasma korzystają też urządzenia do zdalnego otwierania drzwi garażu, więc nasz notebook może rywalizować o dostęp z nimi. Również bezprzewodowe telefony i kuchen­ki mikrofalowe używają tego pasma. Wszystkie te techniki pracują z 1 lub 2 Mb/s i z mocą na tyle niską że nie kolidują ze sobą za bardzo. W roku 1999 wprowadzono dwie nowe techniki, aby osiągnąć wyższą przepustowość sieci, nazwane OFDM i HR-DSSS. Działają one odpowiednio z szybkością

54 Mb/s i 11 Mb/s. W roku 2001 wprowadzono drugą modulację OFDM, lecz w innym paśmie ni pierwsza. Przedstawimy je pokrótce poniżej. Technicznie należą one do warstwy fizycznej i powinniśmy je byli opisać w rozdziale 2., lecz ponieważ są ściśle związane z sieciami LAN ogólnie i z podwarstwą MAC 802.11 w szczególności, omówimy je tutaj.

4.4.2. Warstwa fizyczna 802.11

Każda z pięciu dozwolonych technik transmisji pozwala przesłać ramkę MAC z jednej stacji do drugiej. Różnią się jednak pod względem użytej technologii i osiągalnej szybkości.

W łączach na podczerwień używa się transmisji rozproszonej (czyli nie w linii optycznej przy 0,85 lub 0,95 µm. Dopuszczalne są dwie szybkości: 1 Mb/s i 2 Mb/s. Przy 1 Mb/s używam jest schemat kodowania, w którym grupa 4 bitów zostaje zakodowana w postaci 16-bitowego słowa, zawierającego piętnaście zer i jedną jedynkę z użyciem tzw. kodu Graya. Ten kod cechuje fakt że mały błąd w synchronizacji prowadzi do jednobitowego błędu na wyjściu. Przy 2 Mb/s z dwóch bitów tworzone jest czterobitowe słowo kodowe, również z jedną jedynką, czyli 0001, 0010, 0100 ( lub 1000). Sygnały w podczerwieni nie przechodzą przez ściany, więc komórki w sąsiednich pomieszczeniach są od siebie dobrze odizolowane. Jednakże z uwagi na niską szybkość i fakt, że promienie słoneczne przytłaczają sygnały podczerwone, nie jest to popularne rozwiązanie.

FHSS (Frequency Hopping Spread Spectrum — modulacja w widmie rozproszonym ze sko­kową zmianą kanału) używa 79 kanałów o szerokości 1 MHz każdy, zaczynając od dolnej granicy pasma ISM 2,4 GHz. Do ustalania częstotliwości, do których będzie przeskakiwać transmisja, uży­wany jest generator liczb pseudolosowych. Dopóki wszystkie stacje używają tej samej wartości początkowej w generatorze liczb pseudolosowych i zachowują synchronizację w czasie, będą prze­skakiwać na te same częstotliwości. Czas przebywania na jednej częstotliwości (ang. dwell time) jest parametrem regulowanym, lecz musi być krótszy niż 400 ms. Pseudolosowy wybór pasm w FHSS zapewnia znacznie uczciwszy przydział widma w nieobjętym przepisami paśmie ISM. Oprócz te­go daje krzynę bezpieczeństwa, ponieważ napastnik nieznający sekwencji przeskoków lub czasu przebywania nie może podsłuchiwać transmisji. Na dłuższych dystansach wielodrożny zanik sy­gnału może stanowić poważny problem, a FHSS zapewnia sporą odporność na to zjawisko. FHSS ma też stosunkowo małą wrażliwość na zakłócenia radiowe, dzięki czemu jest technologią popu­larną w łączach między budynkami. Jej główną wadą jest mała przepustowość.

Trzecia metoda modulacji, DSSS (Direct Sequence Spread Spectrum — rozpraszanie wid­ma z wykorzystaniem sekwencji bezpośredniej), również jest ograniczona do 1 lub 2 Mb/s. Używany w niej schemat jest pod pewnymi względami podobny do systemu CDMA, lecz pod innymi jest odmienny. Każdy bit jest przesyłany jako 11 chipów z użyciem tzw. ciągu Barkera. Wykorzystuje on modulację fazy przy 1 megabodzie, przesyłając jeden bit na bod przy 1 Mb/s i 2 bity na bod w trybie 2 Mb/s. Przez lata FCC wymagała, aby wszelki sprzęt do komu­nikacji bezprzewodowej działający w paśmie ISM w USA używał widma rozproszonego, lecz w maju 2002 roku ta zasada została zarzucona wraz z pojawieniem się nowych technologii.

Pierwsza z szybkich bezprzewodowych sieci lokalnych, 802.11a, używa OFDM (Orthogo-nal Freąuency Division Multiplexing — multipleksowanie z ortogonalnym podziałem częstotli­wości), aby osiągnąć 54 Mb/s szerszym paśmie ISM 5 GHz. Jak nazwa wskazuje, używane są różne częstotliwości, łącznie 52 (48 dla danych i 4 dla synchronizacji), co przypomina trochę ADSL. Ponieważ transmisja odbywa się jednocześnie na różnych częstotliwościach, technika ta jest uznawana za formę widma rozproszonego, lecz odmienną od DCM A i FHSS. Podział sygnału na wiele wąskich pasm ma kilka znaczących zalet w porównaniu z użyciem pojedynczego szerokiego pasma, w tym większą odporność na zakłócenia wąskopasmowe i możliwość korzystania z pasm nieciągłych. Stoso­wany jest tu skomplikowany system kodowania oparty na modulacji fazy dla szybkości do 18 Mb/s i QAM powyżej. Przy 54 Mb/s 216 bitów danych jest kodowanych do 288-bitowych symboli. Jed­ną z motywacji dla OFDM jest zgodność z europejskim systemem HiperLAN/2 (Doufexi i in., 2002). Technika ta zapewnia dobre wykorzystanie pasma (mierzone w bitach na Hz) i dobrą odporność na wielodrożne zaniki sygnału.

Następna jest HR-DSSS (High Rate Direct Sequence Spread Spectrum) — kolejna technika działająca w widmie rozproszonym i używająca 11 milionów chipów na sekundę, aby osiągnąć 11 Mb/s w paśmie 2,4 GHz. Nosi nazwę 802.1lb, lecz nie jest następcą 802.1la. W rzeczywistości ten standard został zaaprobowany jako pierwszy i jako pierwszy trafił na rynek. W 802.1lb dostępne są szybkości transmisji 1, 2, 5,5 i 11 Mb/s. Dwie najwolniejsze działają z szybkością 1 megaboda odpowiednio z 1 i 2 bitami na bod, z wykorzystaniem modulacji fazy (dla zgodności z DSSS). Dwie szybsze pracują z 1,375 megaboda z 4 i 8 bitami na bod, korzystając z kodów Walsha-Hadamarda. Szybkość transmisji danych musi być podczas działania regulowana dynamicznie, aby osiągnąć optymalną szybkość w aktualnych warunkach obciążenia i zakłóceń. W praktyce szyb­kość robocza 802.1lb niemal zawsze wynosi 11 Mb/s. Wprawdzie 802.1lb jest wolniejszy od 802.1la, lecz jego zasięg jest mniej więcej siedmiokrotnie większy, co w wielu sytuacjach jest ważniejsze.

Udoskonalona wersja 802.1lb, 802.11g, została przyjęta przez IEEE w listopadzie 2001 po wielu debatach, czyjej opatentowanej technologii powinna używać. Wykorzystuje ona metodę modulacji OFDM z 802.11, lecz działa w wąskim paśmie ISM 2,4 GHz równolegle z 802.1lb. W teorii może pracować z szybkością do 54 Mb/s. Nie jest jeszcze jasne, czy taka szybkość będzie zrealizowana w praktyce. Oznacza to tylko, że komitet 802.11 wyprodukował trzy różne szybkie lokalne sieci bezprzewodowe: 802.1la, 802.1lb i 802.1lg (nie mówiąc o trzech wolnych bezprzewodowych sieciach LAN). Możemy zadać w pełni uzasadnione pytanie, czy komitet normalizacyjny powinien tak postępować. Może wyznaje zasadę omne triumperfectum...

4.4.3. Protokół podwarstwy MAC w 802.11

Wróćmy z krainy elektroniki do krainy informatyki. Protokół podwarstwy MAC w 802.11 znacznie różni się od swojego odpowiednika z Ethernetu z uwagi na nieuniknioną złożoność środowiska bez­przewodowego w porównaniu z systemami kablowymi. W Ethernecie stacja po prostu czeka na ciszę w eterze i zaczyna nadawać. Jeśli nie odbierze paczki zakłóceń podczas pierwszych 64 bajtów, ram­ka niemal na pewno została doręczona poprawnie. W sieciach bezprzewodowych się to nie sprawdza.

Zacznijmy od problemu ukrytej stacji, wspomnianego wcześniej i ponownie przedstawionego na rysunku 4.23 (a). Ponieważ nie wszystkie stacje są w zasięgu radiowym wszystkich pozostałych, transmisje odbywające się w jednym miejscu komórki mogą nie zostać odebrane w innym miejscu tej samej komórki. W naszym przykładzie stacja C nadaje do stacji B. Gdy A sprawdzi stan kanału, nie wykryje transmisji i dojdzie do błędnego wniosku, że może zacząć nadawać do stacji B.

Oprócz tego występuje problem odwrotny — problem odkrytej stacji, zilustrowany na rysunku 4.23 (b). Tutaj B chce nadawać do C, więc sprawdza stan kanału. Gdy słyszy transmisję, błędnie wnioskuje, że nie może nadawać do C, mimo że A może właśnie nadawać do stacji D (niepokazanej). Oprócz tego większość radiowych nadajników-odbiorników działa w trybie półdupleksowym, co oznacza, że nie mogą jednocześnie nadawać i nasłuchiwać paczek zakłóceń na tej samej częstotliwości. Z uwagi na te problemy 802.11 nie używa CSMA/CD jak Ethernet.

RYSUNEK 4.23. (a) Problem ukrytej stacji, (b) Problem odkrytej stacji

Aby poradzić sobie z tym, 802.11 obsługuje dwa tryby działania. Pierwszy, zwany DCF (Distri buted Coordination Function — funkcja koordynacji rozproszonej), nie stosuje żadnych mecha­nizmów centralnej kontroli (pod tym względem przypomina Ethernet). Drugi, zwany PCF (Poim Coordination Function — funkcja koordynacji punktowej) używa stacji bazowej do koordynacji wszelkich działań w jej komórce. Wszystkie implementacje muszą obsługiwać DCF, lecz tryb PCF jest opcjonalny. Omówimy teraz po kolei oba.

Gdy stosowany jest DCF, 802.11 używa protokołu o nazwie CSMA/CA (CSMA with Colli-sion Avoidance — CSMA z unikaniem kolizji). W tym protokole używane jest zarówno wykrywa­nie kanału fizycznego, jak i wirtualnego. CSMA/CA pozwala na dwa tryby działania. W pierwszym stacja, która chce nadawać, sprawdza stan nośnika. Gdy kanał jest wolny, po prostu zaczyna nadawać. Nie sprawdza stanu kanału podczas nadawania, lecz wysyła całą swoją ramkę, która może zostać dotrzeć do odbiornika zniszczona z powodu zakłóceń w jego okolicy. Jeśli kanał jest zajęty, nadajnik czeka na jego zwolnienie i zaczyna nadawać. W razie kolizji stacje odczekują losowy czas, używając binarnego algorytmu odczekiwania wykładniczego i ponawiają próbę.

Drugi tryb działania CSMA/CA opiera się na MACA W i stosuje wykrywanie kanału wirtualnego, jak na rysunku 4.24. W tym przykładzie A chce nadawać do B, C jest stacją w zasięgu A (i być może w zasięgu B, lecz to nie jest ważne). D jest stacją w zasięgu B, lecz poza zasięgiem A.

RYSUNEK 4 .24. Wykrywanie kanału wirtualnego z użyciem CSMA/CA

Protokół zaczyna działanie, gdy A chce wysłać dane do B. Zaczyna od wysłania ramki RTS do # z żądaniem zezwolenia na wysłanie do niej ramki danych. Gdy B otrzymuje to żądanie, może zde­cydować się przyznać pozwolenie; w takim przypadku odsyła z powrotem ramkę CTS. Po odebraniu

CTS A wysyła swoją ramkę i uruchamia czasomierz ACK (potwierdzenia). Po poprawnym odebra­niu ramki danych B odpowiada ramką ACK, kończąc wymianę. Jeśli w A czas oczekiwania na ACK upłynie przed powrotem tej ramki, cała procedura protokołu jest przeprowadzana ponownie.

Rozważmy teraz tę wymianę z perspektywy C i D. Stacja C jest w zasięgu A, więc może ode­brać ramkę RTS. Jeśli ją odbierze, to orientuje się, że inna stacja zamierza za chwilę rozpocząć transmisję, więc dla dobra ogólnego powstrzymuje się od transmisji aż do ukończenia wymiany. Na podstawie informacji zawartych w żądaniu RTS może określić, jak długo potrwa wymiana, łącznie z finalnym ACK, więc zaznacza u siebie zajętość kanału wirtualnego oznaczoną przez wektor NAV (Network Allocation Vector — wektor przydziału sieci) z rysunku 4.24. D nie odbiera RTS, lecz słyszy CTS, zatem również oznacza u siebie sygnał NAV. Zwróćmy uwagę, że sygnały NAW nie są przesyłane; stanowią jedynie wewnętrzne przypomnienie, że stacja przez określony czas powinna powstrzymać się od nadawania.

W przeciwieństwie do sieci kablowych w sieciach bezprzewodowych występuje sporo zakłóceń i są zawodne, w sporej części z winy kuchenek mikrofalowych, które również używają pasm ISM nieobjętych licencjami. Z tego powodu szansa pomyślnego dotarcia ramki do celu maleje wraz z długością ramki. Jeśli prawdopodobieństwo wystąpienia błędu w określonym dowolnym bicie wynosi p, to prawdopodobieństwo odebrania całej n-bitowej ramki bez żadnych błędów wynosi (1-p)ⁿ. Na przykład dla p = 10^-4 prawdopodobieństwo poprawnego odebrania całej ramki Ethernet (12 144 bity) jest mniejsze niż 30%. Jeśli p = 10^-5, jedna ramka na 9 dotrze uszkodzona. Nawet przy p = 10^-6 ponad 1% ramek ulegnie uszkodzeniu, co przekłada się na prawie tuzin na sekundę i więcej, jeśli używane są ramki krótsze od maksymalnej długości. Krótko mówiąc, jeśli ramka jest zbyt długa, ma bardzo niewielką szansę dotarcia bez uszkodzeń i prawdopodobnie będzie musiała zostać przesłana jeszcze raz.

Aby rozwiązać problem zakłóceń w kanale, 802.11 pozwala na podział ramek na mniejsze fragmenty, z których każdy ma własną sumę kontrolną. Fragmenty są ponumerowane indywidualnie i potwierdzane z użyciem protokołu stop-and-wait (tzn. nadajnik nie może wysłać fragmentu k + 1, dopóki nie otrzyma potwierdzenia fragmentu k). Po przejęciu kanału za pomocą RTS i CTS można wysłać wiele fragmentów pod rząd, jak na rysunku 4.25. Sekwencja fragmentów nazywana jest czasem wiązką fragmentów (fragment burst).

RYSUNEK 4.25. Wiązka fragmentów

Fragmentacja zwiększa przepustowość przez ograniczenie retransmisji do uszkodzonych frag­mentów zamiast całych ramek. Rozmiar fragmentu nie jest ustalony przez standard, lecz stanowi parametr każdej komórki i może być regulowany przez stację bazową. Mechanizm NAV powstrzy­muje inne stacje od nadawania jedynie aż do następnego potwierdzenia, lecz inny mechanizm (opisany poniżej) pozwala na przesłanie całej paczki fragmentów bez przeszkód.

Cały powyższy opis stosuje się do trybu DCF 802.11. W tym trybie nie ma centralnego stero­wania, a stacje rywalizują o czas antenowy podobnie jak w Ethernecie. Drugim dopuszczalnym try­bem jest PCF, w którym stacja bazowa odpytuje inne stacje, czy mają jakieś ramki do wysłania. Po­nieważ w trybie PCF kolejność transmisji jest w pełni kontrolowana przez stację bazową, kolizje w ogóle nie występują. Standard definiuje mechanizm odpytywania, lecz nie częstotliwość i porządek odpy­tywania, a nawet nie ustala, czy wszystkie stacje powinny otrzymywać usługi na tym samym poziomie.

Podstawowy mechanizm polega na okresowym (10 do 100 razy na sekundę) rozgłaszaniu przez stację bazową ramki nawigacyjnej. Ramka ta zawiera parametry systemu, takie jak sekwencje przeskakiwania częstotliwości i czas przebywania (dla FHSS), synchronizację zegara itp. Zaprasza też nowe stacje do zapisywania się na usługę odpytywania. Po zapisaniu się stacji na usługę od­pytywania z określoną częstotliwością, efektywnie ma gwarantowaną określoną część pasma, co umożliwia gwarantowanie jakości usług.

W urządzeniach mobilnych żywotność baterii zawsze stanowi problem, więc 802.11 zwraca uwagę na kwestię zarządzania zasilaniem. Stacja bazowa może wprowadzić stację mobilną w tryb uśpienia, dopóki nie zostanie wprost obudzona przez stację bazową lub użytkownika. Konieczność „usypiania" stacji oznacza jednak, że na stacji bazowej spoczywa obowiązek buforowania wszelkich kierowanych do niej ramek, podczas gdy stacja mobilna hibernuje. Ramki te będą odebrane później.

PDF i DCF mogą współistnieć w jednej komórce. Na pierwszy rzut oka jednoczesne sterowanie centralne i rozproszone wydaje się niemożliwe, lecz 802.11 udostępnia mechanizm osiągnięcia tego celu. Działa on poprzez dokładne zdefiniowanie odstępów czasu między ramkami. Po wysła­niu ramki wymagany jest określony czas martwy, zanim którakolwiek stacja będzie mogła wysłać ramkę. Zdefiniowane są cztery interwały, każdy do innego celu. Przedstawia je rysunek 4.26.

RYSUNEK 4.26. Odstępy między ramkami w 802.11

Najkrótszym interwałem jest SIFS (Short InterFrame Spacing — krótki odstęp między ram­kami). Daje on szansę pierwszeństwa stacjom w pojedynczym dialogu. Obejmuje to zezwolenie nadajnikowi na wysłanie CTS w odpowiedzi na RTS, odbiornikowi na wysłanie ACK po następny fragment lub pełną ramkę danych, i pozwolenie nadawcy paczki fragmentów na wysłanie następ­nego fragmentu bez konieczności ponownego wysyłania RTS.

Zawsze po interwale SIFS ma prawo odpowiedzieć dokładnie jedna stacja. Jeśli stacja ta nie wykorzysta danej okazji i upłynie czas PIFS (PCF InterFrame Spacing — odstęp między ramkami dla PCF), stacja bazowa może wysłać ramkę nawigacyjną lub odpytującą. Ten mechanizm pozwala stacji wysłać ramkę danych lub ciąg fragmentów, aby dokończyć ramkę bez wtrącania się innych stacji, lecz jednocześnie daje stacji bazowej szansę przejęcia kanału, gdy poprzedni nadajnik skoń­czy transmisję, bez konieczności rywalizacji z nadgorliwymi użytkownikami.

Jeśli stacja bazowa nie ma nic do powiedzenia i upłynie czas DIFS (DCF InterFrame Spacing -— odstęp między ramkami dla DCF), każda stacja będzie mogła próbować przejąć kanał, aby wysłać nową ramkę. Stosują się tu tradycyjne zasady rywalizacji, a w razie kolizji może okazać się po­trzebny binarny algorytm odczekiwania wykładniczego.

Ostatni interwał, EIFS (Extended InterFrame Spacing — przedłużony odstęp między ram­kami), jest używany tylko przez stację, która odebrała uszkodzoną lub niewłaściwą ramkę, do zgłoszenia problemu z ramką. Temu zdarzeniu nadano najniższy priorytet dlatego, że odbiornik może nie mieć pojęcia o odbywającej się transmisji, powinien odczekać znaczący czas, aby uniknąć za­kłócania trwającego dialogu pomiędzy dwiema stacjami.

4.4.4. Struktura ramki 802.11

Standard 802.11 definiuje trzy różne klasy ramek: danych, sterujące i zarządzania. Każda z nich ma nagłówek z różnorodnymi polami używanymi w podwarstwie MAC. Oprócz tego pewne ramki są używane przez warstwę fizyczną, lecz te zajmują się głównie używanymi technikami modulacji, więc nie będziemy ich tu omawiać.

Format ramki danych przedstawia rysunek 4.27. Pierwsze jest pole Sterowanie ramką, które zawiera 11 podpól. Pierwsze podpole zawiera wersję protokołu i pozwala na jednoczesne używanie dwóch protokołów w tej samej ramce. Następne jest podpole Typ (ramka danych, sterująca lub zarzą­dzająca) i Podtyp (RTS lub CTS). Pola Do DS i Z DS wskazują czy ramka kieruje się do czy z między­komórkowego systemu dystrybucji (np. Ethernetu). Bit MF oznacza, że będą następować kolejne frag­menty. Bit Ponowienie oznacza retransmisję ramki wysłanej uprzednio. Bit Zarządzanie zasilaniem jest używany przez stację bazową do przełączenia odbiornika w tryb uśpienia lub wyprowadzenia z trybu uśpienia. Bit Więcej wskazuje, że nadajnik ma kolejne ramki dla odbiornika. Bit W oznacza, że treść ramki została zaszyfrowana za pomocą algorytmu WEP (Wired Equivalent Privacy). Na koniec włączenie bitu 0 informuje odbiornik, że sekwencja ramek musi zostać przetworzona ściśle po kolei.

RYSUNEK 4.27. Ramka danych 802.11

Drugie pole ramki danych, Czas trwania, informuje, jak długo ramka i jej potwierdzenie będą najmować kanał. Pole to jest też obecne w ramkach sterujących i służy do zarządzania prze inne stacje mechanizmem NAV. Nagłówek ramki zawiera cztery adresy, wszystkie w formacie IEEE 802. Adresy źródłowy i docelowy są oczywiście niezbędne, lecz do czego służą dwa pozostałe? Proszę pamiętać, że ramki mogą wchodzić i wychodzić z komórki przez stację bazową. Dwa pozostałe adresy wskazują źródłową i docelową stację bazową dla ruchu między komórkami.

Pole Sekwencja pozwala na numerowanie ramek. Dwanaście z szesnastu dostępnych bitów identyfikuje ramkę, a cztery fragment. Pole Dane zawiera ładunek użyteczny, maksymalnie 2312 bajtów, po którym następuje jak zwykle Suma kontrolna.

Ramki zarządzające mają format podobny jak ramki danych, z wyjątkiem jednego z adresów stacji bazowej, ponieważ ich zasięg jest ograniczony do pojedynczej komórki. Ramki sterujące są jeszcze krótsze i zawierają tylko jeden lub dwa adresy, a nie zawierają pola danych ani sekwencji. Kluczową informację zawiera pole podtypu, zwykle RTS, CTS lub ACK.

4.4.5. Usługi

Standard 802.11 określa, że każda zgodna z nim bezprzewodowa sieć lokalna musi świadczyć dziewięć usług. Usługi te dzielą się na dwie kategorie: pięć usług dystrybucyjnych i cztery usługi stacji. Usługi dystrybucyjne wiążą się z zarządzaniem przynależnością do komórki i interakcjami ze stacjami na zewnątrz komórki. W przeciwieństwie do nich usługi stacji wiążą się z działaniami wewnątrz pojedynczej komórki.

Pięć usług dystrybucyjnych świadczą stacje bazowe. Wiążą się one z ruchami stacji wchodzą­cych i wychodzących z komórek, podłączających się i odłączających od stacji bazowych. Są to:

1. Asocjacja. Tej usługi stacje mobilne używają do łączenia się ze stacjami bazowymi. Zwykle jest używana bezpośrednio po wejściu stacji w zasięg stacji bazowej. Po pojawieniu się w za­sięgu stacja mobilna ogłasza swoją tożsamość i możliwości. Do możliwości zaliczają się obsłu­giwane szybkości transmisji, zapotrzebowanie na usługi PCF (tzn. odpytywanie) i wymogi związane z zarządzaniem zasilaniem. Stacja bazowa może przyjąć lub odrzucić stację mobilną. Po akceptacji stacja mobilna musi się uwierzytelnić.

2. Dezasocjacja. Stacja bazowa lub mobilna może w ten sposób zerwać związek. Każda stacja powinna użyć tej usługi przed wyłączeniem się lub opuszczeniem komórki, lecz stacja bazo­wa może jej użyć przed wyłączeniem dla konserwacji.

3. Reasocjacja. Za pomocą tej usługi stacja może zmienić swoją preferowaną stację bazową. Jest to przydatne dla stacji mobilnych przemieszczających się z jednej komórki do drugiej. Jeśli usługa zostanie użyta poprawnie, w konsekwencji przekazania nie zostaną utracone żadne dane (aczkolwiek 802.11, podobnie jak Ethernet, jest jedynie usługą z użyciem dostępnych możliwości).

1. Dystrybucja. Ta usługa decyduje, jak kierować ramki wysłane do stacji bazowej. Jeśli odbiorca jest lokalny względem stacji bazowej, ramki mogą być przesyłane wprost kanałem radiowym. W przeciwnym razie trzeba je przekazać poprzez sieć kablową.

1. Integracja. Gdy trzeba przesłać ramkę przez sieć inną niż 802.11, mającą inny schemat adre­sowania lub format ramki, ta usługa zajmuje się translacją z formatu 802.11 na format wymaga­ny przez sieć docelową.

Pozostałe cztery usługi są wewnątrzkomórkowe (tzn. wiążą się z działaniami w obrębie jednej komórki) i są stosowane po dokonaniu asocjacji. Te usługi to:

1. Uwierzytelnianie. Ponieważ bezprzewodowe wiadomości mogą z łatwością być wysyłane i od­bierane przez stacje nieautoryzowane, stacja musi się uwierzytelnić, zanim otrzyma zezwolenie na wysyłanie danych. Po asocjacji stacji mobilnej przez stację bazową (czyli po zaakceptowaniu w komórce) stacja bazowa wysyła specjalną ramkę wezwania, aby sprawdzić, czy stacja mobilna zna przydzielony jej tajny klucz (hasło). Stacja udowadnia znajomość tajnego klucza przez zaszyfrowanie ramki wezwania i odesłanie jej do stacji bazowej. Jeśli wynik jest poprawny, sta­cja mobilna zostaje w pełni przyjęta do komórki. W oryginalnym standardzie stacja bazowa nie musi udowadniać swojej tożsamości stacji mobilnej, lecz prace nad naprawieniem tego de­fektu już trwają.

2. Delegalizacja. Gdy uwierzytelniona uprzednio stacja chce opuścić sieć, jest delegalizowana. Po delegalizacji nie może już używać sieci.

3. Prywatność. Aby zachować poufność przy transmisji przez bezprzewodową sieć lokalną, in­formacje muszą być szyfrowane. Ta usługa zarządza szyfrowaniem i deszyfracją. Algoryt­mem wskazanym przez standard jest RC4, opracowany przez Ronalda Rivesta z M.I.T.

(4) Doręczanie danych. W końcu w tym wszystkim chodzi o transmisję danych, więc 802.11 oczywiście udostępnia mechanizm ich wysyłania i odbierania. Ponieważ standard 802.11 został zamodelowany na Ethernecie, a transmisja w Ethernecie nie jest w 100% niezawodna, przesył danych w 802.11 również nie jest gwarantowany. Wykrywaniem i korekcją błędów muszą zająć się warstwy wyższe.

Komórka 802.11 ma pewne parametry, które można skontrolować i w niektórych przypadkach wyregulować. Wiążą się one z szyfrowaniem, interwałami oczekiwania, szybkościami transmisji danych, częstotliwościami sygnałów nawigacyjnych i tak dalej.

Bezprzewodowe sieci LAN oparte na 802.11 zaczynają pojawiać się w budynkach biurowych, portach lotniczych, hotelach, restauracjach i miasteczkach akademickich na całym świecie. Przewiduje się szybki wzrost tej technologii. Informacje o masowym wdrożeniu 802.11 w CMU przedstawia Hills (2001).

4.5. Szerokopasmowe łącza bezprzewodowe

Zbyt długo siedzieliśmy w budynku. Wyjdźmy na zewnątrz i sprawdźmy, czy coś ciekawego dzieje się tu w sieciach. Okazuje się, że całkiem sporo, z czego część wiąże się z tzw. ostatnią milą. Po uwol­nieniu w wielu krajach rynku systemów telefonicznych konkurenci zakorzenionej firmy telefonicznej mają często prawo oferować legalne usługi głosowe i szybki dostęp do Internetu. Zapotrzebowanie jest bez wątpienia duże. Problem w tym, że koszty pociągnięcia światłowodu, koncentryka lub choćby skrętki kategorii 5. do milionów domów i firm są zaporowe. Co może zrobić firma rywalizująca o klienta?

Odpowiedzią są szerokopasmowe łącza bezprzewodowe. Postawienie dużej anteny na wzgórzu tuż poza miastem i instalowanie na dachach domów klientów anten skierowanych w jej stronę jest znacznie łatwiejsze i tańsze niż kopanie rowów i przeciąganie kabli. Wobec tego rywalizujące firmy telekomunikacyjne są bardzo zainteresowane udostępnianiem wielomegabitowych usług bezprze­wodowego dostępu do Internetu, przesyłania głosu, filmów na zamówienie itp. Jak widzieliśmy na rysunku 2.26, LMDS został wynaleziony właśnie do tych zastosowań. Jednakże do niedawna każdy operator tworzył własny system. Ten brak standardów oznaczał, że sprzęt i oprogramowanie nie mogły być produkowane masowo, przez co ceny pozostawały wysokie, a popularność niska.

Wiele osób z branży zdało sobie sprawę, że kluczowym brakującym elementem był standard dla szerokopasmowej transmisji bezprzewodowej, więc IEEE poproszono o powołanie komitetu, zło­żonego z pracowników kluczowych firm i uczelni, do opracowania standardu. Następnym numerem dostępnym w nazewnictwie 802 był 802.16, więc standard otrzymał ten numer. Prace zaczęły się w czerwcu 1999 roku, a ostateczny standard został zaaprobowany w kwietniu 2002. Jego oficjalna nazwa brzmi „Air Interface for Fixed Broadband Wireless Access Systems" (Interfejs radiowy dla stacjonarnych szerokopasmowych systemów dostępu bezprzewodowego), jednakże niektórzy wolą nazywać go bezprzewodową siecią miejską (wireless MAN) lub bezprzewodową pętlą lokalną (wireless local Ioop). Wszystkie te nazwy będziemy traktować jako równoważne.

Podobnie jak niektóre inne standardy 802, na 802.16 duży wpływ miał model OSI, łącznie z (pod)warstwami, terminologią, elementarnymi funkcjami usług itd. Niestety, podobnie jak OSI jest dość skomplikowany. W poniższych punktach opiszemy w skrócie część cech 802.16, lecz ten opis jest daleki od kompletnego i pomija wiele szczegółów. Dodatkowe informacje o łączności bez­przewodowej przedstawili Bolcskei i inni (2001) oraz Webb (2001). Standard 802.16 opisuje Eklund i inni (2002).

4.5.1. Porównanie 802.11 z 802.16

W tym miejscu możemy się zastanawiać, po co nowy standard? Dlaczego nie mielibyśmy po prostu użyć 802.11? Przeciwko wykorzystaniu 802.11 przemawia wiele powodów, głównie dlatego, że 802.11 i 802.16 rozwiązują odmienne problemy. Zanim przejdziemy do terminologii 802.16. warto chyba poświęcić kilka słów temu, dlaczego w ogóle potrzebny jest nowy standard.

Środowiska, w których działają 802.11 i 802.16, są pod pewnymi względami podobne, przede wszystkim zapewniają szybką komunikację bezprzewodową, lecz różnią się też pod pewnymi istotnymi względami. Po pierwsze, 802.16 udostępnia usługi dla budynków, a budynki nie są mobilne. Nie przenoszą się często z komórki do komórki. Duża część 802.11 służy mobilności, która nie jest tu istotna. Po drugie, w budynku może znajdować się więcej niż jeden komputer. Ta komplikacja nie występuje, gdy stacją końcową jest pojedynczy notebook.

Ponieważ właściciele budynków są bardziej skłonni wydać więcej pieniędzy na sprzęt komunika­cyjny niż właściciele notebooków, dostępne są lepsze radia. Ta różnica oznacza, że 802.16 może używać łączności pełnodupleksowej, czego unika się w 802.11, aby utrzymać niskie koszty sprzętu.

Ponieważ 802.16 obejmuje zasięgiem część miasta, odległości mogą wynosić kilka kilome­trów, co oznacza, że moc odbierana w stacji bazowej może różnić się znacząco dla różnych stacji. Te różnice wpływają na stosunek sygnał/szum, co z kolei dyktuje użycie kilku schematów modu­lacji. Oprócz tego otwarta komunikacja na terenie miasta oznacza, że zabezpieczenia i prywatność są niezbędne i obowiązkowe.

Co więcej, każda komórka może mieć znacznie więcej użytkowników niż standardowa komórka 802.11, a użytkownicy ci będą korzystać z większego pasma przepustowości niż typo­wy użytkownik 802.11. W końcu rzadko się zdarza, aby firma zaprosiła 50 użytkowników z lapto­pami do jednego pomieszczenia, aby sprawdzić, czy dadzą radę zatkać sieć bezprzewodową 802.11 przez oglądanie 50 filmów jednocześnie. Z tego powodu potrzebne jest szersze pasmo częstotliwości niż mogą zapewnić zakresy ISM, co zmusza 802.16 do korzystania ze znacznie wyższego zakresu czę­stotliwości 10 - 66 GHz jedynego miejsca, gdzie dostępne jest jeszcze niewykorzystane pasmo.

Lecz te fale milimetrowe mają inne właściwości fizyczne niż dłuższe fale z zakresów ISM, co z kolei wymaga zupełnie innej warstwy fizycznej. Fale milimetrowe są silnie pochłaniane przez wo­dę (zwłaszcza deszcz, lecz do pewnego stopnia też przez śnieg, grad i, przy odrobinie pecha, przez gęstą mgłę). Wobec tego obsługa błędów jest znacznie ważniejsza niż wewnątrz budynków. Fale mili­metrowe mogą być skupiane w kierunkowe wiązki (w 802.11 transmisja jest wszechkierunkowa), więc decyzje podjęte w 802.11 w związku z wielodrożnymi zanikami sygnału nie stosują się tutaj.

Kolejnym problemem jest jakość usług. Wprawdzie 802.11 w pewnym stopniu obsługuje ruch w czasie rzeczywistym (z użyciem trybu PCF), lecz ten standard nie został tak naprawdę za­projektowany dla telefonii i intensywnego korzystania z multimediów. W przeciwieństwie do niego od 802.16 oczekuje się pełnego wsparcia dla tych usług, ponieważ jest to standard przeznaczony dla firm i mieszkańców.

Krótko mówiąc, 802.11 został pomyślany jako mobilny Ethernet, a 802.16 jak bezprzewodowa, lecz stacjonarna telewizja kablowa. Te różnice są tak duże, że otrzymane standardy różnią się znacznie, ponieważ są optymalizowane pod innymi kątami.

Warto też w skrócie porównać 802.16 z systemem telefonii komórkowej. W telefonach mobilnych mamy do czynienia z wąskopasmowymi, zorientowanymi na transmisję głosu mobilnymi stacjami o małej mocy, które komunikują się za pomocą mikrofal o średniej długości. Nikt nie ogląda dwu­godzinnych filmów o wysokiej rozdzielczości przez telefony GSM (jak na razie). Nawet UMTS raczej nie ma większych szans na zmianę tej sytuacji. Krótko mówiąc, świat bezprzewodowych sieci miejskich jest o wiele bardziej wymagający od świata telefonii komórkowej, więc potrzebny był zupełnie odmienny system. To, czy 802.16 będzie można w przyszłości użyć w urządzeniach mobil­nych, jest ciekawym pytaniem. Standard nie został dla nich zoptymalizowany, lecz możliwość ist­nieje. Jak na razie koncentruje się na urządzeniach stacjonarnych.

4.5.2. Stos protokołów 802.16

RYSUNEK 4.28. Stos protokołów 802.16

Stos protokołów 802.16 przedstawia rysunek 4.28. Ogólna struktura jest podobna jak w innych sieciach 802, lecz z większą liczbą podwarstw. Najniższa podwarstwa zajmuje się transmisją. Używane jest tu tradycyjne radio wąskopasmowe z konwencjonalnymi metodami modulacji. Nad warstwą transmisji fizycznej znajduje się podwarstwa zbieżności, która ukrywa różnorodność technologii przed warstwą łącza danych. W rzeczywistości 802.11 też ma coś w tym rodzaju, lecz komitet zdecydował się nie formalizować tej podwarstwy za pomocą nazwy w stylu OSI.

Wprawdzie nie przedstawiliśmy tego na rysunku, lecz trwają już prace nad dodaniem dwóch no­wych protokołów warstwy fizycznej.

Standard 802.16a będzie obejmował OFDM w paśmie częstotli­wości od 2 do 11 GHz. Standard 802.16b będzie pracować w paśmie ISM 5 GHz. Oba są próbami zbliżenia się do 802.11.

Warstwa łącza danych składa się z trzech podwarstw. Najniższa zajmuje się prywatnością i bezpie­czeństwem, które są o wiele ważniejsze w publicznych sieciach zewnętrznych niż w prywatnych sie­ciach wewnątrz budynków. Podwarstwa zarządza szyfrowaniem, deszyfracją i zarządzaniem kluczami.

Następna jest wspólna część podwarstwy MAC. Tutaj mieszczą się główne protokoły, takie jak protokół zarządzający kanałem. Model wygląda tak, że stacja bazowa steruje systemem. Może bardzo wydajnie planować kanały w dół (tzn. z bazy do abonenta); gra również ważną rolę w zarzą­dzaniu kanałami do transmisji w górę (od abonenta do stacji bazowej). Nietypową cechą tej podwar­stwy MAC jest to, że w przeciwieństwie do innych sieci 802 jest w pełni połączeniowa, aby mogła gwarantować jakość usług dla zastosowań telefonicznych i multimedialnych.

Zależna od usługi podwarstwa zbieżności zastępuje podwarstwę łącza logicznego z innych proto­kołów 802. Stanowi ona interfejs do warstwy sieciowej. Występuje tu komplikacja polegająca na tym, że 802.16 został zaprojektowany do bezproblemowej integracji zarówno z protokołami datagramów (tzn. PPP, IP i Ethernet), jak i ATM. Problem w tym, że protokoły pakietowe są bezpołączeniowe, a sieci ATM połączeniowe. Wobec tego każde połączenie ATM musi być odwzorowane na połą­czenie 802.16, co w zasadzie powinno być proste. Lecz do którego połączenia 802.16 powinien zostać przypisany przychodzący pakiet IP? Właśnie ten problem rozwiązuje ta warstwa.

4.5.3. Warstwa fizyczna 802.16

Jak już wspomniano, szerokopasmowa łączność bezprzewodowa wymaga bardzo dużego fragmentu widma, a jedyne miejsce, gdzie to pasmo jest dostępne, to zakres od 10 do 66 GHz. Te fale milime­trowe mają ciekawą właściwość, której nie dzielą z dłuższymi mikrofalami: rozchodzą się po linii prostej, inaczej niż dźwięk, lecz podobnie jak światło. Dzięki temu stacja bazowa może mieć kilka

RYSUNEK 4.29. Środowisko transmisji 802.16

Ponieważ poziom sygnału w paśmie milimetrowym szybko spada wraz z odległością od stacji bazowej, razem z nim maleje stosunek sygnał/szum. Z tego powodu w 802.16 stosowane są trzy metody modulacji, w zależności od dystansu pomiędzy użytkownikiem a stacją bazową. Dla naj­bliższych abonentów używana jest metoda QAM-64 z 6 bitami na bod. Dla abonentów w średniej odległości stosuje się QAM-16 z 4 bitami na bod, a dla najdalszych QPSK z 2 bitami na bod. Na przykład przy typowej porcji widma o szerokości 25 MHz QAM-64 daje 150 Mb/s, QAM-16 daje 100 Mb/s, a QPSK 50 Mb/s. Inaczej mówiąc, im dalej abonent znajduje się od stacji bazowej, tym niższe są szybkości transmisji danych (podobnie jak w ADSL z rysunku 2.23). Wykresy konstelacji dla tych trzech technik modulacji przedstawia rysunek 2.21.

Mając za zadanie stworzyć system szerokopasmowy przy tych wszystkich ograniczeniach, projektanci 802.16 napracowali się nad ekonomicznym wykorzystaniem dostępnego pasma. Przede wszystkim nie podobał im się sposób działania GSM i DAMPS. Oba systemy używają różnych pasm częstotliwości do transmisji wysyłającej i pobierającej, lecz o jednakowej szerokości. W przy­padku głosu ruch jest raczej najczęściej symetryczny, lecz w dostępie do Internetu często ruch po­bierający jest większy od ruchu wysyłającego. Wobec tego 802.16 zapewnia znacznie bardziej ela­styczną metodę przydziału pasma. Stosowane są dwie techniki, FDD (Freąuency Division Duplexing — praca dwukierunkowa z podziałem częstotliwości) i TDD (Time Division Duplexing — praca dwukierunkowa z podziałem czasu). Drugą technikę przedstawia rysunek 4.30. Tutaj stacja bazowa okresowo wysyła ramki. Każda ramka zawiera szczeliny czasowe. Pierwsze są dla ruchu po­bierającego. Po nich następuje czas ochronny, używany przez stacje do przełączenia kierunku. Na koniec mamy szczeliny dla ruchu wysyłającego. Liczba szczelin czasowych przeznaczonych na każdy kierunek może być zmieniana dynamicznie, aby dostosować przepustowość w każdym kie­runku do obciążenia.

Ruch pobierający jest mapowany na szczeliny czasowe przez stację bazową. Nad tym kierun­kiem stacja bazowa ma pełną kontrolę. Ruch wysyłający jest bardziej złożony i zależy od wymaganej jakości usług. Do przydzielania szczelin przejdziemy poniżej, przy opisie podwarstwy MAC.

Inną ciekawą cechą warstwy fizycznej jest jej zdolność do pakowania wielu ramek MAC jedna za drugą w pojedynczej fizycznej transmisji. Ta funkcja zwiększa wykorzystanie widma przez re­dukcję liczby potrzebnych preambuł i nagłówków warstwy fizycznej.

RYSUNEK 4.30. Ramki i szczeliny czasowe w pracy dwukierunkowej z podziałem czasu

Warto też zwrócić uwagę na użycie kodów Hamminga do współbieżnej korekcji błędów w war­stwie fizycznej. Niemal wszystkie pozostałe sieci po prostu wykrywają błędy za pomocą sum kontrolnych i żądają retransmisji błędnie odebranych ramek, lecz w środowisku rozległych sieci sze­rokopasmowych oczekuje się występowania tak wielu błędów, że korekcja błędów jest przeprowa­dzana w warstwie fizycznej, oprócz sum kontrolnych w wyższych warstwach. Skutek korekcji błędów jest taki, że kanał wygląda na lepszy niż jest w rzeczywistości (podobnie jak płyty CD-ROM spra­wiają wrażenie bardzo niezawodnych, lecz tylko dlatego, że ponad połowa wszystkich bitów po­święcona jest korekcji błędów w warstwie fizycznej).

4.5.4. Protokół podwarstwy MAC 802.16

Warstwa łącza danych jest podzielona na trzy podwarstwy, jak na rysunku 4.28. Ponieważ kryptogra­fią zajmiemy się dopiero w rozdziale 8., trudno tu objaśnić, jak działa podwarstwa zabezpieczeń. Wystarczy powiedzieć, że szyfrowanie służy do zachowania tajności wszystkich przesyłanych danych. Tylko ładunek użyteczny ramki jest szyfrowany, nagłówki nie. Ta właściwość oznacza, że ktoś podsłuchujący może zobaczyć, kto z kim rozmawia, lecz nie pozna treści rozmowy.

Dla tych, którzy wiedzą już coś o kryptografii, w jednym akapicie wyjaśnimy działanie pod­warstwy zabezpieczeń. Jeśli ktoś nie wie nic o kryptografii, ten akapit nie będzie specjalnie oświe­cający (lecz radzę powrócić do niego po przeczytaniu rozdziału 8.).

W chwili połączenia abonenta ze stacją bazową obie strony przeprowadzają wzajemne uwie­rzytelnienie z użyciem kryptografii z kluczem publicznym RSA, korzystając z certyfikatów X.509. Ładunek użyteczny ramek jest szyfrowany w systemie z kluczem symetrycznym, albo DES z łącze­niem bloków zaszyfrowanych, albo potrójnym DES z dwoma kluczami. Najprawdopodobniej nie­długo zostanie dodany AES (Rijndael). To nie było takie straszne, prawda?

Przyjrzyjmy się teraz wspólnej części podwarstwy MAC. Ramki MAC zajmują całkowitą liczbę szczelin czasowych warstwy fizycznej. Każda ramka składa się z podramek, z których dwie pierwsze są mapami ruchu wysyłającego i pobierającego. Mapy te informują, co znajduje się w po­szczególnych szczelinach czasowych i które szczeliny są wolne. Mapa ruchu pobierającego zawie­ra dodatkowo różne parametry systemu na potrzeby nowych stacji podłączających się do sieci.

Kanał pobierający jest stosunkowo prosty. Stacja bazowa po prostu decyduje, co umieścić w każ­dej podramce. Kanał wysyłający jest bardziej skomplikowany, ponieważ dostępu do niego potrzebują rywalizujący ze sobą nie skoordynowani abonenci. Przydział dostępu do kanału jest ściśle związany z kwestią jakości usług. Zostały zdefiniowane cztery klasy usług:

(1) Usługa ze stałą szybkością transmisji bitów.

(2) Usługa ze zmienną szybkością transmisji bitów w czasie rzeczywistym.

(3) Usługa ze zmienną szybkością transmisji bitów nie w czasie rzeczywistym.

(4) Usłup'. z użyciem dostępnych możliwości (best-effort).

Wszystkie usługi w 802.16 są połączeniowe, a każde połączenie otrzymuje usługę z jednej z powyż­szych klas, wybieraną podczas nawiązywania połączenia. Takie rozwiązanie zdecydowanie różni się od 802.11 i Ethernetu, w których w podwarstwie MAC nie występują połączenia.

Usługa ze stałą szybkością transmisji bitów jest przeznaczona do przesyłania niekompresowanego głosu, jak np. w kanale Tl. Usługa ta musi wysyłać ustalone ilości danych w z góry ustalonych od­stępach czasu. Osiąga się to przez przeznaczanie określonych szczelin czasowych dla każdego połą­czenia tego typu. Po przydzieleniu pasma szczeliny czasowe są przydzielane automatycznie, bez konieczności proszenia o każdą następną.

Usługa ze zmienną szybkością transmisji bitów w czasie rzeczywistym jest przeznaczona na media kompresowane i inne niekrytyczne zastosowania w czasie rzeczywistym, w których wymaga­ne pasmo może zmieniać się w czasie. Osiąga się to przez odpytywanie abonenta przez stację ba­zową w stałych odstępach czasu, jak wiele pasma wymaga w danej chwili.

Usługa ze zmienną szybkością transmisji bitów nie w czasie rzeczywistym jest przeznaczona dla intensywnych transmisji, które nie wymagają czasu rzeczywistego, na przykład do przesyłania dużych plików. W tej usłudze stacja bazowa odpytuje abonenta często, lecz nie w tak sztywno przydzielonych odstępach czasu. Klient ze stałą szybkością transmisji bitów może w jednej ze swoich ramek ustawić bit żądający odpytania, aby przesłać dodatkowe dane ze zmienną szybko­ścią transmisji.

Jeśli stacja nie odpowie na k odpytań pod rząd, stacja bazowa przenosi ją do grupy multiemisji i odbiera jej indywidualne odpytywanie. Zamiast tego na grupowe odpytanie może odpowiedzieć każda stacja z grupy, rywalizując o usługę. W ten sposób stacje o niewielkim ruchu nie marnują cennych odpytań.

Na koniec usługa z użyciem dostępnych możliwości jest przeznaczona dla wszystkich pozosta­łych sytuacji. Nie odbywa się w niej odpytywanie i abonent musi rywalizować o pasmo z innymi abonentami tej samej usługi. Żądanie przydzielenia pasma odbywają się w szczelinach czasowych transmisji wysyłających, oznaczonych jako dostępne dla rywalizacji. Jeśli żądanie zostanie przyjęte, jego powodzenie zostanie odnotowane w następnej mapie w transmisji pobierającej. W przeciwnym razie abonenci ponowią próbę później. Aby zminimalizować kolizje, został użyty binarny algorytm od­czekiwania wykładniczego z Ethernetu.

Standard definiuje dwie formy przydzielania pasma: na stację i na połączenie. W pierwszym przypadku stacja abonencka agreguje zapotrzebowania wszystkich użytkowników w budynku i składa za nich grupowe zamówienia. Gdy otrzymuje przydział pasma, wydziela je użytkownikom według własnego upodobania. W drugim przypadku stacja bazowa zarządza bezpośrednio każdym połączeniem.

4.5.5. Struktura ramki 802.16

Wszystkie ramki MAC zaczynają się od ogólnego nagłówka. Po nagłówku następuje opcjonalny ładunek użyteczny i opcjonalna suma kontrolna, jak na rysunku 4.31. Ładunek użyteczny nie jest potrzebny w ramkach sterujących, na przykład żądających przydziału szczelin w kanale. Suma kontrolna też jest, o dziwo, opcjonalna, z uwagi na korekcję błędów w warstwie fizycznej i fakt, że przy transmisji w czasie rzeczywistym nie występuje żadna próba retransmisji ramek. Po co więc w ogóle zawracać sobie wtedy głowę sumami kontrolnymi?

Pola nagłówka z rysunku 4.31 są następujące: bit EC mówi, czy ładunek ramki jest zaszyfrowa­ny. Pole Typ identyfikuje typ ramki, głównie informując, czy obecne są pakowanie i fragmentacja. Pole CI wskazuje obecność lub brak końcowej sumy kontrolnej. Pole EK informuje, jaki klucz szy­frujący jest używany (jeśli w ogóle). Pole Długość podaje całkowitą długość ramki, łącznie z na­główkiem. Pole Identyfikator połączenia określa, do którego połączenia należy ramka. Na koniec CRC nagłówka zawiera sumę kontrolną samego nagłówka używającą wielomianu x⁸ + x² + x + 1.

Rysunek 4.31 (b) przedstawia drugi typ nagłówka dla ramek żądających pasma. Zaczyna się od bitu „1" zamiast „0" i przypomina standardowy nagłówek ramki, z wyjątkiem drugiego i trzeciego bajta, które tworzą 16-bitową liczbę informującą, jakie pasmo jest potrzebne do przeniesienia określonej liczby bajtów. Ramki żądania pasma nie zawierają ładunku ani CRC dla całej ramki.

O 802.16 można by powiedzieć znacznie więcej, lecz nie tutaj. Po dodatkowe informacje odsy­łam do samego standardu.

4.6. Bluetooth

W roku 1994 firma L. M. Ericsson zainteresowała się łączeniem swoich telefonów komórkowych z in­nymi urządzeniami (np. PDA) bez użycia kabli. Razem z czterema innymi firmami (IBM, Intel, Nokia i Toshiba) Ericsson utworzył SIG (Special Interes Group, czyli konsorcjum) w celu opracowania standardu bezprzewodowego łączenia urządzeń i akcesoriów komputerowych i komunikacyjnych z użyciem tanich łączy radiowych o małej mocy i zasięgu. Projekt został nazwany Bluetooth od przydomku króla Wikingów Haralda Sinozębego (Bl&tand, po angielsku Bluetooth, 940 - 981), który połączył (tzn. podbił) Danię i Norwegię też nie używając kabli.

Wprawdzie pierwotnym zamysłem było po prostu pozbycie się kabli spomiędzy urządzeń, lecz standard szybko zaczął rozszerzać zakres i wkraczać na terytorium bezprzewodowych sieci LAN. Wprawdzie dzięki temu posunięciu standard staje się bardziej użyteczny, lecz zaczyna rywalizować o zainteresowanie z 802.11. Co gorsze, oba systemy zakłócają się też elektrycznie. Warto zanotować, że Hewlett-Packard wprowadził jakiś czas temu sieć na podczerwień służącą do łączenia kompute­rowych urządzeń peryferyjnych, lecz ten standard nigdy specjalnie się nie przyjął.

Nie zrażone tym konsorcjum Bluetooth w lipcu 1999 wydało 1500-stronicową specyfikację VI.0. Niedługo później grupa standaryzacji IEEE zajmująca się bezprzewodowymi sieciami osobi­stymi, 802.15, przyjęła dokument Bluetooth jako podstawę i zaczęła w nim dłubać. Wprawdzie stan­daryzacja czegoś, co już ma bardzo drobiazgową specyfikację i żadnych niezgodnych implementacji, które trzeba zgrać, wydaje się posunięciem dziwnym, lecz historia pokazała, że obecność otwarte­go standardu zarządzanego przez neutralną organizację typu IEEE często promuje technologię. Ści­ślej mówiąc, specyfikacja Bluetooth dotyczy kompletnego systemu, od warstwy fizycznej aż do warstwy aplikacji. Komitet IEEE 802.15 standaryzuje tylko warstwy fizyczną i łącza danych; reszta stosu protokołów wykracza poza jego zainteresowania.

Mimo że IEEE zaaprobował pierwszy standard sieci osobistej (PAN — Personal Area Network) 802.15.1 w roku 2002, lecz grupa Bluetooth nadal pracuje nad ulepszeniami. Wprawdzie wersje kon­sorcjum i IEEE nie są identyczne, lecz jest nadzieja, że wkrótce zbiegną się w jeden standard.

4.6.1. Architektura Bluetooth

Zacznijmy poznawanie systemu Bluetooth od krótkiego przeglądu, z czego się składa i do czego ma służyć. Podstawową jednostką systemu Bluetooth jest tzw. piconet („pikosieć"), która składa się z wę­zła głównego (master) i maksymalnie siedmiu aktywnych węzłów podrzędnych (slave) w odległości do 10 metrów. W jednym (dużym) pomieszczeniu może działać jednocześnie kilka takich mikro­skopijnych sieci, a nawet można je łączyć węzłem mostu, jak na rysunku 4.32. Połączony ze sobą zbiór sieci piconet nosi nazwę scatternet (sieć rozrzucona).

RYSUNEK 4.32. Dwie sieci piconet można połączyć w sieć scatternet

Poza siedmioma aktywnymi węzłami podrzędnymi w sieci piconet może znajdować się do 255 węzłów zaparkowanych. Są to urządzenia, które węzeł główny przełączył w stan niskiego poboru energii, aby oszczędzać ich baterie. W stanie zaparkowanym urządzenie nie może zrobić nic poza zareagowaniem na sygnał aktywacji lub nawigacyjny ze swojego węzła głównego. Są jeszcze dwa po­średnie stany zasilania, hołd (wstrzymanie) i sniff(vęszieme), lecz nimi nie będziemy się zajmować.

Powodem wybrania struktury master-slave było to, że projektanci chcieli umożliwić imple­mentację kompletnych układów Bluetooth w cenie poniżej 5 dolarów. W konsekwencji tej decyzji układy podrzędne są dość głupie — w zasadzie robią tylko to, co każe im węzeł główny. Piconet w istocie jest scentralizowanym systemem TDM, w którym węzeł główny kontroluje zegar i przy­dziela szczeliny czasowe urządzeniom. Cała komunikacja odbywa się pomiędzy węzłem głównym i podrzędnymi; bezpośrednia komunikacja pomiędzy dwoma węzłami podrzędnymi jest niemożliwa.

4.6.2. Zastosowania Bluetooth

Większość protokołów sieciowych po prostu udostępnia kanały pomiędzy komunikującymi się urządzeniami i pozwala twórcom aplikacji decydować, do czego kanał będzie użyty. Na przykład 802.11 nie określa, czy użytkownicy powinni wykorzystywać notebooki do czytania poczty, przeglądania WWW czy czegoś innego. W przeciwieństwie do tego standardu specyfikacja Blueto­oth wymienia 13 konkretnych zastosowań, które mają być obsługiwane i udostępnia osobny stos protokołów dla każdego z nich. Niestety, takie podejście wprowadza duże skomplikowanie, które­go nie będziemy tu omawiać. Wszystkie zastosowania, zwane profilami, przedstawia tabela 4.4. Krótkie zapoznanie się z nimi być może pozwoli nam lepiej zrozumieć, co chce osiągnąć grupa Bluetooth.

Profil ogólnego dostępu nie jest tak naprawdę aplikacją, lecz raczej podstawą, na której budo­wane są prawdziwe aplikacje. Jego głównym zadaniem jest nawiązywanie i utrzymywanie bezpiecz­nych łączy (kanałów) pomiędzy węzłem głównym i podrzędnymi. Również profil wykrywania usług, używany przez urządzenia do odkrywania, jakie usługi oferują inne urządzenia, jest stosunkowo ogólny. Od wszystkich urządzeń Bluetooth oczekuje się implementacji tych dwóch profili. Wszystkie pozostałe są opcjonalne.

Profil portu szeregowego jest protokołem transportowym, którego używa większość pozosta­łych profili. Emuluje on linię szeregową i jest przydatny zwłaszcza w starszych aplikacjach, wyma­gających łącza szeregowego.

Profil ogólnej wymiany obiektów definiuje relację klient-serwer dla przenoszenia danych. Klienty inicjują operacje, lecz węzeł podrzędny może być zarówno klientem, jak i serwerem. Podob­nie jak profil portu szeregowego jest to element konstrukcyjny dla innych profili.

Trzy następne profile wiążą się z sieciami komputerowymi. Profil dostępu do sieci lokalnej po­zwala na łączenie się urządzenia Bluetooth ze stałą siecią. Jest on bezpośrednim rywalem 802.11. Profil łącza telefonicznego był motorem do powstania całego projektu. Pozwala na łączenie bez ka­bla notebooka z telefonem mobilnym zawierającym wbudowany modem. Profil faksu przypomina łącze telefoniczne z tą różnicą że pozwala na wysyłanie i odbieranie faksów za pomocą przeno­śnego faksu i telefonu mobilnego bez łączenia ich kablem.

Trzy kolejne profile związane są z telefonią Profil telefonii bezprzewodowej udostępnia metodę łączenia zestawu słuchawkowego telefonu bezprzewodowego ze stacją bazową. W chwili obecnej większość telefonów bezprzewodowych nie może służyć w roli telefonów mobilnych (komórkowych), lecz w przyszłości te dwa typy urządzeń mogą się połączyć. Profil interkomu pozwala na łączenie dwóch telefonów jak radiotelefonów przenośnych. Profil zestawu słuchawkowego umożliwia roz­mowę bez zajmowania rąk pomiędzy zestawem słuchawkowym i jego stacją bazową na przykład do rozmów przez telefon podczas prowadzenia samochodu.

Trzy pozostałe profile służą do przesyłania obiektów pomiędzy dwoma urządzeniami bezprzewo­dowymi: wizytówek, obrazów, plików danych. Profil synchronizacji jest przeznaczony do ładowania danych do PDA lub notebooka przy wychodzeniu z nim z domu i odbieraniu danych z tego urządze­nia po powrocie do domu.

Czy naprawdę konieczne było szczegółowe wypisanie wszystkich tych zastosowań i użycie osobnego stosu protokołów dla każdego z nich? Prawdopodobnie nie, lecz różne grupy robocze opracowywały różne fragmenty standardu, a każda z nich koncentrowała się na własnym problemie i generowała własny profil. Tutaj sprawdziło się w praktyce prawo Conwaya: w kwietniowym wy­daniu czasopisma Datamation z 1968 roku Melvin Conway zauważył, że jeśli przydzielimy n osób do napisania kompilatora, to otrzymamy kompilator n-przebiegowy. Bardziej ogólnie mówiąc, struktura oprogramowania odzwierciedla strukturę grupy, która je napisała. Prawdopodobnie mo­głyby wystarczyć dwa stosy protokołów zamiast trzynastu: jeden do przesyłu plików i jeden do strumieniowej komunikacji w czasie rzeczywistym.

4.6.3. Stos protokołów Bluetooth

Standard Bluetooth zawiera wiele protokołów luźno pogrupowanych w warstwy. Struktura warstw nie jest zgodna z modelem OSI, modelem TCP/IP, modelem 802 ani żadnym innym. Jednakże IEEE pracuje nad modyfikacją standardu Bluetooth, aby lepiej wtłoczyć go do modelu 802. Podstawową architekturę protokołów Bluetooth zmodyfikowaną przez komitet 802 przedstawia rysunek 4.33.

RYSUNEK 4.33. Architektura protokołów Bluetooth w wersji 802.15

Na samym dole znajduje się fizyczna warstwa radiowa, która dość dokładnie odpowiada warstwie fizycznej modeli OSI i 802. Zajmuje się transmisją radiową i modulacją. Wiele problemów wiąże się w niej z próbą maksymalnego zredukowania kosztów, aby urządzenia mogły trafić na masowy rynek.

Warstwa pasma podstawowego do pewnego stopnia jest odpowiednikiem podwarstwy MAC, lecz jednocześnie zawiera elementy warstwy fizycznej. Zajmuje się sterowaniem przez węzeł główny szczelinami czasowymi i grupowaniem ich w ramki.

Następna warstwa zawiera grupę do pewnego stopnia spokrewnionych protokołów. Menedżer łą­czy zajmuje się tworzeniem logicznych kanałów pomiędzy urządzeniami, w tym zarządzaniem zasila­niem, uwierzytelnianiem i jakością usług. Protokół adaptacji sterowania łączem logicznym (nazywany często L2CAP) izoluje wyższe warstwy od szczegółów transmisji. Przypomina on standardową podwarstwę LLC z 802, lecz różni się od niej technicznie. Jak nazwa wskazuje, protokoły audio i ste­rujący zajmują się odpowiednio dźwiękiem i sterowaniem. Aplikacje mogą z nich korzystać bez­pośrednio, bez konieczności przechodzenia przez protokół L2CAP.

Następna idąc w górę jest warstwa pośrednia, zawierająca mieszankę różnych protokołów. IEEE wstawił tu LLC z 802 dla zgodności ze swoimi innymi sieciami 802. Protokoły RFcomm, telefonii i wykrywania usług są tu rdzenne. RFcomm (Radio Freąuency communication — komuni­kacja na częstotliwościach radiowych) jest protokołem emulującym standardowy port szeregowy służący w PC do podłączania, między innymi, klawiatury, myszy i modemu. Został on stworzo­ny, aby pozwolić na łatwiejsze używanie starszych urządzeń. Protokół telefonii działa w czasie rzeczywistym i obsługuje trzy wymienione wcześniej profile związane z mową, a oprócz tego za­rządza nawiązywaniem i kończeniem połączeń telefonicznych. Na koniec protokół wykrywania usług służy do znajdowania usług w sieci.

W najwyższej warstwie mieszczą się aplikacje i profile, które do swoich działań wykorzystują protokoły z warstw niższych. Każda aplikacja ma własny dedykowany podzbiór protokołów. Kon­kretne urządzenia, na przykład zestawy słuchawkowe, zwykle używają tylko protokołów wymaga­nych w konkretnym zastosowaniu i żadnych innych.

W poniższych punktach opiszemy trzy najniższe warstwy stosu protokołów Bluetooth, ponie­waż odpowiadają one z grubsza podwarstwom fizycznej i MAC.

4.6.4. Warstwa radiowa w Bluetooth

Warstwa radiowa przenosi bity z urządzenia głównego do podrzędnego i na odwrót. Jest to system o małej mocy i zasięgu 10 metrów działający w paśmie ISM 2,4 GHz. Pasmo zostało podzielone na 79 ka­nałów po 1 MHz. Modulacja odbywa się przez kluczowanie częstotliwości; 1 bit na Hz daje łączną przepustowość 1 Mb/s, lecz duża część tego pasma jest tracona na informacje dodatkowe. Aby ka­nały były przydzielane sprawiedliwie, używa się modulacji w widmie rozproszonym ze skokową zmianą kanału, z 1600 przeskoków na sekundę i czasem przebywania równym 625 us. Wszystkie węzły w piconecie przeskakują jednocześnie, a stacja główna dyktuje sekwencję przeskoków.

Ponieważ zarówno 802.11, jak i Bluetooth działają w paśmie ISM 2,4 GHz na tych samych 79 kanałach, to zakłócają się nawzajem. Bluetooth przeskakuje szybciej niż 802.11, więc znacznie bardziej prawdopodobne jest, że urządzenie Bluetooth zrujnuje transmisję 802.11 niż na odwrót. Ponieważ 802.11 i 802.15 są standardami IEEE, więc IEEE szuka rozwiązania tego problemu, lecz to nie jest takie łatwe, gdyż oba systemy z tego samego powodu korzystają z pasma ISM 2,4 GHz — nie wymaga ono licencji. Standard 802.1 la używa drugiego pasma ISM (5 GHz), lecz ma znacznie mniejszy za­sięg niż 802.1 lb (z uwagi na właściwości fal radiowych), więc nie we wszystkich przypadkach uży­cie 802.1 la jest rozwiązaniem idealnym. Niektóre firmy rozwiązały problem w ogóle zabraniając używania Bluetooth. Rozwiązanie oparte na rynku polega na tym, że sieć o większej mocy (poli­tycznej i ekonomicznej, a nie elektrycznej) żąda od słabszej sieci modyfikacji jej standardu, aby przestała zakłócać. Pewne przemyślenia na ten temat opublikował Lansford i inni (2001).

4.6.5. Warstwa pasma podstawowego w Bluetooth

Warstwa pasma podstawowego jest najbliższym odpowiednikiem podwarstwy MAC, jaki istnieje w Bluetooth. Przekształca ona surowy strumień bitów w ramki i definiuje pewne kluczowe for­maty. W najprostszej formie stacja główna w każdej sieci piconet definiuje serię szczelin czasowych o długości 625 us, przy czym transmisje stacji głównej zaczynają się w szczelinach parzystych, a transmisje stacji podrzędnych w nieparzystych. Jest to tradycyjne multipleksowanie z podziałem czasu, w którym stacja główna dostaje połowę szczelin, a stacje podrzędne dzielą się drugą połową. Ramki mogą mieć długość 1, 3 lub 5 szczelin.

Zależności czasowe w przełączaniu częstotliwości pozostawiają czas ustalania się równy 250 - 260 us na przeskok, aby ustabilizować obwody radiowe. Szybsze ustalanie jest możliwe, lecz tylko za wyższą cenę. Dla ramki zajmującej jedną szczelinę pozostaje 366 z 625 bitów. 126 z nich zajmuje kod dostępu i nagłówek, co zostawia 240 bitów na dane. Gdy łączy się pięć szczelin, potrzebny jest tylko jeden czas ustalania i używany jest nieco krótszy czas ustalania, więc z 5 • 625 = 3125 bitów w pięciu szczelinach czasowych warstwie pasma podstawowego pozostaje 2781 bitów. Oznacza to, że dłuższe ramki są o wiele wydajniejsze od ramek zajmujących jedną szczelinę.

Każda ramka jest przesyłana kanałem logicznym, zwanym łączem (link), pomiędzy stacją główną i podrzędną. Istnieją dwa typy łączy. Pierwszym jest łącze ACL (Asynchronous Connection-less bezpołączeniowe asynchroniczne), używane do przesyłania danych z komutacją pakietów pojawiających się w nieregularnych odstępach czasu. Dane te biorą się z warstwy L2CAP po stronie nadajnika i są doręczane do L2CAP po stronie odbiornika. Ruch ACL jest doręczany z użyciem dostępnych możliwości, bez gwarancji. Ramki mogą się gubić i wymagać retransmisji. Stacja podrzędna może mieć ty lko jedno łącze ACL ze swoją stacją główną.

Drugi typ to łącze SCO (Synchronous Connection Oriented — połączeniowe synchroniczne) do przesyłania danych w czasie rzeczywistym, na przykład do połączeń telefonicznych. Ten typ kanału jest kojarzony ze stałą szczeliną w każdym kierunku. Z uwagi na krytyczność czasu w łączach SCO ramki przesyłane nimi nigdy nie są retransmitowane. Zamiast tego można zapewnić wysoką nieza­wodność przez korekcję błędów. Stacja podrzędna może mieć maksymalnie trzy łącza SCO ze swoją stacją główną. Każde łącze SCO może służyć do przesyłania jednego kanału audio PCM 64 000 b/s.

4.6.6. Warstwa L2CAP w Bluetooth

Warstwa L2CAP ma trzy podstawowe funkcje. Po pierwsze, przyjmuje z wyższej warstwy pakiety o wielkości do 64 kB i dzieli je na ramki do transmisji. Na drugim końcu łącza ramki są ponownie zestawiane w pakiety.

Po drugie, obsługuje multipleksowanie i demultipleksowanie różnych źródeł pakietów. Gdy pa­kiet zostanie złożony ponownie, warstwa L2CAP ustala, do którego protokołu warstwy wyższej ma zostać przekazany, na przykład do RFcomm lub telefonii.

Po trzecie, L2CAP obsługuje wymogi jakości usług, zarówno podczas tworzenia łączy, jak i pod­czas ich eksploatacji. Poza tym w czasie zestawiania łącza negocjowany jest maksymalny dopusz­czalny rozmiar ładunku użytecznego, aby zapobiec zagłuszeniu urządzenia z małymi pakietami przez urządzenie z dużymi pakietami. Ta funkcja jest niezbędna, ponieważ nie wszystkie urządzenia potrafią obsługiwać maksymalne pakiety o wielkości 64 kB.

4.6.7. Struktura ramki Bluetooth

Istnieje kilka formatów ramek, z których najważniejszy przedstawia rysunek 4.34. Ramka zaczyna się od kodu dostępu, który zwykle identyfikuje stację główną, dzięki czemu stacje podrzędne w za­sięgu dwóch stacji głównych mogą ustalić, które informacje są przeznaczone dla nich. Następny jest 54-bitowy nagłówek zawierający typowe pola podwarstwy MAC. Po nim następuje pole danych o wielkości do 2744 bitów (dla transmisji w pięciu szczelinach). W pojedynczej szczelinie czasowej format pozostaje taki sam, z wyjątkiem pola danych, które ma 240 bitów.

Przyjrzyjmy się pobieżnie nagłówkowi. Pole Adres identyfikuje, dla którego z ośmiu aktyw­nych urządzeń ramka jest przeznaczona. Pole Typ identyfikuje typ ramki (ACL, SCO, poll, nuli), typ korekcji błędów używany w polu danych i liczbę szczelin zajmowanych przez ramkę. Bit Prze­pływ zaznacza stacja podrzędna, gdy jej bufor jest pełny i nie może przyjmować więcej danych. Jest to prymitywna forma sterowania przepływem. Bit Potwierdzenie służy do doczepienia ACK do ramki „na barana". Bit Sekwencja służy do numerowania ramek, aby unikać retransmisji. Ponieważ

protokół jest typu stop-and-wait, 1 bit wystarcza. Po nim następuje Suma kontrolna ramki. Cały 18-bitowy nagłówek jest powtórzony trzykrotnie, tworząc 54-bitowy nagłówek z rysunku 4.34. Po stronie odbiornika prosty układ sprawdza wszystkie trzy kopie każdego bitu. Jeśli wszystkie są ta­kie same, bit zostaje przyjęty. Jeśli nie, wygrywa większość. Jak widać, 54 bity transmisji służą do przesłania 10-bitowego nagłówka. Tak wysoka redundancja jest potrzebna, aby można było w nie­zawodny sposób przesyłać dane w obecności silnych zakłóceń z użyciem tanich urządzeń o małej mocy nadajnika (2,5 mW) i z niewielką mocą obliczeniową.

W polu danych ramek ACL używa się różnych formatów. Ramki SCO są prostsze — pole da­nych ma zawsze 240 bitów. Zostały zdefiniowane trzy odmiany, pozwalające na przesłanie 80, 160 lub 240 bitów faktycznego ładunku użytecznego, gdzie reszta jest używana do korekcji błędów. W naj­bardziej niezawodnej wersji (ładunek użyteczny 80 bitów) zawartość jest po prostu powtarzana trzy­krotnie, podobnie jak nagłówek.

Ponieważ stacja podrzędna może używać tylko nieparzystych szczelin, otrzymuje 800 szczelin na sekundę, podobnie jak stacja główna. Przy 80-bitowym ładunku roboczym zdolność przepu­stowa kanału wynosi po 64 000 b/s w każdym kierunku, co dokładnie wystarcza na pojedynczy pełnodupleksowy kanał głosowy PCM (dlatego też została wybrana szybkość 1600 przeskoków na sekundę). Liczby te oznaczają, że pełnodupleksowy kanał głosowy z 64 000 b/s w każdą stronę, używający najbardziej niezawodnego formatu, całkowicie nasyca piconet mimo surowej przepu­stowości 1 Mb/s. W najmniej niezawodnej odmianie (240 bitów na szczelinę bez redundancji) jed­nocześnie mogą być obsługiwane trzy pełnodupleksowe kanały głosowe, dlatego też dopuszcza się maksymalnie trzy łącza SCO na stację podrzędną.

O Bluetooth można powiedzieć znacznie więcej, lecz tu nie wystarczy na to miejsca. Dodatko­we informacje przedstawili Bhagwat (2001), Bisdikian (2001), Bray i Sturman (2002), Haartsen (2000), Johansson i inni (2001), Miller i Bisdikian (2001) oraz Sairam i inni (2002).

4.7. Przełączanie w warstwie łącza danych

Wiele organizacji eksploatuje dwie lub więcej sieci LAN i chce je połączyć. Sieci lokalne mogą być łączone za pomocą urządzeń zwanych mostami (ang. bridge), które działają w warstwie łącza danych. Mosty w celu kierowania danych sprawdzają adresy warstwy łącza danych. Ponieważ z założenia nie mają sprawdzać pola ładunku użytecznego kierowanych przez siebie ramek, mogą przesyłać IPv4 (protokół używany dziś w Internecie), IPv6 (będzie używany w Internecie w przyszłości), AppleTalk, ATM, OSI i wszelkie inne typy pakietów. W przeciwieństwie do nich routery sprawdzają adresy w pakietach i kierują pakiety na podstawie tych informacji. Wprawdzie ten podział pomiędzy mostami i routerami wydaje się jednoznaczny, pewne nowe techniki (takie jak przełączany Ethernet) rozmyły nieco ten obraz, co zobaczymy później. W następnych punktach przyjrzymy się mostom i przełączni­kom, zwłaszcza służącym do łączenia różnych sieci LAN 802. Wyczerpujący opis mostów, prze­łączników i związanych z nimi zagadnień podaje Perlman (2000).

Zanim przejdziemy do technologii mostów, warto przyjrzeć się pewnym typowym sytuacjom, w których mosty są używane. Wymienimy sześć powodów, dla których w jednej organizacji może pojawić się kilka sieci lokalnych.

Po pierwsze, wiele działów uczelni i dużych firm ma własne sieci LAN, głównie do łączenia własnych komputerów osobistych, stacji roboczych i serwerów. Ponieważ potrzeby różnych działów różnią się od siebie, każdy z nich mógł wybrać inną sieć LAN bez oglądania się na inne działy. Prędzej czy później pojawia się potrzeba interakcji, więc mosty stają się potrzebne. W tym przykła­dzie powstało więcej sieci lokalnych z powodu autonomii ich właścicieli.

Po drugie, organizacja może być geograficznie rozrzucona po kilku budynkach w dość znacznej odległości jeden od drugiego. Zainstalowanie osobnych sieci lokalnych w każdym budynku i połą­czenie ich mostami i łączami laserowymi może być tańsze niż przeciągnięcie jednego kabla po­między wszystkimi budynkami.

Po trzecie, może pojawić się potrzeba podzielenia logicznie pojedynczej sieci lokalnej na odrębne LAN, aby poradzić sobie z obciążeniem. Na przykład na wielu uczelniach dostępne są tysiące komputerów na potrzeby studentów i pracowników. Pliki są zwykle przechowywane w serwerach plików i pobierane do komputerów użytkowników na żądanie. Ogromna skala systemu wyklucza połączenie wszystkich stacji roboczych jedną siecią lokalną — łączna potrzebna przepustowość byłaby o wiele za wysoka. Zamiast tego używa się kilku sieci LAN połączonych mostami, jak na rysunku 4.35. Każda LAN zawiera grupę stacji roboczych i własny serwer plików, dzięki czemu większość ruchu ogranicza się do jednej sieci lokalnej i nie obciąża sieci szkieletowej.

RYSUNEK 4 .35. Kilka sieci LAN połączonych siecią szkieletową w celu poradzenia sobie z obciążeniem wyższym od zdolności przesyłowych pojedynczej sieci lokalnej

Warto zanotować, że chociaż zwykle rysujemy LAN jako kabel wielogałęziowy, jak na ry­sunku 4.35 (w sposób klasyczny), to częściej sieci te są implementowane z użyciem koncentra­torów, a obecnie przełączników. Jednakże długi wielogałęziowy kabel z podłączonymi do niego wieloma komputerami jest funkcjonalnie identyczny jak koncentrator z komputerami. W obu przy­padkach wszystkie komputery należą do tej samej domeny kolizji i wszystkie używają protokołu CSMA/CD do wysyłania ramek. Przełączane (komutowane) sieci LAN wyglądają jednak inaczej, jak zobaczymy za chwilę.

Po czwarte, w niektórych sytuacjach pojedyncza sieć LAN wystarczyłaby pod względem obcią­żenia, lecz fizyczna odległość pomiędzy najbardziej oddalonymi od siebie komputerami jest zbyt wielka (np. ponad 2,5 km dla Ethernetu). Nawet jeśli położenie kabli będzie łatwe, sieć nie będzie działać z powodu nadmiernie długiego opóźnienia podróży w obie strony. Jedynym rozwiązaniem jest tu podzielenie sieci lokalnej i zainstalowanie mostów pomiędzy segmentami. W ten sposób całkowity dystans pomiędzy komputerami można zwiększyć.

Po piąte, trzeba pamiętać o niezawodności. W pojedynczej sieci LAN niesprawny węzeł, który wysyła ciągły strumień śmieci, może sparaliżować sieć. Mosty można wstawiać w miejscach kry­tycznych, podobnie jak drzwi pożarowe w budynkach, aby zapobiegać blokadzie całego systemu przez jeden oszalały węzeł. W przeciwieństwie do wzmacniaka, który kopiuje wszystko bez wy­jątku, most można zaprogramować tak, by decydował, co przekazać dalej, a co nie.

Po szóste i ostatnie, mosty mogą zwiększyć bezpieczeństwo firmy. Większość interfejsów sie­ciowych LAN ma dostępny tzw. tryb nasłuchu (promiscuous mode), w którym komputer otrzy­muje wszystkie ramki, a nie tylko zaadresowane do niego. Szpiedzy i wścibscy uwielbiają tę funk­cję. Wstawiając mosty w wybranych miejscach i pilnując, aby nie przekazywały dalej poufnych danych, administrator może izolować fragmenty sieci, aby przesyłane dane nie „wyciekały" i nie trafiały w niepowołane ręce.

W idealnych warunkach mosty powinny być w pełni przezroczyste, co oznacza, że powinno być możliwe przeniesienie komputera z jednego segmentu kabla do innego bez zmian w sprzęcie, oprogramowaniu i konfiguracji. Poza tym komputery w dowolnym segmencie powinny mieć zdol­ność do komunikacji z komputerami w każdym innym segmencie, niezależnie od typów sieci LAN używanych w obu segmentach i w segmentach po drodze między nimi. Ten cel czasem jest osią­gany, lecz nie zawsze.

4.7.1. Mosty pomiędzy 802.x i 802.y

Wiedząc, do czego potrzebne są mosty, przejdźmy do sposobu ich działania. Rysunek 4.36 ilustruje działanie prostego mostu z dwoma portami. Host A w bezprzewodowej (802.11) sieci LAN ma do przesłania pakiet do stacjonarnego hosta B w sieci Ethernet (802.3), z którą połączona jest bezprzewodowa LAN. Pakiet przechodzi w dół do podwarstwy LLC i otrzymuje nagłówek LLC (za­znaczony na rysunku na czarno). Następnie przechodzi do podwarstwy MAC i zostaje do niego dołą­czony nagłówek 802.11 (oraz stopka, nie pokazana na rysunku). Ta całość zostaje wysłana w eter i odebrana przez stację bazową, która rozpoznaje, że pakiet musi przejść do stacjonarnego Ethernetu. Po dojściu do mostu łączącego sieci 802.11 i 802.3 pakiet, zaczynając od warstwy fizycznej, wędruje w górę. W podwarstwie MAC mostu zostaje usunięty nagłówek 802.11. Goły pakiet (z nagłówkiem LLC) zostaje następnie przekazany do podwarstwy LLC mostu. W tym przykładzie pakiet jest przeznaczony dla sieci LAN 802.3, więc wędruje w dół po stronie 802.3 mostu i wychodzi w Et­hernet. Zwróćmy uwagę, że most łączący k różnych sieci LAN będzie miał k różnych podwarstw MAC i k różnych warstw fizycznych, po jednej dla każdego typu.

Jak na razie wygląda, że przeniesienie ramki z jednej sieci LAN do drugiej jest łatwe. Niestety, tak nie jest. W tym punkcie przedstawimy kilka z trudności, które możemy napotkać przy próbie budowania mostu pomiędzy różnymi sieciami lokalnymi 802 (i miejskimi). Skupimy się na 802.3, 802.11 i 802.16, lecz istnieją też inne, każda z własnymi problemami.

Zacznijmy od tego, że każdy typ sieci używa innego formatu ramki (patrz rysunek 4.37). W prze-:iwieństwie do różnic pomiędzy sieciami Ethernet, Token Bus i Token Ring, za które odpowiada hi­storia i wybujałe ego korporacji, tutaj różnice są do pewnego stopnia usprawiedliwione. Na przykład ?ole Czas trwania w 802.11 bierze się z protokołu MACAW i nie ma na nie miejsca w Ethernecie.

RYSUNEK 4.37. Formaty ramek IEEE 802. Długości pól nie są narysowane proporcjonalnie

W wyniku tego kopiowanie ramki pomiędzy różnymi sieciami wymaga przeformatowania, co zajmuje czas procesora, wymaga obliczenia sumy kontrolnej na nowo i wprowadza możliwość pojawiania się niewykrytych błędów powodowanych uszkodzonymi bitami w pamięci mostu.

Drugi problem polega na tym, że połączone sieci LAN nie zawsze działają z tą samą szybko­ścią. Przy przekazywaniu z szybszej sieci do wolniejszej długiego ciągu ramek, nadchodzących jedna za drugą, most nie będzie w stanie pozbywać się ramek tak szybko, jak przychodzą. Na przykład, jeśli Gigabit Ethernet z maksymalną szybkością wtłacza bity do 11 Mb/s sieci 802. Ib, most musi je buforować i mieć nadzieję, że nie skończy mu się pamięć. Mosty łączące trzy lub więcej sieci mają podobny problem, gdy kilka sieci próbuje wysyłać z maksymalną szybkością dane do jednej LAN, nawet jeśli wszystkie działają z tą samą szybkością.

Trzeci problem, potencjalnie najpoważniejszy, polega na tym, że różne sieci lokalne 802 mają różne maksymalne długości ramek. Oczywisty kłopot pojawia się, gdy zachodzi potrzeba przeka­zania długiej ramki do sieci, która nie będzie mogła jej przyjąć. W tej warstwie podział ramki na ka­wałki jest wykluczony. Wszystkie protokoły zakładają, że ramka albo dociera, albo nie. Nie istnieje żaden mechanizm do ponownego składania ramek z mniejszych kawałków. Nie znaczy to, że takich Protokołów nie można stworzyć. Jest to możliwe i było już realizowane. Po prostu żaden protokół łącza danych nie udostępnia tej funkcji, więc mosty nie mogą ingerować w ładunek użyteczny ramki. Zasadniczo rozwiązania nie ma. Ramki zbyt duże, aby można było je przekazać dalej, muszą być odrzucone. I możemy pożegnać się z przezroczystością.

Kolejnym problemem jest bezpieczeństwo. Zarówno 802.11, jak i 802.16 obsługują szyfrowa­nie w warstwie łącza danych.'Ethernet nie. Oznacza to, że różnorodne usługi szyfrowania dostępne w sieciach bezprzewodowych są tracone przy przechodzeniu transmisji przez Ethernet. Co gorsze, jeśli bezprzewodowa stacja używa szyfrowania w warstwie łącza danych, nie będzie jak odszy­frować danych po przesłaniu przez Ethernet. Jeśli stacja bezprzewodowa nie używa szyfrowania, dane będą wystawione na widok publiczny w łączu radiowym. Tak czy inaczej mamy problem.

Jednym z rozwiązań problemu z bezpieczeństwem może być szyfrowanie w warstwie wyższej, lecz wtedy stacja 802.11 musi wiedzieć, czy komunikuje się z inną stacją w sieci 802.11 (co ozna­cza użycie szyfrowania w warstwie łącza danych), czy nie (co oznacza, że nie należy szyfrować). Zmuszenie stacji do dokonywania wyboru likwiduje przezroczystość.

Ostatnią kwestią jest jakość usług. Zarówno 802.11, jak i 802.16 oferują ją w różnych posta­ciach, pierwsza z użyciem trybu PCF, a druga za pomocą połączeń ze stałą szybkością transmisji bitów. W Ethernecie pojęcie jakości usług nie istnieje, więc transmisje pomiędzy dwiema po­przednimi sieciami utracą jakość usługi przy przechodzeniu przez Ethernet.

4.7.2. Lokalne sieci złożone

Poprzedni punkt dotyczył problemów z łączeniem dwóch różnych sieci lokalnych IEEE 802 jed­nym mostem. Jednakże w dużych organizacjach z wieloma sieciami LAN już samo łączenie ich wiąże się z szeregiem problemów, nawet jeśli wszystkie są typu Ethernet. Idealnie powinniśmy móc po prostu kupić mosty zaprojektowane zgodnie ze standardem IEEE, wetknąć do nich złącza sieciowe i wszystko powinno z miejsca zacząć działać bez zarzutu. Nie powinno to wymagać zmian w sprzęcie i w oprogramowaniu, ustawiania adresów na przełącznikach, pobierania tablic routingu i parametrów... Powinno wystarczyć włożenie wtyczki. Co więcej, mosty nie powinny w ogóle wpły­wać na działanie istniejących sieci LAN. Inaczej mówiąc, mosty powinny być całkowicie przezro­czyste (niewidoczne dla sprzętu i oprogramowania). O dziwo, to rzeczywiście jest możliwe. Zobaczmy teraz, jak ta sztuczka się udaje.

RYSUNEK 4.38. Konfiguracja z czterema sieciami lokalnymi i dwoma

W najprostszej formie przezroczysty most funkcjonuje w trybie nasłuchu, odbierając każdą ramkę przesyłaną w sieci LAN, do której jest podłączony. Weźmy na przykład konfigurację z ry­sunku 4.38. Most BI jest podłączony do sieci nr 1 i 2, a most B2 do sieci 2, 3 i 4. Docierająca do mo­stu BI w sieci LAN 1 ramka przeznaczona dla A może zostać natychmiast odrzucona, ponieważ już znajduje się we właściwej sieci lokalnej, lecz ramki w LAN 1 przeznaczone dla hostów C lub F muszą zostać przekazane dalej.

Most odbierający ramkę musi zdecydować, czyją odrzucić czy przekazać dalej, a w drugim przypadku, do której LAN ma ramkę przekazać. Decyzję tę podejmuje, wyszukując adres docelowy w dużej tablicy (przemieszczania) zapisanej w moście. Tablica może zawierać każdy możliwy adres docelowy i informować, do której linii wyjściowej (LAN) ten adres należy. Na przykład tablica w B2 wskazałaby A jako hosta w LAN 2, ponieważ B2 musi wiedzieć tylko to, do której sieci przekazać ramkę dla A To, że w rzeczywistości wystąpi kolejne przekazanie ramki dalej, nie jest dla B2 istotne.

W chwili podłączenia mostów wszystkie tablice przemieszczania są puste. Żaden most nie zna żadnego adresu docelowego, więc używa algorytmu rozpływowego — każda ramka przychodząca przeznaczona dla nieznanego odbiorcy jest wysyłana do wszystkich LAN, do których most jest pod­łączony, z wyjątkiem tej, z której ramka dotarła. Z upływem czasu mosty poznają położenie adre­sów docelowych w sposób opisany poniżej. Gdy adres docelowy jest już znany, ramki przezna­czone dla niego zostają po prostu wysłane do właściwej sieci lokalnej i nie zalewają innych sieci.

Algorytm używany przez przezroczyste mosty nosi nazwę uczenia się wstecz (backward lear-ning). Jak wspomniano powyżej, most działa w trybie nasłuchu, więc widzi każdą ramkę wysłaną w każdej ze swoich LAN. Sprawdzając adresy źródłowe może określić, który komputer jest do­stępny w której sieci lokalnej. Na przykład, jeśli most BI z rysunku 4.38 zobaczy w LAN 2 ramkę pochodzącą od C, to dowie się, że host C musi być dostępny przez LAN 2, więc wprowadza do swojej tablicy przemieszczania wpis informujący, że ramki przeznaczone dla C powinny przechodzić do LAN 2. Każda następna ramka zaadresowana do C i pochodząca z LAN 1 będzie przekazana dalej, lecz ramka dla C pochodząca z LAN 2 zostanie odrzucona.

Topologia może się zmieniać w miarę włączania, wyłączania i przenoszenia komputerów i mo­stów. Aby poradzić sobie z dynamicznie zmieniającymi się topologiami, most przy dokonaniu każdego wpisu w tablicy przemieszczania notuje godzinę dotarcia ramki. Za każdym razem, gdy do mostu dociera ramka mająca już wpis w tablicy, jej wpis jest aktualizowany przez wprowadzenie aktualnego czasu. Dzięki temu każdy wpis zawiera informację, kiedy konkretny komputer był wi­dziany po raz ostatni.

Okresowo proces w moście przegląda tablicę przemieszczania i usuwa wszystkie wpisy mające więcej niż kilka minut. Dzięki temu, jeśli komputer zostanie odłączony od swojej sieci lokalnej, przeniesiony do innego pokoju i podłączony do innej sieci, w ciągu kilku minut wraca do normalnego działania bez interwencji administratora. Algorytm ten oznacza też, że jeśli komputer nie wysyłał niczego przez kilka ostatnich minut, każda ramka przychodząca do niego będzie rozsyłana do wszyst­kich sieci, dopóki sam komputer nie wyśle swojej ramki.

Procedura rutingu przychodzących ramek jest zależna od sieci lokalnej, z której ramka pochodzi (źródłowej LAN), i sieci, w której znajduje się zamierzony odbiorca (docelowej LAN) i wygląda tak:

1. Jeśli źródłowa i docelowa LAN są te same, odrzuć ramkę.

2. Jeśli źródłowa i docelowa LAN są różne, przekaż ramkę dalej.

3. Jeśli docelowa LAN jest nieznana, użyj rozpływu.

Ten algorytm musi być stosowany do każdej przychodzącej ramki. Dedykowane układy scalone VLSI wyszukują i aktualizują wpisy w tablicach w ciągu kilku mikrosekund.

4.7.3. Drzewa częściowe mostów

Aby zwiększyć niezawodność, niektóre ośrodki mają dwa lub więcej równoległych mostów pomię­dzy parami LAN, jak na rysunku 4.39. Jednakże taka struktura wprowadza dodatkowe problemy, ponieważ tworzy pętle w topologii.

Prosty przykład tych problemów możemy zobaczyć, obserwując, jak na rysunku 4.39 traktowa­na jest ramka F z nieznanym adresem docelowym. Każdy most, postępując zgodnie z regułami traktowania nieznanych adresów docelowych, używa algorytmu rozpływowego, co w tym przykładzie oznacza po prostu skopiowane ramki do LAN 2. Po chwili most 1 zauważa ramkę F₂ o nieznanym adresie docelowym, którą kopiuje do LAN 1, generując w ten sposób F₃ (nie pokazaną na rysunku). Most 2 analogicznie kopiuje Fi do LAN 1, generując F₄ (również nie pokazaną). Teraz most 1 przekazuje dalej F₄, a most 2 kopiuje F₃. Ten cykl może powtarzać się bez końca.

Rozwiązanie tego problemu polega na komunikowaniu się mostów ze sobą i nałożeniu na fak­tyczną topologię drzewa częściowego, które sięga do każdej sieci lokalnej. W wyniku tego pewne potencjalne połączenia pomiędzy LAN są ignorowane w celu utworzenia fikcyjnej topologii bez pętli. Na przykład na rysunku 4.40 (a) widzimy dziewięć sieci LAN połączonych dziesięcioma mostami. Tę konfigurację możemy odwzorować na graf z LAN w roli węzłów. Łuki łączą wszyst­kie pary LAN połączonych mostami. Ten graf może zostać zredukowany do drzewa częściowego przez odrzucenie łuków przedstawionych na rysunku 4.40 (b) linią przerywaną. W owym drzewie czę­ściowym z każdej sieci lokalnej do każdej innej sieci lokalnej istnieje dokładnie jedna trasa. Po uzgodnieniu drzewa częściowego przez mosty całe przekazywanie dalej pakietów pomiędzy sie­ciami odbywa się wzdłuż tego drzewa. Ponieważ ścieżki pomiędzy źródłem i celem transmisji są zawsze jednoznaczne, pętle nie mogą wystąpić.

Aby zbudować drzewo częściowe, najpierw mosty muszą wybrać spośród siebie jeden, który będzie węzłem głównym (korzeniem) drzewa. Wybór odbywa się przez rozgłoszenie przez każdy most swojego numeru seryjnego określanego przez producenta i dającego gwarancję, że jest glo­balnie unikatowy. Most o najniższym numerze seryjnym zostaje węzłem głównym. Następnie two­rzone jest drzewo najkrótszych ścieżek z węzła głównego do każdego innego mostu i sieci LAN. Otrzymujemy drzewo częściowe (inaczej dendryt). Gdy któryś most lub LAN zawiedzie, tworzone jest nowe drzewo.

W wyniku użycia tego algorytmu powstają unikatowe ścieżki z każdej sieci LAN do węzła głównego, czyli również do każdej innej LAN. Wprawdzie drzewo obejmuje wszystkie sieci lokalne, lecz nie każdy most musi się w nim znaleźć (aby uniknąć powstawania pętli). Nawet po utworzeniu drzewa częściowego algorytm pracuje dalej podczas normalnej eksploatacji, aby automatycznie wy­krywać zmiany w topologii i aktualizować drzewo. Rozproszony algorytm tworzenia drzewa częścio­wego stworzył i szczegółowo opisał Radia Perlman (2000). Algorytm został standardem w IEEE 802.1D.

4.7.4. Odległe mosty

Częstym zastosowaniem mostów jest łączenie dwóch (lub więcej) odległych sieci lokalnych. Na przykład firma może mieć zakłady w kilku miastach, z osobną siecią w każdym zakładzie. Najlepiej byłoby, gdyby wszystkie sieci LAN były ze sobą połączone, aby cały system funkcjonował jak jedna duża sieć lokalna.

Ten cel można osiągnąć przez umieszczenie mostu w każdej LAN i połączenie mostów parami za pomocą łączy dwupunktowych (tzn. łączy dzierżawionych od firmy telefonicznej). Rysunek 4.41 przedstawia prosty system z trzema sieciami lokalnymi. Stosują się do niego typowe algorytmy ru-tingu. Najprościej jest uznać łącza dwupunktowe za sieci LAN bez hostów, wówczas otrzymamy standardowy system sześciu sieci lokalnych połączonych czterema mostami. Nic, czego dowie­dzieliśmy się do tej pory o sieciach lokalnych, nie mówi, że LAN musi zawierać hosty.

RYSUNEK 4.41. Zdalne mosty mogą posłużyć do łączenia odległych sieci lokalnych

W łączach dwupunktowych mogą być stosowane różnorodne protokoły. Można na przykład wybrać jakiś standardowy dwupunktowy protokół łącza danych, taki jak PPP, umieszczając kompletne ramki MAC w polu ładunku użytecznego. Taka strategia sprawdza się najlepiej, gdy wszystkie sieci LAN są identyczne, a jedynym problemem jest przekazywanie ramek do właściwej sieci. Inna opcja polega na usunięciu nagłówka i stopki MAC w moście źródłowym i umieszczenie całej reszty w polu ładunku protokołu dwupunktowego. W moście docelowym może zostać wygenerowa­ny nowy nagłówek i stopka MAC. Wadą takiego rozwiązania jest to, że suma kontrolna docierają­ca do hosta docelowego nie została obliczona przez hosta źródłowego, więc błędy wprowadzone przez uszkodzone bity w pamięci mostu nie zostaną wykryte.

4.7.5. Wzmacniaki, koncentratory, mosty, przełączniki, routery i bramy

Jak dotąd poznaliśmy szereg sposobów na przenoszenie ramek i pakietów z jednego segmentu kabla do drugiego. Wspomnieliśmy wzmacniaki, mosty, przełączniki, koncentratory, routery i bramy. Wszystkie te urządzenia są powszechnie stosowane, lecz różnią się na bardziej i mniej subtelne spo­soby. Ponieważ jest ich tak wiele, to chyba warto przyjrzeć się im razem, aby poznać podobieństwa i różnice.

Po pierwsze, urządzenia te funkcjonują w różnych warstwach, jak widać z rysunku 4.42 (a). Warstwa jest ważna, ponieważ różne urządzenia używają różnych fragmentów informacji do podję­cia decyzji o sposobie komutacji. W typowym scenariuszu użytkownik generuje jakieś dane prze­znaczone do przesłania do odległego komputera. Dane te są przekazywane do warstwy transporto­wej, która następnie dodaje nagłówek (np. TCP) i przekazuje uzyskaną całość w dół do warstwy sieciowej. Ta dodaje własny nagłówek, aby utworzyć pakiet warstwy sieciowej, na przykład IP. Na rysunku 4.42 (b) pakiet IP został zaznaczony na szaro. Następnie pakiet przechodzi do warstwy łącza danych, która dodaje własny nagłówek oraz sumę kontrolną (CRC) i wynikłą ramkę przeka­zuje w celu transmisji (np. poprzez LAN) do warstwy fizycznej.

RYSUNEK 4.42. (a) Przynależność urządzeń do warstw, (b) Ramki, pakiety i nagłówki

Przyjrzyjmy się teraz urządzeniom przełączającym i ich związkom z pakietami i ramkami. Na samym dole, w warstwie fizycznej, znajdziemy wzmacniaki. Są to urządzenia analogowe podłączone do dwóch segmentów kabla. Sygnał pojawiający się w jednym segmencie zostaje wzmocniony i wy­słany do drugiego. Wzmacniaki nie rozumieją ramek, pakietów i nagłówków. Rozumieją napięcia. Klasyczny Ethernet, na przykład, pozwala na cztery wzmacniaki pod rząd, umożliwiając zwięk­szenie maksymalnej długość kabla z 500 metrów do 2500 metrów.

Następne są koncentratory. Koncentrator ma pewną liczbę linii wejściowych, które łączy elektrycznie. Ramki pojawiające się w dowolnej linii są wysyłane do wszystkich pozostałych. Jeśli jednocześnie przyjdą dwie ramki, wystąpi kolizja, tak samo jak w kablu koncentrycznym. Inaczej mówiąc, cały koncentrator stanowi jedną domenę kolizji. Wszystkie linie wchodzące do koncen­tratora muszą działać z tą samą szybkością. Koncentratory różnią się od wzmacniaków tym, że (zazwyczaj) nie wzmacniają przychodzących sygnałów i są tak skonstruowane, że mieszczą kilka kart z kilkoma łączami na każdej, lecz różnice są niewielkie. Podobnie jak wzmacniaki, koncen­tratory nie sprawdzają adresów 802 i nie używają ich w żaden sposób. Koncentrator przedstawia rysunek 4.43 (a).

Przejdźmy teraz do warstwy łącza danych, w której znajdziemy mosty i przełączniki. Mosty już trochę poznaliśmy. Most łączy dwie lub więcej sieci LAN, jak na rysunku 4.43 (b). Gdy przychodzi do niego ramka, oprogramowanie mostu wydobywa adres docelowy z nagłówka ramki i szuka go

w tablicy, aby sprawdzić, gdzie ma przesłać ramkę. W Ethernecie adresem tym jest 48-bitowy adres docelowy z rysunku 4.16. Podobnie jak koncentratory, nowoczesne mosty zawierają karty łączy dla różnych typów i szybkości sieci. W moście, w przeciwieństwie do koncentratora, każda linia jest osobną domeną kolizji.

Przełączniki przypominają mosty — oba urządzenia kierują ruch na podstawie adresów ramek. W istocie wiele osób używa tych nazw zamiennie. Urządzenia różnią się tym, że przełącznik najczęściej służy do łączenia poszczególnych komputerów, jak na rysunku 4.43 (c). Gdy host A z ry­sunku 4.43 (b) chce wysłać ramkę do hosta B, most odbiera ramkę, lecz ją odrzuca; natomiast prze­łącznik z rysunku 4.43 (c) musi aktywnie przekazać ramkę zAdoB, ponieważ inaczej ramka tam nie dotrze. Każdy port przełącznika zwykle przeznaczony jest dla jednego komputera, więc przełącz­niki muszą mieć miejsce na o wiele więcej kart złączy niż mosty, przeznaczone tylko do łączenia sieci lokalnych. Ponieważ każdy port jest osobną domeną kolizji, przełączniki nigdy nie tracą ramek z powodu kolizji. Jeśli jednak ramki będą przychodzić szybciej, niż będzie można je retransmitować, w przełączniku może braknąć miejsca w buforach i urządzenie zacznie porzucać ramki.

Aby nieco złagodzić ten problem, współczesne przełączniki zaczynają przekazywać ramki natychmiast po nadejściu pola adresu docelowego nagłówka, lecz przed dotarciem reszty ramki (oczywiście pod warunkiem, że linia wyjściowa jest wolna). Przełączniki te nie stosują komutacji z buforowaniem. Czasem są określane nazwą przełączników typu cut-through (przetnij-przepuść). Zwykle proces ten odbywa się sprzętowo, podczas gdy mosty tradycyjnie zawierały procesor, który przeprowadzał komutację z buforowaniem w oprogramowaniu. Lecz ponieważ wszystkie współ­czesne mosty i przełączniki zawierają specjalne układy scalone służące do komutacji, różnica po­między mostem i przełącznikiem jest bardziej marketingowa niż techniczna.

Jak do tej pory poznaliśmy wzmacniaki i koncentratory, które są dość podobne do siebie, oraz mosty i przełączniki, które również przypominają się nawzajem. Teraz przejdziemy w górę do ro­uterów, które różnią się od wszystkich dotychczasowych urządzeń. Gdy pakiet dociera do routera, nagłówek i stopka ramki są usuwane, a pakiet mieszczący się w polu ładunku użytecznego ramki (zacieniowany na rysunku 4.42) jest przekazywany do oprogramowania rutingu. Oprogramowanie to na podstawie nagłówka pakietu wybiera linię wyjściową. W pakiecie IP nagłówek zawiera adres 32-bitowy (IPv4) lub 128-bitowy (IPv6), a nie 48-bitowy adres 802. Oprogramowanie rutingu nie widzi adresu ramki i nie wie nawet, czy pakiet został przysłany przez LAN czy przez łącze dwu-punktowe. Routery i ruting poznamy w rozdziale 5.

O jeszcze jedną warstwę wyżej znajdziemy bramy w warstwie transportowej. Łączą one dwa komputery, używające odmiennych połączeniowych protokołów transportowych. Załóżmy, na przy­kład, że komputer używający połączeniowego protokołu TCP/IP chce komunikować się z kompute­rem używającym połączeniowego protokołu ATM. Brama w warstwie transportowej może kopio­wać pakiety z jednego połączenia do drugiego, w razie potrzeby zmieniając ich format.

Na koniec bramy w warstwie aplikacji rozumieją format i zawartość danych i tłumaczą komu­nikaty z jednego formatu na drugi. Brama e-mail może, na przykład, tłumaczyć wiadomości interne­towe na wiadomości SMS dla telefonów komórkowych.

4.7.6. Wirtualne sieci LAN

U zarania sieci lokalnych grube żółte kable wiły się w rynienkach kablowych wielu budynków biu­rowych. Każdy komputer, obok którego przechodziły, był do nich podłączany. Często kabli było więcej i łączyły się z centralną siecią szkieletową (jak na rysunku 4.35) lub koncentratorem. Nie zastanawiano się, który komputer należy do której sieci lokalnej. Wszyscy użytkownicy w sąsiednich pokojach byli łączeni z tą samą siecią LAN, niezależnie od tego, czy należeli do niej czy nie. Geo­grafia przebijała logikę.

Pojawienie się lOBase-T i koncentratorów w latach 90. zmieniło to radykalnie. Prowadzono na nowo okablowanie w budynkach (niemałym kosztem), wyrywając żółte węże ogrodnicze i instalując skrętkę z każdego pomieszczenia biurowego do centralnej szafki kablowej na końcu każdego koryta­rza lub w centralnej sali komputerowej, jak na rysunku 4.44. Jeśli Z-ca Dyrektora d/s Okablowania był wizjonerem, instalowano skrętkę kategorii 5.; jeśli kutwą, używano istniejącego okablowania te­lefonicznego kategorii 3. (tylko po to, aby je wymienić za kilka lat, gdy pojawił się Fast Ethernet).

RYSUNEK 4.44. Budynek ze scentralizowanym okablowaniem używającym koncentratorów i przełącznika

Wprowadzenie do Ethernetu koncentratorów (a później przełączników) umożliwiło w wielu przypadkach konfigurowanie sieci LAN logicznie, a nie fizyczne. Firma chcąca mieć k sieci LAN kupuje k koncentratorów. Decydując, które złącza przeznaczone są dla konkretnych koncentrato­rów, można podzielić użytkowników na sieci lokalne w sposób mający sens organizacyjny, bez zwracania większej uwagi na geografię. Oczywiście jeśli dwie osoby z tego samego działu pracują w dwóch różnych budynkach, to przypuszczalnie będą należeć do osobnych koncentratorów i sieci LAN. Mimo to sytuacja jest teraz o wiele lepsza niż przy przydzielaniu użytkowników do sieci lokalnych wyłącznie na podstawie geografii.

Czy to ma znaczenie, kto jest w której sieci LAN? W końcu w praktycznie każdej organizacji wszystkie LAN są ze sobą połączone. Krótko mówiąc — tak, to ma znaczenie. Administratorzy sieci z różnych powodów lubią grupować użytkowników w sieciach LAN w sposób odzwiercie­dlający strukturę organizacyjną, a nie fizyczny rozkład budynku. Jednym z powodów jest bezpieczeń­stwo. Każdą kartę sieciową można przełączyć w tryb nasłuchu, tak że będzie kopiować całość ruchu w sieci. Wiele działów, takie jak badawcze, patentowe i finansowe, używa informacji, których nie chce wypuszczać poza swój obręb. W takich sytuacjach umieszczenie wszystkich użytkowników danego działu w jednej sieci lokalnej i niedopuszczenie, by jakiekolwiek dane wychodziły poza tę sieć, ma sens. Kierownictwo nie życzy sobie wyjaśnień, że taka struktura będzie możliwa tylko wtedy, gdy wszyscy pracownicy każdego działu będą pracować w sąsiednich pomieszczeniach bez intruzów.

Drugim powodem jest obciążenie sieci. Niektóre LAN są bardziej intensywnie wykorzystywane od innych i czasem warto je odseparować. Na przykład, jeśli pracownicy z działu badań prowadzą różne ciekawe eksperymenty, które czasem wymykają się spod kontroli i zapychają LAN, to dział finansowy może nie chcieć pomagać im przez oddanie części własnego pasma.

Trzecim powodem są rozgłoszenia. Wiele sieci lokalnych obsługuje rozgłoszenia i wiele proto­kołów wyższych warstw korzysta z tej funkcji. Na przykład, gdy użytkownik chce wysłać pakiet pod adres IP x, to skąd może wiedzieć, jaki adres MAC umieścić w ramce? Zajmiemy się tą kwestią w rozdziale 5., lecz krótko mówiąc, host rozgłasza ramkę z pytaniem: „Kto jest właścicielem adre­su IP x?" i czeka na odpowiedź. Zastosowań rozgłoszeń jest o wiele więcej. W miarę dołączania ko­lejnych sieci LAN liczba rozgłoszeń docierających do każdego komputera rośnie liniowo z liczbą komputerów.

Z rozgłoszeniami wiąże się jeszcze ten problem, że od czasu do czasu karta sieciowa zawodzi i zaczyna generować niekończący się potok ramek rozgłoszeniowych. Wynikiem takiej „burzy trans­misyjnej" (broadcast storm) jest (1) zajęcie całej zdolności przepustowej LAN przez te ramki i (2) sparaliżowanie wszystkich komputerów w połączonych ze sobą sieciach przez przetwarzanie i od­rzucanie wszystkich rozgłaszanych ramek.

Na pierwszy rzut oka może się wydawać, że zasięg burzy transmisyjnej da się ograniczyć przez separowanie LAN mostami i przełącznikami, lecz jeśli naszym celem jest osiągnięcie przezroczy­stości sieci (tzn. komputer można przenieść do innej LAN po drugiej stronie mostu i nikt tego nie zauważy), to mosty muszą przekazywać ramki rozgłoszeńiowe.

Wiemy już, dlaczego firmy mogą chcieć korzystać z wielu sieci lokalnych o ograniczonym zasięgu, więc wróćmy do problemu separacji topologii logicznej od fizycznej. Załóżmy, że użyt­kownik zostaje przeniesiony z jednego działu firmy do innego bez zmiany miejsca pracy lub zmienia miejsce pracy bez zmiany działu. W przypadku okablowania z koncentratorami oznacza to, że administrator sieci musi pójść do szafki kablowej, wyciągnąć wtyczkę komputera tego użyt­kownika z jednego koncentratora i wpiąć do drugiego.

W wielu firmach zmiany organizacyjne odbywają się cały czas, co oznacza, że administratorzy systemów spędzają mnóstwo czasu na wyciąganiu wtyczek i wkładaniu ich w inne miejsca. Poza tym w pewnych przypadkach zmiana bywa w ogóle niemożliwa, ponieważ skrętka z komputera użytkownika jest za daleko od właściwego koncentratora (np. w innym budynku).

W odpowiedzi na żądanie większej elastyczności producenci sieci komputerowych zaczęli pracować nad sposobem całkowicie programowych zmian „okablowania". Wynikiem tych prac była wirtualna sieć LAN (VLAN — Virtual LAN), która nawet została przyjęta przez komitet 802 jako standard. W chwili obecnej idea ta jest wdrażana w wielu organizacjach. Przyjrzyjmy się jej pokrótce. Dodatkowe informacje o VLAN przedstawili Breyer i Riley (1999) oraz Seifert (2000).

Wirtualne sieci lokalne opierają się na specjalnie zaprojektowanych z myślą o nich przełączni­kach, aczkolwiek na peryferiach mogą zawierać koncentratory, jak na rysunku 4.44. Aby zestawić sieć opartą na VLAN, administrator sieci decyduje, ile wirtualnych sieci lokalnych będzie używanych, które komputery będą należeć do konkretnych VLAN i jakie będą nazwy tych sieci. Często wirtualne sieci lokalne są oznaczane (nieformalnie) kolorami, ponieważ umożliwia to drukowanie koloro­wych schematów przedstawiających fizyczne rozmieszczenie komputerów, na których komputery należące do czerwonej VLAN są oznaczone na czerwono, należące do zielonej na zielono i tak dalej. W ten sposób jeden schemat pozwala przedstawić jednocześnie układ fizyczny i logiczny. Jako przykład rozważmy cztery sieci lokalne z rysunku 4.45 (a), gdzie osiem komputerów należy do szarej VLAN (Sz), a siedem do białej VLAN (Bi). Cztery fizyczne sieci LAN są połączone dwoma mostami, BI i B2. Gdyby było tu używane scentralizowane okablowanie skrętką, na ry­sunku mogłyby jeszcze znajdować się cztery koncentratory, lecz logicznie kabel wielogałęziowy i koncentrator są równoważne. Taki sposób narysowania sieci upraszcza trochę rysunek. Poza tym pojęcie „most" jest obecnie używane głównie wtedy, gdy do każdego portu podłączony jest więcej niż jeden komputer, jak w tym przykładzie, lecz poza tym pojęcia „most" i „przełącznik" można stosować zamiennie. Rysunek 4.45 (b) przedstawia te same komputery i wirtualne sieci LAN, lecz tym razem wykorzystujące przełączniki z jednym komputerem na każdym porcie.

RYSUNEK 4.45.

(a) Cztery fizyczne sieci LAN zorganizowane w dwie VLAN, szarą i białą z użyciem dwóch mostów.

(b) Te same15 komputerów zorganizowanych w dwie VLAN przez przełączniki

Aby wirtualna sieć lokalna mogła działać prawidłowo, należy zdefiniować tablice konfiguracyj­ne w mostach i przełącznikach. Tablice te informują, które VLAN są dostępne przez które porty (przełączniki). Gdy ramka przychodzi, powiedzmy, z szarej VLAN, musi zostać przekazana do wszystkich portów oznaczonych Sz. Dotyczy to zwykłego ruchu (transmisji pojedynczych), jak również transmisji grupowych i rozgłoszeń.

Zwróćmy uwagę, że port może być oznaczony kilkoma kolorami VLAN. Zobaczymy to wyraź­niej na rysunku 4.45 (a). Załóżmy, że komputer - rozgłasza ramkę. Most BI odbierają i stwierdza, że pochodzi z komputera w szarej VLAN, więc przekazuje ramkę na wszystkie porty oznaczone Sz (z wyjątkiem tego, na który przyszła). Ponieważ BI ma tylko dwa inne porty i oba są oznaczone Sz, ramka zostaje wysłana na oba.

W B2 sytuacja wygląda inaczej. Tutaj most wie, że w LAN 4 nie ma żadnych szarych kompute­rów, więc do tej sieci ramka nie jest przekazywana. Idzie tylko do LAN 2. Gdyby jeden z użytkowników LAN 4 zmienił dział i został przeniesiony do szarej VLAN, wówczas trzeba byłoby zaktualizować tablice w B2, aby oznaczyć ten port SzBi zamiast Bi. Gdyby komputer F przeszedł do szarej sieci, port do LAN 2 należałoby zmienić na Sz zamiast SzBi.

Wyobraźmy sobie teraz, że wszystkie komputery w LAN 2 i LAN 4 stają się szare. Wówczas nie tylko porty B2 do LAN 2 i LAN 4 zostaną oznaczone Sz, lecz port z BI do B2 również zmieni oznaczenie z SzBi na Sz, ponieważ białych ramek docierających do BI z LAN 1 i 3 nie trzeba już przekazywać do B2. Na rysunku 4.45 (b) obowiązuje ta sama sytuacja, z tą różnicą, że wszystkie porty wychodzące do pojedynczych komputerów są oznaczone pojedynczym kolorem, ponieważ jest tu tylko jedna wirtualna sieć lokalna.

Do tej pory zakładaliśmy, że mosty i przełączniki skądś wiedzą, jaki kolor ma przychodząc; ramka. Skąd to wiedzą? W użyciu są trzy metody:

1. Do każdego portu przypisywany jest kolor VLAN.

2. Każdy adres MAC otrzymuje kolor VLAN.

3. Każdy adres protokołu warstwy 3. lub IP otrzymuje kolor VLAN.

W pierwszej metodzie każdy port jest oznaczony kolorem VLAN. Ta metoda działa jednak tylko wtedy, gdy wszystkie komputery na jednym porcie należą do tej samej wirtualnej sieci lokalnej Na rysunku 4.45 (a) dla BI ta właściwość obowiązuje dla portu do LAN 3, lecz nie do LAN 1.

W drugiej metodzie most lub przełącznik zawiera tablicę, w której 48-bitowy adres MAC każ­dego przyłączonego do niego komputera jest skojarzony z VLAN, do której komputer należy. W tych warunkach można mieszać wirtualne sieci lokalne w fizycznej LAN, jak w LAN 1 z rysunku 4.45 (a) Gdy przychodzi ramka, most lub przełącznik musi jedynie wydobyć adres MAC i znaleźć go w ta­blicy, aby sprawdzić, z której VLAN pochodzi ta ramka.

W trzeciej metodzie most lub przełącznik sprawdza pole ładunku użytecznego ramki, na przy­kład aby zaklasyfikować wszystkie komputery IP jako należące do jednej VLAN, a wszystkie kom­putery Apple Talk jako należące do innej. W pierwszym typie adres IP może też służyć do identyfikacji komputera. Ta strategia jest najbardziej przydatna, gdy wiele komputerów to notebooki, które mogą być zadokowane w dowolnym z kilku dostępnych miejsc. Ponieważ każda stacja dokująca ma wła­sny adres MAC, to wiedza, która stacja została użyta, nie mówi nic o VLAN, w której jest notebook.

Jedyny problem z tym podejściem polega na tym, że narusza najbardziej fundamentalną regułę sieci komputerowych — niezależność warstw. Warstwy łącza danych nie powinna interesować zawartość pola ładunku użytecznego. Warstwa ta nie powinna sprawdzać ładunku, a już na pewno nie na podstawie zawartości podejmować decyzji. Konsekwencją użycia takiego podejścia jest to, że zmiana w protokole warstwy 3. (na przykład modernizacja z IPv4 do IPv6) spowoduje nagłe prze­stanie działania przełączników. Niestety, na rynku dostępne są przełączniki działające w ten sposób.

Oczywiście nie ma nic złego w rutingu opartym na adresach IP — niemal całość rozdziału 5. poświęcona jest rutingowi — lecz mieszanie warstw prosi się o kłopoty. Producent może zbagateli­zować ten argument mówiąc, że jego przełączniki rozumieją zarówno IPv4, jak i IPv6, więc wszyst­ko jest w porządku. Lecz co stanie się, gdy pojawi się IPv7? Producent prawdopodobnie powie: Trzeba będzie kupić nowy przełącznik, czy to tak źle?

Standard IEEE 802.1Q

Po krótkim zastanowieniu możemy dojść do wniosku, że tak naprawdę liczy się VLAN samej ramki, a nie komputera wysyłającego ramkę. Gdyby istniała jakaś metoda identyfikacji VLAN w nagłówku ramki, to nie istniałaby już potrzeba sprawdzania ładunku użytecznego. W nowych LAN, takich jak 802.11 lub 802.16, łatwo byłoby dodać pole VLAN do nagłówka. W rzeczy samej pole Identyfikator połączenia w 802.16 przypomina nieco charakterem identyfikator VLAN. Lecz co mamy zrobić z Ethernetem, który jest dominującym typem LAN i nie ma w zapasie żadnego pola nagłówka cze­kającego na identyfikator VLAN?

Komitet IEEE 802 został uszczęśliwiony tym problemem w roku 1995. Po długich dyskusjach zrobił coś nie do pomyślenia i zmienił nagłówek Ethernet. Nowy format został opublikowany w stan­dardzie IEEE 802.1Q, wydanym w roku 1998. Nowy format zawiera znacznik VLAN, z którym zapoznamy się za chwilę. To oczywiste, że zmiana czegoś tak mocno zakorzenionego jest niezupeł­nie trywialna. Nasuwa się kilka pytań:

1. Czy musimy wyrzucić na śmietnik kilka milionów istniejących kart Ethernet?

2. Jeśli nie, to kto generuje nowe pola?

3. Co stanie się z ramkami, które już mają maksymalną wielkość?

Oczywiście komitet 802 zdawał sobie aż za dobrze sprawę z tych problemów i musiał wymyślić ja­kieś rozwiązanie, co też uczynił.

Kluczem do rozwiązania jest uświadomienie sobie, że pola VLA1M są faktycznie używane tylko przez mosty i przełączniki, a nie przez komputery użytkowników. Wobec tego na rysunku 4.45 nie muszą koniecznie być obecne w liniach biegnących do stacji końcowych, pod warunkiem, że znajdą się w liniach pomiędzy mostami i przełącznikami. Wobec tego, aby można było korzystać z VLAN, mosty i przełączniki muszą obsługiwać wirtualne sieci lokalne, lecz ten wymóg obowiązywał już wcześniej. Teraz wprowadzamy tylko dodatkowy wymóg, aby rozpoznawały standard 802.1Q, co robiąjuż nowe urządzenia.

Czy trzeba wyrzucać istniejące karty Ethernet? Nie. Pamiętajmy, że komitet 802.3 nie dał nawet rady przekonać użytkowników do zmiany pola Typ na pole Długość. Możemy wyobrazić sobie re­akcję na ogłoszenie, że wszystkie istniejące karty Ethernet należy wyrzucić. Jednakże można mieć nadzieję, że nowe karty Ethernet pojawiające się na rynku będą zgodne z 802.1Q i będą poprawnie wypełniać pola VLAN.

Jeśli więc nadawca ramki nie generuje pól VLAN, to kto to robi? Odpowiedź brzmi: dodaje je pierwszy most lub przełącznik obsługujący VLAN, który ma kontakt z ramką, a ostatni na trasie usuwa pola. Lecz skąd wie, która ramka należy do którego VLAN? No cóż, pierwszy most lub przełącznik może przydzielić numer VLAN do portu, sprawdzić adres MAC lub (uchowaj Boże!) sprawdzić ładunek użyteczny. Dopóki wszystkie karty Ethernet nie będą zgodne z 802.1Q, jeste­śmy w zasadzie w punkcie wyjścia. Prawdziwa nadzieja w tym, że wszystkie karty Gigabit Ethernet od początku będą zgodne z 802.1Q i że w miarę modernizacji sieci do standardu Gigabit Ethernet 802.1Q będzie wprowadzany automatycznie. A jeśli idzie o problem z ramkami dłuższymi od 1518 bajtów, 802.1Q podniósł limit do 1522 bajtów.

W okresie przejściowym w wielu instalacjach będą współistnieć starsze urządzenia (zwykle klasyczny lub Fast Ethernet) nierozpoznające VLAN i inne (zwykle Gigabit Ethernet), obsłu­gujące VLAN. Sytuację tę ilustruje rysunek 4.46, na którym zacieniowane symbole obsługują VLAN, a puste nie. Dla uproszczenia zakładamy, że wszystkie przełączniki obsługują VLAN. W przeciw­nym razie pierwszy przełącznik z obsługą VLAN może dodawać znaczniki na podstawie adre­sów MAC lub IP.

RYSUNEK 4.46. Przejście ze starszych wersji Ethernet do obsługi VLAN. Symbole zacieniowane obsługują VLAN, puste nie rozpoznają tego standardu

Na tym rysunku karty Ethernet obsługujące VLAN generują bezpośrednio ramki ze znacznikami (tzn. 802.1Q), a dalsza komutacja wykorzystuje te znaczniki. Do celu komutacji przełączniki mu­szą wiedzieć, które VLAN są osiągalne na każdym porcie, tak jak uprzednio. Wiedza, że ramka należy do szarej VLAN nie pomaga zbyt wiele, dopóki przełącznik nie dowie się, które porty łączą się z komputerami w szarej VLAN. Wobec tego przełącznik potrzebuje tablicy indeksowanej po VLAN informującej, których portów ma używać i czy obsługują VLAN czy też są starszego typu.

Gdy starszy PC wysyła ramkę do przełącznika obsługującego VLAN, ten buduje nową ramkę ze znacznikiem, opierając się na wiedzy o VLAN nadawcy (używając portu, adresu MAC lub adresu IP). Od tej chwili przestaje być ważne, czy nadawca był starszym urządzeniem. Analogicznie przełącz­nik, który musi dostarczyć ramkę ze znacznikiem do starszego komputera, musi ponownie sfor­matować ramkę zgodnie ze starszym formatem przed jej doręczeniem.

Przyjrzyjmy się teraz formatowi ramki 802.1Q. Przedstawia go rysunek 4.47. Jedyna zmiana polega na dodaniu pary dwubajtowych pól. Pierwsze zawiera ID protokołu VLAN i zawsze ma war­tość 0x8100. Ponieważ ta liczba jest większa niż 1500, wszystkie karty Ethernet interpretują ją jako typ, a nie długość. Co zrobiłaby z taką ramką starsza karta sieciowa, nie wiadomo, ponieważ ramki te^ao typu nie są wysyłane do starszych kart.

RYSUNEK 4.47. Formaty ramek Ethernet 802.3 i 802.1Q

Drugie dwubajtowe pole zawiera trzy podpola. Najważniejsze z nich zawiera i dentyfi kator VLAN i zajmuje 12 najmłodszych bitów. O to w tym wszystkim chodzi — do której wirtualnej sieci lokal­nej należy ramka? Trzybitowe pole Priorytet nie ma nic wspólnego z VLAN, lecz ponieważ zmiana nagłówka Ethernet to wydarzenie dekady, które zajęło trzy lata i zaangażowało setkę ludzi, dlaczego przy okazji nie dodać innych przydatnych rzeczy? Pole to umożliwia rozróżnianie krytycz­nego i niekrytycznego ruchu w czasie rzeczywistym oraz ruchu niewymagającego czasu rzeczywi­stego, aby pozwolić na świadczenie w Ethernecie wyższej jakości usług. Potrzebne jest do przesyła­nia głosu przez Ethernet (aczkolwiek uczciwość każe wspomnieć, że IP od ćwierćwiecza zawiera podobne pole i nikt go nigdy nie używał).

Ostatni bit, cfi (Canonical Format Indicator — wskaźnik postaci kanonicznej), powinien na­zywać się cei (Corporate Ego Indicator — wskaźnik ego korporacji). Początkowo miał rozróż­niać adresy MAC z rosnącym i malejącym porządkiem bitów, lecz to zgubiło się wśród innych kon­trowersji. W tej chwili jego obecność oznacza, że ładunkiem użytecznym jest „zamrożona" ramka 802.5, która ma nadzieję znaleźć inną sieć LAN 802.5 u celu, będąc przenoszona między nimi za pomocą Ethernetu. Nie ma to oczywiście niczego wspólnego z VLAN, lecz polityka komitetów standaryzacji przypomina klasyczną politykę: ty zagłosujesz na mój bit, ja zagłosuję na twój bit.

Jak już wspomnieliśmy, gdy ramka ze znacznikiem dociera do przełącznika obsługującego VLAN, Przełącznik używa ID VLAN jako indeksu do tablicy, aby ustalić, na który port ją wysłać. Lecz skąd bierze się ta tablica? Jeśli jest tworzona ręcznie, to wróciliśmy do punktu wyjściowego — ręcznej konfiguracji mostów. Uroda przezroczystych mostów polega na tym, że są plug-and-play i nie wyma­gają żadnej ręcznej konfiguracji. Szkoda byłoby utracić tę właściwość. Na szczęście mosty obsługujące VLAN potrafią konfigurować się automatycznie, obserwując przechodzące przez nie znaczniki.

Jeśli ramka oznaczona jako VLAN 4 przyjdzie na port 3, to ewidentnie jakiś komputer na porcie 3 należy do VLAN 4. Standard 802.1Q opisuje, jak dynamicznie tworzyć tablice, głównie odwołując się do odpowiednich fragmentów algorytmu Perlmana, który został znormalizowany w 802.1 D.

Zanim zamkniemy tematykę rutingu VLAN, warto poczynić ostatnie spostrzeżenie. Wielu ludzi ze świata Internetu i Ethernetu fanatycznie faworyzuje sieci bezpołączeniowe i gwałtownie sprzeci­wia się czemukolwiek, co zatrąca połączeniami w warstwie łącza danych lub sieciowej. A jednak wirtualne sieci lokalne wprowadzają coś, co zaskakująco przypomina połączenia. Aby właściwie wykorzystać VLAN, każda ramka niesie nowy specjalny identyfikator, który jest używany jako indeks tablicy wewnątrz przełącznika, aby ustalić, gdzie ramka ma zostać wysłana. W sieciach bezpołączeniowych do rutingu używany jest adres docelowy, a nie jakiś identyfikator połączenia. Więcej takich przykładów powolnego dążenia do połączeń zobaczymy w rozdziale 5.

4.8. Podsumowanie

W części typów sieci jeden kanał jest używany do całej komunikacji. W takich sieciach podstawo­wym problemem projektowym jest przyznawanie dostępu do kanału rywalizującym stacjom, które chcą z niego skorzystać. Opracowano wiele algorytmów przydzielania kanału. Zestawienie niektó­rych z najważniejszych metod przydzielania kanału zawiera tabela 4.5.

Najprostsze metody przydzielania to FDM i TDM. Są one skuteczne, gdy liczba stacji jest niewielka i stała, a ruch odbywa się w sposób ciągły. Obie metody są powszechnie stosowane w takich warunkach, na przykład do podziału pasma w dalekosiężnych łączach telefonicznych.

Tam, gdzie liczba stacji jest duża i zmienna, lub gdzie ruch odbywa się impulsowo, FDM i TDM nie są najlepszymi rozwiązaniami. Jako alternatywa został zaproponowany protokół ALOHA z po­działem na szczeliny i bez. ALOHA i jego liczne odmiany i pochodne były powszechnie omawiane, analizowane i używane w rzeczywistych systemach.

Gdy istnieje możliwość wykrywania stanu kanału, stacje mogą unikać rozpoczynania transmisji podczas nadawania przez inną stację. Ta technika, zwana wykrywaniem nośnej, umożliwiła po­wstanie szeregu różnych protokołów, które mogą być używane w sieciach lokalnych i miejskich.

Dobrze znana jest klasa protokołów, która całkowicie eliminuje rywalizację, a przynajmniej znacząco ją redukuje. Odliczanie binarne całkowicie eliminuje rywalizację. Protokół adaptacyjnego przejścia przez drzewo redukuje ją przez dynamiczne dzielenie stacji na dwie rozłączne grupy, z któ­rych jedna ma prawo nadawać, a druga nie. Próbuje tak dokonać podziału, aby tylko jedna stacja gotowa do nadawania miała do tego prawo.

Bezprzewodowe sieci LAN mają własne problemy i rozwiązania. Największy kłopot sprawiają ukryte stacje, więc CSMA nie działa. Jedna klasa rozwiązań, której przykładami są MACA i MAC A W. usiłuje stymulować transmisje dookoła stacji docelowej, aby CSMA działał lepiej. Używane są też modulacja w widmie rozproszonym ze skokową zmianą kanału i rozpraszanie widma z wykorzy­staniem sekwencji bezpośredniej. IEEE 802.11 łączy CSMA i MACA W w CSMA/CA.

Ethernet jest dominującą formą sieci lokalnych. Używa CSMA/CD do przydzielania kanału. Starsze wersje wykorzystywały kabel biegnący od komputera do komputera, lecz obecnie najpo­pularniejsza jest skrętka z koncentratorami. Szybkości wzrosły z 10 Mb/s do 1 Gb/s i rosną dalej.

Bezprzewodowe sieci LAN stają się popularne, a wśród nich dominuje 802.11. Jej warstwa fi­zyczna pozwala na pięć różnych trybów transmisji, w tym podczerwień, rozmaite schematy z rozpra­szaniem widma i wielokanałowy system FDM. Może on działać ze stacją bazową w każdej komórce, lecz potrafi też pracować bez stacji bazowej. Protokół jest odmianą MACA W z wykrywaniem ka­nału wirtualnego.

Zaczynają pojawiać się bezprzewodowe sieci miejskie. Są to systemy szerokopasmowe, uży­wające radia do zastępowania ostatniego odcinka łączy telefonicznych. Używane są tu tradycyjne wąskopasmowe techniki modulacji. Jakość usług jest ważna i 802.16 definiuje jej cztery klasy (stała szybkość transmisji bitów, dwie zmienne szybkości transmisji bitów i z użyciem dostępnych możliwości).

System Bluetooth również jest bezprzewodowy, lecz jego miejsce jest głównie na biurku i służy do łączenia bez użycia kabla zestawów słuchawkowych i innych urządzeń peryferyjnych z komputerami. Jest też przeznaczony do łączenia urządzeń peryferyjnych, na przykład faksów, z telefonami mobil­nymi. Podobnie jak 802.11 używa modulacji w widmie rozproszonym ze skokową zmianą kanału w paśmie 1SM. Z uwagi na spodziewane poziomy zakłóceń w wielu środowiskach i potrzebę inte­rakcji w czasie rzeczywistym do różnych protokołów wbudowane są złożone mechanizmy współ­bieżnej korekcji błędów.

Przy tak dużej liczbie różnych typów LAN potrzebny jest sposób łączenia ich ze sobą. Do tego celu służą mosty i przełączniki. Algorytm drzewa częściowego służy do konfigurowania mostów plug-and-play. Nową techniką w łączeniu sieci LAN są wirtualne sieci lokalne, które separują lo­giczną topologię sieci LAN od ich topologii fizycznej. Wprowadzono nowy format ramek Ethernet (802.1Q) ułatwiający wprowadzanie LAN w organizacjach.