Protokół routingu stanu łącza z mglistym widzeniem

Hazy -Sighted Link State Routing Protocol ( HSLS ) to bezprzewodowy protokół routingu sieci kratowej opracowywany przez Fundację CUWiN . Jest to algorytm umożliwiający komputerom komunikującym się za pośrednictwem radia cyfrowego w sieci kratowej przekazywanie wiadomości do komputerów znajdujących się poza zasięgiem bezpośredniego kontaktu radiowego. Jego obciążenie sieciowe jest teoretycznie optymalne, wykorzystując zarówno proaktywny, jak i reaktywny stan łącza routing w celu ograniczenia aktualizacji sieci w czasie i przestrzeni. Jego wynalazcy uważają, że jest to bardziej wydajny protokół również do trasowania sieci przewodowych. HSLS został wynaleziony przez naukowców z BBN Technologies .

Efektywność

HSLS został stworzony, aby dobrze skalować się do sieci z ponad tysiącem węzłów, aw większych sieciach zaczyna przekraczać wydajność innych algorytmów routingu. Osiąga się to za pomocą starannie zaprojektowanej równowagi między częstotliwością aktualizacji a zakresem aktualizacji w celu optymalnego propagowania informacji o stanie łącza. W przeciwieństwie do tradycyjnych metod, HSLS nie zalewa sieci informacjami o stanie łącza, aby poradzić sobie z ruchomymi węzłami, które zmieniają połączenia z resztą sieci. Co więcej, HSLS nie wymaga, aby każdy węzeł miał ten sam widok sieci.

Dlaczego protokół stanu łącza?

Algorytmy stanu łącza są teoretycznie atrakcyjne, ponieważ znajdują optymalne trasy, zmniejszając marnotrawstwo przepustowości transmisji. Twórcy HSLS twierdzą [ potrzebne źródło ] , że protokoły routingu dzielą się na trzy zasadniczo różne schematy: proaktywne (takie jak OLSR ), reaktywne (takie jak AODV ) i algorytmy, które akceptują trasy nieoptymalne. Jeśli je wykreślić, stają się one mniej wydajne, ponieważ są bardziej czysto pojedynczą strategią, a sieć się rozrasta. Wydaje się, że najlepsze algorytmy znajdują się pośrodku.

Informacje o routingu nazywane są „aktualizacją stanu łącza”. Odległość, na jaką kopiowany jest stan łącza, to „ czas życia ” i jest liczbą, ile razy może zostać skopiowany z jednego węzła do drugiego.

Mówi się, że HSLS optymalnie równoważy cechy proaktywnego, reaktywnego i suboptymalnego podejścia do routingu. Strategie te są mieszane poprzez ograniczenie aktualizacji stanu łącza w czasie i przestrzeni. Ograniczając czas życia, zmniejsza się przepustowość transmisji. Ograniczając czas, w którym proaktywna aktualizacja tras jest przesyłana, można zebrać i przesłać kilka aktualizacji jednocześnie, oszczędzając również przepustowość transmisji.

  • Algorytm stanu łącza z definicji wykorzystuje dostępne informacje do wyznaczenia najlepszej trasy, dzięki czemu trasa jest możliwie najbardziej optymalna, biorąc pod uwagę dostępne informacje.
  • Trasowanie nieoptymalne zachodzi w sposób naturalny, ponieważ odległe węzły otrzymują informacje rzadziej.
  • Minimalizowanie proaktywnych aktualizacji to trudna część. Schemat jest adaptacją dwóch algorytmów routingu o ograniczonym stanie łącza. Jeden, „Near-Sighted Link-State Routing”, jest ograniczony w przestrzeni, w liczbie węzłów przeskoków, które mogą być przesyłane informacje o routingu. Drugi algorytm routingu, „Discretized Link-State Routing”, ogranicza czasy, w których informacje o routingu mogą być przesyłane. Ponieważ optymalne tłumienie aktualizacji zarówno w przestrzeni, jak iw czasie wynosi około dwa, rezultatem jest okresowa proaktywna aktualizacja z fraktalną potęgą dwóch odległości przeskoku danych dla danych (np. odległości przeskoku 1, 2, 1, 4, 1, 2, 1, 8...).
  • Routing reaktywny występuje, ponieważ nieudana próba użycia sąsiedniego łącza powoduje wygaśnięcie następnego licznika czasu, prawdopodobnie wciągając informacje w celu znalezienia alternatywnej trasy. W przypadku każdej kolejnej awarii ponowna próba eskaluje reakcję na szerszą grupę odbiorców połączonych węzłów.

Jak to działa

Projektanci rozpoczęli dostrajanie tych elementów od zdefiniowania miary globalnej marnotrawstwa sieci. Obejmuje to odpady z przesyłania aktualizacji tras, a także odpady z nieefektywnych ścieżek transmisji. Ich dokładna definicja brzmi: „Całkowity narzut jest definiowany jako ilość przepustowości wykorzystanej powyżej minimalnej przepustowości wymaganej do przesyłania pakietów na najkrótszą odległość (w liczbie przeskoków), przy założeniu, że węzły miały natychmiastowe informacje o pełnej topologii. "

Następnie przyjęli pewne rozsądne założenia i wykorzystali optymalizację matematyczną, aby znaleźć czasy przesyłania aktualizacji stanu łącza, a także szerokość węzłów, które powinny obejmować aktualizacje stanu łącza.

Zasadniczo oba powinny rosnąć do potęgi dwóch w miarę upływu czasu. Teoretyczna optymalna liczba jest bardzo bliska dwóm, z błędem wynoszącym zaledwie 0,7%. Jest to znacznie mniej niż prawdopodobne błędy z założeń, więc dwa to całkowicie rozsądna liczba.

Lokalna aktualizacja routingu jest wymuszana po każdym zerwaniu połączenia. Jest to reaktywna część algorytmu. Lokalna aktualizacja routingu zachowuje się tak samo, jak wygaśnięcie licznika czasu.

W przeciwnym razie za każdym razem, gdy opóźnienie od ostatniej aktualizacji podwaja się, węzeł przesyła informacje o routingu, które podwajają liczbę branych pod uwagę przeskoków sieci. Trwa to do pewnego górnego limitu. Górna granica nadaje sieci globalny rozmiar i zapewnia stały maksymalny czas odpowiedzi dla sieci bez ruchomych węzłów.

Algorytm ma kilka specjalnych funkcji, aby poradzić sobie z przypadkami, które są powszechne w sieciach radiowych, takimi jak łącza jednokierunkowe i transmisja w pętli spowodowana nieaktualnymi tablicami routingu . W szczególności przekierowuje wszystkie transmisje do pobliskich węzłów za każdym razem, gdy traci połączenie z sąsiednim węzłem. Gdy to nastąpi, retransmituje również swoje sąsiedztwo. Jest to przydatne właśnie dlatego, że najcenniejsze, dalekosiężne łącza są jednocześnie najmniej niezawodne w sieci radiowej.

Zalety

Sieć ustanawia całkiem dobre trasy w czasie rzeczywistym i znacznie zmniejsza liczbę i rozmiar wiadomości wysyłanych w celu utrzymania połączenia w sieci w porównaniu z wieloma innymi protokołami. Wiele prostszych protokołów routingu typu mesh po prostu zalewa całą sieć informacjami o routingu za każdym razem, gdy zmienia się łącze.

Rzeczywisty algorytm jest dość prosty.

Informacje o routingu i transfer danych są zdecentralizowane, dlatego powinny charakteryzować się dobrą niezawodnością i wydajnością bez lokalnych punktów aktywnych.

System wymaga wydajnych węzłów z dużą ilością pamięci do obsługi tablic routingu. Na szczęście te z czasem stają się coraz tańsze.

System daje bardzo szybkie, stosunkowo dokładne odgadnięcie, czy węzeł znajduje się w sieci, ponieważ w każdym węźle obecne są kompletne, choć nieaktualne informacje o routingu. Jednak to nie to samo, co wiedzieć, czy węzeł jest w sieci. To przypuszczenie może być odpowiednie dla większości sieci taryfowych, takich jak telefonia, ale może nie być odpowiednie dla wojska lub awioniki związanej z bezpieczeństwem .

HSLS ma dobre właściwości skalowalności. Asymptotyczna skalowalność jego całkowitego narzutu jest standardowym stanem łącza, który skaluje się jako O , gdzie N to liczba węzłów w sieci.

Krytyka

Ponieważ HSLS rzadko wysyła odległe aktualizacje, węzły nie mają aktualnych informacji o tym, czy odległy węzeł jest nadal obecny. Ten problem występuje do pewnego stopnia we wszystkich protokołach stanu łącza, ponieważ baza danych stanu łącza może nadal zawierać anons z uszkodzonego węzła. Jednak protokoły takie jak OSPF będzie propagować aktualizację stanu łącza od sąsiadów uszkodzonych węzłów, dzięki czemu wszystkie węzły szybko dowiedzą się o upadku uszkodzonego węzła (lub rozłączeniu). Dzięki HSLS nie można rozróżnić między węzłem, który jest nadal obecny w odległości 10 przeskoków, a węzłem, który uległ awarii, dopóki byli sąsiedzi nie wyślą ogłoszeń na duże odległości. W związku z tym HSLS może zawieść w pewnych okolicznościach wymagających wysokiego poziomu pewności.

Podczas gdy dokumenty opisujące HSLS nie koncentrują się na bezpieczeństwie, techniki takie jak podpisy cyfrowe w aktualizacjach tras mogą być używane z HSLS (podobnie jak OSPF z podpisami cyfrowymi), a BBN zaimplementował HSLS z podpisami cyfrowymi w wiadomościach wykrywania sąsiadów i aktualizacjach stanu łącza. Takie schematy są trudne w praktyce, ponieważ w ad hoc nie można zapewnić dostępności serwerów infrastruktury klucza publicznego . Podobnie jak prawie wszystkie protokoły routingu, HSLS nie zawiera mechanizmów chroniących ruch danych. (Zobacz IPsec i TLS ).

Zobacz też

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Hazy_Sighted_Link_State_Routing_Protocol&oldid=1063349863 ”