Protokół routingu wektora odległości

Protokół routingu wektora odległości w sieciach danych określa najlepszą trasę dla pakietów danych na podstawie odległości. Protokoły routingu oparte na wektorze odległości mierzą odległość na podstawie liczby routerów , przez które pakiet musi przejść; jeden router liczy się jako jeden przeskok. Niektóre protokoły wektora odległości uwzględniają również opóźnienia sieci i inne czynniki wpływające na ruch na danej trasie. Aby określić najlepszą trasę w sieci, routery korzystające z protokołu wektora odległości wymieniają między sobą informacje, zwykle tablice routingu oraz liczniki przeskoków dla sieci docelowych i ewentualnie inne informacje o ruchu. Protokoły routingu opartego na wektorze odległości wymagają również, aby router okresowo informował swoich sąsiadów o topologii sieci .

Protokoły routingu wektora odległości wykorzystują algorytm Bellmana-Forda do obliczenia najlepszej trasy. Inny sposób obliczania najlepszej trasy w sieci opiera się na koszcie łącza i jest realizowany za pomocą protokołów routingu według stanu łącza .

Termin wektor odległości odnosi się do faktu, że protokół manipuluje wektorami ( tablicami ) odległości do innych węzłów w sieci. Algorytm wektora odległości był oryginalnym ARPANET i został szerzej zaimplementowany w sieciach lokalnych z protokołem Routing Information Protocol (RIP).

Przegląd

Protokoły routingu opartego na wektorze odległości wykorzystują algorytm Bellmana-Forda . W tych protokołach każdy router nie posiada informacji o pełnej topologii sieci . Rozgłasza swoją obliczoną wartość odległości (DV) innym routerom i otrzymuje podobne ogłoszenia od innych routerów, chyba że zmiany zostaną wprowadzone w sieci lokalnej lub przez sąsiadów (routery). Korzystając z tych ogłoszeń routingu, każdy router zapełnia swoją tablicę routingu. W następnym cyklu anonsowania router anonsuje zaktualizowane informacje ze swojej tablicy routingu. Ten proces jest kontynuowany, dopóki tablice routingu każdego routera nie osiągną stabilnych wartości.

Wadą niektórych z tych protokołów jest powolna konwergencja.

Przykłady protokołów routingu wektora odległości:

Metodologia

Routery korzystające z protokołu wektora odległości określają odległość między sobą a miejscem docelowym. Najlepsza trasa dla pakietów protokołu internetowego , które przenoszą dane przez sieć danych, jest mierzona liczbą routerów (przeskoków), przez które pakiet musi przejść, aby dotrzeć do sieci docelowej. Ponadto niektóre protokoły wektora odległości uwzględniają inne informacje o ruchu, takie jak opóźnienie sieci . Aby ustalić najlepszą trasę, routery regularnie wymieniają informacje z sąsiednimi routerami, zwykle ich tablice routingu , liczbę przeskoków dla sieci docelowej i ewentualnie inne informacje związane z ruchem. Routery, które implementują protokół wektora odległości, polegają wyłącznie na informacjach dostarczanych im przez inne routery i nie oceniają topologii sieci .

Protokoły wektora odległości aktualizują tablice routingu routerów i określają trasę, po której pakiet zostanie wysłany przez następny przeskok , którym jest interfejs wyjściowy routera i adres IP interfejsu routera odbierającego. Odległość jest miarą kosztu dotarcia do określonego węzła. Najtańszą trasą między dowolnymi dwoma węzłami jest trasa o minimalnej odległości.

Aktualizacje są przeprowadzane okresowo w protokole wektora odległości, w którym całość lub część tablicy routingu routera jest wysyłana do wszystkich sąsiadów skonfigurowanych do korzystania z tego samego protokołu routingu wektora odległości. Gdy router uzyska te informacje, może zmienić swoją własną tablicę routingu, aby odzwierciedlić zmiany, a następnie poinformować o nich swoich sąsiadów. Proces ten został opisany jako „routing na podstawie plotek”, ponieważ routery polegają na informacjach otrzymywanych od innych routerów i nie mogą ustalić, czy informacje te są rzeczywiście ważne i prawdziwe. Istnieje wiele funkcji, które mogą pomóc w przypadku niestabilności i niedokładnych informacji o trasach.

Rozwój routingu wektora odległości

Najstarszym protokołem routingu i najstarszym protokołem wektora odległości jest wersja 1 Routing Information Protocol (RIPv1). Protokół RIPv1 został formalnie ujednolicony w 1988 r. Wyznacza najkrótszą ścieżkę w sieci wyłącznie na podstawie przeskoków, czyli liczby routerów, które należy przekazać, aby dotrzeć do sieci docelowej. RIP jest protokołem bramy wewnętrznej , więc może być używany w sieciach lokalnych (LAN) na routerach wewnętrznych lub granicznych. Routery z implementacją protokołu RIPv1 wymieniają swoje tablice routingu z sąsiednimi routerami, wysyłając pakiet RIPv1 co 30 sekund do wszystkich połączonych sieci. Protokół RIPv1 nie jest odpowiedni dla dużych sieci, ponieważ ogranicza liczbę przeskoków do 15. Ten limit przeskoków został wprowadzony w celu uniknięcia pętli routingu, ale oznacza również, że sieci połączone przez więcej niż 15 routerów są nieosiągalne.

Protokół wektora odległości przeznaczony do użytku w sieciach rozległych (WAN) to Border Gateway Protocol (BGP). BGP jest protokołem bramy zewnętrznej i dlatego jest wdrażany na ruterach granicznych i zewnętrznych w Internecie . Wymienia informacje między routerami za pośrednictwem protokołu kontroli transmisji (TCP). Routery z implementacją protokołu BGP określają najkrótszą ścieżkę w sieci na podstawie szeregu czynników innych niż przeskoki. Protokół BGP może również zostać skonfigurowany przez administratorów, tak aby określone trasy były preferowane lub unikane. Protokół BGP jest używany przez dostawców usług internetowych (ISP) i firmy telekomunikacyjne.

Wśród protokołów wektora odległości, które zostały opisane jako hybrydowe, ponieważ wykorzystują metody routingu związane z protokołami routingu według stanu łącza , jest zastrzeżony protokół Enhanced Interior Gateway Routing Protocol (EIGRP). Został opracowany przez firmę Cisco w latach 80. XX wieku i został zaprojektowany w celu zapewnienia lepszej konwergencji i generowania mniejszego ruchu sieciowego między routerami niż protokół routingu stanu łącza OSPF ( Open Shortest Path First ).

Innym przykładem protokołu routingu opartego na wektorze odległości jest Babel .

Policz do nieskończoności problem

Bellmana -Forda nie zapobiega powstawaniu pętli routingu i cierpi na problem zliczania do nieskończoności . Istota problemu liczenia do nieskończoności polega na tym, że jeśli A mówi B, że ma gdzieś ścieżkę, B nie ma sposobu, aby wiedzieć, czy ścieżka zawiera B jako część. Aby zobaczyć problem, wyobraź sobie podsieć połączoną jak A-B-C-D-E-F i niech metryką między routerami będzie „liczba skoków”. Załóżmy teraz, że A jest w trybie offline. W procesie aktualizacji wektorów B zauważa, że ​​trasa do A, która była odległością 1, jest niedostępna – B nie otrzymuje aktualizacji wektora od A. Problem polega na tym, że B również otrzymuje aktualizację od C, a C nadal nie świadomy faktu, że A jest na dole – więc mówi B, że A to tylko dwa skoki z C (C do B do A). Ponieważ B nie wie, że ścieżka z C do A prowadzi przez siebie (B), aktualizuje swoją tabelę o nową wartość „B do A = 2 + 1”. Później B przekazuje aktualizację do C i ze względu na fakt, że A jest osiągalny przez B (z punktu widzenia C), C decyduje się zaktualizować swoją tabelę do „C do A = 3 + 1”. To powoli rozprzestrzenia się w sieci, aż osiągnie nieskończoność (w takim przypadku algorytm koryguje się, ze względu na właściwość relaksacji Bellmana-Forda).

Obejścia i rozwiązania

RIP wykorzystuje technikę podzielonego horyzontu z techniką odwróconej trucizny, aby zmniejszyć ryzyko tworzenia się pętli i wykorzystuje maksymalną liczbę przeskoków, aby przeciwdziałać problemowi „liczenia do nieskończoności”. Te środki zapobiegają tworzeniu się pętli routingu w niektórych, ale nie we wszystkich przypadkach. Dodanie czasu wstrzymania (odmowa aktualizacji trasy przez kilka minut po wycofaniu trasy) praktycznie we wszystkich przypadkach pozwala uniknąć tworzenia się pętli, ale powoduje znaczne wydłużenie czasu zbieżności.

Niedawno opracowano szereg protokołów wektora odległości bez pętli — godnymi uwagi przykładami są EIGRP , DSDV i Babel . We wszystkich przypadkach unikają one tworzenia pętli, ale są bardziej złożone, a ich wdrażanie zostało spowolnione przez sukces protokołów routingu według stanu łącza, takich jak OSPF .

Przykład

W tej sieci mamy 4 routery A, B, C i D:

Networkabcd.svg

Oznaczamy bieżący czas (lub iterację) w algorytmie za pomocą T i rozpoczynamy (w czasie 0 lub T=0) od utworzenia macierzy odległości dla każdego routera do jego bezpośrednich sąsiadów. Podczas tworzenia poniższych tablic routingu najkrótsza ścieżka jest podświetlona na zielono, a nowa najkrótsza ścieżka jest podświetlona na żółto. Szare kolumny wskazują węzły, które nie są sąsiadami bieżącego węzła i dlatego nie są uważane za prawidłowy kierunek w jego tabeli. Kolor czerwony oznacza nieprawidłowe wpisy w tabeli, ponieważ odnoszą się one do odległości od węzła do samego węzła lub przez niego samego.

T=0
od poprzez przez B przez C przez D
do A
być 3
do C 23
do D
od B poprzez przez B przez C przez D
do A 3
być
do C 2
do D
od C poprzez przez B przez C przez D
do A 23
być 2
do C
do D 5
Z d poprzez przez B przez C przez D
do A
do B
do C 5
do D
W tym momencie wszystkie routery (A,B,C,D) mają nowe „najkrótsze ścieżki” dla swoich DV (lista odległości między nimi a innym routerem przez sąsiada). Każdy z nich transmituje to nowe DV do wszystkich swoich sąsiadów: A do B i C, B do C i A, C do A, B i D oraz D do C. Gdy każdy z tych sąsiadów otrzyma te informacje, teraz ponownie obliczają najkrótsza ścieżka z niego korzystająca.

Na przykład: A otrzymuje DV od C, który mówi A, że istnieje ścieżka przez C do D, z odległością (lub kosztem) równą 5. Ponieważ bieżąca „najkrótsza ścieżka” do C to 23, to A wie, że ma ścieżka do D, która kosztuje 23+5=28. Ponieważ nie ma innych krótszych ścieżek, o których A wie, umieszcza to jako swoje bieżące oszacowanie najkrótszej ścieżki od siebie (A) do D, przez C.
T=1
od poprzez przez B przez C przez D
do A
być 3 25
do C 5 23
do D 28
od B poprzez przez B przez C przez D
do A 3 25
być
do C 26 2
do D 7
od C poprzez przez B przez C przez D
do A 23 5
być 26 2
do C
do D 5
Z d poprzez przez B przez C przez D
do A 28
być 7
do C 5
do D
Ponownie, wszystkie routery zyskały w ostatniej iteracji (przy T=1) nowe „najkrótsze ścieżki”, więc wszystkie transmitują swoje DV do swoich sąsiadów; Skłania to każdego sąsiada do ponownego obliczenia najkrótszych odległości.

Na przykład: A otrzymuje DV od B, który mówi A, że istnieje ścieżka przez B do D, z odległością (lub kosztem) równą 7. Ponieważ aktualna „najkrótsza ścieżka” do B to 3, to A wie, że ma ścieżka do D, która kosztuje 7+3=10. Ta ścieżka do D o długości 10 (przez B) jest krótsza niż istniejąca „najkrótsza ścieżka” do D o długości 28 (przez C), więc staje się nową „najkrótszą ścieżką” do D.
T=2
od poprzez przez B przez C przez D
do A
być 3 25
do C 5 23
do D 10 28
od B poprzez przez B przez C przez D
do A 3 7
być
do C 8 2
do D 31 7
od C poprzez przez B przez C przez D
do A 23 5 33
być 26 2 12
do C
do D 51 9 5
Z d poprzez przez B przez C przez D
do A 10
być 7
do C 5
do D
Tym razem tylko routery A i D mają nowe najkrótsze ścieżki dla swoich DV. Więc rozgłaszają swoje nowe DV do swoich sąsiadów: A nadaje do B i C, a D nadaje do C. To powoduje, że każdy z sąsiadów otrzymujących nowe DV ponownie oblicza swoje najkrótsze ścieżki. Ponieważ jednak informacje z DV nie dają żadnych krótszych ścieżek niż te, które już mają w swoich tablicach routingu, nie ma żadnych zmian w tablicach routingu.
T=3
od poprzez przez B przez C przez D
do A
być 3 25
do C 5 23
do D 10 28
od B poprzez przez B przez C przez D
do A 3 7
być
do C 8 2
do D 13 7
od C poprzez przez B przez C przez D
do A 23 5 15
być 26 2 12
do C
do D 33 9 5
Z d poprzez przez B przez C przez D
do A 10
być 7
do C 5
do D
Żaden z routerów nie ma nowych najkrótszych ścieżek do rozgłaszania. Dlatego żaden z routerów nie otrzymuje żadnych nowych informacji, które mogłyby zmienić ich tablice routingu. Algorytm zatrzymuje się.
  • G. Malkin (listopad 1998). RIP wersja 2 . Sieciowa Grupa Robocza. doi : 10.17487/RFC2453 . STD 53. RFC 2453 . Standard internetowy. Przestarzałe dokumenty RFC 1723 i 1388 . Zaktualizowany przez RFC 4822 .
  • „Algorytm znajdowania ścieżki dla routingu bez pętli” , JJ Garcia-Luna-Aceves i S. Murthy, IEEE/ACM Transactions on Networking, luty 1997
  • „Detection of Invalid Routing Announcements in the RIP Protocol”, D. Pei, D. Massey i L. Zhang, IEEE Global Communications Conference (Globecom), grudzień 2003

Dalsza lektura

Pobrane z „ https://en.wikipedia.org/w/index.php?title=Distance-vector_routing_protocol&oldid=1115689294 ”