Rozgromienie - Routing

Routing to proces wyboru ścieżki dla ruchu w sieci lub między lub między wieloma sieciami. Ogólnie rzecz biorąc, routing jest wykonywany w wielu typach sieci, w tym w sieciach z komutacją łączy , takich jak publiczna komutowana sieć telefoniczna (PSTN) i sieciach komputerowych , takich jak Internet .

W sieciach z przełączaniem pakietów routing jest procesem decyzyjnym wyższego poziomu, który kieruje pakiety sieciowe ze źródła do miejsca docelowego przez węzły sieci pośredniczącej za pomocą określonych mechanizmów przekazywania pakietów. Przekazywanie pakietów to przesyłanie pakietów sieciowych z jednego interfejsu sieciowego do drugiego. Węzły pośrednie to zazwyczaj urządzenia sieciowe , takie jak routery , bramy , zapory lub przełączniki . Komputery ogólnego przeznaczenia również przekazują pakiety i wykonują routing, chociaż nie mają specjalnie zoptymalizowanego sprzętu do tego zadania.

Proces routingu zwykle kieruje przekazywaniem na podstawie tablic routingu . Tabele routingu przechowują zapis tras do różnych miejsc docelowych w sieci. Tabele routingu mogą być określane przez administratora, poznawane przez obserwację ruchu w sieci lub budowane przy pomocy protokołów routingu .

Routing, w węższym znaczeniu tego słowa, często odnosi się do routingu IP i jest przeciwstawiony mostowaniu . Routing IP zakłada, że adresy sieciowe są ustrukturyzowane i że podobne adresy oznaczają bliskość w sieci. Adresy strukturalne pozwalają pojedynczemu wpisowi w tablicy routingu reprezentować trasę do grupy urządzeń. W dużych sieciach adresowanie strukturalne (routing, w wąskim znaczeniu) przewyższa adresowanie niestrukturalne (mostkowanie). Routing stał się dominującą formą adresowania w Internecie. Mostkowanie jest nadal szeroko stosowane w sieciach lokalnych .

Schematy dostaw

Schematy routingu różnią się sposobem dostarczania wiadomości:

• Unicast dostarcza wiadomość do jednego konkretnego węzła przy użyciu powiązania jeden do jednego między nadawcą a miejscem docelowym: każdy adres docelowy jednoznacznie identyfikuje pojedynczy punkt końcowy odbiorcy.
• Transmisja dostarcza wiadomość do wszystkich węzłów w sieci przy użyciu powiązania jeden-do-wszystkich ; pojedynczy datagram (lub pakiet ) od jednego nadawcy jest kierowany do wszystkich potencjalnie wielu punktów końcowych powiązanych z adresem rozgłoszeniowym . Sieć automatycznie replikuje datagramy w razie potrzeby, aby dotrzeć do wszystkich odbiorców w zasięgu emisji, czyli na ogół do całej podsieci sieci .
• Multiemisja dostarcza wiadomość do grupy węzłów, które wyraziły zainteresowanie otrzymaniem wiadomości przy użyciu powiązania jeden-do-wielu z wielu lub wiele-do-wielu z wielu ; datagramy są kierowane jednocześnie w jednej transmisji do wielu odbiorców. Multiemisja różni się od rozgłaszania tym, że adres docelowy wyznacza podzbiór, niekoniecznie wszystkie, dostępne węzły.
• Anycast dostarcza wiadomość do dowolnej osoby z grupy węzłów, zazwyczaj do najbliższego źródła przy użyciu powiązania jeden-do-jednego z wielu, w którym datagramy są kierowane do dowolnego pojedynczego członka grupy potencjalnych odbiorców, z których wszystkie są identyfikowane przez ten sam adres docelowy. Algorytm routingu wybiera z grupy jednego odbiornika, na podstawie którego jest najbliższy według pewnej miary odległości lub kosztu.

Unicast jest dominującą formą dostarczania wiadomości w Internecie. Ten artykuł koncentruje się na algorytmach routingu emisji pojedynczej.

Rozkład topologii

W przypadku routingu statycznego małe sieci mogą korzystać z ręcznie skonfigurowanych tabel routingu. Większe sieci mają złożone topologie, które mogą się szybko zmieniać, przez co ręczna budowa tablic routingu jest niewykonalna. Niemniej jednak, większość publicznej komutowanej sieci telefonicznej (PSTN) używa wstępnie obliczonych tablic routingu z trasami awaryjnymi, jeśli najbardziej bezpośrednia trasa zostanie zablokowana (patrz routing w PSTN ).

Routing dynamiczny próbuje rozwiązać ten problem, automatycznie konstruując tablice routingu w oparciu o informacje przenoszone przez protokoły routingu , co pozwala sieci działać niemal autonomicznie, zapobiegając awariom i blokadom sieci. W Internecie dominuje routing dynamiczny. Przykłady protokołów i algorytmów routingu dynamicznego obejmują protokół RIP ( Routing Information Protocol ), OSPF ( Open Shortest Path First ) i protokół EIGRP ( Enhanced Interior Gateway Routing Protocol ).

Algorytmy wektora odległości

Algorytmy wektora odległości wykorzystują algorytm Bellmana-Forda . To podejście przypisuje numer kosztu do każdego łącza między każdym węzłem w sieci. Węzły przesyłają informacje z punktu A do punktu B ścieżką, która skutkuje najniższym kosztem całkowitym (tj. sumą kosztów łącz pomiędzy używanymi węzłami).

Gdy węzeł uruchamia się po raz pierwszy, wie tylko o swoich bezpośrednich sąsiadach oraz o bezpośrednim koszcie związanym z dotarciem do nich. (Te informacje — lista miejsc docelowych, łączny koszt każdego z nich i następny przeskok do wysłania danych, aby się tam dostać — tworzą tablicę routingu lub tablicę odległości .) Każdy węzeł regularnie wysyła do każdego sąsiedniego węzła własną aktualną ocenę całkowitego kosztu dotarcia do wszystkich znanych mu miejsc docelowych. Sąsiednie węzły badają te informacje i porównują je z tym, co już wiedzą; wszystko, co stanowi ulepszenie tego, co już mają, wstawiają do własnej tabeli. Z biegiem czasu wszystkie węzły w sieci wykrywają najlepszy następny skok i całkowity koszt dla wszystkich miejsc docelowych.

Gdy węzeł sieci ulegnie awarii, wszelkie węzły, które wykorzystały go jako następny przeskok, odrzucają wpis i przekazują zaktualizowane informacje o routingu do wszystkich sąsiednich węzłów, które z kolei powtarzają proces. Ostatecznie wszystkie węzły w sieci otrzymują aktualizacje i odkrywają nowe ścieżki do wszystkich miejsc docelowych, które nie obejmują węzła dolnego.

Algorytmy stanu łącza

Podczas stosowania algorytmów stanu łącza, graficzna mapa sieci jest podstawowymi danymi używanymi dla każdego węzła. Aby utworzyć swoją mapę, każdy węzeł zalewa całą sieć informacjami o innych węzłach, z którymi może się połączyć. Każdy węzeł następnie niezależnie gromadzi te informacje na mapie. Korzystając z tej mapy, każdy router niezależnie określa najmniej kosztowną ścieżkę od siebie do każdego innego węzła przy użyciu standardowego algorytmu najkrótszych ścieżek , takiego jak algorytm Dijkstry . Wynikiem jest wykres drzewa zakorzeniony w bieżącym węźle, tak że ścieżka przez drzewo od korzenia do dowolnego innego węzła jest ścieżką o najniższym koszcie do tego węzła. To drzewo służy następnie do skonstruowania tablicy routingu, która określa najlepszy następny przeskok do przejścia z bieżącego węzła do dowolnego innego węzła.

Zoptymalizowany algorytm routingu stanu łącza

Algorytm routingu według stanu łącza zoptymalizowany dla mobilnych sieci ad hoc to zoptymalizowany protokół routingu według stanu łącza (OLSR). OLSR jest proaktywny; wykorzystuje komunikaty Hello i Topology Control (TC) do wykrywania i rozpowszechniania informacji o stanie łącza za pośrednictwem mobilnej sieci ad hoc. Używając wiadomości Hello, każdy węzeł wykrywa informacje o sąsiednich 2 przeskokach i wybiera zestaw przekaźników wielopunktowych (MPR). Protokół MPR odróżnia OLSR od innych protokołów routingu według stanu łącza.

Protokół ścieżka-wektor

Zarówno routing wektora odległości, jak i routing według stanu łącza to protokoły routingu wewnątrzdomenowego. Są używane wewnątrz systemu autonomicznego , ale nie pomiędzy systemami autonomicznymi. Oba te protokoły routingu stają się niewykonalne w dużych sieciach i nie mogą być używane w routingu międzydomenowym . Routing z wykorzystaniem wektora odległości jest niestabilny, jeśli w domenie jest więcej niż kilka przeskoków. Routing stanu łącza wymaga znacznych zasobów do obliczania tablic routingu. Powoduje również duży ruch z powodu powodzi.

Routing ścieżka-wektor jest używany do routingu międzydomenowego. Jest podobny do routingu z wykorzystaniem wektora odległości. Trasowanie wektora ścieżki zakłada, że ​​jeden węzeł (może być ich wiele) w każdym systemie autonomicznym działa w imieniu całego systemu autonomicznego. Ten węzeł nazywa się węzłem głośnika. Węzeł głośnika tworzy tablicę routingu i anonsuje ją do sąsiednich węzłów głośnika w sąsiednich systemach autonomicznych. Idea jest taka sama jak w przypadku routingu opartego na wektorze odległości, z tą różnicą, że tylko węzły głośnikowe w każdym systemie autonomicznym mogą się ze sobą komunikować. Węzeł głośnika ogłasza ścieżkę, a nie metrykę węzłów w swoim systemie autonomicznym lub innych systemach autonomicznych.

Algorytm routingu wektora ścieżki jest podobny do algorytmu wektora odległości w tym sensie, że każdy router graniczny anonsuje miejsca docelowe, do których może dotrzeć, do sąsiedniego routera. Jednak zamiast reklamować sieci pod względem miejsca docelowego i odległości do tego miejsca, sieci są reklamowane jako adresy docelowe i opisy ścieżek prowadzących do tych miejsc docelowych. Ścieżka, wyrażona w kategoriach domen (lub konfederacji), przez które przeszliśmy do tej pory, jest przenoszona w specjalnym atrybucie ścieżki, który rejestruje sekwencję domen routingu, przez które przeszły informacje o osiągalności. Trasa jest definiowana jako para między miejscem docelowym a atrybutami ścieżki do tego miejsca docelowego, a więc nazwa, trasowanie wektora ścieżki; Routery otrzymują wektor zawierający ścieżki do zbioru miejsc docelowych.

Wybór ścieżki

Wybór ścieżki obejmuje zastosowanie metryki routingu do wielu tras w celu wybrania (lub przewidzenia) najlepszej trasy. Większość algorytmów routingu używa jednocześnie tylko jednej ścieżki sieciowej. Routing wielościeżkowy, a zwłaszcza techniki routingu wielościeżkowego o równych kosztach , umożliwiają korzystanie z wielu alternatywnych ścieżek.

W sieciach komputerowych metryka jest obliczana przez algorytm routingu i może obejmować takie informacje, jak przepustowość , opóźnienie sieci , liczba przeskoków , koszt ścieżki , obciążenie, maksymalna jednostka transmisji , niezawodność i koszt komunikacji. Tablica routingu przechowuje tylko najlepsze możliwe trasy, podczas gdy bazy danych stanów łączy lub topologiczne mogą również przechowywać wszystkie inne informacje.

W przypadku nakładających się lub równych tras algorytmy biorą pod uwagę następujące elementy w kolejności priorytetów, aby zdecydować, które trasy zainstalować w tablicy routingu:

1. Długość prefiksu : pasujący wpis w tabeli tras z dłuższą maską podsieci jest zawsze preferowany, ponieważ dokładniej określa miejsce docelowe.
2. Metryka : podczas porównywania tras poznanych za pomocą tego samego protokołu routingu preferowana jest niższa metryka. Metryki nie mogą być porównywane między trasami poznanymi z różnych protokołów routingu.
3. Odległość administracyjna : podczas porównywania wpisów w tabeli tras z różnych źródeł, takich jak różne protokoły routingu i konfiguracja statyczna, mniejsza odległość administracyjna wskazuje na bardziej niezawodne źródło, a tym samym preferowaną trasę.

Ponieważ metryka routingu jest specyficzna dla danego protokołu routingu, routery wieloprotokołowe muszą korzystać z zewnętrznej heurystyki, aby wybierać między trasami poznanymi z różnych protokołów routingu. Na przykład routery Cisco przypisują każdej trasie wartość znaną jako odległość administracyjna , przy czym mniejsze odległości administracyjne wskazują trasy poznane na podstawie protokołu, który uważa się za bardziej niezawodny.

Administrator lokalny może skonfigurować trasy specyficzne dla hosta, które zapewniają większą kontrolę nad wykorzystaniem sieci, umożliwiają testowanie i zapewniają lepsze ogólne bezpieczeństwo. Jest to przydatne do debugowania połączeń sieciowych lub tablic routingu.

W niektórych małych systemach pojedyncze centralne urządzenie z wyprzedzeniem decyduje o pełnej ścieżce każdego pakietu. W niektórych innych małych systemach, którekolwiek urządzenie brzegowe wprowadza pakiet do sieci, decyduje z wyprzedzeniem o pełnej ścieżce tego konkretnego pakietu. W obu przypadkach urządzenie do planowania trasy musi znać wiele informacji o tym, jakie urządzenia są podłączone do sieci i jak są ze sobą połączone. Po uzyskaniu tych informacji może użyć algorytmu, takiego jak algorytm wyszukiwania A*, aby znaleźć najlepszą ścieżkę.

W szybkich systemach w każdej sekundzie przesyłanych jest tak wiele pakietów, że jedno urządzenie nie jest w stanie obliczyć pełnej ścieżki dla każdego pakietu. Wczesne szybkie systemy radziły sobie z przełączaniem obwodów , ustawiając ścieżkę raz dla pierwszego pakietu między źródłem a miejscem docelowym; późniejsze pakiety między tym samym źródłem a tym samym miejscem docelowym nadal podążają tą samą ścieżką bez ponownego obliczania, aż do zerwania obwodu . Późniejsze systemy o dużej szybkości wstrzykują pakiety do sieci bez żadnego urządzenia, które kiedykolwiek obliczałoby pełną ścieżkę dla pakietów.

W dużych systemach jest tak wiele połączeń między urządzeniami, a te połączenia zmieniają się tak często, że nie jest możliwe, aby jedno urządzenie nawet wiedziało, jak wszystkie urządzenia są ze sobą połączone, a tym bardziej nie oblicza pełnej ścieżki przez nie. Takie systemy zazwyczaj używają routingu następnego przeskoku .

Większość systemów używa deterministycznego algorytmu routingu dynamicznego . Gdy urządzenie wybiera ścieżkę do określonego miejsca docelowego, zawsze wybiera tę samą ścieżkę do tego miejsca, dopóki nie otrzyma informacji, które sprawią, że uzna, że ​​inna ścieżka jest lepsza.

Kilka algorytmów routingu nie wykorzystuje algorytmu deterministycznego do znajdowania najlepszego łącza dla pakietu, który ma dotrzeć ze swojego pierwotnego źródła do ostatecznego miejsca docelowego. Zamiast tego, aby uniknąć gorących punktów przeciążenia w systemach pakietowych, kilka algorytmów wykorzystuje algorytm losowy — paradygmat Valianta — który kieruje ścieżkę do losowo wybranego pośredniego miejsca docelowego, a stamtąd do rzeczywistego miejsca docelowego. W wielu wczesnych centralach telefonicznych, randomizer był często używany do wyboru początku ścieżki w wielostopniowej sieci szkieletowej .

W zależności od aplikacji, dla której wykonywany jest wybór ścieżki, można użyć różnych metryk. Na przykład w przypadku żądań internetowych można użyć ścieżek o minimalnym opóźnieniu, aby zminimalizować czas ładowania strony internetowej, lub w przypadku masowych transferów danych można wybrać najmniej wykorzystywaną ścieżkę, aby zrównoważyć obciążenie w sieci i zwiększyć przepustowość. Popularnym celem wyboru ścieżki jest zmniejszenie średniego czasu realizacji przepływów ruchu i całkowitego zużycia przepustowości sieci. Ostatnio zaproponowano metrykę wyboru ścieżki, która oblicza całkowitą liczbę bajtów zaplanowanych na krawędziach na ścieżkę jako metrykę wyboru. Udostępniono empiryczną analizę kilku wskaźników wyboru ścieżki, w tym tę nową propozycję.

Wielu agentów

W niektórych sieciach trasowanie komplikuje fakt, że żadna pojedyncza jednostka nie jest odpowiedzialna za wybór ścieżek; zamiast tego w wybieranie ścieżek lub nawet części pojedynczej ścieżki zaangażowanych jest wiele jednostek. Komplikacje lub nieefektywność mogą skutkować, jeśli podmioty te wybiorą ścieżki optymalizacji własnych celów, co może kolidować z celami innych uczestników.

Klasycznym przykładem jest ruch w systemie drogowym, w którym każdy kierowca wybiera trasę, która minimalizuje czas jego podróży. Przy takim trasowaniu trasy równowagi mogą być dłuższe niż optymalne dla wszystkich kierowców. W szczególności paradoks firmy Braess pokazuje, że dodanie nowej drogi może wydłużyć czas podróży wszystkich kierowców.

W modelu z jednym agentem, używanym na przykład do wyznaczania tras pojazdów sterowanych automatycznie (AGV) w terminalu, rezerwacje są dokonywane dla każdego pojazdu, aby zapobiec jednoczesnemu korzystaniu z tej samej części infrastruktury. Takie podejście jest również określane jako routing uwzględniający kontekst.

Internet jest podzielony na systemy autonomiczne (AS), takie jak dostawcy usług internetowych (ISP), z których każdy kontroluje trasy obejmujące jego sieć. Routing odbywa się na wielu poziomach. Najpierw ścieżki na poziomie AS są wybierane za pomocą protokołu BGP , który tworzy sekwencję AS, przez którą przepływają pakiety. Każdy AS może mieć do wyboru wiele ścieżek oferowanych przez sąsiednie AS. Te decyzje dotyczące routingu często korelują z relacjami biznesowymi z sąsiednimi AS, które mogą nie mieć związku z jakością lub opóźnieniem ścieżki. Po drugie, po wybraniu ścieżki na poziomie AS, często do wyboru jest wiele odpowiadających jej ścieżek na poziomie routera. Wynika to po części z tego, że dwóch dostawców usług internetowych może być połączonych wieloma połączeniami. Wybierając pojedynczą ścieżkę na poziomie routera, powszechną praktyką każdego dostawcy usług internetowych jest stosowanie routingu hot-potato : wysyłanie ruchu ścieżką, która minimalizuje odległość przez własną sieć dostawcy usług internetowych — nawet jeśli ta ścieżka wydłuża całkowitą odległość do miejsca docelowego.

Rozważmy na przykład dwóch dostawców usług internetowych, A i B . Każdy z nich jest obecny w Nowym Jorku , połączony szybkim łączem z opóźnieniem5  ms — i każdy ma obecność w Londynie połączoną łączem 5 ms. Załóżmy, że obaj dostawcy usług internetowych mają transatlantyckiej więzi, które łączą ich dwie sieci, ale „ogniwo zawiera opóźnienia 100 ms i B ” s ma opóźnienie 120 ms. Przy układaniu wiadomość ze źródła w A „s sieci Londynu do miejsca przeznaczenia w B ” sieci New York s, może wybrać, aby natychmiast wysłać wiadomość do B w Londynie. Oszczędza to A pracy związanej z wysyłaniem jej przez drogie łącze transatlantyckie, ale powoduje, że wiadomość doświadcza opóźnienia 125 ms, podczas gdy inna trasa byłaby o 20 ms szybsza.

Badanie pomiarowe tras internetowych z 2003 r. wykazało, że między parami sąsiednich dostawców usług internetowych ponad 30% ścieżek ma zawyżone opóźnienia z powodu routingu hot-potato, a 5% ścieżek jest opóźnionych o co najmniej 12 ms. Inflacja spowodowana wyborem ścieżki na poziomie AS, choć znaczna, została przypisana głównie brakowi mechanizmu BGP do bezpośredniej optymalizacji pod kątem opóźnień, a nie samolubnym politykom routingu. Zasugerowano również, że gdyby istniał odpowiedni mechanizm, dostawcy usług internetowych byliby skłonni współpracować w celu zmniejszenia opóźnień, zamiast korzystać z routingu hot-potato. Taki mechanizm został później opublikowany przez tych samych autorów, najpierw dla przypadku dwóch dostawców usług internetowych, a następnie dla przypadku globalnego.

Analiza tras

Ponieważ Internet i sieci IP stały się kluczowymi narzędziami biznesowymi, wzrosło zainteresowanie technikami i metodami monitorowania stanu routingu w sieci. Nieprawidłowy routing lub problemy z routingiem powodują niepożądane pogorszenie wydajności, trzepotanie lub przestoje. Monitorowanie tras w sieci odbywa się za pomocą narzędzi i technik analizy tras .

Scentralizowany routing

W sieciach, w których dostępna jest logicznie scentralizowana kontrola nad stanem przekazywania, na przykład przy użyciu sieci definiowanej programowo , można stosować techniki routingu mające na celu optymalizację globalnych i ogólnosieciowych metryk wydajności. Zostało to wykorzystane przez duże firmy internetowe, które obsługują wiele centrów danych w różnych lokalizacjach geograficznych podłączonych za pomocą prywatnych łączy optycznych, których przykłady obejmują Global WAN firmy Microsoft, Express Backbone firmy Facebook i B4 firmy Google. Globalne metryki wydajności do optymalizacji obejmują maksymalizację wykorzystania sieci, minimalizację czasu zakończenia przepływu ruchu i maksymalizację ruchu dostarczonego przed określonymi terminami. Zwłaszcza minimalizacja czasu realizacji przepływu przez prywatną sieć WAN nie przyciągnęła dużej uwagi społeczności naukowej. Jednak wraz z rosnącą liczbą firm, które obsługują globalnie rozproszone centra danych połączone za pomocą prywatnych sieci między centrami danych, prawdopodobnie nastąpi wzrost wysiłków badawczych w tej dziedzinie. Niedawne prace nad skróceniem czasów realizacji przepływów przez prywatną sieć WAN omawiają modelowanie routingu jako problem optymalizacji grafów poprzez przesuwanie wszystkich kolejek do punktów końcowych. Autorzy proponują również heurystykę, aby skutecznie rozwiązać problem, poświęcając znikomą wydajność.

Zobacz też

Bibliografia

Dalsza lektura

Zewnętrzne linki

• Problem odliczania do nieskończoności
• „Cechy stabilności” to sposoby na uniknięcie problemu „odliczania do nieskończoności”.
• Analizy przypadków Cisco IT dotyczące routingu i przełączania
• „Routing IP i podsieci” . www.eventhelix.com . Pobrano 28.04.2018 .