Open shortest path first

Open shortest path first

Open shortest path first

Pile de protocoles
7 • Application
6 • Présentation
5 • Session
4 • Transport
3 • Réseau
2 • Liaison
1 • Physique
Modèle Internet
Modèle OSI

OSPF (Open Shortest Path First) est un protocole de routage IP interne de type protocole à état de liens (link-state protocol).

Sommaire

Fonctionnement général

Dans OSPF, chaque routeur établit des relations d'adjacence avec ses voisins immédiats en envoyant des messages hello à intervalle régulier. Chaque routeur communique ensuite la liste des réseaux auxquels il est directement connecté par des messages LSA (Link-State Advertisements) propagés de proche en proche à tous les routeurs du réseau. L'ensemble des LSA forme la base de données des liens Link-State Database (LSDB), qui est identique pour tous les routeurs participants. Chaque routeur utilise ensuite l'algorithme de Dijkstra, Shortest Path First pour déterminer la route la plus courte vers chacun des réseaux connus dans la LSDB.

Le bon fonctionnement d'OSPF requiert donc une complète cohérence dans le calcul SPF, il n'est donc par exemple pas possible de filtrer des routes ou de les résumer à l'intérieur d'une aire.

En cas de changement de topologie, de nouveaux LSA sont propagés de proche en proche, et l'algorithme SPF est exécuté à nouveau sur chaque routeur.

Métrique

OSPF utilise une métrique numérique simple, basée sur un coût additif. La valeur par défaut du coût d'un lien est de 108/bande passante du lien en bit/s. Un lien de 10 Mbit/s aura par exemple un coût de 10. Pour tenir compte des connexions à très haute vitesse (1 Gbit/s et plus), on peut fixer manuellement le coût de chaque lien, ou bien fixer une bande passante de référence supérieure à celle par défaut.

Répartition de la charge

OSPF est capable de répartir la charge sur plusieurs liens, pour autant que la métrique soit exactement identique pour chaque destination.

Notion d'aire

Afin d'éviter de propager la totalité de la base de données des liens et de limiter l'impact négatif du flapping (alternance rapide dans la disponibilité d'un lien physique), on segmente l'ensemble des routeurs en groupes connexes appelés aires, à la frontière desquels on peut procéder à des résumés. Les routeurs à la frontière des aires sont appelés Area Border Router (ABR).

Il existe toujours une aire dorsale (backbone area' ou area 0) à laquelle toutes les aires doivent être directement connectées.

Un routeur qui injecte dans OSPF des routes depuis un autre protocole de routage ou des routes statiques est appelé Autonomous System Border Router (ASBR), ces routes seront marquées comme externes dans OSPF.

Adjacence sur un réseau à diffusion

Une relation d'adjacence est nécessaire pour que les routeurs OSPF se partagent des informations de routage. Dans un réseau Ethernet si chaque routeur devait établir une contiguïté avec chaque autre routeur et échanger des informations d’état de liens la charge serait excessive, le nombre d'adjacences étant de \frac{n(n-1)}{2}, soit en O(n2). Pour pallier ce problème, on choisit un DR (routeur désigné) qui va recevoir toutes les informations sur l'état des liens et les retransmettre aux autres routeurs. Celui-ci devenant un point critique du réseau, on désigne aussi un BDR (routeur désigné de secours). Le nombre d'adjacence est donc en O(n).

OSPF utilise uniquement du multicast pour discuter avec les deux adresses suivantes :

  • 224.0.0.5 utilisé par le routeur désigné (DR) pour envoyer les informations d’état de liens à tous les autres routeurs sur le segment.
  • 224.0.0.6 utilisé par tous les routeurs pour envoyer les informations d'état de liens vers les routeurs désignés (DR et BDR).

L’algorithme de Dijkstra

OSPF utilise cet algorithme pour déterminer le meilleur chemin à prendre. On le nomme aussi algorithme SPF (Shortest Path First) ou algorithme du plus court chemin d’abord. Il a été formulé par Edsger Dijkstra.

Basé sur l'algorithme de Dijkstra, OSPF déclenche ses mises à jour à chaque changement dans la topologie du réseau, ce qui permet de réduire le temps de convergence. À partir d'une mise à jour, un routeur met en place une base de données topologique permettant le calcul de l'accessibilité aux réseaux grâce au calcul d'un arbre de la topologie à l'aide de l'algorithme.

Avantages et inconvénients

Avantages d'OSPF

  • C'est un standard IETF qui fait l'objet du RFC2328[1], il fait donc l'objet d'implémentations par de nombreux vendeurs et ne pose pas de problème d'interopérabilité, il est de ce fait particulièrement populaire,
  • son temps de convergence est particulièrement rapide, de l'ordre de quelques secondes,
  • il intègre la notion de taille de masque variable (VLSM), indispensable à la gestion des réseaux sans classe actuels,
  • il est économe en bande passante : en régime, seuls de courts messages hello sont envoyés, et en cas de changement de topologie, seuls les LSA modifiés sont envoyés aux voisins. Chaque routeur retransmet l'ensemble de ses LSA à ses voisins toutes les trente minutes.

Inconvénients d'OSPF

  • comme chaque routeur dispose de la totalité de la base de données de liens, tous doivent disposer de la capacité mémoire suffisante pour la stocker,
  • la capacité CPU joue un rôle dans le calcul SPF et donc la vitesse de convergence, en particulier pour les topologies complexes et instables,
  • OSPF est sensible au phénomène de flapping,
  • la configuration d'OSPF est plus complexe, principalement si le réseau est segmenté en aires,
  • le concept de backbone area peut limiter les topologies possibles,
  • il ne permet pas la répartition de la charge sur plusieurs liens de métrique différente, comme EIGRP peut le faire,
  • OSPFv2 est spécifique à IP. Pour d'autres protocoles, comme par exemple IPv6, une nouvelle version du protocole est nécessaire : OSPFv3[2].

Références

  1. (en) RFC 2328 - OSPF Version 2
  2. (en) RFC 5340 - OSPF for IPv6

Bibliographie

  • (en) John T. Moy OSPF: Anatomy of an Internet Routing Protocol Addison-Wesley Professional 1998, (ISBN 0201634724)
  • (en) Brent Stewart, CCNP Building Cisco Scalable Internetworks Official Study Guide, 4th ed, Cisco Press 2007, (ISBN 158720147X)

Voir aussi

Liens internes

  • Autres protocoles de routage interne :
    • EIGRP (Enhanced Interior Gateway Routing Protocol)
    • RIP (Routing Information Protocol)
    • IS-IS (Intermediate system to intermediate system)

Lien externe


  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Open shortest path first ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Open shortest path first de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Open Shortest Path First — (OSPF) ist ein Verfahren aus der EDV Netztechnik. Es bezeichnet ein von der IETF entwickeltes Link State Routing Protokoll. Es ist im RFC 2328 (obsolet: RFC 1247 von 1991) festgelegt und basiert auf dem von Edsger W. Dijkstra entwickelten… …   Deutsch Wikipedia

  • Open Shortest Path First — (OSPF) is an adaptive routing protocol for Internet Protocol (IP) networks. It uses a link state routing algorithm and falls into the group of interior routing protocols, operating within a single autonomous system (AS). It is defined as OSPF… …   Wikipedia

  • Open Shortest Path First — (frecuentemente abreviado OSPF) es un protocolo de enrutamiento jerárquico de pasarela interior o IGP (Interior Gateway Protocol), que usa el algoritmo Dijkstra enlace estado (LSA Link State Algorithm) para calcular la ruta más corta posible. Usa …   Wikipedia Español

  • Open Shortest Path First — (frecuentemente abreviado OSPF) es un protocolo de encaminamiento jerárquico de pasarela interior o IGP (Interior Gateway Protocol), que usa el algoritmo Dijkstra enlace estado (LSA Link State Algorithm) para calcular la ruta más corta posible.… …   Enciclopedia Universal

  • Open Shortest Path First — Open Shortest Path First,   OSPF …   Universal-Lexikon

  • Open Shortest Path First — Pile de protocoles 7.  Application 6.  Présentation 5.  Session 4.  Tr …   Wikipédia en Français

  • Multicast Open Shortest Path First — MOSPF (Multicast open shortest path first) ist die Multicast Erweiterung zu OSPF (open shortest path first). MOSPF ermöglicht das Multicast Routing innerhalb einer OSPF Domain. Hierbei ist aber besonderes Augenmerk auf die Tatsache zu legen, dass …   Deutsch Wikipedia

  • Multicast Open Shortest Path First — The Multicast Open Shortest Path First (MOSPF) protocol is an extension to the Open Shortest Path First (OSPF) protocol to support multicast routing, allowing routers to share information about group memberships. The routing and remote access… …   Wikipedia

  • Open Shortest Path First —    Abbreviated OSPF. A routing protocol used on TCP/IP networks that takes into account network loading and bandwidth when routing information over the network. Routers maintain a map of the network and swap information on the current status of… …   Dictionary of networking

  • open shortest path first —    (OSPF)    Permits routers to exchange network configuration data in TCP/IP networks …   IT glossary of terms, acronyms and abbreviations

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”