m1if15:routage:routeedl

<rst> +——————————-+

Etats des liens : OSPF et IS-IS

+——————————-+

Présentation


- les algorithmes à vecteur de distance ne connaissent que leurs voisins et les destinations atteignables par ces derniers.

- les algorithmes à états des liens sont caractérisés par :

 + une base de données de toutes les liaisons du ou des réseaux considérés (base de données topologique);
 + un algorithme de diffusion de ces informations (innondation) des mises à jour;
 + un calcul local des routes vers tous les autres noeuds du ou des réseaux, cela demande plus de calculs mais cela accélère la convergeance du réseau.

- OSPF et IS-IS sont les 2 représentants les plus connus :

 + OSPF est déjà largement répandu
 + IS-IS est a priori préféré dans les data-center (pour le passage à l'échelle)

OSPF focalisera plus notre attention car il est plus utilisé dans les réseaux d'entreprises).

Principes


- Chaque routeur maintien une base de données de toutes les liaisons du réseau. - Le calcul locale utilise l'algorithme `Shortest Path First de W.E.Dijkstra`_ (1959) - pour plus de détails voir “Introduction to Algorithms by Cormen, Leiserson and Rivest (MIT Press/McGraw-Hill 1994, ISBN 0-262-03141-8 (MIT Press) and ISBN 0-07-013143-0 (McGraw-Hill).” - problèmes :

 + le cout nécessaire au calcul, en fonction de la taille : la complexité d'OSPF en version optimale est O(m+n*lg(n))
 + maintien de la cohérence des données réppliquées
 + temps et cout des mise à jour

.. _`Shortest Path First de W.E.Dijkstra`: http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

Base des voisins


- chaque routeur maintien une base des *routeurs voisins* (directement connectés), c'est la neighbors database - multi-diffusion régulière via une adresse de multidiffusion (224.0.0.5 pour les routeurs OSPF) de paquets Hello (timer hello interval, par défaut 15 s ce qui est adapté aux liaisons rapides) - après 3 messages sans réponse, le voisin est considéré comme *absent* (timer dead interval, en principe 3 * hello interval) - Pour être voisin,

  • les voisins doivent pouvoir communiquer
  • les interfaces doivent être déclarées dans le processus ospf (Il y a 2 facon différente selon l'utilisation de ipv4 ou ipv6)
  • tous les paramètres doivent correspondre (ainsi que l'authentification)

Innondation et numérotation des versions


- base des voisins (Hello) : identifiant le router id - router id : 4 octets *= une adresse ipv4*

 + affectation d'un identifiant (commande);
 + par défaut, l'adresse IP la plus petite des interfaces actives (utiliser le llopback de préférence);
 + il est possible de choisir l'identifiant (ce qui est nécessaire en ipv6);

- acquittement requis

L'innondation peut poser des problèmes lorsque plusieurs routeurs sont connecté à un même voisinage. Par exemple plusieurs routeurs sur un même switch. En effet, le principe de l'innondation est que lorsque un routeur recoit une mise à jour d'un autre, il la transmet à tous les voisins sauf celui qui l'a envoyé.

 + un message recu via une liaison bipoint n'est pas retransmis sur cette liaison;
 + mais un message recu via un réseau à diffusion/NBMA (non broadcast multiple access) doit être envoyé au autres. Ce qui serait trop couteux car génère O(n^2) messages (pour n routeurs connectés) et crée des boucles.

Le solution est de désigner un routeur chargé des transmissions le DR, les routeurs qui ne sont pas DR transmettent les mises à jour au seul DR qui transmet aux autres.

  1. économie de message
  2. le *routeur désigné* (DR pour Designated Router) est élu via une priorité ou son *router id*
  3. un *routeur de secours* (BDR pour Backup Designated Router) est aussi choisi pour relayer le précédent en cas de panne (reprise quasi immédiate).

- numérotation des mise à jour (*versioning*)

  1. démarage à -N/2, puis -N/3, … → 0 (non utilisé)
  2. ensuite de 1 à N/2 (pas 1 modulo N/2 en excluant la valeur 0)

- permet les reprises en cas de perte de connectivité

Link State Advertisement (LSA)


- Identifié par l'ID du routeur émetteur

http://www.cisco.com/web/learning/le31/le46/cln/qlm/CCNP/bsci/Introducing-OSPF-AUG07/player.html

http://docstore.mik.ua/cisco/pdf/routing/OSPF%20Routing%20Protocol%281%29.pdf

commandes http://perso.univ-lyon1.fr/fabien.rico/site/_media/m1if15:lexique-de-commandes-cisco.pdf

http://www.cisco.com/c/en/us/td/docs/ios/12_2/iproute/command/reference/fiprrp_r/1rfospf.pdf

</rst>

  • m1if15/routage/routeedl.txt
  • Dernière modification : 2019/05/10 09:44
  • de fabien.rico