1.ROUTING

ROUTING

Algorytmy Routuj±ce

Wektor Odległo¶ci

Wektor odległo¶ci jest jednym z ogólnie uznanych algorytmów służ±cych do tworzenia tzw. tabeli Routingu.Tabela ta jest "drogowskazem" według którego nasz komputer przesyła, lub wysyła pakiety w sieć. Jak działa algorytm wektora odległo¶ci? WyobraĽmy sobie, że mamy następuj±c± strukturę sieci:

Przy czym za poszczególne punkty uznamy konkretne sieci reprezentowane przez routery(czyli komputery przesyłaj±ce dane pomiędzy sieciami o rożnych topologiach) Zalóżmy teraz że A chce wysłać pakiet do B? sk±d ma wiedzieć przez jaki interfejs sieciowy wypu¶cić informacje?W tym przypadku problem nie jest aż tak wielki router B jest bezpo¶rednio poł±czony z A wiec zdobycie informacji o jego położeniu nie nastręcza A specjalnych trudno¶ci. jednak wysłanie pakietu do E lub F wymaga znacznie trudniejszej procedury. i tu tablica routingu jest nieocenionym Ľródłem wiedzy, algorytm natomiast pozwoli nam to Ľródło szybko i sprawnie wypelnić(ręczne wypełnianie nie jest polecane, aczkolwiek możliwe:)) Na pocz±tku tabela routingu A wygl±da następuj±co:

Zilustrujemy działanie algorytmu na przykładzie routera C jego tablica na pocz±tku wygl±da tak:

Idea polega na tym, że każdy router wysyła do swoich s±siadów pakiet z informacjami zapisanymi w swojej tabeli, wiadomo¶ć ta składa się z dwóch pól:

Co robi C po otrzymaniu pakietu? Sprawdza czy do niektórych sieci nie będzie mu się łatwiej dostać przesyłaj±c informacje przez D niż bezpo¶rednio. W jaki sposób według algorytmu:):

jak to działa dla naszego przykładu? C sprawdza jak daleko ma do E i F, wychodzi mu nieskończono¶ć porównuje to z informacjami od D, które mówi± mu że je¶li prze¶le dane zaadresowane do E lub F poprzez D odleglo¶ć wyniesie 1, C dodaje do tego koszt dotarcia do D czyli 1 i wychodzi mu 2, ponieważ 2 < nieskończono¶ci aktualizuje tabelę która po tym zabiegu wyglada tak:

W ten sposób wysyłaj±c pakiety zawieraj±ce uzupełnienia poszczególne routery uzupełniaj± swoje tablice routingu, bardzo istotnym jest fakt, że pakiety te s± wysyłane jedynie do s±siadów.C nigdy nie otrzyma uaktualnienia od A, jedynie B może go poinformować jak dotrzeć do A.

W praktyce zależnie od implementacji:)

Stan ł±cza

Algorytm stanu ł±cza jest drugim z powszechnie stosowanych algorytmów routuj±cych. Bazowe założenia s± identyczne jak te przy wektorze odległo¶ci. Uznajemy że każdy węzeł jest zdolny do poznania stanu ł±czy do swoich s±siadów a także do okre¶lani ich kosztu. Pomysł tego algorytmu zakłada że jeżeli węzeł posiada powyższe informacje i uda się je rozpowszechnić w sieci to każdy węzeł będzie w stanie zbudować sobie mapę sieci. Możliwo¶ć dokonania takiego rozpowszechnienia zapewniaj± dwa mechanizmy:

Niezawodny rozpływ

Niezawodny rozpływ jest procesem którego zadanie polega na upewnieniu się czy, każdy węzeł bior±cy udział w wyborze trasy, otrzymał kopię informacji o stanie ł±cza każdego innego węzła. "Rozpływ" polega na tym że każdy węzeł przesyła do wszystkich swoich s±siadów cało¶ć posiadanej przez siebie informacji o stanie ł±cza . Każdy węzeł który t± informacje dostanie przesyła ja dalej, proces ten trwa tak długo, aż wszystkie węzły w sieci otrzymaj± te informacje.

Pierwsze dwa składniki s± potrzebne by umożliwić obliczenie trasy, nie wymagaj± dodatkowego tłumaczenia. Dwa ostanie s± niezbędne aby usługa była niezawodna. Przez niezawodno¶ć rozumiemy tutaj utrzymywanie jedynie najnowszych wersji informacji w każdy z węzłów

W jaki sposób się to odbywa?

1.sprawdza czy ma już kopie LSP węzła Y je¶li nie dodaje je¶li ma to

2.porownuje numery sekwencyjne je¶li nowy przybyły ma wyższy numer od już posiadanego LSP zastępuje go i przesyła nowy pakiet do wszystkich swoich s±siadów za wyj±tkiem tego od którego go otrzymał, w przeciwnym przypadku odrzuca nowy pakiet

każdy węzeł jest zobowi±zany do okresowego tworzenia nowego LSP.Za każdym razem gdy generowany jest nowy LSP jego numer sekwencyjny jest zwiększany o 1. Nie jest wymagane "zawijanie się" numerów. Dlatego pole numeru sekwencyjnego powinno być możliwie duże(zwykle 64 bity). je¶li węzeł ulegnie awarii i powróci po jakim¶ czasie do działania wtedy rozpoczyna nadawanie z ustawionym numerem 0. je¶li węzeł nie nadawał przez dłuższy okres czasu wszystkie jego LSP "zmarly"(o tym za chwile), je¶li nie po jakim¶ czasie uda mus się odebrać kopie własnego pakietu LSP i ustawić odpowiedni numer sekwencyjny. Pakiet "umiera" kiedy jego TTL osi±gnie 0, każdy węzeł posiadaj±cy taki pakiet natychmiast go usuwa, TTL zmniejsza się ze stał± okre¶lona szybko¶ci±. Istotnym problem jest synchronizacja wieku pakietu tak aby wszystkie węzły usuwały go jednocze¶nie.

Obliczenie trasy

je¶li dany węzeł posiada kopie LSP każdego innego węzła sieci , potrafi obliczyć kompletna mapę topologii sieci i za jej pomoc± wybrać optymalna ¶cieżkę. Obliczanie to odbywa się za pomoc± algorytmu obliczania najkrótszej ¶cieżki Djikstry. nie będę nikogo tutaj zanudzał stronę teoretyczna i od razu przejdę do strony praktycznej zagadnienia. W praktyce węzły stosuj± zmodyfikowana wersje algorytmu Djikstry zwana przeszukiwaniem w przód. Polega to na tym ze każdy węzeł utrzymuje dwie listy, listę WSTEPNA i listę POTWIERDZONA, każda z list przechowuje elementy w postaci (ODBIORCA, KOSZT, NASTEPNYETAP).Algorytm działa następuj±co:

1.Inicjuje listę potwierdzona elementem dla samego siebie, element ten ma koszt 0.

2.Wezel wła¶nie dodany do listy listy potwierdzonej w poprzednim kroku, nazwij NASTEPNYM, wybierz jego LSP.

3.Dla każdego SASIADA węzła NASTEPNEGO, oblicz KOSZT, za cenę którego można dotrzeć do tego SASIADA. jest to suma kosztu ode mnie do węzła NASTEPNEGO i od węzła NASTEPNEGO do SASIADA.

a) jeżeli SASIAD nie jest aktualnie ani na li¶cie WSTEPNEJ ani na li¶cie POTWIERDZONEJ, wtedy dodaj(SASIAD,KOSZT,NASTEPNYETAP) do listy WSTEPNEJ, gdzie NASTEPNYETAP jest kierunkiem w którym musze się poruszać, aby dotrzeć do węzła NASTEPNEGO.

b) jeżeli SASIAD jest aktualnie na li¶cie WSTEPNEJ, i KOSZT jest mniejszy od aktualnie umieszczonego kosztu na li¶cie dla SASIADA, wtedy zast±p aktualny element przez (SASIAD, KOSZT, NASTEPNYETAP), gdzie NASTEPNYETAP jest kierunkiem, w którym powinien się poruszać, aby dotrzeć do węzła NASTEPNEGO

4.jeżeli lista WSTEPNA jest pusta, zatrzymaj się. W przeciwnym przypadku, pobierz element z listy Wstępnej o najmniejszym koszcie, przesuń go na listę POTWIERDZONA, i wróć do kroku 2.

Miary

Sobota wieczór:)