Protocole OSPF + Protocole de Diusion
Exercice : protocole de routage OSPF
Dans cet exercice, nous nous intressons au calcul de la table de routage. Supposons que le
nud F du rseau a la vision suivante du rseau :
liaison
distance
liaison
distance
liaison
distance
C vers F
1
E vers B
1
A vers B
1
C vers D
2
E vers F
2
A vers D
3
D vers A
3
F vers C
1
B vers D
3
D vers B
3
F vers D
4
B vers E
1
D vers F
4
F vers E
2
1. Dessinez le rseau partir des informations ci-dessus.
1
Correction :
3
D
2
3
A
B
4
F
1
2
A
D
2
1
C
2. Ecrivez la table de routage du noeud F.
Correction :
route : = un plus court chemin dans le rseau
construction d'un arbre de plus court chemin en utilisant l'algorithme de Dijkstra.
Description des variables.
cap(k) correspond si l' algo a dj dcid si l' arte est dj dans l' arbre.
d(i) distance entre le noeud racine s de l'arbre.
Description de l' algorithme.
Procedure initialisation :
v, v sommets de G, distance(v ) := inf inity
v, v sommets de G, pere(v ) := nil
d(s) = 0
Procedure centrale
Pour i = 1, . . . , n 1 faire
Pour chaque arc (u,v) de G faire
si d(v) > d(u) + cap(u, v) alors
d(v) d(u) + cap(u, v)
pere(v) = v
destination
A
B
C
D
E
F
liaison
F vers E
F vers E
F vers C
F vers C
F vers E
locale
Exercice : protocole OSPF et ses direntes mtriques.
Le protocole de routage OSPF calcule les routes de plus cout chemins en fonction d'une
fonction de cot (ou de distance) sur les artes. Cette fonction peut tre par exemple, le cot des
liens, la abilit des liens, le temps de transmission des liens. Dans cet exercice, nous considrons
que la fonction de cot d'un lien correspond la charge de tra c qui le traverse.
Considrons la topologie (orient) suivante :
D
A
C
B
Au top 0, aucun tra c existe dans le rseau. Au top 1, la situation suivante est considre :
1. la quantit de tra c allant de A vers D et celle allant de C vers D correspond 1 unit.
2. la quantit de tra c allant de B vers D et celle allant de C vers D correspond e unit
avec e < 1
1. Dterminer les routes pour aller vers D de chaque noeud du rseau au top 0. (si deux routes
ont de mme cot, alors la route utilisant le nombre de liens le plus petit sera favorise).
Correction :
vue locale du rseau
la route pour aller de A vers D est AD
la route pour aller de C vers D est CD
la route pour aller de B vers D est BCD
C
B
2. Au top 1, le tra c circule dans le rseau. Les cots des artes changent. Chaque noeud du
rseau s'appercoit de ces modi cations et adapte sa table de routage en fonction.
(a) Quelles sont les nouveaux cots des artes ?
Correction :
D
1
le
le
le
le
cot
cot
cot
cot
de l'arc A D est 1
de l'arc B C est e
de l'arc C D est 1 + e
des autres arcs est 0
1+e
C
0
0
e
B
(b) Dterminer les routes pour aller vers D de chaque noeud du rseau.
Correction :
vue locale du rseau
1
la route pour aller de A vers D est AD
la route pour aller de C vers D est CBAD
la route pour aller de B vers D est BAD
1+e
C
0
0
e
B
3. Au top 2, chaque noeud s'appercoit que les cots des artes changent. Ils recalculent ainsi
leur table de routage.
(a) Quelles sont les nouveaux cots des artes ?
Correction :
2+e
le
le
le
le
cot
cot
cot
cot
de l'arc A D est 2 + e
de l'arc B A est 1 + e
de l'arc B C est 1
des autres arcs est 0
D
0
C
0
1+e
0
B
(b) Dterminer les routes pour aller vers D de chaque noeud du rseau.
Correction :
2+e
la route pour aller de A vers D est ABCD
la route pour aller de C vers D est CD
la route pour aller de B vers D est BCD
D
0
C
0
1+e
0
B
4. et ainsi de suite. Qu'en dduisez-vous ?
Correction :
con guration 1 :
Les cots :
description
2+e
C
1+e
1
0
Alors les nouvelles routes sont les suivantes :
la route pour aller de A vers D est AD
la route pour aller de C vers D est CBAD
la route pour aller de B vers D est BAD
con guration 2
Les cots :
2+e
: description
D
0
C
0
1+e
0
B
Alors les nouvelles routes sont les suivantes :
la route pour aller de A vers D est ABCD
la route pour aller de C vers D est CD
la route pour aller de B vers D est BCD
Le systme oscille entre la con guration 1 et la con guration 2. Les routes sont instables ! ! ! ce qui
n'est pas bien pour des protocoles de routage car plus les routes sont instables, plus les paquets
ont des chances de se perdre ou de circuler longtemps dans le rseau. Prendre la charge de tra c
sur un lien comme mtrique est une mauvaise ide.
Diusions dans les systmes distribus
La diusion est l'opration qui consiste pour un site donn envoyer un mme message tous
les autres sites d'un systme. Nous considrons un systme constitu de n sites P0 , P1 , . . . , Pn1
tous interconnects.
Exercice : Diusion asynchrone en cas de panne sur les liens.
1. Dcrire un algorithme de diusion partir de P0 vers les autres sites (en supposant aucune
panne). Calculer le nombre de communications ncessaires pour raliser cette diusion.
Correction :
La procedure suivante est decrite pour le noeud p0 initiateur.
Procedure diffuser(M)
Envoyer(<M>) a $P_1,\dots,P_{n-1}$ dans cet ordre
Correction :
n 1 communications.
Nous voulons construire un algorithme de diusion qui fonctionne mme en cas de pannes
de certains sites. Nous appelons panne d'un site l'arrt soudain d'un site. On suppose qu'un site
une fois en panne reste en panne et ne fait plus rien.
2 Proposer un algorithme de diusion partir de P0 vers les autres sites qui tolre une
panne d'un des sites (on suppose que si P0 est en le site en panne, il a au moins le temps
d'envoyer un message). Calculer le nombre de communications ncessaires pour raliser
cette diusion.
Soit S0 = {p0 , p1 }
La procedure suivante est decrite pour le noeud p0 initiateur.
Correction :
Procedure diffuser(M)
Envoyer(<M>) a $P_1,\dots,P_{n-1}$ dans cet ordre;
Pour tout (q tel que q dans V - S0) faire
Envoyer(<M>) a q
Accepter(M) ;
La procedure suivante est decrite pour tout noeud qk 6= p0 .
Procedure diffuser(M)
Si (q_k \in S_0) alors
Si (k < 1) alors
Envoyer(<M>) a $P_{k+1},\dots,P_{t}$ dans cet ordre;
Pour tout (q tel que q dans V - S0)
Envoyer(<M>) a q
accepter(M) ;
Correction :
faire
n 1 + n 2 = 2n 3 communications
3 Gnraliser cet algorithme qui tolre jusqu' t sites en panne.
Correction :
Soit S0 = {p0 , p1 , . . . , pt }
La procedure suivante est decrite pour le noeud p0 initiateur.
Procedure diffuser(M)
Envoyer(<M>) a $P_1,\dots,P_{n-1}$ dans cet ordre;
Pour tout (q tel que q dans V - S0) faire
Envoyer(<M>) a q
Accepter(M) ;
La procedure suivante est decrite pour tout noeud qk 6= p0 .
Procedure diffuser(M)
Si (q_k \in S_0) alors
Si (k < t) alors
Envoyer(<M>) a $P_{k+1},\dots,P_{t}$ dans cet ordre;
Pour tout (q tel que q dans V - S0) faire
Envoyer(<M>) a q
accepter(M) ;
Principe du tout ou rien.
Si p tombe en panne. Si p a le temps d'envoyer un message, tous les autres sites le recevront sinon
personnes ne le recoit.
si c'est un site q tombe en panne tous les sites vont recevoir le message.
Correction :
Le site envoie n 1 messages.
Chaque P
site qi envoie t i + n (t + 1) = n i 1 messages.
t
n 1 + t=1 (n i 1) = (t + 1)(n 1 t/2) messages
Exercice : Diusion ne respectant pas l'ordre FIFO des messages
On suppose maintenant que les sites sont tous ables, mais que le rseau de communications
peut ne pas respecter l'ordre FIFO. On suppose maintenant que P0 diuse plusieurs messages
vers les autres sites. Proposer une mthode pour garantir que ces sites traitent les messages en
respectant l'ordre d'envoi par P0 .
Correction :
Description des variables
num_envoi(p) le numro d'envoi
seq(i) signifie que le noeud i a reu le message de numro 1, . . . , seq(i) 1.
Code du site p
Procdure Init
nume nvoi(p) := 0;
Procdure diffuser (M)
num_envoi(p) := num_envoi(p) + 1 ;
Pour tout noeud q dans V diffrent de p faire
Envoyer(<M, num_envoi(p) >) q ;
u 6= p
Procdure Init
seq(u) := 1 ;
Code du site
Lors de la rception de <M, num_envoi(p) > de p
Stocker (M) ;
Attendre (num_envoi(p)= seq(u)) ;
Dlivrer(M) ;
seq(u) := seq(u) + 1 ;
Dtruire(M) ;
Inconvnient du protocole
un site i peut avoir stocker beaucoup de messages avant de pouvoir les dlivrer et de pouvoir
les dtruire (par exemple si un des messages est trs lent par rapport aux suivants et arrive bien
aprs eux).
Le numro de squence des messages crot au del de toute limite raisonnable si p diuse beaucoup
de messages. C'est un problme de taille de messages.
Ici on utilise explicitement le fait que le rseau ne perd pas de message. Dans le cas contraire,le
protocole peut tre bloqu et ne plus dlivrer de messages.
Pour rsoudre les deux premiers points on peut mettre en place un systme d'acquittements dans
une fentre de taille t fixe. Dans ce systme, le site p fait au plus t diusions de suite avant de
recevoir des acquittements. Chaque fois qu'un site i a pu dlivrer un message, il envoie un acquittement
p, comprenant le numro du message acquitt. Lorsque p a reu les acquittements de tous les sites,
pour les derniers messages envoys non encore acquitts, il peut continuer diuser. Dans ce protocole,
les numros de squence des messages diuss et les numros de squence en rception sont construits
modulo t, en commenant 0. Du coup, les numros de squence ne dpassent pas une certaine valeur et
le deuxime problme est rsolu. Chaque site n'aura stocker qu'au plus t messages avant de les dtruire
et si t est su samment petit, le premier problme est rsolu.
