Un des protocoles les plus utilisés par les gestionnaires de réseau: Le protocole OSPF pour Open Shortest Path First.

• Basé sur l'algorithme de routage à état de lien (Dijkstra) conçu en 1987.
• Standardisé par IETF via les RFC 2328 et 2740

Pour permettre a chaque routeur de découvrir son voisinage et de le diffuser aux autres routeurs OSPF s'appuie sur une base de donnée locale sur chaque routeur désignée LSDB pour Link State DataBase. Elle contient donc la cartographie du réseau, c' est à dire l'ensemble des routeurs composant le réseau et des liens entre ces routeurs.

La LSDB se construit à la réception de paquets de contrôle et elle est utilisée une fois constituée pour calculer localement les routes par le biais de l'algorithme de Dijkstra.

Pour identifier les voisins directs, OSPF s'appuie sur l'envoi régulier de paquets Hello.

Qu'entend on par routeur voisin?

Chaque routeur a plusieurs interfaces, chaque interface a sa propre adresse logique de réseau (adresse IP). Un routeur peut donc être vu comme un élément matérialisant la frontière de ses sous-réseaux, il fait parti de chacun de ces sous-réseaux. Deux routeurs sont dits voisins s'ils ont tous les deux une interface faisant parti du même sous réseau.

Le routeur envoi donc dans chaque sous-réseau auquel il est connecté, un paquet qui annonce sa présence à tous les autres routeurs du même sous-réseau. Ce paquet Hello n’intéresse pas les terminaux, qui ne participent pas au processus de routage. Le paquet Hello est envoyé à destination d'une adresse IP multicast (224.0.0.5) permettant d'atteindre l'ensemble des routeurs OSPF et eux seulement.

En configuration standard, un paquet Hello est envoyé toutes les 10 secondes ou 30 secondes selon le type de réseau.

Outre la découverte, le retour des paquets confirme que les voisins sont toujours fonctionnels, c'est donc également un moyen de détecter les pannes.

En l'absence de réception de 4 paquets Hello consécutifs, e voisin est considéré en panne et supprimé de la liste de voisins.

Le paquet Hello contient:

• Identité du routeur émetteur
• Informations de configuration du protocole
• Liste des voisins
• Type de réseau permettant l'association d'une métrique/score (plus le réseau est rapide, plus la métrique est faible).

Le routeur dispose donc d'une liste de voisins, et des caractéristiques des liens qui le relie à ses voisins. C' est cette information qu'il va transmettre à tous les autres routeurs faisant parti du réseau afin de leur permettre de mettre à jour leur table.

Pour cela le protocole OSPF définit 4 types de messages:

• DBD pour DataBase Description: diffusion périodique du nom de tous les routeurs (Le nom d'un routeur correspond à l'adresse IP d'une interface, la plus grande par exemple)
• LSR pour Link State Request: Lorsque un routeur par l’intermédiaire de la lecture des paquets DBD identifie un routeur qu'il ne connaît pas encore, il demande à l'emetteur du paquet DBD un complément d'information via le paquet LSR.
• LSU pour Link State Update: réponse contenant les informations détaillées concernant un routeur.
• LSAck pour Link State Acquittement, acquitte de la bonne réception des informations. Fiabilise la cartographie du réseau.

Sur certains types de réseaux, la surcharge du protocole peut devenir importante: plus le nombre de routeurs augmente plus le nombre de paquets Hello et d'annonce DBD augmentent.

Pour limiter cette charge, les routeurs peuvent être paramétrés pour élire un routeur particulier dit routeur désigné qui se chargera de recevoir l'ensemble des informations transmises par les routeurs et de les rediffuser ensuite.

Cette élection est réalisée au moyen des paquets Hello en définissant d'abord un critère.

Pour rester efficace même sur de plus grands réseaux, OSPF permet de diviser un grand réseau en aires. L'administrateur réseau doit définir les aires (quel routeur appartient à quelle aire).

• Un sous réseau appartient à une seule aire
• Une aire contient un ou plusieurs sous réseaux

Une fois les aires définies, OSPF s'exécutera indépendamment dans chaque aire comme s'il s'agissait de réseaux distincts. Seuls les routeurs à la frontière de chaque aire se synchroniseront pour calculer les routes dans le réseau global. Pour cela les routeurs aux frontières des différentes aires définissent une nouvelle aire particulière appelée Backbone (épine dorsale).

La division en aires permet de limiter le nombre de récepteurs concernés par chaque émission, ainsi que la taille de la base de données des liens. Elle réduit donc la charge du protocole aux grandes échelles.

Pour conclure

• OSPF mise en œuvre de l'algorithme de routage à état de lien
• OSPF calcule les chemins les plus efficaces au sens d'une métrique modélisant la capacité des liens entre chaque couple de routeurs.
• OSPF est concu pour fonctionner sur de petit et de grands réseaux en limitant le volume du trafic de controle.
• OSPF est distribué, dynamique et capable de s'adapter assez rapidement aux évolution de la topologie.

• OSPF appartient à la famille des algorithmes de routage à état de lien. OSPF est une mise en œuvre directe de l'algorithme de routage à état de liens auquel on a ajouté plusieurs optimisations pour le rendre plus efficace dans les réseaux les plus fréquents.
• Un routeur est connecté, via l'une de ses interfaces, à un sous-réseau dans lequel 8 autres routeurs sont présents. Afin de se faire connaître de tous ses voisins, il enverra un seul paquet Hello. Les paquets Hello sont envoyés à une adresse multicast dans un sous-réseau. Un seul paquet suffira donc pour atteindre tous les routeurs appartenant au même sous-réseau.
• En supposant qu'un paquet Hello est envoyé toutes les 10 secondes, il faut 40 secondes à un routeur pour détecter qu'un de ses voisins est en panne via ce mécanisme. Un routeur supprimera un de ses voisins de sa table de voisinage s'il ne reçoit pas quatre paquets Hello consécutifs, soit au bout de 40 secondes à partir du dernier paquet reçu.
• L'élection d'un routeur désignée est utile seulement dans les réseaux comportant un grand nombre de routeurs. Le routeur désigné sert uniquement à éviter que chaque couple de routeur n'ait à dialoguer pour acquérir la topologie du réseau. Il est le seul destinataire des paquets de découverte des liens du réseau, ce qui permet d'économiser de nombreux envois. C'est donc dans les réseaux comportant beaucoup de routeurs qu'il est le plus efficace car le nombre de messages économisés est directement fonction du nombre de routeurs.
• Diviser un réseau en aires permet de réduire le volume de trafic de contrôle et le temps de calcul des tables de routage. Le fonctionnement d'OSPF étant restreint à chaque aire, les paquets diffusés (DBD, etc.) ne se propageront pas au-delà de la frontière d'une aire. Par conséquent, le volume de paquets de contrôle émis et retransmis sera moindre en divisant le réseau de cette manière. La convergence de l'algorithme de Dijkstra étant directement liée au nombre de routeurs présents, le temps de calcul des routes sera amélioré avec cette division, même s'il faut aussi prendre en compte les nœuds faisant partie du backbone qui se verront affecter des tâches supplémentaires.