RIP
Origine
RIP (Routing Information Protocol) est un protocole de routage historique de la catégorie des IGP (Interior Gateway Protocol) publié dans la RFC 2453 :
RIP is a routing protocol based on the Bellman-Ford (or distance
vector) algorithm. This algorithm has been used for routing
computations in computer networks since the early days of the
ARPANET.
L'introduction se poursuit avec la notion d'AS (Autonomous System) particulièrement bien résumée :
In an international network, such as the Internet, it is very
unlikely that a single routing protocol will used for the entire
network. Rather, the network will be organized as a collection of
Autonomous Systems (AS), each of which will, in general, be
administered by a single entity. Each AS will have its own routing
technology, which may differ among AS's. The routing protocol used
within an AS is referred to as an Interior Gateway Protocol (IGP). A
separate protocol, called an Exterior Gateway Protocol (EGP), is used
to transfer routing information among the AS's. RIP was designed to
work as an IGP in moderate-size AS's. It is not intended for use in
more complex environments.
L'intérêt
S'il est vrai que RIP a été largement remplacé par des protocoles de routage plus élaborés comme OSPF (Open Shortest Path First) et IS-IS (Intermediate System to Intermediate System), l'étudier n'en demeure pas moins intéressant pour comprendre sa simplicité et ses limites. Par ailleurs, RIP a introduit certains mécanismes repris dans des technologies plus récentes—comme le split horizon dans VPLS (L2VPN sur MPLS).
Enfin, il arrive que RIP soit encore utilisé, par exemple dans les L3VPN sur MPLS afin d'échanger simplement et efficacement les routes entre le CE et le PE. Ceci respecte tout à fait les recommendations de la RFC, s'agissant là d'un échange de routes trivial et limité à un seul lien (un seul hop). Il peut aussi être utilisé face à du matériel vieillissant ne supportant pas d'autre protocole de routage. Si ledit matériel répond au besoin depuis des années, la question de l'intérêt de le changer se pose. Cela demanderait de l'investissement en temps et en argent sachant qu'il n'est pas certain que le nouveau matériel réponde aussi bien au besoin. Et c'est sans compter la pollution engendrée par l'ancien matériel, que deviendrait-il ?
Quelques ressources :
Protocole à vecteur de distance
Pour comprendre le fonctionnement, rien ne vaut un exemple :
10.0.0.0/30 et 10.0.0.4/30 avec une distance de 1.
À son tour, R2 annonce ses routes directement connectées à R3 avec, en plus,
celle apprise depuis R1 en incrémentant la distance associée qui passe à 2.
Et ainsi de suite.
Naturellement, lorsqu'un routeur reçoit une route qu'il connaît déjà,
celle avec la plus petite distance est retenue.
La distance peut être la somme de n'importe quelle métrique :
Distance is a somewhat generalized concept, which may cover
the time delay in getting messages to the entity, the dollar cost of
sending messages to it, etc.
Dans RIP, la métrique est le nombre de saut. Dans EIGRP (RFC 7868), la métrique est plus complexe et est dite composite car elle prend en compte plusieurs métriques via une formule.
Distance vector algorithms get their
name from the fact that it is possible to compute optimal routes when
the only information exchanged is the list of these distances.
Enfin, comme l'explique l'extrait ci-dessus, on parle de vecteur
car chaque routeur envoie à ses voisins une liste (des destinations avec les distances respectives).
Or, une liste est aussi couramment appelée vecteur—en
Java par exemple, les types ArrayList et Vector sont proches.
Noter que, chaque routeur se basant sur les annonces (les « rumeurs ») reçues de ses voisins,
les protocoles à vecteur de distance sont aussi appelés routing by rumor.
Ci-dessous une capture et les configurations sur Cisco correspondant à l'exemple :
10.0.0.8/30 et 10.0.0.12/30
avec une distance de 1 et les autres routes apprises depuis R2 dont les distances associées ont été incrémentées.
| R1 | R2 | R3 |
|---|---|---|
|
|
|
Split horizon
En regardant l'exemple de plus près, on voit vite que certaines annonces de route sont inutiles.
Il ne sert à rien que R1 annonce à R2 la route 10.0.0.4/30 car c'est une route directement connectée entre eux.
De même, il n'est pas nécessaire que R2 ré-annonce à R1 la route 10.0.0.0/30 car R1 en est l'originaire.
In particular, it is
never useful to claim reachability for a destination network to the
neighbor(s) from which the route was learned.
Pour éviter ces annonces superflues (et qui gaspillent de la bande passante), il existe le split horizon—désactivé dans l'exemple précédent pour aborder le protocole simplement et bêtement.
Counting to infinity
Si le split horizon est plus intelligent dans l'annonce des routes, il permet surtout d'éviter les boucles de routage entre deux routeurs voisins. En son absence, le scénario suivant peut en effet arriver :
10.0.0.0/30 de R1, après avoir été annoncée à R2, est down.
Plus tard, R2 annonce cette route à R1 qui l'accepte (ne la connaissant plus).
R1 la ré-annonce à R2 en incrémentant la distance et R2 accepte la distance de 3
car R1 est, pour lui, l'originaire de cette route.
R2 la ré-annonce à R1 et ainsi de suite jusqu'à l'infini.
Tant que ces annonces ont lieu, une boucle de routage est bien créée :
si R2 reçoit un paquet à destination de 10.0.0.0/30, il va le router vers R1 qui va le lui retourner
et ainsi de suite jusqu'à expiration du TTL.
Le split horizon aurait évité ceci car R2, à l'étape 3,
n'aurait pas ré-annoncé la route 10.0.0.0/30 à R1, ce dernier en étant l'originaire.
La route aurait fini par expirer sur R2 au bout d'un certain temps (180 secondes dans RIP).
10.0.0.0/30 n'a pas expiré sur R2 et les autres routeurs,
elle est encore utilisée par ces derniers.
Si des paquets sont routés vers R1, des messages Unreachable seront retournés.
Le réseau est ainsi dit instable (il n'a pas « convergé »).
Split horizon with poisoned reverse
En réalité, deux types de split horizon existent :
The "simple split
horizon" scheme omits routes learned from one neighbor in updates
sent to that neighbor. "Split horizon with poisoned reverse"
includes such routes in updates, but sets their metrics to infinity.
Le premier type est celui étudié précédemment : les routes apprises depuis son voisin ne lui sont pas ré-annoncées. Dans le deuxième type, ces routes sont ré-annoncées mais avec une distance infinie (16 dans RIP), le but étant d'éviter les boucles de routage entre deux routeurs voisins plus rapidement.
Si la route directement connectée 10.0.0.0/30 de R1 devient down
et qu'il l'a reçoit plus tard de R2 avec une distance ∞,
il va l'accepter et la considérer comme non utilisable.
Après un certain temps, il va la ré-annoncer à R2
(qui en est devenu l'originaire de son point de vue) avec la même distance ∞.
R2 saura alors à son tour que la route est down (car R1 en est toujours l'originaire de son point de vue)
et la boucle de routage sera dès lors évitée.
Noter qu'avant que R1 ré-annonce la route avec la distance ∞,
R2 continue à router à tord des paquets vers R1
(comme dans le simple split horizon).
Triggered updates (ou Route poisoning)
Les deux types de split horizon ont donc un premier manquement : le réseau est instable pendant un temps. De plus, une boucle de routage entre trois routeurs peut survenir :
Split horizon with poisoned reverse will prevent any routing loops
that involve only two routers. However, it is still possible to end
up with patterns in which three routers are engaged in mutual
deception. For example, A may believe it has a route through B, B
through C, and C through A. Split horizon cannot stop such a loop.
This loop will only be resolved when the metric reaches infinity and
the network involved is then declared unreachable. Triggered updates
are an attempt to speed up this convergence.
Comme toute RFC qui se respecte, un exemple pratique pour illustrer les propos n'est pas fourni—c'est au lecteur de se creuser les méninges. Après un temps de réflexion, nous pouvons trouver un exemple possible. D'ailleurs, bien que seul le split horizon with poisoned reverse soit mentionné, cela concerne aussi le simple split horizon. Ci-dessous des schémas représentant les deux cas sur une topologie semblable à celle brièvement mentionnée.
Une boucle de routage est bien engendrée entre les trois routeurs.
Le problème de counting to infinity est également présent pour la route 10.0.0.12/30 :
- B la ré-annoncera avec une distance de
5à A qui l'acceptera (B en étant l'originaire de son point de vue). - A la ré-annoncera avec une distance de
6à C qui l'acceptera (A en étant l'originaire de son point de vue). - C la ré-annoncera avec une distance de
7à B qui l'acceptera (C en étant l'originaire de son point de vue).
Et ainsi de suite. Ces annonces et la boucle de routage auront lieu jusqu'à que la distance atteigne l'infini (16 dans RIP). La solution apportée est celle des triggered updates, aussi connue sous le nom route poisoning.
Triggered updates
are an attempt to speed up this convergence. To get triggered
updates, we simply add a rule that whenever a router changes the
metric for a route, it is required to send update messages almost
immediately, even if it is not yet time for one of the regular update
message. (...) If an update arrives from G itself, the
receiving router is required to believe the new information, whether
the new metric is higher or lower than the old one. If the result is
a change in metric, then the receiving router will send triggered
updates to all the hosts and routers directly connected to it. They
in turn may each send updates to their neighbors. The result is a
cascade of triggered updates.
Le principe est simple : dès qu'une route change de distance sur un routeur,
ce dernier en informe immédiatement ses voisins, lesquels en informent aussitôt les leurs.
Voici une capture illustrant un triggered update suite à une route devenue down :
10.0.0.0/30 vient d'être down.
Dans la capture de droite, R2 fait suivre l'information à ses voisins.
Tous les routeurs sont ainsi informés et, contrairement au split horizon,
la route 10.0.0.0/30 n'est pas utilisée inutilement jusqu'à expiration.
Ainsi, tous les routeurs sur le réseau sont au courant plus rapidement. Comme expliqué dans la RFC, les triggered updates sont bien un attempt pour accélérer la convergence. Les boucles de routage sont moins probables mais toujours possible. En effet, les triggered updates peuvent se perdre en chemin ou un routeur peut recevoir, après un triggered update, une annonce d'un routeur qui n'était pas encore au courant.