TermNSI/Routage/EXERCICES.md

# 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
```

*(Les chiffres sur les liaisons représentent le nombre de sauts.)*

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

| Destination | Passerelle | Distance (sauts) |
|-------------|------------|------------------|
| B | | |
| C | | |
| D | | |
| E | | |
| F | | |
| G | | |

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

| Destination | Passerelle | Distance (sauts) |
|-------------|------------|------------------|
| A | | |
| B | | |
| C | | |
| E | | |
| F | | |
| G | | |

---

## Exercice 2 : Protocole RIP

### Question 1 - Mise à jour des tables

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

| Destination | Distance |
|-------------|----------|
| X | 2 |
| Y | 4 |
| Z | 1 |

R est à distance **1 saut** de V. Quelles seront les nouvelles distances que R pourrait enregistrer pour X, Y et Z ? Dans quel cas R mettra-t-il à jour sa propre table ?

### Question 2 - Limite de RIP

Pourquoi RIP est-il limité à 15 sauts maximum ? Quelle conséquence cela a-t-il sur les réseaux pouvant utiliser RIP ?

### Question 3 - Convergence

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

---

## Exercice 3 : Algorithme de Dijkstra

Soit le graphe pondéré suivant (les poids représentent des coûts de liaison) :

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

1. Appliquer l'algorithme de Dijkstra depuis **A**. Compléter le tableau d'exécution :

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

2. Quel est le plus court chemin de A vers E ? Donner le chemin complet et son coût total.

---

## Exercice 4 : Protocole OSPF

La formule de coût OSPF est :

$$\text{coût} = \frac{10^8}{d}$$

où $d$ est le débit de la liaison en bits/seconde.

### Question 1 - Calcul de coûts

Calculer le coût OSPF des liaisons suivantes :

| Type de liaison | Débit | Coût |
|-----------------|-------|------|
| Ethernet 10 Mbps | 10 × 10⁶ bps | |
| Fast Ethernet 100 Mbps | 100 × 10⁶ bps | |
| Gigabit Ethernet | 10⁹ bps | |
| Liaison série 2 Mbps | 2 × 10⁶ bps | |

### Question 2 - Choix du meilleur chemin

Un réseau propose deux chemins de A vers Z :
- **Chemin 1** : A → B → Z, avec une liaison à 100 Mbps puis une liaison à 10 Mbps
- **Chemin 2** : A → C → D → Z, avec trois liaisons à 100 Mbps

Quel chemin OSPF sélectionnera-t-il ? Justifier par le calcul.

---

## Exercice 5 : Comparer RIP et OSPF

Compléter le tableau comparatif :

| Critère | RIP | OSPF |
|---------|-----|------|
| Type d'algorithme | | |
| Métrique utilisée | | |
| Vision du réseau | | |
| Limite de distance | | |
| Vitesse de convergence | | |
| Taille de réseau adaptée | | |

---

## Exercice 6 : Implémenter Dijkstra en Python

Implémenter la fonction `dijkstra(graphe, source)` qui retourne un dictionnaire des distances minimales depuis `source` vers tous les sommets du graphe.

```python
def dijkstra(graphe, source):
    """
    graphe : dict {sommet: [(voisin, poids), ...]}
    source : sommet de départ
    Retourne : dict {sommet: distance_minimale}
    """
    # À compléter
    pass


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

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

---

Auteur : Florian Mathieu

Licence CC BY NC

<a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/"><img alt="Licence Creative Commons" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png" /></a> <br />Ce cours est mis à disposition selon les termes de la <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International</a>.