Trasowanie (routing)

Wstępne wiadomości o trasowaniu

Trasowanie (Routing) jest mechanizmem kierowania i przenoszenia informacji w intersieci, od stacji nadawczej (Source) do stacji odbiorczej (Destination). Na tej drodze informacja musi przejść przez co najmniej jeden element pośredniczący, którym może być most lub router. Na pierwszy rzut oka trasowanie i mostowanie to mechanizmy bardzo podobne. Tak jednak nie jest - różnią się one istotnie.

Zasadnicza różnica polega na tym, że mostowanie realizowane jest w warstwie 2 modelu OSI (warstwa Łącza danych), a trasowanie w warstwie 3 (Sieciowa). Mostowanie i trasowanie korzystają więc z różnych informacji w procesie przenoszenia danych od stacji nadawczej do stacji odbiorczej, a to sprawia, że ich funkcje są realizowane w różny sposób.

Nauka zdefiniowała funkcje i zadania trasowania już ponad 20 lat temu. Technicznie i komercyjnie mechanizm trasowania zaczęto stosować jednak dopiero w połowie lat 80. Przyczyną tego była prostota i jednorodność technologiczna sieci lat 70. (trasowanie było zbyteczne). Dopiero niedawno popularne stały się duże intersieci. Stąd obecne wielkie zainteresowanie mechanizmami trasowania.

Dwie podstawowe funkcje trasowania

Proces trasowania można sprowadzić do dwóch zasadniczych funkcji:

1. Wyznaczenie optymalnych tras (ścieżek) między stacją nadawczą i stacją odbiorczą.
2. Transport grup informacji (pakietów) przez intersieć, często nazywany przełączaniem. Wyznaczanie trasy należy do zadań trudnych, a przełączanie pakietów jest stosunkowo proste.

Wyznaczanie optymalnej trasy

Tablica trasowania

Przy określaniu optymalnej trasy algorytmy trasowania używają standardowej miary trasowania, np. długości ścieżki.

Przy określaniu optymalnej trasy między stacją nadawczą a stacją odbiorczą algorytmy trasowania tworzą tablice trasowania (Routing Tables), przechowujące informacje o trasach przesyłania pakietów. Informacje o trasach są różne, zależnie od stosowanego algorytmu routingu.

Istotny jest związek stacja odbiorcza/następny hop, informujący router o tym, że do określonej stacji odbiorczej można optymalnie dotrzeć wysyłając pakiet do routera reprezentującego następny hop. W sytuacji gdy router odbiera przychodzący pakiet, sprawdza adres stacji odbiorczej i usiłuje skojarzyć ten adres z następnym hop. Tablice trasowania mogą zawierać także inne informacje, takie jak zalety trasy. Routery porównują miary tras w celu wyboru trasy optymalnej; miary te różnią się zależnie od użytego algorytmu trasowania.

Routery komunikują się między sobą i pamiętają zawartości swoich tablic trasowania w czasie transmisji różnych komunikatów. Jednym z nich jest komunikat aktualizacji trasowania (Routing Update), składający się w całości lub w części z zawartości tablicy trasowania. Dany router - na podstawie analizy komunikatów aktualizacji trasowania, pochodzących od wszystkich pozostałych routerów - może budować szczegółowy obraz topologii sieci. Innym komunikatem, przesyłanym między routerami, jest stan łącza (Link-State Advertisement). Również ten komunikat może być użyty do budowy kompletnej topologii sieci po to, by umożliwić routerom określenie optymalnych tras między stacjami nadawczymi a odbiorczymi.

Przełączanie

Trasa pakietu od stacji nadawczej do stacji odbiorczej

Algorytmy przełączania to mechanizmy stosunkowo proste i są w zasadzie takie same dla większości protokołów trasowania. W większości wypadków stacja nadawcza decyduje o wysłaniu pakietu do stacji odbiorczej. Stacja nadawcza, dysponując adresem routera, wysyła pakiet pod jego fizyczny adres MAC (Media Access Control) wraz z adresem logicznym (np. protokołu IP - warstwa Sieciowa) stacji odbiorczej.

Po otrzymaniu pakietu router stwierdza, czy potrafi transportować pakiet do następnego hop. Jeśli router nie może tego zrobić, to zwykle pakiet zostaje stracony. Jeśli router wie, jak transportować pakiet, to zmienia fizyczny adres, tak by osiągnąć następny hop, po czym transmituje pakiet.

Hop - termin opisujący przemieszczanie pakietu danych między dwoma routerami. Hop count - miara trasowania używana do pomiaru odległości między stacją nadawczą i odbiorczą. W szczególnym przypadku następny hop może być stacją odbiorczą. Jeśli tak nie jest, to znaczy, że następnym hop jest router, który realizuje proces decyzyjny. W miarę jak pakiet przesuwa się w sieci, jego adres fizyczny zmienia się, natomiast jego adres logiczny nie ulega zmianie.</font>

Warto podkreślić, że ISO opracowała terminologię związaną z hierarchiczną organizacją sieci, bardzo użyteczną przy opisie omawianego procesu. Przypomnijmy, urządzenia bez możliwości przesyłania pakietów między sieciami nazywane są stacjami sieciowymi lub urządzeniami końcowymi ES (End Systems), z kolei urządzenia mające takie możliwości nazywa się systemami pośredniczącymi IS (Intermediate Systems). Urządzenie IS można dalej dzielić na komunikujące się w ramach domeny (Intradomain IS) oraz komunikujące się w ramach domeny i między domenami (Interdomain IS). Domena trasowania to część intersieci będącej pod wspólnym zarządem, to znaczy regulowana przez określony zestaw reguł administracyjnych. Domeny trasowania są także zwane autonomicznymi systemami AS (Autonomous Systems). Przy pewnych protokołach domeny trasowania mogą być dzielone na obszary trasowania (Routing Areas), ale mimo to protokoły trasowania intradomenowego (Intradomain Routing) są ciągle stosowane do przełączania wewnątrz i między obszarami.

Algorytmy trasowania

Algorytmy trasowania są różne pod względem wielu parametrów. Po pierwsze - zróżnicowanie zależy od celów określonych przez konstrukcję algorytmu. Po drugie - istnieją różne typy algorytmów trasowania i każdy z nich ma inny wpływ na sieć i zasoby routerów. Wreszcie po trzecie - algorytmy trasowania używają różnych miar mających wpływ na obliczenie trasy optymalnej.

Cele wyznaczone przez konstrukcję algorytmów trasowania

Pętle trasowania

Konstrukcje algorytmów trasowania spełniają jeden lub więcej celów spośród następującego zbioru możliwości:

• optymalizacja,
• prostota,
• odporność i stabilność,
• szybka konwergencja,
• elastyczność.

Optymalizacja odnosi się do możliwości algorytmu trasowania co do wyboru najlepszej trasy, a to zależy od przyjętej do obliczeń miary trasowania i wagi przypisanej poszczególnym miarom. Na przykład jeden algorytm może używać liczby hop i opóźnień, ale w kalkulacjach waga związana z opóźnieniami może być większa. Oczywiście protokoły trasowania muszą dokładnie definiować algorytmy kalkulacji miar.

Algorytmy trasowania powinny być zaprojektowane tak, by były możliwie najprostsze. Inaczej mówiąc, algorytm trasowania musi mieć bardzo efektywnie zaprojektowaną warstwę funkcjonalną przy minimalnych nakładach na oprogramowanie i eksploatację. Efektywność jest szczególnie ważna w sytuacji, gdy oprogramowanie algorytmu trasowania musi działać na komputerze z ograniczonymi zasobami sprzętowymi.

Algorytmy trasowania muszą być odporne i stabilne, co oznacza ich poprawne działanie nawet w niezwykłych okolicznościach i trudnych do przewidzenia warunkach, np. przy uszkodzeniach sprzętu czy niewłaściwej eksploatacji. Routery pracujące w punktach stykowych sieci mogą powodować poważne kłopoty w razie uszkodzenia. Dlatego najlepszymi algorytmami trasowania okazują się te, które wytrzymały próbę czasu i okazały się stabilne w różnych warunkach pracy sieci.

Ponadto algorytmy trasowania muszą charakteryzować się krótkim czasem konwergencji. Konwergencja jest procesem uzgadniania optymalnych tras między wszystkimi routerami w sieci. Jeśli wydarzenia w sieci powodują naprzemian zanikanie lub dostępność tras, to routery obwieszczają ten fakt rozgłaszając komunikaty aktualizujące, przenikające całą sieć, stymulujące ponowną kalkulację optymalnych tras i uzgodnienie tych tras. Algorytmy o długim czasie konwergencji mogą powodować powstawanie pętli trasowania, a nawet zaniki pracy sieci.

Algorytmy trasowania powinny być ponadto elastyczne, co oznacza, iż powinny szybko i dokładnie dostosowywać się do różnorodnych okoliczności występujących w sieci. Jeśli np. segment sieci ulega uszkodzeniu, to algorytmy trasowania powinny szybko określić następną optymalną trasę dla wszystkich routerów normalnie obsługujących omawiany segment. Algorytmy trasowania mogą być tak programowane, by adaptować m.in. zmiany w szerokości pasma, rozmiarze kolejki routerów i opóźnieniu wprowadzanemu przez sieć.

Typy algorytmów trasowania

Rozróżnia się następujące typy algorytmów trasowania:

• statyczne i dynamiczne,
• jednościeżkowe i wielościeżkowe,
• płaskie i hierarchiczne,
• z inteligencją stacji i z inteligencją routera,
• intradomenowe i interdomenowe,
• działające według stanu łącza i na podstawie wektora odległości.

Statyczne i dynamiczne algorytmy trasowania

Przed rozpoczęciem trasowania statyczne algorytmy wymagają od administratora sieci wpisywania zawartości tabel routerów, będących odwzorowaniem topologii sieci. Odwzorowania te mogą być zmienione również tylko przez administratora sieci. Algorytmy używające statycznych routerów są stosukowo proste w swojej konstrukcji i pracują poprawnie w sieciach małych o prostej architekturze.

Ponieważ statyczne systemy trasowania nie mogą reagować na zmiany w sieci, to generalnie nie są one przydatne do stosowania w sieciach dużych, gdzie zmiany następują praktycznie ciągle. Dlatego większość obecnie stosowanych algorytmów trasowania to algorytmy dynamiczne, dostosowujące się do zmiennych warunków występujących w sieci, na drodze analizy aktualizujących komunikatów trasowania. W wypadku, gdy aktualizujący komunikat trasowania wskazuje, że w sieci wystąpiły zmiany, oprogramowanie trasujące ponownie oblicza trasy i wysyła do routerów nowe komunikaty aktualizujące. W ślad za tym komunikaty, przenikając przez sieć, stymulują routery do uruchomienia algorytmów trasowania i zmieniają ich tablice trasowania.

Jednościeżkowe i wielościeżkowe algorytmy trasowania

Niektóre protokoły trasowania wspierają tworzenie wielościeżkowych tras między stacją nadawczą i odbiorczą. Algorytmy realizujące taki mechanizm zezwalają na przemieszczanie ruchu przez wiele linii. Zaleta algorytmów wielościeżkowych jest oczywista: zapewniają one większą przepustowość i niezawodność.

Płaskie i hierarchiczne algorytmy trasowania

Niektóre algorytmy trasowania operują w płaskiej przestrzeni, inne zaś używają hierarchii trasowania. W systemie płaskim wszystkie routery są równoprawne względem siebie. W systemie hierarchicznym niektóre routery tworzą kręgosłup trasowania. Pakiety z routerów nie tworzących kręgosłupa wędrują do routerów w kręgosłupie trasowania, przez który przepływają do obszaru, w którym znajdują się stacje odbiorcze.

Systemy trasowania często wyznaczają logiczne grupy stacji sieciowych, zwane domenami, systemami autonomicznymi lub obszarami. W systemach hierarchicznych pewne routery w domenie mogą komunikować się z routerami z innych domen, inne zaś mogą komunikować się z routerami w ramach ich własnej domeny. W sieciach bardzo dużych mogą istnieć dodatkowe poziomy hierarchii, z routerami na najwyższym poziomie, tworzącymi wspomniany kręgosłup trasowania.

Podstawową zaletą trasowania hierarchicznego jest to, że odwzorowuje ono organizację firmy lub instytucji. Większość komunikacji przebiega w małych grupach firmowych (domenach). Ponieważ intradomenowe routery muszą mieć tylko informację o routerach w swojej domenie, to ich algorytmy trasowania mogą być uproszczone, a co za tym idzie - ruch aktualizujący może zostać również zredukowany.

Algorytmy trasowania z inteligencją stacji i routera

W niektórych algorytmach trasowania zakłada się, że stacja nadawcza będzie określać całą trasę. Trasowanie takie jest nazywane trasowaniem źródłowym (Source Routing). W systemach trasowania źródłowego routery pracują jak urządzenia z mechanizmem pamiętaj i transportuj, przesyłając pakiety do następnego routera.

W innych algorytmach zakłada się, że stacje nic nie wiedzą o routerach. W tych wypadkach routery określają trasę w intersieci opierając się na własnych kalkulacjach. Mówimy, że w pierwszej metodzie stacje sieciowe mają inteligencję trasowania, a w metodzie drugiej inteligencję trasowania mają routery.

Intradomenowe i interdomenowe algorytmy trasowania

Niektóre algorytmy pracują tyko wewnątrz domen, inne zaś wewnątrz domen i między domenami. Natura tych algorytmów jest różna. To dlatego optymalny algorytm intradomenowy jest niekoniecznie optymalny jako algorytm interdomenowy.

Algorytmy działające według stanu łącza i na podstawie wektora odległości

Algorytmy działające według stanu łącza (pierwszą trasą jest trasa najkrótsza - Shortest Path First) przesyłają informację trasowania do wszystkich węzłów w intersieci. Jednak każdy router przesyła tylko porcję tabeli trasowania opisującej stan swoich łączy.

Algorytmy działające na podstawie wektora odległości (znane także jako algorytmy Bellmana-Forda) zwracają się do każdego routera w celu przesłania całych lub częściowych swoich tablic trasowania, ale tylko do swoich sąsiadów. W istocie algorytmy działające według stanu łącza wysyłają aktualizacje w mniejszych porcjach wszędzie, a algorytmy działające na podstawie wektora odległości wysyłają większe porcje aktualizacji tylko do routerów sąsiednich.

Algorytmy działające na podstawie stanu łącza dokonują konwergencji szybciej i dlatego są mniej podatne na powstawanie pętli trasowania niż algorytmy działające na podstawie wektora odległości. Z drugiej strony - algorytmy działające na podstawie stanu łącza potrzebują więcej mocy procesora i więcej pamięci niż algorytmy działające na podstawie wektora odległości. Dlatego algorytmy działające na podstawie stanu łącza mogą być droższe w implementacji i użytkowaniu. Mimo różnic oba typy algorytmów spełniają swoje zadania w wielu okolicznościach.

Miary trasowania

Tabele trasowania zawierają informacje używane przez programowanie w celu wybrania najlepszej trasy. Powstaje pytanie, jak tabele trasowania są zbudowane? Co stanowi specyfikę informacji zawartej w tabelach? W jaki sposób algorytmy trasowania decydują o tym, że jedna trasa jest preferowana bardziej niż inna?

Algorytmy trasowania używają wielu różnych miar do określania najlepszej trasy. Zaawansowane algorytmy trasowania mogą przy selekcji trasy opierać się na wielu miarach, tworząc z nich miarę wypadkową (hybrydową).

Rozróżnia się obecnie następujące miary trasowania:

• długość ścieżki,
• niezawodność,
• opóźnienie,
• szerokość pasma,
• obciążenie,
• koszt komunikacji.

Długość ścieżki jest najczęściej używaną miarą trasowania. Niektóre protokoły trasowania zezwalają administratorowi sieci na arbitralne przypisywanie kosztów każdemu łączu sieciowemu. W takim wypadku koszt ścieżki jest sumą kosztów związanych z każdym łączem składającym się na ścieżkę. Inne protokoły trasowania natomiast używają miary hop count, rozumianej jako liczba przejść pakietu przez urządzenia intersieciowe - np. routery - od stacji nadawczej do stacji odbiorczej.

Niezawodność, w kontekście algorytmów trasowania, odnosi się do skuteczności każdego łącza (określanego liczbą przekłamanych bitów). Niektóre łącza mogą ulegać uszkodzeniom częściej od innych. Po uszkodzeniu sieci niektóre łącza można naprawić szybciej i prościej niż inne.

Opóźnienie trasowania oznacza czas potrzebny do przesłania pakietu od stacji nadawczej do stacji odbiorczej w intersieci. Opóźnienie zależy od wielu czynników, m.in. od szerokość pasma, jakim dysponują pośredniczące łącza sieciowe, przeciążenia wszystkich pośredniczących łączy oraz fizycznej drogi, którą musi przepłynąć informacja. Jak widać, na opóźnienie składa się wiele różnych zmiennych, dlatego miara ta jest ważna i popularna.

Szerokość pasma odnosi się do dostępnej pojemności ruchu w określonym łączu.

Obciążenie to stopień zajętości zasobu sieciowego, np. routera. Obciążenie zależy od wielu czynników, np. stopnia wykorzystania procesora czy liczby pakietów przetwarzanych w czasie jednej sekundy.

Koszt komunikacji jest ważną miarą trasowania, przede wszystkim dlatego, że niektóre firmy nie dbają o wydajność. Nawet wtedy, gdy opóźnienia są duże, przesyłają pakiety przez własne linie zamiast korzystać z sieci publicznych, za które się płaci tylko w czasie ich używania.