Corrigé des exercices — Routage

Exercice 1 : Tables de routage

Soit le réseau suivant :

    A ---1--- B ---2--- E
    |         |
    3         5
    |         |
    C ---4--- D ---1--- F
         \         /
          2       1
           \     /
             G

Question 1 : Compléter la table de routage du routeur A

Destination	Passerelle	Distance (sauts)
B	B	1
C	C	1
D	C	2
E	B	2
F	C	3
G	C	2

Explication : Depuis A, pour atteindre : - B : directement connecté (1 saut) - C : directement connecté (1 saut) - D : via C (A→C→D = 2 sauts) - E : via B (A→B→E = 2 sauts) - F : via C puis D (A→C→D→F = 3 sauts) - G : via C (A→C→G = 2 sauts)

Question 2 : Compléter la table de routage du routeur D

Destination	Passerelle	Distance (sauts)
A	C	2
B	B	1
C	C	1
E	B	2
F	F	1
G	G	1

Exercice 2 : Protocole RIP

Question 1 : Principe de mise à jour

Un routeur R reçoit de son voisin V la table suivante :

Destination	Distance
X	2
Y	4
Z	1

Si R est à distance 1 de V, quelle sera la mise à jour de la table de R ?

Réponse :

R ajoute 1 (la distance vers V) à chaque entrée :

Destination	Distance via V
X	2 + 1 = 3
Y	4 + 1 = 5
Z	1 + 1 = 2

R ne mettra à jour sa table que si ces distances sont inférieures aux distances actuellement connues.

Question 2 : Limite de RIP

Pourquoi RIP est-il limité à 15 sauts maximum ?

Réponse : - Au-delà de 15 sauts, la destination est considérée comme inaccessible (distance = 16 = infini) - Cette limite évite les boucles infinies de routage - Elle limite aussi la taille des réseaux pouvant utiliser RIP - C'est pourquoi RIP est adapté aux petits réseaux seulement

Question 3 : Convergence

Combien de temps faut-il au minimum pour qu'une information de routage traverse 5 routeurs avec RIP ?

Réponse : - RIP envoie des mises à jour toutes les 30 secondes - Pour traverser 5 routeurs : 5 × 30 = 150 secondes (2 min 30 s) minimum

Exercice 3 : Algorithme de Dijkstra

Question 1 : Exécution manuelle

Soit le graphe pondéré suivant :

        4
    A -----> B
    |        |
   2|        |1
    v        v
    C -----> D -----> E
        1        3

Appliquer l'algorithme de Dijkstra depuis A.

Résolution pas à pas :

Étape	Sommet traité	d(B)	d(C)	d(D)	d(E)
Init	-	∞	∞	∞	∞
1	A	4	2	∞	∞
2	C	4	2	3	∞
3	D	4	2	3	6
4	B	4	2	3	6
5	E	4	2	3	6

Résultat final : - A → A : 0 - A → B : 4 (chemin direct) - A → C : 2 (chemin direct) - A → D : 3 (via C) - A → E : 6 (via C puis D)

Question 2 : Reconstruction du chemin

Quel est le plus court chemin de A vers E ?

Réponse : A → C → D → E (coût total : 6)

Exercice 4 : Protocole OSPF

Question 1 : Calcul du coût d'une liaison

La formule OSPF est : coût = 10^8 / débit

Calculer le coût des liaisons suivantes :

Type de liaison	Débit	Coût
Ethernet 10 Mbps	10 × 10^6 bps	10^8 / 10^7 = 10
Fast Ethernet 100 Mbps	100 × 10^6 bps	10^8 / 10^8 = 1
Gigabit Ethernet	10^9 bps	10^8 / 10^9 = 0.1 ≈ 1
Liaison série 2 Mbps	2 × 10^6 bps	10^8 / (2×10^6) = 50

Note : En pratique, le coût minimum est souvent fixé à 1.

Question 2 : Choix du meilleur chemin

Soit un réseau avec deux chemins possibles de A vers Z : - Chemin 1 : A → B → Z avec liaisons à 100 Mbps et 10 Mbps - Chemin 2 : A → C → D → Z avec trois liaisons à 100 Mbps

Quel chemin OSPF choisira-t-il ?

Calcul : - Chemin 1 : coût = 1 + 10 = 11 - Chemin 2 : coût = 1 + 1 + 1 = 3

Réponse : OSPF choisira le chemin 2 car son coût (3) est inférieur à celui du chemin 1 (11), même s'il traverse plus de routeurs.

Exercice 5 : Comparaison RIP vs OSPF

Question : Différences fondamentales

Critère	RIP	OSPF
Type d'algorithme	Vecteur de distance (Bellman-Ford)	État de liens (Dijkstra)
Métrique	Nombre de sauts	Coût (basé sur le débit)
Vision du réseau	Locale (voisins uniquement)	Globale (carte complète)
Limite	15 sauts max	Pas de limite de sauts
Convergence	Lente (30s entre mises à jour)	Rapide
Complexité	Simple	Plus complexe
Adapté pour	Petits réseaux	Grands réseaux

Exercice 6 : Implémentation Python de Dijkstra

def dijkstra(graphe, source):
    """
    Algorithme de Dijkstra pour trouver les plus courts chemins.

    :param graphe: dict {sommet: [(voisin, poids), ...]}
    :param source: sommet de départ
    :return: dict des distances minimales
    """
    # Initialisation
    distances = {sommet: float('inf') for sommet in graphe}
    distances[source] = 0
    non_visites = set(graphe.keys())

    while non_visites:
        # Sélectionner le sommet non visité avec la plus petite distance
        courant = min(non_visites, key=lambda s: distances[s])
        non_visites.remove(courant)

        # Si la distance est infinie, les sommets restants sont inaccessibles
        if distances[courant] == float('inf'):
            break

        # Mettre à jour les distances des voisins
        for voisin, poids in graphe[courant]:
            nouvelle_distance = distances[courant] + poids
            if nouvelle_distance < distances[voisin]:
                distances[voisin] = nouvelle_distance

    return distances


# Test
graphe = {
    'A': [('B', 4), ('C', 2)],
    'B': [('D', 1)],
    'C': [('D', 1)],
    'D': [('E', 3)],
    'E': []
}

print(dijkstra(graphe, 'A'))
# Résultat : {'A': 0, 'B': 4, 'C': 2, 'D': 3, 'E': 6}

Auteur : Florian Mathieu

Licence CC BY NC

Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.