Protokół routingu według stanu łącza — Link-state routing protocol

Protokoły routingu według stanu łącza to jedna z dwóch głównych klas protokołów routingu używanych w sieciach z komutacją pakietów do komunikacji komputerowej , druga to protokoły routingu działające na podstawie wektora odległości . Przykłady protokołów routingu według stanu łącza obejmują Open Shortest Path First (OSPF) i Intermediate System to Intermediate System (IS-IS).

Protokół stanu łącza jest wykonywany przez każdy węzeł przełączający w sieci (tj. węzły przygotowane do przekazywania pakietów; w Internecie nazywane są routerami ). Podstawowa koncepcja routingu według stanu łącza polega na tym, że każdy węzeł konstruuje mapę połączeń z siecią w postaci wykresu , pokazującego, które węzły są połączone z jakimi innymi węzłami. Następnie każdy węzeł niezależnie oblicza następną najlepszą ścieżkę logiczną od niego do każdego możliwego miejsca docelowego w sieci. Każda kolekcja najlepszych ścieżek utworzy następnie tablicę routingu każdego węzła .

Kontrastuje to z protokołami routingu opartymi na wektorze odległości , w których każdy węzeł współdzieli swoją tabelę routingu z sąsiadami. W protokole stanu łącza jedyna informacja przekazywana między węzłami jest związana z łącznością . Algorytmy stanu łącza są czasami określane nieformalnie, jako że każdy router „mówi światu o swoich sąsiadach”.

Historia

Uważa się, że jest to pierwsza adaptacyjna sieć routingu komputerów, wykorzystująca routing według stanu łącza jako jego serce, została zaprojektowana i wdrożona w latach 1976-77 przez zespół z Plessey Radar kierowany przez Bernarda J Harrisa; projekt dotyczył "Wavell" - systemu komputerowego dowodzenia i kontroli dla armii brytyjskiej.

Pierwsza koncepcja routingu według stanu łącza została opublikowana w 1979 r. przez Johna M. McQuillana (wtedy w Bolt, Beranek i Newman ) jako mechanizm, który szybciej oblicza trasy, gdy zmieniają się warunki sieciowe, a tym samym prowadzi do bardziej stabilnego routingu.

Późniejsze prace w BBN Technologies pokazały, jak wykorzystać technikę stanu łącza w systemie hierarchicznym (tj. takim, w którym sieć została podzielona na obszary), aby każdy węzeł przełączający nie potrzebował mapy całej sieci, a jedynie obszaru( s) w którym jest zawarta.

Technika ta została później zaadaptowana do użytku we współczesnych protokołach routingu według stanu łącza IS-IS i OSPF. Literatura firmy Cisco odnosi się do protokołu routingu rozszerzonej bramy wewnętrznej (EIGRP) jako protokołu „hybrydowego”, mimo że dystrybuuje on tabele routingu zamiast map topologii. Jednak synchronizuje on tablice routingu podczas uruchamiania, tak jak robi to OSPF, i wysyła określone aktualizacje tylko wtedy, gdy nastąpią zmiany topologii.

W 2004 roku Radia Perlman zaproponowała wykorzystanie routingu według stanu łącza do przekazywania ramek warstwy 2 za pomocą urządzeń zwanych mostami routingu lub Rbridge. Internet Engineering Task Force ma znormalizowane z przezroczystą wzajemnych połączeń dużą ilością linków protokołu (tryl) do osiągnięcia tego celu.

Niedawno ta hierarchiczna technika została zastosowana w bezprzewodowych sieciach kratowych z wykorzystaniem zoptymalizowanego protokołu routingu stanu łącza (OLSR). Tam, gdzie połączenie może mieć różną jakość, jakość połączenia może być wykorzystana do wyboru lepszych połączeń. Jest to używane w niektórych protokołach routingu, które wykorzystują transmisję na częstotliwości radiowej.

W 2012 roku organizacja IEEE zakończyła i zatwierdziła standaryzację wykorzystania IS-IS do sterowania przekazywaniem sieci Ethernet za pomocą mostkowania najkrótszej ścieżki (SPB) IEEE 802.1aq .

Dystrybucja map

Ten opis obejmuje tylko najprostszą konfigurację; tj. jeden bez obszarów, dzięki czemu wszystkie węzły mają mapę całej sieci. Przypadek hierarchiczny jest nieco bardziej złożony; zobacz różne specyfikacje protokołów.

Jak wspomniano wcześniej, pierwszym głównym etapem algorytmu stanu łącza jest udostępnienie mapy sieci każdemu węzłowi. Odbywa się to za pomocą kilku dodatkowych kroków.

Określanie sąsiadów każdego węzła

Po pierwsze, każdy węzeł musi określić, do jakich innych portów jest podłączony poprzez w pełni działające łącza; robi to za pomocą protokołu osiągalności, który działa okresowo i oddzielnie z każdym z jego bezpośrednio połączonych sąsiadów.

Dystrybucja informacji do mapy

Następnie każdy węzeł okresowo (oraz w przypadku zmiany łączności) wysyła krótką wiadomość, ogłoszenie o stanie łącza , która:

• Identyfikuje węzeł, który go produkuje.
• Identyfikuje wszystkie inne węzły (routery lub sieci), z którymi jest bezpośrednio połączony.
• Zawiera „numer kolejny”, który zwiększa się za każdym razem, gdy węzeł źródłowy tworzy nową wersję wiadomości .

Ta wiadomość jest wysyłana do wszystkich węzłów w sieci. Jako niezbędny prekursor, każdy węzeł w sieci pamięta, dla każdego ze swoich sąsiadów, numer sekwencyjny ostatniej wiadomości o stanie łącza, którą otrzymał od tego węzła. Gdy w węźle odebrane zostaje ogłoszenie o stanie łącza, węzeł wyszukuje numer sekwencyjny, który zapisał dla źródła tej wiadomości o stanie łącza: jeśli ta wiadomość jest nowsza (tj. ma wyższy numer sekwencyjny), jest zapisywana , numer sekwencyjny jest aktualizowany, a kopia jest wysyłana kolejno do każdego z sąsiadów tego węzła. Ta procedura szybko dostarcza kopię najnowszej wersji ogłoszenia o stanie łącza każdego węzła do każdego węzła w sieci.

Sieci, w których działają algorytmy stanu łącza, można również podzielić na hierarchie, które ograniczają zakres zmian tras. Te cechy oznaczają, że algorytmy stanu łącza lepiej skalują się do większych sieci.

Tworzenie mapy

Na koniec, z pełnym zestawem ogłoszeń o stanie łącza (po jednym z każdego węzła w sieci), każdy węzeł tworzy wykres mapy sieci. Algorytm iteruje po zbiorze ogłoszeń o stanie łącza; dla każdego z nich tworzy łącza na mapie sieci, od węzła, który wysłał tę wiadomość, do wszystkich węzłów, które ta wiadomość wskazuje, że są sąsiadami węzła nadawczego.

Uznaje się, że żaden link nie został prawidłowo zgłoszony, chyba że oba końce są zgodne; np. jeśli jeden węzeł zgłasza, że ​​jest połączony z innym, ale drugi węzeł nie zgłasza, że ​​jest połączony z pierwszym, występuje problem i łącze nie jest uwzględnione na mapie.

Uwagi dotyczące tego etapu

Wiadomość o stanie łącza zawierająca informacje o sąsiadach jest ponownie przeliczana, a następnie zalewana w całej sieci, ilekroć następuje zmiana w łączności między węzłem a jego sąsiadami; np. w przypadku awarii łącza. Każda taka zmiana zostanie wykryta przez protokół osiągalności, który każdy węzeł uruchamia ze swoimi sąsiadami.

Obliczanie tablicy routingu

Jak wspomniano na początku, drugim głównym etapem algorytmu stanu łącza jest tworzenie tablic routingu poprzez inspekcję map. Odbywa się to ponownie w kilku krokach.

Obliczanie najkrótszych ścieżek

Każdy węzeł niezależnie uruchamia na mapie algorytm, aby określić najkrótszą ścieżkę od siebie do każdego innego węzła w sieci; ogólnie używany jest jakiś wariant algorytmu Dijkstry . Opiera się to na koszcie łącza na każdej ścieżce, który obejmuje między innymi dostępną przepustowość.

Węzeł utrzymuje dwie struktury danych: drzewo zawierające węzły, które są „ukończone” oraz listę kandydatów . Algorytm zaczyna się od obu struktur pustych; następnie dodaje do pierwszego sam węzeł. Wariant algorytmu zachłannego następnie powtarzalnie wykonuje następujące czynności:

• Wszystkie sąsiednie węzły, które są bezpośrednio połączone z węzłem, są po prostu dodawane do drzewa (z wyjątkiem węzłów, które są już w drzewie lub na liście kandydatów). Pozostałe są dodawane do drugiej listy (kandydatów).
• Każdy węzeł na liście kandydackiej jest porównywany z każdym z węzłów już w drzewie. Węzeł kandydujący, który jest najbliżej któregokolwiek z węzłów znajdujących się już w drzewie, sam jest przenoszony do drzewa i dołączany do odpowiedniego węzła sąsiedniego. Gdy węzeł zostanie przeniesiony z listy kandydatów do drzewa, jest usuwany z listy kandydatów i nie jest uwzględniany w kolejnych iteracjach algorytmu.

Powyższe dwa kroki są powtarzane, dopóki na liście kandydatów pozostaną jakieś węzły. (Gdy ich nie ma, wszystkie węzły w sieci zostaną dodane do drzewa.) Ta procedura kończy się na drzewie zawierającym wszystkie węzły w sieci, z węzłem, na którym działa algorytm, jako korzeniem drzewa . Najkrótsza ścieżka od tego węzła do dowolnego innego węzła jest wskazywana przez listę węzłów, przez które przechodzi się, aby dostać się od korzenia drzewa do pożądanego węzła w drzewie..!

Wypełnianie tablicy routingu

Mając do dyspozycji najkrótsze ścieżki, następnym krokiem jest wypełnienie tablicy routingu. Dla dowolnego danego węzła docelowego najlepszą ścieżką dla tego miejsca docelowego jest węzeł, który jest pierwszym krokiem od węzła głównego, w dół gałęzi w drzewie najkrótszej ścieżki, która prowadzi do pożądanego węzła docelowego. Aby utworzyć tablicę routingu, wystarczy przespacerować się po drzewie, pamiętając tożsamość węzła na początku każdej gałęzi i wypełnić wpis w tablicy routingu dla każdego węzła, który natrafia się na tę tożsamość.

Optymalizacje algorytmu

Opisany powyżej algorytm został maksymalnie uproszczony, aby ułatwić zrozumienie. W praktyce stosuje się szereg optymalizacji.

Częściowe przeliczenie

Za każdym razem, gdy nastąpi zmiana mapy połączeń, konieczne jest ponowne obliczenie drzewa najkrótszej ścieżki, a następnie ponowne utworzenie tabeli routingu. Praca BBN Technologies odkryła, jak przeliczyć tylko tę część drzewa, na którą mogła mieć wpływ dana zmiana na mapie. Ponadto tablica routingu byłaby zwykle wypełniana, gdy obliczane jest drzewo najkrótszej ścieżki, zamiast robić z tego oddzielną operację.

Redukcja topologii

W niektórych przypadkach uzasadnione jest zmniejszenie liczby węzłów generujących komunikaty LSA. Na przykład węzeł, który ma tylko jedno połączenie z grafem sieci, nie musi wysyłać komunikatów LSA, ponieważ informacja o jego istnieniu może być już zawarta w komunikacie LSA jego jedynego sąsiada. Z tego powodu można zastosować strategię redukcji topologii, w której tylko podzbiór węzłów sieci generuje komunikaty LSA. Dwa szeroko badane podejścia do redukcji topologii to:

1. Przekaźniki MultiPoint, które są podstawą protokołu OLSR , ale zostały również zaproponowane dla OSPF
2. Połączone zestawy dominujące, które ponownie zostały zaproponowane dla OSPF

Routing stanu rybie oko

Z FSR LSA są wysyłane z różnymi wartościami TTL w celu ograniczenia ich rozproszenia i ograniczenia narzutu z powodu komunikatów kontrolnych. Ta sama koncepcja jest używana również w Hazy Sighted Link State Routing Protocol .

Tryby awaryjne

Jeśli wszystkie węzły nie działają dokładnie na tej samej mapie, mogą powstawać pętle routingu . Są to sytuacje, w których w najprostszej formie dwa sąsiednie węzły uważają się za najlepszą drogę do danego celu. Każdy pakiet skierowany do tego miejsca docelowego docierający do dowolnego węzła będzie pętlą między nimi, stąd nazwa. Możliwe są również pętle routingu obejmujące więcej niż dwa węzły.

Może się tak zdarzyć, ponieważ każdy węzeł oblicza swoje drzewo najkrótszej ścieżki i swoją tabelę routingu bez interakcji z innymi węzłami. Jeśli dwa węzły zaczynają się od różnych map, możliwe są scenariusze, w których tworzone są pętle routingu. W pewnych okolicznościach pętle różnicowe mogą być włączone w środowisku wielu chmur. Węzły o zmiennym dostępie w protokole interfejsu mogą również ominąć problem jednoczesnego węzła dostępowego.

Protokół Optimized Link State Routing Protocol dla mobilnych sieci ad hoc

Optimized link State Routing Protocol (OLSR) to protokół routingu stanu łącza zoptymalizowany dla sieci komórkowych doraźnych (które mogą być również wykorzystywane w innych sieciach bezprzewodowych ad hoc ). OLSR jest proaktywny, wykorzystuje komunikaty Hello i Topology Control (TC) do wykrywania i rozpowszechniania informacji o stanie łącza w mobilnej sieci ad hoc . Używając wiadomości Hello, każdy węzeł wykrywa informacje o sąsiednich 2 przeskokach i wybiera zestaw przekaźników wielopunktowych (MPR). Protokół MPR sprawia, że ​​protokół OLSR jest unikalny na tle innych protokołów routingu według stanu łącza. Poszczególne węzły wykorzystują informacje o topologii do obliczenia ścieżek następnego przeskoku w odniesieniu do wszystkich węzłów w sieci przy użyciu najkrótszych ścieżek przekazywania przeskoków.

Zobacz też

• 802.1aq Mostkowanie najkrótszej ścieżki

Bibliografia

• Josh Seeger i Atul Khanna, Zmniejszenie narzutu na routing w rosnącej sieci DDN , MILCOMM '86, IEEE, 1986
• Radia Perlman „Rbridges: Transparent Routing” , Infocom 2004.

Dalsza lektura

• Sekcja „stan łącza a wektor odległości” w rozdziale „Podstawy routingu” w podręczniku Cisco „Internetworking Technology Handbook”