Rozpatrując Internet pod kątem zarządzania ruchem, był on do niedawna środowiskiem usług tzw. best effort (realizuj jak najlepiej potrafisz). Bardzo małe właściwości zarządzania ruchem istniały w sieciach IP dla zarządzania zróżnicowanych kolejek i ustalania harmonogramu usług dla pakietów należących do różnych klas usług.

Rozpatrując Internet pod kątem sterowania routingiem, to stosuje on zdecentralizowane protokoły routingu wewnątrzdomenowego. Są one wysoce skalowalne i elastyczne, jednakże bazują na prostych algorytmach selekcji ścieżek oraz mają małą funkcjonalność dla elastycznego sterowania procesem wyboru ścieżek.

1. Trasowanie adaptacyjne

Wczesna sieć ARPANET poznała ważność trasowania adaptacyjnego, gdzie decyzje o routingu bazowały na aktualnym stanie sieci. Podejście do problemu routingu z minimalnymi opóźnieniami zaowocowało przekazywaniem pakietów do ich miejsca przeznaczenia wzdłuż ścieżki, dla której szacunkowy czas tranzytu był najmniejszy. Każdy węzeł przechowywał tabelę opóźnień sieciowych, reprezentującą szacunkowe opóźnienia jakie pakiet mógł doznać wzdłuż danej ścieżki do swojego przeznaczenia. Tabela minimalnych opóźnień była transmitowana przez węzeł okresowo do jego sąsiadów. Najkrótsza ścieżka, w myśl ilości skoków, była także rozgłaszana, aby dać spójną informację.

Wadą tego rozwiązania jest to, że dynamiczne metryki łączy miały tendencje do tworzenia tzw. magnesów ruchu, powodujących natłok w sieci, który przemieszczał się z jednej miejsca w sieci do innego, doprowadzających do wahań i niestabilności sieci.

2. Trasowanie dynamiczne w sieci Internet

Internet, który rozwinął się z sieci ARPANET, zaadoptował algorytm routowania dynamicznego z rozproszonym sterowaniem w celu wyznaczenia ścieżki, po której pakiety powinny podążać do swojego przeznaczenia. Algorytm routingu jest adaptacją algorytmu najkrótszej ścieżki (ang. shortest path algorithm), gdzie koszty bazują na metrykach łączy (rys.1). Metryki łącza mogą być opierane na wielkościach statycznych lub dynamicznych. Metryki łączy bazujące na wielkościach statycznych mogą być przypisane administracyjnie według kryteriów lokalnych. Natomiast metryki tworzone w oparciu o wielkości dynamiczne mogą być funkcją miar natłoku sieci, takich jak opóźnienia lub utrata pakietów.

Rys. 1 Routing shortest path wewnątrz systemu autonomicznego bazujący na OSPF/IS-IS w oparciu o wagi łączy.

Szybko dostrzeżono, że przypisanie statycznych metryk było nieadekwatne, ponieważ łatwo prowadziło do niekorzystnych scenariuszy, w których pewne łącza stawały się nadmiernie obciążone (występował na nich natłok), natomiast pozostałe były lekko obciążone. Jedną z wielu przyczyn nieodpowiedniego przypisania statycznych metryk łączy było to, że czynność ta była robiona bez brania pod uwagę matrycy ruchu w sieci. W związku z tym, protokoły routingu nie brały pod uwagę atrybutów ruchu i ograniczeń przepustowości w trakcie podejmowania decyzji o routingu. W efekcie tego, koncentracja ruchu była lokalizowana we fragmentach infrastruktury sieciowej i potencjalnie powodowała natłok w sieci. Nawet, jeśli metryki łączy były przypisane zgodnie z matrycą ruchu, to wciąż pojawiało się niezrównoważone obciążenie w sieci z powodu wielu czynników, takich jak np.:

- zasoby sieciowe mogą nie być umieszczone w optymalnych miejscach z perspektywy routingu

- przewidywania błędnych wielkości ruchu i/lub dystrybucji ruchu

- dynamiki w matryce ruchu spowodowanej czasową naturą zachowań ruchu, zmianami reguł BGP (ang. Border Gateway Protocol), itp.

Ta niedostateczność tradycyjnych, wewnętrznych systemów routingu jest jednym z czynników zainteresowania się technologią zorientowaną na ścieżki z jawnym routingiem (ang. explicit routing) i zawężonym routingu (ang. constraint-based routing), jaką jest MPLS (ang. MultiProtocol Label Switching).

3. Trasowanie ToS

Trasowanie Type-of-Service (ToS) angażuje różne trasy biegnące do tego samego przeznaczenia z selekcją zależną od pola ToS pakietu IP. Klasy ToS mogą być sklasyfikowane jako małe opóźnienia i duża przepływność. Każde łącze jest skojarzone z wieloma kosztami łącza i każde łącze jest używane do obliczenia trasy dla konkretnego ToS. Dla każdego ToS obliczane jest oddzielne drzewo najkrótszych ścieżek. Algorytm najkrótszej ścieżki musi być uruchomiony dla każdego ToS, powodując w rezultacie kosztowne obliczenia. Klasyczny routing oparty o ToS jest teraz przestarzały, a pole ToS w nagłówku IP zostało zastąpione przez pole DS (Diffserv). Trudno jest osiągnąć efektywną inżynierię ruchu (traffic engineering) w oparciu o routing ToS, gdyż wciąż każda klasa zależy wyłącznie od routingu najkrótszej ścieżki, który doprowadza do lokalizacji koncentracji ruchu wewnątrz sieci.

4. Technika Equal Cost Multi-Path

Następną techniką, która próbuje zniwelować braki w systemie routingu bram wewnątrzdomenowych z algorytmem SPF (ang. Shortest Path First) jest Equal Cost Multi-Path (ECMP). W klasycznym algorytmie SPF, jeśli istnieją dwie lub więcej najkrótszych ścieżek do danego przeznaczenia, algorytm wybierze tylko jedną z nich. Został on trochę zmodyfikowany w ECMP, bo jeśli istnieją dwie lub więcej najkrótszych ścieżek pomiędzy dwoma węzłami, to ruch pomiędzy tymi węzłami jest rozdzielany między wieloma ścieżkami o jednakowym koszcie. Dystrybucja ruchu pomiędzy ścieżkami o równym koszcie jest zwykle wykonywana na jeden z dwóch sposobów:

- w oparciu o pakiety w sposób cykliczny lub

- w oparciu o strumień stosując mieszanie adresów IP źródłowych i przeznaczenia i jeśli to możliwe innych pól nagłówka IP.

Pierwszy sposób może powodować nieuporządkowany przepływ pakietów, a drugi jest zależny od ilości i dystrybucji strumieni. Podział obciążenia oparty o strumienie może być niemożliwy do przewidzenia w sieciach korporacyjnych, gdzie liczba strumieni jest relatywnie mała i mniej różnorodna (np. mieszanie może być nierównomierne), ale jest ogólnie efektywny w rdzeniach sieci publicznych, gdzie liczba strumieni jest olbrzymia i różnorodna.

W ECMP koszty łączy są statyczne a ograniczenia pasma nie są brane pod uwagę, wobec czego ECMP próbuje rozdzielać ruch, tak równomiernie jak jest to możliwe, między ścieżki o równym koszcie, niezależnie od statusu natłoku każdej ścieżki. W rezultacie, jeśli dane są dwie ścieżki o równym koszcie, to jest możliwe, że jedna ze ścieżek będzie bardziej zatłoczona niż druga. Inną wadą ECMP jest to, że podział obciążenia nie może być osiągnięty na wielu ścieżkach, które nie mają identycznego kosztu.

5. Model nakładkowy

W modelu nakładkowym, czyli sieci z połączeniami wirtualnymi, takimi jak w ATM (ang. Asynchronous Transfer Mode), FR (ang. Frame Relay) lub WDM (ang. Wavelength Division Multiplexing), możliwe jest zestawianie połączeń wirtualnych, pomiędzy routerami, które są usytuowane na brzegach sieci połączeń wirtualnych. W tym trybie, dwa routery, które są połączone przez połączenie wirtualne, widzą bezpośrednie sąsiedztwo pomiędzy sobą, niezależnie od drogi fizycznej, obranej przez połączenie wirtualne w sieci ATM, FR lub WDM. W istocie, model nakładkowy rozprzęga logiczną topologię widzianą przez routery od topologii fizycznej, zarządzanej przez sieci ATM, FR lub WDM (rys.2). Model nakładkowy, bazujący na ATM i FR, umożliwia administratorowi sieci lub automatowi zastosowanie inżynierii ruchu (traffic engineering) dla realizacji optymalizacji ścieżek, dzięki rekonfiguracji i ponownemu rozmieszczaniu połączeń wirtualnych.

Rys. 2 Model nakładkowy sieci ATM.

Tak więc bardziej obciążone połączenia wirtualne lub mniej optymalne łącza fizyczne mogą być przekierowane na mniej zatłoczone lub bardziej zoptymalizowane łącza. W modelu tym, inżynieria ruchu (traffic engineering) może być również zastosowana do ustalania relacji między parametrami ruchu (np., PCR, SCR i MBS w ATM) połączenia wirtualnego a aktualnym ruchem, przenoszonym przez to połączenie. Relacje te moga być ustalane w oparciu o znane lub zaprojektowane profile ruchu.

Model nakładkowy wykorzystujący IPoA (ang. IP over ATM) wymaga zarządzania dwoma odseparowanymi sieciami z różnymi technologiami (IP i ATM), powodując zwiększoną zawiłość eksploatacji i koszt. W pełni kratowym modelu nakładkowym (struktura mesh), każdy router byłby połączony z każdym innym routerem w sieci, w związku z tym całkowita liczba sąsiedztw jest kwadratem liczby routerów.

6. Trasowanie oparte na ograniczeniach

Trasowanie oparte na ograniczeniach (ang. Constrained-Based Routing) ma związek z klasą systemów routingu, które wyznaczają drogę poprzez sieć, spełniającą określony zbiór ograniczeń i wymagań. Można ogólnie stwierdzić, że constrained-based routing jest w stanie optymalizować wydajność całej sieci, jednocześnie minimalizując koszty. Ograniczenia i specyficzne wymagania mogą być narzucane przez samą sieć lub przez reguły administracyjne. Ograniczenia mogą zawierać szerokość pasma, liczbę skoków, opóźnienia oraz instrumenty polityk (reguł) takie jak atrybuty klas zasobów. Ograniczenia mogą również zawierać atrybuty specyficzne dla domen określonych technologii sieciowych i kontekstów, które narzucają restrykcje na obszar rozwiązań funkcji routingu. Technologie zorientowane na ścieżki, takie jak MPLS mają zaimplementowany constraint-based routing, który jest atrakcyjny dla publicznych sieci IP.

Koncepcja constraint-based routingu wewnątrz kontekstu wymagań inżynierii ruchu (traffic engineering) MPLS w sieciach IP została zdefiniowana w. Odmiennie niż QoS, który generalnie ma zastosowanie do strumieni ruchu, constraint-based routing jest odpowiedni do ruchu agregowanego jak i do strumieni ruchu i może być przedmiotem szerokiej gamy ograniczeń, mogących zawierać polityki restrykcji.