La notion de routage est inhérente au fonctionnement du datagramme
IP (examiné page ![[*]](crossref.png)
).
Le routage des datagrammes IP n'est rien d'autre que l'opération qui
consiste à trouver une route pour les conduire vers la destination,
c'est à dire l'adresse du champ destination de l'en-tête
(page ).
Un premier examen du routage nous a conduit à distinguer le routage
direct, sur un même lan et associé à l'usage des services du protocole
ARP (Voir page ) puis le routage indirect, appellé ainsi
parcequ'il fait appel aux services d'une ou plusieurs passerelles avant
d'atteindre la destination. Dans les deux cas la décision de routage
porte sur la partie réseau de l'adresse IP du destinataire, ou encore le
netid.
Le routage indirect se subdivise en deux catégories : le routage statique, qui implique l'usage d'une passerelle par défaut et enfin le routage dynamique, sujet qui concerne ce chapitre.
L'idée d'une route statique est séduisante par sa facilité de mise
en 
uvre pour l'organisation des `` petits réseaux ''. Elle se
résume le plus souvent à ajouter une simple ligne dans la configuration
de l'appareil à raccorder au réseau, et cette information vitale peut
même être récupérée automatiquement à l'aide de protocoles comme BOOTP ou DHCP !
Sur un routeur ciscoVIII1,la ligne de configuration :
ip route 0.0.0.0 0.0.0.0 138.195.52.129
Indique que tous les datagrammes non routables directement doivent
être envoyés à l'adresse 138.195.52.129. Une seule route par
défaut peut être définie pour une pile IP comme il a été expliqué lors
de l'analyse de l'algorithme de routage page
.
Cette disposition très simple est bien commode car elle évite de se poser des questions compliquées sur le choix de la route, en déléguant à d'autres ce travail délicat. En effet, il faudra bien à un certain moment du trajet suivi par les datagrammes, qu'un dispositif particulier, étymologiquement un routeur, prenne une décision face à des possibilités multiples.
Ce routeur plus intelligent sera probablement celui qui permet à vos datagrammes de rejoindre l'internet si vous appartenez à une entité qui a son autonomie (voir plus loin), ou le routeur du prestataires FAI pour un particulier, ou une plus petite entité, abonné à un service xDSL quelconque.
La présence de plusieurs routes possibles pour rejoindre une destination implique de facto l'usage d'un protocole de routage dynamique. Une route statique privilégie une seule route et ignore les autres. L'existence de plusieurs routes est une nécessité pour assurer la redondance du service, voire même l'équilibrage du trafic sur plusieurs liens.
1.1 IGP, EGP, Système autonome
Au commencement, l'Arpanet était un seul réseau géré de manière homogène, du moins par un ensemble de personnes dépendantes de la même entité administrative, ce qui permettait d'en orienter le développement de la même manière partout. Le protocole de routage dynamique était un ancêtre du protocole RIP étudié dans ce chapitre. Ce protocole, comme on va le voir, implique que les routeurs s'échangent continuement des informations sur les meilleures routes à employer. Sans entrave, chaque routeur finit par avoir une route pour atteindre tout le monde, partout !
L'extension de ce réseau à des entités très différentes entres elles, a conduit les architectes réseaux de l'époque à créer la notion de système autonomes (autonomous systems ou AS dans le texte), afin de permettre à chacun de développer son réseau interne sans risque d'en diffuser le contenu à l'extérieur (soucis de confidentialité et de sécurité).
Un système autonome se caractérise par un numéro, ou numéro d'AS,
sur 16 bits dont l'attribution dépend de l'IANA et de ses délégations,
par exemple autonomous-system 2192 que l'on pourrait retrouver
dans la configuration d'un external gateway de la
figure VIII.01.
Cette nouvelle architecture entraine des changements dans l'usage des protocoles de routage. Certains sont plus adaptés que d'autres à router des blocs d'adresses IP conformément à des politiques de routage (routing policy) internationales, ce sont les EGP comme external gateway protocol. Leur ancêtre se nomme d'ailleurs EGP, il est remplacé aujourd'hui par BGP (Border Gateway Protocol).
À l'intérieur du système autonome, les protocoles de routages sont des IGP comme Interior Gateway Protocol et ne sont plus du tout adaptés à la gestion de l'internet moderne. Par contre ils répondent plus ou moins bien au besoin des réseaux internes si compliqués et vastes soient-ils. Ces IGP échangent bien entendu des routes avec les EGP, le routage ne serait pas possible sans cela.
figure VIII.01 -- Un AS, le monde extérieur, le monde intérieur !
Ce chapitre de cours examine deux IGP très classiques, RIP et OSPF ! Si ces deux protocoles se rencontrent très fréquemment sur les réseaux, ils diffèrent beaucoup dans leurs propriétés comme nous allons le voir...
1.2 Vecteur de distances vs État de liens
RIP Routing Information Protocol et OSPF Open Shortest Path First sont construits sur des approches différentes.
Les algorithmes de routage à vecteur de distances (basés sur l'algorithme de Bellman-Ford) conduisent les routeurs à transmettre à leurs voisins réseaux immédiats une copie de leur table de routage. Ces tables se modifient au fur et à mesure de leur propagation, car chaque route est associée à une métrique qui croît par défaut d'une unité au passage de chaque routeur (le routeur voisin accessible sur le même LAN est associé à une métrique de 1, etc...). Le choix de la meilleure route est établi par chaque routeur en considérant la valeur minimale de cette métrique pour toutes les routes qui aboutissent à la même destination. Seule la meilleure route est propagée, les autres sont oubliées.
Pour ces considérations on dit que le calcul de la route est distribué et par conséquence chaque routeur n'a pas la connaissance de la topologie globale du réseau : il n'en connait qu'une version interprétée par ses voisins.
Les algorithmes à états de liens bâtissent les tables de routages différemment. Chaque routeur est responsable de la reconnaissance de tous ses voisins, plus ou moins lointains, à qui il envoie une liste complète des noms et des coûts (en terme de bande passante, par défaut) contenu dans une base de données à sa charge et qui représente l'intégralité de tous les routeurs du nuage avec lesquels il doit travailler.
Chaque routeur a donc une connaissance exhaustive de la topologie du `` nuage '' dans lequel il se situe et c'est à partir de cette représentation qu'il calcule ses routes à l'aide d'un algorithme connu de recherche du plus court chemin dans un graphe : celui de DijkstraVIII2
RIP est l'acronyme de Routing Information Protocol. C'est le protocole historique de routage d'ArpanetVIII3, défini dans la RFC 1058 (historique) de 1988. Il est amusant de constater que l'écriture de cette RFC vient de l'analyse fonctionelle du dæmon routed présent sur les machines BSD de l'époqueVIII4.
Le principe de fonctionnement de RIP est basé sur le calcul distribué du chemin le plus court dans un graphe, selon l'algorithme Bellman-FordVIII5 décrit à la fin des années 1950.
Le terme chemin le plus court désigne implicitement l'usage d'une métrique pour comparer les longueurs. Ici, la métrique est basiquement le nombre de sauts (hops) entre deux routeurs. Pour tout routeur, les réseaux directement rattachés sont accessibles avec un nombre de saut égal à 1 (par défaut). La métrique pour s'atteindre soit-même étant toujours 0 par hypothèse.
Les routes qui sont propagées d'un routeur à un autre voient leur métrique augmenter de 1 (ou plus) à chaque franchissement d'un routeur. En pratique on ne dépasse guère une profondeur de quelques unités, sinon le protocole devient inefficace comme on le verra au paragraphe suivant. Plus précisement, une route assortie de la métrique 16 est considérée comme infinie, donc désigne une destination (devenue) inaccessible.
Cette limitation du protocole laisse quand même aux architectes d'infrastructures réseaux la possibilité de concevoir des réseaux séparés les uns des autres par un maximum de 15 routeurs...Au delà de cette limite il faut forcément envisager l'usage d'un autre protocole !
figure VIII.02 -- La route vers H depuis R a une métrique de 2 et passe par R1
Sur la figure VIII.02 Le routeur R peut atteindre l'hôte H avec une route dont la métrique est 2 et qui passe par le routeur R1.
Il faut bien noter qu'avec RIP, chaque routeur n'est en relation qu'avec ses voisins directs, c'est à dire ceux avec lesquels il partage un LANVIII6. Typiquement un routeur qui fait du RIP a au moins deux interfaces (elles peuvent être virtuelles), donc voit deux LANs. Ici R1 a un rôle central et incontournable car ni R ni R2 ne s'échangent directement des routes.
Pour cette raison, les routes sont globalement issues d'un calcul distribué. Pour chaque routeur l'établissement de sa table de
routage s'effectue à partir des informations fournies par les routeurs
de son voisinage, c'est à dire ceux qu'il peut atteindre par un
routage directe (cf page ).
La connaissance des routes acquises par chaque routeur ne s'effectue qu'au travers du résultat des calculs de routes effectués par ses voisins, calculs qu'il confrontera à sa propre table de routage et à son propre calcul de route (le choix d'une route plus courte à l'aide de la métrique annoncée), puis diffusera à son tour. Par ce principe, dans la figure VIII.02, R1 a connaissance du réseau N indirectement grâce aux annonces de routes diffusées par R2.
Le terme vecteurs de distances est employé parceque la propagation des routes s'effectue sous la forme de vecteurs : `` Pour atteindre telle destination, il faut passer par ce routeur et la métrique associée vaut cette valeur ''. Donc une direction et une métrique, d'où l'analogie avec un vecteur.
Le moyen de propagation des tables de routes est un broadcast IP
(adresse 255.255.255.255 Limited broadcast pour RIPv1) ou
des annonces multicast (adresse 224.0.0.9 si on utilise
RIPv2VIII7).
Le coût de la liaison locale, c'est à dire celle du routeur vers
lui-même, est `` 0 '' alors que celle pour atteindre
n'importe quel autre point est `` infini '' (valeur 16 par défaut).
Le routeur envoie un paquet de questionnement (request packet)
à ses voisins pour constituer sa table de routage initiale.
La RFC 2453 précise que celle-ci contient 5 informations pour
chaque entrée :
Cet évênement a lieu périodiquement (30 secondes) où dès que
quelque chose change dans la table de routage (Triggered
updates page
), ou encore à
réception d'un paquet de demande de route, par exemple par un
hôte d'un réseau directement raccordé (voir
page ) ;
Le fonctionnement de RIP a un coté `` magique '' et pourtant l'algorithme converge vers un état stable, c'est démontré !
Examinons-en le fonctionnement élémentaire sur un réseau théorique de trois routeurs alignés lors d'un démarrage `` à froid '' :
figure VIII.03 -- Fonctionnement élémentaire
Chaque routeur découvre les réseaux qui lui sont directement
rattachés et se connait lui-même, c'est à dire qu'il connait sa
ou ses adresses IP. On peut le formaliser par un triplet
(Destination, gateway, métrique), pour R1 ça donne
(R1,local,0)VIII8 ;
Chacun annonce ses routes de manière asynchrone, met à jour
sa table de routage et annonce celle-ci, tout ça
de manière un peu asynchrone. On examine les tables de routages
une fois ces échanges stabilisés.
Pour R3 de manière symétrique : (R2,R2,1), (R1,R2,2).
Que se passe t-il maintenant si R3 devient inaccessible (coupure réseau, hôte arrêté...) ?
Basiquement R2 devrait supprimer la route vers R3. Il n'en fait rien pour l'instant puisque R1 annonce une route (R3,R2,2). R2 décide donc qu'il existe une route (R3,R1,3) et annonce sa nouvelle table.
R1 ayant reçu une route modifiée de R2 modifie sa propre route qui devient (R3,R2,4) et ainsi de suite dans une boucle infernale qui tend à compter jusqu'à l'infini. For heureusement le calcul s'arrêtera à 16 par défaut, R1 et R2 conclueront alors que R3 n'est pas (plus) accessible et finiront par retirer la route de leur table !
On peut aisement se rendre compte de la stupidité de cette démarche ainsi (et c'est surtout ce qu'on lui reproche) de la perte de temps engendrée. D'où les améliorations apportées :
2.1.1 Horizon partagé ou Split horizon
Le concept est simple, il suffit de constater (toujours dans la figure VIII.03) qu'il est stupide si R1 route via R2 des paquets pour R3, d'essayer pour R2 de router ces paquets vers R1.
Donc R1 ne doit pas annoncer à R2 des routes passant par R2. Les routes annoncées ne sont donc plus identiques sur chaque réseau mais tiennent compte des destinations qui sont atteintes via chacune de ces liaisons pour éviter ce type d'annonce.
figure VIII.04 : L'`` horizon partagé '' ne résout pas tout !
Il existe une variante plus efficace encore, qui consiste, pour R1, à annoncer à R2 la route (R3,R2,16), donc une route infinie. R2 ne pourra donc pas utiliser cette route pour atteindre R3 via R1. Il n'y a pas de boucle de comptage à l'infini et R2 concluera tout de suite à l'inaccessibilité de R3. Ces deux astuces réunies sont repérées dans la RFC sous le terme split horizon with poisoned reverse.
La figure VIII.03 représente donc un cas théorique facile. En pratique, un des intérêts du routage dynamique étant d'avoir plusieurs routes possibles pour atteindre une destination, on aura plutôt la situation de la figure VIII.04 ce qui amène au cas de figure suivant :
Supposons que l'hôte H devienne inaccessible, la technique ci-dessus empêchera R3 de tenter de router les datagrammes vers R1 et R2, mais, du fait du caractère asynchrone des mises à jours, R1 ayant reçu de R3 le fait que H est inaccessible peut conclure que R2 est le meilleur chemin avec un coût de 3 et cette fausse information peut se propager à R3 via R2 et le comptage à l'infini est reparti...
Pour y remédier le protocole comporte un dispositif de mises à jours déclenchées :
2.1.2 Mises à jour déclenchées ou Triggered updates
L'éventualité d'une situation de comptage à l'infini évoquée dans le contexte de la figure VIII.04 peut être endiguée par ce dispositif.
Seules des mises à jours très rapides peuvent conduirent R1 et R2 à converger vers la conclusion que la distance vers H est devenue infinie.
La règle initiale est que quand un routeur change la métrique d'une route, il doit envoyer un message de mise à jour aussi vite que possible à tous ses voisins immédiats. Ce message ne contient que ce qui a changé et non l'intégralité de la table.
Mises à jour rapides ne signifient pas pour autant `` tempêtes de paquets sur le réseau '', d'une part parceque le principe de l'horizon partagé est conservé, et que d'autre part, une temporisation aléatoire (de 1 à 5 secondes) limite la fréquence d'émission de chaque mise à jour. Durant ce laps de temps la réception d'une mise à jour peut être également prise en compte et donc entrainer un changement des routes établies.
La différence entre ce dipositif et les annonces régulières tient à sa fréquence d'émission et au contenu restreint aux seules routes dont la métrique a changé.
La RFC 2453 conclue toutefois `` However, counting to infinity is still possible ''. Qui n'est vraiment pas très satisfaisant...
2.2 Le protocole RIPv1 vs RIPv2
RIP est encapsulé dans paquet UDP avec 520 comme port de destination :
figure VIII.05 -- RIP est transporté par UDP/IP
Étant donné le mode de propagation des annonces de routes, le choix du protocole UDP est tout à fait approprié. Cependant, la RFC 2453 spécifie que le nombre maximum de routes est limité à 25, comme il faut 20 octets (figure VIII.06) pour décrire une route, la partie utile du datagramme fait au plus 4 + 25 x 20 = 504 octets et le datagramme complet 532 octets au maximum, le risque de fragmentation est nul sur des lans et via les liaisons point à point modernes (PPP par exemple).
Par contre, s'il faut propager plus de 25 routes, il faut envisager l'émission d'autant de datagramme que nécessaire !
À l'intérieur du message RIP de la figure VIII.03 les octets s'organisent de la manière suivante :
figure VIII.06 -- Format d'un message RIPv2
Le format d'un message RIP laisse plein d'espace vide (surtout quand il s'agit de RIPv1 -- les champs marqués d'une * sur la figure). L'alignement des champs sur des mots de 32 bits en est à l'origine.
Ce champ peut également contenir la valeur
hexadécimale
Rien n'est défini dans la RFC 2453 pour
être plus confidentiel...
C'est un `` traceur '' pour identifier une route
qui provient d'un autre IGP voire d'un autre
EGP et qui est propagée par RIP.
En fonctionnement normal l'adresse
Ce cas de figure arrive à la frontière entre deux
réseaux, quand par exemple un routeur interne annonce une
meilleure route via un routeur du même lan.
)
donc AF_INET pour IPv4.
0xffff pour indiquer qu'il
s'agit un bloc d'authentification.
Dans ce cas l'identifiant de route contient
la valeur 2 et les 16 octets qui suivent un mot
de passe en clair, aligné à gauche et complété
par des zéros !
0.0.0.0 signifie
que la route passe par celui qui l'annonce. Ici il s'agit
d'une autre adresse IPv4, différente de celle de
l'annonceur. Celui-ci n'utilise pas RIP (sinon il
ferait l'annonce lui-même), mais sans doute un
autre protocole de routage.
En résumé, les apports de RIPv2 sont les suivants :
244.0.0.9
pour propager des routes (plutôt qu'un
limited broadcast IP, plus perturbateur
parceque lu par tous les hôtes.
Pour le fonctionnement de l'algorithme nous invitons le lecteur à consulter l'excellente simulation mise à disposition par l'Université Pierre Mendès France de Grenoble, à cette url (cliquer sur le bouton `` Appliquette '') :
http://brassens.upmf-grenoble.fr/IMSS/mamass/graphecomp/bellmannFord.htm
Dans les réseaux simples, le plus courant est d'utiliser le nombre de sauts, hop, c'est à dire le nombre de routeurs à franchir pour arriver à destination. Les réseaux plus complexe, on privilégira une métrique basée sur le délais, par exemple.
L'apparition des protocoles à états de liens n'a pas empêché son développement, la RFC 2453 de 1998, décrit RIPv2 encore en usage dans bon nombre de (petits) réseaux.
uvre ;
2.4.2 Points faibles
uds
sont séparés par des liaisons utilisant des bandes passantes
disparates ;
L'origine du protocole OSPF, et de la technologie de routage par `` états des liaisons '', datent du tout début des années 1980, pour faire face aux insuffisances du protocole à vecteurs de distances, constatées sur les réseaux Arpanet et Cyclades. Son développement est dû aux efforts du groupe OSPF de l'IETF.
3.1 Grandes lignes de fonctionnement
Les explications qui suivent font l'hypothèse d'un réseau IP qui supporte la propagation de trames avec une adresse de destination de type multicastVIII9, autrement dit ne traite pas le cas des réseaux sans diffusion ce type ou encore NBMA (Non Broadcast Multi-Access networks).
Basiquement un protocole à états de liens a un fonctionnement simple :
uds du réseau ;
En résumé un tel protocole a deux grandes activités, la première est de propager ses états et d'écouter ceux de ces voisins au sein de l'AS, c'est ce qu'on appelle le flooding, en français procédé par inondation, la deuxième est de calculer des routes à partir de tous les états de liens reçus. Ce calcul est effectué à l'aide de l'algorithme de Dijkstra de recherche du plus court chemin dans un graphe.
Pour les réseaux complexes, OSPF permet le groupement de routeurs en zones distinctes, areas, qui établissent des nuages autonomes qui routent les datagrammes entres eux, mais ne laissent pas filtrer leur trafic interne de LSP. Se dégage ainsi une hiérarchie de routeurs, ceux qui sont au milieu de la zone, ceux qui en sont à la frontière et assurent les échanges avec les autres zones, enfin ceux qui assurent les échangent avec les EGP (comme BGP) pour le trafic externe à l'AS.
Tous les échanges sont authentifiés. Par ce biais, seulement les routeurs prévus dans la configuration participent au routage. La technique d'authentification peut différer d'une zone à une autre (cf paragraphe 3.7.2)
Enfin, les échanges de données sont structurées autour d'un
protocole nommé HELLO. Ce protocole applicatif est véhiculé par deux
adresses multicast (page ) qui lui sont
attribuées : principalement 224.0.0.5 et 224.0.0.6 dans
certains cas, voir le paragraphe 3.6). Le protocole est
encapsulé directement dans les datagrammes IP, et le champ PROTO
contient la valeur 89 (fichier /etc/protocols).
Le choix de l'un ou de l'autre est assujeti à l'examen de ce qui les différencie, que l'on résume dans les X points suivants :
) ;
En synthèse OSPF est plus performants sur les points suivants :
3.3 Principe de propagation des états
L'établissement des tables de routages dépend de la complétude d'une table appelée link-state database, base de données d'états de liens, présente à l'identique sur chaque routeur de la zone. Cette table est alimentée par les états de liens, Link State Packet (LSP), que s'envoient les routeurs entres eux. Or cette distribution dépend du routage...
Contrairement à ce que l'on pourrait en déduire, il n'y a pas de
problème de précédence entre ces deux opérations, car la stratégie de
distribution repose sur l'usage d'une adresse de multicast, valable
uniquement dans un LAN (page ) donc qui ne
dépend pas de l'état de la table de routage !
Chaque changement d'état sur un lien doit être signalé au plus vite à tous les voisins excepté celui qui a signalé le changement. C'est un procédé par inondation, ou flooding dans la littérature.
Intuitivement ce modèle de propagation semble rapide mais génère potentiellement un nombre exponentiel de copies de chaque paquet...
Pour éviter une tempête prévisible de LSP, l'idée initiale des concepteurs consiste à ajouter à chaque LSP un numéro de séquence :
Ce dispositif tend à modérer la tempête de mises à jour mais induit d'autres interrogations :
Il annonce des LSP avec un numéro de séquence plus petit que
ceux déjà en circulation et qui donc seront ignorés, même si
plus pertinents.
Cette constatation est voisine de la situation de deux parties
d'un même réseau, séparées à la suite d'une rupture de
connectivitée et qui se retrouvent mais après que l'un des
compteurs soit repassé par 0 ?
Qui amènent les réponses suivantes :
Ensuite, pour établir une relation d'ordre entre les LSP,
la règle suivante est adoptée :
On peut déclarer que le LSP b est plus récent que a si
les conditions :
sont réunies. C'est ce que schématise graphiquement la figure VIII.07 ci-dessus ;
C'est une valeur numérique (codée sur 16 bits selon la
RFC 2328) positionnée non nulle par le routeur qui émet le
LSP.
, chapitre
concernant SNMP).
figure VIII.07 -- Relation d'ordre entre deux LSP
En résumé :
figure VIII.08 -- Propagation des LSP par inondation ou `` flooding ''
La figure VIII.08 montre un exemple simple de
propagation d'un changement d'état initié par le nud C. En trois
étapes tous les routeurs sont mis au courant. À l'étape 2 on peut
remarquer que les routeurs B,F et G s'interdisent de renvoyer le LSP à
C, son émetteur. On remarque également que F et G s'envoient le
même paquet, mais celui issu de F a un âge plus ancien, il sera
donc oublié immédiatement, comme celui issu de G, pour la même raison.
Le Nud E reçoit le même LSP depuis B et F, le premier arrivé
sera pris en compte, le deuxième oublié. Même remarque pour D à la fin
de la troisième étape.
La durée totale de ces trois étapes est pratiquement celle nécessaire pour propager les datagrammes (donc fortement dépendante de la bande passante), de quelques milli-secondes à quelques centaines de milli-secondes, donc !
3.3.1 Valeur des états de liens
Le coût des liens, nommé également la métrique, agit directement sur le choix d'une route plutôt qu'une autre comme on le voit dans le paragraphe qui suit.
Le constructeur Cisco préconiseVIII10 une formule qui est reprise partout :
bps signifie bits per second. Ce qui signifie qu'une liaison Ethernet à 10Mbits (dix milions de bits par seconde, un milion d'octets par secondes) a un coût de 108 / 107 = 10.
Le petit tableau ci-dessous indique quelques valeurs pour des débit connus :
Média
Coût
Liaison série 56kbps
1785
T1 (série 1544 kbps)
64
E1 (série 2048 kbps)
48
Token ring 4Mbps
25
Ethernet 10Mbps
10
Token ring 16Mbps
6
Ethernet 100Mbps
1
...
...
Bien entendu on peut toujours imposer manuellement sa propre valeur de coût d'une liaison, pour influencer le routage !
3.4 Calcul du plus court chemin
Pour le fonctionnement de l'algorithme de Dijkstra nous invitons le lecteur à consulter l'excellente simulation mise à disposition par l'Université Pierre Mendès France de Grenoble, à cette url (cliquer sur le bouton `` Appliquette '') :
http://brassens.upmf-grenoble.fr/IMSS/mamass/graphecomp/dijkstra.htm
Les réseaux à administrer peuvent être vastes et complexes, dans ces conditions il est souvent pertinent de les regrouper en sous-ensembles. La conception d'OSPF permet de le faire, il s'agit d'un concept nommé zone ou (area) et qui se traduit par une hiérarchisation du routage.
Outre la structuration plus claire du réseau global en sous réseaux, l'avantage de cette approche est également de diminuer le nombre de routes sur lequel porte le calcul de plus court chemin, et aussi de diminuer le trafic des mises à jour, non négligeable sur un réseau vaste et complexe.
La RFC précise qu'une zone doit faire le lien avec toutes les autres, il s'agit forcément de la zone 0, qui joue donc le rôle de l'arête centrale (OSPF Backbone).
De cette structuration découle le fait que tous les routeurs n'ont pas le même rôle, certain sont au milieu d'une zone et d'autres à la frontière entre deux zones, voire même à la frontière entre le nuage OSPF et d'autres mécanismes de routage, vers d'autres AS :
figure VIII.09 -- Organisation en zones - Hiérarchie de routeurs
La RFC précise quatre types de routeurs dans ce cas de figure :
3.6 Fonctionnement à l'intérieur d'une zone
Le fonctionnement du mécanisme d'inondation à l'intérieur d'une zone, tel que nous l'avons succintement décrit au paragraphe 3.3, induit que lors de la diffusion d'un LSP chaque routeur propage le changement d'état reçu à son voisinage réseau. Ce comportement induit un trafic en N2, si N est le nombre de routeurs sur le LAN en question.
OSPF essaie de réduire ce nombre à seulement N en faisant jouer un rôle particulier à l'un des routeurs, le routeur désigné, ou Designated Router (DR). Celui-ci reçoit les mises à jours car il écoute sur une autre adresse multicast, 224.0.0.6 (tous les routeurs OSPF désignés) et si besoin est propage à nouveau cette information vers les autres routeurs du LAN, avec ce coup-ci l'adresse 224.0.0.5 (tous les routeurs OSPF).
Se pose immédiatement la question de la panne éventuelle du routeur DR, celle-ci bloquerait la mise à jour des bases d'états de liens. À cet effet un routeur désigné de sauvegarde est également élu, c'est le Backup Designated Router, mis à jour en même temps que le DR mais qui reste muet sur le réseau tant que le protocole HELLO n'a pas détecté un dysfonctionnement du DR.
figure VIII.10 -- Propagation d'un LSP, sans et avec un DR
Sur la figure VIII.10, schéma de gauche, le routeur
R propage un nouvel LSP à tous ses voisins, puis chacun propage ce qu'il
a reçu vers les voisins pour lesquels il n'a rien reçu. Le nombre de
paquets est alors en théorie celui du nombre de paires
possiblesVIII11, soit
encore :
, 10 pour cet exemple.
Pour le schéma de droite, le routeur DR a reçu un LSP et le diffuse aux trois routeurs concernés. Notons que le BDR ne fait rien, il a également reçu la mise à jour mais s'abstient de toute action tant que le DR est opérationnel.
Avant de pouvoir établir une hiérarchie entres eux et d'échanger efficacement des états de liens, les routeurs doivent déterminer qui sont leurs voisins, autrement dit la topologie du réseau qui les entoure.
La RFC 2328 définit une progression selon 8 états (7 pour les réseaux avec propagation par multicast) pour chaque routeur OSPF, avant de pouvoir échanger efficacement avec ses voisins. Il est utile d'en avoir connaissance pour diagnostiquer une situation.
L'établissement (ou non) de ces états repose sur la structuration du protocole HELLO, qui se décline en cinq types de paquets différents, nous les examinons au paragraphe 3.7
Dans la liste des voisins transmise dans le paquet
le routeur n'apparaît pas, la communication reste
uni-directionnelle ;
Pour pouvoir échanger des états de liens et
construire des routes, chaque routeur doit former
une contiguïté (adjacency) avec chacun
de ses voisins. C'est une
relation avancée entre routeurs OSPF. Elle
s'établit en commençant par l'état suivant ;
Les LSU sont acquittés par des Link-state
acknowledgment (LSAck) ;
)
sont échangées, et le routeur ayant la plus
forte valeur de RID (Router ID)
gagne. Cette dernière valeur est fonction
de l'adresse IP la plus élevée pour tous les
interfaces du routeur, et d'un coefficient
configuré manuellement (non démocratique) ;
ur du fonctionnement du protocole.
Le protocole HELLO est en charge de l'établissement et du maintien des relations de voisinage entre routeurs. Il s'assure également que les communications entre chaque voisin sont bi-directionnelles. Comme nous l'avons précisé en introduction ce paquet est encapsulé dans un datagramme IP, donc en lieu et place d'un protocole de transport (qu'il ne remplace pas).
Des paquets de type HELLO sont envoyés à fréquence périodique sur tous les interfaces des routeurs. Les communications sont repérées comme étant bi-directionnelles si un routeur se reconnait dans la liste (des voisins connus) émise dans le paquet HELLO d'un voisin. Le protocole sert également à l'élection du Routeur Désigné (DR).
Sur les réseaux permettant le multicast, chaque routeur s'annonce lui-même en envoyant périodiquement des paquets HELLO. Ce dispositif permet aux routeurs voisins de se connaître dynamiquement, de vérifier continuellement l'accessibilité des voisins déjà connus.
Le protocole HELLO se compose principalement d'un en-tête de 6 mots de 4 octets (24 octets) et d'un complément qui dépend du type de paquet. Ce type est défini dès le premier mot de l'en-tête.
L'adresse IP de destination peut prendre une
valeur multicast ou unicast.
figure VIII.11 -- Organisation globale de l'en-tête du protocole OSPF
3.7.2 En-tête standard des paquets OSPF
Tous les paquets OSPF démarrent par un en-tête standard de 24 octets :
figure VIII.12 -- En-tête standard de 24 octets
0.0.0.0.
AuType
Description
0
Pas d'authentification
1
Mot de passe en clair sur le réseau
2
Crypto à partir d'un secret partagé
3.7.3 En-tête des paquets HELLO
Un paquet de type 1 (Hello) est envoyé périodiquement sur tous les interfaces des routeurs qui participent au nuage OSPF. L'objectif est de maintenir les relations de voisinages et d'adjacences comme vu précédement. C'est une sorte de Keep-alive pour les besoins du protocole.
Les octets de la figure VIII.13 sont à placer en continuité de ceux de la figure VIII.12, pour former un en-tête de 24 + 24 = 48 octets minimum. La taille s'accroît ensuite de quatre octets par RID supplémentaire de voisin.
figure VIII.13 -- En-tête du paquet HELLO
0.0.0.0 s'il n'y en a pas.
La description des 4 autres types de paquets se trouve à l'annexe A.3 de la RFC.
Pour en savoir plus :
Sites web :
http://www.cisco.com/warp/customer/104/1.html
http://brassens.upmf-grenoble.fr/IMSS/mamass/graphecomp/bellmannFord.htm
Ouvrages de références :
Next: IX Éléments de réseaux
Up: B Réseaux IP avancés
Previous: B Réseaux IP avancés
Contents
Index
François Laissus
2009-02-27