Voici des tables de routage : pour chacun des
routeursA, 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
A
A
B
B
C
C
D
D
E
E
F
B
G
D
Table de B
Pour aller à
passer par
A
A
B
B
C
C
D
A
E
A
F
F
G
F
Table de C
Pour aller à
passer par
A
A
B
B
C
C
D
A
E
A
F
F
G
F
Table de D
Pour aller à
passer par
A
A
B
A
C
A
D
D
E
E
F
G
G
G
Table de E
Pour aller à
passer par
A
A
B
A
C
A
D
D
E
E
F
G
G
G
Table de F
Pour aller à
passer par
A
B
B
B
C
C
D
G
E
G
F
F
G
G
Table de G
Pour aller à
passer par
A
D
B
F
C
F
D
D
E
E
F
F
G
G
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 :
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 :
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é :
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 par
distance
A
A
0
B
B
1
C
C
1
D
D
1
E
E
1
F
G
Table de B
Pour aller à
passer par
distance
A
A
1
B
B
0
C
D
E
F
F
1
G
Table de C
Pour aller à
passer par
distance
A
A
1
B
C
C
0
D
E
F
F
1
G
Table de D
Pour aller à
passer par
distance
A
A
1
B
C
D
D
0
E
F
G
G
1
Table de E
Pour aller à
passer par
distance
A
A
1
B
C
D
E
E
0
F
G
G
1
Table de F
Pour aller à
passer par
distance
A
B
B
1
C
C
1
D
E
F
F
0
G
Table de G
Pour aller à
passer par
distance
A
B
C
D
D
1
E
E
1
F
G
G
0
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 par
distance
A
A
0
B
B
1
C
C
1
D
D
1
E
E
1
F
B
2
G
D
2
Table de B
Pour aller à
passer par
distance
A
A
1
B
B
0
C
A
2
D
A
2
E
A
2
F
F
1
G
Table de C
Pour aller à
passer par
distance
A
A
1
B
A
2
C
C
0
D
A
2
E
A
2
F
F
1
G
Table de D
Pour aller à
passer par
distance
A
A
1
B
A
2
C
A
2
D
D
0
E
A
2
F
G
G
1
Table de E
Pour aller à
passer par
distance
A
A
1
B
A
2
C
A
2
D
A
2
E
E
0
F
G
G
1
Table de F
Pour aller à
passer par
distance
A
B
2
B
B
1
C
C
1
D
E
F
F
0
G
Table de G
Pour aller à
passer par
distance
A
D
2
B
C
D
D
1
E
E
1
F
G
G
0
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 par
distance
A
A
0
B
B
1
C
C
1
D
D
1
E
E
1
F
B
2
G
D
2
Table de B
Pour aller à
passer par
distance
A
A
1
B
B
0
C
A
2
D
A
2
E
A
2
F
F
1
G
A
3
Table de C
Pour aller à
passer par
distance
A
A
1
B
A
2
C
C
0
D
A
2
E
A
2
F
F
1
G
A
3
Table de D
Pour aller à
passer par
distance
A
A
1
B
A
2
C
A
2
D
D
0
E
A
2
F
A
3
G
G
1
Table de E
Pour aller à
passer par
distance
A
A
1
B
A
2
C
A
2
D
A
2
E
E
0
F
A
3
G
G
1
Table de F
Pour aller à
passer par
distance
A
B
2
B
B
1
C
C
1
D
A
3
E
A
3
F
F
0
G
B
4
Table de G
Pour aller à
passer par
distance
A
D
2
B
A
3
C
A
3
D
D
1
E
E
1
F
D
4
G
G
0
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) :
La box, d'adresse IP 192.168.1.1,
atteinte en un temps moyen de 2,012 ms (un hop)
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,
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.