P

AŃSTWOWA

W

YŻSZA

S

ZKOŁA

Z

AWODOWA W

T

ARNOWIE

I

NSTYTUT

P

OLITECHNICZNY

KIERUNEK

:

I

NFORMATYKA

ROK

:

IV

Ćwiczenie nr 2

Sieć Aloha

Bezprzewodowe systemy transmisji danych

Laboratoria

2

Celem ćwiczenia jest zapoznanie się z protokołem wielodostępu do medium radiowego o

nazwie Aloha. Dodatkowo student powinien sobie utrwalić wiadomości związane ze sztuką

symulacji komputerowej z użyciem oprogramowania COMNET. Po wykonaniu ćwiczenia

student powinien wiedzieć:

•

Co to jest sieć Aloha

•

Jak działa protokół Aloha

•

Jakie są cechy charakterystyczne protokołu Aloha

•

Kiedy jest/była używana ta metoda dostępu do medium

•

Jak zbudować i przeanalizować sieć opartą na protokole Aloha

1. Wstęp teoretyczny

ALOHA – jeden z algorytmów dostępu wielokrotnego do kanału. Opracowany w latach 70.

XX w. na University of Hawaii m.in. przez Normana Abramsona. Początkowo używany do

naziemnej komunikacji radiowej z czasem znalazł zastosowanie we wszystkich systemach, w

których niekoordynowani użytkownicy korzystają z jednego kanału (tzw. systemy

rywalizacyjne).

Podstawową ideą systemu ALOHA jest wysyłanie przez nadajnik danych zawsze, gdy tylko

się pojawią. Gdy ramka dotrze do celu wysyłana jest kolejna. Gdy nastąpi kolizja, nadajnik

odczekuje losowy czas i wysyła ją ponownie. Losowość jest tu szczególnie ważna, gdyż w

przeciwnym razie te same ramki wciąż by ze sobą kolidowały.

3

Wydajność tego systemu, a co za tym idzie - wykorzystanie kanału są niewielkie. Pomimo

swojej prostoty i małej wydajności szczelinowy protokół ALOHA znalazł zastosowanie nie

tylko w kilku wczesnych eksperymentach. Przypomniano sobie o nim w chwili wynalezienia

dostępu do Internetu przez sieci telewizji kablowych.

Podsumowując:

•

Wszyscy użytkownicy używają jednego wspólnego kanału transmisyjnego. Każdy

użytkownik wysyła swoje pakiety bez jakiejkolwiek synchronizacji z innymi

użytkownikami kanału.

•

Nałożenie sie jakiejkolwiek części jednego pakietu na inny pakiet w czasie powoduje

kolizje.

•

Każdy pakiet jest zabezpieczony przy pomocy kodu umożliwiającego detekcje

błędów.

•

Po wysłaniu pakietu nadawca czeka na sygnał potwierdzenia poprawności odbioru

ACK (ang. Acknowledgment) od odbiorcy.

•

Jeżeli nadawca nie otrzyma potwierdzenia ACK, wówczas uznaje nadany pakiet za

stracony i wysyła go ponownie, po losowo ustalonym czasie.

Prawdopodobieństwo wystąpienia kolizji w takim systemie będzie małe, jeżeli liczba

użytkowników wspólnego kanału transmisyjnego będzie mała oraz ruch generowany przez

każdego z nich nie będzie zbyt duży. Wzrost liczby użytkowników będzie powodował coraz

częstsze nakładanie sie na siebie pakietów a tym samym wzrost prawdopodobieństwa

wystąpienia kolizji.

Wydajność protokołu Aloha została przedstawiona na kolejnym rysunku:

4

Gdy znajdujemy sie na opadającej części wykresu i jeżeli oferowany ruch G wzrośnie z

powodu statystycznych fluktuacji, to przepływność S zmaleje. Oznacza to, że zmniejszy się

liczba poprawnych transmisji, a tym samym wzrośnie liczba kolizji i retransmisji. W

rezultacie punkt pracy systemu będzie przesuwał sie w prawo i ostatecznie przepływność S

osiągnie wartość zero.

System jest stabilny tak długo jak długo punkt pracy znajduje sie na lewo od maksymalnej

wartości na wykresie. W takim przypadku nagły wzrost ruchu G powoduje wzrost

przepływności, który z kolei przyczynia sie do zmniejszenia liczby pakietów oczekujących na

retransmisje. Jeżeli jednak losowy wzrost ruchu spowoduje przesuniecie punktu pracy

systemu na opadająca cześć krzywej wówczas ponownie będziemy mieli do czynienia z

niestabilna sytuacja. Wniosek jest wiec taki, że protokół ALOHA dla sieci o nieskończonej

liczbie terminali jest z natury niestabilny, ponieważ nawet duży wzrost retransmitowanych

pakietów, nie zmniejsza liczby nowych pakietów transmitowanych w kanale.

W przypadku skończonej liczby terminali, losowy krótkotrwały wzrost liczby kolizji

zmniejsza strumień nowych pakietów gdyż terminale retransmitujące pakiety nie generują

nowych pakietów (znajdują sie w stanie blokady). W takiej sytuacji rośnie szansa na

poprawne przesłanie retransmitowanych pakietów. Dla zapewnienia stabilności sieci

konstruktor musi opracować algorytm, według którego odbywa sie retransmisja pakietów,

które uległy kolizji. Nie wchodząc w szczegóły możemy stwierdzić, że przy skończonej

liczbie użytkowników sieć ALOHA może być stabilna dzięki odpowiedniemu doborowi

wielkości bufora w nadajniku oraz doborowi algorytmu według którego odbywa sie

retransmisja pakietów.

Więcej informacji na temat protokołu Aloha oraz jego implementacji w symulatorze

COMNET można znaleźć w instrukcji do symulatora na stronach 119-123.

2. Przebieg ćwiczenia

Zbudować sieć komputerową z użyciem protokołu Aloha (np. tak jak na przedstawionym

rysunku):

Początkowo przyjąć następujące założenia:

• W źródle wiadomości ustalić wielkość przesyłanych wiadomości na stałą wartość z

przedziału 100 - 300 bajtów.

• Kolejne wiadomości mają być generowane wg rozkładu wykładniczego Exp (10.0).

• Wiadomości są wysyłane do węzła centralnego.

• Ilość generowanych wiadomości zmieniać modyfikując liczbę komputerów w grupie

(w zakresie od 1 do n tak, aby w końcowej części wykresu uzyskać nasycenie się

łącza).

• Ustawić prędkość łącza na stałą wartość z przedziału 4800 do 9600 bitów/s.

• Retransmisja ramki powinna następować po czasie zgodnym z rozkładem

prawdopodobieństwa: Exp (1000.0,1).

• Należy przyjąć, że kanał transmisyjny jest idealny.

• Czas symulacji ustawić na 3600 sekund.

5

Zbadać:
a) wpływ wygenerowanych danych na parametr alfa
alfa = (ilość ramek odebranych/ ilość ramek wysłanych) *100%

ilość wygenerowanych danych może być zmieniana poprzez określenie liczby komputerów,

wielkość generowanych wiadomości, a także odstęp między kolejnymi ramkami IAT

(wielkość preferowana)

b) Wpływ ruchu realizowanego S na średnie opóźnienie ramki D

gdzie wielkość ruchu realizowanego S = λ* τ, λ – średnia liczba odbieranych ramek/sekundę,

τ – czas transmisji ramki i τ = N/C, N – wielkość ramki, C – przepływność kanału.

c) Zbadać wpływ niejednorodności transmitowanych ramek na wydajność kanału (np. źródło
1 generuje wiadomości o stałym rozmiarze z zakresu 10-30B, a źródło 2 o stałym rozmiarze z
zakresu 500B-700B – tak jak na poniższym rysunku)