TCP Congestion Control: A Deep Dive

Najkrótsza ścieżka jako pierwsza: Algorytm Dijkstry

Każdy router w internecie, w istocie, rozwiązuje problem najkrótszej ścieżki z jednego źródła na grafie: węzłami są routery, krawędziami są połączenia, a wagą krawędzi jest koszt (często związany z przepustowością lub skonfigurowanym metryką). Algorytm Dijkstry, opublikowany przez Edsgera Dijstra w 1959 roku, znajduje najtańszą ścieżkę od jednego routera do każdego innego routera w sieci o nieujemnych wagach, i robi to bez potrzeby sprawdzania ścieżek, które są już udowodniono gorsze niż te znalezione wcześniej.

dist[źródło] = 0; dist[pozostałe] = nieskończoność zwiedzono = {} pętla: jeśli istnieją niezbadane węzły: u = niezbadany węzeł o najmniejszym dist[u] oznacz u jako zwiedzony dla każdego sąsiada v u: jeśli dist[u] + waga(u,v) < dist[v]: dist[v] = dist[u] + waga(u,v) parent[v] = u Demonstracja na żywo · Algorytm Dijkstry znajduje najkrótsze ścieżki w miarę zmiany kosztów połączeń● NA ŻYWO Krok przyłaszczyłowy — zawsze rozszerzaj najbliższego niezbadanego węzła następnego — jest dowodem tylko wtedy, gdy wagi są nieujemne: po ustabilizowaniu węzła, żadna późniejsza relaksacja przez niezbadany (koniecznie dalszy) węzeł nie może kiedykolwiek wygenerować krótszej ścieżki do niego. Zaimplementowany z użyciem koperty binarnej lub Fibonacciego dla kolejki priorytetowej, działa w czasie O((V+E) log V), wystarczająco szybko, aby ponownie obliczać trasy dla sieci o tysiącach routerów przy każdej zmianie topologii.

dist[source] = 0;  dist[all others] = infinity
visited = {}
while unvisited nodes remain:
    u = unvisited node with the smallest dist[u]
    mark u visited
    for each neighbour v of u:
        if dist[u] + weight(u,v) < dist[v]:
            dist[v] = dist[u] + weight(u,v)
            prev[v] = u                       // for path reconstruction

OSPF: Algorytm Dijkstry w pojedynczej sieci

OSPF (Open Shortest Path First) to algorytm Dijkstry realizowany w praktyce, w obrębie pojedynczego obszaru autonomicznego (firmy, uczelni lub sieci dostawcy usług internetowych). Każdy router rozsyła do innych swoich lokalnych stanów powiązanych z linkami – czyli informacji o sąsiadach i kosztach połączeń – tak aby każdy router otrzymał identyczną mapę całej topologii. Następnie niezależnie na tej mapie uruchamiany jest algorytm Dijkstry, który oblicza jego własny stół routingu. Koszt jest zazwyczaj odwrotny do przepustowości, dlatego OSPF naturalnie preferuje połączenie 10 Gbps w stosunku do 100 Mbps, nawet jeśli ścieżka o przepustowości 100 Mbps ma mniej hopów.

BGP: routowanie między sieciami, a nie tylko najtańsza ścieżka

Pomiędzy autonomic systemami – pomiędzy dostawcami usług internetowych (ISP), zasadniczo – routowanie internetu polega na protokole BGP (Border Gateway Protocol), ponieważ ISP nie chcą technicznie najkrótszej ścieżki, a ścieżki, które uwzględniają relacje biznesowe: ruch klienta tranzytowego jest preferowany w stosunku do ruchu bezpłatnego partnera, który z kolei jest preferowany w stosunku do płatnej trasy tranzytowej konkurenta. BGP to protokół wektorowy ścieżek, a nie stan linku: każdy router ogłasza pełną trasę AS, którą by użył, a każde inne urządzenie stosuje politykę lokalną w celu wyboru spośród konkurencyjnych ogłoszeń, a nie współdzielonej funkcji kosztów.

Co się dzieje, gdy zniknie połączenie

Przerwanie połączenia w obrębie domeny OSPF spowoduje, że każdy router przekaże ponownie nowe dane o stanie linku, uruchomi ponownie Dijkstry i skonwertuje się na nowo na drzewo najkrótszej ścieżki – zwykle poniżej jednej sekundy na nowoczesnym sprzęcie, choć zalewanie i ponowne obliczenia nie są natychmiastowe, co stanowi idealnie okno czasowe dla pojawienia się tymczasowych pętli routingu, ponieważ różne routery mogą krótko posiadać niespójne widoki topologii. Konwergencja BGP po awarii jest znacznie wolniejsza i może trwać minuty, ponieważ wycofania ścieżek AS muszą propagować hop po hopie przez cały internet, a routery stosują tłumienie, aby uniknąć wzmacniania fal routingu do globalnej niestabilności.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Network Packet Routing i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.