Objectif : implémenter en Python la construction des tables de routages des routeurs d’un réseau, selon le protocole RIP.
Chaque routeur sera représenté par un objet de la classe Routeur, et le réseau sera un graphe (classe Graphe) de routeurs.
Voici un programme de base :
from graphes import Graphe
class Routeur:
def __init__(self, nom):
self.table = {} # dictionnaire {dest: [pass, metr]}
self.nom = nom
def __repr__(self):
return str(self.nom)
def repr_table(self):
...
return ""
def initialiser(self, reseau):
...
def generer_message_RIP(self):
message = [] # de la forme [(destination, metrique), ...]
...
return message
def envoyer_message_RIP(self, voisin):
...
def mise_a_jour_table(self, source, message):
...
if __name__ == "__main__":
# Le réseau de routeurs (un Graphe)
reseau = Graphe(oriente = False)
# Les routeurs (objets de type Routeur)
routeurs = {}
N = 7
for i in range(N):
nom = chr(65+i) # lettres de 'A' à ...
routeurs[nom] = Routeur(nom)
# Construction du réseau de routeurs
...
# Initialisation des routeurs
for routeur in routeurs.values():
routeur.initialiser(reseau)
# Simulation RIP
while True:
for routeur in routeurs.values(): # tous les routeurs
for voisin in reseau.voisins(routeur): # les voisins du routeurs
routeur.envoyer_message_RIP(voisin)
Classe Graphe
class Graphe:
""" Implémentation d'un graphe à partir d'un dictionnaire d'adjacence
"""
def __init__(self, oriente = True):
self.A = {} # dictionnaire d'adjacence
self.oriente = oriente
def __repr__(self):
return str(self.A)
def __len__(self):
return len(self.A)
def ajouter_sommet(self, x):
""" Ajoute un sommet x
"""
if not x in self.A:
self.A[x] = set()
def ajouter_arete(self, x, y):
""" Ajoute une arête entre les sommets x et y
"""
self.ajouter_sommet(x)
self.ajouter_sommet(y)
self.A[x].add(y)
if not self.oriente:
self.A[y].add(x)
def supprimer_arete(self, x, y):
""" Supprime une arête entre les sommets x et y
"""
self.A[x].discard(y)
self.A[y].discard(x)
def voisins(self, x):
""" Renvoie l'ensemble des voisins du sommet x
"""
return self.A[x]
def get_aretes(self):
""" Renvoie la liste des arêtes
sous forme d'une liste de tuples
(compatible networkx)
"""
L = []
for s, V in self.A.items(): # s : sommet V : Voisins de s
for v in V:
L.append((s, v))
return L
def arete(self, x, y):
""" Renvoie True s'il existe une arête
entre le sommet x et le sommet y
"""
return x in self.A[y]
Fonction pour représenter les graphes graphiquement
import matplotlib.pyplot as plt
import networkx as nx
import matplotlib.colors as mcolors
import netgraph
LIST_COLORS = list(mcolors.TABLEAU_COLORS.values())
def plot_graphe(g, **kargs):
print(kargs, g.__class__.__module__, g.__class__.__name__)
if isinstance(g, nx.DiGraph) or isinstance(g, nx.Graph):
G = g
node_color = {n:"#FFFFFF" for n in G.nodes}
elif g.__class__.__name__ == 'Graphe':
if g.oriente:
G = nx.DiGraph()
else:
G = nx.Graph()
G.add_edges_from(g.get_aretes())
#print(G.nodes())
coul = ["#FFFFFF"]*len(G.nodes)
node_color = {n:"#FFFFFF" for n in G.nodes}
if hasattr(g, 'data') and 'coul' in g.data:
for i, n in enumerate(G.nodes):
if n in g.data['coul']:
G.nodes[n]['coul'] = g.data['coul'][n]
coul[i] = LIST_COLORS[G.nodes[n]['coul']]
node_color[n] = LIST_COLORS[G.nodes[n]['coul']]
elif isinstance(g, dict):
G = nx.Graph()
for n, v in g.items():
for n2 in v:
G.add_edge(n, n2)
node_color = {n:"#FFFFFF" for n in G.nodes}
else:
raise Exception(f"Type de graphe non reconnu :{g.__class__.__module__} {g.__class__.__name__}")
if 'node_positions' in kargs:
pos = kargs['node_positions']
else:
pos = nx.layout.spring_layout(G)
plot_instance = netgraph.InteractiveGraph(G, node_labels=True,
node_layout = pos,
node_color=node_color,
node_size = 5,
arrows = True)
plt.show()
Dans un premier temps, afin de vérifier le bon fonctionnement du protocole, nous utiliserons le réseau ci-dessous :
Compléter la partie # Construction du réseau de routeurs (afficher le graphe pour vérifier).
Compléter la méthode initialiser de la classe Routeur.
Afin d’obtenir un affichage plus clair, compléter la méthode repr_table.
Compléter chacune des méthodes de la classe Routeur. Faire en sorte que les tables de routage des routeurs s’affichent à chacune de leurs modifications.
