Routing stanu typu rybie oko

Fisheye State Routing (FSR) to propozycja niejawnego hierarchicznego protokołu routingu ukierunkowanego na sieci ad hoc . Podstawowe zasady FSR są wspólne dla innych proaktywnych protokołów routingu według stanu łącza . W proaktywnych protokołach stanu łącza każdy węzeł sieci stale aktualizuje mapę topologii, która umożliwia obliczenie najkrótszej ścieżki (a tym samym następnego przeskoku) do dowolnego miejsca docelowego w sieci. Oryginalność FSR jest inspirowana techniką „ rybiego oka ” w celu zmniejszenia rozmiaru informacji wymaganych do przedstawienia danych graficznych: Oko ryby wychwytuje z dużą szczegółowością piksele w pobliżu ogniska, podczas gdy szczegóły zmniejszają się wraz z odległością od ogniska wzrasta punkt.

W routingu podejście typu „rybie oko” przekłada się na utrzymywanie aktualnego zestawu informacji o odległości i jakości ścieżki dla bezpośredniego sąsiedztwa węzła, w stosunku do coraz mniej aktualnych informacji w miarę wzrostu odległości. Rybie oko reprezentuje ważny kompromis między dokładnością funkcji routingu a narzutem związanym z generowaniem komunikatów sterujących przez protokół routingu.

FSR nigdy nie został udostępniony publicznie jako samodzielny protokół routingu, a jego specyfikacja nigdy nie została sfinalizowana. Podstawowa zasada została zawarta w szeroko stosowanym OLSRd (implementacja protokołu routingu OLSR typu open source).

Zasada działania protokołu

FSR jest protokołem routingu według stanu łącza, dlatego składa się z trzech zadań:

1. Wykrywanie sąsiadów: każdy węzeł wysyła wiadomość HELLO co δ sekund do swoich sąsiadów z jednym przeskokiem, w celu ustanowienia i utrzymania relacji sąsiedzkich.
2. Rozpowszechnianie informacji: każdy węzeł rozsyła komunikaty LSA (Link State Announcements) co Δ sekund (gdzie Δ > δ), które zawierają informacje o łączu sąsiada, do wszystkich innych węzłów w sieci.
3. Obliczanie trasy: na podstawie informacji zawartych w komunikatach LSA węzeł może zrekonstruować całą topologię sieci i użyć algorytmu Dijkstry do obliczenia tras do dowolnego węzła w sieci.

Osobliwością FSR jest to, że komunikaty LSA są generowane co Δ sekund przy użyciu sekwencji odrębnych wartości czasu życia (TTL). Weźmy jako przykład sekwencję 1, 3, 8, 64, sąsiedzi z 1 przeskokiem otrzymują LSA co Δs, więc mają najbardziej aktualne informacje. Sąsiedzi z 2 przeskokami odbierają LSA z TTL 3, 8, 24. Węzły w odległości od 4 do 8 przeskoków odbierają tylko LSA z TTL 8 i 64. Wszystkie pozostałe odbierają tylko LSA z TTL 64. W konsekwencji każdy węzeł ma coraz mniej aktualnych informacji o topologii sieci wraz ze wzrostem odległości.

Protokół wykorzystuje fakt, że gdy pakiet przemieszcza się od źródła do miejsca docelowego, węzły napotkane na najkrótszej ścieżce mają coraz bardziej precyzyjne informacje topologiczne o pozycji topologicznej miejsca docelowego (w miarę zmniejszania się ich odległości do miejsca docelowego), więc utrata dokładności w obliczeniach najkrótszej ścieżki od węzła źródłowego jest kompensowana wzdłuż ścieżki do miejsca docelowego.

FSR zmniejsza zatem ogólną ilość informacji rozprzestrzenianych w sieci, ponieważ LSA nie są wysyłane z ustalonym maksymalnym czasem TTL.

Wady

Jednym z typowych problemów z protokołami stanu łącza jest to, że w przypadku zerwania węzła lub łącza mogą powstać tymczasowe pętle. Wynika to z faktu, że komunikaty HELLO są wysyłane z większą częstotliwością niż komunikaty LSA, więc jeśli węzeł ulegnie awarii, jego sąsiedzi wykryją przerwane łącze znacznie wcześniej niż inne węzły. Natychmiast przeliczają swoje tablice routingu, co może powodować konflikt z tablicami routingu innych węzłów, i może powstać pętla . Może się to zdarzyć, gdy dwa węzły mają informacje o różnym wieku i dlatego obliczają swoje tablice routingu na dwóch różnych topologiach sieci. FSR robi to z założenia, wprowadza obszary w sieci z potencjalnie różnymi zestawami informacji, więc zwiększa prawdopodobieństwo tworzenia tymczasowych pętli.