Le protocole de routage OSPF

OSPF


LE PROTOCOLE DE ROUTAGE

Le rôle du routeur est d’acheminer des paquets entre différents réseaux. Pour cela, il se base sur sa table de routage comportant les éléments nécessaires (@ réseau, masque, @IP du routeur cible, interface de sortie) au transfert du paquet. De plus le routeur doit posséder une table de routage contenant tous les numéros de réseaux pour lesquels il doit être capable de faire du routage (ou utilisation d’une route par défaut).
Pour éviter un paramétrage manuel fastidieux de ces tables de routage, surtout si le nombre de réseaux et de sous réseaux est important, on utilise le routage dynamique qui s’effectue par des protocoles appelés protocoles de routage.
Il existe deux principales familles : les protocoles internes (IGP : Interior Gateway Protocol) qui établissent les tables de routage des routeurs appartenant à une entité unique appelée AS (Autonomous System : système autonome) et les protocoles externes (EGP : Exterior Gateway Protocol) permettant l’échange des informations entre ces systèmes autonomes.
Au sein des protocoles internes, il existe deux types : les protocoles à vecteur de distance (Distant Vector Protocol) qui utilisent le saut de routeur comme métrique, et les protocoles à états de liens (Link State Protocol), beaucoup plus performants que les précédents, que nous allons voir en détail à travers le protocole OSPF


OSPF (Open Shortest Path First)

OSPF a été conçu à la fin des années 80 pour répondre aux principaux défauts des protocoles à vecteurs de distance (limitation du nombres de sauts à 15 max, temps de convergence trop important…). C’est un protocole ouvert (pas de copyright), la version 2 (la plus récente) a été définie et normalisée par l’IETF (Internet Engineering Task Force) en 1998 par la RFC(Request For Comment) n°2328, une version 3 (RFC 2740) a été conçu pour Ipv6.
OSPF est un protocole de routage interne à état de liens fonctionnant dans la pile TCP/IP, il se place directement sur IP (protocole n°89).
Son principe est simple, chaque routeur détermine l’état de ses connections (liens) avec les routeurs voisins, il diffuse ses informations à tous les routeurs appartenant à une même zone. Ces informations forment une base de données, qui doit être identique à tous les routeurs de la même zone. Sachant qu’un système autonome (AS) est constitué de plusieurs zones, l’ensemble de ces bases de données représente la topologie de l’AS. A partir de cette base de données, chaque routeur va calculer sa table de routage grâce à l’algorithme SPF (Short Path First).

CONCEPTS

Topologie logique et hiérarchisation (niveau AS)

AS ou système autonome : c’est un ensemble de réseaux régi par une autorité administrative, les tables de routage sont calculées et diffusées pour tous les routeurs de l’AS avec le même protocole de routage interne (IGP).

AREA ou zone : de façon a pouvoir mieux gérer un système autonome de grande importance et réduire les échange d’informations, on a divisé ce dernier en plusieurs zones appelées Area. Chaque area possède sa propre topologie et ne connaît pas les autres. Un lien ou un réseau appartient à une seule area, les frontières d’area se situent sur les routeurs et non sur les liens. Chaque area est identifiée par un numéro sur 32 bits (area ID) indépendant du plan d’adressage du réseau. Les areas sont structurées en étoile autour d’une area particulière appelée area 0 ou area backbone.

Type d’area :

-Aire 0 (area backbone) : elle est constituée de routeurs BR (Backbone Router) connectant deux ou plusieurs areas C’est le chemin obligatoire pour passer d’une zone à l’autre. Il se peut qu’un routeur backbone, connectant deux zones, n’est pas relié physiquement à l’area 0, on le relie alors par un lien virtuel.

-Aire secondaire (standard area) : elle est constituée de routeurs IR (Internal Router) ne connaissant que la topologie de la zone, ces derniers calculent localement les tables de routage.

-Aire terminale (stub area) : même comportement que les standard area sauf qu’il n’y a pas de mémorisation de route externe (hors du système autonome).

Il existe trois types de communication :
-intra-area : échange d’informations propre à cette zone.
-inter-area :échange d’informations minimales pour la connexion des zones.
-inter-AS :communication permettant la connexion entre les systèmes autonomes.

OSPF définit pour chaque routeur un rôle et un fonctionnement particulier :

Type de routeur :

-IR (Internal Router) :il fonctionne au sein d’une zone (autre que backbone), il crée et entretient une Link-State-Database (base de données d’état de lien) en fonction de tous les réseaux de sa zone et il renvoie ses informations à tous les autres routeurs de la zone.
Cette Link-State-Database est identique à tous les IR de cette zone.

-ABR (Area Border Router) : routeur de bordure connectant deux ou plusieurs zones. Il possède les Link State-Database des zones qu’il connecte. Il distribue ces informations à la zone de Bacbone. De plus il résume (summarization des routes) ces informations pour minimiser les mises à jour.

-BR (Backbone Router) : chaque zone doit être connectée à l’area 0 et ceci au travers de Backbone Router. Il fonctionne comme un ABR.

-ASBR (Autonomous System Boundary Router) : ce routeur de frontière fait office de passerelle entre les systèmes autonomes. Pour cela il se connecte à un ASBR homologue (d’un autre AS) pour apprendre les routes externes et diffuser les siennes.




Topologie physique et hiérarchisation (Niveau Area)

Pour que les routeurs s’échangent les informations de routage, ils doivent être adjacents, c’est à dire qu’ils doivent se découvrir les uns les autres. Cette adjacence va se construire grâce au protocole HELLO (permet la découverte des voisins et vérifie qu’ils sont toujours accessibles). De plus elle est dépendante du type de réseau physique, OSPF définit pour ses interfaces, trois types de réseau :

-Point à Point (PPP, HDLC) : segment permettant de connecter deux routeurs.

-BMA :Broadcast Multiple Access (ethernet) : segment permettant de connecter plusieurs routeurs.

-NBMA :Non Broadcast Multiple Access (X25, Frame Relay, ISDN) : segment permettant de connecter plusieurs routeurs.

Sur les types BMA et NBMA, beaucoup de routeurs peuvent être connectés et si chaque routeur doit établir une adjacence avec tous les autres, les échanges vont provoquer une surcharge dans la zone. On va donc désigner un routeur (DR :Designated Router) qui va devenir adjacent à tous les autres. Il va collecter les informations d’état de lien des autres routeurs et ensuite les rediffuser à tous. Ce DR devient un point névralgique du segment, pour sécuriser ce système on va désigner un routeur de secour : le BDR (Backup Designated Router).
Ce système se déroule sous forme d’élection et se base sur l’@IP de l’interface du routeur. Par contre l’élection du DR et du BDR ne s’applique que pour les réseaux BMA et NBMA.
OSPF utilise le multicast pour adresser ses paquets : concrétement, les paquets s’adressant à tous les routeurs de la zone utilisent l’@ multicast 224.0.0.5, tandis que les paquets adressés uniquement au DR et au BDR utilisent l’@ multicast 224.0.0.6.

FONCTIONNEMENT

Descriptif général :

La table de routage est obtenue au final grâce à l’application de l’algorithme SPF (Short Path First) sur une base d’information décrivant les liens qui unissent les routeurs d’une area. Un lien est une interface de routeur et son état est la description de cette interface (@IP, masque, routeurs connectés…). Cette base est nommée Link State Database ou Topology Table, elle est identique à tous les routeurs de la zone. Au démarrage, un routeur doit se faire connaître des autres, il utilise le protocole HELLO, puis il génére un LSA (Link State Advertisement) représentant tous les états de liens de voisinage du routeur. Cet échange d’état de lien entre les routeurs se fait par innondation (flooding). Des mises à jour d’état de lien (Lin State Update) permettent de mettre à niveau tous les routeurs. Lorsque les bases de données sont synchronisées (identiques entre tous les routeurs de l’area), chaque routeur va calculer “ l’arbre du chemin le plus court ” en appliquant l’algorithme SPF (algorithme de Dijkstra). Il construira ainsi sa table de routage (routing table ou forwarding table).

Déroulement du processus :

(Etat des interfaces) ETAPE 1 :Découverte des voisins (adjacence des routeurs)

(Down state) Pas d’échange d’informations, attente d’un paquet HELLO.

(Init state) Les routeurs envoient des paquets HELLO (toutes les 10s) pour établir une relation avec son voisin. Dès qu’il reçoit un HELLO il passe à l’état suivant.

(Two-way state) Deux possibilités : soit il n’y a que deux routeurs (liaison point à point), alors les routeurs deviennent adjacents (on passe à l’étape 3), soit il y a plusieurs routeurs, dans les cas de réseaux BMA et NBMA, on passe à l’étape 2.

ETAPE 2 : Election du DR et du BDR

-1 : OSPF sélectionne au hasard un routeur R1 qui examine tous les autres qui ont atteint l’état “ Two-way ”.
-2 : Il retire ceux qui ont une priorité 0 (champs “ Router priority ” du paquet HELLO, valeur à 1 par défaut et 255 max pour forcer une élection).
-3 : Il choisit celui dont la priorité est la plus elevée et le nomme BDR, s’il y a ex-aequo sur la priorité, il choisira celui dont l’ID (champs “ Router ID ” du paquet HELLO) est la plus elevée. Cette ID est l’@IP de l’interface physique ou (pour les routeurs Cisco notamment) l’@IP d’interface loopback.
-4 : Si aucun routeur ne s’est déclaré DR, OSPF transforme le BDR en DR et recommence les étapes 2 et 3 pour élire le BDR.
-5 : Le DR construit les adjacences avec les autres (de même que le BDR).

ETAPE 3 : Découverte des routes

(ExStart state) Etablissement d’une relation maître/esclave entre les routeurs, le routeur ayant l’ID (champs “ Router ID ”) la plus elevée devient le maître. Le DR est toujours le maître.

(Exchange state) Les routeurs décrivent leurs Link-Database aux autres. C’est le maître qui initie l’échange de paquets type 2 DBD (Database Description). Ces paquets contiennent une description de la LDB (Link-State Database) avec un numéro de séquence. Les routeurs confirment la réception par des paquets de type 5 (LSAck) comportant le numéro de séquence. Chacun compare ses informations avec les informations reçues, si ces dernières sont plus récentes le routeur passe en mode “ Loading ”.

(Loading state) Le routeur envoie des paquets de type 3 LSR (Link-state Request) pour mettre à jour sa base d’état de lien au routeur possédant des LSA plus récentes, ce dernier répond en envoyant un paquet de type 4 (LSU :link-state Update), ces LSU sont accusées par des LSAck. Ces paquets contiennent les Link-state Advertisements (LSA) qui sont les informations d’état de lien complètes.

(Full Adjacency) Lorsque le Loading state est complet, les Link-state database sont synchronisées, c’est à dire identiques à tous les routeurs de l’area, et chaque routeur établit une liste de ces routeurs voisins (adjcency database).

ETAPE 4 : Solution des routes (table de routage)

Lorsque le routeur a établit sa Link-state database, il peut créer sa table de routage. Il utilise pour cela l’algorithme SPF qui tient compte de la bande passante du lien (voir algorithme SPF).

ETAPE 5 : Maintien des tables de routage

Lorsqu’il y a un changement d’état de lien (par exemple si une interface ne reçoit plus de paquet HELLO d’une autre interface, elle considére le lien “ down ”), le routeur envoie une LSU avec les nouvelles informations à son DR et son BDR. Ceux-ci innondent alors de LSU les autres routeurs, de nouvelles tables de routage sont crées. Si aucun changement topologique n’intervient, les informations sont rafraichies, les LSA ont, par défaut, une durée de vie de 30 minutes.

EXEMPLE D’ECHANGE DE LSA



LES ALGORITHMES

L’algorithme SPF (Short Path First) ou algorithme de Dijkstra

L’algorithme de Dijkstra (mathématicien hollandais) est utilisé pour le calcul des tables de routage. Le but étant d’établir le chemin le plus court entre une source et sa destination, l’algorithme utilise deux structures : la structure PATH contenant le chemin pour aller d’un routeur à un autre au meilleur coût et la structure TENT qui contient les tentatives de chemin qui n’ont pas le meilleur coût. Pour résumer, SPF fait la somme des coûts à partir de lui même (router root) vers tous les réseaux de destinations, s’il y a plusieurs chemins possibles vers une destination, c’est celle qui a le coût le plus faible qui est choisie.
Le coût dépend de la bande passante, plus elle diminue plus le coût est elevé, selon la formule : cost = 108/Bandwith.

L’algorithme TDSP (Two Disjoint Shortest Paths) en projet

OSPF a considérablement diminué le temps de convergence par rapport au protocole à vecteur de distance RIP, mais suite à une panne simple, il dépasse la minute, ce qui est encore trop long pour des applications temps réel. Ce temps de convergence est dû à trois facteurs : au temps mis par un routeur pour décider qu’un routeur voisin est en panne, au temps pour resynchroniser les bases de données topologiques et le temps necessaire pour recalculer la table de routage. Ce nouvel algorithme permet de réduire ce temps de convergence. C’est en fait une version modifié de l’algorithme de Dijkstra basé sur le calcul de deux chemins (un chemin de secour disjoint du premier chemin) utilisés pour chaque destination possible du réseau et en un seul passage. Cela supprime les deux derniers facteurs de temps cités plus haut.



SECURITE
Par défaut les informations sont reçues par les routeurs sans authentification de l’expéditeur.
On peut activer un mécanisme d’authentification des messages OSPF. Il y a deux types d’authentification : d’une part par simple mot de passe et d’autre part par un processus de hachage (Message Digest authentication : MD5). Ces authentifications seront partagées au sein d’une même zone.
-Athentification par simple mot de passe : tous les routeurs se partagent un mot de passe qui passera en clair.
-Authentification MD5 : une clé (key : mot de passe) et un key-id sont configirés sur chaque routeur. Chaque routeur générera une emprunte de 64 bits du paquet OSPF à envoyer en fonction de sa clé et de sa key-id grâce à l’algorithme de hachage MD5. Le routeur destinataire effectuera la même opération, en comparant son résultat avec le “ message digest reçu, il pourra être sûr de l’expéditeur.




CONCLUSION

OSPF a été développé pour palier aux nombreux problèmes de RIP et répondre au besoin de routage sur des grands réseaux.
Ses principaux avantages sont :
-convergence rapide
-pas de limite de routeurs ‘RIP se limite à 15 sauts)
-supporte VLSM et CIDR pour réduire les routes
-métrique précise (en fonction de la bande passante)
-répartition de charge (load balancing) grâce à une gestion de plusieurs routes pour une même destination.
-sécurisation par authentification de routage
-utilisation du multicast et mise à jour incrémentielle et non entières.
Par contre OSPF nécessite pour ses calculs une consommation de ressources processeur et mémoire très importante sur les routeurs.




ANNEXES




En-tête OSPF


version 2
type 1 Hello 2 Database Description (sert pour les routeurs adjacents) 3 Link State Request (sert pour les routeurs adjacents) 4 Link State Update 5 Link State Ack (retourné vers l'expéditeur du Link State Update, après un temps t aléatoire)
packet length taille en octets de entête+données ospf
router ID id du routeur source (chaque routeur doit avoir un ID unique dans le système autonome)
area ID id de l'area concernée
checksum checksum de entête+données-authentification
auType type d'authentification : 0 : null 1 : simple 2 : cryptographique
authentification données d'authentification : type 0 : non significatif type 1 : mot de passe type 2 : données (numéro de clé utilisée, numéro de séquence, etc.). Dans ce cas hash(paquet_ospf+clé_secrete_connue_de_tous_les_routeurs) est ajouté en fin du paquet.




Message HELLO




network mask masque réseau associé à l'interface
hellointerval nombre de secondes entre les envois de Hello
options options supportées par ce routeur (non détaillé)
rtrpri priorité du routeur : si vaut 0 est inéligible en tant que designated ou backup designated router
routerdeadinterval nombre secondes nécessaires avant de déclarer ce routeur comme mort
designated router DR de ce réseau. 0.0.0.0 si il n'existe pas
backup designated BDR de ce réseau. 0.0.0.0 si il n'existe pas
neighbor ID des routeurs de qui on a reçu des paquets Hello