W celu zbudowania optymalnego drzewa dystrybucji multicast stosuje się protokoły routingu multicastowego, które bazują na specjalnie do tego celu przygotowanych algorytmach. Podstawowym zadaniem protokołu jest utworzenie optymalnej ścieżki pomiędzy nadawcą (lub kilkoma nadawcami) informacji, a odbiorcami danych multicastowych.
Sposób konstrukcji drzewa ma istotne znaczenie dla optymalizacji sieci pod względem wydajności. Biorąc pod uwagę złożoność algorytmu, chcemy minimalizować zużycie zasobów sprzętowych (w tym przypadku routerów lub ewentualnie zarządzalnych przełączników) i poprawiać parametry transmisji (np. zminimalizować opóźnienia w przekazach).
Algorytmy tworzenia drzew dystrybucyjnych można podzielić ze względu na sposób, w jaki te struktury są tworzone. Najprostszymi algorytmami są, tzw. prymitywne (simply-minded), następnie trochę bardziej złożone, to algorytmy tworzące drzewa od źródła (source trees) oraz kolejne, najbardziej złożone algorytmy drzewa współdzielonego (shared trees). W dystrybucji multicast zakłada się dowolną ilość odbiorców w sieci Internet, co pociąga za sobą różne uwarunkowania dotyczące rozmieszczenia odbiorców w topologii tejże sieci. Dlatego ze względu na rozproszenie odbiorców w sieci możemy wyróżnić dwa tryby:
- tryb gęsty (ang. dense mode) – kiedy to w pewnym obszarze duża liczba podsieci posiada przynajmniej po jednym członku grupy. Istnieje wtedy konieczność przekazywania pakietów do wszystkich tych podsieci.
- tryb rzadki (ang. sparse mode) – kiedy to członkowie grup znajdują się w dużym rozproszeniu.
Liczba podsieci zawierających członków grup multicastowych w porównaniu z całkowitą ich liczbą jest znikoma. Poniżej zostało opisanych kilka algorytmów tworzenia drzew dystrybucyjnych.
Zalewanie
Algorytm zalewania (flooding) nazywany rozpływowym jest najprostszą metodą rozprowadzania pakietów do odbiorców. Jest to algorytm statyczny. W technice tej, gdy do routera dotrze pakiet zaadresowany do grupy multicastowej, jest on wysyłany na wszystkie interfejsy oprócz tego, z którego przyszedł. Ten sam pakiet, który po raz kolejny raz trafia do routera, jest odrzucany. Algorytm zalewania jest bardzo prosty w implementacji. Routery nie muszą pamiętać tablic routingu, a jedynie monitorować pakiety napływające do routera.
Jednak powoduje to nieefektywne użycie zasobów sprzętowych routera. W przypadku dużych sieci algorytm ten generuje ogromne liczby pakietów, które trzeba ograniczać przez mechanizm postarzania pakietów (TTL). Ponadto jest on słabo skalowalny, więc jedynym rozsądnym zastosowaniem mogą być tutaj małe sieci bez większych wymagań.
Drzewo rozpinające
Algorytm drzewa rozpinającego (Spanning Tree) jest bardziej efektywnym algorytmem niż zalewanie (ang. flooding). Jak mówi nazwa, polega on na wyznaczeniu drzewa rozpinającego pewnej określonej części sieci zawierającej nadawcę i odbiorców w taki sposób, aby całkowity koszt drzewa był minimalny (Minimum Spanning Tree Algorithm). Pomiędzy każdą parą routerów istnieje jedynie jedno aktywne połączenie, dlatego w drzewie wytworzonym za pomocą tego algorytmu istnieje minimalna liczba połączeń. Pakiety są duplikowane jedynie wtedy, gdy dochodzi do rozwidlenia dróg dystrybucyjnych, co eliminuje powstawanie pętli. Dlatego nie jest potrzebne monitorowanie pakietów przepływających przez router. W momencie, kiedy router otrzymuje pakiet, przekazuje go do wszystkich sąsiadujących routerów, z wyjątkiem tego, od którego pakiet otrzymał. Siatka połączeń stworzona według algorytmu rozpinającego dla routera A, została przedstawiona na poniższym rysunku.
Rysunek 1. Wszystkie połączenia danej sieci (a) oraz drzewo rozpinające dla routera A (b)
Algorytm ten jest dość wydajny oraz łatwy w implementacji. Nie jest zalecany w przypadku większych sieci, ponieważ ruch generowany jest duży i może przekraczać w pewnych przypadkach przepustowość tych sieci. W ten sposób mogą powstawać częste kolizje. Więc wniosek nasuwa się sam – algorytm ten można stosować w przypadku mniejszych sieci.
Algorytmy tworzenia drzewa od źródła
Intuicyjnie rzecz przyjmując, najlepszą z punku widzenia sieci ścieżką jest najkrótsza ścieżka biegnąca od źródła do odbiorców. W przypadku multicastu jest to oczywiście zestaw ścieżek biegnących do odbiorców tworzących drzewo od źródła (source trees). Źródło jest tutaj korzeniem (root.) drzewa. Algorytm ten nie tworzy drzewa dystrybucji opinającego całą podsieć, a tylko strukturę drzewa dla danego źródła i odbiorców informacji z niej wysyłanych. Zgodnie z założeniem multicastu jeden host może być członkiem wielu takich drzew. Algorytm tworzenia drzewa od źródła jest bardziej efektywny od wcześniej opisanych, poza tym ma mniejsze wymagania co do zasobów sprzętowych routerów oraz przepustowości sieci. Poniżej zostaną opisane algorytmy należące do tej grupy.
Algorytm RPB (Reverse-Path Broadcasting)
Algorytm RPB (Reverse-Path Broadcasting) można określić jako algorytm wstecznej drogi. Jest to najprostszy z algorytmów typu Source Trees Algorithm. Działanie jego polega na określaniu drogi jaką przebył pakiet od źródła do routera, który to dokonuje oceny. Jeżeli jest to najkrótsza możliwa droga, która łączy router ze źródłem, to pakiet przekazywany jest do wszystkich sąsiednich routerów, za wyjątkiem tego od którego został dostarczony. Ścieżki biegnące w kierunku od nadawcy od routera, tzn. te, przez które pakiety napływają do routera, określane są jako rodzic (parent). Natomiast ścieżki, którymi wypływają pakiety w kierunku do odbiorców określane są jako dziecko (child). Więc każdy router ma jedną ścieżkę typu rodzic, która jest częścią najkrótszej drogi od źródła. Z kolei liczba ścieżek typu dziecko równa jest liczbie sąsiadów danego routera.
Algorytm RPB cechuje wydajność i łatwość implementacji. Dane od źródła do odbiorców przekazywane są różnymi drogami, co zapobiega koncentracji ruchu w niektórych obszarach sieci. Algorytm ten stosowany jest w przypadku protokołów „stanu łącza”. Ponieważ routery działające w oparciu o takie protokoły dysponują danymi na temat topologii sieci, w obrębie danej domeny, mogą w prosty sposób oceniać długości dróg połączeniowych. Jednak RPB ma istotną wadę. Transmitowane dane mogą być przekazywane do podsieci, w obrębię których nie znajduje się żaden aktywny członek grupy.
Rysunek 2. Drzewo przedstawiające działanie algorytmu RPB
Na rysunku 2 został pokazany sposób działania algorytmu RPB. Pakiety od źródła wędrują do routera A, gdzie poprzez połączenie 1 przekazywane są do routera B. Ten z kolei przekazuje je do wszystkich sąsiadujących routerów, ale tylko w przypadku, gdy połączenia, którymi biegną pakiety, są połączeniami typu rodzic. W tym przypadku będą to routery D i E. Router C został pominięty, gdyż połączenie 3 nie jest dla niego drogą typu rodzic. Dane dla niego napłyną drogą oznaczoną numerem 3, ponieważ jest to jego połączenie typu rodzic.
Algorytm TRPB
Algorytm TRPB (Truncated Reverse-Path Broadcasting) jest udoskonaloną wersją algorytmu RPB. W trakcie rozsyłania pakietów uwzględnia on informacje na temat członkowstwa w grupach multicastowych, przekazywanych przez protokół IGMP. Dlatego, gdy w topologii drzewa wystąpi sytuacja, w której pojawi się router nie obsługujący w swojej podsieci żadnych członków jakiejkolwiek grupy oraz gdy router ten nie jest routerem pośredniczącym (tzn. przekazującym dane multicast do innych routerów), wtedy dane multicast nie będą do niego wysyłane. Algorytm ten likwiduje niepotrzebny ruch w podsieciach granicznych, w których nie ma członków grup multicast. Ale też ma wadę, ponieważ nie bierze pod uwagę członkowstwa w grupach w obrębie podsieci pośrednich. Tę niedogodność likwiduje kolejny omawiany algorytm.
Algorytm RPM
Algorytm RPM (Reverse-Path Multicasting) tworzy drzewo dystrybucyjne, używając jedynie podsieci zawierających aktywnych członków grup multicast oraz podsieci i routery, które znajdują się po drodze do podsieci zawierających członków tychże grup. Ruch do sieci, w których nie ma aktywnych członków jest blokowany poprzez odcinanie liścia. Dodatkowo ruch do routerów w kierunku nadawcy może być także blokowany przez odcinanie gałęzi. Na rysunku 3 przedstawiono działanie algorytmu RPM.
Rysunek 3. Drzewo przedstawiające działanie algorytmu RPM
Pierwszy pakiet jest wysyłany do wszystkich interfejsów z wyjątkiem źródła. Transmisja ta jest przeprowadzana na bazie algorytmu TRPB. Dzięki temu każdy z routerów w sieci otrzyma wiadomość, przez co z kolei każdy aktywny członek grupy oczekujący na dane przyłączony do takiego routera otrzyma tę wiadomość. Jeżeli żadna z podsieci podłączona do routera nie zawiera ani jednego aktywnego członka, wtedy router ten wysyła wiadomość zwrotną z żądaniem odcięcia go (prune) od struktury drzewa dystrybucyjnego. Wiadomość ta przekazywana jest przez interfejs, z którego napływają pakiety, czyli poprzez łącze „rodzica”. Informacja ta kierowana jest tylko do poprzedniego routera po drodze do źródła, dlatego pakiet przekazywany jest ze wskaźnikiem TTL=1.
Do routera, który wysłał wiadomość z żądaniem odcięcia przestają napływać kolejne porcje danych. Z kolei router, do którego napłynęła informacja o odcięciu z routera podrzędnego, przechowuje tę informacje w swojej pamięci. Może on także wysłać informacje o odcięciu do routera nadrzędnego, kiedy to stwierdzi, że w jego podsieciach nie ma już aktywnych członków grup.
Operacje takie pozwalają optymalizować drzewo poprzez odcinanie gałęzi. Ponieważ liczba członków grup oraz samych grup zmienia się dynamicznie, dlatego drzewo dystrybucyjne co pewien czas musi być poddawane uaktualnieniu. Odbywa się to poprzez usunięcie z pamięci routerów informacji o odciętych gałęziach i przesłaniu kolejnych pakietów do wszystkich sąsiadujących routerów.
Wynikają z tego dwie wady tego algorytmu. Po pierwsze relatywnie duże zużycie pamięci routerów, ponieważ routery muszą przechowywać informację o odciętych gałęziach i wraz ze zmianami topologii sieci uaktualniać te dane. Po drugie konieczność wysyłania co pewien czas pakietów do każdego z routerów, nawet jeśli w jego podsieciach nie zawiera się żaden członek grupy multicast. Wady te czynią ten algorytm nie skalowalnym. Dlatego powstał algorytm współdzielonego drzewa, który radzi sobie z problemem skalowalności.
Technika współdzielonego drzewa
Algorytm tworzenia drzewa współdzielonego (Shared Tree) jest techniką odmienną niż poprzednio omawiane algorytmy. Różnica polega na tym, ze zamiast tworzyć osobne drzewo dystrybucyjne dla każdego źródła, algorytm współdzielonego drzewa buduje jedna taką, wspólna strukturę dla danej grupy multicastowej. Przykład drzewa dystrybucyjnego typu Shared Tree został przedstawione na rysunku 4.
Rysunek 4. Drzewo dystrybucyjne typu Shared Tree
W metodzie tej można znaleźć pewne podobieństwa do algorytmu drzewa rozpinającego, jednakże umożliwia ona tworzenie osobnych drzew dla każdej grupy hostów, więc jest lepiej dostosowywana, czyli efektywniejsza. Każdy host, chcący przyłączyć się do danej grupy multicast, musi dołączyć się do określonego współdzielonego drzewa, za pośrednictwem którego będzie otrzymywał pakiety z danymi. Wszystkie dane są przenoszone za pośrednictwem takiej struktury niezależnie od tego, jakie jest ich źródło.
Jedną z głównych zalet tego algorytmu jest bardzo efektywne wykorzystywanie zasobów sprzętowych routerów. Od routerów wymaga się jedynie przechowywania danych konfiguracyjnych danej grupy multicast znajdującej się w zasięgu działania routera. Nie potrzebne jest tutaj przechowywanie informacji na temat źródła. Kolejną zaletą jest oszczędność dostępnej przepustowości. Dane docierają jedynie do aktywnych odbiorców grup multicastowych.
Pomimo tych wszystkich zalet, algorytm ten ma także istotna wadę. Dla transmisji z różnych źródeł używane jest to samo drzewo dystrybucji, dlatego też przy niesprzyjających warunkach może dojść do zbyt dużej koncentracji ruchu w którymś z połączeń. To z kolei może doprowadzić do przestojów, a co za tym idzie opóźnień, a w krytycznych sytuacjach nawet do błędów w transmisji.
Wszystkie omówione algorytmy były podstawą do stworzenia pewnych protokołów routingu stosowanych w transmisji rozgłoszeniowej. Protokoły te zostaną omówione w następnych artykułach.
Autor: Jacek Kajdasz, www.multicast.pl
