Skip to main content

Le routage dans les réseaux

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 / MAJ des tables de routages est une opération importante et cruciale dans les réseaux. La table de routage peut être manuelle, statique ou dynamique.

Algorithme de routage​

Le rôle de l'algorithme de routage est de chosir 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). L'utilisation du chemin optimal, qui 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 noeud central se charge de collecter les informations sur chaque lien (on/off, utilisation capacité) et de calculer la table de routage pour chaque noeud 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 routages consistances. (Internet préfère le distribué pour des raisons de taille)

À la source vs saut par saut​

En routage à la source, un paquet peut transporter toute sa route (ie la liste éventuellement exhaustive de tous les noeuds entre sa source et sa destination). L'utilisation des options IPv4 et IPv6 impliquent 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étemriniste, tous les paquets vers une même destination seront retransmis au même noeud suivant. En routage stochastique, chaque routeur maintient plusieurs noeuds aval pour une même destination, ce qui permet de limiter les oscillations de trafic. (Internet utilise le 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és de la route principale

Statique vs dynamique​

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

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 faire
                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

O((a+n)log n) => a = nbr arcs , n = nbr sommets

(O(a + s log n)) si tas de fibo

0%