Protokół routingu działający na podstawie wektora odległości - Distance-vector routing protocol

Dystans-wektor protokół routingu w sieciach danych wyznacza najlepszą trasę dla pakietów danych na podstawie odległości. Protokoły routingu działające na podstawie wektora odległości mierzą odległość na podstawie liczby routerów, które pakiet musi przejść, jeden router liczy się jako jeden przeskok. Niektóre protokoły działające na podstawie wektora odległości uwzględniają również opóźnienia w sieci i inne czynniki wpływające na ruch na danej trasie. Aby określić najlepszą trasę w sieci, routery, w których zaimplementowano protokół wektora odległości, wymieniają między sobą informacje, zwykle tabele routingu, liczniki przeskoków dla sieci docelowych i ewentualnie inne informacje o ruchu. Protokoły routingu działające na podstawie wektora odległości wymagają również, aby router okresowo informował swoich sąsiadów o zmianach topologii sieci .

Protokoły routingu działające na podstawie wektora odległości wykorzystują algorytm Bellmana – Forda do obliczenia najlepszej trasy. Inny sposób obliczania najlepszej trasy w sieci jest oparty na koszcie łącza i jest wdrażany 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 algorytmem routingu ARPANET i został szerzej zaimplementowany w sieciach lokalnych z protokołem Routing Information Protocol (RIP).

Metodologia

Routery korzystające z protokołu wektora odległości określają odległość między sobą a miejscem docelowym. Najlepszą trasą dla pakietów protokołu internetowego, które przenoszą dane przez sieć danych, jest liczba routerów (przeskoków), które pakiet musi przejść, aby dotrzeć do sieci docelowej. Ponadto niektóre protokoły działające na podstawie wektora odległości uwzględniają inne informacje o ruchu, takie jak opóźnienia w 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, opierają się wyłącznie na informacjach dostarczanych im przez inne routery i nie oceniają topologii sieci .

Protokoły działające na podstawie wektora odległości aktualizują tablice routingu routerów i określają trasę, po której pakiet zostanie wysłany w następnym przeskoku, który jest interfejsem wyjściowym routera i adresem 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. Ten proces został opisany jako „routing na podstawie plotek”, ponieważ routery polegają na informacjach, które otrzymują od innych routerów i nie mogą określić, czy informacje są rzeczywiście prawidłowe i prawdziwe. Istnieje wiele funkcji, które mogą pomóc w przypadku niestabilności i niedokładnych informacji o routingu.

Rozwój routingu działającego na podstawie wektora odległości

Najstarszym protokołem routingu i najstarszym protokołem wektora odległości jest wersja 1 protokołu Routing Information Protocol (RIPv1). Protokół RIPv1 został formalnie ustandaryzowany w 1988 roku. Ustala 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ą RIPv1 wymieniają swoje tablice routingu z sąsiednimi routerami, nadają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 zaimplementowany na routerach granicznych i zewnętrznych w Internecie . Wymienia informacje między routerami za pośrednictwem sesji protokołu kontroli transmisji (TCP). Routery z implementacją BGP określają najkrótszą ścieżkę w sieci na podstawie szeregu czynników innych niż przeskoki. Administratorzy mogą również skonfigurować protokół BGP, aby określone trasy były preferowane lub omijane. 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ż wykorzystuje metody routingu związane z protokołami routingu według stanu łącza , jest zastrzeżony protokół EIGRP ( Enhanced Interior Gateway Routing Protocol ). Został opracowany przez firmę Cisco w latach 80. XX wieku i został zaprojektowany w celu zapewnienia lepszej konwergencji i mniejszego ruchu sieciowego między routerami niż protokół routingu według stanu łącza Open Shortest Path First (OSPF).

Innym przykładem protokołu routingu wektora odległości jest Babel .

Licz do nieskończoności

Bellman-Ford algorytm nie zapobiega pętli routingu dzieje i cierpi z powodu policzyć do nieskończoności problemu . Rdzeniem problemu zliczania do nieskończoności jest to, że jeśli A mówi B, że ma gdzieś ścieżkę, B nie ma możliwości dowiedzenia się, czy ścieżka zawiera B jako jej część. Aby wyraźnie 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 odłączony. W procesie aktualizacji wektora B zauważa, że ​​trasa do A, która była odległością 1, jest wyłączona - B nie otrzymuje aktualizacji wektora od A. Problem w tym, że B również otrzymuje aktualizację z C, a C nadal nie jest świadomy faktu, że A jest w dół - 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 samą 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ż stanie się nieskończonością (w takim przypadku algorytm koryguje się sam, z powodu właściwości relaksacji Bellmana-Forda).

Obejścia i rozwiązania

RIP wykorzystuje technikę split horizon z techniką odwrócenia trucizny, aby zmniejszyć prawdopodobieństwo utworzenia pętli i wykorzystuje maksymalną liczbę przeskoków, aby przeciwdziałać problemowi „liczenia do nieskończoności”. Środki te pozwalają uniknąć tworzenia pętli routingu w niektórych, ale nie we wszystkich przypadkach. Dodanie czasu wstrzymania (odmowa aktualizacji trasy przez kilka minut po wycofaniu trasy) pozwala uniknąć tworzenia pętli praktycznie we wszystkich przypadkach, ale powoduje znaczne wydłużenie czasów zbieżności.

Niedawno opracowano szereg protokołów wektora odległości bez pętli - godnymi uwagi przykładami są EIGRP , DSDV i Babel . Zapobiegają tworzeniu się pętli we wszystkich przypadkach, ale są bardziej skomplikowane, a ich wdrażanie zostało spowolnione przez sukces protokołów routingu stanu łącza, takich jak OSPF .

Przykład

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

Networkabcd.svg

Bieżący czas (lub iteracja) w algorytmie oznaczamy T i zaczynamy (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 tabel routingu najkrótsza ścieżka jest podświetlana na zielono, a nowa najkrótsza ścieżka jest podświetlana 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 siebie lub przez niego samego.

T = 0
od poprzez via B przez C przez D
do A
być 3
do C. 23
do D.
od B. poprzez via B przez C przez D
do A 3
być
do C. 2
do D.
od C. poprzez via B przez C przez D
do A 23
być 2
do C.
do D. 5
Z d poprzez via B przez C przez D
do A
być
do C. 5
do D.
W tym momencie wszystkie routery (A, B, C, D) mają nowe „najkrótsze ścieżki” dla swojego DV (lista odległości, które są od nich do innego routera przez sąsiada). Każdy z nich rozgłasza ten nowy 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 otrzymuje tę informację, teraz ponownie obliczają najkrótsza ścieżka za jego pomocą.

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ż aktualna „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 wie A, podaje to jako bieżące oszacowanie najkrótszej ścieżki od siebie (A) do D, przez C.

T = 1
od poprzez via B przez C przez D
do A
być 3 25
do C. 5 23
do D. 28
od B. poprzez via B przez C przez D
do A 3 25
być
do C. 26 2
do D. 7
od C. poprzez via B przez C przez D
do A 23 5
być 26 2
do C.
do D. 5
Z d poprzez via 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; To zachęca 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) 7. Ponieważ aktualna „najkrótsza ścieżka” do B wynosi 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 via B przez C przez D
do A
być 3 25
do C. 5 23
do D. 10 28
od B. poprzez via B przez C przez D
do A 3 7
być
do C. 8 2
do D. 31 7
od C. poprzez via B przez C przez D
do A 23 5 33
być 26 2 12
do C.
do D. 51 9 5
Z d poprzez via 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 transmitują 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 odbierających nowe DV ponownie oblicza swoje najkrótsze ścieżki. Jednakże, ponieważ informacje z DV nie dają 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 via B przez C przez D
do A
być 3 25
do C. 5 23
do D. 10 28
od B. poprzez via B przez C przez D
do A 3 7
być
do C. 8 2
do D. 13 7
od C. poprzez via B przez C przez D
do A 23 5 15
być 26 2 12
do C.
do D. 33 9 5
Z d poprzez via 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 się zatrzymuje.

Bibliografia

Dalsza lektura