TP sur Internet: Adresses IP et Routage

Version du 2019-12-20 13:30:32

Introduction

Le but d'un réseau informatique est de connecter des ordinateurs entre eux pour qu'il puisse s'envoyer des messages, des fichiers, des ordres etc. La façon la plus simple de connecter deux ordinateurs est de les relier avec un câble réseau (aussi appelé « câble ethernet » ou « câble RJ45 »).

Quand on a beaucoup d'ordinateurs à connecter entre eux, cela devient vite difficile de brancher un câble de chaque ordinateur à chaque autre ordinateur, parce que le nombre de câbles nécessaires augmente très vite. On peut le voir dans la figure ci-dessous: Il faut 3 câbles pour relier 3 ordinateurs, 6 câbles pour en relier 4, et ... 15 câbles pour en relier seulement 6 ! Quand on atteint un nombre de 10 ordinateurs à relier ça devient très compliqué.

ressources/graphe-complet.svg

Notion de Route

La solution est de ne pas mettre un câble de chaque ordinateur à chaque autre ordinateur. Un ordinateur sera connecté à certains ordinateurs, mais pas à tous. Mais si on choisi bien quels ordinateurs on connecte, alors il y a toujours moyen d'envoyer des messages d'un ordinateur à n'importe quel autre ordinateur en demandant aux autres ordinateurs de transférer les messages.

ressources/connections-indirectes.svg

A et F peuvent s'envoyer des messages en demandant à B et E de les transférer : c'est une connection indirecte.

Quand deux ordinateurs peuvent s'envoyer des messages sans l'aide d'autres ordinateurs parce qu'ils sont reliés par un câble réseau, ont dit qu'ils ont une connection directe; et quand deux ordinateurs peuvent s'envoyer des messages en les faisant transférer par d'autres ordinateurs, on dit qu'ils ont une connection indirecte. La suite de connections directes par lesquelles passe un message pour aller d'un ordinateur à un autre s'appelle la route du message.

Quand on a un groupe d'ordinateurs et qu'on veut tous les connecter entre eux, la façon la plus simple est de choisir un des ordinateurs et d'y connecter tous les autres : on appelle ça un réseau en étoile. L'ordinateur qui est connecté directement à tous les autres est appelé routeur (dans ce cas précis on peut aussi parler de commutateur ou switch, mais on ne vas utiliser ce terme dans ce TP).

ressources/réseau-en-étoile.svg

Un réseau en étoile. Le routeur est représenté par un cercle.

Le réseau en étoile est simple et ne demande pas beaucoup de câbles, mais il est surtout utilisé pour connecter des ordinateurs qui sont dans une même salle. Ça n'est pas pratique de créer un réseau en étoile dans tout un bâtiment. Les réseaux ont donc souvent la forme suivante: des sous-réseaux qui sont des réseaux en étoile et dont les routeurs sont reliés entre eux.

ressources/multiples-étoiles.svg

Un réseau constitué de plusieurs sous-réseaux en étoile.

Notion d'Adresse

Pour qu'un ordinateur puisse transférer un paquet (les messages que s'envoient les ordinateurs via un réseau sont appelés « paquets ») il faut lui indiquer quelle est la destination du paquet. Pour cela, chaque ordinateur dans un réseau a une adresse. Exactement comme les adresses des maisons pour envoyer le courrier postal.

Un moyen serait de juste donner un numéro à chaque ordinateur: On dirait alors à un ordinateur quelque chose comme « transfère ce paquet vers l'ordinateur numéro 8 ». En pratique, l'adresse d'un ordinateur comporte deux numéros: le numéro de sous-réseau et le numéro d'hôte. L'idée est que tous les ordinateurs connecté à un même routeur ont le même numéro de sous-réseau. Pour simplifier, dans ce TP on aura même un seul routeur par sous-réseau.

Les hôtes (un ordinateur est appelé un « hôte » dans un réseau) sont donc « groupés » par sous-réseau et chaque sous-réseau a un numéro. Cela rend beaucoup plus simple de trouver la route d'un paquet: il suffit d'envoyer le paquet au routeur du sous-réseau de destination, puis on sait que ce routeur saura comment l'envoyer à l'hôte de destination du paquet.

Premiers Pas

On va représenter en Python l'adresse de chaque ordinateur par (n, m)n sera le numéro du sous-réseau et m le numéro d'hôte. Par exemple (1, 3) sera l'hôte numéro 3 du sous-réseau numéro 1.

Nous allons adopter la convention suivante : le routeur d'un sous-réseau aura toujours l'adresse la plus basse de son sous-réseau, c'est à dire qu'il aura un numéro d'hôte de 0. Par exemple le routeur du sous-réseau numéro 1 aura pour adresse (1, 0).

On va créer une première fonction dont le but sera de représenter cette convention: cette fonction prendra en entrée un numéro de sous-réseau et renverra l'adresse du routeur de ce sous-réseau.

Ouvrez le fichier ma_solution.py dans votre éditeur de code. Copiez-y le code suivant et remplacez le commentaire #[À REMPLACER]# par la valeur que la fonction doit renvoyer. Ça devrait être très simple de trouver quoi mettre après return

def adresse_routeur(sous_réseau):
    return #[À REMPLACER]#

Testez votre fonction en lançant le fichier ma_solution.py puis en appelant votre fonction avec quelques numéros de sous-réseau, par exemple 1, 2, 3... Vous devriez obtenir le résultat suivant:

>>> adresse_routeur(1)
(1, 0)
>>> adresse_routeur(2)
(2, 0)
>>> adresse_routeur(3)
(3, 0)

Ensuite, on va créer une fonction qui prend en entrée une adresse et qui renvoie True si l'adresse est celle d'un routeur et False sinon (la fonction renvoie donc un booléen). La fonction va simplement extraire le numéro d'hôte de l'adresse, et regarder si il est égal à zéro ou pas. Attention il y a deux blocs à remplacer cette fois-ci !

def est_un_routeur(adresse):
    numéro_hôte = adresse[#[À REMPLACER]#]
    if #[À REMPLACER]#:
        return True
    else:
        return False

Quelques indices: Souvenez-vous qu'on représente une adresse réseau par une variable de la forme (x, y). C'est ce qu'on appelle un tuple en Python, et si une variable t est un tuple alors on peut accéder à son premier composant (dans notre exemple, x) en faisant t[0], à son deuxième composant (dans note exemple, y) en faisant t[1] etc. Ici on veut le deuxième composant de l'adresse.

Testez votre fonction en lançant à nouveau votre fichier de solution et en appelant votre fonction avec différentes adresses : votre fonction devrait renvoyer True si le numéro d'hôte est zéro, et False sinon.

>>> est_un_routeur((1, 3))
False
>>> est_un_routeur((2, 0))
True
>>> est_un_routeur((1, 0))
True

Fantastique ! On est maintenant près à écrire notre première fonction de routage. À nouveau on commence par quelque chose de simple, et ici on va commencer avec un seul routeur auquel chaque hôte est connecté. C'est donc un un réseau en étoile. Même s'il n'y a qu'un seul réseau, et que ça ne sert donc pas à grand chose de parler de sous-réseau ici, on va lui donner un numéro de sous-réseau, le numéro 1. Voici ce à quoi notre réseau va ressembler:

ressources/plan-étoile.svg

Le plan de notre réseau en étoile.

Notre fonction de routage va prendre deux entrées: la location actuelle du paquet et sa destination. Elle va renvoyer la prochaine adresse vers laquelle le paquet doit être transféré, ou alors elle renverra None pour indiquer que le paquet est arrivé à destination et n'a donc plus besoin d'être transféré.

Voici le code à copier dans votre éditeur. Il est plus compliqué, mais ne vous inquiétez pas, nous allons le remplir petit-à-petit:

def prochaine_étape_étoile(location_paquet, destination):
    if location_paquet == destination:
        return #[À REMPLACER]#
    elif est_un_routeur(location_paquet):
        #[À REMPLACER]#
    else:
        #[À REMPLACER]#

On voit qu'il y a trois blocs à remplacer. Le premier se situe dans une condition if location_paquet == destination:, c'est donc le code à exécuter quand le paquet est arrivé à destination. On a déjà dit plus haut la valeur qu'on voulait renvoyer dans ce cas-là.

Le deuxième bout de code à remplacer est exécuté quand est_un_routeur(location_paquet) renvoie True, c'est à dire quand le paquet est actuellement au niveau du routeur du réseau. En regardant le plan du réseau, on voit que le routeur peut le transférer directement au destinataire du paquet. La « prochaine étape » est donc la destination du paquet.

Enfin, le dernier bout de code à remplacer se situe dans le bloc else:, il est donc exécuté si aucune des deux conditions précédentes n'a été exécutée, c'est à dire que le paquet n'est pas arrivé à destination et il n'est pas au niveau du routeur. La paquet est donc au niveau d'un hôte, et il doit être envoyé au routeur pour que le routeur puisse le transférer à son destinataire. On doit donc renvoyer l'adresse du routeur, plus précisément l'adresse du routeur du sous-réseau actuel. À vous de trouver comment écrire ça ! Un indice: le sous-réseau actuel est location_paquet[0].

Voici quelques exemples avec les résultats attendus pour tester votre fonction. Quand Python n'imprime rien à l'écran (c'est à dire qu'on a directement >>> qui s'écrit), c'est que la fonction a renvoyé la valeur spéciale None.

>>> prochaine_étape_étoile((1, 3), (1, 2))
(1, 0)
>>> prochaine_étape_étoile((1, 0), (1, 2))
(1, 2)
>>> prochaine_étape_étoile((1, 2), (1, 2))
>>> prochaine_étape_étoile((1, 2), (1, 2)) == None
True

On est maintenant capable de simuler la route entière d'un paquet, de sa source à sa destination. On va écrire une fonction route_étoile qui prend en entrée deux adresses, celle de la source du paquet et sa destination, et renvoie la liste des adresses par lesquelles le paquet est passé (par « liste » on entend une liste Python, qui se crée soit avec [] soit avec list()). À nouveau on va voir par quoi remplacer les blocs #[À REMPLACER]# un par un.

def route_étoile(source, destination):
    étapes = list()
    location_paquet = #[À REMPLACER]#
    while #[À REMPLACER]#:
        étapes.append(location_paquet)
        location_paquet = #[À REMPLACER]#
    return étapes

Le premier #[À REMPLACER]# est la location initiale du paquet. C'est très simple: le paquet commence à l'adresse de sa source (la « source » d'un paquet est l'hôte qui l'a envoyé).

Le deuxième #[À REMPLACER]# est la condition d'une boucle while, donc la condition pour qu'on continue d'exécuter la boucle. Avant de le remplacer il faut donc qu'on regarde ce que fait cette boucle while, et on remplacera donc ce bloc en dernier.

La boucle while contient deux instructions: la première est déjà remplie pour vous, elle ajoute la location actuelle du paquet à la liste des étapes que l'on renvoie à la fin de la fonction. La deuxième instruction change la location du paquet. C'est l'instruction qui représente le fait que le paquet est transféré d'une adresse à une autre. C'est ici qu'il va falloir utiliser la fonction prochaine_étape_étoile que vous avez écrit. Cette ligne de code devrait se décrire comme ceci: « on calcule la prochaine étape en fonction de la location actuelle et la destination du paquet, et le résultat est la nouvelle location du paquet ».

On sait maintenant ce que fait la boucle while: elle représente un transfert du paquet d'une adresse à une autre. Elle doit donc être répétée tant que le paquet n'est pas arrivé à destination. Souvenez-vous, notre fonction prochaine_étape_étoile renvoie une valeur très particulière quand le paquet est arrivé à destination, et cette valeur sera alors la nouvelle valeur de la variable location_paquet. Avec ceci vous devriez pouvoir trouver quoi mettre comme condition de votre boucle while.

Voici un exemple pour tester votre fonction route_étoile, où on voit bien qu'un paquet envoyé de l'adresse (1, 2) pour l'adresse (1, 3) est d'abord envoyé au routeur (dont l'adresse est (1, 0)) puis à sa destination finale où la route s'arrête.

>>> route_étoile((1, 2), (1, 3))
[(1, 2), (1, 0), (1, 3)]

Un Réseau Plus Complexe

Transferts de Routeur à Routeur

On va modifier les fonctions que l'on a créé pour qu'elles puissent fonctionner sur un réseau un peu plus compliqué qu'un réseau en étoile. On imagine qu'un Lycée veut connecter les ordinateurs de plusieurs salles: deux salles de TP et la salle des profs. Les plans du Lycée sont ci-dessous:

ressources/plan-lycée.svg

On voit bien que ce serait trop compliqué de relier tous les ordinateurs à un routeur central. Au lieux de ça, on va mettre un routeur par salle: chaque hôte sera connecté au routeur de sa salle et les routeurs seront connectés entre eux. C'est à dire qu'il y aura un sous-réseau par salle, dont le numéro est indiqué à côté de la salle.

Tout d'abord, on remarque que le sous-réseau de chaque salle est un réseau en étoile, donc les fonctions qu'on a créé devraient fonctionner pour l'envoi d'un paquet entre hôtes situés dans la même salle. Vérifiez cela en calculant la route d'un paquet de disons (2, 1) à (2, 3) en utilisant les fonctions que vous avez créé précédemment.

>>> route_étoile((2, 1), (2, 3))
[(2, 1), (2, 0), (2, 3)]

On va maintenant modifier nos fonctions pour pouvoir calculer la route d'un sous-réseau à l'autre. Copiez le code de votre fonction prochaine_étape_étoile à la fin de votre fichier ma_solution.py et changez le nom de la fonction en prochaine_étape_complexe. Copiez aussi la fonction route_étoile et renommez-là route_complexe, et changez son contenu pour qu'elle appelle prochaine_étape_complexe au lieu d'appeler prochaine_étape_étoile.

On va commencer en ne considérant que les réseaux 1 et 2. Voici le plan de notre réseau:

ressources/réseaux-1-et-2.svg

Quand un paquet est envoyé de disons (1, 1) à (2, 2), il doit être envoyé au routeur du sous-réseau 1, qui doit le transférer au routeur du sous-réseau 2, qui peut le transférer à sa destination finale. La partie qui nous manque est le transfert d'un routeur à un autre routeur.

On doit donc rajouter quelques lignes de code dans notre fonction prochaine_étape_complexe qui doivent faire le chose suivante: si la location actuelle du paquet est un routeur, si ce routeur est celui du sous-réseau de la destination du paquet alors on transfère le paquet directement à sa destination finale (ce qu'on faisait déjà avant). Sinon, on transfère le paquet au routeur du sous-réseau de destination. À vous de trouver les modifications à effectuer ! Notez que notre fonction contient déjà une condition est_un_routeur(location_paquet).

Voici un exemple de résultat auquel on s'attend:

>>> route_complexe((1, 2), (2, 3))
[(1, 2), (1, 0), (2, 0), (2, 3)]

Tables de Routage

On va maintenant relier le sous-réseau numéro 3 au reste du réseau. Seulement, le routeur du sous-réseau numéro 3 est loin de celui du sous-réseau numéro 1, et donc ça n'est pas pratique de tirer un câble entre les deux. On va donc relier le routeur du sous-réseau numéro 3 uniquement à celui du routeur numéro 2, qui est plus proche. On va quand même être capable d'envoyer des paquets entre les sous-réseau numéro 1 et 3, mais pas directement : il faut transférer le paquet au routeur du sous-réseau 2 qui peut servir de « pont » entre les deux.

ressources/réseaux-1-2-et-3.svg

Cela va demander de changer notre fonction prochaine_étape_complexe qui pour l'instant considère qu'un routeur peut transférer un paquet directement à n'importe quel autre routeur. On va utiliser ce qu'on appelle des tables de routage. Une table de routage est la structure de données dans laquelle un routeur stocke l'information suivante: pour chaque sous-réseau, à quel routeur transférer les paquets qui ont pour destination ce sous-réseau. Par exemple le routeur 1 doit se souvenir que s'il reçoit un paquet qui a pour destination le sous-réseau 3, il doit le transférer au routeur 2.

On va stocker toutes nos tables de routage dans un seul dictionnaire Python. Le voici partiellement rempli:

tables_de_routage = {
    1: {
        2: 2,
        3: 2,
    },
    2: {
        1: 1,
        3: 3,
    },
    3: {
        #[À REMPLACER]#
    }
}

Voici comment on a organisé ce dictionnaire: à chaque numéro de sous-réseau il associe la table de routage du routeur de ce sous-réseau. Cette table est elle-même un dictionnaire. La table d'un routeur associe le numéro d'un sous-réseau au routeur auquel transférer les paquets qui ont ce sous-réseau pour destination. Par exemple la table de routage du routeur du sous-réseau 1 peut s'obtenir de la façon suivante:

>>> tables_de_routage[1]
{2: 2, 3: 2}

Ce qui veut dire que le routeur 1 doit transférer les paquets pour le sous-réseau 2 directement au routeur 2, et les paquets pour le sous-réseau 3 au routeur 2 également. Notez que comme tables_de_routage[1] est un dictionnaire on peut accéder à ses éléments en rajoutant des crochets, par exemple, si on se pose la question « à quel routeur le routeur 1 doit-il transférer les paquets qui ont comme destination le sous-réseau 3 ? », on peut y répondre en faisant:

>>> tables_de_routage[1][3]
2

Ce qui veut dire que les paquets doivent être transférés au routeur 2.

Vous devriez maintenant être capables de compléter la table de routage.

Quand c'est fait, copiez votre fonction prochaine_étape_complexe et renommez-là prochaine_étape_tables. Ajoutez un paramètre tables_de_routage en entrée de cette fonction. Puis, on va encore modifier la même partie de la fonction: celle qui est exécutée quand le paquet est situé au niveau d'un routeur et que ce routeur n'est pas celui de la destination.

Dans notre fonction pour l'instant, l'instruction dans ce cas est de le transférer au routeur du sous-réseau de destination. On va le remplacer par l'instruction suivante: « transférer au routeur indiqué par la table de routage en fonction de la destination du paquet ». Notez qu'il va falloir utiliser le numéro du routeur actuel pour sélectionner la bonne table de routage. N'oubliez pas qu'on a montré plus haut comment lire dans une table de routage le numéro du prochain routeur à qui transférer le paquet.

On va aussi copier la fonction route_complexe en une fonction route_tables qui a un paramètre tables_de_routage supplémentaire et qui appelle la fonction prochaine_étape_tables en lui passant la variable tables_de_routage.

Pour finir, testez votre fonction route_tables en calculant la route de paquets du sous-réseau 3 au sous-réseau 1 et vice-versa, et vérifiez que le paquet est toujours transféré via des connections qui existent vraiment sur la carte du réseau (par exemple, le paquet ne peut pas être transféré directement du routeur 1 au routeur 3).

>>> route_tables((3, 2), (1, 1), tables_de_routage)
[(3, 2), (3, 0), (2, 0), (1, 0), (1, 1)]
>>> route_tables((1, 3), (3, 4), tables_de_routage)
[(1, 3), (1, 0), (2, 0), (3, 0), (3, 4)]

Félicitations !

Vous ne vous en rendez pas forcément compte, mais votre fonction route_tables peut maintenant calculer des routes sur des réseaux assez complexes. Pour vous le montrer, voici une collection de tables de routage plus complexe que vous pouvez copier dans votre fichier ma_solution.py:

tables_complexes = {
    1: {2:5, 3:5, 4:5, 5:5, 6:5, 7:5, 8:5},
    2: {1:3, 3:3, 4:3, 5:3, 6:3, 7:3, 8:3},
    3: {1:5, 2:2, 4:5, 5:5, 6:5, 7:5, 8:5},
    4: {1:5, 2:5, 3:5, 5:5, 6:5, 7:5, 8:8},
    5: {1:1, 2:3, 3:3, 4:4, 6:6, 7:6, 8:4},
    6: {1:5, 2:5, 3:5, 4:5, 5:5, 7:7, 8:5},
    7: {1:6, 2:6, 3:6, 4:6, 5:6, 6:6, 8:6},
    8: {1:4, 2:4, 3:4, 4:4, 5:4, 6:4, 7:4},
}

Ces tables représentent le réseau suivant:

ressources/réseau-complexe.svg

Un réseau beaucoup plus complexe que les précédents. Pour chaque hôte on n'a marqué que son numéro d'hôte, le numéro de sous-réseau est indiqué dans un rectangle en pointillés.

Vous pouvez simuler la route de paquets dans ce réseau en utilisant votre fonction route_tables et en lui passant tables_complexes comme collection de tables de routage:

>>> route_tables((8,4), (1, 3), tables_complexes)
[(8, 4), (8, 0), (4, 0), (5, 0), (1, 0), (1, 3)]
>>> route_tables((7, 2), (8, 2), tables_complexes)
[(7, 2), (7, 0), (6, 0), (5, 0), (4, 0), (8, 0), (8, 2)]