<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.
- économie de message
- le *routeur désigné* (DR pour Designated Router) est élu via une priorité ou son *router id*
- 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*)
- démarage à -N/2, puis -N/3, … → 0 (non utilisé)
- 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>