Un brin de réseau


Tel un cahier de notes, ce blog propose des articles sur les technologies réseaux et leur utilisation pratique, le tout illustré avec des maquettes et des captures.

#about #contact

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 ?

Protocole à vecteur de distance

Pour comprendre le fonctionnement, rien ne vaut un exemple :

dv
Dans un tel protocole, chaque routeur annonce initialement à ses voisins ses routes directement connectées. Aussi, R1 annonce à R2 ses routes 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 :

cap-rip
La capture correspondant à l'annonce des routes de R3 à ses voisins (R4 uniquement ici). On retrouve les routes directement connectées 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.
Remarquer la database construite sur chaque routeur.
R1 R2 R3

  R1#show running-config
  !
  interface FastEthernet0/0
   ip address 10.0.0.2 255.255.255.252
   no ip split-horizon # voir plus bas
  !
  interface FastEthernet0/1
   ip address 10.0.0.5 255.255.255.252
   no ip split-horizon # voir plus bas
  !
  router rip
   version 2 # support du classless (CIDR)
   network 10.0.0.0 # classful (source)
  !

  R1#show ip rip database
  10.0.0.0/8    auto-summary
  10.0.0.0/30    directly connected, Fa0/0
  10.0.0.4/30    directly connected, Fa0/1
  10.0.0.8/30
      [1] via 10.0.0.6, 00:00:13, Fa0/1
  10.0.0.12/30
      [2] via 10.0.0.6, 00:00:13, Fa0/1
              

  R2#show running-config
  !
  interface FastEthernet0/0
   ip address 10.0.0.6 255.255.255.252
   no ip split-horizon # voir plus bas
  !
  interface FastEthernet0/1
   ip address 10.0.0.9 255.255.255.252
   no ip split-horizon # voir plus bas
  !
  router rip
   version 2 # support du classless (CIDR)
   network 10.0.0.0 # classful (source)
  !

  R2#show ip rip database
  10.0.0.0/8    auto-summary
  10.0.0.0/30
      [1] via 10.0.0.5, 00:00:24, Fa0/0
  10.0.0.4/30    directly connected, Fa0/0
  10.0.0.8/30    directly connected, Fa0/1
  10.0.0.12/30
      [1] via 10.0.0.10, 00:00:18, Fa0/1
              

  R3#show running-config
  !
  interface FastEthernet0/0
   ip address 10.0.0.10 255.255.255.252
   no ip split-horizon # voir plus bas
  !
  interface FastEthernet0/1
   ip address 10.0.0.13 255.255.255.252
   no ip split-horizon # voir plus bas
  !
  router rip
   version 2 # support du classless (CIDR)
   network 10.0.0.0 # classful (source)
  !

  R3#show ip rip database
  10.0.0.0/8    auto-summary
  10.0.0.0/30
      [2] via 10.0.0.9, 00:00:05, Fa0/0
  10.0.0.4/30
      [1] via 10.0.0.9, 00:00:05, Fa0/0
  10.0.0.8/30    directly connected, Fa0/0
  10.0.0.12/30    directly connected, Fa0/1
              

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.

dv-split-horizon
Avec le split horizon, l'exemple précédent devient ceci. Une route directement connectée entre deux routeurs n'est plus annoncée entre eux. Une route apprise depuis son voisin ne lui est plus ré-annoncée. Plus techniquement dit, un routeur ne ré-annonce pas une route sur l'interface par laquelle il l'a reçue (information disponible dans sa database).

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 :

dv-mutual-deception-2
La route directement connectée 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).

dv-unreachable
Noter qu'avec le split horizon, la boucle de routage est, certes, évitée mais tant que la route 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.

dv-split-horizon-with-poisoned-reverse
Comme dans le simple split horizon, une route directement connectée entre deux routeurs n'est plus annoncée entre eux. Une route apprise depuis son voisin lui est, ici, ré-annoncée mais avec une distance infinie.

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 :

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 :

dv-triggered-updates
Dans la capture de gauche, R1 annonce que sa route directement connectée 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.