Protocole d'informations d'acheminement (RIP)

C. Hedrick (Rutgers University)

Groupe de travail Réseau
Request for Comments : 1058
Juin 1988

Table des Matières

  1. Statut de ce document
  2. Résumé
  3. Introduction
    1. Limitations du protocole
    2. Organisation de ce document
  4. Algorithmes à vecteurs de distance
    1. S'accommoder des changements dans la topologie
    2. Éviter l'instabilité
      1. Horizon partagé
      2. Mises à jour déclenchées
  5. Spécifications du protocole
    1. Formats des messages
    2. Considérations d'adressage
    3. Temporisateurs
    4. Traitement de l'entrée
      1. demande
      2. réponse
    5. Traitement de la sortie
    6. Compatibilité
  6. Fonctions de contrôle
  7. Bibliographie

Statut de ce document

Ce RFC décrit un protocole existant d'échange d'informations d'acheminement entre des routeurs et d'autres hôtes. Il est destiné à servir de base pour le développement de logiciels de routeurs pour la communauté Internet. La distribution de ce document est libre.
Cette traduction française a été effectuée par Frédéric Delanoy.
Vous pouvez le contacter ici.

Résumé

Ce document est destiné à faire les choses suivantes :

  1. Documenter un protocole et des algorithmes qui sont actuellement largement utilisés pour l'acheminement, mais qui n'ont jamais été formellement documentés.
  2. Spécifier quelques améliorations aux algorithmes pour améliorer la stabilité des chemins dans les grands réseaux. Ces améliorations n'introduisent aucune incompatibilité avec les mises en œuvre existantes. Elles vont être incorporées dans toutes les mises en œuvre de ce protocole.
  3. Suggérer quelques fonctionnalités supplémentaires pour permettre une plus grande configurabilité et un plus grand contrôle. Ces fonctionnalités ont été spécialement développées pour résoudre des problèmes qui ont surgi dans l'utilisation réelle faite par la communauté NSFnet. Néanmoins, elles devraient avoir une utilité plus générale.

Le Protocole d'informations d'acheminement (RIP) décrit ici est fondé librement sur le programme « routed » distribué avec la Berkeley Software Distribution 4.3. Cependant, il existe plusieurs autres mises en œuvre de ce qui est supposé être le même protocole. Malheureusement, ces différentes mises en œuvre sont en désaccord sur divers points de détail. Les spécifications présentées ici représentent une combinaison des fonctionnalités empruntées à diverses mises en œuvre. Nous croyons qu'un programme conçu en suivant le présent document pourra interopérer avec routed, et avec toutes les autres mises en œuvre de RIP dont nous avons connaissance.

Notez que cette description adopte un point de vue différent de celui de la plupart des mises en œuvre existantes quant au moment où les métriques devraient être incrémentées. En procédant à un changement correspondant dans la métrique utilisée pour un réseau local, nous avons gardé la compatibilité avec d'autres mises en œuvre existantes. Reportez-vous au paragraphe 3.6 pour obtenir des détails sur ce sujet.

1. Introduction

Le présent mémoire décrit un protocole d'une série de protocoles d'acheminement fondés sur l'algorithme de Bellman-Ford (ou à vecteurs de distance). Cet algorithme a été utilisé pour des calculs d'acheminement dans les réseaux informatiques depuis les débuts d'ARPANET. Les formats et le protocole particuliers de paquet décrits ici sont fondés sur le programme « routed », qui est inclus dans la distribution Berkeley de Unix. Il est devenu un standard de facto pour l'échange d'informations d'acheminement entre routeurs et hôtes. Il est mis en œuvre dans ce but par la plupart des vendeurs commerciaux de routeurs IP. Notez néanmoins qu'un grand nombre de ces vendeurs ont leurs propres protocoles qui sont utilisés entre leurs routeurs.

Ce protocole est le plus utile comme « protocole de routeurs internes ». Dans un réseau à l'échelle d'une nation comme l'est l'Internet actuel, il est très improbable qu'un unique protocole d'acheminement soit utilisé dans la totalité du réseau. Le réseau sera plutôt organisé comme une collection de « systèmes autonomes ». Un système autonome sera en général administré par une seule entité, ou disposera au moins d'un certain degré de contrôle technique et administratif. Chaque système autonome aura sa propre technologie de routage, qui peut être différente pour des systèmes autonomes distincts. Le protocole de routage utilisé à l'intérieur d'un système autonome est référencé en tant que protocole de routeurs internes (IGP, Interior Gateway Protocol). Un protocole séparé est utilisé pour servir d'interface entre les systèmes autonomes. Le premier protocole de ce type, toujours utilisé sur Internet, est le protocole de routeurs externes (EGP, Exterior Gateway Protocol). De tels protocoles sont habituellement appelés protocoles d'acheminement inter-AS. RIP a été conçu pour fonctionner avec des réseaux de taille modérée en utilisant une technologie raisonnablement homogène. Ainsi, il convient comme IGP pour beaucoup de campus et de réseaux régionaux utilisant des lignes série dont la vitesse ne varie pas grandement. Il n'est pas destiné à une utilisation dans des environnements plus complexes. Pour plus d'information sur les situations où RIP est supposé convenir, voyez Braden et Postel [3].

RIP fait partie d'une classe d'algorithmes connue sous le nom d'« algorithmes à vecteurs de distance ». La première description de cette classe d'algorithmes connue par l'auteur est présentée dans Ford et Fulkerson  [6]. De ce fait, ils sont parfois connus sous le nom d'algorithmes de Ford-Fulkerson. Le terme Bellman-Ford est également utilisé. Il provient du fait que la formulation est fondée sur l'équation de Bellman, la base de la « programmation dynamique ». (Pour une introduction standard dans ce domaine, voyez  [1].) La présentation qui est en faite dans ce document se fonde étroitement sur  [2]. Ce texte contient une introduction aux mathématiques des algorithmes d'acheminement. Il décrit et justifie plusieurs variantes de l'algorithme présenté ici, ainsi qu'un certain nombre d'autres algorithmes liés. Les algorithmes de base décrits dans ce protocole ont déjà été utilisés dans l'acheminement informatique depuis 1969 dans ARPANET. Néanmoins, l'ancêtre spécifique de ce protocole se trouve dans les protocoles réseau de Xerox. Les protocoles PUP (voyez  [4]) utilisaient le Gateway Information Protocole pour échanger des informations d'acheminement. Une version quelque peu mise à jour de ce protocole a été adoptée pour l'architecture de systèmes de réseau Xerox (XNS, Xerox Network Systems), sous le nom de « Routing Information Protocol ». (Voyez [7].) Le routed de Berkeley est en grande partie identique au Routing Information Protocol, les adresses XNS étant remplacées par un format d'adresse plus général capable d'utiliser IP et d'autres types d'adresses, et où les mises à jour de routage sont limitées à une mise à jour toutes les 30 secondes. Du fait de cette similitude, le terme « Routing Information Protocol »(ou simplement RIP) est utilisé pour se référer à la fois au protocole XNS et au protocole utilisé par routed.

RIP est destiné à être utilisé à l'intérieur de l'Internet fond é sur IP. Internet est organisé en un grand nombre de réseaux connectés par des routeurs. Les réseaux peuvent être soit des liaisons point-à-point, soit des réseaux plus complexes comme Ethernet ou ARPANET. Les hôtes et routeurs se voient remettre des datagrammes IP adressés à un hôte quelconque. L'acheminement est la méthode par laquelle l'hôte ou le routeur décide de l'endroit où envoyer le datagramme. Il peut être capable d'envoyer le datagramme directement à la destination, si elle est l'un des réseaux directement connectés à l'hôte ou au routeur. Cependant, le cas intéressant se produit quand la destination n'est pas directement accessible. Dans ce cas, l'hôte ou le routeur essaie d'envoyer le datagramme à un routeur qui est plus proche de la destination. Le but d'un protocole d'acheminement est très simple : fournir l'information nécessaire pour effectuer un routage.

1.1 Limitations du protocole

Le présent protocole ne résout pas tous les problèmes d'acheminement imaginables. Comme mentionné plus haut, il est principalement destiné à une utilisation en tant qu'IGP, dans des réseaux raisonnablement homogènes de taille modérée. De plus, les limitations spécifiques suivantes devraient être mentionnées :

1.2 Organisation de ce document

Le corps principal de ce document est organisé en deux parties, qui occupent les deux prochaines sections :

section 2
Un développement conceptuel et une justifications des algorithmes à vecteurs de distance en général.
section 3
La description réelle du protocole.

Chacune de ces deux sections est largement autonome. La section 2 essaie de donner une présentation informelle des fondements mathématiques de l'algorithme. Notez que la présentation suit une méthode en « spirale ». Un algorithme initial, assez simple, est décrit. Ensuite, des raffinements y sont ajoutés dans les paragraphes suivants. La section 3 est la description réelle du protocole. À part en cas de référence spécifique à la section 2, il devrait être possible de mettre RIP en œuvre entièrement à partir des spécifications fournies dans la section 3.

2. Algorithmes à vecteurs de distance

L'acheminement est la tâche consistant à trouver un chemin d'un émetteur à une destination souhaitée. Dans le « modèle IP Catenet », il se réduit essentiellement à trouver des passerelles entre des réseaux. Aussi longtemps qu'un message reste sur un réseau ou sous-réseau unique, tout problème de routage est résolu par une technologie qui est spécifique du réseau. Par exemple, Ethernet et ARPANET définissent tous deux un moyen par lequel tout émetteur peut parler à toute destination spécifiée à l'intérieur de ce propre réseau. Le routage IP entre en jeu essentiellement quand les messages doivent aller d'un émetteur sur un tel réseau vers une destination située sur un autre réseau. Dans ce cas, le message doit traverser des passerelles connectant les réseaux. Si les réseaux ne sont pas adjacents, le message peut traverser plusieurs réseaux intermédiaires, et les passerelles les connectant. Une fois que le message arrive sur une passerelle située sur le même réseau que la destination, la propre technologie de ce réseau est utilisée pour atteindre la destination.

Tout au long de cette section, le terme « réseau » est utilisé de façon générique pour couvrir un seul réseau de diffusion (par exemple, Ethernet), une ligne point à point, ou l'ARPANET. Le point critique est qu'un réseau est traité comme une seule entité par IP. Soit aucun routage n'est nécessaire (comme pour une ligne point à point), soit ce routage est effectué d'une manière transparente pour IP, permettant à IP de traiter le réseau entier comme un système unique complètement connecté (comme pour un réseau Ethernet ou ARPANET). Notez que le terme « réseau » est utilisé d'une façon quelque peu différente dans les discussions concernant l'adressage IP. Un seul numéro de réseau IP peu être affecté à une collection de réseaux, où l'adressage de « sous-réseaux » est utilisé pour décrire les réseaux individuels. En fait, nous utilisons ici le terme « réseau« pour nous référer aux sous-réseaux dans le cas où un adressage des sous-réseaux est utilisé.

Un certain nombre d'approches différentes pour la découverte de routes entre réseaux sont possibles. Une manière utile de catégoriser ces approches est de se fonder sur le type d'information que les passerelles doivent s'échanger afin d'être capables de trouver des routes. Les algorithmes à vecteurs de distance sont fondés sur l'échange d'une petite quantité d'information. Chaque entité (routeur ou hôte) qui participe au protocole d'acheminement est supposée conserver de l'information sur toutes les destinations du système. Généralement, les informations concernant toutes les entités connectées au réseau sont résumées par une seule entité qui décrit le chemin vers toutes les destinations de ce réseau. Ce résumé est possible car, en ce qui concerne IP, l'acheminement intérieur d'un réseau est invisible. Chaque entrée de la base de données d'acheminement inclut le prochain routeur auquel les datagrammes destinés à l'entité devraient être envoyés. De plus, elle inclut une « métrique« mesurant la distance totale menant à l'entité. La distance est un concept quelque peu généralisé, qui peut couvrir le délai d'acheminement des messages vers l'entité, son coût d'émission en €, etc. Les algorithmes à vecteurs de distance tirent leur nom du fait qu'il est possible de calculer des routes optimales quand la seule information échangée est la liste de ces distances. En outre, l'information n'est échangée qu'entre entités adjacentes, c'est-à-dire des entités partageant un réseau commun.

Bien que l'acheminement soit la plupart du temps fondé sur des informations concernant les réseaux, il est parfois nécessaire de garder une trace des routes menant aux hôtes individuels. Le protocole RIP ne fait aucune distinction formelle entre réseaux et hôtes. Il décrit simplement l'échange d'information concernant des destinations, qui peuvent être soit des réseaux, soit des hôtes. (Notez néanmoins qu'une mise en œuvre peut choisir de ne pas prendre en charge les routes menant à des hôtes. Voyez le paragraphe 3.2) En fait, les développements mathématiques se conçoivent le plus à propos en termes de chemins d'un hôte ou routeur à l'autre. Quand on considère l'algorithme en termes abstraits, il vaut mieux se représenter une entrée d'acheminement pour un réseau comme une abréviation des entrées d'acheminement pour toutes les entités connectées à ce réseau. Ce type d'abréviation n'a de sens que parce que nous considérons que les réseaux n'ont pas de structure interne visible au niveau IP. Par conséquent, nous affectons généralement la même distance à chaque entité d'un réseau donné.

Nous disions ci-dessus que chaque entité conserve une base de données d'acheminement comprenant une entrée pour chaque destination possible du système. Une mise en œuvre réelle va probablement devoir conserver l'information suivante sur chaque destination :

adresse dans les mises en œuvre IP de ces algorithmes, cela sera l'adresse IP de l'hôte ou du réseau
routeur le premier routeur sur le chemin de destination.
interface le réseau physique qui doit être utilisé pour atteindre le premier routeur.
métrique un nombre indiquant la distance à la destination.
temporisateur la durée écoulée depuis la dernière mise à jour de l'entrée

De plus, divers fanions et d'autres informations internes seront probablement inclus. Cette base de données est initialisée par une description des entités qui sont directement connectées au système. Elle est mise à jour en fonction de l'information reçue dans les messages des routeurs voisins.

L'information la plus importante échangée entre hôtes et routeurs est celle véhiculée par les messages de mise à jour. Chaque entité qui participe au processus d'acheminement envoie des messages de mise à jour qui décrivent la base de données d'acheminement comme elle existe actuellement dans cette entité. Il est possible de maintenir des routes optimales pour le système entier en utilisant uniquement les informations obtenues depuis les entités voisines. L'algorithme utilisé pour cela sera décrit au paragraphe suivant.

Comme mentionné plus haut, le but de l'acheminement est de déterminer un chemin pour amener des datagrammes à leur destination finale. Les algorithmes à vecteurs de distance sont fond és sur un tableau de la meilleure route vers chaque destination du système. Bien sûr, pour définir quelle route est la meilleure, il faut disposer d'un moyen de mesure de sa « bonté ». On l'appelle la « métrique ».

Dans les réseaux simples, il est habituel d'utiliser une métrique qui compte simplement le nombre de routeurs qu'un message doit traverser. Dans des réseaux plus complexes, une métrique est choisie pour représenter le délai total que subit le message, son coût d'émission, ou une autre quantité pouvant être minimisée. L'exigence principale est qu'il doit être possible de représenter la métrique comme une somme de «coûts» pour les bonds individuels.

Formellement, s'il est possible de se rendre directement d'une entité i à une entité j (c'est-à-dire sans traverser d'autres routeurs intermédiaires), alors un coût d(i,j) est associé au bond entre i et j. Dans le cas normal où toutes les entités d'un réseau donné sont considérées comme similaires, d(i,j) est le même pour toutes les destinations d'un réseau donné, et représente le coût d'utilisation de ce réseau. Pour obtenir la métrique d'un chemin complet, il suffit d'additionner les coûts individuels des bonds composant la route. Dans le cadre de ce document, nous supposons que les coûts sont des entiers positifs.

Soit D(i,j) la métrique du meilleur chemin allant de l'entité i à l'entité j. Elle devrait être définie pour chaque paire d'entités. d(i,j) représente les coûts des pas individuels. Formellement, soit d(i,j) le coût du chemin direct allant de l'entité i à l'entité j. Il vaut l'infini si i et j ne sont pas des voisins immédiats. (Notez que d(i,i) égale l'infini, c'est-à-dire que nous considérons qu'il n'existe pas de connexion directe d'un nœud vers lui-même.) Puisque les coûts s'additionnent, il est facile de montrer que la meilleure métrique doit être décrite par

             D(i,i) = 0,                      pour tout i
             D(i,j) = min [d(i,k) + D(k,j)],  sinon (i différent de j)
                       k

et que les meilleurschemins débutent en allant de i aux voisins k pour lesquels d(i,k)+D(k,j) possède la valeur minimale. (Cela peut être démontré par induction sur le nombre de pas des routes.) Notez que nous pouvons limiter la deuxième équation aux k qui sont des voisins immédiats de i. Pour les autres, d(i,k) = infini, de sorte que le terme les impliquant ne peut jamais être le minimum.

Il s'avère que l'on peut calculer la métrique par un simple algorithme fond é sur ceci : l'entité i contacte ses voisins k pour qu'ils lui envoient leurs estimations des distances vers la destination j. Quand i obtient les estimations de k, il ajoute d(i,k) à chacun des nombres. C'est simplement le coût de traversée du réseau entre i et k. De temps à autre, i compare les valeurs de ses voisins et prend la plus petite.

Une preuve est données dans [2] que cet algorithme convergera vers les estimations correctes de D(i,j) en un temps fini en l'absence de changement de topologie. Les auteurs ne font que peu d'hypothèses sur l'ordre dans lequel les entités s'envoient leurs informations l'une l'autre, ou sur recalculer le minimum. En gros, les entités ne peuvent pas simplement arrêter d'envoyer des messages ou de recalculer des métriques, et les réseaux ne peuvent retarder les messages indéfiniment. (La défaillance d'une entité de routage est un changement de topologie.) De plus, leur démonstration ne fait pas d'hypothèses sur les estimations initiales de D(i,j), à part qu'elles doivent être non négatives. Le fait que ces hypothèses plutôt faibles soient suffisamment bonnes est important. Puisqu'on ne doit pas faire d'hypothèses sur le moment d'envoi des mises à jour, on peut exécuter l'algorithme de façon asynchrone en toute sécurité, c'est-à-dire que chaque entité peut envoyer des mises à jour en fonction de sa propre horloge. Les mises à jour peuvent être perdues par le réseau, pour autant qu'elles ne le soient pas toutes. Puisqu'on ne doit pas faire d'hypothèses sur la condition de démarrage, l'algorithme peut gérer les changements. Quand le système change, l'algorithme de routage commence à converger vers un nouvel équilibre, en utilisant l'ancien comme point de départ. Il est important que l'algorithme converge en un temps fini quel que soit le point de départ. Sinon, certains types de changements pourraient mener à un comportement non convergent.

L'exposé de l'algorithme donné plus haut (et sa démonstration) suppose que chaque entité conserve des copies des estimations provenant de chacun de ses voisins, et calcule de temps à autre un minimum sur tous les voisins. En fait, les mises en œuvre réelles ne le font pas nécessairement. Elles se rappellent simplement de la meilleure métrique rencontrée jusqu'ici, et de l'identité du voisin qui l'a envoyée. Elles remplacent cette information à chaque fois qu'elles en voient une meilleure (c'est-à-dire plus petite). Cela leur permet de calculer le minimum de façon incrémentale, sans avoir à stocker les données de tous les voisins.

Il y a une autre différence entre l'algorithme décrit dans les textes, et ceux utilisés dans des protocoles réels comme RIP : la description ci-dessus ferait inclure par chaque entité une entrée pour elle-même, en montrant une distance de zéro. En fait, ce n'est généralement pas le cas. Rappelez-vous que toutes les entités présentes sur un réseau sont normalement résumées en une seule entité pour le réseau. Considérez la situation d'un hôte ou d'un routeur G qui est connecté au réseau A. C représente le coût d'utilisation du réseau A (habituellement une métrique de un). (Rappelez-vous que nous supposons que la structure interne d'un réseau n'est pas visible pour IP, et que le coût de déplacement entre deux entités quelconques est par conséquent toujours le même.) En principe, G devrait obtenir un message de chaque autre entité sur le réseau A, en montrant un coût de 0 pour aller de cette entité à elle-même. G calculerait ensuite C + 0 comme la distance la séparant de H. Plutôt que G doive regarder tous ces messages identiques, l'algorithme démarre simplement en créant une entrée pour le réseau A dans sa table, et en lui affectant une métrique de C. Cette entrée pour le réseau A devrait être perçue comme un résumé des entrées de toutes les entités du réseau A. La seule entité sur A qui ne peut être récapitulée par cette entrée commune est G elle-même, car le coût du trajet entre G et G est 0, et pas C. Mais puisque nous n'avons jamais besoin de ces entrées nulles, nous pouvons nous en passer sans problème en conservant uniquement l'entrée pour le réseau A. Notez une autre implication de cette stratégie : puisque les entrées nulles ne sont absolument pas nécessaires, les hôtes ne fonctionnant pas comme routeur ne doivent pas envoyer de message de mise à jour. À l'évidence, les hôtes qui ne font pas office de routeur (c'est-à-dire les hôtes qui ne sont connectés qu'à un seul réseau) ne peuvent disposer d'autre information utile pour contribuer que leur propre entrée D(i,i) = 0. Comme ils n'ont qu'une seule interface, il est facile de voir qu'une route vers n'importe quel réseau les traversant ira simplement sur cette interface et en ressortira immédiatement. Par conséquent, le coût d'une telle route sera plus élevé que le meilleur coût d'au moins C. Puisque nous n'avons pas besoin des entrées nulles, les hôtes non-routeur n'ont aucunement besoin de participer au protocole d'acheminement.

Résumons ce qu'un hôte ou un routeur G fait. Pour chaque destination du système, G conservera une estimation de la métrique courante pour cette destination (c'est-à-dire le coût total pour l'atteindre) et l'identité du routeur voisin dont les données ont servi de base au calcul de la métrique. Si la destination est sur un réseau qui est directement connecté à G, alors G utilise simplement une entrée qui montre le coût d'utilisation du réseau, et le fait qu'aucun routeur n'est nécessaire pour atteindre la destination. Il est facile de montrer qu'une fois que le calcul a convergé vers les métriques correctes, le voisin qui est enregistré par cette technique est en fait le premier routeur sur le chemin vers la destination. (S'il y a plusieurs chemins de même coût, il s'agit du premier routeur sur l'un d'entre eux.) La combinaison de la destination, de la métrique et du routeur est typiquement référencée comme une route vers la destination avec cette métrique, en utilisant ce routeur.

La méthode vue jusqu'ici ne permet que de diminuer la métrique, car la métrique existante est conservée jusqu'à ce qu'une autre plus petite apparaisse. Il est possible que l'estimation initiale soit trop basse. Par conséquent, il doit y avoir un moyen d'augmenter la métrique. Il s'avère suffisant d'utiliser la règle suivante : supposez que la route actuelle vers une destination a la métrique D et utilise le routeur G. Si un nouveau jeu d'informations arrive depuis une autre source que G, ne mettez à jour la route que si la nouvelle métrique est meilleure que D. Mais si de nouvelles informations arrivent depuis G lui-même, mettez toujours à jour D avec la nouvelle valeur. Il est facile de montrer qu'avec cette règle, le processus de mise à jour incrémentale produit les mêmes routes qu'un calcul se souvenant de la dernière information provenant de tous les voisins et obtient un minimum explicite. (Notez que la discussion suppose à cet instant que la configuration du réseau soit statique. Elle ne prend pas en compte la possibilité qu'un système puisse tomber en panne.).

Pour résumer, voici l'algorithme à vecteurs de distance de base comme il a été développé jusqu'à présent. (Notez que ce n'est pas une description du protocole RIP. Il y a encore plusieurs raffinements à ajouter.) La procédure suivante est entreprise par chaque entité qui participe au protocole d'acheminement (Ceci doit inclure tous les routeurs du système. Les hôtes qui ne sont pas des routeurs peuvent également participer) :

2.1 S'accommoder des changements dans la topologie

La discussion ci-dessus suppose que la topologie du réseau est fixe. En pratique, les routeurs et les lignes tombent souvent en panne et redeviennent actives. Pour traiter cette possibilité, nous devons modifier légèrement l'algorithme. La version théorique de l'algorithme impliquait un minimum sur tous les voisins immédiats. Si la topologie change, le jeu de voisins change. Par conséquent, la prochaine fois qu'un calcul sera effectué, le changement sera reflété. Néanmoins, comme mentionné plus haut, les mises en œuvre réelles utilisent une version incrémentale de la minimisation. Seule le meilleur chemin vers toute destination est conservé. Si le routeur impliqué dans ce chemin connait une défaillance, ou si la connexion réseau est interrompue, le calcul ne reflèterait jamais le changement. L'algorithme énoncé jusqu'ici dépend du fait qu'un routeur avertisse ses voisins si ses métriques changent. Si le routeur a ne défaillance, il n'a alors aucun moyen de prévenir ses voisins d'un changement.

Afin de traiter les problèmes de ce type, les protocoles à vecteurs de distance doivent prendre certaines dispositions pour invalider des routes. Les détails dépendent du protocole spécifique. Par exemple, dans RIP, chaque routeur qui participe à l'acheminement envoie un message de mise à jour à tous ses voisins toutes les 30 secondes. Supposez que le chemin actuel pour le réseau N utilise le routeur G. Si nous n'avons pas de nouvelles de G depuis 180 secondes, nous pouvons supposer que soit le routeur a une défaillance, soit que la connexion nous y reliant est devenue indisponible. Ainsi donc, nous marquons le chemin comme invalide. Quand nous entendons d'un autre voisin qu'il a un chemin valide vers N, le chemin valide remplacera l'invalide. Notez que nous attendons 180 secondes avant d'invalider un chemin même si nous nous attendons à recevoir des nouvelles de chaque voisin toutes les 30 secondes. Malheureusement, des messages sont occasionnellement perdus par les réseaux. Il n'est donc probablement pas souhaitable d'invalider un chemin sur la base d'un seul message manqué.

Comme nous le verrons ci-dessous, il est utile de disposer d'un moyen d'avertir les voisins qu'il n'y a actuellement pas de chemin valide vers un réseau donné. RIP, ainsi que plusieurs autres protocoles de cette classe, effectue cela via un message de mise à jour normal, en marquant ce réseau comme inaccessible. Une valeur de métrique spécifique est choisie pour indiquer une destination injoignable ; cette valeur de métrique est plus grande que la plus grande métrique valide que l'on s'attend à voir. Dans la mise en œuvre existante de RIP, la valeur 16 est utilisée. Cette valeur est habituellement référencée comme l'« infini« , car elle est plus grande que la plus grande métrique valide. 16 peut sembler être un nombre étonnamment petit. On l'a choisi petit à ce point pour des raisons que nous verrons sous peu. Dans la plupart des mises en œuvre, la même convention est utilisée en interne pour marquer une route comme invalide.

2.2 Éviter l'instabilité

L'algorithme présenté jusqu'ici permettra toujours à un hôte ou un routeur de calculer un tableau d'acheminement correct. Néanmoins, cela n'est pas encore assez pour le rendre utile en pratique. Les preuves précitées auxquelles on se réfère montrent uniquement que les tableaux d'acheminement convergeront vers les valeurs correctes en un temps fini. Elles ne garantissent pas que ce temps sera suffisamment court pour être utile, ni ne disent ce qui arrivera aux métriques des réseaux devenus inaccessibles.

Il est assez facile d'étendre la mathématique pour traiter les routes devenues inaccessibles. La convention suggérée plus haut fera cela. Nous choisissons une grande valeur de métrique pour représenter l'« infini« . Cette valeur doit être suffisamment grande pour qu'aucune métrique réelle ne puisse l'égaler. Pour les besoins de cet exemple, nous utiliserons la valeur 16. Supposons qu'un réseau devienne inaccessible. Tous les routeurs voisins immédiats arrivent en fin de temporisation et fixent la métrique pour ce réseau à 16. Pour les besoins de l'analyse, nous pouvons supposer que tous les routeurs voisins ont obtenu un nouveau matériel les connectant directement au réseau disparu, avec un coût de 16. Puisque c'est la seule connexion au réseau disparu, tous les autres routeurs du système vont converger vers de nouveaux chemins qui traversent l'un de ces routeurs. Il est facile de voir qu'une fois que la convergence s'est produite, tous les routeus auront des métriques d'au moins 16 pour le réseau disparu. Les routeurs situés à un bond des voisines d'origine finiront avec des métriques d'au moins 17 ; ceux situés à deux bonds des voisins d'origine finiront avec des métriques d'au moins 18, etc. Comme ces métriques sont plus grandes que la valeur de métrique maximale, elles sont toutes fixées à 16. Il est évident que le système convergera maintenant vers une métrique de 16 pour le réseau disparu, et ce pour tous les routeurs.

Malheureusement, la question du temps que prendra la convergence n'est pas réductible en une réponse aussi simple. Avant d'aller plus loin, il sera utile de regarder un exemple (emprunté de [2]). Notez, à propos, que ce que nous sommes sur le point de montrer ne se passera pas avec une mise en œuvre correcte de RIP. Nous essayons de montrer pourquoi certaines fonctionnalités sont nécessaires. Notez que les lettres correspondent à des routeurs, et les lignes à des réseaux.

       A-----B
        \   / \
         \ /  |
          C  /    
          | /     
          |/      
          D
          |<=== réseau cible

Dans cet exemple, tous les réseaux ont un coût de 1, sauf le lien direct allant de C à D, qui a un coût de 10.

Chaque routeur disposera d'un tableau montrant un chemin vers chaque réseau. Néanmoins, à des fins d'illustration, nous ne montrons que les chemins menant de chaque routeur au réseau marqué au bout du diagramme.
Voici les chemins d'accès au réseau cible depuis chacun des hôtes/routeurs :

   D : directement connecté, métrique 1
   B : chemin via D, métrique 2
   C : chemin via B, métrique 3
   A : chemin via B, métrique 3

Supposons maintenant que le lien de B à D tombe en panne. Les chemins devraient maintenant être ajustés pour utiliser le lien allant de C à D. Malheureusement, cela prendra un moment pour que cela se produise. Les changements d'acheminement débutent quand B remarque que le chemin menant à D n'est plus utilisable. Pour la simplicité, le tableau ci-dessous suppose que tous les routeurs envoient des mises à jour au même moment. Le tableau montre la métrique du réseau cible, comme elle apparaît dans le tableau d'acheminement de chaque routeur.

Évolution de la métrique du réseau cible au cours du temps
Hôte via coût via coût via coût via coût via coût via coût
D dir* 1 dir 1 dir 1 dir 1 ... dir 1 dir 1
B inac# C 4 C 5 C 6 C 11 C 12
C B 3 A 4 A 5 A 6 A 11 A 12
A B 3 C 4 C 5 C 6 C 11 C 12

*directement connecté
#inacessible

Voici le problème : B est capable de se débarrasser du chemin en panne en utilisant un mécanisme de temporisation. Mais des vestiges de ce chemin persistent dans le système pendant une longue période. Initialement, A et C pensent toujours qu'ils peuvent atteindre D via B. Aussi, ils continuent d'envoyer des mises à jour indiquant des métriques de 3. Lors de l'itération suivante, B fera savoir qu'il peut atteindre D via soit A soit C. Bien sûr, il ne le peut pas. Les routes signalées par A et C ne sont maintenant plus envisageables, mais ils n'ont aucun moyen de déjà le savoir. Et même lorsqu'ils découvrent que leurs chemins via B se sont volatilisés, ils pensent tous deux qu'il y a un chemin disponible via l'autre. Finalement, le système converge, comme les mathématiques le soutiennent, mais cela peut prendre un peu de temps avant que cela ne se produise. Le pire cas se présente quand un réseau devient complètement inaccessible depuis une partie du système. Dans ce cas, les métriques vont s'accroître lentement d'une manière semblable à celle vue plus haut jusqu'à ce qu'elles atteignent finalement l'infini. Pour cette raison, le problème est appelé « comptage à l'infini ».

Vous devriez maintenant voir pourquoi l'« infini » doit être choisi aussi petit que possible. Si un réseau devient complètement inaccessible, il est souhaitable que le comptage à l'infini cesse dès que possible. L'infini doit être suffisamment grand pour qu'aucune route ne soit aussi longue. Mais il ne devrait pas être plus grand que nécessaire. Ainsi, le choix de l'infini est un compromis entre taille du réseau et vitesse de convergence en cas de comptage à l'infini. Les concepteurs de RIP croyaient que le protocole ne serait probablement pas utilisable dans un réseau d'un diamètre supérieur à 15.

Il y a plusieurs méthodes qui peuvent être employées pour éviter des problèmes comme celui-ci. Celles utilisées par RIP sont appelées « Horizon partagé avec empoisonnement », et « Mises à jour déclenchées«.

2.2.1 Horizon partagé

Notez que certains des problèmes exposés plus haut proviennent du fait que A et C sont engagés dans une partie de tromperie mutuelle. Chacun prétend être capable de rejoindre D via l'autre. Cela peut être évité en faisant un peu plus attention à l'endroit où l'information est envoyée. En particulier, il n'est jamais utile de proclamer l'accessibilité d'un réseau destination au(x) voisin(s) duquel(desquels) on a appris la route. L'« horizon partagé » est un mécanisme destiné à éviter les problèmes causés par l'inclusion de routes dans des mises à jour envoyées à un routeur, alors que ce routeur est lui-même à l'origine de ces informations. Le mécanisme d'« horizon partagé simple » omet les routes apprises depuis un voisin dans les mises à jour envoyées à ce voisin. L'« horizon partagé avec empoisonnement » inclut de telles routes dans les mises à jour, mais fixe leur métrique à l'infini.

Si A pense qu'il peut atteindre D via C, ses messages vers C devraient indiquer que D n'est pas joignable. Si le chemin vers C est réel, alors soit C dispose d'une connexion directe vers D, soit d'une connexion passant par un autre routeur quelconque. Le chemin de C peut éventuellement ne pas revenir à A, puisque cela forme une boucle. En indiquant à C que D est inaccessible, A se prémunit simplement contre la possibilité que C puisse s'être trompé et croire qu'il y a une route passant par A. C'est évident pour une ligne point à point. Mais considérez le cas où A et C sont connectés par un réseau à diffusion comme Ethernet, et qu'il y a d'autres routeurs sur ce réseau. Si A a un chemin via C, il devrait indiquer que D est inaccessible quand il parle à un autre routeur de ce réseau. Les autres routeurs du réseau peuvent atteindre C eux-mêmes. Ils n'auront jamais besoin de passer par A pour accéder à C. Si le meilleur chemin de A passe réellement par C, aucun autre routeur de ce réseau n'a besoin de savoir que A peut atteindre D. C'est heureux, car cela signifie que le même message de mise à jour qui a été utilisé pour C peut être utilisé pour tous les autres routeurs du même réseau. Par conséquent, les messages de mise à jour peuvent être émis par diffusion.

En général, l'horizon partagé avec empoisonnement est plus sûr que l'horizon partagé simple. Si deux routeurs possèdent des chemins pointant l'un vers l'autre, l'annonce de routes empoisonnées avec une métrique de 16 cassera la boucle immédiatement. Si les chemins empoisonnés ne sont simplement pas annoncés, les chemins erronés devront être éliminés par l'attente de l'expiration d'une temporisation. Néanmoins, l'empoisonnement a un désavantage : il accroît la taille des messages d'acheminement. Considérez le cas d'un cœur de réseau de campus connectant plusieurs bâtiments différents. Dans chaque bâtiment, il y a un routeur connectant le cœur de réseau à un réseau local. Réfléchissez à quelles mises à jour d'acheminement ces routeurs devraient procéder sur le cœur de réseau. Tout ce que le reste du réseau doit réellement savoir sur chaque routeur est l'identité des réseaux locaux qui y sont connectés. En utilisant l'horizon partagé simple, seuls ces chemins apparaîtront dans les messages de mise à jour envoyés par le routeur au cœur de réseau. Si l'horizon partagé avec empoisonnement est utilisé, le routeur doit mentionner tous les chemins qu'il apprend du cœur de réseau, avec une métrique de 16. Si le système est grand, cela peut résulter en un grand message de mise à jour, dont presque toutes les entrées indiquent des réseaux inaccessibles.

Dans un sens statique, l'annonce de chemins empoisonnés avec une métrique de 16 ne fournit pas d'information supplémentaire. S'il y a beaucoup de routeurs sur un réseau à diffusion, ces entrées supplémentaires peuvent utiliser une bande passante significative. La raison pour laquelle ils sont présents est d'améliorer le comportement dynamique. Quand la topologie change, mentionner les chemins qui ne devraient pas traverser le routeur aussi bien que ceux qui le devraient peut accélérer la convergence. Néanmoins, dans certaines situations, les gestionnaires de réseaux peuvent préférer accepter une convergence un peu plus lente afin de minimiser la surcharge due au routage. De ce fait, les mises en œuvre peuvent à leur convenance utiliser l'horizon partagé simple plutôt que l'horizon partagé avec empoisonnement, ou peuvent fournir une option de configuration permettant au gestionnaire de réseaux de choisir quel comportement utiliser. Il est également permis de mettre en œuvre des mécanismes hybrides qui annoncent certains chemins empoisonnés avec une métrique de 16 et omettent les autres. Un exemple d'un tel mécanisme serait d'utiliser une métrique de 16 pour les chemins empoisonnés pour une certaine période de temps après les changements d'acheminement les impliquant, et après cela les omettre dans les mises à jour.

2.2.2 Mises à jour déclenchées

L'horizon partagé avec empoisonnement inversé empêchera toute boucle d'acheminement n'impliquant que deux routeurs. Néanmoins, il est toujours possible d'arriver à des situations où trois routeurs sont engagés dans une partie de tromperie mutuelle. Par exemple, A peut croire qu'il a un chemin vers B, B vers C, C vers A. L'horizon partagé ne peut arrêter une telle boucle. La boucle ne sera résolue que lorsque la métrique atteindra l'infini, et le réseau impliqué sera ensuite déclaré injoignable. Les mises à jour déclenchées constituent une tentative d'accélérer cette convergence. Pour utiliser des mises à jour déclenchées, nous ajoutons simplement une règle qui dit qu'à chaque fois qu'un routeur change la métrique d'un chemin, il doit envoyer des messages de mise à jour presque immédiatement, même si ce n'est pas encore le moment d'envoi du message de mise à jour régulier. (Les détails de planification différeront de protocole à protocole. Certains protocoles à vecteurs de distance, RIP compris, spécifient un délai faible, afin d'éviter que des mises à jour déclenchées ne génèrent un trafic réseau excessif.). Notez la façon dont cela se combine avec les règles de calcul de nouvelles métriques. Supposons que le chemin allant d'un routeur à la destination N emprunte le routeur G. Si une mise à jour provient de G lui-même, le routeur récepteurdoit croire la nouvelle information, que la nouvelle métrique soit supérieure ou inférieure à l'ancienne. Si le résultat est une modification de la métrique, alors le routeur récepteur enverra des mises à jour déclenchées à tous les hôtes et routeurs qui y sont directement connectés. Ils peuvent alors à leur tour envoyer des mises à jour à leurs voisins. Le résultat est une cascade de mises à jour déclenchées. Il est facile de montrer quels hôtes et routeurs sont impliqués dans la cascade. Supposez qu'un routeur G soutienne qu'un chemin vers la destination N est périmé. G enverra des mises à jour déclenchées à tous ses voisins. Néanmoins, les seuls voisins qui croiront la nouvelle information sont ceux dont les routes vers N passent par G. Les autres routeurs et hôtes considéreront ceci comme une information sur un nouveau chemin moins bon que celui qu'ils utilisent déjà, et l'ignoreront. Les voisins dont les routes passent par G mettront à jour leurs métriques et enverront des mises à jour déclenchées à tous leurs voisins. À nouveau, seuls les voisins dont les routes les traversent y prêteront attention. Par conséquent, les mises à jour déclenchées se propageront vers l'arrière le long de tous les chemins menant à la passerelle G, en mettant à jour les métriques pour leur donner la valeur « infini ». Cette propagation s'arrêtera dès qu'elle atteindra une partie du réseau dont la route vers la destination N emprunte un autre chemin.

Si le système pouvait rester tranquille lorsque la cascade de mises à jour déclenchées se produit, il serait possible de prouver que le comptage à l'infini ne se produira jamais. Les mauvaises routes seront toujours supprimées immédiatement, et aucune boucle d'acheminement ne pourrait se former.

Malheureusement, la réalité n'est pas aussi idyllique. Pendant que les mises à jour déclenchées sont envoyées, des mises à jour régulières peuvent se produire au même moment. Les routeurs qui n'ont pas encore reçu la mise à jour déclenchée enverront toujours de l'information fond ée sur le chemin qui n'existe plus. Il est possible qu'après que la mise à jour déclenchée ait traversé un routeur, elle puisse recevoir une mise à jour normale de l'un des routeurs qui n'a pas encore été prévenu. Cela pourrait reconstituer un vestige orphelin du chemin défectueux. Si les mises à jour déclenchées se produisent suffisamment rapidement, c'est très improbable. Néanmoins, le comptage à l'infini est toujours possible.

3. Spécifications du protocole

RIP est destiné à permettre à des hôtes et routeurs d'échanger des informations pour calculer des chemins au travers d'un réseau IP. RIP est un protocole à vecteurs de distance. Il possède donc les fonctionnalités générales décrites dans la section 2. RIP peut être mis en œuvre à la fois par les hôtes et par les routeurs. Comme dans la plupart de la documentation IP, le terme « hôte » sera utilisé ici indifféremment pour désigner l'un ou l'autre. RIP est utilisé pour véhiculer de l'information sur les chemins vers des « destinations » pouvant être des hôtes individuels, des réseaux, ou une destination spéciale utilisée pour transmettre une route par défaut.

Tout hôte utilisant RIP est censé disposer d'interfaces vers un ou plusieurs réseaux. Ils sont référencés sous le terme de « réseaux directement connectés ». Le protocole se fonde sur l'accès à certaines informations sur chacun de ces réseaux. La plus importante est sa métrique ou « coût ». La métrique d'un réseau est un entier compris entre 1 et 15 inclus. Elle est définie d'une manière non spécifiée par ce protocole. La plupart des mises en œuvre existantes utilisent toujours une métrique de 1. De nouvelles mises en œuvre devraient permettre à l'administrateur système de fixer le coût de chaque réseau. En plus du coût, chaque réseau aura un numéro de réseau IP et le gabarit de sous-réseau associé. Ils doivent être spécifiés par l'administrateur système d'une façon non spécifiée dans le présent protocole.

Notez que les règles spécifiées au paragraphe 3.2 supposent qu'il y a un seul gabarit de sous-réseau qui s'applique à chaque réseau IP, et que seuls les gabarits de sous-réseau des réseaux directement connectés sont connus. Il peut y avoir des systèmes qui utilisent des gabarits de sous-réseau pour différents sous-réseaux à l'intérieur d'un unique réseau. Il peut également y avoir des exemples où il vaut mieux qu'un système connaisse les gabarits de sous-réseau des réseaux distants. Néanmoins, de telles situations requerraient des modifications des règles qui gouvernent la propagation d'informations sur les sous-réseaux. De telles modifications soulèvent des problèmes d'interopérabilité, et doivent donc être considérées comme une modification du protocole.

Chaque hôte qui met en œuvre RIP doit posséder un tableau d'achemine ment. Ce tableau comprend une entrée pour chaque destination qui est accessible via le système décrit par RIP. Chaque entrée contient au moins les informations suivantes :

Les entrées pour les réseaux directement connectés sont définies par l'hôte, en utilisant des informations récoltées par des moyens non spécifiés par ce protocole. La métrique d'un réseau directement connecté est définie par le coût de ce réseau. Dans les mises en œuvre RIP existantes, 1 est toujours utilisé comme coût. Dans ce cas, la métrique RIP se réduit à un simple comptage des bonds. Des métriques plus complexes peuvent être utilisées quand il est préférable d'indiquer une priorité de certains réseaux sur d'autres, par exemple à cause de différences de bande passante ou de fiabilité.

Les mises en œuvre peuvent également choisir de permettre à l'administrateur système d'entrer des chemins supplémentaires. Ceux-ci seraient plus que probablement des chemins vers des hôtes ou réseaux à l'extérieur de la portée du système d'acheminement.

Les entrées pour les destinations autres que celles initiales sont ajoutées et mises à jour par les algorithmes décrits dans les paragraphes suivants.

Afin que le protocole fournisse une information d'acheminement complète, chaque routeur du système doit participer au processus. Les hôtes qui ne sont pas des routeurs ne doivent pas participer, mais beaucoup de mises en œuvre prennent des dispositions pour qu'ils écoutent l'information d'acheminement afin de leur permettre d'entretenir leurs tableaux d'acheminement.

3.1 Formats des messages

RIP est un protocole fond é sur UDP. Chaque hôte utilisant RIP dispose d'un processus de routage qui envoie et reçoit des datagrammes sur l'accès UDP n° 520. Toutes les communications adressées à un processeur RIP d'un autre hôte sont envoyées à l'accès 520. Tous les messages de mise à jour d'acheminement sont envoyés depuis l'accès 520. Des messages de mise à jour d'acheminement non sollicités ont l'accès de source et de destination égal à 520. Ceux envoyés en réponse à une requête sont envoyés à l'accès d'où provenait la requête. Des requêtes spécifiques et des requêtes de déboggage peuvent être envoyées depuis des accès différents de 520, mais sont dirigées vers l'accès 520 de la machine cible.

Il y a des dispositions dans le protocole qui permettent des processus RIP « silencieux ». Un processus silencieux n'envoie normalement aucun message. Néanmoins, il écoute les messages envoyés par d'autres. Un RIP silencieux pourrait être utilisé par des hôtes qui n'agissent pas en tant que routeurs, mais qui veulent écouter les mises à jour d'acheminement afin de surveiller les routeurs locaux et de tenir leurs tableaux d'acheminement interne à jour. (Voir dans [5] un exposé sur les différentes manières dont les hôtes peuvent garder trace de la topologie d'un réseau.) Un routeur qui a perdu le contact avec tous ses réseaux sauf un pourrait choisir de devenir silencieux, puisqu'il n'est alors plus un routeur.

Néanmoins, cela ne devrait pas être fait s'il y a la moindre possibilité que des routeurs voisins dépendent de ses messages pour détecter que le réseau en panne est à nouveau opérationnel. (Le programme 4BSD routed utilise les paquets d'acheminement pour surveiller le fonctionnement des liaisons point à point.) Le format de paquet est donné à la Figure 1.

Format des datagrammes contenant de l'information réseau. La taille des champs est donnée en octets. Sauf spécification contraire, les champs contiennent des entiers binaires, dans l'ordre Internet normal avec l'octet de plus fort poids en premier. Chaque chiffre au-dessus de la ligne supérieure représente un bit.

       0                   1                   2                   3 
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
      | commande (1)  | version (1)   |      doit être zéro (2)        |
      +---------------+---------------+--------------------------------+
      | id. de famille d'adresses (2) |      doit être zéro (2)        |
      +-------------------------------+--------------------------------+
      |                         adresse IP (4)                         |
      +----------------------------------------------------------------+
      |                       doit être zéro (4)                       |
      +----------------------------------------------------------------+
      |                       doit être zéro (4)                       |
      +----------------------------------------------------------------+
      |                           métrique (4)                         |
      +----------------------------------------------------------------+
                                      .
                                      .
                                      .

La partie du datagramme allant de l'identifiant de famille d'adresse à la métrique peut apparaître jusqu'à 25 fois.
L'adresse IP est l'adresse Internet habituelle sur 4 octets, dans l'ordre de transmission réseau.

Figure 1 : Format de paquet

Chaque datagramme contient une commande, un numéro de version et des arguments éventuels. Ce document décrit la version 1 du protocole. Les détails du traitement du n° de version sont décrits au paragraphe 3.4. Le champ « commande » est utilisé pour spécifier l'objet de ce datagramme. Voici un résumé des commandes mises en œuvre dans la version 1 :

commande description
1 demande Une requête au système répondant indiquant d'envoyer tout ou partie de sa table de routage.
2 réponse Un message contenant tout ou partie de la table de routage de l'émetteur. Ce message peut être envoyé en réponse à une requête ou sur demande, ou peut être un message de mise à jour généré par l'émetteur.
3 traceon Obsolète. Les messages contenant cette commande doivent être ignorés.
4 traceoff Obsolète. Les messages contenant cette commande doivent être ignorés.
5 réservé Cette valeur est utilisée par Sun Microsystems pour ses propres besoins. Si de nouvelles commandes sont ajoutées dans une version ultérieure, elles devraient commencer par 6. Les messages contenant cette commande peuvent être ignorés en toute sécurité par les implémentations qui choisissent de ne pas y répondre.

Pour demande et réponse, le reste du datagramme contient une liste des destinations, avec des informations sur chacune d'entre elles. Chaque entrée de cette liste contient un réseau ou un hôte de destination, et sa métrique associée. Le format de paquet est destiné à permettre à RIP de transporter des informations d'acheminement pour plusieurs protocoles différents. De ce fait, chaque entrée a un identificateur de famille d'adresse indiquant quel type d'adresse est spécifié dans cette entrée. Le présent document ne décrit que l'acheminement pour les réseaux de type Internet. L'identifiant de famille d'adresse pour IP est 2. Aucune des mises en œuvre de RIP auxquelles l'auteur a accès ne met en œuvre d'autre type d'adresse. Néanmoins, pour permettre un développement futur, les mises en œuvre doivent sauter les entrées qui spécifient des familles d'adresses qui ne sont pas supportées par la mise en œuvre. (La taille de ces entrées sera la même que celle d'une entrée spécifiant une adresse IP.) Le traitement du message continue normalement après que toutes les entrées non acceptées aient été sautées. L'adresse IP est l'adresse Internet normale, mémorisée sur 4 octets dans l'ordre de transmission du réseau. Le champ 'métrique' doit contenir une valeur comprise entre 1 et 15 inclus, spécifiant la métrique actuelle pour la destination, ou la valeur 16, qui indique que la destination est inaccessible. Chaque chemin envoyé par un routeur supplante tout chemin vers la même destination provenu précédemment du même routeur.

La taille maximale d'un datagramme est de 512 octets. Cela n'inclut que les parties du datagramme décrites ci-dessus. Les en-têtes IP et UDP ne sont pas pris en compte. Les commandes impliquant des informations sur le réseau permettent que l'information soit éclatée sur plusieurs datagrammes. Aucune disposition spéciale n'est nécessaire pour les continuations, car des résultats corrects se produiront si les datagrammes sont traités individuellement.

3.2 Considérations d'adressage

Comme indiqué dans la section 2, l'acheminement à vecteurs de distance peut être utilisé pour décrire des chemins vers des hôtes individuels ou vers des réseaux. Le protocole RIP permet n'importe laquelle de ces possibilités. Les destinations apparaissant dans les messages demande et réponse peuvent être des réseaux, des hôtes, ou un code spécial utilisé pour indiquer une adresse par défaut. En général, les types de chemins réellement utilisés dépendront de la stratégie d'acheminement utilisée pour le réseau particulier. Beaucoup de réseaux sont configurés de telle sorte qu'une information d'acheminement pour les hôtes individuels n'est pas nécessaire. Si chaque hôte d'un réseau ou d'un sous-réseau donné est accessible au travers des mêmes routeurs, il n'y a alors aucune raison de mentionner les hôtes individuels dans les tableaux d'acheminement. Néanmoins, les réseaux qui incluent des lignes point à point requièrent parfois que les routeurs gardent une trace des chemins vers certains hôtes. La nécessité ou non de cette fonctionnalité dépend de l'adressage et de l'approche de l'acheminement utilisés dans le système. Par conséquent, certaines mises en œuvre peuvent choisir de ne pas prendre en charge les routes vers des hôtes. Si les routes vers des hôtes ne sont pas prises en charge, elles doivent être supprimées quand elles sont reçues dans des messages réponse. (Voir le paragraphe 3.4.2)

Les formats de paquets RIP ne font pas de distinction entre les différents types d'adresse. Les champs qui sont étiquetés « adresse » peuvent contenir un des éléments suivants :

Les entités qui utilisent RIP sont supposées utiliser l'information la plus spécifique disponible lors de l'acheminement d'un datagramme, c'est-à-dire que lors de l'acheminement d'un datagramme, son adresse de destination doit d'abord être comparée à la liste des adresses d'hôtes. Ensuite, elle doit être examinée pour voir si elle correspond à un numéro de sous-réseau ou de réseau connu. Finalement, si aucun des cas précités ne convient, le chemin par défaut est utilisé.

Quand un hôte évalue les 'informations qu'il reçoit via RIP, son interprétation d'une adresse dépend de sa connaissance ou non du gabarit de sous-réseau qui s'applique au réseau. Si c'est le cas, il est alors possible de déterminer la signification de l'adresse. Par exemple, considérons le réseau 128.6. Il a un gabarit de sous-réseau de 255.255.255.0. Donc, 128.6.0.0 est un numéro de réseau, 128.6.4.0 est un numéro de sous-réseau, et 128.6.4.1 est une adresse d'hôte. Néanmoins, si l'hôte ne connaît pas le gabarit de sous-réseau, l'évaluation de l'adresse peut être ambiguë. S'il y a une partie hôte non nulle, il n'y a aucun mécanisme sûr pour déterminer si l'adresse représente un numéro de sous-réseau ou une adresse d'hôte. Comme un numéro de sous-réseau serait inutile sans le gabarit de sous-réseau, les adresses sont supposées représenter des hôtes dans cette situation. Afin d'éviter ce type d'ambiguïté, les hôtes ne doivent pas envoyer de routes de sous-réseaux aux hôtes dont on ne peut présumer qu'ils connaissent le gabarit de sous-réseau approprié. Normalement, les hôtes ne connaissent les gabarits de sous-réseau que des réseaux directement connectés. Par conséquent, à moins que des dispositions spéciales n'aient été prises, les chemins menant à un sous-réseau ne doivent pas être envoyés à l'extérieur du réseau dont le sous-réseau fait partie.

Ce filtrage est exécuté par les routeurs à la « frontière » du réseau comportant des sous-réseaux. Ce sont desrouteurs qui connectent ce réseau à d'autres réseaux. À l'intérieur d'un réseau découpé en sous-réseaux, chaque sous-réseau est traité comme un réseau individuel. Les entrées d'acheminement pour chaque sous-réseau sont passées en revue par RIP. Néanmoins, les routeurs frontière n'envoient aux hôtes des autres réseaux qu'une seule entrée pour le réseau entier. Cela signifie qu'un routeur frontière enverra des informations différentes à des voisins différents. Pour les voisins connectés au réseau composé de sous-réseaux, il génère une liste de tous les sous-réseaux auxquels il est directement connecté, en utilisant le n° de sous-réseau. Pour les voisins connectés à d'autres réseaux, il crée une unique entité pour le réseau entier, en montrant la métrique associée à ce réseau. (Cette métrique serait normalement la plus petite métrique des sous-réseaux auquel le routeur est rattaché.)

De façon similaire, les routeurs frontières ne doivent pas mentionner de chemin d'hôtes vers des hôtes situés dans l'un des réseaux directement connectés dans les messages envoyés à d'autres réseaux. Ces chemins seront synthétisés par l'entrée unique pour le réseau considéré comme un tout. Nous ne spécifions pas ce qu'il faut faire avec les chemins d'hôtes de réseaux « distants » (c'est-à-dire les hôtes ne faisant pas partie d'un des réseaux directement connectés). Généralement, ces chemins indiquent un hôte qui est accessible via une route qui ne prend pas en charge d'autres hôtes sur le réseau duquel fait partie l'hôte en question.

L'adresse spéciale 0.0.0.0 est utilisée pour décrire un chemin par défaut. Un chemin par défaut est utilisé quand il n'est pas commode de faire la liste de tous les réseaux possibles dans les mises à jour RIP, et quand un ou plusieurs des routeurs proches connectés au système sont prêts à traiter du trafic à destination de réseaux qui ne sont pas explicitement sur la liste. Ces routeurs devraient créer des entrées RIP pour l'adresse 0.0.0.0, tout comme si c'était un réseau auquel ils sont connectés. La mise en œuvre pratique de la création d'entrées 0.0.0.0 par un routeur est laissée aux soins de la mise en œuvre. La plupart du temps, l'administrateur système disposera d'un moyen de spécifier quels routeurs devraient créer des entrées pour 0.0.0.0. Néanmoins, d'autres mécanismes sont possibles. Par exemple, une mise en œuvre pourrait décider que tout routeur parlant EGP devrait être déclaré routeur par défaut. Il peut être utile de permettre à l'administrateur réseau de choisir la métrique à utiliser pour ces entrées. S'il y a plus d'un routeur par défaut, cela lui permettra d'exprimer une priorité de l'un sur l'autre. Les entrées pour 0.0.0.0 sont traitées par RIP exactement de la même manière qu'un réseau réel ayant cette adresse. Néanmoins, l'entrée est utilisée pour acheminer tout datagramme dont l'adresse de destination ne correspond à aucun des réseaux du tableau. Les mises en œuvre ne sont pas obligés de prrendre en charge cette convention. Néanmoins, cela est fortement recommandé. Les mises en œuvre qui ne supportent pas 0.0.0.0 doivent ignorer les entrées comportant cette adresse. Dans de telles situations, elles ne doivent pas propager l'entrée dans leurs propres mises à jour RIP. Les administrateurs système devraient s'assurer que les chemins vers 0.0.0.0 ne se propagent pas plus loin que prévu. Généralement, chaque système autonome a son routeur par défaut préféré. Par conséquent, les chemins impliquant 0.0.0.0 ne devraient généralement pas quitter la frontière d'un système autonome. Les mécanismes permettant d'imposer cela ne sont pas spécifiés dans le présent document.

3.3 Temporisateurs

Ce paragraphe décrit tous les événements déclenchés par des temporisateurs.

Toutes les 30 secondes, le processus de sortie reçoit l'ordre de générer une réponse complète pour chaque routeur voisin. Quand il y a beaucoup de routeurs sur un même réseau, ces routeurs ont tendance à se synchroniser entre eux de sorte qu'ils émettent tous des mises à jour au même moment. Cela peut se produire à chaque fois que le temporisateur de 30 secondes est affecté par la charge de travail du système. Il est indésirable que ces messages de mise à jour deviennent synchronisés, car cela peut mener à des collisions inutiles sur les réseaux à diffusion. De ce fait, les mises en œuvre doivent prendre une des deux précautions suivantes :

Il y a deux temporisateurs associés à chaque chemin, une « temporisation » et un « temporisateur de ramassage des déchets »i. À l'expiration de la temporisation, le chemin n'est plus valide. Néanmoins, il est conservé dans le tableau pour un court moment, le temps que les voisins soient prévenus que le chemin à été abandonné. À l'expiration du temporisateur de ramassage des déchets, la route est finalement supprimée des tableaux.

La temporisation est initialisée quand un chemin est établi, et à chaque fois qu'un message de mise à jour est reçu pour le chemin. Si 180 secondes s'écoulent depuis le dernier moment où la temporisation a été initialisée, le chemin est considéré avoir dépassé sa période de validité, et le processus de suppression que nous sommes sur le point de décrire est démarré à cet effet.

Les suppressions peuvent se produire pour une des deux raisons suivantes :

  1. la temporisation expire
  2. la métrique est fixée à 16 du fait de la réception d'une mise à jour depuis le routeur en cours

(Voir au paragraphe 3.4.2 un exposé sur le traitement des mises à jour provenant d'autres routeurs.) Dans chacun des cas, les événements suivants se produisent :

Jusqu'au moment où le temporisateur de ramassage des déchets expire, le chemin est inclus dans toutes les mises à jour envoyées par cet hôte, avec une métrique de 16 (infini). Quand le temporisateur de ramassage des déchets expire, le chemin est supprimé des tableaux.

Si un nouveu chemin vers ce réseau est établi alors que le temporisateur de ramassage des déchets est en cours de fonctionnement, le nouveau chemin remplacera celui qui est sur le point d'être effacé. Dans ce cas, le temporisateur de ramassage des déchets doit être réinitialisé.

Voir au paragraphe 3.5 un exposé sur le délai requis dans l'exécution de mises à jour déclenchées. Bien que les mises en œuvre de ce délai requièrent un temporisateur, il est plus naturel d'en discuter au paragraphe 3.5 qu'ici.

3.4 Traitement de l'entrée

Ce paragraphe décrira le traitement des datagrammes reçus sur l'accès UDP 520. Avant de traiter les datagrammes en détail, certaines vérifications de format générales doivent être faites. Elles dépendent du champ n° de version du datagramme de la façon suivante :

0 Les datagrammes dont le numéro de version est 0 doivent être ignorés. Ils proviennent d'une version précédente du protocole, dont le format de paquet était spécifique de la machine.
1 Les datagrammes dont le numéro de version est 1 doivent être traités comme décrit dans le reste de cette spécification. Tous les champs qui sont étiquetés plus haut « doit être à zéro » doivent être vérifiés. Si l'un de ces champs contient une valeur non nulle, le message entier doit être ignoré.
>1 Les datagrammes dont le numéro de version est supérieur à 1 doivent être traités comme décrit dans le reste de cette spécification. Tous les champs qui sont étiquetés plus haut « doit être à zéro » doivent être ignorés. De futures versions du protocole pourraient placer des données dans ces champs. Les mises en œuvre de la version 1 doivent ignorer ces données supplémentaires et ne traiter que les champs spécifiés dans ce document.

Après avoir vérifié le numéro de version et effectué toutes les vérifications préliminaires, le traitement dépendra de la valeur du champ de commande.

3.4.1 Demande

Demande est utilisé pour demander une réponse contenant tout ou partie du tableau d'acheminement de l'hôte. [Notez que le terme « hôte » est utilisé indifféremment pour désigner un hôte ou un routeur ; dans la plupart des cas, il serait inhabituel qu'un hôte non-routeur envoie des messages RIP.] Normalement, les requêtes sont envoyés par diffusion, à partir d'un accès 520 UDP de source. Dans ce cas, les processus silencieux ne répondent pas à la requête. Les processus silencieux sont par définition des processus qui ne devraient normalement pas voir d'information dacheminement. Néanmoins, il peut y avoir des situations impliquant la surveillance de routeurs où l'on souhaite que même un processus silencieux puisse examiner le tableau d'acheminement. Dans ce cas, la requête devrait être envoyée depuis un n° d'accès UDP différent de 520. Si une requête provient de l'accès 520, les processus silencieux ne répondent pas. Si la requête provient de tout autre accès, les processus doivent répondre même s'ils sont silencieux.

La requête est traitée entrée par entrée. S'il n'y a pas d'entrée, aucune réponse n'est fournie. Il y a un cas particulier : s'il y a exactement une entrée dans la requête, avec un identifiant de famille d'adresses de valeur nulle (signifiant « non spécifié »), et une métrique de valeur infinie (c'est-à-dire 16 pour les mises en œuvre actuelles), il s'agit d'une requête d'envoi de l'entièreté du tableau d'acheminement. Dans ce cas, un appel est fait au processus de sortie pour envoyer le tableau d'acheminement à l'accès requis.

Mis à part ce cas particulier, le traitement est assez simple. Parcourez la liste des entrées de la requête une par une de haut en bas. Pour chaque entrée, recherchez la destination dans la base de données d'acheminement de l'hôte. S'il y a un chemin, placez la métrique de ce chemin dans le champ métrique dans le datagramme. S'il n'existe pas de chemin vers la destination spécifiée, placez l'infini (c'est-à-dire 16) dans le champ métrique du datagramme. Une fois que toutes les entrées ont été remplies, fixez la commande à 'réponse' et renvoyez le datagramme à l'accès d'où il provenait.

Notez qu'il y a une différence de traitement si la requête est relative à un groupe de destinations spécifié, ou à un tableau d'acheminement entier. Si la requête demande un tableau d'hôtes complet, un traitement de sortie normal est effectué. Cela inclut l'horizon partagé (voir le paragraphe 2.2.1) et le masquage de sous-réseaux (paragraphe 3.2), de sorte que certaines entrées du tableau d'acheminement ne seront pas montrés. Si la requête réclame des entrées spécifiques, elles sont recherchées dans le tableau d'acheminement et l'information est retournée. Aucun traitement d'horizon partagé n'est effectué, et les sous-réseaux sont retournés si c'est requis. Nous prévoyons que ces requêtes vont être utilisées dans différents contextes. Quand un hôte démarre pour la première fois, il diffuse ses requêtes sur chaque réseau connecté en demandant un tableau d'acheminement complet. En général, nous supposons que les tableaux d'acheminement complets vont être employés pour mettre à jour le tableau d'acheminement d'un autre hôte. Pour cette raison, l'horizon partagé et tous les autres filtrages doivent être utilisés. Les requêtes pour des réseaux spécifiques ne sont faites que par des logiciels de diagnostic, et ne sont pas utilisées pour l'acheminement. Dans ce cas, le requérant voudrait connaître le contenu exact de la base de données d'acheminement, et ne voudrait pas qu'on lui cache la moindre information.

3.4.2 Réponse

Des réponses peuvent être reçues pour plusieurs raisons différentes :

Le traitement est identique quelle que soit la façon dont les réponses ont été générées.

Puisque le traitement d'une réponse peut mettre à jour le tableau d'acheminement de l'hôte, la validité de la réponse doit être vérifiée avec soin. La réponse doit être ignorée si elle ne provient pas de l'accès 520. L'adresse IP source devrait être examinée pour voir si le datagramme provient d'un voisin valide. La source du datagramme doit se situer sur un réseau directement connecté. Cela vaut également la peine de vérifier si la réponse provient de l'une des adresses propres de l'hôte. Les interfaces situées sur des réseaux à diffusion peuvent recevoir des copies de leur propre diffusion immédiatement. Si un hôte traite sa propre sortie comme une nouvelle entrée, une certaine confusion en résultera certainement, et de tels datagrammes doivent être ignorés (sauf dans les circonstances formulées dans le prochain paragraphe).

Avant de traiter réellement une réponse, il peut être utile d'utiliser son existence comme entrée pour un processus gardant une trace de l'état de l'interface. Comme mentionné plus haut, nous invalidons un chemin quand nous n'avons pas reçu de nouvelles de son routeur depuis un certain temps. Cela fonctionne bien pour les chemins provenant d'un autre routeur. Il est également souhaitable de savoir quand l'un de nos réseaux directement connectés est tombé en panne. Ce document ne spécifie aucune méthode particulière pour faire cela, car de telles méthodes dépendent des caractéristiques du réseau et de l'interface réseau rattachée. Néanmoins, de telles méthodes impliquent souvent d'écouter les datagrammes arrivant sur cette interface. Des datagrammes arrivants peuvent être utilisés comme une indication que cette interface fonctionne. Néanmoins, il y a lieu de faire attention, car il est possible qu'une interface tombe en panne de manière telle que des datagrammes d'entrée sont reçus, mais les datagrammes de sortie ne sont jamais envoyés avec succès.

Maintenant que le datagramme dans son ensemble a été validé, traitez ses entrées une à une. À nouveau, commencez en faisant la validation. Si la métrique est plus grande que l'infini, ignorez l'entrée. (Cela devrait être impossible, si l'autre hôte fonctionne correctement. Des métriques incorrectes et autres erreurs de format devraient probablement provoquer des alertes ou être enregistrées.) Regardez ensuite l'adresse destination. Vérifiez l'identificateur de famille d'adresses. S'il ne possède pas une valeur attendue (par exemple, 2 pour les adresses Internet), ignorez l'entrée. Détectez maintenant différents types d'adresses inappropriées. Ignorez l'entrée si l'adresse est de classe D ou E, ou si elle est située sur le réseau 0 (sauf pour 0.0.0.0, si les routes par défaut sont acceptées), ou sur le réseau 127 (le réseau de bouclage). Vérifiez également si c'est une adresse de diffusion, c'est-à-dire dont la partie hôte n'est composée que de chiffres 1 sur un réseau qui accepte la diffusion, et ignorez de telles entrées. Si la mise en œuvre a choisi de ne pas prendre en charge les routes d'hôtes (voir au paragraphe 3.2), vérifiez si la partie hôte de l'adresse est non nulle ; si c'est le cas, ignorez l'entrée

Rappelez vous que le champ 'adresse' contient un certain nombre d'octets inutilisés. Si le n° de version du datagramme est 1, ils doivent être examinés. Si l'un d'entre eux n'est pas nul, l'entrée doit être ignorée. (Beaucoup de ces cas indiquent que l'hôte initiateur du message ne fonctionne pas correctement. Par conséquent, une certaine forme d'enregistrement d'erreur ou d'alerte devrait être mise en place.)

Mettez à jour la métrique en ajoutant le coût du réseau par lequel le message est arrivé. Si le résultat est supérieur à 16, utilisez 16, c'est-à-dire

   métrique = min (métrique + coût, 16)

Examinez maintenant l'adresse pour voir s'il y a déjà un chemin la rejoignant. En général, si ce n'est pas le cas, il faut en ajouter un. Néanmoins, il y a plusieurs exceptions. Si la métrique est infinie, n'ajoutez pas d'entrée. (On pourrait en mettre à jour une existante, mais on n'ajoute pas de nouvelles entrées possédant une métrique infinie.) Il faut éviter d'ajouter des chemins vers des hôtes si l'hôte fait partie d'un réseau ou sous-réseau pour lequel nous disposons d'un chemin au moins aussi bon. Si aucune de ces exceptions ne s'applique, ajoutez une nouvelle entrée dans la base de données d'acheminement. Ceci inclut les actions suivantes :

S'il y a un chemin existant, comparez d'abord les routeurs. Si ce datagramme provient du même routeur que le chemin existant, réinitialisez la temporisation. Ensuite, comparez les métriques. Si le datagramme provient du même routeur que le chemin existant et que la nouvelle métrique est différente de l'ancienne, ou si la nouvelle métrique est plus petite que l'ancienne, effectuez les actions suivantes :

Si la nouvelle métrique est 16 (infini), cela démarre le processus d'effacement de la route. La route n'est alors plus utilisée pour router les paquets, et le temporisateur d'effacement est démarré (voir section 3.3). Notez qu'un effacement n'est entamé que si la métrique est d'abord fixée à 16. Si la métrique valait déjà 16, alors une nouvelle suppression n'est pas entreprise. (Entamer un effacement déclenche un temporisateur. L'ennui est que nous ne voulons pas réinitialiser le temporisateur toutes les 30 secondes, car de nouveaux messages arrivent avec une métrique infinie.)

Si la nouvelle métrique est identique à l'ancienne, le plus simple est de ne rien faire de plus (au-delà de réinitialiser la temporisation, comme spécifié ci-dessus). Néanmoins, le routed 4BSD utilise une heuristique supplémentaire ici. Normalement, il est absurde de passer à un chemin de même métrique que le chemin existant mais avec un routeur différent. Néanmoins, si le chemin existant montre des signes de dépassement possible du délai, il peut être préférable de passer immédiatement à un chemin de remplacement de même valeur, plutôt que d'attendre que la temporisation se produise. (Voyez au paragraphe 3.3 l'exposé sur les temporisations.) Par conséquent, si la nouvelle métrique est identique à l'ancienne, routed examine l'état de la temporisation pour le chemin existant. Si on est au moins à mi-chemin de l'expiration de sa période de validité, routed passe au nouveau chemin, c'est-à-dire que le routeur est remplacé par celui de la source du message actuel. Cette heuristique est facultative.

Toute entrée échouant à ces essais est ignorée, car elle n'est pas meilleure que le chemin actuel.

3.5 Traitement de la sortie

Ce paragraphe décrit le traitement utilisé pour créer des messages de réponse contenant tout ou partie du tableau d'acheminement. Ce traitement peut être déclenché de l'une des manières suivantes :

Avant de décrire la façon dont un message est généré pour chaque réseau directement connecté, nous commenterons la façon dont les destinations sont choisies pour les deux derniers cas. Normalement, quand une réponse doit être envoyée à toutes les destinations (c'est-à-dire que la mise à jour régulière, ou une mise à jour déclenchée, est en cours de préparation), une réponse est envoyée à l'hôte situé à l'autre bout de chaque liaison point à point, et une réponse est diffusée sur tous les réseaux connectés qui acceptent la diffusion. Ainsi donc, une réponse est préparée pour chaque réseau directement connecté et envoyée à l'adresse correspondante (de la destination ou de diffusion). Dans la plupart des cas, cela atteint tous les routeurs voisins. Néanmoins, il y a certains cas où cela peut ne pas être assez bien. Cela peut impliquer un réseau qui n'accepte pas la diffusion (par exemple, ARPANET), ou une situation impliquant des routeurs stupides. Dans de telles circonstances, il peut être nécessaire de spécifier une liste réelle de routeurs et hôtes voisins, et d'envoyer explicitement un datagramme à chacun d'entre eux. Il revient à la mise en œuvre de décider si un tel mécanisme est nécessaire, et le cas échéant de définir comment la liste est spécifiée.

Les mises à jour déclenchées requièrent un traitement particulier pour deux raisons. Premièrement, l'expérience montre que les mises à jour déclenchées peuvent provoquer des charges excessives sur des réseaux de capacité limitée ou comportant trop de routeurs. Le protocole requiert donc que les mises en œuvre prennent des dispositions pour limiter la fréquence des mises à jour déclenchées. Après l'émission d'une mise à jour déclenchée, un temporisateur devrait être démarré pour un temps aléatoire compris entre 1 et 5 secondes. Si d'autres changements susceptibles de déclencher des mises à jour se produisent avant que le temporisateur n'expire, une simple mise à jour est déclenchée quand le temporisateur expire, et le temporisateur est ensuite fixé à une autre valeur aléatoire comprise entre 1 et 5 secondes. Une mise à jour déclenchée peut être supprimée si une mise à jour régulière est prévue avant que la mise à jour déclenchée ne soit envoyée.

Deuxièmement, les mises à jour déclenchées n'ont pas besoin d'inclure le tableau d'acheminement entier. En principe, seules les chemins qui ont été modifiés doivent être inclus. Les messages générés faisant partie d'une mise à jour déclenchée doivent donc au moins inclure les chemins dont le fanion de changement de route est défini. Ils peuvent inclure des chemins supplémentaires, ou tous les chemins, à la discrétion de la mise en œuvre ; néanmoins, quand des mises à jour d'acheminement complètes requièrent de nombreux paquets, l'envoi de tous les chemins est fortement déconseillé. Quand une mise à jour déclenchée est traitée, les messages devraient être générés pour chaque réseau directement connecté. Le traitement de l'horizon partagé est effectué lors de la génération de mises à jour déclenchées aussi bien que lors des mises à jour normales (voir ci-dessous). Si, après le traitement de l'horizon partagé, un chemin modifié devait apparaître identique à son état antérieur, le chemin ne doit pas être envoyé ; si, en conséquence, aucun chemin ne doit être envoyé, la mise à jour peut être omise sur ce réseau. (Si un chemin n'a subi qu'un changement de métrique, ou utilise un nouveau routeur situé sur le même réseau que l'ancien routeur, le chemin sera envoyé sur le réseau de l'ancien routeur avec une métrique infinie à la fois avant et après le changement.) Une fois que toutes les mises à jour déclenchées ont été générées, les fanions de changement de route devraient être réinitialisés.

Si le traitement de l'entrée est autorisé alors que la sortie est en train d'être générée, un inter-verrouillage approprié doit être mis en œuvre. Les fanions de changement de route ne devraient pas être modifiés à la suite du traitement de l'entrée quand un message de mise à jour déclenchée est en cours de génération.

La seule différence entre une mise à jour déclenchée et les autres messages de mise à jour est la possible omission des chemins qui n'ont pas changé. Les mécanismes restants, qui sont sur le point d'être décrits, doivent tous s'appliquer aux mises à jour déclenchées.

Voici la façon dont un datagramme de réponse est généré pour un réseau directement connecté particulier :

L'adresse IP de source doit être celle de l'hôte émetteur sur ce réseau. C'est important parce que l'adresse de source est placée dans les tableaux d'acheminement d'autres hôtes. Si une adresse de source incorrecte est employée, d'autres hôtes peuvent être incapables d'acheminer les datagrammes. Parfois, les routeurs sont configurés avec plusieurs adresses IP sur une même interface physique. Normalement, cela signifie que plusieurs réseaux IP logiques sont transportés sur un même support physique. Dans de tels cas, un message de mise à jour séparé doit être envoyé à chaque adresse, avec cette adresse comme adresse IP de source.

Spécifiez le numéro de version de la version actuelle de RIP. (La version décrite dans le présent document est la 1.) Fixez la commande à 'réponse'. Fixez les octets marqués « doit être zéro » à zéro. Maintenant, commencez à remplir les entrées.

Pour remplir les entrées, parcourez de haut en bas tous les chemins du tableau d'acheminement interne. Rappelez-vous que la taille maximale d'un datagramme est de 512 octets. Quand il n'y a plus d'espace pour le datagramme, envoyez le message actuel et démarrez-en un nouveau. Si une mise à jour déclenchée est en cours de génération, seules les entrées dont les fanions de changement de route sont spécifiés doivent être incluses.

Voyez au paragraphe 3.2 la description des problèmes soulevés par les chemins vers des sous-réseaux ou d'hôtes. Les chemins vers des sous-réseaux n'auront aucune signification à l'extérieur du réseau, et doivent être omis si la destination n'est pas sur le même réseau composé de sous-réseaux ; ils devraient être remplacés par un unique chemin vers le réseau duquel font partie les sous-réseaux. De la même façon, les chemins d'hôtes doivent être éliminés si ils sont synthétisés par un chemin de réseau, comme décrit dans la discussion du paragraphe 3.2.

Si le chemin réussit ces essais, alors les destination et métrique sont placées à l'intérieur de l'entrée dans le datagramme de sortie. Les chemins doivent être inclus dans le datagramme même si leur métrique est infinie. Si le routeur du chemin est situé sur le réseau pour lequel le datagramme est préparé, la métrique de l'entrée est fixée à 16, ou bien l'entrée entière est omise. L'omission de l'entrée revient simplement à faire de l'horizon partagé. L'inclusion d'une entrée de métrique égale à 16 est de l'horizon partagé avec empoisonnement. Voyez au paragraphe 2.2 un exposé plus complet sur ces solutions de remplacement.

3.6 Compatibilité

Le protocole décrit dans le présent document est destiné à interopérer avec routed et d'autres mises en œuvre existantes de RIP. Néanmoins, un point de vue différent est adopté au sujet du moment de l'incrémentation de la métrique que celui choisi dans la plupart des mises en œuvre précédentes. En utilisant la perspective précédente, le tableau d'acheminement interne a une métrique de 0 pour tous les réseaux directement connectés. Le coût (qui est toujours de 1) est ajouté à la métrique quand la route est envoyée dans un message de mise à jour. À l'opposé, dans le présent document, les réseaux directement connectés apparaissent dans le tableau d'acheminement interne avec des métriques égales à leur coût ; les métriques ne valent pas nécessairement 1. Dans le présent document, le coût est ajouté aux métriques quand des chemins sont reçus dans des messages de mise à jour. Les métriques du tableau d'acheminement sont envoyées dans des messages de mise à jour sans modification (à moins que cela ne soit altéré par l'horizon partagé).

Ces deux points de vue résultent en une émission de messages de mise à jour identiques. Les métriques présentes dans le tableau d'acheminement diffèrent d'une constante « 1 » dans les deux descriptions. En fait, il n'y a donc aucune différence. Le changement a été effectué car les nouvelles descriptions facilitent le traitement des situations où différentes métriques sont utilisées sur des réseaux directement rattachés.

Les mises en œuvre qui ne prennent en charge que des coûts de réseaux de un ne doivent pas être modifiées pour se conformer au nouveau style de présentation. Néanmoins, elles doivent de toute manière suivre les autres prescriptions fournies dans ce document.

4. Fonctions de contrôle

La présente section décrit les contrôles administratifs. Ils ne font pas partie du protocole en tant que tels. Néanmoins, l'expérience engrangée avec les réseaux existants suggère qu'ils sont importants. Puisqu'ils ne font pas nécessairement partie du protocole, ils sont considérés comme facultatifs. Néanmoins, nous recommandons fortement qu'au moins quelques uns d'entre eux soient inclus dans chaque mise en œuvre.

Ces contrôles sont prévus principalement pour permettre à RIP d'être connecté à des réseaux dont l'acheminement peut être instable ou sujet aux erreurs. Voici quelques exemples :

Il est parfois désirable de limiter les hôtes et routeurs depuis lesquels on acceptera des informations. À l'occasion, des hôtes ont été mal configurés d'une façon telle qu'ils commencent par envoyer des informations inappropriées.

Un certain nombre de sites limitent le groupe de réseaux qu'ils permettent dans les messages de mise à jour. Une organisation A pourrait disposer d'une connexion vers une organisation B qu'elles utilisent pour une communication commune directe. Pour des raisons de sécurité ou de performance, A pourrait ne pas vouloir permettre l'utilisation de cette connexion par d'autres organisations. Dans de tels cas, A ne devrait pas inclure les réseaux de B dans les mises à jour que A envoie à des tiers.

Voici quelques contrôles typiques (noter cependant que le protocole RIP ne les exige pas plus que les autres contrôles) :

Bibliographie

[1] R.E Bellman, Dynamic Programming, Princeton University Press, Princeton, N.J., 1957.
[2] D.P. Bertsekas, R.G. Gallaher, Data Networks, Prentice-Hall, Englewood Cliffs, N.J., 1987.
[3] R. Braden, J. Postel, Requirements for Internet Gateways, USC/Information Sciences Institute, RFC-1009, juin 1987.
[4] D.R. Boggs, J.F. Shoch, A.E. Taft, R.M. Metcalfe, Pup : An Internetwork Architecture, IEEE Transactions on Communications, avril 1980.
[5] D.D Clark, Fault Isolation and Recovery, MIT-LCS, RFC-816, juillet 1982.
[6] L.R. Ford Jr., D.R. Fulkerson, Flows in Networks, Princeton University Press, Princeton, N.J., 1962.
[7] Xerox Corp., Internet Transport Protocols, Xerox System Integration Standard XSIS 028112, décembre 1981.