Routage

Les réseaux sont reliés entre eux par des routeurs caractérisés par plusieurs interfaces. Les routeurs sont chargés de l'acheminement des paquets IP. Les paquets IP portent dans leur en-tête IP des adresses IP source et de destination. Les routeurs décident de la route à faire suivre aux paquets IP par consultation d'une table de routage. La création et la mise à jour des tables de routage sont des opérations cruciales dans les réseaux. La table de routage peut être statique (configurée manuellement) ou dynamique (calculée par un protocole de routage).

Algorithme de routage

Le rôle de l'algorithme de routage est de choisir un chemin optimal suivi par les paquets à acheminer en utilisant la topologie du sous-réseau et en fonction de critères donnés (métriques). Le chemin optimal n'est pas forcément le plus court : il peut s'agir du chemin au délai le plus court, du chemin le plus sécurisé, du chemin le moins cher, ou tout simplement du chemin utilisant le moins de sauts.

Centralisé vs distribué

En routage centralisé, un nœud central se charge de collecter les informations sur chaque lien (on/off, utilisation, capacité) et de calculer la table de routage pour chaque nœud du réseau (envisageable lorsque le réseau est administré de façon centralisée et qu'il n'est pas trop grand). En routage décentralisé, les routeurs coopèrent selon un protocole de routage distribué de façon à construire des tables de routage cohérentes (Internet utilise le routage distribué pour des raisons de taille).

À la source vs saut par saut

En routage à la source, un paquet peut transporter toute sa route (i.e. la liste, éventuellement exhaustive, des nœuds entre sa source et sa destination). Les options de routage par la source d'IPv4 et l'en-tête de routage d'IPv6 permettent du routage à la source. En routage saut par saut, un paquet ne véhicule que l'adresse de la destination.

Déterministe vs stochastique

En routage déterministe, tous les paquets vers une même destination sont retransmis au même nœud suivant. En routage stochastique, chaque routeur maintient plusieurs nœuds aval pour une même destination, ce qui permet de limiter les oscillations de trafic. (Internet utilise le routage déterministe, car cela permet de minimiser le déséquencement des paquets).

À chemin unique vs à chemin multiple

En routage à chemin multiple, chaque routeur maintient une route principale et des routes alternatives qu'il peut utiliser en cas d'indisponibilité de la route principale.

Statique vs dynamique

En routage dynamique, le choix de la route dépend de la mesure actuelle de l'état du réseau. Le routage dynamique peut donc aider au contrôle de congestion mais peut aussi introduire des oscillations.

Algorithme de Dijkstra

Les protocoles à état de liens (comme OSPF) calculent les plus courts chemins avec l'algorithme de Dijkstra :

fonction Dijkstra(G: graphe à arcs pondérés, s: sommet):(fonction V_G -> R, fonction V_G -> V_G)
    (d,père) = relacherInit(G,s)
    Y = V_G

    tant que Y n'est pas l'ensemble vide faire
        extraire un élément u de Y de valeur d minimale
        pour chaque successeur v de u faire
            si v appartient à Y alors
                relacher(u,v,G,d,père)
    retourner(d,père)

procédure relacherInit(G: graphe à arcs pondérés, s: sommet):(tableau V_G -> R, tableau V_G -> V_G)
    d = tableau indicé par V_G initialisé à l'infini
    père = tableau indicé par V_G initialisé à NULL
    d[s] = 0
    retourner (d,père)

procédure relacher(u:sommet, v:sommet, G:graphe à arcs pondérés, d: tableau V_G -> R, père : tableau V_G -> V_G)
    si d(v) > d(u) + poids(u,v)
        d[v] = d(u) + poids(u,v)
        père[v] = u

La complexité est en $O((a+n)\log n)$ avec un tas binaire, où $a$ est le nombre d'arcs et $n$ le nombre de sommets, et en $O(a + n \log n)$ avec un tas de Fibonacci.