Elle est définie par des familles d’algorithmes dont les objectifs sont de choisir :

- la route la plus économique ;
- la route la plus rapide ;
- la route la plus sûre.

Les principes du routage

Le routage est en général une opération qui concerne la couche 3 de l’OSI, mais, pour répondre aux besoins de la réalisation de réseaux locaux, on a donné la possibilité à la couche MAC d’effectuer du routage à ce niveau. Il est réalisé par une machine désignée sous le nom de routeur qui est :

- soit un équipement spécialisé ;
- soit une station Unix configurée comme telle ;
- soit encore un serveur Novell ou une station TCP/IP

le routage désigne l’opération exécutée par le logiciel d ‘un routeur (ou un équipement se comportant comme tel) ; il consiste à lire les adresse de destination des paquets (information de niveau 3), à choisir le cheminement qui permettra d’adresser ceux-ci et à permettre aux trames de passer au travers de deux ponts reliant deux brins de réseau. Pour réaliser cette fonction, trois techniques ont été élaborées :

- celle du pont « transparent »
- du Source Routing Bridge
- et celle du STR (Source Routing Transparent Bridge)

Dans tous les cas le processus de routage est entièrement automatique.

Le fonctionnement des routeurs

La fonction routage est particulièrement simple à mettre en œuvre, mais elle comporte une limite importante : c’est une opération qui s’effectue au niveau 3 du modèle (c.à.d des couches contrôles de liens) et certains protocoles ne sont pas routables comme les protocoles SNA (Systems Network Architecture), APPN (Advanced Peer-to-Peer Networking) , LAT ou Netbios. La grande différence avec un pont réside dans le fait que le routeur travaille sur des informations niveau paquets. Pour réaliser sa fonction le routeur doit constituer et maintenir des tables de routage continuellement mise a jour ; ce processus et celui du choix des routes à prendre s’effectuent dans le cadre d’un algorithme qui lui est propre. Dans la mesure où ils sont capables d’effectuer des opération de délestage automatique, les routeurs effectuent des opérations infiniment plus complexes que les ponts.

Les protocoles de routage : le routage désigne l’opération qui consiste à acheminer un paquet de données vers une direction en fonction de l'adresse de destination du paquet. La question qui se pose est la suivante : comment sont construites les tables de routage et quelles sont les informations qui la composent ? Pour qu'une opération puisse se réaliser, deux conditions sont à remplir :

- le paquet doit être géré par un protocole routable ;
- le nœud doit être en mesure de supporter au moins un protocole de routage.

Le principe consiste, pour chaque routeur, à gérer des tables de routage en précisant l'adresse du réseau de destination, le nombre de nœuds à traverser pour l'atteindre, et l'adresse du port permettant l'accès du nœud. Tous les protocoles de transport ne sont pas routables (par exemple les protocoles SDLC [Synchronous Data Link Control]. LAT et DECNET [Digital Equipment Corporation NETwork] ne le sont pas directement); pour qu'ils le soient, deux conditions doivent être remplies :

- le noeud doit comporter une fonction routage qui soit en mesure d'assurer l'implémentation de l'algorithme, les manipulations et les mises à jour des tables ;
- le paquet à router doit comporter toutes les informations pour la réalisation de l'opération (c'est-à-dire la disponibilité des adresses de destination).

Le rôle du routage est de déterminer le meilleur chemin à prendre pour accéder à un point. Les algorithmes de routage sont nombreux, et certains ne sont pas encore publiés; il est cependant possible de les classer en deux familles :

- le routage interne ;
- le routage externe

Routage interne : Un protocole de routage est dit « interne » (au sens TCP/IP) lorsqu'il est propre à un système autonome. Un tel système dépend d'un seul administrateur de réseau; il a la charge de choisir les protocoles et de donner une vision homogène de l'ensemble.RIP (Routing Information Protocol) est le plus couramment utilisé ; il a été mis au point à l'Université de Berkeley sur la base de recherches effectuées à Palo Alto et doit son succès à sa diffusion - pratiquement universelle - sur tous les centraux Unix ou TCP,IP. Son principe consiste à chercher la meilleure voie possible - estimée en nombre de passerelles

(Hop) - à traverser. La principale critique qu'on peut lui adresser tient au fait que son nombre de nœuds est limité (maximum 15) et que son choix des routes ne tient pas compte de la qualité des lignes et de leur charge. Dans la pratique, RIP est implémenté par défaut sur tous les nœuds. Issu de la technique dite de «vecteur distant », ce protocole est basé sur une classification des nœuds en « non actifs » et «actifs» (si une passerelle est active, elle propage les routes qu'elle connaît vers les autres, ce qui leur permet de mettre à jour leurs tables de routage). HELLO se base sur la notion de temps d'acheminement des paquets ; son principe consiste à mesurer le temps nécessaire à un paquet pour aller vers un nœud de destination et de choisir la route la plus rapide. SPF (Shortest Path First) est destiné aux réseaux de grandes dimensions et a un principe équivalent à celui de RIP. OSPF (Open Shortest Path First) n'est pas encore, à ce jour, un protocole disponible pour tous les systèmes. Comme RIP son principe consiste à choisir la route la plus courte mais en y incluant les notions de qualité et de coût des lignes, ce qui lui permet de, déterminer plusieurs chemins possibles pour une même destination.

Routage externe : Les protocoles dits « externes » - ou EGP (Exterior Gateway Protocol) - sont décrits par le RFC 1163. Implémentés dans des passerelles se chargeant d'établir la communication, ils permettent un routage entre domaines autonomes, c'est-à-dire entre deux réseaux (ou ensemble de réseaux) dépendant d'administrations différentes. On désigne sous le nom de voisins externes (Exterior Neighbour) deux passerelles en relation directe mais appartenant à deux domaines différents. C'est le protocole EGP qui se charge d'échanger des informations au travers de ces passerelles et assure trois fonctions essentielles :

- Acquérir le voisin (Neighbour Acquisition), c'est-à-dire permettre à une passerelle de demander une autorisation d'échange à une autre. Cette action se déroule par émission d'un message EGP suivant une périodicité désignée sous le nom de Hello Intervall.
- Surveiller constamment la disponibilité des passerelles EGP, c'est-à-dire interroger périodiquement leurs voisines en leur transmettant une trame d'interrogation Poll. Cette procédure, apparemment complexe, permet de désynchroniser le processus de calcul de la route de celui du transfert (ce qui a pour effet de produire un meilleur rendement de la communication).
- Mettre à jour les tables de routage (ce qui consiste - pour deux passerelles - à échanger des informations sur celles de leurs propres domaines, mais également sur les passerelles donnant accès à d'autres [si elles en ont connaissance]).

Les mécanismes de routage : La mise en place de mécanismes de routage pose deux problèmes de construction :

- quelles sont les informations à mettre dans les tables de routage ? ;
- comment - dans la mesure où la performance du réseau a un objectif constant - obtenir ces informations ?

Le principe de leur construction reste celui de la passerelle et se présente comme un nœud installé entre les réseaux. Le routage s'effectue à partir des informations figurant dans les tables ; ces dernières contiennent les adresses du réseau (en fait d'autres passerelles) et celles des routes dites « par défaut » (c'est-à-dire des adresses de passerelles).

Les algorithmes de routage. Le choix, par les organismes de normalisation, d'un algorithme de routage qui soit performant et économique est au cœur d'enjeux industriels qui concernent un marché en pleine expansion. Les algorithmes sont construits sur

deux principes de base :

- le routage par vecteurs distants ;
- le routage LSR (Link State Routing).

L'objectif est de trouver le cheminement le plus rapide, à un instant donné, pour qu'un paquet puisse atteindre son nœud de destination.

Routage par vecteurs distants. Le principe des algorithmes de vecteurs distants consiste à construire, pour chaque nœud, une métrique qui soit composée du nombre de passerelles nécessaire pour atteindre un nœud. Le processus de calcul de la route s'effectue selon les phases suivantes :

- Chaque routeur dispose de son propre identificateur.
- Chaque routeur identifie le coût de la ligne le raccordant au prochain routeur, la valeur étant traduite par un entier dont le plus petit est l.
- Chaque routeur commence par évaluer son vecteur distant à la valeur 0 pour lui-même et infinie pour ses voisins.
- Chaque routeur transmet à ses voisins son vecteur distant, lequel met à jour ses tables de routage.
- A partir des informations reçues, chaque routeur calcule la distance minimum, exprimée en nombre de nœuds.

Ces informations sont mises à jour périodiquement, chaque fois qu'une nouvelle destination est rencontrée ou qu'un vecteur distant, pour une même destination, est constaté par le routeur.

Routage LSR. L'idée de base du Link State Routing est que chaque nœud dispose d'une topographie du réseau constituée par les ponts-routeurs régulièrement mise à jour. Le principe de son fonctionnement est le

suivant :

- Chaque routeur se charge de rencontrer ses voisins et d'enregistrer leurs noms dans ses tables.
- Chaque routeur construit une table désignée sous le nom de LSP (Line State Racket) qui contient la liste et les noms des destinations.
- Le LSP est transmis à tous ses voisins, lesquels construisent une table de tous ceux qu'ils ont reçus.
- Quand tous les LSP sont arrivés, le routeur construit un graphique à partir duquel on peut déterminer la meilleure destination possible en appliquant l'algorithme de Dijkstra.

Le routage multiprotocoles.

La technologie des routeurs est basée sur la réalisation d'un protocole de «bout en bout» qui transporte des informations en mode Full Duplex entre deux nœuds. Ce protocole (du moins dans la situation actuelle) est propriétaire (ce qui veut dire que les routeurs doivent provenir du même constructeur). La réalisation d'un routeur multiprotocoles a pour objet de transporter un trafic entre deux nœuds (ou plus) qui appartienne à plusieurs protocoles de haut niveau. Dans la pratique les constructeurs fournissent un interface logiciel permettant de réaliser la translation du protocole externe dans le protocole interne de façon biunivoque. La difficulté du routage (qui rend particulièrement complexe la réalisation de produits) est que cette opération doit être distribuée dans le temps et dans l'espace et que les décisions de routage qui sont prises pour chaque paquet dans les nœuds doivent prendre en compte cette contrainte. Un routeur multiprotocoles doit donc disposer de tables de routage et effectuer en continu les opérations suivantes :

- échange des tables de routage entre les nœuds.
- obligation pour chaque nœud de gérer l'état général du réseau afin de mettre à jour les tables de routage.
- modifier les tables en fonction des états du réseau.

Pour réaliser des routeurs multiprotocoles, il existe deux approches possibles :

- soit un équipement spécifique, connecté sur les réseaux locaux, qui prenne en compte la totalité du trafic et ne route que la partie qui l'intéresse ;
- soit le produit MPR de Novell qui transforme un PC en routeur multiprotocoles (ce PC pouvant être soit dédié à la fonction de routage, soit commun avec le serveur).

Cette dernière solution permet l'interconnexion derouteurs à travers des réseaux longue distance.

Les principes du routage multiprotocoles. Les routeurs multiprotocoles sont destinés à acheminer sur un même support de transmission (liaisons Transfix, Numéris, X25) un trafic appartenant à différents protocoles routables (lP, lPX, etc.) d'une façon transparente pour les utilisateurs finaux. Un routeur est destiné à interconnecter au moins deux réseaux locaux, c'est-à-dire que l'opération de routage consistera à acheminer - d'un nœud à l'autre - des trames Ethernet et/ou des trames Token-Ring, voire FDDI. Les routeurs vont utiliser entre eux un protocole dit « de proche en proche » dont certains sont normalisés et d'autres propriétaires (exemple CISCO avec leur protocole IGRP [Interior Gateway Routing Protocol]). Ces protocoles ont certaines propriétés qui sont, d'une part, la transparence par rapport aux données acheminées et, d'autre part, les possibilités de routage dynamique. Cette dernière propriété consiste à déterminer un certain nombre d'acheminements alternés en cas d'indisponibilité ou de surcharge d'une liaison primaire. Toute la qualité d'un routage consiste dans la façon dont cette opération est effectuée. Le routeur sait reconnaître dans les trames Ethernet et les trames SDLC le protocole de haut niveau auquel il appartient.

Dans un routeur multiprotocoles le logiciel va tester le code protocole de la trame et l'encapsuler dans les paquets du protocole interne (qui vont être acheminés d'un routeur à l'autre dans le cadre d'un protocole de « proche en proche »).

Le routage lP.

L'architecture TCP/IP est devenue un standard en matière d'interconnexion de réseaux. Cette situation est due à la richesse des concepts mis en œuvre ainsi qu'à l'universalité des implémentations disponibles. L'architecture TCP/IP est parfaitement en mesure d'assurer les mêmes fonctions qu'un gestionnaire de réseau local (comme « NetWare » ou « LAN Manager »), c'est-à-dire de serveur de fichiers, de programmes, d'impressions et d'administration du réseau.

L'adressage. Le principe de l'adressage consiste à définir deux champs différents :

- le champ réseau ;
- le champ hôte (ou nœud), le choix de leur taille étant laissé à l'utilisateur.

Un même nœud peut disposer de deux adresses, correspondant à deux rattachements physiques sur deux réseaux différents.

Classes d'adresses. II existe quatre classes d'adresses lP tenant sur 32 bits. chacune d'elles correspondant à une typologie de réseau particulière et dont le principe varie entre ces deux extrêmes :

- beaucoup de réseaux et peu de nœuds ;
- peu de réseaux et beaucoup de nœuds (dits « hôtes »).

Classe Identificateur Adresse réseau Hôte

A 0724 7 24
B 101416 14 16
C 11021 21 8
D 1110

Ce système (qui dépend de la typologie du réseau) définit une adresse totale, fournie par les couches supérieures sur 32 bits, la taille des champs-adresses « physique» et «hôte». Les paquets reçus sont remis à la couche lP et transformés par cette dernière en datagrammes qui vont alors avoir à résoudre deux problèmes importants :

- la résolution des adresses ;
- la transmission.

En premier lieu il faut établir une correspondance entre l'adresse lP et l'adresse physique (exemple, carte Ethernet tenant en 48 bits). Le mécanisme de résolution d'adresses (connu sous le nom de protocole ARP [Address Resolution Protocol]) se chargera, par dialogue, d'effectuer une correspondance entre les deux adresses (physique et logique). En second lieu il faut

résoudre le problème de la mise en relation entre l'adresse IP et celle de l'interface du PC (cette opération est à effectuer au moment de l'installation du logiciel). Un même « hôte » est en mesure de disposer de plusieurs adresses correspondant à des rattachements différents (c'est le cas des postes situés en position de passerelle ou de routeur). Les critères de choix d'un mode

d'adressage sont les suivants :

- Dans le cas où le réseau aura à se connecter sur un réseau public (Internet), l'adressage devra être conforme à celui du NIC (Network Information Center), et une demande d'homologation devra être transmise à l'INRIA (Institut national de la recherche en informatique et en automatique).
- Dans le cas où le réseau devra rester entièrement privé, nous recommandons de définir un réseau physique par département (les réseaux communiqueront entre eux par des « pc-Passerelles »). Toute remise en cause ultérieure pouvant être douloureuse, il faudra dans tous les cas prendre son temps avant de définir ce plan !

Sous-réseau. La manipulation du plan d'adressage peut présenter des contraintes lourdes d'exploitation. C'est la raison pour laquelle le concept du sous-réseau a été introduit. Le principe consiste à définir certains bits de l'adresse-réseau comme appartenant - pour le nœud considéré - à un sous-réseau et à associer un masque de taille égale à l'adresse IP dont la signification est la suivante :

- à chaque bit du masque égal à l, le bit correspondant de l'adresse IP est dit appartenir à une adresse-réseau ;
- à chaque bit du masque égal à 0, le bit correspondant de l'adresse IP est dit appartenir à un sous-réseau.

Masques de sous-réseau. Un réseau (au sens IP) a besoin d'une adresse qui lui soit spécifique ; la taille de son champ étant parfois insuffisante pour décrire le réseau il est possible de prendre des bits appartenant à l'adresse-hôte et de les allouer à l'adresse-réseau ou vice versa, ce qui conduit à déterminer un nouveau schéma d'adressage pour le sous-réseau. Pour effectuer cette modification du système d'adressage, on utilise la notion de « masque binaire », directement associé à l'adresse IP. Son principe est de définir une suite de bits = l (qui constitueront l'adresse-réseau) et de bits = 0 (qui constitueront l'adresse-hôte) que l'on désignera sous le nom de sous-réseau et à partir de laquelle on pourra effectuer les opérations de routage internes au réseau.

Protocole ARP. Chaque nœud dispose d'au moins une adresse IP ; cependant, sur un réseau donné, deux nœuds ne peuvent communiquer que s'ils disposent d'adresses réelles, reconnues par les ports de communication. Pour transmettre un paquet, le nœud émetteur doit effectuer une opération dite de mapping entre l'adresse IP et l'adresse physique. Ce problème dit « de

résolution d'adresse » a été réglé par la définition d'algorithmes de bas niveau. Une difficulté réside encore dans la structure des champs d'adressage qui ne sont pas compatibles (Ethernet a une adresse physique comportant 48 bits et IP n'en comporte que 32). Le protocole ARP (Address Resolution Protocol) est basé sur le principe suivant :

- Lorsqu'une station du réseau a besoin de connaître l'adresse physique d'une autre (alors qu'elle ne connaît que son adresse IP), elle transmet sous la forme d'un broadcast.
- La station réceptrice, reconnaissant son adresse IP, retransmet à l'émetteur son adresse physique, lequel la stocke alors dans la mémoire-cache du nœud.
- Le protocole ARP permet donc à un émetteur de connaître l'adresse physique du destinataire alors qu'il ne dispose que de son adresse IP.

Protocole RARP. Comme il existe des stations ne disposant pas d'unité où ils pourraient stocker les adresses physiques des nœuds de destination, un protocole complémentaire - RARP (Reverse Address Resolution Protocol) - a été développé qui non seulement en tient compte, mais, de plus, limite la transmission de paquets sur le réseau (opération toujours coûteuse). Ce protocole est basé sur le principe suivant lequel, si la station qui demande une adresse physique a un destinataire, celui-ci aura vraisemblablement à demander l'adresse physique de l'émetteur. Le protocole transmet donc - à l'ensemble du réseau et dans le même paquet - l'adresse IP et l'adresse physique de l'émetteur; les stations se présentant comme des serveurs RARP retransmettent leurs adresses (IP et physique) dans leur réponse.

Le routage des datagrammes. Le datagramme se présente comme un paquet transmis sur le réseau en mode dit «non connecté» (c'est-à-dire que deux paquets envoyés vers une même destination sont susceptibles de prendre deux cheminements différents). Cette situation est facile à mettre en évidence. On écrit deux programmes pour deux stations reliées à un même réseau :

- le premier programme pour transmettre des paquets en mode « datagramme » dans une boucle ;
- le second programme pour les lire et les afficher.

On s'aperçoit alors que sur 5 000 paquets transmis un certain nombre ne parviennent jamais, et que beaucoup arrivent dans le désordre. C'est la raison pour laquelle on a mis au point une technique dite de l’encapsulage qui consiste à mettre une trame dans une autre, laquelle sera transmise et acquittée (c'est ainsi que l'on encapsule des paquets IP dans des trames X25, en utilisant la norme dite « RFC 877 »). Le routage est une opération permettant d'acheminer un paquet de données en fonction de son adresse de destination et des tables de routage contenues dans les nœuds routeurs. Cependant, dans un réseau IP, les

interconnexions sont réalisées par des nœuds « Passerelles» (ou Gateway), chacun étant relié à au moins deux réseaux différents (toute machine disposant d'un rattachement physique à au moins deux réseaux est en mesure de se comporter comme une passerelle). Cette distinction entre nœud et passerelle conduit à définir deux types de routage :

- le routage direct qui consiste à transmettre des paquets d'un nœud à l'autre sur un même réseau ;
- le routage indirect qui consiste à transmettre des paquets d'un réseau à l'autre au travers d'une passerelle.

Pour que cette opération puisse se réaliser, tous les nœuds du réseau doivent comporter l'adresse de la passerelle afin que les paquets non destinés au réseau lui soient transmis ; ainsi les paquets transitent de passerelle en passerelle jusqu'à destination. Chaque passerelle contient des tables de routage, accessibles à partir des nœuds passerelles ; dans la mesure où un champ désigne l'adresse du réseau de destination, la structure du routage IP - dont le principe de l'algorithme se base sur le calcul d'adresses dit Next Hope (prochain saut) - se prête particulièrement bien à ce type de mécanisme.

Le routage GGP. La mise en place de mécanismes de routage pose deux problèmes de construction :

- quelles sont les informations à mettre dans les tables de routage ? ;
- comment (dans la mesure où la performance du réseau a un objectif constant) obtenir ces informations ?

Le principe de leur construction reste celui de la passerelle et se présente comme un nœud installé entre les réseaux. Le routage s'effectue à partir des informations contenues dans les tables. Ces dernières contiennent des adresses de réseau (en fait d'autres passerelles) et des routes dites « par défaut » (c'est-à-dire des adresses de passerelles).

L’IP Tunnelling. Le transport par TCP/IP est devenu non seulement universel, mais également un outil de connexion de protocoles hétérogènes grâce à une technique dite d'encapsulage qui consiste à mettre les données d'un protocole externe dans des paquets IP et à les reconstituer sur des nœuds de destination. Lorsqu'il s'agit à' encapsuler des protocoles dits « non routables», il faut présenter aux couches supérieures l'équivalent de ce qui est une ligne. La technique dite de Tunnelling (utilisée pour acheminer un trafic SNA [Systems Network Architecture] ou DECNET [Digital Equipment Corporation NETwork]) sur un réseau IP) consiste à créer un circuit virtuel entre le routeur d'origine et le routeur de destination que tous les paquets IP - dans lesquels auront été encapsulés les messages du protocole non routable - emprunteront.