Algorithme De Routage 2x6f21

Table des matières 1 Introduction

2

2 Définitions 2.1 Routage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Routeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Table de routage . . . . . . . . . . . . . . . . . . . . . . . . .

2 2 2 2

3 Algorithmes de routage 3.1 Routage statique . . . . . . . 3.2 Routage à vecteur de distance 3.3 Routage à états de lien . . . . 3.3.1 Rencontre des voisins . 3.3.2 Mesure des coûts . . . 3.3.3 Construction du LSP . 3.3.4 Distribution du LSP . 3.4 Hybride . . . . . . . . . . . . 3.5 Routage Hiérarchique . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

4 Protocoles de routage sur Internet 4.1 Protocoles de routage intra-domaine . 4.1.1 RIP . . . . . . . . . . . . . . 4.1.2 OSPF . . . . . . . . . . . . . 4.1.3 IGRP . . . . . . . . . . . . . 4.2 Protocoles de routage inter-domaine :

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

4 4 4 9 9 10 10 11 13 14

. . . . . . . . . . . . BGP

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

15 15 15 18 21 24

5 Routage point à point sur Internet 5.1 Propagation d’un datagramme de la source 5.2 Format d’un datagramme . . . . . . . . . 5.3 Fragmentation et Reassemblage d’un IP . 5.4 ICMP- . . . . . . . . . . . . . . . . . . . .

à . . .

la destination . . . . . . . . . . . . . . . . . . . . . . . .

. . . .

. . . .

26 26 28 30 33

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

6 Application

33

7 Conclusion

33

1

1

Introduction

2

Définitions

2.1

Routage

Le routage est une méthode d’acheminement des informations à la bonne destination à travers un réseau de connexion donné. Le problème de routage consiste à déterminer un acheminement optimal des paquets à travers le réseau au sens d’un certain critère de performance. Le problème consiste à trouver l’investissement de moindre coût en capacités nominales et de réserves qui assure le routage du trafic nominal et garantit sa suivie en cas de n’importe quelle panne d’arc ou de nœud. Les équipements utilisés dans un routage sont appelés des routeurs.

2.2

Routeur

Un routeur est un équipement d’interconnexion de réseaux informatique permettant d’assurer le routage des paquets entre deux ou plusieurs réseaux afin de déterminer le chemin qu’un paquet de données va emprunter. Les premiers routeurs étaient de simples ordinateurs ayant plusieurs cartes réseau, dont chacune était reliée à un réseau différent. Les routeurs actuels sont pour la plupart des matériels dédiés spécialement à la tâche de routage et pour y parvenir, les routeurs doivent établir une table de données relative à la configuration du réseau : c’est la table de routage.

2.3

Table de routage

Une table de routage contient souvent les informations suivantes : – La 1ère colonne est l’adresse du réseau de destination, – La 2ème colonne est le masque utilisé par le réseau de destination, – La 3ème colonne est l’adresse de la erelle à utiliser pour atteindre ce réseau, – La 4ème colonne donne l’adresse de l’interface sortant à utiliser pour atteindre cette erelle, – La 5ème colonne donne le métrique ou coût associé à cette route. La commande netstat –rn permet d’obtenir la table de routage de votre machine. La commande route print permet d’obtenir les mêmes informations. Ces différentes tables de routages permettront aux équipements du réseau grâce à divers algorithmes de routage de faire des échanges de paquets. Les 2

Figure 1 – Exemple de routeur

Figure 2 – Table de routage du routeur 1

Figure 3 – Table de routage du routeur 2

Figure 4 – Table de routage du PC 1

Figure 5 – Table de routage du PC 2 contenus de ces tables de routages s’éditeront de façon manuelle ou dynamique avec l’expansion du réseau selon le type d’algorithme de routage 3

Figure 6 – Table de routage du PC 3 utilisé.

3

Algorithmes de routage

Du fait de la variété des objectifs qui sont visés, il existe plusieurs types d’algorithmes de routage. Ceux-ci peuvent correspondre à des politiques déterministes ou adaptatives selon qu’elles s’adaptent ou non aux variations du trafic et de topologie du réseau. On distingue ainsi des algorithmes de routage statiques et des algorithmes dynamiques.

3.1

Routage statique

L’algorithme routage statique est le plus simple, toutes les routes sont décrites de manière statique dans la configuration de l’équipement. A chaque modification topologique du réseau, ces informations seront rééditées manuellement. C’est l’algorithme le moins adaptatif et pour cause, tout est statique.

3.2

Routage à vecteur de distance

Pour les routages à vecteur de distance chaque routeur maintient une table indexée par, et contenant une entrée pour chaque routeur du sousréseau. Chaque entrée contient deux parties : la liaison (voisin) optimale vers la destination et le temps ou la distance à cette destination. La mesure utilisée peut être le nombre de sauts (nombre de routeurs), le temps , le nombre total de paquets en file d’attente sur le chemin ...Un routeur calcule ses distances en utilisant les distances calculées par ses voisins. Le processus de calcul des distances se présente comme suit. Chaque routeur : 1. Est configuré avec un ID unique 2. Est aussi configuré avec un nombre indiquant le coût de chaque lien (soit une valeur fixe comme 1,soit par un calcul). 4

3. Commence avec une valeur de 0 pour lui-même et une valeur "infinie" pour toutes les autres destinations 4. Transmet son vecteur de distance à tous ses voisins chaque fois que l’information change ( aussi bien quand un nouveau voisin apparaît que périodiquement). 5. Sauvegarde le vecteur de distance le plus récent reçu de ses voisins 6. Calcule son vecteur de distance en minimisant le coût vers chaque destination.Ce calcul se fait par examen du coût (minimal) à la destination transmise par chaque voisin et par ajout du coût ( préconfiguré) de ce lien. 7. Les événements suivants entraînent la mise à jour du vecteur de distance (a) La réception d’un voisin d’un vecteur de distance différent du précédent (b) La découverte qu’un lien est défectueux.Dans ce cas on recalcule le vecteur de distance sans tenir compte de ce voisin.

Figure 7 – (a) Sous-Réseau (b) Vecteur de A,I,H,K ;nouvelle table pour J Exemple Considérons comment J calcule sa route vers G.Il sait qu’il peut aller à A en 8ms, et A dit qu’il peut aller à G en 18ms,donc J compte un délai 5

de 26ms vers G en ant par A.Il fait de même pour la route vers G en ant par I,H et K comme 41 (31+10), 18 (6+12) et 37 (31+6) ms respectivement.La plus petite de ces valeurs est 18 donc J crée une entrée dans sa table indiquant que la distance vers G est de 18 et que la route e par H.La même méthode est utilisée pour calculer la distance vers toutes les autres destinations.La nouvelle table de routage pour J est montrée dans la dernière colonne de la figure. Le problème du comptage à l’infinie

L’algorithme de vecteur de distance fonctionne en théorie mais a un sérieux inconvenient en pratique : bien qu’il converge vers la bonne solution il peut le faire très lentement.En particulier il réagit rapidement aux bonnes nouvelles mais lentement aux mauvaises.

Figure 8 – Problème du comptage à l’infinie Considérons un sous-réseau à 5 noeuds (linéaire) de la figure où la mesure est le nombre de sauts.Supposons qu’initialement A est défectueux et que tous les routeurs sont au courant.En d’autres mots ils ont tous une entrée infinie vers A. Quand A fonctionne à nouveau les autres routeurs l’apprennent grâce aux échanges.Par simplicité on suppose que les routeurs initient l’échange périodiquement et simultanément.Lors de la première échange, B apprend que son voisin à un délai de zéro vers A.B crée une entrée dans sa table indiquant que A est à un saut vers sa gauche.Tous les autres routeurs pensent toujours que A est défectueux.A ce stade la table de A est montrée sur la deuxième ligne de la figure (a).A la prochaîne échange C apprend que B est 6

à un saut de A et met à jour sa table.Mais D et E ne l’apprendrons que plus tard.On voit clairement que la bonne nouvelle se propage à un rythme de un saut par échange.Ainsi dans un réseau de N noeuds tous les noeuds seront informés après N échanges. Considérons maintenant le cas de la figure (b) où tous les routeurs fonctionnent initialement.Les routeurs B,C,D et E ont une distance vers A de 1,2,3 et 4 respectivement.Ensuite A tombe en panne (ou bien la liaison entre A et B est coupée). A la première échange B ne reçoit rien de A.Heureusement C indique qu’il a une route vers A de 2 sauts.Mais B ne sait pas que le chemin de C e par B lui-même ( C pouvant avoir plusieurs chemins de longueur 2 vers A).Conséquence B pense pouvoir atteindre A par C avec une distance de 3 sauts.D et E ne mettent pas à jour leur entrée à la première échange. A la seconde échange C remarque que tous ses voisins disent avoir une distance de 3 vers A.Il choisit l’un au hasard et change sa distance à 4 ( troisième ligne de la figure (b) ).Et Ainsi de suite comme le montre la figure. On voit donc clairement pourquoi les mauvaises nouvelles se propagent lentement : aucun routeur n’a une valeur supérieur d’au moins 1 au minimum de ses voisins.Progressivement tous les routeurs augmentent leur valeur vers l’infinie.Mais le nombre d’échange dépend de la valeur de infinie.Pour cette raison il est conseillé de mettre infinie comme le plus long chemin + 1. Cependant si la mesure est le temps il n’y a pas limite supérieure définie et une très grande valeur est nécessaire pour empêcher un chemin de délai long d’être traité comme en panne.Il s’agit du problème du comptage à l’infinie Quelques solutions ont été proposées pour rémédier à ce problème. Hold-Down L’idée de cette technique est que si le chemin vers D tombe est défectueux on attend pendant un moment avant de mettre à jour.Cependant cette technique ralentit la convergence et ne prévient pas le problème du comptage à l’infinie. Division de l’horizon (Split Horizon) 7

La règle est que si R envoie du traffic à D en ant par N,alors R indique à N que sa distance à D est infinie.Puisque R envoie du traffic à D par N la distance réelle de R à N importe peu pour N.La distance de N à D ne dépend pas de celle de R à D. Dans notre exemple simple de la figure cette technique empêchera le comptage à l’infinie puisque C aurait reporté à B que la distance de C à A est infinie. Quand A est défectueux B n’a plus d’autres chemins possibles à A et conclut que A est injoignable.Quand B informe C que A est injoignable C sait que A est injoignable et ainsi de suite. Cependant la technique ne marche pas dans le cas de la figure

Figure 9 – Comptage à l’infini avec split horizon Quand la liaison vers D se casse R1 conclut que D est injoignable puisque R2 et R3 avaient tous deux rapportés à R1 que D est injoignable ( règle du split horizon).Quand R2 reçoit le rapport de R1 que D est injoignable R2 conclut que le meilleur chemin vers D e par R3.R2 conclut qu’il est à une distance 3 de D, rapporte à R3 que D est injoignable ( règle du split horizon) et rapporte à R1 que D est joignable à une distance de 3.R1 pense maintenant que D est joignable par R2 à un coût de 4.Et le problème du comptage à l’infinie persiste. La règle des deux mesures On calcule deux distances pour chaque destination : une basée sur les sauts et l’autre basé sur le "coût" (fonction).La fonction de coût est utilisée pour calculer le meilleur chemin.Le saut est utilisé pour déterminer les destinations injoignables ( ce qui permet de limiter l’infi à la longueur du réseau +1).Cette technique est utilisé par la première version de RIP.

8

Mises à jour déclenchés (Triggered updates) La première version de RIP envoyait les vecteurs de distance(échange) de façon périodique. Ce qui ralentissait la convergence.Dans cette technique on procède à l’échange dès qu’un événement survient. Poison Reverse Cette technique indique une valeur infinie pour explicitement rapporter que D est injoignable au lieu de simplement ne pas mentionner D.Elle est souvent utilisée en conjonction avec split horizon. Utilisation du routage à vecteur de distance Ce type de routage est très simple, facile à configurer ,maintenir et utiliser. Il est donc très pratique pour de petits réseaux où la performance n’est pas critique.

3.3

Routage à états de lien

L’idée sous-jacente du routage à états de lien est simple.Chaque routeur doit faire ce qui suit : 1. Rencontrer ses voisins et connaître leurs addresses. 2. Mesurer le coût vers chacun de ses voisins 3. Construire un paquet appelé paquet à état de lien (LSP) contenant une liste des noms et des coûts à chacun de ses voisins 4. Envoyer le LSP à tous les autres routeurs et enregistrer le LSP le plus récent de chacun des autres routeurs 5. Construire le plus court chemin vers tous les autres routeurs 3.3.1

Rencontre des voisins

Dans une liaison point à point les voisins peuvent se rencontrer en envoyant un paquet spécial HELLO les identifiant. Dans un réseau LAN la rencontre est souvent faite par une transmission périodique du même type d’un paquet spécial à un groupe d’adresses prédéfinies. Parfois le groupe d’adresses est configuré manuellement.

9

3.3.2

Mesure des coûts

Le moyen le plus direct de mesurer les coûts est d’envoyer sur la ligne un paquet spécial ECHO que l’autre routeur doit renvoyer immédiatement.En mesurant le temps et en le divisant par deux le routeur expéditeur peut avoir une approximation du délai.Pour de meilleurs résultats on peut effectuer ce test plusieurs fois et prendre la moyenne. Un problème intéressant est de savoir s’il faut tenir compte ou pas de la charge.Pour en tenir compte il suffit de démarrer le chrono lorsque le paquet est en fin de la file d’attente.Pour l’ignorer on attend que le paquet atteigne le début de la file d’attente. Inclure la charge signifie que lorsqu’un routeur à le choix entre deux lignes de bande ante égale il choisit la moins chargée.Ce qui pourra donner de meilleure performance. Cependant il y a des arguments contre ce choix.On peut se retrouver dans un cas où les routeurs oscilleront alternativement entre deux choix ( surchageant l’un avant de se rabattre sur le second et ainsi de suite).Pour éviter cette oscillation on peut distribuer la charge sur plusieurs lignes en introduisant une fraction de charge sur chaque ligne. 3.3.3

Construction du LSP

Figure 10 – Construction du LSP La contruction de ce paquet est facile une fois qu’on connaît ses voisins et le coût.Le paquet peut commencer par le nom de l’expéditeur suivi par un nombre de séquence et une âge ( à décrire plus loin) et d’une liste des voisins.Pour chaque voisin on donne son coût.

10

Le – – – 3.3.4

LSP est généré périodiquement mais aussi à certains événements : Un nouveau voisin vient Le coût vers un voisin existant a changé La liaison vers un voisin est rompue. Distribution du LSP

Il s’agit de la partie la plus difficile de l’algorithme.Si elle est mal faite les conséquences suivantes peuvent apparaître : – Les routeurs auronts des LSP différents.Ce qui signifie qu’ils calculeront les routes en se basant sur des informations différentes.Beaucoup de liaisons peuvent devenir non fonctionnelles à cause de ça. – La distribution des LSP peut devenir cancéreuse : le nombre de LSP se multiplie rapidement jusqu’à ce que toutes les ressources du réseau soient utilisées uniquement sur les LSP. Dans un premier temps on décrira un algorithme de base avant de l’affiner. L’idée fondamentale ici est d’utiliser l’inondation ou flooding pour distribuer les LSP.Chaque paquet contient un nombre de séquence qui est incrémenté chaque fois qu’un nouveau LSP est envoyé.Les routeurs enregistrent chaque pair( routeur source , séquence) qui leur est envoyée.Quand un nouveau LSP arrive on le compare aux LSP déjà reçu.S’il est nouveau il est transmis à toutes les liaisons ( les voisins) sauf celle qui l’a envoyé.Si c’est un double on le rejète.Si un paquet avec un nombre de séquence plus petit que celui que le routeur a déjà reçu arrive,il est rejeté comme étant obsolète. Cet algorithme a quelques problèmes.Si le nombre de séquence atteint son maximum et qu’on le réinitialise alors il y aura confusion.La solution consiste à utiliser un très grand nombre, un nombre à 32 bits par exemple.Avec un LSP par seconde il faudra 137 ans pour atteindre le maximum. Si un routeur tombe en panne il ne connaîtra plus sa séquence.Si il démarre à nouveau avec 0 comme séquence son LSP sera rejeté. De plus si une séquence est corrompue et 65 540 est reçue au lieu de 4 ( erreur d’un bit) les paquets de 5 à 65 540 seront rejetés. La solution à tous ces problèmes consiste à introduire l’âge de chaque paquet et de le décrémenter une fois par seconde.Quand l’âge atteint 0 les informations provenant de ce routeur sont abandonnées.L’âge du LSP est 11

aussi décrémentée par un routeur avant qu’il ne l’envoie pour s’assurer qu’un LSP ne soit perdu et continue à vivre pendant une période infinie (un paquet dont l’âge atteint 0 est rejeté). Quelques améliorations ont été apportées au modèle précédent pour le rendre plus robuste. Un LSP contient les éléments suivants : – Une source – Un nombre de séquence – L’âge – La liste des voisins Le nombre de séquence est de dimension linéaire.Il débute à zéro et quand il atteint son maximum plus aucun LSP provenant de la source ne sera accepté.Ce nombre doit être assez grand ( 32 bits) de telle sorte qu’il n’atteindra jamais son maximum sauf dans le cas d’un mauvais fonctionnement ( mauvais calcul de la séquence). L’âge est initialisé à une valeur ( fixe) par le routeur qui génère le LSP. Cette valeur doit être de l’ordre d’une heure. Chaque routeur qui reçoit un LSP doit le décrémenter d’au moins 1 ( avant de l’envoyer) et doit continuer de le décrémenter pendant que le LSP est en mémoire. Quand un routeur reçoit un LSP et détermine qu’il doit l’envoyer à certaines de ses liaisons il ne doit pas immédiatement l’envoyer dans la file d’attente. Il doit pendant un temps fixe être conservé dans la mémoire ( des LSP à mettre dans la file d’attente) et assigné un bit ( un flag) à chaque liaison. Si avant l’envoie un autre LSP ( de la même source) arrive avec le même nombre de séquence on change les flag de façon à ne plus l’envoyer au routeur expéditeur. Si par contre le nombre de séquence est plus grand on remplace l’ancien LSP (il ne sera donc jamais transmis). De plus on doit envoyer pour chaque LSP un accusé de réception.I n’est pas nécessaire de générer l’accusé de réception immédiatement mais un flag doit indiquer qu’on doit envoyer un accusé à une liaison.Ainsi le LSP en mémoire du routeur R à 2k flags qui lui sont associés avec k le nombre de liaisons connectées à R.La moitié des flags indique s’il faut envoyer le LSP à ces liaisons ou pas alors que l’autre moitié indique s’il faut envoyer des accusés de réception. Quand la bande ante devient disponible on scanne

12

les flags et on envoie le LSP aux liaisons concernées ou on envoie l’accusé aux autres liaisons.

Figure 11 – Buffer des paqutets du routeur B Si on reçoit initialement un LSP en provenance du lien j on l’enregistre et on met à 1 tous les flags d’envoie sauf celui de j et tous les flags d’accusé sont mis à zéro sauf celui de j ( qui est mis à 1).Si on reçoit un double ( du LSP) en provenance d’une liaison i on met à 0 le flag d’envoie i et on met à 1 le flag d’accusé i.Si par contre on reçoit un accusé en provenance d’une liaison i on met à zéro les flags i d’envoie et d’accusé. ( voir figure) On s’assure aussi que tous les routeurs

3.4

Hybride

La stratégie d’utiliser les deux algorithmes (DV et LS) a été implementé dans ARPANET quand le système devrait er de l’algorithme de vecteur à distance à celui d’état de liens.Le premier code d’ARPANET exécutait seulement vecteur à distance.Une version intermédiaire a été implémentée et exécutait les deux algorithmes.Cette version distribuait aussi bien des vecteurs de distance que des LSPs.Les deux algorithmes n’interagissent pas dans le sens où l’algorithme à état de lien établissait ses routes en se basant sur les LSPs. S’il y a un seul routeur R qui exécute la version intermédiaire alors que tous les autres routeurs exécutent le code original, l’algorithme à état de lien dans R conclura que le réseau entier est constitué de R et de ses noeuds. De façon similaire le calcul des vecteurs de distance se basait uniquement sur les vecteurs de distance reçus.La version intermédiaire du code contenait aussi un switch pouvant être configuré par istration réseau spécifiant si le choix des routes devrait se basé sur la base de donnée des vecteurs de distance ou des états de lien. 13

Une troisième version du code exécutait seulement l’algorithme à état de lien. Au début le réseau était constitué de routeurs exécutant seulement le code original.Ensuite, un à un les routeurs ont été modifiés pour exécuter la version intermédiaire du code.C’est seulement après que tous les routeurs aient été modifiés pour tourner le code intermédiaire ( de telle sorte la base de donnée des LSPs calculés était correct) que c’était possible de basculer sur état de lien grâce au switch. Pendant que les routeurs exécutaient le code intermédiaire mais n’envoyaient que la base de données des vecteurs de distance l’exactitude de l’algorithme à état de lien était vérifiée par comparaison des bases de données envoyées. Quand tous les routeurs étaient basculés sur état de lien il n’était plus nécessaire de tourner les deux alogrithmes simultanément alors la troisième version du code pouvait être chargée dans les routeurs un par un. L’inconvenient de cette approche est dû au fait que la version intermédiaire multipliait la mémoire,la bande ante et le temps de calcul par deux.

3.5

Routage Hiérarchique

Dans les sections précédentes nous voyons un réseau comme étant simplement un ensemble de routeurs interconnectés.Chaque routeur exécute le même algorithme pour calculer les routes du réseau.En pratique ce modèle est un peu trop simpliste à cause d’au moins deux raisons principales : Echelle Au fûr et à mesure que le nombre de routeurs augmente, la surcharge due au calcul,au stockage et à la transmission des tables de routage devient prohibitive.L’Internet consiste en des millions de routeurs interconnectés et de plus de 50 millions d’hôtes.Enregistrez les tables de routage de chacun des hôtes nécessiterait une quantité énorme de mémoire.La surcharge nécessaire pour mettre à jour ces informations serait telle qu’il n’y aura plus de bande ante pour la transmission des données. Autonomie istrative Idéallement une organisation doit pouvoir istrer son réseau comme il le veut ( utiliser l’algorithme de routage de son choix ou "cacher" la structure interne de son réseau) tout en étant capable de se connecter à d’autres réseaux. 14

Figure 12 – Routage hiérarchique Ces deux problèmes peuvent être résolus en groupant les routeurs en "régions" ou "systèmes autonomes" ( ASs).Les routeurs dans la même région exécuteront le même algorithme (LS ou DV).Les algorithmes de routage s’exécutant au sein d’un même AS sont appelés protocole de routage intra-autonome.Il sera nécessaire de connecter les ASs entre eux et ainsi un ou plusieurs routeurs auront la tâche supplémentaire d’être responsable de router les paquets aux destinations en dehors de l’AS.On appelle ces routeurs des erelles (gateway).Pour que les erelles routent les paquets d’un AS à un autre ( avec possiblité de er par d’autres erelles avant d’atteindre la destination) elles doivent savoir comment router entre ellesmêmes.L’algorithme utilisé par les erelles pour router entre les différents AS est connu sous le nom de protocole de routage inter-autonome(interautonomous system routing protocol)

4 4.1 4.1.1

Protocoles de routage sur Internet Protocoles de routage intra-domaine RIP

Le protocole de routage d’information (RIP) est l’un des premiers protocoles utilisé comme protocole intra-domaine d’internet et est toujours largement utilisé aujourd’hui. Il tient son nom et ses origines de l’architecture réseau de l’entreprise Xerox (XNS). L’utilisation répandue RIP est due large15

Figure 13 – Portion d’un système autonome ment à l’apparition en 1982 d’une version d’UNIX ant le T/IP, une distribution de Berkeley (BSD). RIP est un protocole basé sur l’algorithme de routage vecteur distance (avec les améliorations possibles). La version de RIP spécifiée dans RFC 1058 utilise le nombre de sauts comme métrique. Chaque liaison a comme métrique la valeur 1, et la limite maximale de la métrique est fixée à 15. Cette valeur limite l’utilisation de RIP aux ASs décrits précédemment ne comptant pas plus de 16 sauts. Rappelez vous que dans l’algorithme vecteur de distance de routage, les routeurs voisins s’échangent des informations de routages les uns avec les autres. Dans RIP, les tables de routage sont échangées toutes les 30 secondes. Le système de message-réponse de RIP lui permet de faire ces échanges. Le message de chaque hôte contient jusqu’à 25 entrées de sa table de routage vers ses destinations. Ces message contenant les tables de routage sont aussi appelés annonces (ments). Pour comprendre le fonctionnement des annonces RIP, considérons la portion de domaine AS de la figure suivante, les rectangles représentant les routeurs et les lignes les différents réseaux interconnectés. Maintenant supposons que la table de routage de D est celle montrée à la figure suivante. Noter que cette table comporte trois colonnes. La première colonne renferme le réseau destinataire, la deuxième indique le routeur suivant sur le plus court chemin et la troisième le nombre de sauts (nombre de réseaux à traverser, y compris le réseau destinataire à dre). Pour cet exemple, la table indique que pour envoyer un datagramme du routeur D à la destination 1, le datagramme devrait être envoyé premièrement au routeur voisin A ; plus encore, la table indique que cette destination 1 est à 2 sauts sur le chemin le plus court. La table indique aussi que le réseau 30 est à 7 sauts de D en ant par le routeur B. En principe, la table de routage devrait 16

avoir une ligne pour chaque réseau du domaine AS. Elle devrait aussi avoir au moins une ligne pour les réseaux extérieurs au domaine AS. La table de la figure suivante et les autres qui la suivent sont juste des tables partielles.

Figure 14 – Table de routage du routeur D

Supposons à présent que 30 secondes plus tard, le routeur D reçoit de A l’annonce suivante de la figure ci-dessous. Noter que cette annonce n’est rien d’autre que le contenu de la table de routage du routeur A. Cette table de routage dit en particulier que le réseau 30 est juste à 4 sauts de A (en ant par C)

Figure 15 – Annonce de A Le routeur D reçoit cette annonce de A, la confronte avec sa table de routage et apprend en particulier qu’il y maintenant une route ant par A au réseau 30 plus courte que celle qui e par B. Par conséquent, D met à jour sa table de routage (principe du plus court chemin). Vous en doutez qu’un chemin plus deviennent encore plus court. Ceci parce que l’algorithme vecteur de distance est encore dans le processus de convergence, du peut être au fait que de nouvelles liaisons ou routeurs ont été ajoutés, ce qui a provoqué le changement des plus courts chemins des tables de routage des routeurs des réseaux. Parlant des propriétés générales de RIP, si un routeur ne reçoit pas d’information d’un de ses vois au moins une fois toutes les 180 secondes, le voisin en 17

Figure 16 – Table de routage de D après réception de l’annonce de A question est considéré comme injoignable c’est-à-dire soit le voisin est tombé en panne ou la liaison est coupée. Lorsque ceci arrive, RIP modifie sa table de routage locale et ensuite la propage à ses voisins (ceux qui sont encore joignables) par annonces. Un routeur peut aussi demander des informations à propos du cout de l’un de ses voisins vers une destination donnée en se servant des requêtes RIP (RIP request message). Les routeurs s’envoient des requêtes et réponses au moyen d’UDP en utilisant le port 520. Le paquet est transporté entre les routeurs sous une forme standard de paquet IP. Un processus appelé routed exécute le protocole RIP sous les systèmes UNIX. En tapant la commande netstat -rn on obtient la table de routage d’une machine exécutant un système UNIX ou Windows . . . 4.1.2

OSPF

Comme RIP, OSPF ( Open Shortest Path First ) est utilisée pour le routage intra-domaine. Le mot “Open” indique que le protocole de routage est libre ( contrairement au protocole CISCO IGRP). La version la plus récente est la version 2 définie dans le RFC 2328. OSPF est un protocole à état de liens qui utilise le principe du flooding et l’algorithme de Dijkstra pour calculer le plus court chemin. Avec OSPF un routeur construit la topologie complète ( graphe orienté ) du système autonome. OSPF vient résoudre un certain nombre de problèmes : Sécurité Toutes les échanges entre routeurs sont authentifiées. Ce qui signifie que seuls les routeurs de confiance peuvent participer aux échanges et ceci afin d’empêcher les intrus ( ou les étudiants en réseaux de prendre leur nouveau savoir comme un jeu) d’injecter des informations incorrectes dans les tables de routage. Chemin multiple de même coûts Quand plusieurs chemins à une destination ont le même coût OSPF permet de les utiliser ( un seul chemin ne doit pas être choisi pour transporter tout le traffic quand plusieurs chemins égaux existent)

18

Figure 17 – Structure hiérarchique de OSPF avec 4 régions Différentes métriques pour différents traffic TOS (type of service) OSPF permet à chaque liaison d’avoir différents coûts pour différents types de service des paquets IP. Ainsi un satellite à grande bande ante peut être configuré pour avoir un coût bas pour les traffics non critiques mais avec un coût élevé pour les traffic critiques. du routage unicast ou multicast OSPF e trois types de connections : 1. Liaison point à point entre exactement deux routeurs 2. Réseaux multiaccès avec diffusion ( la plupart des LAN) 3. Réseaux multiaccès sans diffusion ( la plupart des WAN ) Un réseau multiaccès est un réseau qui peut avoir plusieurs routeurs chacun d’eux communiquant directement avec les autres.

19

OSPF opère en représentant les réseaux, routeurs et liaisons par un graphe orienté où à chaque arc est assigné un coût. Il calcule ensuite le plus court chemin ( Dijkstra ). Une connection série entre deux routeurs est représentée par une paire d’arcs une dans chaque direction. Leurs poids peut être différent. Un réseau multiaccès est représenté par un noeud pour le réseau lui-même plus un noeud pour chaque routeur. Les arcs du noeud réseau au noeuds routeurs ont un poids de 0 et sont donc ignorés du graphe. La plupart des systèmes autonomes ( AS ) de l’Internet sont très larges et difficile à istrer. OSPF les divise en région numérotée où une région est un réseau ou une séquence de réseaux continus. Les régions ne s’entrecroisent pas mais n’ont pas besoin d’être exhaustive ( soit certains routeurs peuvent n’appartenir à aucune région). Une région est une généralisation des sousréseaux. En dehors de la région sa topologie et ses détails ne sont pas visibles. Chaque AS a une région backbone appelé région 0. Toutes les régions sont connectées ( par des tunnels) au backbone de telle sorte qu’il est possible d’aller de n’importe quelle région de l’AS à une autre en ant par le backbone. Un tunnel est représenté sur le graphe par un arc avec un coût. Un routeur connecté à deux ou à plusieurs régions fait partie du backbone. Comme avec les autres régions la topologie du backbone n’est pas visible à l’extérieur. A l’intérieur d’une région, chaque routeur a la même base de donnée et tourne le même alogrithme du plus court chemin. Sa tâche principale est de calculer le plus court chemin de lui-même à tous les autres routeurs de la région, y compris le routeur connecté au backbone ( il doit y en avoir au moins un). Un routeur qui connecte deux régions a besoin de la base de données des deux régions et doit exécuter le plus court chemin pour chacun d’eux séparément. Pendant un fonctionnement normal trois types de routes sont nécessaires : intra-région, inter-région et inter-AS. Les routes intra-régions sont les plus faciles puisque le routeur source connaît déjà le plus court chemin au routeur de destination. Le routage inter-région procède toujours en trois étapes : aller de la source au backbone ; aller du backbone à la région de destination ; aller à la destination. Cet algorithme force une configuration en étoile avec le backbone étant le hub et les autres régions étant les hôtes. Les paquets sont routés de la source à la destination telle quelle. Ils ne sont pas encapsulés sauf s’ils vont vers une région où la seule connection au backbone est un tunnel. 20

OSPF distingue 4 classes de routeurs : 1. Les routeurs internes sont entièrement au sein d’une région 2. Les routeurs sur la frontière d’une région connectent deux ou plusieurs régions 3. Les routeurs backbone sont sur le backbone 4. Les routeurs frontière de l’AS communiquent avec les autres ASes Ces classes peuvent s’entremêlées. Par exemple tous les routeurs de la frontière d’une région font automatiquement partie du backbone. De plus un routeur du backbone mais qui n’est dans aucune région est aussi un routeur interne. Quand un routeur démarre, il envoie des messages HELLO à toutes ses liaisons point-to-point et les diffuse sur les LANs au groupe constitué de tous les autres routeurs. Sur les WANs il a besoin d’une information de configuration pour savoir qui er. Selon les réponses chaque routeur apprend qui sont ses voisins. Les routeurs sur le même LAN sont tous voisins. OSPF fonctionne en échangeant des informations entre routeurs adjacents, qui est différent de routeurs voisins. En particulier il est inefficace que chaque routeur sur un LAN communique avec tous les autres routeurs du LAN. Pour éviter cette situation, un routeur est élu comme étant le routeur désigné. Il est dit adjacent à tous les autres routeurs sur le LAN et échange des informations avec eux. Les routeurs voisins qui ne sont pas adjacents n’échangent pas entre eux.Un routeur désigné de sauvegarde est toujours maintenu pour faciliter la transition au cas où le routeur désigné principal crash ou doit être remplacé immédiatement. Pendant son fonctionnement normal chaque routeur inonde périodiquement des messages LINK STATE UPDATE à chacun de ses routeurs adjacents. Ce message donne l’état et fournit le coût utilisé dans la base de donnée de la topologie. On envoie un accusé de réception pour chaque message. Chaque message a un nombre de séquence pour qu’un routeur sache si un LINK STATE UPDATE est plus vieux ou récent que celui qu’il a actuellement. Les routeurs envoient aussi ces messages quand une liaison tombe en panne, est établie ou quand son coût change. 4.1.3

IGRP

IGRP est un algorithme de routage propriétaire développé par Cisco au milieu des années 80 en tant que successeur de RIP. IGRP est basé sur le 21

vecteur distance. Plusieurs coûts de métriques (délai, largeur de bande, fiabilité, charge, saut, taille de paquet able MTU) peuvent être utilisés dans la prise des décisions avec possibilité pour l’istrateur réseau de fixer le poids associé à chacun de ces métriques. Cette possibilité d’utiliser les couts définis par l’istrateur dans le choix des routes constitue une différence énorme par rapport à RIP. Nous verrons par la suite que c’est la politique adoptée dans les protocoles inter-domaine comme BGP qui permet également la l’istration des routes à choisir au cours du routage. Une autre importante différence par rapport au RIP est l’utilisation d’un protocole de transport fiable pour communiquer les informations de routage, l’utilisation des messages de mise à jour qui sont envoyés juste quand les coûts des tables de routages changent (au lieu de le faire périodiquement), et aussi l’utilisation d’un algorithme de routage de mise à jour diffusées pour vite construire les boucles de chemins. Les nœuds IGRP s’échangent des informations relatives aux six métriques durant leur mise à jour, mais ce ne sont pas les six métriques qui sont utilisés pour calculer les routes. En effet, seules la largeur de bande, le délai, la charge et la fiabilité sont utilisés pour calculer les routes. Les deux autres à savoir comptage de sauts et le MTU aident à faciliter le calcul des routes d’autres façons. Comptage du nombre de sauts IGRP utilise le comptage de sauts comme moyen pour connaitre à quelles distance se trouvent ses destinataires de lui. Chaque routeur sur un chemin compte pour 1 dans le comptage de sauts. Contrairement à RIP, IGRP ne fixe pas la limite des sauts à 16. La valeur par défaut utilisée par IGRP est de 100. Cette valeur peut bien évidemment augmenter pouvant même atteindre 255. Ce qui permet l’utilisation d’IGRP dans de réseaux plus large contrairement à RIP. Il est important de noter que le nombre de sauts n’entre pas dans le calcul de chemin le plus cours ; Il permet juste à IGRP d’éviter le comptage à l’infini. Les routes dont le nombre de sauts dée la valeur limite fixée sont considérées comme invalides. Les nœuds dont les chemins d’accès sont déclarés invalides ne sont plus adressés pendants les échanges d’annonces de mise à jour. Cette différence fondamentale dans l’utilisation du nombre de sauts montre bien combien les deux protocoles RIP et IGRP sont différents. MTU MTU identifie la plus grande taille de datagramme qu’un routeur IGRP peut accepter. Cette valeur n’est pas utilisée pour calculer les routes. Les nœuds IGRP se communiquent la taille maximale de datagramme MTU qu’ils peuvent er. Les datagrammes dont la taille 22

excède cette limite devront être fragmentés en de petits datagrammes satisfaisant la valeur du MTU é par le routeur IRGP suivant. Largeur de bande La largeur de bande identifie la vitesse de transmission de l’équipement connecté sur le port d’entrée ou de sortie du routeur. Les valeurs de ce champ partent de 1200bps à 10Gbps. La valeur par défaut configurée par CISCO (CISCO IOS) est de 1544Mbps supposant ainsi que la liaison est de type T1. Il est important de noter que bien que cette valeur par défaut est de 1544Mbps de largeur de bande, les interfaces des différents ports ne vont pas tenter d’utiliser plus que ce qui n’est disponible. Ces ports sont connectés à un dispositif (driver) tel que CSU/DSU. Ce sont ces dispositifs qui se chargent de mettre les données sur les équipements de transmission. En effet, l’utilisation des valeurs de bandes par défaut effectivement annulent l’effet de ces dernières dans le calcul des routes. Par conséquent, il est préférable de définir la valeur actuellement disponible par port d’interface au lieu de juste accepter les valeurs par défaut. En définissant les valeurs en fonction de chaque lien, on augmente la performance de RIP à calculer et à choisir le chemin optimal. Pour le calcul des métriques, IGRP observe les largeurs de bande de ces interfaces et choisit la plus petites parmi elles. Cette valeur est ensuite divisée par 10000000 exprimant ainsi la valeur en kbps. Le délai Le délai mesure le temps nécessaire pour traverser une liaison dans le réseau, en supposant que le lien est libre. Le délai assigné à une route dans un réseau IGRP est la somme des délais attribué à l’interface sortante de chaque routeur sur la route. Plutôt que de développer un algorithme pour le calcul des délais par route, IGRP utilise une valeur moyenne par technologie de transmission. Une liaison de type Ethernet 10Mbs a par exemple 10 fois le délai d’une liaison de type Ethernet 100Mbps. IGRP remplit automatiquement ces délais de métrique pour chaque équipement de transmission selon sa technologie et sa largeur de bande. Les istrateurs peuvent aussi changer ces valeurs tout en restant dans les marges acceptables pour refléter certaines conditions particulières dans le réseau. Charge Le facteur charge mesure la largeur de bande effectivement disponible sur une liaison. Plus une liaison est chargée, plus il faudra de temps pour la traverser. La métrique de IGRP concernant la charge permet de faire des calculs de route de façon optimal selon le degré d’utilisation d’une liaison. Les valeurs de charge possibles sont comprises entre 1 et 255 et peuvent être fixées par l’istrateur réseau IGRP. Fiabilité Une autre manière pour l’istrateur d’un réseau IGRP d’in23

fluencer sur les résultats de des calculs de route est l’utilisation de la métrique de fiabilité. Cette métrique comme celle de la charge peut prendre une valeur en 1 et 255

4.2

Protocoles de routage inter-domaine : BGP

Le protocole BGP ( Border Gateway Protocol ) version 4 spécifié dans le RFC 1771 à 1774 est le standard international de facto utilisé pour le routage inter-domaine. BGP n’utilise pas le coût des liaisons mais plutôt propage les informations telles que la séquence de ASs à parcourir afin d’atteindre un AS donné. BGP ne spécifie pas aussi comment une route spécifique vers une destination donnée doit être choisie parmi celle qui existe. Cette décision est une décision de principe et est laissée à l’istrateur réseau. Des exemples de principes incluent des considérations politiques, de sécurité ou économique.On peut avoir : 1. Aucun traffic à travers certains ASs 2. Ne jamais mettre l’Irac sur une route commençant par le Pentagone 3. Ne pas utiliser les Etats Unis pour aller de la Colombie à l’Ontario 4. Transiter Albanie si et seulement s’il n’y a plus d’autres alternatives pour la destination 5. les traffics commençant ou finissant à IBM ne doivent pas er par Microsoft Ces règles sont configurées manuellement ( ou grâce à un script). Elles ne font pas partie du protocole. Pour un routeur BGP le monde est constitué de ASs et des liaisons les connectant. Les voisins immédiats dans le graphe des ASs ( s’il y a un lien entre un routeur de la frontière de chacun d’eux) sont appelés peers. Les réseaux sont groupés en 3 catégories : La première stub networks qui a une seule connection aux graphes. Ces réseaux ne peuvent pas être utilisés pour transiter le traffic parce que il n’y a aucune connection de l’autre côté. Ensuite on a les réseaux multiconnectés ( multiconnected networks). Ils peuvent être utilisés sauf qu’ils refusent. Enfin on a les réseaux de transit ( transit networks ) comme les backbones qui acceptent gérer les paquets d’une tierce partie avec des restrictions ou contre de l’argent.

24

Le protocole BGP définit 4 types de messages : OPEN Les peers communiquent en utilisant le protocol T et le numéro de port 179. T assure une échange fiable avec contrôle de congestion entre les peers. Quand une erelle BGP veut établir un avec un BGP peer, un message OPEN lui est envoyé. Cela permet au BGP de s’identifier et de s’authentifier. Si le message OPEN est accepté par le peer celui-ci renvoie un message KEEPALIVE. UPDATE Ce message est utilisé pour informer d’un chemin vers une destination donnée à un peer. Il peut être aussi utilisée pour retirer des routes précédemment utilisées. KEEPALIVE Ce message est utilisé pour informer que l’expéditeur est fonctionnelle. NOTIFICATION Utilisé pour informer qu’une erreur a été détectée ou que l’expéditeur s’apprête à fermer la session. BGP est fondamentallement un protocole à vecteur de distance mais diffère des protocoles comme RIP. Au lieu de juste maintenir le coût à chaque destination c’est le chemin qui est maintenu. Au lieu d’envoyer périodiquement le coût vers chaque destination c’est la route exacte qui est envoyée. Pourquoi différents protocoles pour le routage inter-domaine et intra-domaine La réponse à cette question va au coeur de la différence entre les buts du routage à l’intérieur d’un AS et entre ASs. Règles Entre ASs les règles sont dominantes. Il peut être important que le traffic débutant à un AS donné ne e pas par un autre AS... A l’intérieur d’un AS tout est sous le contrôle d’un même istrateur et les règles jouent un rôle moins importantes dans le choix des routes Augmentation La capacité d’un algorithme de routage et d’une structure de données pouvant augmenter pour gérer le routage vers un grand nombre de réseaux est une question critique pour le routage interdomaine. A l’intérieur d’un AS ce n’est pas le cas. Si un domaine devient trop grand on peut toujours le diviser en deux AS et exécuter le routage inter-domaine entre eux. Performance Puisqu’un routage inter-domaine est très orienté vers les règles la qualité ( performance) des routes est souvent un problème secondaire ( une route plus longue satisfaisant les critères est choisie par 25

rapport à une plus courte mais ne les satisfaisant pas). Ainsi entre AS il n’y a pas la notion de coûts associés aux routes. A l’intérieur d’un AS par contre le routage est beaucoup plus orienté vers la performance.

5 5.1

Routage point à point sur Internet Propagation d’un datagramme de la source à la destination

Dans cette section, nous allons voir comment IP transporte les datagrammes d’une source à une destination au moyen des routeurs. A cet effet une vue détaillée d’un datagramme IP est requise. La figure suivante nous donne un aperçu sur la composition d’un datagramme IP. Il faut noter que tous les datagrammes IP ont une zone d’adresse source et une zone d’adresse destination codée chacune sur 32 bits. La zone de donnée est typiquement remplie des segments T ou UDP.

Figure 18 – Champ significatif du format IP

Comment alors la couche réseau transporte les datagrammes créés d’une source à une destination ? Nous répondrons à cette question à l’aide de la figure suivante.

Figure 19 – Réseau Premièrement supposons que le client A veuille envoyer un datagramme IP au client B. Le datagramme sera donc transporté de A vers B. Au niveau 26

du client A, IP extrait d’abord l’adresse réseau (223.1.1) de l’adresse destination de B (223.1.1.2). Il parcourt ensuite sa table de routage et trouve qu’il y à une correspondance au niveau de la première ligne et observe que le nombre de sauts à la destination est 1. Ceci indique au client A que B est sur le même réseau que lui. A e alors le datagram IP à sa couche liaison en lui indiquant que la destination est sur le même réseau. Ainsi le protocole de la couche liaison a alors sous sa responsabilité de transporter le datagramme au client B.

Figure 20 – Table de routage de A

Considérons à présent le cas intéressant suivant : Le client A veut envoyer un datagramme IP au client E, dont l’adresse IP est le 223.1.2.2 et qui est sur un autre réseau que A. A parcourt sa table de routage une fois encore, mais cette fois ci, trouve une correspondance à la deuxième ligne. En trouvant que le nombre de sauts à effectuer est 2, A conclut que la destination est sur un autre réseau que lui. Sa table de routage lui indique par ailleurs que pour envoyer un datagramme à E, il devrait d’abord l’envoyer au routeur à l’adresse 223.1.1.4. A envoie alors le datagramme à la couche liaison et lui précise qu’il doit l’envoyer à l’adresse 223.1.1.4. La couche liaison transporte le datagramme à l’interface 1 du routeur. Le datagramme est maintenant au niveau du routeur 1. C’est à lui que revient alors la responsabilité de transporter le datagrams à sa destination ultime. Le routeur extrait la portion réseau de l’adresse destination du datagram soit 223.1.2., ensuite, parcourt sa table de routage (figure suivante). Le routeur trouve une correspondance à la seconde ligne de sa table de routage. La table indique au routeur que le datagramme devrait être envoyé à son interface 2 et que le nombre de sauts à effectuer est 1, ce qui montre que la destination est directement reliée à l’interface 2. Le routeur envoie le datagramme à l’interface 2. Une fois le datagramme à l’interface 2 du routeur, le routeur e le datagramme au protocole de la couche liaison et lui indique que la destination est sur le même réseau. La couche liaison a alors à en charge la responsabilité de transporter le datagramme de l’interface 2 du routeur au client E, lesquels sont tous deux attachés au même réseau locale. 27

Figure 21 – Table de routage du routeur Il faut noter que la 2ième colonne réservée aux routeurs suivants est entièrement vide. Ceci est dû au fait que les réseaux (223.1.1., 223.1.2., et 223.1.3.) sont directement reliés au routeur, ainsi, il n’est plus nécessaire de er par d’autres routeurs intermédiaires. Cependant, si le client A et le client E étaient séparés par 2 routeurs, alors la table de routage du premier routeur sur le chemin de A à E indiquerait 2 comme sauts à effectuer et spécifierait l’adresse IP du second routeur comme prochaine adresse sur le chemin. Le premier routeur aurait alors envoyé le datagramme au second routeur en utilisant le protocole de la couche liaison qui connecte les deux routeurs. Le second routeur enverrait ensuite le datagramme à sa destination en utilisant le protocole de la couche liaison qui connecte le second routeur à la destination du client.

5.2

Format d’un datagramme

Le format d’un datagramme est montré sur la figure ci-contre : Les champs les plus importants d’un datagramme IPv4 sont : Version Number Il s’agit de 4 bits spécifiant la version du protocole du datagramme. En regardant ce champ le routeur peut déterminer comment interpréter le reste du datagramme. Header Length Comme un datagramme IPv4 peut contenir un nombre variable d’options ces 4 bits sont nécessaires pour déterminer où commence les données. La plupart des datagrammes IP ne contiennent pas d’options ainsi le datagramme IP a 20 octets pour l’entête. TOS Le Type de Service a été introduit pour permettre à différents types de datagrammes IP de se distinguer les uns des autres afin qu’on puisse les traiter différemment. Quand le réseau sera chargé par exemple il serait utile de distinguer les datagrammes ICMP des datagrammes transportant les données ( HTTP par exemple). Il serait aussi utile de distinguer les datagrammes temps-réels (utilisés dans les applications de 28

Figure 22 – Format d’un datagramme IPv4

29

teléphonie sur IP) des datagrammes non temps-réels ( FTP par exemple). Récemment Cisco a interprété les 3 premiers bits du ToS comme définissant des niveaux différentiels de service pouvant être fourni par le routeur. Les niveaux de service à fournir étant définis par l’istrateur réseau. Datagram Length Il s’agit de la longueur total du datagramme ( entête plus donnée) mesurée en octets. Comme ce champ est sur 16 bits la taille théorique maximum d’un datagramme IP est 65 535 octets. Cependant les datagrammes déent rarement les 1500 octets et sont même souvent limités à 576 octets. Identifier, Flags, Fragmentation Offset Ces trois champs sont nécessaires pour la fragmentation de l’IP ( voir plus bas pour plus de détails).

5.3

Fragmentation et Reassemblage d’un IP

Nous allons voir dans cette section comment les datagrammes IP sont fragmentés et réassemblés pendant leur transport. Il faut noter que les protocoles de la couche liaison ne transportent pas tous la même taille de paquets. Il y a des protocoles qui e de grande tailles alors que d’autres ne peuvent er que de petite taille de paquet. Par exemple, les paquets d’Ethernet peuvent porter plus de 1500 octets alors que les paquets des réseaux plus larges ne peuvent pas porter plus de 576 octets. La taille maximale qu’un paquet de la couche liaison peut transporter est appelée MTU (maximum transfer units). Comme chaque datagramme IP doit être encapsulé par les paquets de la couche liaison pour le transport d’un routeur à un routeur suivant, le MTU du protocole de liaison limite la longueur d’un datagramme à une valeur fixe. Le fait d’avoir une limite fixe n’est pas encore un grand problème. Ce qui constitue réellement un problème est le fait que chacune des liaisons sur le chemin entre la source et la destination peut utiliser un protocole différent de liaison ayant un MTU différent de celui des autres. La solution à ce problème est de fragmenter les données contenues dans le datagramme IP en deux ou plusieurs datagrammes IP plus petits et de les envoyer ensuite sur les liaisons de plus faible MTU. Chacun de ces petits datagrammes est connu sous le nom de fragment. Les fragments doivent être réassemblés avant qu’ils n’atteignent la couche transport à la destination. En effet T et UDP sont conçu pour accepter de la couche réseau des segments complets non fragmentés. Les concepteurs

30

d’IPV4 ont pensé que le processus de réassemblages (et éventuellement réfragmentation) de datagramme dans les routeurs diminuerait de façon significative leur performance et ont préféré mettre le processus de réassemblage à la fin d’acheminement au lieu de le mettre à l’intérieur du réseau. Lorsqu’un client destinataire reçoit une série de datagrammes d’une même source, il doit déterminer si parmi ces datagrammes, il en existe qui sont des fragments d’un certain datagramme plus grand. Si il y en a, le client doit chercher à quel moment il a reçu le dernier fragments de ces datagrammes et comment les fragments qu’il venait de recevoir doivent être agencés les uns à la suite des autres pour constituer le datagramme original. Pour permettre au destinataire de faire une telle opération, les concepteurs d’IPV4 mettent des champs d’identification, de flag et de fragmentation dans les datagrammes IP. Lorsqu’un datagramme est créé, le client émetteur met un numéro d’identification là-dessus, ensuite ajoute les adresses de source et de destination. L’émetteur incrémente le numéro d’identification pour chaque nouveau datagramme créé. Lorsqu’un routeur doit fragmenter un datagramme, chacun des fragments résultant est cacheté de l’adresse source, de l’adresse destination et du numéro d’identification du datagramme original. Lorsque le destinataire reçoit les séries de datagrammes d’une même source, il peut examiner les numéros d’identification des datagrammes pour déterminer lesquels constituent des fragments d’un datagramme original plus grand. Comme IP est un protocole non fiable, un ou plusieurs datagrammes peut/peuvent ne jamais arriver à destination. Pour cette raison, afin que le destinataire soit sûr d’avoir reçu le dernier fragment du datagramme original, le dernier fragment possède un flag dont le bit est mis à 0 tandis- que tous les autres fragments ont le bit de ce même flag à 1. Aussi, afin que le destinataire sache qu’il n’y a pas de fragments manquants (et ainsi d’être capable de réassembler les fragments dans le bon ordre), le champ offset est utilisé pour spécifier à quel endroit un fragmenter doit être précisément agencé dans le datagramme original.

Figure 23 – Fragmentation IP

31

La figue ci-dessus illustre un exemple de fragmentation de datagramme. Un datagramme de 4000 octets arrive à un routeur, et ce datagramme doit être envoyé sur une liaison dont le MTU est de 1500 octets. Ceci implique que les 3980 octets du datagramme original doivent être séparés en trois frayements (chacun d’entre eux étant encore un datagramme IP). Supposons que le datagramme original a pour numéro d’identification 777. Ainsi, les caractéristiques des trois datagrammes seront comme suit : – 1er fragment : – 1480 octets dans le champ de données du datagramme IP – Numéro d’identification = 777 – Offset = 0 (signifie que le fragment sera à la position de l’octet 0) – Flag = 1 (signifie qu’il y en reste) – 2ième fragment – 1480 octets dans le champ information – Numéro d’identification = 777 – Offset = 1480 (signifie qu’il sera inséré à la position 1480) – Flag = 1 (signifie qu’il en reste) – 3ième fragment – 1020 octets (=3980-1480-1480) dans le champ information – Numéro d’identification = 777 – Offset = 2960 (signifie qu’il sera inséré à la position 2960) – Flag = 0 (signifie que c’est le dernier fragment) Le contenu du datagramme n’est envoyé à la couche transport que lorsque la couche IP a complètement reconstitué le datagramme IP original. Si un ou plusieurs datagrammes n’arrivent pas à destination, le datagramme est perdu et n’est pas envoyé à la couche transport. Mais si le protocole T est celui utilisé par la couche transport, alors T va essayer de reconstituer cette perte en demandant à la source de renvoyer les données du datagramme original. La fragmentation et le réassemblage constitue un nouveau fardeau pour les routeurs sur Internet (un effort supplementaire de créer des fragments à partir des datagrammes) et pour les clients destinataire (un effort supplémentaire de réassembler les fragments). Pour cette raison, il est préférable de faire de minimums de fragmentations que possible. Ceci est souvent mis en œuvre en limitant les segments T et UDP à des valeurs relativement petites, ainsi la fragmentation de ces datagrammes est peu probable. Etant donné que tous les protocoles de liaison de données és par IP sont supposés avoir des MTU à au moins 576 octets, la fragmentation peut être entièrement éliminée 32

en utilisant un MSS de 536 octets, 20 octets pour l’entête du segment T et 20 octets pour l’entête du datagramme IP. C’est pourquoi le transfert de la donnée en grande quantité (comme avec http) sont de taille comprise entre 512-536 octets.

5.4

ICMP-

le protocole ICMP ( Internet Control Message Protocol ) est utilisé par les hôtes les routeurs et les erelles pour communiquer les informations de la couche réseau entre eux. Il est spécifié dans le RFC 792. L’utilisation la plus typique de ce protocole est pour le report des erreurs. Par exemple quand une session Telnet,FTP, ou HTTP s’exécute on peut rencontrer des messages du type “Destination network unreachable”. Ce message a son origine dans ICMP. A un niveau donné un routeur a été incapable de trouver un chemin vers l’hôte spécifié dans l’application Telnet, FTP or HTTP. Ce routeur crée et envoie un message de type 3 à l’hôte indiquant l’erreur.L’hôte reçoit le message ICMP et retourne le code d’erreur au code T qui essaie de se connecter. T en retour envoie le code d’erreur à l’application. ICMP est souvent considéré comme faisant partie de IP, mais il se situe juste au-dessus de IP car les messages ICMP sont transportés dans les paquets IP. En effet les messages les messages ICMP sont transportés au sein des paquets IP comme offset juste comme les paquets T ou UDP. Le très répandu programme ping utilise ICMP. Ping envoie un message de code 0 de ICMP de type 8. La destination voyant la requête renvoie une réponse du même type. Un autre message intéresssant de ICMP est un message appelé “ source quench message”. Ce message est utilisé rarement en pratique. Son but était de gérer le contrôle de congestion.

6

Conclusion

33