Protocoles de routage

I/ Tables de routage

1) Tables

Voici des tables de routage : pour chacun des routeurs A, B, C, D, E, F, G elles indiquent par qui passer pour amener un message à un routeur donné.

Table de A
Pour aller àpasser par
AA
BB
CC
DD
EE
FB
GD
Table de B
Pour aller àpasser par
AA
BB
CC
DA
EA
FF
GF
Table de C
Pour aller àpasser par
AA
BB
CC
DA
EA
FF
GF
Table de D
Pour aller àpasser par
AA
BA
CA
DD
EE
FG
GG
Table de E
Pour aller àpasser par
AA
BA
CA
DD
EE
FG
GG
Table de F
Pour aller àpasser par
AB
BB
CC
DG
EG
FF
GG
Table de G
Pour aller àpasser par
AD
BF
CF
DD
EE
FF
GG

Par exemple, si le routeur A doit transférer un message (ou un fichier) au routeur G, sa propre table de routage lui recommande de l'envoyer au routeur D, dont la table de routage dit que pour envoyer le message à G, il doit l'envoyer directement à G.

2) Réseau

On constate que chaque table de routage comprend tous les routeurs du réseau, y compris le routeur possédant la table. Par exemple, la table de routage de A possède l'information A→A signifiant que si A doit envoyer une information à lui-même, il l'envoie en boucle locale.

En dehors de ça, les informations B→B, C→C, D→D et E→E signifient que A est relié directement à ses voisins B, C, D, E. Ceci permet donc de reconstituer le réseau à partir des tables de routage.

a) Codage Python des tables

Une table de routage peut être codée en Python, par un dictionnaire :

tA = {'A':'A','B':'B','C':'C','D':'D','E':'E','F':'B','G':'D'}
tB = {'A':'A','B':'B','C':'C','D':'A','E':'A','F':'F','G':'F'}
tC = {'A':'A','B':'B','C':'C','D':'A','E':'A','F':'F','G':'F'}
tD = {'A':'A','B':'A','C':'A','D':'D','E':'E','F':'G','G':'G'}
tE = {'A':'A','B':'A','C':'A','D':'D','E':'E','F':'G','G':'G'}
tF = {'A':'B','B':'B','C':'C','D':'G','E':'G','F':'F','G':'G'}
tG = {'A':'D','B':'F','C':'F','D':'D','E':'E','F':'F','G':'G'}

Il peut être pratique de se référer aux tables par un dictionnaire de tables comme

tables = {'A':tA,'B':tB,'C':tC,'D':tD,'E':tE,'F':tF,'G':tG}

b) Construction du réseau

Deux sommets n et k sont adjacents si la table de n comprend l'information k→k (sauf si n==k) :

g = Graph(format='svg',engine='dot',strict=True)
for n in 'ABCDEFG':
	g.node(n,shape='circle')
for n in 'ABCDEFG':
	for k in tables[n]:
		if k!=n and tables[n][k]==k:
			g.edge(n,k)

c) Un vieil ami

Dans le cas présent, le réseau ABCDEFG n'est autre que le graphe de Moser :

%3 A A B B A--B C C A--C D D A--D E E A--E B--C F F B--F C--F D--E G G D--G E--G F--G

Le but de ce chapitre est d'étudier le problème inverse : comment, à partir du réseau, retrouver les tables de routage ?

II/ Protocole RIP

Par exemple, un pirate informatique a malencontreusement coupé le câble reliant les routeurs F et G, ainsi que les câbles B-C et D-E.

Le réseau a donc été modifié :

%3 A A B B A--B C C A--C D D A--D E E A--E F F B--F C--F G G D--G E--G

Comment reconstituer les tables de routage ?

1) Protocole RIP

Le protocole RIP (Routing Information Protocol) est basé sur la notion de distance entre deux sommets d'un graphe (ou nombre de sauts entre routeurs). Chaque routeur envoit un message à ses voisins, comprenant sa table de routage, et sait en retour quels sont ses voisins : ils sont à distance 1 du routeur (qui est à distance 0 de lui-même).

Les tables sont donc initialisées ainsi :

Table de A
Pour aller àpasser pardistance
AA0
BB1
CC1
DD1
EE1
F
G
Table de B
Pour aller àpasser pardistance
AA1
BB0
C
D
E
FF1
G
Table de C
Pour aller àpasser pardistance
AA1
B
CC0
D
E
FF1
G
Table de D
Pour aller àpasser pardistance
AA1
B
C
DD0
E
F
GG1
Table de E
Pour aller àpasser pardistance
AA1
B
C
D
EE0
F
GG1
Table de F
Pour aller àpasser pardistance
A
BB1
CC1
D
E
FF0
G
Table de G
Pour aller àpasser pardistance
A
B
C
DD1
EE1
F
GG0

2) Mise à jour des tables

En envoyant sa table à A, le routeur B lui révèle qu'il est relié à F par un chemin de longueur 1. Cela révèle à A qu'il peut joindre F en passant par B, par un chemin de longueur 2.

Table de A
Pour aller àpasser pardistance
AA0
BB1
CC1
DD1
EE1
FB2
GD2
Table de B
Pour aller àpasser pardistance
AA1
BB0
CA2
DA2
EA2
FF1
G
Table de C
Pour aller àpasser pardistance
AA1
BA2
CC0
DA2
EA2
FF1
G
Table de D
Pour aller àpasser pardistance
AA1
BA2
CA2
DD0
EA2
F
GG1
Table de E
Pour aller àpasser pardistance
AA1
BA2
CA2
DA2
EE0
F
GG1
Table de F
Pour aller àpasser pardistance
AB2
BB1
CC1
D
E
FF0
G
Table de G
Pour aller àpasser pardistance
AD2
B
C
DD1
EE1
F
GG0

3) Nouvelles mises à jour

Après les derniers échanges de tables entre routeurs voisins, on retrouve les tables de routage au complet :

Table de A
Pour aller àpasser pardistance
AA0
BB1
CC1
DD1
EE1
FB2
GD2
Table de B
Pour aller àpasser pardistance
AA1
BB0
CA2
DA2
EA2
FF1
GA3
Table de C
Pour aller àpasser pardistance
AA1
BA2
CC0
DA2
EA2
FF1
GA3
Table de D
Pour aller àpasser pardistance
AA1
BA2
CA2
DD0
EA2
FA3
GG1
Table de E
Pour aller àpasser pardistance
AA1
BA2
CA2
DA2
EE0
FA3
GG1
Table de F
Pour aller àpasser pardistance
AB2
BB1
CC1
DA3
EA3
FF0
GB4
Table de G
Pour aller àpasser pardistance
AD2
BA3
CA3
DD1
EE1
FD4
GG0

4) Exemple

La commande

♟️ traceroute framasoft.org

utilise un algorithme similaire pour déterminer la liste des routeurs parcourus pour aller à l'adresse framasoft.org. L'affichage annonce que par défaut, on limite la recherche à une distance de 30 ("hops") maximum :

traceroute to framasoft.org (144.76.131.212), 30 hops max, 60 byte packets
 1  192.168.1.1 (192.168.1.1)  1.739 ms  2.012 ms  2.982 ms
 2  * * *
 3  reunion.orange.fr (193.252.148.140)  11.907 ms  12.046 ms  12.256 ms
 4  * * *
 5  edna.framasoft.org (144.76.131.212)  232.493 ms  232.846 ms  220.171 ms

On trouve le passage par les routeurs suivants (en partant de l'ordinateur 127.0.0.1) :

  1. La box, d'adresse IP 192.168.1.1, atteinte en un temps moyen de 2,012 ms (un hop)
  2. Le serveur du FAI, d'adresse IP 193.252.148.140, atteint depuis la box en 10 ms en moyenne (12,046-2,012), au 2e hop,
  3. et le serveur framasoft.org, d'adresse IP 144.76.131.212, atteint en 220 ms en moyenne depuis le FAI.

Certains hops prennent plus de temps que d'autres, et il peut s'avérer plus efficace de les éviter. C'est le but du protocole OSPF qui tient compte des coûts plutôt que des distances.

III/ Protocole OSPF

Le protocole OSPF (open shortest path first) utilise l'algorithme de Dijkstra pour déterminer le plus court chemin.

1) Réseau avec durées

%3 A A B B A--B 1 C C A--C 1 D D A--D 1 E E A--E 1 B--C 1 F F B--F 3 C--F 2 D--E 1 G G D--G 2 E--G 3 F--G 12

2) Tables de routage initialisées

Table de A
Pour aller àpasser pardurée
AA0
BB1
CC1
DD1
EE1
F
G
Table de B
Pour aller àpasser pardurée
AA1
BB0
CC1
D
E
FF3
G
Table de C
Pour aller àpasser pardurée
AA1
BB1
CC0
D
E
FF2
G
Table de D
Pour aller àpasser pardurée
AA1
B
C
DD0
EE1
F
GG2
Table de E
Pour aller àpasser pardurée
AA1
B
C
DD1
EE0
F
GG3
Table de F
Pour aller àpasser pardurée
A
BB3
CC2
D
E
FF0
GG12
Table de G
Pour aller àpasser pardurée
A
B
C
DD2
EE3
FF12
GG0

3) Après échange avec les voisins

Table de A
Pour aller àpasser pardurée
AA0
BB1
CC1
DD1
EE1
FC3
GD3
Table de B
Pour aller àpasser pardurée
AA1
BB0
CC1
DA2
EA2
FF3
GF15
Table de C
Pour aller àpasser pardurée
AA1
BB1
CC0
DA2
EA2
FF2
GF14
Table de D
Pour aller àpasser pardurée
AA1
BA2
CA2
DD0
EE1
FG14
GG2
Table de E
Pour aller àpasser pardurée
AA1
BA2
CA2
DD1
EE0
FG15
GG3
Table de F
Pour aller àpasser pardurée
AC3
BB3
CC2
DG14
EG15
FF0
GG12
Table de G
Pour aller àpasser pardurée
AD3
BF15
CF14
DD2
EE3
FF12
GG0

3) Nouvelles routes plus courtes

Table de A
Pour aller àpasser pardurée
AA0
BB1
CC1
DD1
EE1
FC3
GD3
Table de B
Pour aller àpasser pardurée
AA1
BB0
CC1
DA2
EA2
FF3
GA4
Table de C
Pour aller àpasser pardurée
AA1
BB1
CC0
DA2
EA2
FF2
GA4
Table de D
Pour aller àpasser pardurée
AA1
BA2
CA2
DD0
EE1
FA4
GG2
Table de E
Pour aller àpasser pardurée
AA1
BA2
CA2
DD1
EE0
FA4
GG3
Table de F
Pour aller àpasser pardurée
AC3
BB3
CC2
DC4
EC4
FF0
GC6
Table de G
Pour aller àpasser pardurée
AD3
BD4
CD4
DD2
EE3
FD6
GG0