Memoire Online - à‰tude portant sur les mécanismes mis en Å“uvre dans le réseau

Acheminer les informations, dans un réseau, consiste à assurer le transit des blocs d'un point d'entrée à un point de sortie désigné par son adresse. Chaque noeud du réseau comporte des tables, dites tables d'acheminement couramment appelées tables de routage, qui indiquent la route à suivre pour atteindre le destinataire (figure III.21). En principe, une table de routage est un triplé<Adresse destination>/<Route à prendre>/<Coût>.

Il convient de distinguer la politique d'acheminement qui indique comment est choisie une route, du protocole de routage ou simplement routage qui décrit comment sont construites les tables d'acheminement, c'est-à-dire qu'il spécifie les échanges d'information entre noeuds, le mode de calcul de la route et du coût. Ces deux notions sont souvent confondues.

- Déterministe, lorsqu'un message arrive dans un noeud, il n'a pas le choix de la route. Une seule route est possible par rapport à la destination. Les tables de routage peuvent être fixées à la configuration du réseau et mises à jour périodiquement par le(s) centre(s) de gestion (gestion centralisée ou décentralisée).

- Adaptative, aucun chemin n'est prédéterminé, le chemin sera fixé au moment du routage en fonction de données sur l'état du réseau (charge, indisponibilité d'un noeud...). La gestion est alors généralement isolée. Le noeud assure la mise à jour de ses tables en fonction de sa connaissance de l'état du réseau.

- Mixte, le choix d'un chemin, adapté à l'état du réseau, est effectué au moment de l'établissement du lien entre les deux entités communicantes. Une fois ce chemin établi, tous les messages d'une même session empruntent le même chemin. La politique est adaptative à l'établissement puis déterministe durant le reste de la session. Cette technique est utilisée dans les réseaux en mode orienté connexion. Le circuit virtuel est construit en politique adaptative et les données sont échangées cri politique déterministe.

III.3.2. Les protocoles de routage

Le routage statique consiste à construire, dans chaque noeud, une table indiquant, pour chaque destination, l'adresse du noeud suivant. Cette table est construite par l'administrateur du réseau lors de configuration du réseau et à chaque changement de topologie. Simple, le routage fixe assure, même lorsque le protocole réseau est en mode datagramme, le maintien en séquence des informations. Aucun bouclage de chemin n'est à craindre, mais il n'existe pas de solution de secours en cas de rupture d'un lien.

Le routage statique n'est pas optimal, il convient parfaitement aux petits réseaux et aux réseaux dans lesquels il n'existe pas de redondance dans les routes. La figure III.22 illustre le contenu des tables de chacun des noeuds pour joindre b2.

Lorsque l'information doit être routée simultanément vers plusieurs destinataires ou groupe d'utilisateurs, il faut dupliquer le message en autant d'exemplaires que de destinataires. Cette technique oblige l'émetteur à connaître tous les destinataires, elle surcharge le réseau. L'adressage de groupe (multicast) autorise l'émission d'un seul message qui ne sera dupliqué que par les noeuds ayant des clients raccordés abonnés à cette adresse dite de multicast (figure 3.10).

Dans le routage par inondation, chaque noeud envoie le message sur toutes ses lignes de sortie, sauf celle d'où provient le message (figure III.24). Pour éviter une surcharge du réseau, chaque message comporte un compteur de sauts. Le compteur est initialisé à l'émission (nombre de sauts autorisés) et décrémenté par chaque noeud. Le message est détruit quand le compteur de sauts est à zéro. Pour éviter les bouclages, les messages sont numérotés, chaque noeud mémorise cet identifiant et détruit les messages déjà vus.

Ce système est très robuste, il résiste à la destruction de plusieurs lignes et garantit de trouver toujours le plus court chemin ; il est utilisé dans certaines communications militaires et par certains protocoles de routage pour diffuser les informations d'état du réseau.

Figure 3.11 Le routage par inondation et la destruction des paquets qui bouclent.

Dans ce mode de routage, chaque noeud tient à jour des tables indiquant quel est le plus court chemin pour atteindre le noeud destination. Chaque lien a un coût affecté ou calculé. A partir de ces informations de coût, chaque routeur détermine le chemin optimal pour joindre une destination. Ce coût ou métrique peut être exprimé en:

Les algorithmes de routage au moindre coût diffèrent selon la manière dont ils prennent en compte ces coûts pour construire les tables de routage. Dans certains protocoles de routage, un noeud peut maintenir plusieurs tables de routage et ainsi acheminer les données en fonction d'une qualité de service requise.

Dans le routage vecteur distance ou routage de Beliman-Ford (distance vectorRouting), chaque noeud du réseau maintient une table de routage qui comporte une entrée pour chaque noeud du réseau et le coût pour joindre ce noeud. Périodiquement chaque noeud diffuse sa table de routage à ses voisins. Le noeud destinataire apprend ainsi les destinations que son voisin sait joindre.

À réception, le noeud compare les informations reçues à sa propre base de connaissance :

- Si la table reçue contient une entrée inconnue, il incrémente le coût de cette entrée du coût affecté au lien par lequel il vient de recevoir cette table et met cette nouvelle entrée dans sa table. Il a ainsi appris une nouvelle destination.

- Si la table contient une entrée qu'il connaît déjà et si le coût calculé (coût reçu incrémenté du coût du lien) est supérieur à l'information qu'il posséda, il ignore cette information, sinon il met sa table à jour de la nouvelle valeur de cette entrée.

De proche en proche chaque noeud apprend la configuration du réseau et le coût des différents chemins La convergence des différentes tables peut être assez longue L'ensemble des schémas de la figure 6.25 illustre ce propos.

A l'initialisation les routeurs n'ont connaissance que de leur propre existence. La table de routage de chacun ne comporte qu'une entrée, elle indique que le coût pour se joindre est nul (destination locale !). Dans cet exemple, le coût a été fixé à 1 pour tous les liens, le coût retenu par un noeud correspond donc au nombre de sauts. Périodiquement le contenu des tables est échange chaque noeud adresse à son voisin les informations Destination/Coût qu'il connaît.

Au premier échange, le noeud A apprend, qu'il peut joindre le noeud B en passant par le lien pour un coût de 0 (contenu de la table du noeud B pour 1 entrée B), coût auquel il convient d'ajouter le coût du transit sur le lien â soit ici 1. A n'a pas, en table, d'information concernant B, il met sa table à jour. Chaque noeud procède de même. En ne considérant que le noeud A, lors du second échange, A apprend qu'il peut joindre les noeuds A, B et C en passant par le lien pour un coût respectif de :

- Pour A, de 1 (valeur reçue) + 1 (coût du lien â), soit 2, Aa déjà une entrée pour cette destination avec un coût de 0, il conserve l'entrée de moindre coût.

- Pour B, de 0 + 1 soit i, valeur déjà dans sa base connaissance, celle-ci est ignorée.

- Pour C, de 1 + 1 soit 2, A n'a aucune entrée concernant C dans sa table, il ajoute cette valeur.

Le même raisonnement est conduit pour chaque noeud. Les échanges ultérieurs n'apportent aucune connaissance nouvelle. Le routage dans le réseau a atteint sa stabilité (convergence des tables). Le routage par vecteur distance est avec ses variantes, l'algorithme le plus utilisé. Mais indépendamment du fait que le temps de convergence peut être long, cet algorithme peut conduire à la création de boucles dans le réseau. La figure III.26 illustre ce propos.

Supposons que le lien entre les noeuds C et B ne soit plus actif. Le noeud B ne recevant plus d'information en provenance de C indique qu'il ne peut plus joindre C en portant le coût de la route à l'infini. Ne pouvant atteindre cette destination B ne diffuse plus celte route. L'instant d'après, B reçoit la table de A, il apprend ainsi qu'il peut atteindre C en passant par pour un coût de 2 + 1 soit 3, il met à jour sa table. Nous venons de créer une boucle, tout ce que A reçoit à destination de C, il l'envoie à B, tout ce que B reçoit à destination de C, il l'envoie en A !

À l'échange suivant, A apprend que joindre C en passant par â a maintenant un coût de 3 + 1 soit 4. Il met sa table à jour. À l'échange suivant, B passe le coût à 5, puis A à 6 jusqu'à ce que le coût devienne l'infini. Pour éviter la création d'une telle boucle, il faut d'une part limiter la valeur de l'infini. Le protocole RIP (Routing Information Protocol) fixe l'infini à 16, la convergence est alors plus rapide. Et d'autre part, il faut interdire aux noeuds de signaler qu'ils connaissent une destination au routeur par lequel ils l'ont apprise. Cette technique dite de l'horizon coupé ou Split Horizon interdit à A de signaler à B qu'il sait comment aller en C en passant par â.

Le principal défaut du routage vecteur distance provient du fait que les routeurs n'ont la connaissance d'un changement d'état du réseau que lorsque leur voisin le leur communique, ce qui peut être long. Pour pallier ce défaut, le routage à état des liens (Link suite Routing) procède différemment (figure 3.12)

- chaque noeud découvre ses voisins et détermine le coût du lien qui les relie ;

- le lien est testé régulièrement et en cas de modification de son coût, le noeud diffuse cette information dans le réseau, sous la forme (A, B, c), le lien du noeud A vers le noeud B a un coût de c ;

- chaque noeud entretien une table où figure, pour chaque lien, son coût (matrice de coûts). À l'aide de ces informations, chaque noeud peut reconstituer la cartographie complète du réseau ;

- à partir de la matrice des coûts, chaque noeud détermine alors sa table de routage (algorithme de Dijkstra).

La figure 3.13illustre le principe d'établissement des tables des routages, après découvertes des voisins, chaque noeud diffus le coût des liens qui le rattachent à ses voisins. À partir de ces informations, il construit une matrice dite matrice des coûts (figure 3.13) qui va lui permettre de déterminer la route de moindre coût pour joindre chaque point du réseau.

	0	7	0		0		0	4
	7	0	3		0		2	0
	0	3	0		5		0	0
	0	0	5		0		7	4
	0	2	0		7		0	3
	4	0	0		4		3	0
à de				A		B			C	D	E	F
A				0		7			0	0	0	4
B				7		0			3	0	2	0
C				0		3			0	5	0	0
D				0		0			5	0	7	4
E				0		2			0	7	0	3
F				4		0			0	4	3	0

Dans l'exemple de matrice de routage représentée figure 6.28, un coût à zéro signifie qu'il n'existe pas de lien entre les deux noeuds, la matrice est symétrique c'est-à-dire que nous avons admis que le coût de A vers B était identique à celui de B vers A. À titre d'illustration nous allons construire la table de routage du noeud A (figure III.29 et 6.30). La figure III.29 est déduite des informations de la matrice de la figure 6.28. Puisqu'il s'agit de déterminer la table de routage du noeud A, on se positionne en A et on examine qu'elles sont les directions joignables de A (de A on peut joindre B et F). On note alors le coût de chacune des directions et on ne retient que la route de moindre coût (lien AF). On réitère le raisonnement en partant maintenant de F (F est dit élu) et ceci jusqu'à ce que toutes les destinations aient été explorées. Les routes apparaissent dans le tableau avec le coût total pour joindre la destination depuis le noeud d'origine (A). Ainsi, « FE, 7 » signifie : la route pour atteindre le noeud E en passant par F coûte 7 depuis la racine.

- l'état validé (noeuds grisés figure 3.15), il n'existe, à partir de la racine, aucun autre chemin de moindre coût pour atteindre le noeud ;

- l'état découverte, il s'agit d'une nouvelle route pour joindre le noeud suivant à partir du noeud qui vient d'être validé ;

- l'état attente (noeuds blancs figure 3.15), après avoir été découverte une route peut être rejetée, s'il en existe déjà une de moindre coût pour joindre le noeud extrémité, ou être mise en attente.

Routes validées	Routes découvertes		Routes en attente
A,0	AB,7 AF,4	(en attente, ?) (validée)	AB,7
AF,4	FE,7 FD,8	(validée) (en attente, ?)	AB,7 FD,8
FE,7	EB,9 ED,14	(Fin et validation d'AB,7) (Fin et validation de FD,8)	AB,7 FD,8
AB,7	BC,10 BE,9	(en attente, ?) (Fin, on sait déjà aller en E pour 7)	BC,10
FD,8	DC,13 DF,15	(Fin et validation de BC, 10) (Fin, on sait déjà aller en F pour 4)	BC,10
BC, 10	CF,15	(Fin, on sait déjà aller en D pour 8)

Noeud destination	Noeud suivant	Coût total
A	Local	0
B	B	7
C	B	10
D	F	8
E	F	7
F	F	4

Le routage au moindre coût nécessite la diffusion, à travers le réseau, d'information concernant soit les tables de routage (Vector distance), soit l'état des liens (Link status). Ce trafic consomme de la bande passante au détriment des données à écouler. Plus le réseau est grand, plus le trafic de mise à jour est conséquent, plus les tables de routage sont importantes et plus le calcul des routes consomment du temps CPU. En routage hiérarchique (figure III.31), le réseau est découpé en domaines appelés systèmes autonomes (AS, Autonomus System). Chaque domaine est identifié, les messages qui transitent dans un domaine qui n'est pas le leur sont éliminés.

Ce mode de découpage des réseaux conduit à définir deux familles de protocoles de routage, notamment utilisés dans Internet :

- Les protocoles internes à un domaine (IGP, Interior Gateway Protocol), qui assurent le routage dans un domaine, mais ignorent les noeuds des autres domaines.

- Les protocoles externes à un domaine (EGP, External Gateway Protocol), qui gèrent l'échange d'information entre domaines et qui annoncent la connectivité de chaque domaine.

Chaque domaine est représenté et connu du reste du réseau par un noeud frontière, dit routeur de bordure, qui supporte à la fois un protocole intérieur au domaine et un protocole externe au domaine. Chaque domaine autonome peut mettre en oeuvre un protocole de routage interne différent.

- RIP (Routing Information Protocol, RFC 1058 ; RIP-2, RFC 1723), du type vecteur distance, RIP a été le premier protocole de routage interne utilisé dans la communauté Internet, il est aujourd'hui remplacé par OSPF. Malgré une convergence lente et un trafic de gestion important, RIP reste le protocole de routage le plus employé.

- OSPF (Open Short Path First), d'origine IETF (RFC 2178), protocole interne à état des liens, il a remplacé RIP dans Internet. Pour éviter l'inondation, les informations d'état sont diffusées sur une adresse de multicast réservée à OSPF.

- IS-IS (Intermediate System to Intermediate System), le protocole de routage interne de l'ISO (ISO 10589), est aussi un protocole à état des liens.

- IGRP (Interior Gateway Routing Protocol), protocole propriétaire de la société Cisco du type vecteur distance, IGRP utilise une métrique construite qui prend en compte le délai d'acheminement, le débit, la fiabilité, la charge du réseau et la MTU (Maximum Transfer Unit).

- EGP (Exterior Gateway Protocol, RFC 827) a été le premier protocole externe utilisé dans Internet.

- BG11 (Border Gateway Protocol, RFC 1771) protocole qui définit les échanges à l'intérieur du domaine (iBGP) et entre systèmes de bordure (eBGP).

Lorsque la décision d'acheminement est prise en fonction d'une adresse destination (mode datagramme ou paquet d'établissement dans le mode connecté), on parle de routage ; l'opération est réalisée par un routeur. La table d'acheminement est dite table de routage (figure 3.17). Cette décision d'acheminement est prise, pour chaque datagramme, par chacun des routeurs traversés (Hop by hop Routing). Il n'y a aucun contexte d'acheminement mémorisé. De ce fait, ce type de réseau résiste à la défaillance d'un noeud (réseau de type Soft state ou réseau sans état). Cependant, la prise de décision à chaque noeud traversé pénalise les performances et donc l'efficacité du transfert de données.

Lorsque l'adresse destination n'intervient pas dans le processus de décision d'acheminement, on parle alors de commutation. En mode connecté (figure 3.18) préalablement à tout envoi de données, un circuit virtuel est construit par une opération de routage, la table de commutation est alors renseignée, les données sont ensuite commutées. La table de commutation contient un identifiant de flux attribué lors de la phase d'établissement (étiquette) et la voie à prendre. Dans la figure 6.33, ce qui arrive avec l'étiquette A par le port x et acheminé sur le port y avec l'étiquette B.

La décision de commutation est plus rapide que la décision de routage, les protocoles récents dits à haut débit comme le Frame Relay ou l'ATM (Asynchronous Transfer Mode) utilisent ce principe. Devant l'efficacité de ce mode d'acheminement dans les réseaux, l'IETF a défini, pour les protocoles réseaux en mode non connecté, le protocole MPLS (Multi Protocol Label Switching) qui offre un service de type circuit virtuel à des protocoles en mode datagramme.

Le mode d'établissement des routes et les critères de sélection de celles-ci sont directement liés au mode de signalisation utilisé dans le réseau. Si le protocole réseau utilise une signalisation dans la bande, la demande d'établissement de route est transportée dans une unité de données du protocole de transfert. Elle doit donc être traitée par la même entité de programme. Le processus d'établissement des routes rentre en concurrence directe avec celui de commutation. Ce système pénalise les performances (figure 3.19).

Lorsque le réseau utilise une signalisation par canal sémaphore, le protocole de signalisation et celui de transfert sont indépendants. Etablissement de routes et commutation sont traités par des entités de programme différentes. Indépendamment du gain en performance, l'indépendance des protocoles permet l'utilisation d'un protocole de signalisation beaucoup plus riche en information, notamment celui-ci pourra transporter des informations en relation directe avec la qualité de service exigée par le flux pour lequel la construction d'un circuit virtuel est demandée (figure 3.20). Les protocoles dits haut débit comme ATM et Frame Relay utilisent ce mode de signalisation.

Les réseaux en mode datagramme ne disposent d'aucun mécanisme d'établissement de routes ce qui leur confère une grande souplesse notamment une grande résistance à la défaillance. Cependant, le mode connecté, en garantissant le séquencement des informations et optimisant le processus d'acheminement, présente des avantages certains notamment pour le transfert des flux multimédia. La figure 6.36 réalise une comparaison succincte des deux modes en mettant en évidence les points forts de chacun d'eux.

Critères	Mode connecté	Mode non connecté
Mise en relation	Oui	Non
Connexion/Déconnexion	Oui	Non
Circuit offert	Permanent durant tout l'échange	Pas de circuit réservé Best effort
Résistance à la défaillance	Non, réseau à état (Hard State)	Oui, réseau sans état (Soft State)
Garantie du séquencement	Oui	Non
Optimisation du réseau	Non	Oui

Aussi, ne serait-il pas possible d'imaginer un protocole réseau qui réalise une synthèse entre ces modes en offrant dans un environnement datagramme les performances du mode connecté ? C'est l'objectif de MPLS (Multi Protocol Label Switching) qui autorise un acheminement commuté des datagrammes. À cet effet, un protocole de distribution d'identifiants de route ou labels prédétermine des routes en établissant une correspondance entre une destination IP et un label. En fonction de son adresse destination, chaque datagramme se voit affecter à l'entrée du réseau, par le routeur de périphérie d'entrée (Edge Label Switching Router ou ELSR), un identifiant de route (label). Il est ensuite acheminé dans le réseau par rapport à cet identifiant et non plus en fonction de l'adresse destination. Comme dans les réseaux en mode connecté, l'identifiant n'a qu'une valeur locale. Le routeur de sortie supprime le label et achemine le datagramme vers sa destination. L'ensemble forme un réseau MPLS (figure 3.22).

à‰tude portant sur les mécanismes mis en Å“uvre dans le réseau

III.3. L'ACHEMINEMENT DANS LE RÉSEAU

III.3.1 Définitions

III.3.2. Les protocoles de routage