Algorytmy routingu
W tym podrozdziale omawiamy algorytmy routingu, których zadaniem jest ustalanie w sieci routerów dobrych ścieżek (tras) od nadawców do odbiorców. „Dobrą” ścieżką jest zwykle ta o najniższym koszcie. Zobaczysz jednak, że w praktyce istotne są też praktyczne kwestie, na przykład polityczne (takie jak „router x należący do organizacji Y nie powinien przekazywać żadnych pakietów pochodzących z sieci należącej do organizacji Z”). Warto zauważyć, że niezależnie od tego, czy w aspekcie sterowania stosowane jest podejście z poziomu routerów, czy logicznie scentralizowane, zawsze potrzebna jest ściśle zdefiniowana sekwencja routerów, przez które pakiet przechodzi w drodze z hosta nadawczego do odbiorczego. Dlatego algorytm routingu wyznaczający te ścieżki jest niezwykle istotny i stanowi następnego kandydata do listy 10 najważniejszych elementów sieci.
Do formułowania problemów związanych z routingiem stosuje się graf. Graf G = (N, E) jest zestawem N węzłów i zbiorem E gałęzi, z których każda jest parą węzłów należących do zestawu N. Z punktu widzenia funkcji routingu warstwy sieciowej węzły grafu reprezentują routery (podejmują decyzje związane z przekazywaniem pakietów), natomiast gałęzie łączące węzły identyfikują fizyczne łącza między routerami.
Tego typu abstrakcyjny model sieci komputerowej zdefiniowany przy użyciu grafu został przedstawiony na rysunku 5.3. Aby zapoznać się z kilkoma grafami reprezentującymi topologie rzeczywistych sieci, należy skorzystać ze źródeł [Dodge 2016; Cheswick 2000]. W źródłach [Zegura 1997; Faloutsos 1999; Li 2004] wyjaśniono, jak dobrze internet modelują różne modele oparte na grafach.
Rysunek 5.3. Abstrakcyjny model sieci komputerowej stworzony za pomocą grafu Jak widać na rysunku 5.3, gałąź posiada też wartość reprezentującą koszt gałęzi.
Zwykle koszt gałęzi może odzwierciedlać długość odpowiedniego fizycznego łącza (na przykład koszt łącza transoceanicznego może być wyższy niż naziemnego łącza o krótkim zasięgu), jego szybkość lub wartość pieniężną powiązaną z łączem. Na potrzeby naszego omówienia po prostu z góry przyjmiemy koszt gałęzi bez zastanawiania się, w jaki sposób go wyznaczono. Dla dowolnej gałęzi (x, y) zbioru E jako c(x, y) oznaczymy koszt gałęzi znajdującej się między węzłami x i y. Jeśli para (x, y) nie należy do zbioru E, wtedy c(x, y) = ?. Ponadto w omówieniu rozpatrujemy wyłącznie grafy nieskierowane (gałęzie takich grafów nie posiadają kierunku). W związku z tym gałąź (x, y) jest tą samą gałęzią, co gałąź (y, x), a ponadto c(x, y) = c(y, x). Omawiane algorytmy można jednak łatwo rozszerzyć o obsługę grafów skierowanych, gdzie z poszczególnymi kierunkami związane są inne koszty. Węzeł y jest nazywany sąsiadem węzła x, gdy gałąź (x, y) należy do zbioru E.
Biorąc pod uwagę, że z różnymi gałęziami grafu powiązano koszt, naturalnym celem algorytmu routingu jest identyfikacja najtańszych ścieżek poprowadzonych między węzłami źródłowymi i docelowymi. Aby zagadnienie to było bardziej precyzyjne, należy przypomnieć, że ścieżka grafu G = (N, E) jest sekwencją węzłów (x1, x2,…, xp), taką, że każda para (x1, x2), (x1, x3),…, (xp–1, xp) identyfikuje gałąź zbioru E. Koszt ścieżki (x1, x2,…, xp) jest po prostu sumą kosztu wszystkich gałęzi ścieżki, mającą postać c(x1, x2)+c(x2, x3)+ … +c(xp–1, xp). W przypadku dowolnych dwóch węzłów x i y istnieje między nimi wiele ścieżek, z których każda posiada koszt. Jedna lub więcej spośród tych ścieżek jest nazywanych ścieżkami najmniejszego kosztu. W związku z tym problem najmniejszego kosztu jest oczywisty. Polega na znalezieniu między węzłem źródłowym i docelowym ścieżki o najniższym koszcie. Przykładowo, widoczna na rysunku 5.3 ścieżka o najmniejszym koszcie (u, x, y, w) poprowadzona między węzłem źródłowym u i węzłem docelowym w posiada koszt o wartości 3. Warto zauważyć, że jeśli wszystkie gałęzie grafu mają taki sam koszt, ścieżka o najmniejszym koszcie jest jednocześnie najkrótszą ścieżką (posiada najmniejszą liczbę łączy znajdujących się między węzłem źródłowym i docelowym).
W ramach prostego ćwiczenia spróbujmy określić ścieżkę o najmniejszym koszcie poprowadzoną na rysunku 5.3 od węzła u do węzła z, a następnie przez chwilę zastanówmy się, jak ścieżkę wyznaczono. Większość osób zidentyfikuje ścieżkę między węzłami u i z przez przyglądnięcie się rysunkowi i nakreślenie kilku tras biegnących między tymi dwoma węzłami, a następnie stwierdzenie, że wybrana ścieżka spośród wszystkich możliwych posiada najmniejszy koszt. (Czy Czytelnik sprawdził wszystkie 17 ścieżek poprowadzonych między węzłami u i z? Raczej nie!). Tego typu wyznaczanie ścieżki jest przykładem scentralizowanego algorytmu routingu. Dysponując pełną informacją na temat sieci, algorytm routingu został uruchomiony w jednym miejscu (w mózgu).
Jeden ze sposobów klasyfikowania algorytmów routingu dzieli je na globalne lub zdecentralizowane.
Globalny algorytm routingu. Tego typu algorytm określa ścieżkę o najmniejszym koszcie między węzłem źródłowym i docelowym za pomocą pełnej globalnej wiedzy na temat sieci. Oznacza to, że jako dane wejściowe algorytm traktuje połączenia między wszystkimi węzłami, a także koszt wszystkich łączy. W związku z tym jest wymagane, aby przed przeprowadzeniem obliczeń algorytm w jakiś sposób uzyskał te informacje. Same obliczenia mogą być wykonane w jednym miejscu (na przykład w logicznie scentralizowanym kontrolerze, tak jak na rysunku 5.2) lub być replikowane w odpowiedzialnym za routing komponencie w każdym routerze (tak jak na rysunku 5.1). W tym przypadku kluczowym elementem rozróżniającym jest to, czy algorytm routingu dysponuje kompletną informacją na temat połączeń i kosztu łączy. W praktyce algorytmy posiadające globalne informacje dotyczące stanu często są nazywane algorytmami stanu łącza. Wynika to stąd, że algorytmy te muszą znać koszt każdego łącza sieci. Algorytmy stanu łącza zostaną omówione w punkcie 5.2.1.
Zdecentralizowany algorytm routingu. W przypadku tego typu algorytmu wyznaczanie ścieżki o najmniejszym koszcie przebiega w sposób iteracyjny i rozproszony. Żaden węzeł nie posiada pełnej informacji na temat kosztu wszystkich łączy sieciowych. Początkowo każdy węzeł dysponuje jedynie wiedzą dotyczącą kosztu łączy, które są do niego bezpośrednio podłączone. Za pomocą iteracyjnego procesu, polegającego na obliczaniu i wymienianiu się informacjami z sąsiednimi węzłami (węzły znajdujące się na drugim końcu łączy podłączonych do rozpatrywanego węzła), węzeł stopniowo wyznacza ścieżkę o najmniejszym koszcie prowadzącą do węzła docelowego lub ich grupy. Zdecentralizowany algorytm routingu, który zostanie omówiony w punkcie 5.2.2, jest nazywany algorytmem wektora odległości, ponieważ każdy węzeł utrzymuje wektor oszacowań kosztu (odległości) łączy prowadzących do pozostałych węzłów sieci. Tego rodzaju zdecentralizowane algorytmy z interaktywną wymianą komunikatów między sąsiednimi routerami są w bardziej naturalny sposób dopasowane do aspektów sterowania, gdzie routery bezpośrednio komunikują się między sobą (zob. rysunek 5.1).
Drugi sposób ogólnej klasyfikacji algorytmów routingu dzieli je na statyczne i dynamiczne. W przypadku statycznych algorytmów routingu trasy bardzo wolno zmieniają się w czasie. Często jest to wynik interwencji użytkownika (na przykład ręcznej edycji tabeli przekazywania routera). Dynamiczne algorytmy routingu modyfikują trasy wraz ze zmianą obciążenia sieci lub jej topologii. Dynamiczny algorytm może być uaktywniany okresowo lub bezpośrednio w odpowiedzi na zmianę topologii lub kosztu łącza. Choć dynamiczne algorytmy lepiej reagują na zmiany pojawiające się w sieci, są też bardziej wrażliwe na problemy, takie jak pętle routingu i wahania związane z trasami.
Trzeci sposób klasyfikowania algorytmów routingu dzieli je na wrażliwe i niewrażliwe na obciążenie. W algorytmach wrażliwych na obciążenie koszt łączy zmienia się dynamicznie, aby uwzględnić aktualny poziom przeciążenia łącza. Jeśli z łączem, które w danej chwili jest przeciążone, powiązano wysoki koszt, algorytm routingu będzie starał się wybrać trasy omijające przeciążone łącze. Choć pierwsze algorytmy routingu sieci ARPAnet były wrażliwe na obciążenie [McQuillan 1980], pojawiło się kilka trudności z nimi związanych [Huitema 1998]. Obecnie stosowane internetowe algorytmy routingu (na przykład RIP, OSPF i BGP) są niewrażliwe na obciążenie, ponieważ koszt łącza nie odzwierciedla wyraźnie jego aktualnego (lub niedawnego) poziomu przeciążenia.
Opracowano na podstawie: