+-------------------------------+ |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